Programación lineal y método Simplex

"Si podés expresar tu problema con sumas y multiplicaciones por constantes, podés resolverlo con Simplex. Y si podés resolverlo con Simplex, podés resolverlo rápido."

Qué vas a aprender en este capítulo

La programación lineal (PL) es el subconjunto de IO donde el objetivo y todas las restricciones son funciones lineales. Es el caso más estudiado, el más útil en la práctica y donde el algoritmo Simplex brilla.

En este capítulo vas a:

Entender qué hace un PL geométricamente.
Convertir cualquier problema a forma estándar.
Ejecutar Simplex a mano para problemas chicos (entender el algoritmo te ayuda a interpretar resultados).
Resolver con software (scipy, Pyomo).
Reconocer casos especiales: óptimo en arista, no acotado, infactible, degenerado.

2.1 La forma geométrica

💡 Intuición

Cada restricción $a_1 x_1 + a_2 x_2 \leq b$ define un semi-plano. La intersección de todas las restricciones es un polígono convexo llamado región factible — es el conjunto de soluciones posibles.

La función objetivo $Z = c_1 x_1 + c_2 x_2$ , vista como recta $c_1 x_1 + c_2 x_2 = Z$ , se desplaza paralelamente al variar $Z$ . Maximizar $Z$ es empujar la recta lo más lejos posible sin salir del polígono.

Teorema fundamental: el óptimo de un PL siempre se alcanza en un vértice del polígono (o en una arista entera, si hay óptimos múltiples).

Eso convierte un problema continuo en uno finito: solo hay que revisar los vértices.

En 2D lo dibujás. En 3D, todavía imaginás. En 50D... ya no — pero el principio se mantiene. Simplex es justamente saltar inteligentemente entre vértices hasta el óptimo.

📝 Ejemplo geométrico — la pupusería del cap. 1

Modelo del cap. 1:

\max Z = 0.50 x_1 + 0.65 x_2

\text{s.a.} \quad x_1 + x_2 \leq 100,\; 30 x_1 + 20 x_2 \leq 2000,\; x_2 \leq 50,\; x_1 \geq 30,\; x_1, x_2 \geq 0

Región factible (en el plano $x_1$ - $x_2$ ):

x_2
50 ┤      ┌──────┐
   │      │      │
   │ A    │  C   │
   │      │      │
   │      │      │
   │      │      │
 0 └──────┴──────┴──────── x_1
   0    30    66.67   100

Vértices (intersecciones de restricciones activas):

Vértice	$(x_1, x_2)$	$Z$
A	$(30, 0)$	15.00
B	$(30, 50)$	47.50
C	$(40, 40)$	46.00
D	$(66.67, 0)$	33.33
E	$(30, 55)$	NO factible (excede masa)

¡Cuidado! B = (30, 50) viola la restricción de queso: $30 \cdot 30 + 20 \cdot 50 = 900 + 1000 = 1900 \leq 2000$ ✓. Y masa $30 + 50 = 80 \leq 100$ ✓. Vértice válido. $Z = 15 + 32.50 = 47.50$ .

Comparando los Z, B = (30, 50) es el óptimo con $Z = 47.50$ . (El cap. 1 había dicho $(40, 40)$ ; corrijo: la solución óptima es B.)

Lección: enumerar vértices funciona en 2D. Para $n$ variables y $m$ restricciones, hay hasta $\binom{n+m}{m}$ vértices — explota rápido. Simplex no enumera todos.

2.2 Forma estándar

📐 Fundamento

Para correr Simplex, el modelo debe estar en forma estándar:

Función objetivo de maximización (si era minimización, multiplicás por $-1$ ).
Todas las restricciones son igualdades.
Todas las variables son no negativas.
Lado derecho ( $b_i$ ) no negativo.

Convertir $\leq$ a igualdad: variables de holgura

$a x_1 + b x_2 \leq c \quad \Rightarrow \quad a x_1 + b x_2 + s = c,; s \geq 0$

$s$ es la holgura (slack): cuánto recurso sobra. En la pupusería, si gastás 4800 g de masa de los 5000 disponibles, la holgura de la restricción de masa es $200$ .

Convertir $\geq$ a igualdad: variables de exceso (+ artificial)

$a x_1 + b x_2 \geq c \quad \Rightarrow \quad a x_1 + b x_2 - e + A = c,; e, A \geq 0$

$e$ = exceso (cuánto te pasaste del mínimo).
$A$ = variable artificial, necesaria para tener una base inicial. Se penaliza en el objetivo (método de la Gran-M) o se elimina al final.

Convertir minimización a maximización

$\min c^T x \Leftrightarrow -\max(-c)^T x$ . Al final, multiplicás $Z$ óptimo por $-1$ .

Variables libres

Si una variable $x$ puede ser negativa (ej: variación de stock), la escribís como $x = x^+ - x^-$ con $x^+, x^- \geq 0$ .

📝 Ejemplo — Estandarizar la pupusería

Original:

\max Z = 0.50 x_1 + 0.65 x_2

x_1 + x_2 \leq 100,\quad 30 x_1 + 20 x_2 \leq 2000,\quad x_2 \leq 50,\quad x_1 \geq 30,\quad x_j \geq 0

Estándar:

\max Z = 0.50 x_1 + 0.65 x_2 - M A_1

$$ \begin{aligned} x_1 + x_2 + s_1 &= 100 \ 30 x_1 + 20 x_2 + s_2 &= 2000 \ x_2 + s_3 &= 50 \ x_1 - e_1 + A_1 &= 30 \ x_1, x_2, s_1, s_2, s_3, e_1, A_1 &\geq 0 \end{aligned} $$

El $-M A_1$ penaliza fuertemente $A_1$ para que el algoritmo lo expulse de la base.

2.3 El algoritmo Simplex

📐 Fundamento

Idea: parte de un vértice de la región factible, y en cada iteración salta a un vértice adyacente que mejora el objetivo, hasta que ningún vecino mejore — ese es el óptimo.

Las tablas Simplex

Representamos el sistema como tabla:

Base	$x_1$	$x_2$	$s_1$	$s_2$	RHS
$s_1$	$a_{11}$	$a_{12}$	1	0	$b_1$
$s_2$	$a_{21}$	$a_{22}$	0	1	$b_2$
Z	$-c_1$	$-c_2$	0	0	0

La base son las variables actualmente en la "solución" (las demás valen 0).
La fila Z lleva los coeficientes negados del objetivo.

Pasos del Simplex

¿Es óptimo? Si todos los coeficientes en la fila Z son $\geq 0$ , sí. Fin.
Si no, elegir variable entrante: la más negativa en la fila Z (es la que más crece $Z$ por unidad).
Elegir variable saliente con la razón mínima: para cada fila con $a_{ij} > 0$ en la columna entrante, calcular $b_i / a_{ij}$ . La fila con razón mínima positiva sale.
Pivote: dividir la fila saliente por el pivote (para que valga 1). Luego restar múltiplos de esa fila a las demás para hacer 0 la columna entrante en otras filas.
Volver al paso 1.

Visualmente: cada iteración te lleva al siguiente vértice.

Convergencia

Simplex converge en un número finito de pasos en la mayoría de los casos. Peor caso teórico: exponencial (Klee-Minty 1972), pero en práctica es rapidísimo: típicamente $O(m)$ iteraciones para $m$ restricciones, con cada iteración $O(mn)$ .

📝 Ejemplo trabajado — Simplex paso a paso

Modelo simplificado (sin restricción $x_1 \geq 30$ para mantenerlo corto):

\max Z = 3 x_1 + 5 x_2

x_1 + x_2 \leq 8,\; x_1 \leq 5,\; x_2 \leq 6,\; x_j \geq 0

Forma estándar:

x_1 + x_2 + s_1 = 8,\; x_1 + s_2 = 5,\; x_2 + s_3 = 6

Tabla inicial:

Base	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS
$s_1$	1	1	1	0	0	8
$s_2$	1	0	0	1	0	5
$s_3$	0	1	0	0	1	6
Z	-3	-5	0	0	0	0

Iteración 1:

Más negativa: $-5$ , entra $x_2$ .
Razones: $s_1: 8/1 = 8$ , $s_2:$ N/A, $s_3: 6/1 = 6$ . Mínima = $s_3$ sale.
Pivote $(s_3, x_2)$ .

Nueva tabla:

Base	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS
$s_1$	1	0	1	0	-1	2
$s_2$	1	0	0	1	0	5
$x_2$	0	1	0	0	1	6
Z	-3	0	0	0	5	30

Iteración 2:

Más negativa: $-3$ , entra $x_1$ .
Razones: $s_1: 2/1 = 2$ , $s_2: 5/1 = 5$ , $x_2:$ N/A. Mínima = $s_1$ sale.
Pivote $(s_1, x_1)$ .

Nueva tabla:

Base	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS
$x_1$	1	0	1	0	-1	2
$s_2$	0	0	-1	1	1	3
$x_2$	0	1	0	0	1	6
Z	0	0	3	0	2	36

Todos los coeficientes de Z son $\geq 0$ → óptimo.

Solución: $x_1 = 2$ , $x_2 = 6$ , $Z = 36$ . Variables de holgura: $s_1 = 0$ (masa saturada), $s_2 = 3$ (sobra capacidad de $x_1$ ), $s_3 = 0$ ( $x_2$ saturada).

2.4 Resolución con software

🛠️ Aplicado

En la práctica, nadie resuelve Simplex a mano más allá de 3 variables. Para problemas reales: software.

Excel Solver

Free, intuitivo. Ideal para problemas chicos y para mostrar resultados a stakeholders.

Datos > Solver (puede requerir activar el complemento).
Definir celda objetivo, celdas cambiantes, restricciones.
Método "LP Simplex".

Python — scipy

from scipy.optimize import linprog

c = [-3, -5]                              # max → negar
A_ub = [[1, 1], [1, 0], [0, 1]]
b_ub = [8, 5, 6]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None)]*2, method='highs')

print("x =", res.x, "Z =", -res.fun)

method='highs' usa el solver HiGHS (mejor que el viejo Simplex de scipy).

Python — PuLP (más expresivo)

import pulp

m = pulp.LpProblem("pupuseria", pulp.LpMaximize)
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)

m += 0.50*x1 + 0.65*x2                    # objetivo
m += x1 + x2 <= 100                       # masa
m += 30*x1 + 20*x2 <= 2000                # queso
m += x2 <= 50                             # chicharrón
m += x1 >= 30                             # contrato

m.solve()
print(f"x1={x1.value()}, x2={x2.value()}, Z={pulp.value(m.objective)}")

PuLP traduce a forma estándar internamente, llama a un solver (CBC por defecto, gratis), y devuelve la solución.

Gurobi/CPLEX

Comerciales. 10-1000× más rápidos que CBC. Necesarios para problemas industriales con millones de variables. Licencia académica gratuita.

2.5 Casos especiales

📐 Fundamento

Óptimos múltiples

Si la función objetivo es paralela a una arista del polígono, toda la arista es óptima. Simplex devuelve un vértice, pero existen infinitas combinaciones igualmente buenas.

Cómo detectarlo: en la solución óptima, alguna variable no básica tiene coeficiente $0$ en la fila Z. Significa que entrarla no cambia $Z$ .

En la práctica: podés elegir entre soluciones óptimas según criterios secundarios (preferencia operativa, robustez).

Solución no acotada

La región factible se extiende al infinito en la dirección de mejora. $Z \to \infty$ . Simplex detecta esto cuando, al elegir variable entrante, todos los $a_{ij}$ en su columna son $\leq 0$ (la razón mínima no existe).

En la realidad: indica que te faltó una restricción. La realidad no permite producción infinita.

Infactibilidad

No existe ningún punto que cumpla todas las restricciones. Polígono vacío.

Cómo detectarlo: al final del Simplex, alguna variable artificial sigue en la base con valor $> 0$ .

En la realidad: las restricciones son contradictorias. Hay que relajar alguna (subir capacidad, bajar mínimos contractuales).

Degeneración

Una variable básica vale 0 (un vértice donde se cruzan más de $n$ restricciones). Puede causar ciclos en Simplex (repetir vértices sin avanzar). Reglas de desempate (Bland's rule) lo evitan.

2.6 Errores comunes

⚠️ Trampa común

Olvidar negar coeficientes al maximizar con linprog. scipy.optimize.linprog minimiza por default. Si tu objetivo es maximización y no negás los coeficientes, obtenés la solución que minimiza los ingresos — exactamente lo opuesto.

Tip: convención: siempre c = [-c1, -c2, ...] para maximizar, y reportar -res.fun como valor óptimo.

⚠️ Trampa común

Modelar variables continuas cuando deben ser enteras. "Producir 40.5 pupusas" no tiene sentido. Si la cantidad es chica, redondear puede dar resultados muy distintos del óptimo entero real.

Tip: si el dominio es naturalmente entero (unidades vendibles, trabajadores asignados), usá programación entera (cap. 4). PL continua solo si la fracción tiene interpretación física (kg, horas) o si las unidades son grandes ( $x = 10^6$ y el error de redondeo es despreciable).

⚠️ Trampa común

Restricciones redundantes. Agregar 10 restricciones equivalentes "por seguridad". No hace daño matemáticamente pero vuelve la solución lenta y dificulta el análisis de sensibilidad (cap. 3).

Tip: revisá el modelo en busca de restricciones que sean consecuencia de otras. Ejemplo: si decís "demanda mínima 30" y "capacidad máxima 100", no hace falta agregar "producción $\leq 1000$ " — ya está implícita.

2.7 Resumen visual

Problema verbal
      │
      ▼
Modelo PL (variables, objetivo, restricciones)
      │
      ▼
Forma estándar (holguras, exceso, artificiales)
      │
      ▼
   Simplex
   ┌───────────────┐
   │ Tabla inicial │
   └──────┬────────┘
          │ pivot until optimal
          ▼
   ┌───────────────┐
   │   Óptimo /    │  ← interpretar:
   │   Múltiple /  │     variables, holguras,
   │  No acotado / │     Z final
   │  Infactible   │
   └───────────────┘

2.8 Ejercicios

Convertí a forma estándar:

\min Z = 2x_1 - 3x_2,\quad x_1 + x_2 \geq 4,\; 2x_1 - x_2 \leq 6,\; x_1, x_2 \geq 0

Resolvé geométricamente (ploteá la región factible y vértices):

\max Z = 4x_1 + 3x_2,\quad 2x_1 + x_2 \leq 12,\; x_1 + 2x_2 \leq 10,\; x_j \geq 0

Ejecutá Simplex paso a paso (al menos 2 iteraciones) sobre el problema anterior.
Implementá el ejercicio 2 en scipy.optimize.linprog y validá el resultado.
Construí un modelo PL donde el óptimo sea múltiple (objetivo paralelo a restricción). Mostralo con software.
Construí uno no acotado. ¿Qué restricción agregarías para hacerlo realista?

2.9 Para profundizar

Vanderbei, Linear Programming: Foundations and Extensions — el moderno standard.
Bertsimas & Tsitsiklis, Introduction to Linear Optimization — MIT, riguroso.
HiGHS (highs.dev) — solver open source más rápido en 2026.
PuLP docs (coin-or.github.io/pulp) — la forma más amigable de usar PL en Python.
Siguiente capítulo: Dualidad y análisis de sensibilidad.

2.10 Mini-proyecto integrador

🏗️ Avance del proyecto — Resolvé tu caso con PL

Continuación del proyecto del cap. 1.

Entregables (cap. 2):

Modelo PL formal del caso elegido — variables, objetivo, todas las restricciones.
Forma estándar con holguras/exceso/artificiales.
Resolver en software — PuLP o scipy. Mostrá código completo.
Solución óptima — valores de las variables, valor de Z, holguras.
Interpretación de negocios — explicá la solución en 1 párrafo legible.
Validación de cordura — ¿la solución tiene sentido? ¿Algún valor te sorprende? ¿Por qué?

Criterio de éxito: podés explicar a un no-matemático qué dice el modelo y por qué creés su solución.

Tiempo estimado: 2-3 horas.

Definiciones nuevas: programación lineal, región factible, polígono convexo, vértice de la región, función objetivo, forma estándar, variable de holgura (slack), variable de exceso (surplus), variable artificial, método de la Gran M, tabla Simplex, variable entrante, variable saliente, pivote, razón mínima, óptimos múltiples, solución no acotada, infactibilidad, degeneración.

← Anterior Fundamentos de Investigación de Operaciones Siguiente → Dualidad y análisis de sensibilidad

Reportar error en este capítulo · Patrocinar este libro

Programación lineal y método Simplex

Qué vas a aprender en este capítulo

2.1 La forma geométrica

2.2 Forma estándar

Convertir ≤\leq≤ a igualdad: variables de holgura

Convertir ≥\geq≥ a igualdad: variables de exceso (+ artificial)

Convertir minimización a maximización

Variables libres

2.3 El algoritmo Simplex

Las tablas Simplex

Pasos del Simplex

Convergencia

2.4 Resolución con software

Excel Solver

Python — scipy

Python — PuLP (más expresivo)

Gurobi/CPLEX

2.5 Casos especiales

Óptimos múltiples

Solución no acotada

Infactibilidad

Degeneración

2.6 Errores comunes

2.7 Resumen visual

2.8 Ejercicios

2.9 Para profundizar

2.10 Mini-proyecto integrador

Convertir $\leq$ a igualdad: variables de holgura

Convertir $\geq$ a igualdad: variables de exceso (+ artificial)