METODO DUAL SIMPLEX - MINIMIZACION

Este método se aplica a problemas óptimos pero infactibles. En este caso, las restricciones se expresan en forma canónica (restricciones).

La función objetivo puede estar en la forma de maximización o de minimización. Después de agregar las variables de holgura y de poner el problema en la tabla, si algún elemento de la parte derecha es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse por el método dual simplex. Note que un elemento negativo en el lado derecho significa que el problema comienza óptimo pero infactible como se requiere en el método dual simplex. En la iteración donde la solución básica llega a ser factible esta será la solución óptima del problema.

Una vez formulado el problema dual, debemos encontrar su solución, el método a emplear será el denominado Método Dual-Simplex el cuál empieza con una solución óptima o mejor que óptima, pero no factible y se mueve hacia el óptimo mediante iteraciones que mejoran su factibilidad conservando su optimalidad. Fíjese que es lo contrario al método Simplex, en donde se empieza mediante una solución factible pero no óptima y mediante iteraciones se mejora la optimalidad, conservando la factibilidad. Esto se ilustra mediante la siguiente gráfica:

CONDICIÓN DE FACTIBILIDAD.

La variable que sale es la variable básica que tiene el valor más negativo (los empates se rompen arbitrariamente si todas las variables básicas son negativas, el proceso termina y esta última tabla es la solución óptima factible).

CONDICIÓN DE OPTIMIDAD.

La variable que entra se elige entre las variables no básicas como sigue. Tome los cocientes de los coeficientes de la función objetivo entre los coeficientes correspondientes a la ecuación asociada a la variable que sale.

Ignore los cocientes asociados a denominadores positivos o cero.

La variable que entra es aquella con el cociente más pequeño si el problema es de minimizar o el valor absoluto más pequeño si el problema es de maximización (rompa los empates arbitrariamente). Si los denominadores son ceros o positivos el problema no tiene ninguna solución factible.

REGLAS DE OBTENCIÓN DE DUAL.

Si el modelo está escrito de forma canónica, el dual resulta singularmente fácil de obtener; si se trata de obtener el dual del dual, se obtendrá el primal, siendo así se trata de una correspondencia biunívoca.

De forma general las reglas para obtener el dual en cualquier modelo lineal se indican de la siguiente forma.

INTERPRETACIÓN DE LAS VARIABLES DUALES.

Cada variable de dual está asociada a una restricción del programa primal, y su valor óptimo representa el incremento de la función objetivo del primal por cada unidad que aumente, el término independiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Los valores de estas variables se denominan precios sombra; los precios sombra obtenidos a partir del optimo del dual serán validos siempre que no varíe la base optima. En consecuencia los resultados obtenidos del dual están íntimamente ligados al análisis de sensibilidad de los términos independientes.

OBTENCIÓN DE LA SOLUCIÓN DUAL.

El dual de un modelo lineal es otro modelo lineal que puede solucionarse después de las oportunas trasformaciones, si alguna de las variables resultantes es no negativa o no restringida en signo, del mismo modo que el primal, sin embargo puede obtenerse la solución del dual resolviendo el primal. Existen dos modos de obtener una solución óptima del dual:

A partir de la tabla simplex optima del primal, la solución obtenida nos permitirá tener un importante resultado. El teorema de la holgura complementaria.

Mediante un programa informático, dado que los programas de resolución de modelos lineales realizan el análisis de sensibilidad, podemos realizar un análisis más exacto de la evolución de los precios sombra.

DUAL SIMÉTRICO Y ASIMÉTRICO

Los problemas duales simétricos son los que se obtienen de un problema primal en forma canónica y normalizada, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades, menor o igual para los problemas de maximización.

CARACTERÍSTICAS

* este método se aplica cuando se tiene al menos una restricción de tipo ≥
* se aplica en los modelos generales de minimizacion
* parte de una solución optima pero no factible

VENTAJAS Y DESVENTAJAS DE LA DUALIDAD.

Una de las ventajas de la existencia del programa dual es la posibilidad de reducir el esfuerzo computacional  al resolver ciertos modelos de programación lineal.

 Permite resolver problemas de programación lineal de forma más rápida y sencilla.

 Es otra vía para resolver un problema de programación lineal.

Facilita profundizar en el contenido económico del problema original (primal).

Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener que resolver completamente el problema.

Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

Una desventaja de este método, es que se requiere para empezar a iterar la condición de factibilidad dual.


FORMATO CANÓNICO.

Un modelo de programación lineal está en formato canónico; si todas las variables son no negativas y las restricciones son del tipo ≤ para un objetivo de maximización o si todas las restricciones son del tipo ≥ para un objetivo de minimización.