UNIVERSIDAD NACIONAL PEDRO RUIZ GALLO
FACULTAD DE INGENIERIA CIVIL, SISTEMAS Y ARQUITECTURA
ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS
INVESTIGACIÓN DE OPERACIONES I.
SANDOVAL QUINDE, MARICIELO
LOYAGA ORBEGOZO, GAVINO MARCELO
CONJUNTO DE PROBLEMAS 4.1A
1. En el ejemplo 4.1-1, deduzca el problema dual asociado si el sentido de la
optimización en el problema primal se cambia a minimización.
PRIMAL PRIMAL EN FORMA DE VARIABLES
ECUACIÓN DUALES
Minimizar z = 5 X1 + 12 X2 + Minimizar z = 5 X1 + 12 X2 + 4
4 X3 X3
Sujeta a: Sujeta a: Y1
X1 + 2X2 ≥10 X1 + 2X2+ X3 + X4 = 10 y2
2X1 – X2 + 3X3 = 8 2X1 – X2 + 3X3 + 0X4 = 8
X1, X2, X3 ≥ 0 X1, X2, X3 , X4 ≥ 0
DUAL
Maximizar W = 10Y1 +
8Y2
Sujeta a:
Y1 + 2Y2 ≤ 5
2Y1 – Y2 ≤ 12
Y1 + 3Y2 ≤ 4
Y1, Y3 ≥ 0, Y2 sin
restricción.
2. En el ejemplo 4.1-2 deduzca el problema dual asociado si el problema primal
se aumenta con una tercera restricción, 3X1+ X2 = 4.
PRIMAL PRIMAL EN FORMA DE VARIABLES
ECUACIÓN DUALES
Minimizar z = 15 X1 + 12 X2 Minimizar z = 15 X1 + 12 X2 +4 X3 +
+ 4 X3 0X4+0X5
Sujeta a: Sujeta a: Y1
X1 + 2X2+ ≥3 X1 + 2X2 - X3 + 0X4 = 3 y2
2X1 – 4X2 ≤ 5 -2X1 + 4X2 + 0X3 + X4 = 5
3X1+ X2 = 4 3X1+ X2 + 0X3 + 0X4 + X5 = 4
X1, X2 ≥ 0 X1, X2, X3 , X4 ≥ 0
DUAL
Maximizar W = 3Y1 +
5Y2 + 4Y2
Sujeta a:
Y1 - 2Y2 + 3Y3 ≤ 15
2Y1 + 4Y2 + Y3 ≤ 12
Y1, Y2 sin restricción, Y3
≥0
3. En el ejemplo 4.1-3 demuestre que aun cuando se cambie el sentido de la
optimización en el primal a minimización, una variable primal no restringida
corresponde siempre a una restricción dual de igualdad.
PRIMAL DUAL
Minimizar z = 5 X1 + 6 X2
Sujeta a: Maximizar W = 5Y1 + 3Y2 + 8Y2
X1 + 2X2= 5 Sujeta a:
-X1 + 5X2 ≥ 3 Y1 - Y2 + 4Y3 ≤ 5
4X1 + 7X2 <=8 -Y1 + Y2 -4Y3 ≤ -5
X1 no restringida, X2 ≥ 0 2Y1 + 5Y2 +7Y3 ≤ 6
PRIMAL EN FORMA DE - Y2 +Y3 ≤ 0
ECUACIÓN
Sustituir X1 = X4 - X3 Y1, Y2, Y3 NO RESTRINGIDA
Minimizar z = 5X4 - 5X3+ 6 X2
Sujeta a:
X4 - X3 + 2X2 = 5
-X4 + X3 + 5X2 – X3 + X5= 3
4X4 - 4X3 + 7 X2 + X6 = 8
X2, X3 , X4 ,X5≥ 0
PRIMAL:
DUAL:
4. Escriba el dual de cada uno de los siguientes problemas primales:
a)
PRIMAL DUAL
MAX Z = -5 X1 + 2 X2 MIM W = -2 Y1 + 5 Y2
Sujeta a: Sujeta a:
-X1 + X2 + X3 ≤ -2 -Y1 + 2X2 ≥ -5
2X1 + 3X2 + 0X3 + X4 ≤ 5 Y1 + 3Y2 ≥ 2
X1, X2, X3 , X4 ≥ 0 Y1 + 0Y2 ≥ 0
0Y1 + Y2 ≥ 0
Y1, Y2 ≥ 0
b)
PRIMAL DUAL
MIN Z = 6 X1 + 3 X2 MAX w = 2Y1 + 5 Y2
Sujeta a: Sujeta a:
6X1 - 3X2 + X3 – X4 + X6 ≥ 2 6Y1 + 3X2 ≤ 6
3X1 + 4X2 + X3 – X5 + X7 ≥ 5 -3Y1 + 4Y2 ≤ 3
X1, X2, X3 ≥ 0 Y1 + Y2 ≤ 0
Y1, Y2 ≥ 0
c)
PRIMAL DUAL
X1 = X4 –X3 MAX w= 5Y1 + 6 Y2
X2 = X6 - X5 Sujeta a:
MIN Z = X1 + X2 2Y1 + 3X2 ≤ 1
Sujeta a: -2Y1 - 3Y2 ≤ 1
2X4 -2X3 + X6 – X5 = 5 Y1, Y2 ≥ 0
3X4 – 3X3 – X6 + X5 =6
X3, X4, X5 , X6 ≥ 0
5. Acerca del ejemplo 4.1-1. Para aplicar el método simplex al primal se
requiere usar una variable artificial en la segunda restricción del primal,
para asegurar una solución básica de inicio. Demuestre que la presencia de
una variable artificial en el primal no afecta la definición del dual, porque
conduce a una restricción dual redundante.
DUAL:
6. ¿Cierto o falso?
a) El dual del problema dual da como resultado el primal original. (V)
b) Si la restricción primal está originalmente en forma de ecuación, la variable dual
correspondiente es necesariamente no restringida. (V)
c) Si la restricción primal es del tipo , la variable dual correspondiente será no negativa
(no positiva) dependiendo de si el objetivo primal es maximización (minimización). (V)
d) Si la restricción primal es del tipo, la variable dual correspondiente será no negativa
(no positiva) dependiendo si el objetivo primal es minimización o (maximización). (F)
e) Una variable primal no restringida dará como resultado una restricción dual de
igualdad. (V)
7. Con frecuencia se citan las siguientes reglas explícitas, en la mayor parte de los
libros sobre investigación de operaciones y programación lineal, para formar el
problema dual. Demuestre que esas reglas están implícitas en la definición general
de la tabla 4.2.
a) Maximizar Z= 10X1 + 24X2 + 8X3
Sujeto a:
2X1 + 4X2 + 2X3 <= 20
4X1 - 2X2 + 6X3 = 16
X1,X2,X3 >= 0
Primal en forma de ecuación:
Maximizar Z= 10X1 + 24X2 + 8X3
Sujeto a:
2X1 + 4X2 + 2X3 + X4 = 20 …Y1
4X1 - 2X2 + 6X3 + 0X4 = 16 …Y2
Convirtiendo a dual:
Minimizar W= 20Y1 + 16Y2
Sujeto a:
2Y1 + 4Y2 >= 10
4Y1 - 2Y2 >= 24
2Y1 + 6Y2 >= 8
Y1 + 0Y2 >= 0
Y1 >=0; Y2 es irrestricta
b) Minimizar Z= 10X1 + 24X2 + 8X3
Sujeto a:
2X1 + 4X2 + 2X3 <= 20
4X1 - 2X2 + 6X3 = 16
X1,X2,X3 >= 0
Primal en forma de ecuación:
Minimizar Z= 10X1 + 24X2 + 8X3
Sujeto a:
2X1 + 4X2 + 2X3 + X4 = 20 …Y1
4X1 - 2X2 + 6X3 + 0X4 = 16 …Y2
Convirtiendo a dual:
Maximizar W= 20Y1 + 16Y2
Sujeto a:
2Y1 + 4Y2 <= 10
4Y1 - 2Y2 <= 24
2Y1 + 6Y2 <= 8
Y1 + 0Y2 <= 0
Y1 >=0; Y2 no esta restringida.
CONJUNTO DE PROBLEMAS 4.2C
1. Resuelva con TORA el dual del problema siguiente, y a continuación
determine su solución óptima a partir de la solución del dual. ¿Es mejor este
procedimiento desde el punto de vista de cómputo?
Minimizar Z= 5X1 + 6X2 + 3X3
Sujeto a:
5X1 + 5X2 + 3X3 >= 50
X1 + X2 – X3 >= 20
7X1 + 6X2 – 9X3 >= 30
5X1 + 5X2 + 5X3 >= 35
2X1 + 4X2 – 15X3 >= 10
12X1 + 10X2 >= 90
X2 – 10X3 >= 20
X1, X2, X3 >= 0
Primal en forma de ecuación:
Minimizar Z= 5X1 + 6X2 + 3X3
Sujeto a:
5X1 + 5X2 + 3X3 – X4 + 0X5 = 50
X1 + X2 – X3 – X5 + 0X6 = 20
7X1 + 6X2 – 9X3 – X6 + 0X7 = 30
5X1 + 5X2 + 5X3 - X7 + 0X8 = 35
2X1 + 4X2 – 15X3 – X8 + 0X9 = 10
12X1 + 10X2 – X9 + 0X10 = 90
X2 – 10X3 – X10 + 0X11 = 20
Convirtiendo a Dual:
Maximizar W= 50Y1 + 20Y2 + 30Y3 + 35Y4 + 10Y5 + 90Y6 + 20Y7
Sujeto a:
5Y1 + Y2 + 7Y3 + 5Y4 + 2Y5 + 12Y6 <= 5
5Y1 + Y2 + 6Y3 + 5Y4 + 4Y5 + 10Y6 + Y7 <= 6
3Y1 - Y2 - 9Y3 + 5Y4 - 15Y5 - 10Y7 <= 3
Y1, y2, y3, y4, y5, y6, y6, y7>= 0
En forma Primal
En forma Dual
La única diferencia, es que en el modelo de PL la cantidad de variables es
considerablemente menor que las restricciones, en donde se puede ahorrar cálculos
resolviendo el dual. Y en el caso de un problema dual hay más variables que
restricciones.
2. Se tiene la siguiente programación lineal:
Maximizar Z = 5X1 + 2X2 + 3X3
sujeta a
X1 + 5X2 + 2X3 = 30
X1 - 5X2 - 6X3 ≤ 40
X1, X2, X3 ≥ 0
La solución óptima produce la siguiente ecuación objetivo:
Z = 0X1 + 23X2 + 7X3 + (5 + M)X4 + 0X5 + 150
donde las variables básicas de inicio son x4 artificial y x5 de holgura. Escriba el
problema dual asociado y determine su solución óptima a partir de la ecuación de
z óptima.
Convirtiendo a Dual
Min W = 30Y1 + 40Y2
Sujeto a:
Y1 + Y2 ≥ 5
5Y1 – 5Y2 ≥ 2
2Y1 – 6Y2 ≥ 3
Y2 ≥ 0 ; Y1 ≥ -M
Variable de
inicio: X4 → Y1
≥ -M
X5 → Y2 ≥ 0
5 + M = Y1 – (-
M) 0
= Y2 – 0
Y1 = 5
Y2 = 0
3. En la siguiente programación lineal:
Maximizar Z = 2X1 + 4X2 + 4X3 – 3X4
sujeta a
X1 + 4X2 + X3 + X4 = 8
X1 + 4X2 + X3 + X4 = 4
X1, X2, X3, X4 ≥ 0
DUAL
Min W = 4Y1 + 8Y2
Sujeto a:
Y1 + Y2 ≥ 2
Y1 + 4Y2 ≥ 4
Y1 + 0Y2 ≥ 4
0Y1 + Y2 ≥ -3
→ Y1 - 4 = 0 → Y1 = 4
→ Y2 + 3 = 3 → Y2 = 0
4. Se tiene la siguiente programación lineal:
Maximizar Z = X1 + 5X2 + 3X3
sujeta a
2X1 + 2X2 + X3 = 3
2X1 - X2 = 4
X1, X2, X3 ≥ 0
a) Escriba el problema dual [Link] W = 3Y1 + 4Y2
Sujeto a:
Y1 + 2Y2 ≥ 1
2Y1 – 2Y2 ≥ 5
Y1 ≥ 3
Y2 ≥ 0
5. Determine una solución factible del siguiente conjunto de desigualdades,
usando el problema dual:
2X1 + 3X2 ≤ 12
-3X1 + 2X2 ≤ -4
3X1 - 5X2 ≤ 2
X1 sin restricción
X2 ≥ 0
DUAL
Min W = 12Y1 + 4Y2 + 2Y3
Sujeto a:
2Y1 +3Y2 + 3Y3 = 0
3Y1 – 2Y2 – 5Y3 ≥ 0
Y1, Y2, Y3 ≥ 0
6. Determine el valor óptimo de la función objetivo para el siguiente
problema, con sólo inspeccionar el dual (no resuelva el dual por el método
simplex).
Minimizar Z = 10X1 + 4X2 + 5X3
sujeta a:
5X1 - 7X2 + 3X3 ≥ 50
X1, X2, X3 ≥ 0
Max W = 50Y1 + 0Y2 +
0Y3 + 0Y4
Sujeto a:
5Y1 ≤ 10
-7Y1 ≤ 4
3Y1 ≤ 5
Y1 = 0, Y2 = 0
