Dualidad En Programación Lineal

Tema 3 Dualidad
En el desarrollo de la programaci´ n lineal la teoria de la dualidad es importante, o tanto desde el punto de vista te´ rico como desde el punto de vista pr´ ctico. Para o a cada modelo lineal se puede escribir el modelo dual asociado. Veremos que resolviendo uno de los modelos se obtiene la soluci´ n de ambos; en la tabla optima o ´ del modelo resuelto aparece tambi´ n lasoluci´ n optima del dual asociado. Algue o ´ nas razones por las que conviene tener en cuenta la dualidad son las siguientes: 1. Teniendo en cuenta que el n´ mero de iteraciones del algoritmo simplex u depende m´ s del n´ mero de restricciones del modelo que del n´ mero de a u u variables, y dado que resolviendo un modelo lineal se obtiene tambi´ n la e soluci´ n del dual asociado, se puede elegir elmodelo que conviene resolver o para obtener la soluci´ n de ambos. o 2. La dualidad permite hacer la interpretaci´ n econ´ mica del problema lineal. o o Veremos que la soluci´ n del problema dual da informaci´ n acerca de la o o soluci´ n del primal. o 3. Teniendo en cuenta las propiedades de la dualidad se construye un nuevo algoritmo, el simplex dual, que es m´ s eficaz que el simplex para calculara la soluci´ n optima de algunos modelos lineales. Adem´ s, este nuevo algoo ´ a o ritmo se aplica en el an´ lisis de sensibilidad y la programaci´ n entera que a se presentan en temas posteriores. 83

84

Tema 3. Dualidad

3.1 El problema dual
Definici´ n 3.1.1 (Forma sim´ trica de maximizaci´ n) Un modelo lineal est´ eso e o a crito en forma sim´ trica de maximizaci´ n si e o • elobjetivo es maximizar, • todas las restricciones son del tipo ≤, • todas las variables son no negativas. Ejemplo. Considerar el modelo lineal max z = x1 − 3x2 + x3 sujeto a x1 + x2 + x3 ≥ 2 −x1 + 2x2 − x3 ≤ 3 x1 − x2 + 2x3 = −1 x1 , x2 , x3 ≥ 0 la forma sim´ trica de maximizaci´ n es e o max z = x1 − 3x2 + x3 sujeto a −x1 − x2 − x3 ≤ −2 −x1 + 2x2 − x3 ≤ 3 x1 − x2 + 2x3 ≤ −1 −x1 + x2 − 2x3 ≤ 1 x1 , x2 ,x3 ≥ 0 2 Definici´ n 3.1.2 (Forma sim´ trica de minimizaci´ n) Un modelo lineal est´ eso e o a crito en forma sim´ trica de minimizaci´ n si e o • el objetivo es minimizar, • todas las restricciones son del tipo ≥,

OpenCourseWare, UPV/EHU

3.1. El problema dual

85

• todas las variables son no negativas. Ejemplo. Considerar el modelo lineal max z = x1 − x2 sujeto a 3x1 + 2x2 ≤ 1 x1 − 2x2≥ 3 x1 , x2 ≥ 0 la forma sim´ trica de minimizaci´ n es e o min (−z) = −x1 + x2 sujeto a −3x1 − 2x2 ≥ −1 x1 − 2x2 ≥ 3 x1 , x2 ≥ 0 2

3.1.1 Relaci´ n primal-dual o
Consideremos el siguiente modelo lineal en forma sim´ trica de maximizaci´ n al e o que llamaremos modelo primal max z = cT x sujeto a Ax ≤ b x≥0 el modelo dual es el siguiente modelo en forma sim´ trica de minimizaci´ n e o min G =bT y sujeto a AT y ≥ c y≥0

Investigaci´ n Operativa. Programaci´ n Lineal o o

86

Tema 3. Dualidad

Ejemplo. Dado el modelo lineal max z = 2x1 − x2 + 3x3 sujeto a x1 − x2 + x3 ≤ 2 3x1 − x2 + 2x3 ≤ 1 x1 , x2 , x3 ≥ 0 el dual asociado es min G = 2y1 + y2 sujeto a y1 + 3y2 ≥ 2 −y1 − y2 ≥ −1 y1 + 2y2 ≥ 3 y1 , y2 ≥ 0 2

3.1.2 Componentes de los modelos primal y dual
Dado un modelo linealprimal y su correspondiente dual la relaci´ n que existe o entre las componentes de ambos modelos es la siguiente • Si la matriz A del modelo primal es de tama˜ o m × n, el modelo primal n tiene m restricciones y n variables. La matriz del problema dual es AT y, por tanto, el modelo dual tiene n restricciones y m variables. • El vector b es el vector de recursos del problema primal y es el vectorde costes del problema dual. • El vector c es el vector de costes del problema primal y es el vector de recursos del problema dual. • El n´ mero de restricciones del primal es igual al n´ mero de variables del u u dual. • El n´ mero de variables del primal es igual al n´ mero de restricciones del u u dual.

OpenCourseWare, UPV/EHU

3.1. El problema dual

87

Objetivo: max restricci´ n...