La programación lineal no es sólo matemática abstracta. Es el motor detrás de la logística, las cadenas de suministro y la gestión de recursos. En esencia, se encuentra el método simplex. Esta técnica estándar encuentra el mejor resultado posible en un sistema definido por restricciones y una función objetivo.
Piénselo de esta manera. Tienes un objetivo. Tal vez sea maximizar las ganancias o minimizar los costos. Tú también tienes límites. Horas máquina. Materias primas. Mano de obra. El método simplex navega por estos límites para encontrar el pico. No adivina. Calcula.
Por qué necesitamos un enfoque sistemático
Podrías pensar que puedes simplemente graficar dos variables y ver dónde se cruzan. Eso funciona para problemas simples. Una fábrica que fabrica dos productos. Dibujas líneas. Encuentra el rincón donde las ganancias alcanzan su punto máximo. Es visual. Es intuitivo.
Pero la realidad rara vez es bidimensional. Los problemas reales implican cientos de ecuaciones y miles de variables. El número de posibles soluciones se vuelve astronómico. Dibujar una gráfica para mil variables es imposible. Necesitarías dimensiones que no puedes percibir.
George Dantzig resolvió esto en 1947. Trabajaba como asesor matemático para la Fuerza Aérea de Estados Unidos. Los militares tuvieron enormes problemas logísticos. Necesitaban optimizar las rutas de suministro y la asignación de recursos. Dantzig ideó el método simplex para eliminar el ruido.
El método restringe el número de puntos extremos que deben examinarse. Convierte una tarea imposible en una manejable. Sigue siendo el algoritmo estándar en las computadoras actuales. Una de las herramientas más útiles jamás inventadas.
Cómo funciona el método Simplex paso a paso
El proceso es sistemático. Se pasa de una posibilidad a la siguiente. Así es como se desarrolla en la práctica.
Primero, se supone que tienes un punto de partida. Un punto extremo. Si no tiene uno, una variante llamada Fase I encuentra un punto de partida factible o determina que no existe una solución.
A continuación, el método prueba ese punto. ¿Es óptimo? La especificación algebraica del problema ejecuta esta verificación. Si la prueba falla, el algoritmo se mueve a un punto extremo adyacente. Se mueve a lo largo de un borde. Elige la dirección en la que la función objetivo aumenta al ritmo más rápido.
A veces la función aumenta sin límite. El procedimiento se detiene e identifica el borde donde el valor llega al infinito positivo. Ha encontrado una solución ilimitada.
Si eso no sucede, aterrizarás en un nuevo punto extremo. Este punto tiene al menos un valor tan alto como el anterior. La secuencia se repite. Continúa hasta que encuentra un punto óptimo o identifica lo ilimitado.
En teoría, los pasos podrían crecer exponencialmente con el número de puntos extremos. En la práctica, la convergencia es rápida. Por lo general, sólo se necesita un pequeño múltiplo del número de puntos extremos.
Un ejemplo concreto: maximizar las ganancias de la fábrica
Veamos un caso tangible. Una fábrica produce dos productos. Los llamamos x1 y x2. El beneficio del segundo tipo es el doble que el del primero. La ganancia total está representada por la ecuación:
x1 + 2×2
Esta es su función objetivo. Quieres maximizarlo.
Naturalmente, querrás ganar sólo x2. Genera más dinero por unidad. Pero existen limitaciones. No se puede simplemente producir infinitamente.
Estos son los límites del mundo real:
- La materia prima para x2 limita la producción a cinco unidades por lote (x2 ≤ 5).
- La materia prima para x1 limita la producción a ocho unidades por lote (x1 ≤ 8).
- El tiempo de la máquina permite un máximo de diez unidades totales (x1 + x2 ≤ 10).
- No se pueden producir cantidades negativas (x1 ≥ 0 y x2 ≥ 0).
El método simplex encuentra los valores de x1 y x2 que maximizan el beneficio dentro de estos límites. Cualquier solución es un par de números (x1, x2). Por ejemplo, producir tres de x1 y seis de x2 es un punto válido (3, 6).
Cuando se representan en un gráfico, estas restricciones forman una región poligonal. Este es el conjunto de soluciones factibles. Los puntos fuera de esta región violan una o más restricciones.
Para ver cómo el método simplex identifica el vértice óptimo, considere la función objetivo x1 + 2×2 = k. Si estableces k en 4, obtendrás una línea en el gráfico. A medida que aumentas k, obtienes líneas paralelas. El valor más alto de k que todavía toca la región factible es el máximo beneficio posible.
En este ejemplo, la línea para k = 15 toca la región en el punto (5, 5). Si k es mayor, la línea queda fuera del conjunto factible. La solución óptima es producir cantidades iguales de cada bien.
Por qué son importantes los vértices en la programación lineal
El resultado no es una coincidencia. En problemas lineales, la solución óptima siempre ocurre en un vértice. Un punto extremo.
Esta es una propiedad fundamental de la programación lineal. La función es lineal. Las restricciones son lineales. La forma es un polígono convexo (o poliedro en dimensiones superiores). El pico de una función lineal sobre un conjunto convexo siempre está en una esquina.
No es necesario comprobar todos los puntos de la región factible. Sólo necesitas comprobar los vértices. El método simplex hace exactamente esto. Salta de vértice en vértice. Sube a la superficie de la región factible. Se detiene cuando no puede subir más.
A veces lo óptimo no es único. Un borde completo podría producir el mismo valor máximo. Pero el método simplex seguirá encontrando uno de esos puntos óptimos. Te da una respuesta concreta. Datos procesables.
Tanto para estudiantes como para profesionales, comprender esta mecánica es clave. No se trata sólo de resolver ecuaciones. Se trata de saber navegar en sistemas complejos con recursos limitados. El método simplex proporciona el camino.
El método simplex no se limita a adivinar respuestas. Camina por los bordes de una región factible, comprobando los vértices hasta encontrar el mejor. Comienza limpiando las matemáticas. Se toman esas desordenadas desigualdades lineales y se las convierte en igualdades limpias. Para ello, agregue “variables de holgura”.
Piense en la holgura como capacidad sobrante. Si tiene una restricción como $x_1 \le 8$, agrega una variable $x_3$ tal que $x_1 + x_3 = 8$. Y recuerda, $x_3$ debe ser mayor o igual a cero. Esto se hace para cada restricción.
- $x_1 + x_3 = 8$ (con $x_3 \ge 0$)
- $x_2 + x_4 = 5$ (con $x_4 \ge 0$)
- $x_1 + x_2 + x_5 = 10$ (con $x_5 \ge 0$)
También necesita una variable para la función objetivo en sí. Llamémoslo $x_0$. Si su objetivo es maximizar $x_0 = x_1 + 2x_2$, lo reescribe como $x_1 + 2x_2 – x_0 = 0$.
Ahora el problema es más sencillo. Encuentre valores no negativos para $x_1$ hasta $x_5$. Haz que $x_0$ sea lo más grande posible.
Comenzando en el origen
¿Por dónde empiezas? El lugar más fácil es el origen. Establezca todas las variables de decisión en cero. $x_1 = 0$. $x_2 = 0$.
Esta es una solución válida. Es un punto extremo. De hecho, es la esquina inicial. El valor objetivo $x_0$ también es cero. No es genial, pero es una medida legal.
¿Podemos hacerlo mejor? Sí. Si aumenta una de las variables desde cero mientras mantiene la otra en cero, $x_0$ aumenta. La pregunta es qué variable le ofrece el mayor rendimiento por su inversión.
Mira la ecuación objetiva: $x_1 + 2x_2 – x_0 = 0$. Reorganizando para $x_0$, obtienes $x_0 = x_1 + 2x_2$.
Aumentar $x_1$ suma 1 al total. Aumentar $x_2$ suma 2. $x_2$ es el claro ganador. Produce el mayor aumento en $x_0$ por cambio de unidad. Entonces, eliges $x_2$ y lo empujas hacia arriba.
Alcanzar la primera restricción
No puedes aumentar $x_2$ para siempre. Las variables deben permanecer no negativas. Si empujas $x_2$ más allá de 5, algo se rompe. Específicamente, observe la segunda restricción: $x_2 + x_4 = 5$.
Si $x_2 = 6$, entonces $x_4$ se convierte en -1. Eso no está permitido. El requisito de no negatividad actúa como un freno estricto. El límite es 5.
Entonces estableces $x_2 = 5$. ¿Cómo es la solución ahora?
- $x_2 = 5$
- $x_1 = 0$ (aún cero)
- $x_4 = 0$ (esta variable alcanzó el límite, por lo que ahora es cero)
- $x_3 = 8$ (ya que $0 + 8 = 8$)
- $
