Ejemplo Soluciones básicas complementarias (III)

Para revisar el razonamiento que fundamenta esta propiedad, obsérvese que la solución dual (y*, z* - c) debe ser factible para el problema dual, puesto que la condición de optimalidad para el problema primal requiere que todas estas variables duales (inclusive las variables de superávit) sean no negativas. Como esta solución es factible, debe ser óptima para el problema dual dada a la propiedad de dualidad débil.

Las soluciones básicas se pueden clasificar según si satisfacen o no cada una de dos condiciones. Una es la condición de factibilidad, a saber, si todas las variables (incluyendo las de holgura) en la solución aumentanda son no negativas. La otra es la condición de optimalidad, es decir, si todos los coeficientes en el renglón 0 (o sea todas la variables en la solución básica complementaria) son no negativos. En la tabla 6.10 se resumen los términos que se emplean aquí para los diferentes tipos de soluciones básicas. Por ejemplo, en la tabla 6.9 las soluciones básicas 1,2,4 y 5 son subóptimas, la 6 es óptima, la 7 y 8 son superóptimas y la 3 no es ni factible ni superóptima.

Propiedad de las soluciones básicas óptimas complementarias

Cada solución básica óptima en el problema primal tiene una solución básica óptima complementaria en el problema dual, en donde los valores respectivos de las funciones objetivo (Z y yo) son iguales. Dado el renglón 0 de la tabla símplex para la solución primal óptima, se puede encontrar la solución dual óptima complementaria (y*, Z*-c), como se puede ver en la tabla 6.4.

Relaciones entre las soluciones básicas complementarias

Ahora se estudiarán las relaciones entre las soluciones básicas complementarias y se comenzará con sus relaciones de factibilidad. Las columnas centrales de la tabla 6.9 proporcionan algunas ideas valiosas. Nótese que para los pares de soluciones básicas complementarias, las respuestas de sí o no a la factibilidad también satisfacen una relación de complementariedad en la mayor parte de los casos. En particular, con una sola excepción, siempre que una solución es factible, la otra no lo es. (También es posible que ninguna solución sea factible, como ocurre con el tercer par). La única excepción es el sexto par, en el que se sabe que la solución del primal es óptima. La columna Z = yo sugiere la explicación. Como la sexta solución dual también es óptima (por la propiedad de soluciones óptimas complementarias), con yo = 36, entonces las primeras cinco soluciones duales no pueden ser factibles, ya que yo < 36, entonces las primeras cinco soluciones duales no pueden ser factibles, ya que yo < 36 (recuérdese que el objetivo del problema dual es minimizar yo). Por la misma razón, las dos últimas soluciones primales no pueden ser factibles, pues Z > 36.

Esta explicación está apoyada por la propiedad de dualidad fuerte que dice que las soluciones óptimas primal y dual tienen Z = yo.

En seguida se establecerá la extensión de la propiedad de las soluciones óptimas complementarias de la sección 6.1 para las formas aumentadas de los dos problemas.

Ejemplo Soluciones básicas complementarias (II)

En forma alternativa, para cada solución básica primal se puede usar la propiedad de holgura complementaria para identificar las variables básicas y no básicas de la solución básica dual complementaria, de manera que el sistema de ecuaciones dado al principio de la sección se puede resolver directamente para obtener esta solución complementaria. Por ejemplo, considérese  la penúltima solución básica primal en la tabla 6.9, en donde x1, x2 y x5 son variables básicas. En las tablas 6.7 y 6.8 se observa que la propiedad de holgura complementaria implica que (z1-c1), (z2-c2) y y3 son variables no básicas en la solución básica dual complementaria. Al establecer estas variables igual a cero en las ecuaciones del problema dual, y1 + 3y3 - (z1-c1) = 3 y 2y2 + 2y3 -(z2-c2) =5, de inmediato se obtiene y1 = 3, y2 = (5/2).

Por último, obsérvese que la tabla 6.9 demuestra que (0, 3/2, 1, 0, 0) es la solución óptima para el problema dual, ya que es la solución básica factible con un valor mínimo para yo (36).

Ejemplo Soluciones básicas complementarias (I)

Para ilustrar estas dos propiedades, considérese de nuevo el problema de la Wyndor Glass Co. de la sección 3.1. En las tablas 5.5 y 5.6 se muestran sus ocho soluciones básicas (cinco factibles y tres no factibles) junto con las respectivas soluciones en los vértices. Entonces, su problema dual (veáse la tabla 6.1) también debe tener ocho soluciones básicas, cada una complementaria a una de las soluciones primales, como se muestra en la tabla 6.9.

Las tres soluciones básicas factibles obtenidas por el método símplex para el problema primal son la primera, la quinta y la sexta soluciones que se muestran en la tabla 6.9. Ya se vio en la tabla 6.5 cómo se pueden leer las soluciones básicas complementarias para el problema dual directamente del renglón 0, se comienza con los coeficientes de las variables de holgura y se sigue con las variables originales. Las otras soluciones básicas duales también se pueden identificar en la misma forma si se construye el renglón 0 para cada una de las otras soluciones básicas primales, empleando las fórmulas dadas en la parte inferior de la tabla 5.7.

Soluciones básicas complementarias (III)

La razón por la que se usa el nombre de holgura complementaria para esta última propiedad es que dice (en parte) que para cada par de variables asociadas, si una de ellas tiene holgura en su restricción de no negatividad  (valor de la variable básica >0), entonces la otra no debe tener holgura (variable no básica = 0). En la sección 6.2 se mencionó que está propiedad tiene una interpretación económica útil en los problemas de programación líneal.

Propiedad de holgura complementaria

La siguiente propiedad indica cómo identificar las variables básicas y no básicas para esta solución básica complementaria.

Propiedad de holgura complementaria

Al usar la asociación entre variables que se da en la tabla 6.7, las variables en la solución básica primal y en la solución básica dual complementaria satisfacen las relaciones de holgura complementaria que se muestran en la tabla 6.8. Es más, esta relación es simétrica, de manera que estas dos soluciones básicas son complementarias entre sí.