Para la solución gráfica de programas lineales con dos variables, lo que se tiene que hacer es trazar un eje de coordenadas cartesianas, para graficar las desigualdades dadas por el problema, después encontrar el Área de Soluciones Factibles y proceder a graficar la función objetivo para conocer el valor óptimo (maximizar o minimizar) que será la solución del problema.

Un fabricante está tratando de decidir sobre las cantidades de producción para dos artículos: mesas y sillas. Se cuenta con 96 unidades de material y con 72 horas de mano de obra. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. Por otra parte, las sillas usan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla. El margen de contribución es el mismo para las mesas que para las sillas: $5.00 por unidad. El fabricante prometió construir por lo menos dos mesas.

El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL. ¿Cuál es el objetivo? Es maximizar la contribución a la ganancia. Cada unidad de mesas o sillas producidas contribuirá con $5 en la ganancia. Así las dos alternativas son la producción de mesas y la producción de sillas. Ahora puede escribirse la función objetivo:

Maximizar  Z = 5x₁ + 5x₂

en donde: x₁ = número de mesas producidas

x₂ = número de sillas producidas

¿Cuáles son las restricciones o limitaciones del problema? Existen tres restricciones. Primero, el material está limitado a 96 unidades. Cada mesa se lleva 12 unidades de material y cada silla usa 8 unidades. La primera restricción es, entonces:

12x₁ + 8x₂ £ 96

La segunda restricción es el total de horas de mano de obra. Una mesa se lleva 6 horas, una silla 12 horas y se dispone de un total de 72 horas. Así:

6x₁ + 12x₂ £ 72

Existe una limitación más. El fabricante prometió producir por lo menos dos mesas. Esto puede expresarse como:

x₁ ³ 2

Por último, las restricciones de no negatividad son:

x₁ ³ 0, x₂ ³ 0

Poniendo todo junto el modelo se tiene:

Maximizar  Z = 5x₁ + 5x₂

Restricciones:

12x₁ + 8x₂ £ 96 6x₁ + 12x₂ £ 72 x₁ ³ 2 x₁ ³ 0, x₂ ³ 0

El siguiente paso en el método gráfico es dibujar todas las restricciones en una gráfica. Esto puede hacerse en cualquier orden. Por conveniencia se comenzará con las restricciones de no negatividad. Éstas se muestran en la siguiente figura:

En esta gráfica, una solución se representaría por un punto con coordenadas x₁ (mesas) y x₂ (sillas). Las coordenadas representarían las cantidades de cada artículo que se deben producir. El cuadrante superior derecho se llama Región Factible puesto que es el único cuadrante en que pueden estar las soluciones. Los otros tres cuadrantes no son factibles, ya que requerirían la producción de cantidades negativas de mesas o de sillas o de ambas.

La siguiente restricción es x₁ ³ 2. La manera más sencilla de dibujar las restricciones de recursos es en dos pasos: (1) convertir una desigualdad en una ecuación y graficar la ecuación y (2) sombrear el área apropiada arriba y abajo de la línea que resulta en el paso 1. Convertir una igualdad en una ecuación aquí significa ignorar la parte de "mayor que" o "menor que" de la restricción.

Así, en el ejemplo, x₁ ³ 2 se convierte en x₁ = 2. Esta ecuación está trazada en la siguiente figura:

Cualquier punto en la línea x₁ = 2 satisface la ecuación. Sin embargo, la restricción es más amplia, ya que cualquier punto x₁ > 2 también la cumplirá. Esto incluye todos los puntos que están a la derecha de la línea x₁ = 2. Entonces, la región factible incluye todos los valores de x₁ que están sobre o a la derecha de la línea x₁ = 2.

La limitación sobre las horas de mano de obra es la siguiente restricción. Como antes, primero se convierte en una ecuación: 6x₁ + 12x₂ = 72. Puede graficarse esta línea si se encuentran dos puntos sobre ella. El par de puntos más sencillos de localizar son las intersecciones con los ejes X₁ y X₂. Para encontrar la intersección con el eje X₂ se hace x₁ = 0. La ecuación se reduce, entonces, a:

12x₂ = 72 x₂ = 6 La intersección con el eje X₁ se encuentra haciendo x₂ = 0. Así: 6x₁ = 72 x₁ =12

Estos dos puntos y la línea que los une se muestran en la siguiente figura:

Cualquier punto que está sobre o abajo de esta línea cumplirá con la restricción. Cualquier punto arriba de esta línea requerirá más de 72 horas de mano de obra y no es aceptable. En la siguiente figura se combina esta restricción con la anterior. En la región factible, ambas restricciones se cumplen.

La última restricción es la de material. Siguiendo el procedimiento anterior, primero se encuentran las intersecciones para la igualdad. Éstas son x₁ = 0, x₂ = 12 y x₁ = 8, x₂ =0. Se localizan los dos puntos en la gráfica; se traza la línea, y como la restricción es del tipo menor o igual que, se sombrea el área que está abajo de la línea. El resultado se muestra en la siguiente figura:

Cualquier solución que esté en la frontera o dentro del área sombreada cumplirá con todas las restricciones. Ahora se utilizará la función objetivo para seleccionar la solución óptima.

Para encontrar la solución óptima, se grafica la función objetivo en la misma gráfica de las restricciones. La función objetivo en este problema es Z = 5x₁ + 5x₂. Como todavía no se conoce el máximo valor factible de Z, no puede trazarse el óptimo de la función objetivo. No obstante, es posible suponer algunos valores para Z y graficar las líneas resultantes. En la siguiente figura se muestran las líneas para Z = 25 yZ = 50:

Las líneas de este tipo se llaman líneas de indiferencia, porque cualquier punto sobre una línea dada da la misma ganancia total. Nótese que la distancia perpendicular del origen a la línea aumenta al aumentar el valor de Z. También, todas las líneas de indiferencia son paralelas entre sí. Estas propiedades gráficas pueden usarse para resolver el problema.

En la siguiente figura, se ilustran todas las restricciones y las dos líneas de indiferencia supuestas. En la gráfica puede observarse que la línea de indiferencia para Z = 50 está completamente fuera de la región factible. Para Z = 25, parte de la línea cae dentro de la región factible. Por tanto, existe alguna combinación de x₁ y x₂ que satisface todas las restricciones y da una ganancia total de $25. Por inspección, puede observarse que hay ganancias más altas que son factibles.

Imaginando que la línea de indiferencia Z = 25 se mueve hacia la línea Z = 50, de las propiedades de la gráfica que se hicieron notar antes, el punto óptimo estará sobre la línea de indiferencia más lejana al origen pero que todavía toque la región factible. Esto se muestra en la siguiente figura:

Con el punto óptimo localizado gráficamente, la única tarea que queda es encontrar las coordenadas del punto. Nótese que el punto óptimo está en la intersección de las líneas de restricción para materiales y horas de mano de obra. Las coordenadas de este punto se pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones utilizando cualquiera de los métodos de solución (suma y resta, sustitución o igualación). Las coordenadas de este punto resultan ser (6, 3). La sustitución de este punto en la función objetivo da la ganancia máxima:

Z = 5(6) + 5(3) = $45

Para resolver gráficamente problemas de programación lineal:

 

1. Exprésense los datos del problema como una función objetivo y restricciones.

    

   Grafíquese cada restricción. Localícese la solución óptima.

Consideremos un Problema de PL en el cual el objetivo es minimizar costos. La solución del problema de minimización sigue el mismo procedimiento que la de problemas de maximización. La única diferencia es que ahora se quiere el menor valor posible para la función objetivo. Supóngase que se tiene el siguiente problema:

Un comprador está tratando de seleccionar la combinación más barata de dos alimentos, que debe cumplir con ciertas necesidades diarias de vitaminas. Los requerimientos vitamínicos son por lo menos 40 unidades de vitamina W, 50 unidades de vitamina X y 49 unidades de vitamina Y. Cada onza del alimento A proporciona 4 unidades de vitamina W, 10 unidades de vitamina X y 7 unidades de vitamina Y; cada onza del alimento B proporciona 10 unidades de W, 5 unidades de X y 7 unidades de Y. El alimento A cuesta 5 pesos/kilogramo y el alimento B cuesta 8 pesos/kilogramo.

La meta en este problema es encontrar la manera menos costosa para satisfacer las necesidades vitamínicas. Las dos alternativas disponibles son los alimentos A y B. Matemáticamente la función objetivo es:

Minimizar Z = 5A + 8B

Las restricciones son los requerimientos mínimos de las tres vitaminas. Éstas se muestran enseguida:

Restricciones: 4A + 10B ³ 40 vitamina W 10A + 5B ³ 50 vitamina X 7A + 7B ³ 49 vitamina Y A ³ 0, B ³ 0 no negatividad

El procedimiento para graficar es el mismo que se usó antes: (1) graficar cada ecuación de restricción; (2) graficar el área apropiada. Para la primera restricción la ecuación es 4A + 10B = 40. Las dos intersecciones con los ejes son (0,4) y (10,0). Esta línea se muestra en la siguiente figura:

La restricción pide 40 unidades o más de la vitamina W. Cualquier punto que esté arriba de la línea de restricción será factible y todos los puntos que quedan abajo de esa línea serán aceptables. En la siguiente figura se muestra la región factible:

Después se grafica la restricción para la vitamina X. La ecuación 10A + 5B = 50 tiene intersecciones con los ejes en (0,10) y (5,0). En la siguiente figura se ilustran las restricciones para las vitaminas W y X. Nótese que las soluciones que quedan en las áreas a o b no son factibles, ya que quedarían abajo de las líneas de restricción.

Al agregar la tercera restricción, este segundo paso queda terminado, como se muestra en la siguiente figura:

En la siguiente figura se muestra la frontera extrema más dos líneas de indiferencia, las de Z = 40 pesos y Z = 60 pesos. La frontera extrema está formada por los puntos a, b, c y d, puesto que éstos son los puntos de intersección factibles más cercanos al origen.

Gráficamente, el objetivo de minimizar el valor de Z significa ajustar una línea de indiferencia tan cerca del origen como sea posible. En la figura anterior puede observarse que existen muchas soluciones posibles para Z = 60, pero ninguna para Z = 40. Imaginando mover la línea Z = 60 hacia el origen, el último punto de contacto con la frontera extrema será el punto b. Entonces, el punto b es la solución óptima. En la figura anterior se observa que el punto b es la intersección de dos líneas:

(1) 4A + 10B = 40

(2) 7A + 7B = 49

Resolviendo el sistema de ecuaciones:

Multiplíquese la ecuación (1) por 7:                                    (3) 28A + 70B = 280

Multiplíquese la ecuación (2) por – 4:                                (4) –28A – 28B = –196

                                                                                                42B = 84

                                                                                                   B = 2

Sustitúyase en la ecuación (1):                                            4A + 10(2) = 40

                                                                                                   A = 5

La solución menos costosa es 5 kilogramos de alimento A y 2 kilogramos de alimento B. El costo total de esta combinación es:

Z = 5A + 8B = 5(5) + 8(2) = 25 + 16 = 41 pesos

Si se usa el método de prueba y error para localizar la solución óptima, se deben encontrar las coordenadas de los puntos a, b, c, y d. Se debe calcular después el valor de la función objetivo para cada punto. A continuación se muestran los resultados de este procedimiento:

2.4. Método Símplex.

            El método símplex es un algoritmo. De hecho, cualquier procedimiento iterativo de solución es un algoritmo. Entonces, un algoritmo es simplemente un proceso en el que se repite (se itera) un procedimiento sistemático una y otra vez hasta obtener el resultado deseado. Cada vez que se lleva a cabo el procedimiento sistemático se realiza una iteración. En consecuencia, un algoritmo sustituye un problema difícil por una serie de problemas fáciles.

            Además de las iteraciones, los algoritmos incluyen un procedimiento para iniciar y un criterio para determinar cuándo detenerse, como se resume enseguida:

            El método símplex es un procedimiento algebraico en el que cada iteración contiene la solución de un sistema de ecuaciones para obtener una nueva solución a la que se le aplica la prueba de optimalidad. No obstante, también tiene una interpretación geométrica muy útil. Para ilustrar los conceptos geométricos generales se empleará la solución gráfica del siguiente problema:

Solución por el método gráfico:

En la figura anterior pueden observarse los puntos de intersección que son las soluciones en los vértices del problema. Los cinco puntos que se encuentran en los vértices de la región factible, ¾ (0,0), (0,6), (2,6), (4,3), (4,0) son las soluciones factibles en los vértices. Algunas de estas soluciones factibles en un vértice son adyacentes, en el sentido de que están conectadas por una sola orilla (segmento de línea) de la frontera de la región factible; esto es, tanto (0,6) como (4,3) son adyacentes a (2,6). Las tres propiedades clave de las soluciones factibles en los vértices y que forman el fundamento del método símplex se resumen como sigue:

Propiedades de las soluciones factibles en un vértice:

1a. Si existe exactamente una solución óptima, entonces debe ser una solución factible en un vértice.

1b. Si existen soluciones óptimas múltiples, entonces al menos dos de ellas deben ser soluciones factibles en vértices adyacentes.

2.   Existe sólo un número finito de soluciones factibles en los vértices adyacentes.

3.   Si una solución en un vértice es igual o menor (según el valor de Z) que todas las soluciones factibles en los vértices adyacentes a ella, entonces es igual o mejor que todas las demás soluciones en los vértices; es decir, es óptima.

            La propiedad 1 significa que la búsqueda de la solución óptima se puede reducir a la consideración de sólo las soluciones factibles en los vértices, de manera que sólo existe un número finito de soluciones que es necesario tomar en cuenta (propiedad 2). La propiedad 3 proporciona una prueba de optimalidad muy conveniente.

            El método símplex explota estas tres propiedades al examinar nada más unas cuantas soluciones factibles en vértices prometedores y al detenerse en cuanto una de ellas pasa la prueba de optimalidad. En particular, se traslada repetidamente (en forma iterativa) de una solución factible en un vértice a otra, adyacente y mejor. Esto se puede realizar en forma muy eficiente hasta que la solución actual no tiene soluciones factibles en vértices adyacentes que sean mejores. Este procedimiento se resume como sigue:

Bosquejo del método símplex:

1.   Paso inicial: inicio en una solución factible en un vértice.

2.   Paso iterativo: traslado a una mejor solución factible en un vértice adyacente. (Repítase este paso las veces que sea necesario).

3.    Prueba de optimalidad: la solución factible en un vértice es óptima cuando ninguna de las soluciones en vértices adyacentes a ella sean mejores.

            Este bosquejo muestra la esencia del método símplex,. En el caso del ejemplo, al utilizar estas reglas de selección el método símplex procede como sigue:

1.   Paso inicial: comienza en (0,0).

2a. Iteración 1: se mueve de (0,0) a (0,6)

2b. Iteración 2: se mueve de (0,6) a (2,6).

3.   Prueba de optimalidad: ni (0,6) ni (4,3) son mejores que (2,6), entonces se detiene, (2,6) es óptima.

Preparación para el método símplex.

            En el procedimiento algebraico es mucho más conveniente manejar ecuaciones que desigualdades. Así, el primer paso para preparar el método símplex es convertir las restricciones funcionales de desigualdad  en restricciones equivalentes. (Las restricciones de no negatividad se pueden dejar como desigualdades porque el algoritmo las usa sólo indirectamente). Esta conversión se hace mediante la introducción de variables de holgura. Considérese la primera restricción funcional del ejemplo:

x₁ £ 4

La variable de holgura para esta restricción es x₃, que no es otra cosa que la holgura entre los dos lados de la desigualdad. Entonces:

x₁ + x₃ = 4

La restricción original x₁ £ 4 se cumple siempre que x₃ ³ 0. Por tanto, x₁ £ 4 es totalmente equivalente al conjunto de restricciones

x₁ + x₃ = 4

y

x₃ ³ 0,

de manera que se usará este conjunto por resultar más conveniente.

            Al introducir variables de holgura en las otras restricciones en forma parecida, el modelo de programación lineal original para este ejemplo se puede sustituir por el modelo equivalente:

Maximizar  Z = 3x₁ + 5x₂,

sujeta a

            Aun cuando este problema es idéntico al anterior, esta forma es mucho más conveniente para la manipulación algebraica y la identificación de las soluciones factibles en los vértices. Ésta se llama la forma de igualdades del problema, para diferenciarla de la forma de desigualdades original y poder introducir la siguiente definición:

Una solución aumentada es una solución para un problema que originalmente se encontraba en forma de desigualdades y que se ha aumentado con los valores correspondientes de las variables de holgura para cambiar el problema a la forma de igualdades.

            Por ejemplo, al aumentar la solución (3,2) en el ejemplo, se obtiene la solución aumentada (3,2,1,8,5), puesto que los valores correspondientes de las variables de holgura son x₃ = 1, x₄ = 8, x₅ = 5.

Una solución básica es una solución en un vértice aumentada.

            Para ilustrar esto, considérese la solución no factible en el vértice (4,6) del ejemplo. Al aumentar con los valores obtenidos para las variables de holgura x₃ = 0, x₄ = 0 y x₅ = –6, se llega a la solución básica correspondiente (4,6,0,0,–6). Se permite que las soluciones básicas sean factibles o no factibles, lo que lleva a la siguiente definición:

Una solución básica factible es una solución factible en un vértice aumentada.

            Así, la solución factible en el vértice (0,6) del ejemplo es equivalente a la solución básica factible (0,6,4,0,6) para la forma de igualdades del problema.

            Como los términos solución básica y solución básica factible constituyen partes muy importantes del vocabulario normal de programación lineal, es necesario aclarar sus propiedades algebraicas. Nótese que para la forma de igualdades del ejemplo, el sistema de restricciones funcionales tiene dos variables más (cinco) que ecuaciones (tres). Este hecho proporciona dos grados de libertad al resolver el sistema, ya que se pueden elegir dos variables cualesquiera y hacerlas iguales a cualquier valor arbitrario para resolver las tres ecuaciones en términos de las tres variables restantes (se excluyen redundancias). El método símplex usa cero para este valor arbitrario. Las variables que por el momento se hacen iguales a cero se llaman variables no básicas; todas las demás se llaman variables básicas. La solución que resulta es una solución básica. Si todas las variables básicas son no negativas, entonces se tiene una solución básica factible. Para cualquier solución básica, la solución en el vértice correspondiente se obtiene simplemente al quitar las variables de holgura. Dos soluciones básicas son adyacentes si todas menos una de sus variables son las mismas; la misma aseveración se cumple para las variables básicas. Entonces, trasladarse de una solución básica factible a una adyacente significa cambiar el estado de una variable de no básica a básica y viceversa para otra variable.

            En términos generales, el número de variables no básicas de una solución básica siempre es igual a los grados de libertad del sistema de ecuaciones y el número de variables básicas siempre es igual al número de restricciones funcionales.

            Al trabajar con el problema en forma de igualdades, conviene tomar en cuenta y manipular la ecuación de la función objetivo al mismo tiempo que las nuevas ecuaciones de las restricciones. Antes de comenzar con el método símplex es necesario escribir el problema una vez más en su forma equivalente:

Maximizar Z,

sujeta a

            Como la ecuación de la función objetivo ya se encuentra en forma de igualdad, no necesita variable de holgura. Con esta interpretación, las soluciones básicas no cambian, excepto que Z puede verse como una variable básica adicional permanente.

            A partir de este momento ya estamos listos para pasar los coeficientes de nuestro problema a lo que conoceremos como la Tabla Símplex:

            La tabla anterior ilustra una propiedad clave que toda tabla símplex debe tener para estar en la forma apropiada; se trata del patrón especial de los coeficientes de las variables básicas. En particular, nótese cómo las columnas de x₃, x₄ y x₅ (al igual que la columna de Z) contiene exactamente un +1 en el renglón que corresponde a esa variable básica (véase la primera columna), y todos los demás coeficientes en esa columna son cero. De la misma manera, cada ecuación contiene exactamente una variable básica con coeficiente distinto de cero, en donde este coeficiente es +1. Esta propiedad es significativa, ya que permite identificar de inmediato la solución básica factible actual a partir de la tabla; esto es, cada variable básica es igual a la constante del lado derecho de su ecuación. Esta primera solución básica factible actual se muestra en la figura anterior en la columna de ¿Es óptima?. De aquí en adelante, para cada nueva iteración del método símplex mostraremos la solución básica factible actual en esta columna de la tabla símplex. (Recuérdese que las variables no básicas son iguales a cero). La tabla símplex inicial quedará automáticamente en esta forma apropiada (a menos que el problema original de programación lineal no esté en nuestra forma estándar).

            El método símplex construye una tabla símplex para cada solución básica factible que se obtiene, hasta alcanzar la solución óptima. A continuación describimos el procedimiento para problemas que ya están en la forma estándar, con b_i > 0 para toda i = 1, 2, …, m.

PASO INICIAL. Se introducen variables de holgura. Después se seleccionan las variables originales como variables no básicas iniciales (se igualan a cero) y las variables de holgura como las variables básicas originales. Esta selección lleva a la tabla símplex inicial anterior. Como esta tabla está en la forma apropiada, de inmediato se obtiene la solución básica factible inicial para el ejemplo, (0,0,4,10,18). Ahora debe realizarse la prueba de optimalidad para determinar si la solución es optima.

PRUEBA DE OPTIMALIDAD. La solución básica factible actual es óptima si y sólo si todos los coeficientes de la ecuación de la función objetivo (renglón de Z) son no negativos ( ³ 0 ). Si es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la nueva solución básica factible, lo que significa el cambio de una variable no básica por una básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución (parte 3).

            En este ejemplo, hay dos coeficientes negativos en la ecuación de Z, -3 para x₁ y -5 para x₂ de manera que debe irse al paso iterativo. Tacharemos la solución básica factible actual como se muestra en la tabla anterior para indicar que esta solución no es óptima.

PASO ITERATIVO.

            Parte 1. Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo (automáticamente se refiere a una variable no básica) que tiene el mayor valor absoluto en la ecuación de Z. Se enmarca la columna correspondiente a este coeficiente; esta columna recibe el nombre de columna pivote. En el ejemplo, el coeficiente negativo más grande (en términos de valor absoluto) es –5 para x₂ (5>3), por lo que x₂ debe convertirse en variable básica. Este cambio se indica en la siguiente tabla con el recuadro en la columna de x₂ abajo del –5:

            Parte 2. Se determina la variable básica que sale; para esto, a) se toma cada coeficiente estrictamente positivo (>0) de la columna enmarcada, b) se divide el lado derecho de cada renglón entre estos coeficientes, c) se identifica la ecuación con el menor coeficiente y d) se selecciona la variable básica para esta ecuación. (Esta variable básica es la que llega a cero primero cuando se incrementa la variable básica entrante). Se enmarca el renglón de esta ecuación en la tabla símplex sin incluir la columna Z y se le da el nombre de renglón pivote. El número que está en la intersección de los dos recuadros se llama pivote.

            En la tabla anterior, se muestran los resultados de las partes 1 y 2 para el ejemplo (antes de enmarcar el renglón); la prueba del cociente mínimo para determinar la variable básica que sale se muestra a la derecha de la tabla. Entonces la variable básica que sale es x₄.

            Parte 3. Se determina la nueva solución básica factible al construir una nueva tabla símplex en la forma apropiada, abajo de la que se tiene. Las primeras dos columnas no cambian, excepto que la variable básica entrante sustituye a la variable básica que sale en la columna de Variable Básica. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a +1, se divide todo el renglón pivote entre el número pivote:

Renglón pivote nuevo = Renglón pivote antiguo / pivote

            En este punto, la tabla símplex para el ejemplo se ve como la que se muestra enseguida. Para obtener un coeficiente 0 para la nueva variable básica en las otras ecuaciones, cada renglón [inclusive el de la ecuación de Z] excepto el renglón pivote, se cambia por la nueva tabla símplex usando la siguiente fórmula:

Renglón nuevo = renglón antiguo - (coeficiente en la columna pivote  ´  renglón pivote nuevo)

en donde el coeficiente en la columna pivote es el número en la columna pivote correspondiente a este renglón.

            Para ilustrar con el ejemplo, los nuevos renglones se obtienen de la forma siguiente:

Renglón de Z:                         [-3      -5        0          0          0,           0]

                                   -(-5)   [  0         1        0          1/2       0,           6]

            Renglón nuevo =          [-3        0        0          5/2       0,         30]

Renglón 1: Sin cambio porque su coeficiente en la columna pivote es cero.

Renglón 3:                              [3         2          0          0          1,         18]

                                   -(2)     [0         1          0          1/2       0,           6]

            Renglón nuevo =          [3         0          0          -1        1,           6]

            Estos cambios llevan a la nueva tabla símplex que se muestra en la siguiente tabla para la
iteración 1:

            Como las variables básicas siempre son iguales al lado derecho de la ecuación que le corresponde, la nueva solución básica factible es (0, 6, 4, 0, 6) con Z = 30.

            Este trabajo completa el paso iterativo, así que debe proseguirse a la prueba de optimalidad. Como la ecuación de Z todavía tiene coeficientes negativos (–3 para x₁), la prueba de optimalidad indica que la solución no es óptima, (lo cual se muestra en la figura anterior) por lo que manda al algoritmo de regreso al paso iterativo para obtener la siguiente solución básica factible. El paso iterativo comienza de nuevo en la tabla símplex actual para encontrar la nueva solución. Si se siguen las instrucciones de las partes 1 y 2, se encuentra que x₁ es la variable básica entrante y x₅ la variable básica que sale, como se muestra en la siguiente tabla:

            En las siguientes tablas se muestra el conjunto completo de las tablas del método símplex para esteejemplo. La nueva solución básica factible es (2, 6, 2, 0, 0), con Z = 36. Al hacer la prueba de optimalidad, se encuentra que la solución es óptima porque no hay coeficientes negativos en la ecuaciónde Z, de manera que el algoritmo ha terminado. En consecuencia, la solución óptima para este ejemplo (sin tomar en cuenta las variables de holgura) es x₁ = 2, x₂ = 6.

            Anteriormente no se dijo qué hacer cuando las reglas de selección del método símplex no llevan a una decisión clara, ya sea porque existen empates (valores iguales) o por otras ambigüedades parecidas.

Empate para la variable básica entrante.

            El paso 1 de cada iteración elige la variable básica que tiene el coeficiente negativo con el mayor valor absoluto en la ecuación de Z actual como la variable básica entrante. Ahora suponga que dos o más variables no básicas tienen el coeficiente negativo más grande (en valor absoluto), es decir, que hay un empate entre ellas. Por ejemplo, esto ocurriría en la primera iteración del ejemplo anterior si se cambiara la función objetivo a Z = 3x₁ + 3x₂, con lo que la ecuación del renglón de Z inicial sería Z-3x₁-3x₂ = 0. ¿Cómo debe romperse este empate?

            La respuesta es que la elección entre estos dos contendientes se puede hacer de manera arbitraria. Tarde o temprano se llegará a la solución óptima, sin importar cuál de las variables empatadas se haya escogido, y no existe un método conveniente para predecir cuál lleva ahí más rápidamente. En este ejemplo ocurre que si se escoge x₁ como variable entrante, el método símplex alcanza la solución óptima (2, 6) en tres iteraciones y si se elige x₂, llega en dos.

Empate para la variable básica que sale - degeneración.

            Ahora suponga que el empate ocurre entre dos o más variables básicas al elegir la variable que sale en el paso 2 de una iteración. ¿Importa cuál se escoge? En teoría sí, y en una forma crítica debido a que puede ocurrir la siguiente sucesión de eventos. Primero, todas las variables empatadas se hacen cero al mismo tiempo cuando aumenta el valor de la variable entrante. Por tanto, aquellas que no se eligieron como variable básica que sale también tendrán un valor de cero en la nueva solución básica factible. (Las variables básicas con valor de cero se llaman degeneradas y el mismo nombre se da a la solución básica factible correspondiente.) Segundo, si una de estas variables básicas degeneradas sigue con valor de cero hasta que se selecciona como variable básica que sale en una iteración posterior, la variable básica entrante deberá también quedar con valor de cero (ya que no puede crecer sin que la variable básica que sale se vuelva negativa), entonces el valor de Z permanecerá sin cambio. Tercero, si Z permanece igual en lugar de mejorar cada iteración, el método símplex puede caer en un ciclo que repite la misma secuencia de soluciones periódicamente, en lugar de aumentar en algún momento para llegar a la solución óptima.

            Por fortuna, aunque en teoría es posible que haya ciclos perpetuos, ha sido en extremo raro que tenga lugar en problemas reales. Si ocurriera un ciclo siempre se puede salir de él cambiando la elección de la variable básica que sale. Por lo tanto se recomienda romper los empates arbitrariamente y seguir el proceso sin preocuparse de las variables que puedan resultar.

Cuando no hay variable básica que sale - Z no acotada.

            Existe otra posibilidad en el paso 2 de una  iteración, de la que no se ha hablado: aquella en la que ninguna variable califica como variable básica que sale. Esta situación puede ocurrir si la variable básica entrante puede crecer indefinidamente sin que ninguna de las variables básicas actuales adquiera valores negativos. En la forma tabular, esto significa que todos los coeficientes en la columna pivote (se excluye el renglón de Z) son negativos o cero.

            Como se ilustra en la siguiente tabla, esta situación surge cuando se considera el siguiente ejemplo:

Maximizar  Z = 3x₁ + 5x₂,

sujeta a                x₁ £ 4

y                  x₁ ³ 0,    x₂ ³ 0

            En este ejemplo se ignoraron las dos últimas restricciones funcionales del ejemplo resuelto anteriormente. Vea en la tabla que x₂ es la variable básica entrante pero el único coeficiente en la columna pivote es cero. Como la prueba del cociente mínimo usa sólo coeficientes mayores que cero, no se cuenta con un cociente que proporcione una variable básica que sale.

            La interpretación de una tabla símplex como la que se muestra en la siguiente tabla es que las restricciones no impiden el crecimiento indefinido de la función objetivo Z, de manera que el método símplex se detiene con el mensaje de que Z es no acotada. Debido a que ni siquiera la programación lineal ha descubierto la manera de lograr ganancias infinitas, el mensaje real en problemas prácticos es: ¡Se ha cometido un error! Tal vez el modelo esté mal formulado, ya sea por haber omitido una restricción relevante o por haberla establecido incorrectamente. De otra manera, pudo haber ocurrido un error en los cálculos.

Soluciones óptimas múltiples.

            En la definición de solución óptima se mencionó que un problema puede tener más de una solución óptima. Si en el ejemplo cambiamos  la función objetivo a Z = 3x₁ + 2x₂ resulta que todos los puntos sobre el segmento de recta entre (2,6) y (4,3) son soluciones óptimas. Entonces todas las soluciones son un promedio ponderado de estas dos soluciones factibles en los vértices óptimas:

(x₁, x₂) = w₁(2, 6) + w₂(4, 3),

donde los pesos w1 yw2  son  números que satisfacen las relaciones:

w₁ + w₂ =  1                y                      w₁ ³ 0,            w₂ ³ 0

Por ejemplo, w₁ = 1/3  y  w₂ = 2/3 da:

(x₁, x₂) = 1/3(2, 6) + 2/3(4, 3) = (2/3+8/3, 6/3+6/3) = (10/3, 4)

como una solución óptima.

            En general, cualquier promedio ponderado de dos o más soluciones (vectores) donde los pesos son no negativos y suman 1 se llama combinación convexa de estas soluciones. Entonces, toda solución óptima en el ejemplo es una combinación convexa de (2, 6) y (4, 3).

            Este ejemplo es representativo de problemas con soluciones óptimas múltiples.

Cualquier problema de Programación Lineal con soluciones óptimas múltiples (y una región factible acotada) tiene al menos dos soluciones factibles en los vértices que son óptimas. Toda solución óptima es una combinación lineal de estas soluciones factibles en los vértices óptimas. En consecuencia, en la forma aumentada, toda solución óptima es una combinación convexa de las soluciones básicas factibles óptimas.

            El método símplex se detiene automáticamente al encontrar una solución básica factible óptima. Sin embargo, en muchas aplicaciones de Programación Lineal existen factores intangibles que no se incorporan al modelo y que pueden ser útiles para tomar decisiones significativas sobre las soluciones óptimas alternativas. En esos casos, también deben identificarse las otras soluciones óptimas. Esto requiere encontrar todas las demás soluciones básicas factible óptimas, y entonces toda solución óptima es una combinación convexa de las soluciones básicas factibles óptimas.

            Una vez que el método símplex encuentra una solución básica factible óptima, se puede detectar si existen otras y, si así es, se encuentra como sigue:

Siempre que un problema tiene más de una solución básica factible óptima, al menos una variable no básica tiene coeficiente cero en la ecuación de Z final, de manera  que si aumenta su valor, el valor de la función Z no cambia. Por lo tanto, estas otras soluciones básicas factibles óptimas se pueden identificar (si se desea) realizando iteraciones adicionales del método símplex, en las que cada vez se elige una variable no básica con coeficiente cero como variable básica entrante. Si una de estas iteraciones no tiene una variable básica que sale esto indica que la región factible es no acotada y la variable básica entrante puede crecer indefinidamente sin cambiar el valor de Z.

2.5. Método de la “M” o de Penalización.

                Hasta este momento se han presentado los detalles del método símplex con la suposición de que el problema se encuentra en nuestra forma estándar (maximizar Z sujeta a las restricciones funcionales de la  forma £ y restricciones de no negatividad sobre todas las variables) con b_i ³ 0 para toda i = 1,  2, ..., m. En esta sección se establecerá cómo hacer los ajustes requeridos a otras formas legítimas de modelos de Programación Lineal. Se verá que todos estos ajustes se pueden hacer en el paso inicial, de manera que el resto del método símplex se aplica justo como se aprendió.

                El único problema serio que introducen las otras formas de restricciones funcionales (= ó ³) es identificar una solución inicial básica factible. Antes, esta solución inicial se encontraba en forma muy conveniente al hacer que las variables de holgura fueran las variables básicas iniciales, donde cada una era igual a la constante no negativa del lado derecho de la ecuación correspondiente. Ahora debe hacerse algo más. El enfoque estándar que se utiliza es estos casos es  la técnica de variables artificiales. Ésta construye un problema artificial más conveniente introduciendo una variable ficticia (llamada variable artificial) en cada restricción que lo requiera. Esta nueva variable se introduce sólo con el fin de que sea la variable básica inicial para esa ecuación. Las restricciones usuales de no negatividad también se aplican sobre estas variables y la función objetivo se modifica para  que imponga una penalización exorbitante en  el caso de que adquieran valores mayores que cero. Las iteraciones del método símplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una, hasta  que todas quedan fuera  de  la solución; después de esto se resuelve el problema real.

                Para ilustrar la técnica de las variables artificiales, primero se considerará el caso en que la única forma no estándar en el problema es la presencia de una o más restricciones en forma de igualdad.

Restricciones en forma de igualdad.

                En realidad, cualquier restricción en forma de igualdad:

a_i1x₁ +a_i2x₂ + . . . + a_inx_n = b_i

es equivalente a dos restricciones de desigualdad:

a_i1x₁ + a_i2x₂ + . . . + a_inx_n £ b_i,

a_i1x₁ + a_i2x₂ + . . . + a_inx_n ³ b_i

                Sin embargo, en lugar de hacer esta sustitución e incrementar con ello el número de restricciones, es más conveniente usar la técnica de la variable artificial. Suponga que se modifica el problema de ejemplo presentado y resuelto en la sección anterior. El único cambio que sufre el modelo de programación lineal es que la tercera restricción, 3x₁ + 2x₂ £ 18, se convierte en una restricción de igualdad:

3x₁ + 2x₂ = 18

                Aplicando la técnica de las variables artificiales se introduce una variable artificial no negativa (denotada por  x₅) en la última ecuación, como si fuera una variable de holgura:

                En resumen si tenemos una restricción funcional en forma de igualdad y deseamos “pasarla a su forma de igualdad”, únicamente debemos sumar una variable artificial.

Restricciones funcionales de la forma ³

                Para ilustrar la manera en que la técnica de las variables artificiales maneja las restricciones de la forma ³ usaremos el siguiente ejemplo:

                Notemos que la tercera restricción es del tipo ³, por lo que para cambiarla a su forma de igualdad tendríamos que restar una variable de superávit (o de excedente), quedando de la siguiente manera:

                Se ha restado la variable de excedente x₅ (se utilizó x₅ porque en la primera restricción agregamos una variable de holgura que sería x₃ y en la segunda restricción agregamos también una variable artificial que sería x₄; todo esto con el fin de convertir las desigualdades a su forma de igualdades) para que consuma el exceso de 0.6x₁ + 0.4x₂, o sea, lo que se pasa de 6. No obstante en este caso debe agregarse otra variable. Esta variable extra, llamada variable artificial se aumenta como sigue:

                La razón de esto es que, si no se agrega la variable artificial, no se estarían cumpliendo las restricciones de no negatividad. Para comprenderlo, se dejará sin aumentar. El método símplex comienza por hacer todas las variables reales (originales) iguales a cero. Entonces:

0.6x₁ + 0.4x₂ - x₅ = 6

Sea x₁ = 0 y x₂ = 0, entonces:

-x₅ = 6

ó

x₅ = -6  (que no cumple la restricción de no negatividad)

                La variable artificial opera para mantener todas las variables no negativas cuando 0.6x₁ + 0.4x₂ es menor que 6. Si x₁ = 0 y x₂ = 0, entonces x₅ = 0 y

         En resumen, una restricción de la forma ³ se convierte a su forma de igualdad restando una variable  de excedente y sumando una variable artificial.

                Consideremos el siguiente problema:

                Como explicamos anteriormente, para resolver este problema, debemos construir un problema artificial que tiene la misma solución óptima que el problema real, haciendo dos modificaciones a este problema real.

1. Se aplica la técnica de las variables artificiales introduciendo una variable artificial no negativa (denotada por x₅) en la última ecuación, como si fuera una variable de holgura:

2.    Se asigna una penalización enorme al hecho de tener x₅ > 0, cambiando la función objetivo
Z = 3x₁ + 5x₂ a:

donde M simbólicamente representa un número positivo muy grande. Este método que fuerza a x₅ hasta el nivel de x₅ = 0 en la solución óptima se llama método de la M.

Nota: Para el caso de minimización, penalizamos a la variable artificial, haciéndola aparecer en la función objetivo con un coeficiente de +M.

         Ahora se encuentra la solución óptima para el problema real aplicando el método símplex al problema artificial.

           Como x₅ juega el papel de la variable de holgura en la tercera restricción del problema artificial, esta restricción es equivalente a 3x₁ + 2x₂ £ 18.

                En particular, el sistema de ecuaciones después de aumentar el problema artificial (en otras palabras, pasarlo a su forma de igualdades) es:

Maximizar Z,

sujeta a

                En este momento estamos preparados para pasar los coeficientes a la tabla símplex:

                Esta tabla todavía no está en la forma apropiada porque el coeficiente de x₅ es diferente de cero en la ecuación de Z (es M). Por lo tanto, antes de que el método símplex pueda aplicar la prueba de optimalidad y encontrar la variable básica entrante, debe pasarse esta tabla a la forma apropiada para que cumpla la condición símplex. Esta condición que debe cumplir toda tabla del método símplex para que pueda reportarnos la siguiente solución básica factible dice que: “Toda variable básica debe tener un 1 en la intersección de su renglón y columna correspondiente y cero en los demás renglones incluido el renglón de Z”, en otras palabras, que toda variable que sea básica solamente debe aparecer en el renglón de la restricción que representa. Para hacer cero el coeficiente M, utilizamos el renglón de x₅ como renglón pivote multiplicándolo por -M y sumando el resultado al renglón de Z. Realizando el procedimiento anterior, la tabla símplex queda de la siguiente manera:

                Podemos observar que la tabla anterior ya se encuentra en la forma apropiada y podemos leer la solución básica factible actual, que es (0, 0, 4, 10, 18), la cual aplicando la prueba de optimalidad vemos que no es óptima ya que todavía tenemos coeficientes negativos en el renglón de Z (los correspondientes a x₁ y x₂). Aplicando el método símplex a la tabla anterior tenemos: el coeficiente negativo con el mayor valor absoluto corresponde a x₁  (-3M-3), recordemos que M es un número muy grande positivo, por lo tanto, x₁ se convierte en la variable básica entrante, realizando los cocientes correspondientes, vemos que x₃ se convierte en la variable básica saliente. El procedimiento completo para resolver este ejemplo se muestra en el siguiente conjunto de tablas:

                Notemos que la primera tabla no se encontraba en la forma apropiada para el método símplex, ya que el coeficiente de la variable básica  x₅ era de -M en el renglón de Z, lo cual hacia que no se cumpliera la condición símplex.

2.6. Método de las dos Fases.

                En el ejemplo presentado en la sección “Restricciones funcionales de la forma ³“, recordemos la función objetivo real:

Problema real:                    Minimizar              Z = 0.4x₁ + 0.5x₂

                Sin embargo, el método de la M utiliza la siguiente función objetivo a través de todo el procedimiento:

Método de la M: Minimizar              Z = 0.4x₁ + 0.5x₂ + Mx₄ + Mx₆

                Como los dos primeros coeficientes (0.4 y 0.5) son despreciables comparados con M, el método de dos fases puede eliminar la M usando las siguientes dos funciones objetivo que definen Z de manera completamente diferente:

Método de las dos fases:

Fase 1:                  Minimizar              Z = x₄ + x₆                              (hasta que x₄ = 0 y x₆ = 0).

Fase 2:                  Minimizar              Z = 0.4x₁ + 0.5x₂    (con x₄ = 0 y x₆ = 0).

                La función objetivo de la fase 1 se obtiene dividiendo la función objetivo del método de la M entre M eliminando los términos despreciables, en otras palabras, la fase 1 consiste en la minimización de la suma de todas las variables artificiales que se introduzcan en el problema. Como  la fase  1 concluye al obtener una solución básica factible para el problema real (aquella en la que x₄ = 0 y x₆ = 0), esta solución se usa como la solución básica factible inicial para aplicar el método símplex al problema real (con su función objetivo) en la fase 2. Antes de resolver el ejemplo de esta manera se hará un resumen de las características generales.

Resumen del método de dos fases.

Paso inicial: Se revisan las restricciones del problema original introduciendo variables artificiales según se necesite para obtener una solución básica factible inicial obvia para el problema artificial.

                Fase 1: uso del método símplex para resolver el problema de programación lineal:

Minimizar  Z = S de todas las variables artificiales, sujeta a las restricciones revisadas.

                La solución óptima que se obtiene para este problema (con Z = 0) será una solución básica factible para el problema real.

                Fase 2: se eliminan las variables artificiales (de todas formas, ahora todas valen cero). Comenzando con la solución básica factible que se obtuvo al final de la fase 1, se usa el método símplex para resolver el problema real.

                Enseguida se resumen los problemas que deben resolverse por el método símplex en las fases respectivas para el ejemplo.

            Problema para la fase 1:

Minimizar         W = x₄ + x₆,

sujeta a

y

            Problema para la fase 2:

Minimizar    Z = 0.4x₁ + 0.5x₂,

sujeta a

y

                Las únicas diferencias entre estos dos problemas se encuentran en la función objetivo y en la inclusión (fase 1) o exclusión (fase 2) de las variables artificiales x₄ y x₆. Sin las variables artificiales, el problema para la fase 2 no tiene una solución básica factible inicial obvia. El único propósito de resolver el problema para la fase 1 es obtener una solución básica factible con x₄ = 0 y x₆ = 0 que se pueda usar como la solución básica factible inicial para la fase 2.

                Las siguientes tablas muestran el resultado de aplicar el método símplex a este problema para la fase 1:

                Notemos que ya hemos obtenido una solución óptima para la fase 1 que consistió en la minimización de la suma de todas las variables artificiales. Observemos también que la función objetivo W terminó con un valor de cero en la última tabla, lo que indica que las dos variables artificiales (x₄ y x₆) valen cero ó tienen valores recíprocos y se cancelan mutuamente para dar cero. En nuestro caso, las dos variables artificiales valen cero ya que no se encuentran en la columna de las variables básicas en la última tabla de la primera fase. La segunda fase consiste en resolver el problema original utilizando como tabla inicial de esta fase la última tabla de la primera fase pero sin considerar la columna de las variables artificiales ya que éstas tomaron el valor de cero en la primera fase. El método símplex aplicado a la segunda fase se muestra en el siguiente conjunto de tablas:

                Notemos que no fue necesario aplicar propiamente el método símplex a la primera tabla de la segunda fase, ya que únicamente aplicando operaciones con matrices para tratar de llevar esta tabla a la forma apropiada para el método símplex fue suficiente para resolver el problema planteado en la segunda fase. Es necesario aclarar que no siempre ocurrirá de esta manera, es decir, si después de dejar la tabla en la forma apropiada, es necesario aplicar el método símplex, se debe aplicar como lo hemos estudiado.

Nota: Independientemente de que el problema original (real) sea de maximización o minimización, la primera fase siempre consistirá en la minimización de la suma de todas las variables artificiales.