Programación lineal — método simplex y solución gráfica

La programación lineal es un método para encontrar el mejor valor de una función objetivo lineal, como la ganancia máxima o el costo mínimo, sujeto a restricciones lineales. En un problema de dos variables, la solución gráfica encuentra la región factible y revisa sus puntos extremos. En problemas más grandes, el método simplex usa algebraicamente la misma idea de los puntos extremos.

Usa programación lineal solo cuando la función objetivo y las restricciones sean lineales. Si la relación se dobla, se curva o depende de productos como $xy$, el modelo no es un programa lineal.

Definición de programación lineal

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

sujeto a restricciones como

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

más desigualdades lineales similares, junto con condiciones como $x_i \ge 0$ cuando los valores negativos no tienen sentido.

El conjunto de todos los puntos que satisfacen cada restricción se llama región factible. La programación lineal pregunta: entre esos puntos factibles, ¿cuál da el mejor valor de la función objetivo?

Cómo funciona el método gráfico

Si solo hay dos variables de decisión, puedes dibujar cada restricción en el plano $xy$. La intersección de todas las regiones permitidas es la región factible.

Cada punto de esa región es una solución válida. La función objetivo asigna un valor a cada uno.

En programación lineal, un hecho clave es este: si existe una solución óptima, entonces al menos una solución óptima ocurre en un punto extremo de la región factible. Por eso el método gráfico se centra en los vértices en lugar de revisar cada punto de la región sombreada.

Ejemplo resuelto: resolver un problema de programación lineal gráficamente

Supón que un taller fabrica dos productos, $A$ y $B$.

• Ganancia por unidad de $A$: $3$
• Ganancia por unidad de $B$: $5$
• Límite de tiempo de máquina: cada unidad de $A$ usa $1$ hora, cada unidad de $B$ usa $2$ horas, y hay como máximo $8$ horas disponibles
• Límite de ensamblaje: cada unidad de $A$ usa $1$ hora, cada unidad de $B$ usa $1$ hora, y hay como máximo $5$ horas disponibles

Sea $x$ el número de unidades de $A$ y sea $y$ el número de unidades de $B$.

Maximizar

$$P = 3x + 5y$$

sujeto a

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Encuentra los puntos extremos

A partir de los ejes y de las rectas de restricción, los puntos extremos factibles son

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

El punto $(2,3)$ se obtiene al resolver las ecuaciones de frontera

$$x + 2y = 8,\quad x + y = 5$$

Al restar, se obtiene $y = 3$, y luego $x = 2$.

Prueba la función objetivo en cada vértice

Calcula la ganancia en cada punto extremo:

• En $(0,0)$, $P = 0$
• En $(5,0)$, $P = 15$
• En $(0,4)$, $P = 20$
• En $(2,3)$, $P = 21$

Entonces la ganancia máxima es

$$P = 21$$

en

$$(x,y) = (2,3)$$

Ese es el método gráfico en una sola frase: grafica la región factible, encuentra los puntos extremos y evalúa allí la función objetivo.

Intuición del método simplex

El método gráfico solo es práctico cuando hay dos variables, y a veces tres si estás dispuesto a imaginar una región en 3D. Los problemas reales de optimización suelen tener muchas variables, así que dibujar la región factible deja de ser realista.

El método simplex mantiene la misma lógica de los puntos extremos, pero lo hace algebraicamente. En términos generales, se mueve de un punto extremo factible a otro que mejora la función objetivo, y se detiene cuando ningún movimiento adyacente da un valor mejor.

Así que un buen modelo mental es:

• Método gráfico: ver los puntos extremos
• Método simplex: recorrer los puntos extremos sin dibujarlos

Esta descripción es la intuición, no el algoritmo completo. El procedimiento simplex real usa una tabla o una forma algebraica equivalente para decidir qué variable entra y cuál sale en cada paso.

Por qué importan los puntos extremos

Las funciones objetivo lineales crean rectas de nivel como

$$3x + 5y = k$$

para distintos valores de $k$. A medida que deslizas esa recta en la dirección de mayor ganancia, el último punto donde todavía toca la región factible es donde ocurre el máximo.

En muchas gráficas, ese último contacto ocurre en un solo vértice. Si la recta objetivo es paralela a un lado de la frontera, varios puntos de ese lado pueden ser todos óptimos. En ese caso, sigue habiendo al menos un punto extremo óptimo.

Errores comunes

Confundir factible con óptimo

Un punto puede satisfacer todas las restricciones y aun así no maximizar ni minimizar la función objetivo. Factible solo significa permitido.

Olvidar las condiciones de no negatividad

Si $x$ e $y$ representan cantidades que produces o transportas, los valores negativos normalmente no tienen sentido. Omitir $x \ge 0$ o $y \ge 0$ puede cambiar el problema.

Suponer que toda respuesta debe ser un número entero

La programación lineal básica permite valores fraccionarios. Si las variables deben ser números enteros, como cantidad de camiones o número de trabajadores, necesitas un modelo de programación entera o una condición adicional de integralidad.

Suponer que todo problema tiene una mejor respuesta

Algunos programas lineales son infactibles, lo que significa que ningún punto satisface todas las restricciones. Otros son no acotados, lo que significa que la función objetivo puede mejorar sin límite. Solo obtienes un óptimo finito cuando las restricciones realmente acotan suficientemente el problema.

Usar el método gráfico cuando hay demasiadas variables

Cuando hay muchas variables, graficar ya no es la herramienta adecuada. Ahí es donde el método simplex u otros métodos de optimización se vuelven necesarios.

Cuándo se usa la programación lineal

La programación lineal se usa cuando las decisiones compiten por recursos limitados y tanto el objetivo como las restricciones pueden modelarse linealmente. Algunos ejemplos típicos son la planificación de producción, el transporte, la asignación de personal, las mezclas, la programación de horarios y la distribución de presupuestos.

El modelo es tan bueno como sus supuestos. Si la relación real no es aproximadamente lineal, o si las variables deben ser enteras, un programa lineal básico puede ser solo un punto de partida.

Prueba un problema similar

Toma un problema verbal pequeño con dos productos, dos límites de recursos y una función de ganancia. Define las variables, grafica las restricciones y prueba tú mismo los puntos extremos. Una vez que esa idea haga clic, el método simplex será mucho más fácil de entender porque extiende la misma lógica a dimensiones mayores.