PRESENTACION

LISNEY SOLIS REYES
YESICA DIAZ
JAIR ZARA CORTEZ
WILSON GONZALES DELGADO
BRANDON MARTINEZ PALMEZANO

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.

DUALIDAD

TEORIA DE LA DUALIDAD

Cada problema de programación lineal tiene un segundo problema asociado con él. Uno se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas, de tal manera que la solución óptima a un problema proporciona información completa sobre la solución óptima para el otro.

Las relaciones entre el primal y el dual se utilizan para reducir el esfuerzo de cómputo en ciertos problemas y para obtener información adicional sobre las variaciones en la solución óptima debidas a ciertos cambios en los coeficientes y en la formulación del problema. Esto se conoce como análisis de sensibilidad o post-optimidad.

 DUALIDAD

El concepto de dualidad desempeña importantes papeles dentro de la programación lineal (también en la no lineal), tanto desde un punto de vista teórico como práctico. Todo programa lineal lleva asociado otro programa lineal conocido como su programa dual; el programa inicial se conoce también como programa primal

IMPORTANCIA DE LA DUALIDAD EN PROGRAMACIÓN LINEAL

La importancia de la teoría de la dualidad se puede resumir, entre otros aspectos, en lo siguiente:

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.

RELACIONES ENTRE LOS MODELOS PRIMAL Y DUAL

1. Los coeficientes objetivos de uno son los coeficientes recurso del otro.

2. Los coeficientes recurso de uno son los coeficientes objetivo del otro.

3. La matriz de coeficientes tecnológicos de uno es la transpuesta de la matriz de coeficientes tecnológicos del otro.

4. Ambos problemas están en formato canónico, como lo comprueban más en detalle las siguientes características

4.1 El objetivo del primo es maximizar en cambio el objetivo del dual es minimizar.

4.2 Las restricciones del Primo son del tipo =, mientras que las del dual son del tipo =.

4.3 Las variables de ambos problemas están restringidas a ser mayores o iguales que cero.

TABLA DE TUCKER

¿CÓMO CONVERTIR UN PROBLEMA PRIMAL A DUAL?

Un problema dual se formula de un problema primal de la siguiente forma:

1. Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.

3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.

4. Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

5. Los signos de desigualdad del problema dual son contrarios a los del primal.

6. Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierten en nuevas variables Ym en el dual.

EJERCICIOS