Scribd
Cargar
7 vistas10 páginas

Equivalencias en Programación Lineal

El documento presenta un análisis del problema dual de programación lineal, incluyendo un sistema de ecuaciones para el proceso de producción y su resolución mediante el método simplex. Se establecen equivalencias entre las variables del problema primal y dual, así como los valores óptimos de cada variable. Además, se detallan las relaciones entre las variables reales y de holgura en ambos problemas.

Cargado por

Renzo Lui Urbisagastegui Apaza
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
7 vistas10 páginas

Equivalencias en Programación Lineal

El documento presenta un análisis del problema dual de programación lineal, incluyendo un sistema de ecuaciones para el proceso de producción y su resolución mediante el método simplex. Se establecen equivalencias entre las variables del problema primal y dual, así como los valores óptimos de cada variable. Además, se detallan las relaciones entre las variables reales y de holgura en ambos problemas.

Cargado por

Renzo Lui Urbisagastegui Apaza
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

SESIÓN VII

EQUIVALENCIAS
INVESTIGACIÓN OPERATIVA I

DR. JAIME ZULOETA VERA


EQUIVALENCIAS
Problema Dual de Programación Lineal
Planteo:
Sea el problema que se propuso en la sesión anterior:
A B DISPONIBILIDADES
MAQUINADO 4 8 480 Y1
INCIDENCIA EN EL
ARMADO 5 6 600 Y2 BENEFICIO POR DPTO.
MONTAJE 12 8 540 Y3
BENEFICIO 100 120
X1 X2

CANTIDADES A
PRODUCIR
EQUIVALENCIAS:
El sistema de ecuaciones del proceso de producción será:
4𝑋1 + 8𝑋2 + 𝑋3 = 480
5𝑋1 + 6𝑋2 + 𝑋4 = 600
12𝑋1 + 8𝑋2 + 𝑋5 = 540
𝑋1 ˄ 𝑋2 ≥ 0
Y su resolución por el método simplex será:
……
X1 X2 X3 X4 X5
Cj 100 120 0 0 0
Ck Pk P0 P1 P2 P3 P4 P5
0 P3 480 4 8 1 0 0 480 / 8 = 60
0 P4 600 5 6 0 1 0 600 / 6 = 100
0 P5 540 12 8 0 0 1 540 / 8 = 67.5
Zj 0 0 0 0 0 0
Zj - Cj X -100 -120 0 0 0
120 P2 60 1 / 2. 1 1 / 8. 0 0 60 / (1/2) = 120
0 P4 240 2 0 ° - 3 / 4. 1 0 240 / 2 = 120
0 P5 60 8 0 -1 0 1 60 / 8 = 7.5
Zj 7200 60 120 15 0 0
Zj - Cj X -40 0 15 0 0
120 P2 56.25 0 1 3 / 16 . 0 ° - 1 / 16.
0 P4 225 0 0 ° - 1 / 2. 1 ° - 1 / 4.
100 P1 7.5 1 0 ° - 1 / 8. 0 ° - 1 / 8.
Zj 7500 100 120 10 0 5
Zj - Cj X 0 0 10 0 5
Dual Y4 Y5 Y1 Y2 Y3
EQUIVALENCIAS
V.R.P V.H.P
𝑷𝑹𝑰𝑴𝑨𝑳: 𝑋1 , 𝑋2 , … … … 𝑋3 , 𝑋4 , 𝑋5 , …

𝑫𝑼𝑨𝑳 ∶ 𝑌1 , 𝑌2 , 𝑌3 , … … … 𝑌4 , 𝑌5 , …
V.R.D V.H.D

A las variables reales del Primal le corresponde las variables de holgura del Dual y, a las
variables de holgura del Primal le corresponde las variables reales del Dual.
Para hallar éstas equivalencias se emplean las siguientes formulas:

𝑿𝒏+𝒊 = 𝒀𝒊 𝒚 𝑿𝒋 = 𝒀𝒎+𝒋
EQUIVALENCIAS
Entonces, conociendo que el Problema directo se tiene (Sin contar las Variables Slacks):
𝑚 𝑁° 𝑑𝑒 𝐹𝑖𝑙𝑎𝑠 = 3 … … … … 𝑝𝑎𝑟𝑎 𝑖 = 1 , 2 , 3
𝑚 𝑁° 𝑑𝑒 𝑐𝑜𝑙𝑢𝑚𝑛𝑎𝑠 = 2 … … … … 𝑝𝑎𝑟𝑎 𝑗 = 1 , 2
Será:

𝑿𝒏+𝒊 𝑝𝑎𝑟𝑎 "𝒊" 𝑣𝑎𝑟𝑖𝑎𝑛𝑑𝑜 : 𝑿𝒋 𝑝𝑎𝑟𝑎 "𝒋" 𝑣𝑎𝑟𝑖𝑎𝑛𝑑𝑜 :


𝑃𝑎𝑟𝑎 𝑖 = 1 → 𝑋2+1 = 𝑋3 = 𝑌𝑖 = 𝑌1 𝑃𝑎𝑟𝑎 𝑗 = 1 → 𝑋1 = 𝑌3+1 = 𝑌4
𝑃𝑎𝑟𝑎 𝑖 = 2 → 𝑋2+2 = 𝑋4 = 𝑌𝑖 = 𝑌2 𝑃𝑎𝑟𝑎 𝑗 = 2 → 𝑋2 = 𝑌3+2 = 𝑌5
𝑃𝑎𝑟𝑎 𝑖 = 3 → 𝑋2+3 = 𝑋5 = 𝑌𝑖 = 𝑌3
EQUIVALENCIAS
EQUIVALENCIAS
PRIMAL DUAL

𝑋1 = 𝑃1 = 7.5 𝑌4 = 0 − 7.5
𝑋2 = 𝑃2 = 56.25 𝑌5 = 0 − 56.25
𝑋3 = 𝑃3 = 0 𝑌1 ≠ 0
𝑋4 = 𝑃4 = 225 𝑌2 = 0 − 225
𝑋5 = 𝑃5 = 0 𝑌3 ≠ 0
EQUIVALENCIAS
Las variables ≠ 0 , están en la última Solución Óptima de la Tabla del Dual así:

480 600 540 0 0


𝐶𝐾 𝑌𝐾 𝑌0 𝑌1 𝑌2 𝑌3 𝑌4 𝑌5

480 𝑌1 10 1 1/2 0 1/8 - 3/16

540 𝑌3 5 0 1/4 1 - 1/8 1/16

𝑍𝑗 7500 480 375 540 -7.5 -56.25

𝑍𝑗 − 𝐶𝑗 X 0 -225 0 -7.5 -56.25


EQUIVALENCIAS
Y1:
𝑋1 = 𝑃1 = −1/8 𝑌4 = 1/8
𝑋2 = 𝑃2 = 3/16 𝑌5 = − 3/16
𝑋4 = 𝑃4 = −1/2 𝑌2 = 1/2
Y3:
𝑋1 = 𝑃1 = 1/8 𝑌4 = −1/8
𝑋2 = 𝑃2 = −1/16 𝑌5 = 1/16
𝑋4 = 𝑃4 = −1/4 𝑌2 = 1/4
Los 𝑍𝑗 − 𝐶𝑗 ; 𝑑𝑒𝑙 𝑝𝑟𝑖𝑚𝑎𝑙 𝑠𝑜𝑛 𝑙𝑜𝑠 𝑃0 𝑜 𝑌0 𝑑𝑒𝑙 𝐷𝑢𝑎𝑙:

𝒀𝟏 = 𝟏𝟎 , 𝒀𝟑 = 𝟓

También podría gustarte