Dualidad

Reporte Exposición 2
• Dualidad
• Ideas intuitivas e interpretación económica
• Método simplex dual
• Análisis de sensibilidad
• Cambios en el lado derecho
• Cambios en la función objetivo
• Juegos estratégicos
• Juegos no-cooperativos en forma normal y en forma extensiva, estáticos y dinámicos
• Juegos en forma normal
• Estrategia dominante
• Equilibrio Nash


Dualidad

La teoríade la dualidad permite, relacionar cada problema de programación lineal con otro denominado problema dual y obtener relaciones sobre el tipo de soluciones de ambos problemas, también proporciona herramientas alternativas para comprobar la optimalidad de soluciones, así como condiciones que puedan utilizarse para el desarrollo de nuevos algoritmos de resolución, entre otros.

Interpretacióneconómica del problema dual
Precio sombra: se define como la proporción con que mejora el valor de la función objetivo a partir de la i – ésima restricción, dependiendo si se trata de maximización tiende a aumentar y a disminuir cuando es minimización.

La interpretación económica de la dualidad se basa directamente en la interpretación más frecuente del problema primal.

Interpretación delproblema dual. Para ver cómo la interpretación del problema primal conduce a una interpretación económica del problema dual. Nótese el valor de Z como:

Z = W1b1 + W2b2 + W3b3 + … + Wmbm

donde cada bi Wi puede interpretarse como la contribución a la ganancia por disponer de bi unidades del recurso i.

Wi se interpreta como la contribución a la ganancia por unidad del recurso i (i = 1, 2, …,m), cuando se usa el conjunto actual de variables básicas para obtener la solución primal.


Sujeto a:


j = 1, …, n m
Suma
i = 1 Unidades del recurso i – ésimo utilizados por unidad de la actividad j - ésima
* Valor unitario del recurso
i - ésimo
= Ganancia asignada a cada unidad de la actividad j - ésima


j = 1, …, m

*

Valor unitario del recurso
i - ésimo

≥ 0Método Simplex Dual

El Método Simplex es un algoritmo iterativo que se inicia en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (si esta existe). La base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que comoparte del Simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad, con este procedimiento se llega igualmente a la solución óptima.

El nuevo algoritmo fue desarrollado por C. E. Lemke en 1954 y se conoce con el nombre de Método Dual – Simplex.

Algoritmo Dual-Simplex para un modelo de maximización

La estrategia del métodoDual-Simplex consiste en la solución de un modelo de Programación Lineal desde el punto de vista Dual, pero trabajando desde la tabla Primal del problema. Se busca tener una solución Dual factible, hasta alcanzar condiciones óptimas en el Dual, aunque desde el punto Primal se tienen soluciones con condiciones óptimas que son no factibles.

Preliminares:

• El renglón cero de la tabla Primaltiene todos sus coeficientes como positivos o ceros (Dual factible). Esta es una condición necesaria para la aplicación directa del método.
• En este método todas las restricciones se escriben en la forma menor o igual que ( ≤ ) de tal forma que s epoda tener el conjunto correcto de variables básicas Duales, por la adición de variables de holgura positivas.
• Se tiene una solución básica factiblecon respecto al Dual, alguno o algunos coeficientes en el Lado Derecho tendrán un coeficiente negativo por la re expresión de las restricciones.
• Se siguen las condiciones del método y se actualiza la tabla de manera habitual; nuevamente manteniendo una solución Dual factible hasta que sea óptima desde el punto de vista Dual, trabajando en la tabla Primal.
• La función objetivo puede estar...