Taller Práctico 2

Solución de problemas LP - Método Simplex

Curso: Técnicas de Optimización

Profesor: Jorge Mario Londoño Peláez

August 26, 2025

1
1 Objetivos del taller
• Dar la solución del problema aplicando los pasos del método simplex
estudiado en clase:

1. Convertir el problema a la forma estandar. Introducir variables

de holgura (slack), exceso, o auxiliares según se necesite.
2. Transcribir el problema al Tableau
3. Establecer una SBF inicial. Considerar casos B = I (trivial),
B ̸= I (utilizar Two-Phase, Big-M)
4. Verificar si la solución actual es óptima o no acotada. En caso
afirmativo terminar.
5. Seleccionar la variable entrante.
6. Identificar la variable saliente.
7. Hacer las reducciones en la tabla. Operaciones pivotear.
8. Volver al paso 4.

• Incorporar el uso de herramientas de software como ‘numpy‘ para au-

tomatizar parcialmente los pasos más importantes del método simplex:
Calcular costos reducidos, realizar operaciones de pivotear filas.

2 Ejercicios a desarrollar
2.1 Ejercicio 1: Maximización con Variables Mixtas y Re-
stricciones Variadas
Una fábrica produce tres tipos de muebles: mesas (M), sillas (S) y estanterı́as
(E). La producción de cada mueble requiere tiempo en el departamento de
corte, ensamblaje y acabado.

• Mesas (M): 3 horas de corte, 4 horas de ensamblaje, 2 horas de

acabado. Beneficio: $60.

• Sillas (S): 2 horas de corte, 3 horas de ensamblaje, 1 hora de acabado.

Beneficio: $40.

• Estanterı́as (E): 4 horas de corte, 2 horas de ensamblaje, 3 horas de

acabado. Beneficio: $70.

2
 La disponibilidad semanal de horas es:
- Corte: Máximo 150 horas.
- Ensamblaje: Al menos 100 horas (debido a un contrato mı́nimo).
- Acabado: Exactamente 80 horas.
Además, la demanda de sillas es ilimitada, pero la producción de mesas
no puede exceder la producción de estanterı́as en más de 10 unidades. La
variable de decisión para la producción de estanterı́as (xE ) puede ser neg-
ativa, lo que indica que se pueden subcontratar estanterı́as (con un costo
asociado que se reflejarı́a en el beneficio como un valor negativo).
Formule y resuelva el problema de programación lineal para maximizar
el beneficio total utilizando el Método Simplex. Asegúrese de manejar la
variable no restringida adecuadamente.
—

2.2 Ejercicio 2: Minimización con Variable No Restringida

Una empresa de alimentos debe producir una mezcla de tres ingredientes:
I1, I2, I3. Cada ingrediente tiene un costo por kilogramo y aporta diferentes
cantidades de nutrientes (N1, N2, N3).

• Ingrediente I1: Costo $5/kg. Aporta: 2 unidades N1, 1 unidad N2

y 2 unidades de N3.
• Ingrediente I2: Costo $7/kg. Aporta: 3 unidades N1, 2 unidades
N2 y 1 unidad de N3.
• Ingrediente I3: Costo $4/kg. Aporta: 1 unidades N1, 3 unidades
N2 y 0 unidades de N3.

Los requisitos de nutrientes para la mezcla final son:

- N1: Al menos 120 unidades.
- N2: Al menos 100 unidades.
- N3: Al menos 80 unidades.

La cantidad de ingrediente I2 (x2 ) puede ser una variable no restringida

en signo, lo que indica que puede haber un ”exceso” o ”déficit” de este
ingrediente que se compensa en el mercado.
Formule y resuelva el problema de programación lineal para minimizar
el costo total de la mezcla, utilizando el Método Simplex. Deberá aplicar el
método de Dos Fases o el Método de la Gran M para encontrar una Solución
Básica Factible inicial, y manejar la variable no restringida adecuadamente.
—

3
2.3 Ejercicio 3: Problema con Casos Especiales
Sujeto a:

Maximize Z = 3x1 + 2x2

subject to 6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x1 , x2 ≥ 0
Resuelva este problema utilizando el Método Simplex e identifique si se
presentan casos especiales de los estudiados en clase.
—

2.4 Ejercicio 4: Problema con Casos Especiales

Una empresa tiene recursos limitados y debe determinar la producción óptima
de dos productos.

Maximize Z = 2x1 + 5x2

subject to x1 + 2x2 ≤ 2
x1 ≤ 2
x2 ≤ 1
x1 , x2 ≥ 0
Resuelva este problema utilizando el Método Simplex. Durante la res-
olución, identifique si se presentan casos especiales y resolver segun corre-
sponda.
—

2.5 Ejercicio 5: Problema con Casos Especiales

Una empresa de transporte tiene un problema de optimización (el cual puede
estar mal formulado).

Maximize Z = 2x1 + x2
subject to − x1 + x2 ≤ 1
x1 − x2 ≤ 1
x1 , x2 ≥ 0

4
 Resuelva este problema utilizando el Método Simplex hasta identificar
el problema que se presenta. Explicar el caso que se presenta y porque el
problema esta mal formulado.

3 Condiciones y Requerimientos:
• Para todos los ejercicios

– Indicar variables de decisión del problema.

– Dar la formulación algebraica del problema.
– Dar la versión estándar del problema e indicar variables adi-
cionales usadas (holgura, exceso, auxiliares, no restringidas).

• Resolución Manual vs. Computacional:

– Ejercicio 1 debe desarrollarse completamente en forma manual

usando el Simplex Tableau paso a paso. Este ejercicio es el más
completo para demostrar el manejo de variables mixtas y restric-
ciones variadas.
– Ejercicios 2-5 pueden desarrollarse usando Notebooks de Python
con librerı́as como NumPy para las operaciones matriciales del pro-
ceso Simplex. Importante: No usar librerı́as especializadas en
LP (como cvxpy, pulp, etc.) para la solución directa de los prob-
lemas.

• Identificación de Casos Especiales: Para cada ejercicio, los estudiantes

deben:

1. Identificar explı́citamente qué caso especial representa el prob-

lema (si aplica): - Problema estándar - Degeneración - Solución
no acotada - Múltiples soluciones óptimas - Infactibilidad
2. Explicar las caracterı́sticas que llevaron a esa identificación
3. Documentar cómo se manejó cada caso especial durante la res-
olución

• Documentación Requerida:

– Mostrar todos los tableaux intermedios

– Justificar cada decisión de variable entrante y saliente

5
 – Explicar cuándo y por qué se aplican reglas especiales (Bland,
Two-Phase, Big-M)
– Interpretar geométricamente el resultado cuando sea posible

4 Rúbrica de Evaluación

Objetivo de 0 (No lo- 1 (Muy 2 (Insufi- 3 (Sufi- 4 (No- 5 (Sobre-

Aprendizaje grado) Insufi- ciente) ciente) table) saliente)
ciente)
1. Formu- No se pre- Identifica Formula el Formula el Formula el Formula el
lación Alge- senta la for- algunas problema problema problema problema
braica del mulación o variables, parcial- correc- de forma de manera
Problema es comple- pero la mente, con tamente, clara y impecable,
tamente in- función errores pero con precisa, con iden-
correcta. objetivo o significa- algún er- identif- tificación
las restric- tivos en ror menor icando exhaustiva
ciones son la función o am- correc- y repre-
incorrectas objetivo o bigüedad tamente sentación
o faltan. varias re- en una todas las algebraica
stricciones restricción. variables, perfecta de
clave. función todos los
objetivo elementos,
y restric- incluyendo
ciones. detalles
sutiles.
2. Conversión No se re- Intenta la Realiza la Convierte Convierte Realiza
a Forma aliza la conversión, conversión el prob- el prob- una con-
Estándar y conversión pero in- con errores lema a lema a versión
Manejo de a forma troduce sustan- forma forma perfecta a
Variables No estándar variables ciales en la estándar estándar la forma
Restringidas o es to- adicionales adición de con correc- estándar,
talmente incorrecta- variables pequeños tamente, con una
errónea. mente o no de hol- errores definiendo com-
maneja las gura/exceso/auxiliares
en la todas las prensión
variables o el manejo definición o variables pro-
no re- de vari- el manejo auxiliares y funda del
stringidas. ables no de las manejando propósito
restringi- variables adecuada- de cada
das es adicionales. mente las variable
incorrecto. Maneja variables adicional y
variables no re- un manejo
no re- stringidas. robusto de
stringidas las vari-
de forma ables no
básica. restringi-
das.

6
3. Apli- No se Intenta Aplica el Aplica el Aplica el Demuestra
cación del aplica el aplicar Simplex Simplex método un dominio
Método Sim- método el Sim- con errores siguiendo Simplex excepcional
plex (Elección Simplex o plex, pero frecuentes la secuen- de forma del método
de Variables, los pasos falla en la en la se- cia de correcta Simplex,
Pivoteo, Itera- son com- mayorı́a lección pasos, pero y sis- ejecutando
ciones) pletamente de los pa- de la con errores temática, todas las
incorrectos. sos clave variable en- ocasionales realizando iteraciones
(elección de trante/saliente en la se- las selec- con pre-
variables, o en las op- lección o en ciones de cisión,
pivoteo). eraciones los cálculos variables eficien-
de pivoteo, de pivoteo. y opera- cia y en-
afectando ciones de tendimiento
la solución pivoteo con de las im-
final. precisión. plicaciones
de cada
paso.
4. Manejo No intenta Reconoce Aplica Aplica Aplica cor- Aplica de
de Solución establecer la necesi- Two- Two- rectamente manera
Básica una SBF dad de Phase/Big- Phase/Big- el método impecable
Factible Ini- inicial o Two- M con M de forma Two-Phase y eficiente
cial (Two- lo hace de Phase/Big- errores aceptable, o Big-M el método
Phase/Big-M) forma com- M, pero la significa- aunque con para en- Two-Phase
pletamente aplicación tivos que algunos contrar o Big-M,
incorrecta es errónea impiden errores la SBF justifi-
cuando o incom- encontrar menores o inicial, de- cando la
B ̸= I. pleta para una SBF inconsis- mostrando elección
establecer correcta. tencias que una com- y de-
una SBF. no impiden prensión mostrando
el avance. sólida de un en-
ambos. tendimiento
profundo
de su
propósito
y limita-
ciones.

7
5. Identi- No iden- Identifica Identifica Identifica Identifica Demuestra
ficación y tifica ni un caso un caso correc- y explica una com-
Manejo de maneja especial especial, tamente claramente prensión
Casos Espe- ningún incorrec- pero la los casos los casos profunda
ciales (De- caso espe- tamente explicación especiales especiales, de los casos
generación, cial pre- o no pro- es pobre o presentes, mostrando especiales,
No Acotado, sente en el porciona el manejo pero la ex- cómo se identi-
Múltiples Sol., problema. ninguna durante plicación es manifes- ficándolos
Infactibilidad) explicación la res- superficial taron en in-
relevante. olución es o el manejo el tableau equı́vocamente,
incorrecto. es incom- y cómo se explicando
pleto. manejaron sus causas
durante el y conse-
Simplex. cuencias, y
aplicando
estrategias
de manejo
(e.g., regla
de Bland)
de forma
experta.
6. Uso de No utiliza Intenta Usa numpy Utiliza Incorpora Integra
Herramientas numpy o usar numpy para al- numpy para numpy de numpy de
de Software lo utiliza pero las im- gunas realizar op- forma manera
(numpy) para incorrecta- plementa- opera- eraciones efectiva elegante y
Operaciones mente sin ciones son ciones, matri- para au- eficiente,
Simplex beneficio. erróneas pero de ciales clave tomatizar mostrando
o no con- forma in- (cálculo las op- un código
tribuyen eficiente de costos eraciones limpio y
a la res- o con er- reducidos, matriciales funcional
olución del rores en la pivoteo), del Sim- que acelera
problema. lógica que pero podrı́a plex, de- y verifica
requieren ser más es- mostrando los cálculos
corrección tructurado una buena del Simplex
manual. o eficiente. com- sin reem-
prensión plazar la
de cómo lógica del
la her- algoritmo.
ramienta
comple-
menta el
método.

8
7. Docu- Sin docu- Presenta Documenta Muestra los Presenta Proporciona
mentación y mentación tableaus algunos tableaus todos los una docu-
Justificación o justi- incom- tableaus, interme- tableaus mentación
(Tableaus, ficación pletos o pero faltan dios y interme- exhaustiva
Decisiones, alguna de incompren- pasos in- justifica las dios de y clara de
Explicaciones) los pasos. sibles; las termedios decisiones forma clara todos los
justifica- cruciales o princi- y justifica tableaus y
ciones de las justi- pales (en- cada de- decisiones,
las deci- ficaciones trante/saliente),
cisión de con justi-
siones son son insu- pero podrı́a variable ficaciones
ausentes. ficientes ser más de- entrante impecables
o poco tallado o y saliente, y expli-
claras. claro. ası́ como la caciones
aplicación concisas y
de reglas precisas.
especiales.
8. Inter- No inter- Intenta Interpreta Interpreta Interpreta Ofrece
pretación de preta los una inter- los re- los re- completa- una inter-
Resultados y resultados pretación, sultados sultados mente la pretación
Presentación o la pre- pero es de forma principales solución profunda y
General sentación incorrecta básica, (solución óptima y matizada
del trabajo o confusa; pero in- óptima, el valor de los re-
es caótica. la pre- completa o valor ob- objetivo, sultados,
sentación con errores; jetivo) y cuando incluyendo
es muy la pre- de forma es posi- sensibili-
deficiente. sentación correcta, ble, ofrece dades (si
es poco y la pre- una inter- aplica)
organizada sentación pretación e impli-
y difı́cil de general es geométrica caciones
seguir. aceptable. clara. prácticas.
La pre- La pre-
sentación sentación
es profe- es ejem-
sional y plar, co-
fácil de herente y
seguir. estéticamente
agradable.