• Author / Uploaded
• Veronica Sierra

• Categories
• Matemáticas Aplicadas
• Física y matemáticas
• Matemáticas
• Análisis matemático
• Análisis

Citation preview

3.2 Relación primal-dual. Las relaciones del primal-dual son: 1. Si un problema primal tiene solución factible, el dual tendrá solución factible y viceversa. 2. Si el problema primal tiene solución factible y función objetivo no acotado, entonces el dual no tendrá solución factible y viceversa. 3. Si el primal no tiene soluciones factibles el dual no tiene solución factible o la función objetivo es no acotada. A menudo en investigación de operaciones, para formular un problema dual se presenta de acuerdo a la tabla 3.2.1.1 Primal estándar Problema objetivo

Problema dual Objetivo

Tipo de restricción

Signo de la variable

Maximización

Minimización

≥

No restringida

Minimización

Maximización

≤

No restringida

Tabla 3.2.1 La relación entre un problema primal y su dual es presentando las tablas óptimas para ambos. En la práctica obsérvese que no es necesario resolver ambos, resolviendo uno (mejor convenga), se puede dar la solución al otro. Suponga el ejemplo 3.2.1

Primal 𝑀𝑎𝑥 𝑋0 = 𝑋1 + 2𝑋2 𝑠. 𝑎 2𝑋1 + 8𝑋2 ≤ 16 𝑋1 + 𝑋2 ≤ 5 𝑋1 , 𝑋2 ≥ 0 Dual 𝑀𝑖𝑛 𝑦0 = 16𝑦1 + 5𝑦2 1

Hamdy Taha, Investigación de Operaciones, 6ª Ed. Editorial Prentice Hall

𝑠. 𝑎 2𝑦1 + 𝑦2 ≥ 1 8𝑦1 + 𝑦2 ≥ 2 𝑦1 , 𝑦2 ≥ 0 Tabla óptima 3.2.2 (resuelta por método simplex) 𝑋1

𝑋2

𝑆1

𝑆2

𝐿𝐷

𝑌0

0

0

1/6

2/3

6

𝑌2

0

1

1/6

-1/3

1

𝑌1

1

0

-1/6

4/3

4

Solución óptima 𝑍 𝑚𝑎𝑥 = 6 𝑋 =4 𝑉𝑅 1 𝑋2 = 1 𝑆 =0 𝑉𝐻 1 𝑆2 = 0

Tabla óptima dual 3.2.3 (por doble fase) 𝑋1

𝑋2

𝑆1

𝑆2

𝐴1

𝐴2

𝐿𝐷

𝑦0

0

0

-4

-1

—

—

6

𝑦2

0

1

-4/3 1/3

𝑦1

1

0

1/6 -1/6 -1/6 1/6

4/3 -1/3 2/3 1/6

Solución óptima: 𝑍𝑚𝑖𝑛 = 6 𝑦1 = 1/6

𝑦2 = 2/3

𝑆1 = 0

𝑆2 = 0

𝐴1 = 0

𝐴2 = 0

Obsérvese que en ambas tablas 3.2.2 y 3.2.3 tenemos la misma solución óptima. Análisis . Para el primal 𝑍𝑚𝑎𝑥 = 6, el dual 𝑍𝑚𝑖𝑛 = 6; propiedad que cuando una maximiza el otro minimiza, en ocasiones no da el mismo valor, esto ocurre cuando la propiedad de dualidad es débil. En este caso 𝑋0 < 𝑦0 , para el problema que se analiza la dualidad es fuerte 𝑋0 = 𝑦0 considerando que ambos problemas son óptimos. Análisis . Observemos en el primal los coeficientes en renglón 𝑋0 , los coeficientes de 𝑆1 y 𝑆2 (variables de inicio) corresponden a la solución de un problema dual como son 𝑆1 = 1/6 y 𝑆2 = 2/3, estos resultados se comparan en la tabla 3.2.3 y observamos que corresponden a las variables duales 𝑦1 = 1/6 y

𝑦2 = 2/3. En resumen, los valores óptimos para un problema dual estarán dados por las variables de aumento (de inicio) en este caso las variables de holgura 𝑆1 y 𝑆2 . Lo mismo ocurre si observamos el renglón 𝑦0 en la tabla 3.2.3 (dual), la solución óptima para el primal son los coeficientes que están bajo 𝑆1 y 𝑆2 que corresponden en orden a 𝑋1 = 4 y 𝑋2 = 1; obsérvese que se prescinde del negativo, esto porque el dual se cambia a minimizar y conocemos la propiedad de 𝑀𝑎𝑥𝑋0 − 𝑀𝑖𝑛(−𝑦0 ). De igual forma, de la tabla óptima 3.2.2 se obtienen las variables de aumento para el dual, estas se encuentran en el renglón 𝑋0 bajo las variables reales 𝑋1 y 𝑋2 ; por lo tanto, las variables de holgura 𝑆1 = 0 𝑆2 = 0. Así mismo, las variables de aumento para el primal están en el renglón 𝑦0 bajo las variables duales 𝑦1 y 𝑦2 , para nuestro ejemplo 𝑆1 = 0 𝑆2 = 0.