Dualidad Y Transporte

1. Una brev´ısima introduccio´n.

Encontrar el ´optimo de un problema de optimizaci´on, es solo una parte del proceso de soluci´on. Muchas veces nos interesar´a saber como var´ıa la soluci´on si var´ıa alguno de los par´ametros del problema que frecuentemente se asumen como determin´ısticos, pero que tienen un caracter intr´ınsicamente aleatorio. M´as especificamente nos interesar´a saber para que rango de los par´ametros que determinan el problema sigue siendo valida la soluci´on encontrada.

Otro aspecto interesante es el tema de dualidad. Dualidad resulta de buscar relaciones que permitan obtener informaci´on adicional de un problema de optimizaci´on general. Esto, tra- ducido a PL nos conduce a relaciones primal-dual. Adem´as veremos algunos teoremas u´tiles de dualidad y el concepto de precio sombra.

2. Acerca de Dualidad

Todo problema de optimizaci´on (primal), tiene un problema asociado (dual) con numerosas propiedades que los relacionan y nos permiten hacer un mejor an´alisis de los problemas. A continuaci´on se describen los resultados que se ocupar´an en la resoluci´on de los problemas.

2.1. Construccio´n del problema dual

Bastante en general, para encontrar el dual de un problema lineal:

1. Si es problema de minimizaci´on el dual ser´a de maximizaci´on y viceversa.

2. En el dual habr´a tantas variables como restricciones 2 en el primal.

3. En el dual habra tantas restricciones como variables en el primal.

4. Los coeficientes de la funci´on objetivo del dual vendr´an dados por los coeficientes del lado derecho de las restricciones del primal.

5. Los coeficientes del lado derecho del dual vendr´an dados por los coeficientes de la funci´on objetivo del primal.

6. Los coeficientes que acompan˜ar´an a las variable en una restriccion del dual correspon- der´an a aquellos coeficientes que acompan˜an a la variable primal correspondiente a la restriccion dual 3.

7. Para saber si las restricciones duales son de ≤, = ´o ≥, se recurre a la tabla de relaciones primal-dual.

...