Problema dual (ejercicios)

ejercicios

1. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA
INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 1





PROBLEMA DUAL




 EJERCICIO N° 1



MAX: Z= 400A + 300B
S.a.
2A + B ≤ 60
A + 3B ≤ 40
A + B ≤ 30
A, B ≥ 0




FORMA ESTÁNDAR

Z= 400A + 300B + 0H1 + 0H2 + 0H3

2A + B + H1 ≤ 60
A + 3B +H2 ≤ 40
A + B + H3 ≤ 30
A, B, H1, H2, H3 ≥ 0




FORMA CANÓNICA O DE ECUACIONES

Z – 400A - 300B - 0H1 - 0H2 - 0H3 = 0

2A + B + H1

= 60
A + 3B +H2 = 40
A + B + H3 = 30
A, B, H1, H2, H3 ≥ 0




VARIABLES
BÁSICAS
VARIABLES
Z A B H1 H2 H3 VALOR
Z
H1
H2
1
0
0
-400 -300 0 0 0
1 1 0 0
3 0 1 0
0
2 60
1 40
H3 0 1 1 0 0 1 30

VE= A
VS= H3
PIVOTE=1

2. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA
INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 2


VARIABLES
BÁSICAS
VARIABLES
Z A B H1 H2 H3 VALOR
Z
H1
H2
A
1 0 100 0 0 400
0 0 -1 1 0 -2
0 0 2 0 1 -1
0 1 1 0 0 1
12000
0
10
30


SOLUCIÓN ÓPTIMA
Z= 12000


VALORES ÓPTIMOS

A=30 B=0


H1=0

H2=10

H3=0



FORMULACIÓN DEL PROBLEMA DUAL




MIN: Z= 60Y1 + 40Y2 + 30Y3

S.a.

2Y1 + Y2 + Y3 ≥ 400

Y1 + 3Y2 + Y3 ≥ 300

Yi ≥ 0






1. 2Y1 + Y3 = 400
-Y1 - Y3 = 300
Y1 = 100





2. 2Y1+ Y3 =400
2(100) + Y3 = 400
Y3 = 400-200
Y3 = 200

3. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA
INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 3




COMPROBACIÓN

Z= 60Y1 + 40Y2 + 30Y3

Z= 60(100)+40(0)+30(200)
Z= 6000 + 6000
Z= 12000




SOLUCIÓN ÓPTIMA
Z= 12000
VALORES ÓPTIMOS
Y1=100
Y2= 0

Y3= 200





 EJERCICIO N° 2

MIN: Z= 4X1 + 7X2
S.a.
X1 ≤ 6
2X2 = 14
3X1 + 2X2 ≥ 20
Xi ≥ 0


FORMA ESTÁNDAR

Z= 4X1 + 7X2 +MA1 +MA2 + 0H1 + 0H2 (-1)

-Z= -4X1 - 7X2 - MA1 - MA2 - 0H1 - 0H2




X1 + H1 ≤ 6

2X2 + A1 =14 (-M)

3X1 + 2X2 + A2 – H2 ≥ 20 (-M)

X1, X2, A1, A2, H1, H2 ≥ 0

4. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA
INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 4

VARIABLES
VARIABLES
BÁSICAS Z X1 X2 A1 A2 H1 H2 VALOR
Z -1 (-3M+4) (-4M+7) 0 0 0 M (-34M)
H1 0 1 0 0 0 1 0 6
A1 0 0 2 1 0 0 0 14




FORMA CANÓNICA O DE ECUACIONES

-Z + 4X1 + 7X2 +MA1 + MA2 + 0H1+ 0H2 = 0

- 3MX1

- 2MX2

- MA1


= -14M


-2MX2


-MA2

+ MH2 = -20M

-Z+ (-3M+4) X1+ (-4M+7) X2 +0H1+MH2 = -34M

S.a.

X1 + H1 = 6

2X2 + A1 = 14

3X1 + 2X2 + A2 -H2 = 20

X1, X2, A1, A2, H1, H2 ≥ 0











A2 0 3 2 0 1 0 -1 20

VE= X2
VS= A1
PIVOTE=2

VARIABLES
BÁSICAS
VARIABLES
Z X1 X2 A1 A2 H1 H2 VALOR
Z
H1
X2
-1
0
0
(-3M+4) 0 (2M-7/2) 0 0 M
0 0 0 1 0
1 1/2 0 0 0
(-6M-49)
1 6
0 7
A2 0 3 0 -1 1 0 -1 6

VE= X1
VS= A2
PIVOTE=3

VARIABLES
BÁSICAS
VARIABLES
Z X1 X2 A1 A2 H1 H2 VALOR
Z
H1
X2
X1
-1 0 0 (M-13/6) (M-4/3) 0 1 1/3
0 0 0 1/3 - 1/3 1 1/3
0 0 1 1/2 0 0 0
0 1 0 - 1/3 1/3 0 - 1/3
-57
4
7
2

5. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA
INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 5




SOLUCIÓN ÓPTIMA
Z= 57
VALORES ÓPTIMOS
X1=2 X2=7
H1=4 H2=10




FORMULACIÓN DEL PROBLEMA DUAL
MIN: Z= 6Y1 + 14Y2 + 20Y3
S.a.

Y1 + 3Y3 ≥ 4

2Y2 + 2Y3 < > 7

Yi ≥ 0




1. 3Y3 =4
Y3 = 4/3




2. 2Y2 + 2(4/3) =7
2Y2 +8/3 = 7
Y2 = 13/6




COMPROBACIÓN

Z= 6Y1 + 14Y2 + 20Y3

Z= 6(0)+14(13/6)+20(4/3)
Z= 57


SOLUCIÓN ÓPTIMA
Z= 57
VALORES ÓPTIMOS

Y1=0 Y2= 13/6 Y3= 4/3

6. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA

INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 6




 EJERCICIO N° 3

MAX: Z= 4X1 + 7X2
S.a.


X1 ≤ 4
2X2 ≤ 12
3X1 + 2X2 = 18
Xi ≥ 0





FORMA ESTÁNDAR

Z= 4X1 + 7X2 –MA1 + 0H1 + 0H2

X1 + H1 ≤ 4

2X2 + H2 ≤ 12

3X1 + 2X2 + A1 = 18 (-M)

X1, X2, A1, H1, H2 ≥ 0






FORMA CANÓNICA O DE ECUACIONES

Z - 4X1 -7X2 +MA1 - 0H1 - 0H2 = 0


-3MX1 - 2MX2

- MA1


= -18M

Z+ (-

3M-4) X1+ (-2M-7)

X2

- 0H1 - 0H2

= -18M



S.a.

X1 + H1 = 4

2X2 + H2 = 12

3X1 + 2X2 + A1 = 18

X1, X2, A1, H1, H2 ≥ 0

7. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA

INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 7




VARIABLES
BÁSICAS
VARIABLES
Z X1 X2 A1 H1 H2 VALOR
Z
A1
1
0
(-3M-4) (-2M-7) 0 0 0
2 1 0 0
(-18M)
3 18
H1 0 1 0 0 1 0 4
H2 0 0 2 0 0 1 12

VE= X1
VS= H1
PIVOTE=1



VARIABLES
BÁSICAS
VARIABLES
Z X1 X2 A1 H1 H2 VALOR
Z 1 0 (-2M-7) 0 (3M+4) 0 (-6M+169
A1 0 0 2 1 -3 0 6
X1
H2
0 1
0 0
0 0 1
0 0
0
1
4
2 12

VE= X2
VS= A1
PIVOTE=2



VARIABLES
BÁSICAS
VARIABLES
Z X1 X2 A1 H1 H2 VALOR
Z
X2
X1
1 0 0 (M+7/2)
0 0 1 1/2
0 1 0 0
-6 1/2 0
0
0
37
-1 1/2 3
1 4
H2 0 0 0 -1 3 1 6

VE= H1
VS= H2
PIVOTE=3



VARIABLES
BÁSICAS
VARIABLES
Z X1 X2 A1 H1 H2 VALOR
Z
X2
X1
H1
1 0 0 (M+4/3) 0 2 1/6
0 0 1 0 0 1/6
0 1 0 1/3 0 - 1/3
0 0 0 - 1/3 1 1/3
50
6
2
2

8. UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE CIENCIAS POLÍTICAS Y ADMINIS TRATIVAS
CARRERA DE CONTABILIDAD Y AUDITORÍA

INVESTIGACIÓN OPERATIVA I QUINTO SEMESTRE “A” YAMBAY JOSSELIN Página 8




SOLUCIÓN ÓPTIMA
Z= 50
VALORES ÓPTIMOS
X1=2 X2=6
H1=2 H2=0




FORMULACIÓN DEL PROBLEMA DUAL
MIN: Z= 4Y1 + 12Y2 + 18Y3
S.a.

Y1 + 3Y3 ≥ 4

2Y2 + 2Y3 ≥ 7

Yi ≥ 0




1. 3Y3 = 4
Y3 = 4/3



2. 2Y2 +2(4/3) = 7
2Y2 = 13/3
Y2 = 13/6




COMPROBACIÓN

Z= 4Y1 + 12Y2 + 18Y3

Z= 4(0)+12(13/6)+18(4/3)
Z= 50


SOLUCIÓN ÓPTIMA
Z= 50
VALORES ÓPTIMOS

Y1=0 Y2= 13/6 Y3= 4/3