Adaptación a otras formas del primal (VI)

Cuando se aplica el método símplex a formas primales no estándar y cuando se usa la técnica de variables artificiales (quizá con la ayuda del método de la M) para adaptarse a ellas, también debe hacerse algún ajuste a la interpretación de dualidad del renglón 0. Esto se debe a que las variables artificiales y las cantidades M revisan el problema primal y, por lo tanto, el problema dual cambia y las soluciones básicas complementarias que se muestran en el renglón 0 son soluciones de este problema dual revisado. Sin embargo, una vez que se han elminado las variables artificiales (se han hecho no básicas) y que la solución actual es una solución básica factible legítima para el problema primal original, se puede usar el renglón 0 para identificar la solución básica complementaria para el problema dual original. En seguida se describirá cómo se hace esto.

Supóngase que se usa la forma de la primera columna de la tabla 6.14. Para cada restricción de igualdad i, su variable artificial juega el papel de variable de holgura, excepto que al principio se agrego M al coeficiente de esta variable en el renglón 0. Por tanto, el valor actual de al variable dual correspondiente yi, es el coeficiente actual de esta variable artificial menos M. Su una restricción del tipo ≤ tiene lado derecho negativo desde el inicio (tal vez era una restricción ≥ y se cambió), de manera que se le ha agregado una variable artificial, el valor de la variable dual correspondiente sigue siendo el coeficiente de su variable de holgura. En este caso se ignora el coeficiente de la variable artificial. Por último, si la variable x es no restringirla en signo y se ha sustituido por la diferencia de dos variables no negativas (xj^+ - xj^-), el coeficiente de xj^+, denotado por (zj^+ - cj), se usará como si se tratara de xj. En otras palabras,

Adaptación a otras formas del primal (V)

De manera equivalente, se puede usar la forma en la primera columna de la tabla 6.14 en lugar de establecer el problema primal (Esta forma se necesita de todas maneras para aplicar el método símplex como se presentó en el capítulo 4.) Empleando las primeras dos conversiones en la tabla 6.12, este enfoque conduce a la forma del problema primal que se muestra en el lado izquierdo de la tabla 6.16. Entonces se usa la forma dual correspondiente en la segunda columna de la tabla 6.14 para construir el problema dual que se muestra en el lado derecho de la tabla 6.16.

Nótese que las dos versiones de los problemas primal y dual en las tablas 6.15 y 6.16 son completamente equivalentes, donde y'2 = -y2. Esta equivalencia es inevitable puesto que las diferencias implican que se sustituyen sólo formas equivalentes.

Adaptación a otras formas del primal (IV)

Para ilustrar este procedimiento, considérese el ejemplo de terapia de radiación que se presentó en la sección 3.4. (Su modelo se muestra en la página 45). Sea éste el problema primal. Antes de encontrar su problema dual, es necesario convertir el modelo en una de las formas permitidas que se muestran en la tabla 6.14. Se hará de las dos maneras.

El modelo de terapia de radiacion casi se ajusta a la forma en la segunda columna de la tabla 6.14. la única discrepancia es que la primera restricción funcional, 0.3x1 + 0.1x2 ≤ 27, se encuentra en la forma ≤ en lugar de ≥ 0 =. Sin embargo, si se multiplican ambos lados por (-1), se convierte a la forma ≥, quedando así la forma permitida del modelo que se muestra en el lado izquierdo de la tabla 6.15. Su problema dual se construye entonces en forma normal (según se resumió en la tabla 6.2a) excepto por la siguiente forma en la primera columna de la tabla 6.14. El resultado se muestra en el lado derecho de la tabla 6.15. Nótese que se ha eliminado la restricción de no negatividad para la segunda variable (y2) ya que la segunda restricción funcional en el problema primal es una restricción de igualdad.

Adaptación a otras formas del primal (III)

La ejemplificación de la construcción del problema dual para un problema primal no estándar no incluyó restricciones de igualdad ni variables no restringidas en signo. De hecho, para estas dos formas existe un camino más corto. ES posible demostrar [véanse los problemas 20 y 17c)] que una restricción de igualdad en el primal debe manejarse como igual que una de la forma ≤ al construir el problema dual, excepto que debe eliminarse la restricción de no negatividad para la variable dual correspondiente (es decir, esta variable queda sin restricción de signo). Por la propiedad de simétria, eliminar una restricción de no negatividad en el problema primal afecta el problema dual sólo en que la restricción correspondiente cambia a una restricción de igualdad.

Gracias a estos atajos, sólo se necesita cambiar el problema primal a la forma que se muestra en cualquiera de las dos columnas de la tabla 6.14. Después se construye el problema dual de la manera acostumbrada y se emplea la forma que se muestra en la otra columna. Las flechas de dos sentidos en la tabla 6.14 muestran la correspondencia específica que debe seguirse entre las dos formas. En particular, una restricción funcional en forma de desigualdad en un problema corresponde a incluir una restricción de no negatividad en el otro, mientras que una restricción en forma de igualdad en un problema corresponde a quitar la restricción de no negatividad en el otro. Debe tenerse cuidado de no mezclar el problema primal. Las mezclas de este tipo no se permiten cuando se trata de construir el problema dual.

Adaptación a otras formas del primal (II)

Como resultado, todas las afirmaciones que se hicieron antes sobre las relaciones del problema dual con el primal también se cumplen en el sentido inverso.

Otra consecuencia de la propiedad de simetría es que no tiene ninguna trascendencia a cuál de los problemas se le dé el nombre de primal y a cuál el de dual. En la práctica, se puede encontrar un problema de programación lineal que se ajuste a nuestra forma estándar y al que se le dé de problema dual. La convención es que el modelo formulado para representar el problema real recibe el nombre de problema primal sin importar qué forma tiene.

Adaptación a otras formas del primal (I)

Hasta este momento se ha supuesto que el modelo del problema primal se encuentra en nuestra forma estándar. Sin embargo, al principio del capítulo se dijo que cualquier problema de programación lineal, en forma estándar o no, posee un problema dual. En esta sección se enfocará la atención a los cambios que sufre el dual para las otras formas del primal.

En la sección 4.6 se presentaron las otras formas no estándar, y se señalo cómo puede convertirse cada una en la forma estándar equivalente, si así se desea. Estas conversiones se resumen en la tabla 6.12. Con esto, siempre se tiene la opción de convertir cualquier modelo a nuestra forma estándar y después construir su problema dual en la forma usual. Como ejemplo, en la tabla 6.13 se hace esto para el problema dual estándar (que también debe tener un dual). Notese que el resultado de todo esto es justo el problema primal estándar! Como cualquier par de problemas primal y dual se pueden cambiar a estas formas, este hecho demuestra una propiedad importante de las relaciones primal-dual:

Propiedades de simetría

Para cualquier problema primal y su problema dual, todas las relaciones entre ellos deben ser simétricas ya que el dual de este problema dual es este problema primal.

Ejemplo Soluciones básicas complementarias (IV)

Usando estas definiciones, en la tabla 6.11 se resumen las relaciones generales entre las soluciones básicas complementarias. En la figura 6.1 se muestra el rango de valores posible (comunes) para las funciones objetivo (Z=yo) que resulta para los tres pares de soluciones dados en la tabla 6.11 (el último par puede tener cualquier valor). Entonces, mientras que el método símplex maneja directamente soluciones básicas subóptimas y trabaja para alcanzar la optimalidad en el problema primal, al mismo tiempo obtiene de manera indirecta las soluciones superóptimas complementarias y las mueve hacia la factibilidad del problema dual. A la inversa, algunas veces es más conveniente (o necesario) trabajar directamente con las soluciones básicas subóptimas y trabajar para alcanzar la optimalidad en el problema primal, lo cual es el propósito del método símplex descrito en la sección 9.2.

Se ha comprobado la utilidad de estas relaciones, en particular para el análisis de sensibilidad, como se verá más adelante en el capítulo.