• Categories
• Matemática

Citation preview

´ Operativa Investigacion ´ Sebastian Albuja, INGENIERI´A MECANICA

NRC: 4225; 29/12/2017; [email protected] ; Sangolqu´ı-Ecuador ´ ´ VARIOS METODOS DE RESOLUCION Resolver los siguientes problemas. Si es de dos variables desarrolle una soluci´ on gr´ afica y use el m´ etodo de dos fases, en caso contrario use el m´ etodo DUAL o el de DOS FASES y compruebe su resultado con cualquier paquete computacional. 1. Minimizar Z = 4X1 +X2 sujeto a: 3X1 + X2 = 3 4X1 + 3X2 ≥ 6 X1 + 2X2 ≤ 4 a) M´ etodo de dos fases:

  

3X1 + X2 + m1 = 3 4X1 + 3X2 − S2 + m2 = 6

 

X1 + 2X2 + S3 = 4

Min Z = m1 +m2 Cj 1 1 0

Xj m1 m2 S3 Zj Zj − C j

bm 3 6 4 9

Cj 0 1 0

Xj X1 m2 S3 Zj Zj − C j

bm 1 2 3 2

0 X1 3 4 1 7 7 0 X1 1 0 0 0 0

0 X2 1 3 2 4 4

0 S2 0 -1 0 -1 -1

0 S3 0 0 1 0 0

1 m1 1 0 0 1 0

0 X2 1/3 5/3 5/3 5/3 5/3

0 S2 0 -1 0 -1 -1

0 S3 0 0 1 0 0

1 m1 1/3 -4/3 -1/3 -4/3 -7/3

1 m2 0 1 0 1 0 1 m2 0 1 0 1 0

Page 1 of 18

Cj 0 0 0

Xj X1 X2 S3 Zj Zj − C j

bm 3/5 6/5 1 0

0 X1 1 0 0 0 0

0 X2 0 1 0 0 0

0 S2 1/5 -3/5 1 0 0

0 S3 0 0 1 0 0

1 m1 3/5 -4/5 1 0 -1

1 m2 -1/5 3/5 -1 0 -1

 3 1   X1 + S2 =   5 5  3 6 X2 − S2 =   5 5    S2 + S3 = 1 Min Z = 4X1 +X2 Cj 4 1 0

Xj X1 X2 S3 Zj Zj − C j

bm 3/5 6/5 1 18/5

4 X1 1 0 0 4 0

1 X2 0 1 0 1 0

0 S2 1/5 -3/5 1 1/5 1/5

Xj X1 X2 S2 Zj Zj − Cj

bm 2/5 9/5 1 17/5

4 X1 1 0 0 4 0

1 X2 0 1 0 1 0

0 S2 0 0 1 0 0

Cj 4 1 0

0 S3 0 0 1 0 0 0 S3 -1/5 3/5 1 -1/5 -1/5

Respuestas:

2 5 9 X2 =  5     M in(Z) = 17 5       

X1 =

b) Soluci´ on Gr´ afica:

Page 2 of 18

Fig. 1.- Ejercicio resuelto mediante Geogebra.

2. Minimizar Z = X1 +2X2 sujeto a: 3X1 + X2 ≥ 3 4X1 + 3X2 ≥ 6 X1 + X2 ≤ 3 a) M´ etodo de dos fases:

   3X1 + X2 − S1 + m1 = 3 4X1 + 3X2 − S2 + m2 = 6   X1 + X2 + S3 = 3 Min Z = m1 +m2 Cj 1 1 0

Xj m1 m2 S3 Zj Zj − C j

bm 3 6 3 9

0 X1 3 4 1 7 7

0 X2 1 3 1 4 4

0 S1 -1 0 0 -1 -1

0 S2 0 -1 0 -1 -1

0 S3 0 0 1 0 0

1 m1 1 0 0 1 0

1 m2 0 1 0 1 0

Page 3 of 18

Cj Xj X1 m2 S3 Zj Zj − Cj

0 1 0

bm 1 2 2 2

0 X1 1 0 0 0 0

0 X2 1/3 5/3 2/3 5/3 5/3

bm 3/5 6/5 6/5 0

0 X1 1 0 0 0 0

0 X2 0 1 0 0 0

Cj 0 0 0

Xj X1 X2 S3 Zj Zj − C j

0 S1 -1/3 4/3 1/3 4/3 4/3 0 S1 -3/5 4/5 -1/5 0 0

0 S2 0 -1 0 -1 -1

0 S3 0 1 0 1 1

1 m1 1/3 -4/3 -1/3 -4/3 -7/3

1 m2 0 1 0 1 0

0 S2 1/5 -3/5 2/5 0 0

0 S3 0 0 1 0 0

1 m1 3/5 -4/5 1/5 0 -1

1 m2 -1/5 3/5 -2/5 0 -1

 3 1 3   X1 − S1 + S2 =   5 5 5   4 3 6 X2 + S1 − S2 =  5 5 5    2 1  − S1 + S2 + S3 = 6 5 5 5 Min Z = X1 +2X2 Cj 1 2 0

Xj X1 X2 S3 Zj Zj − C j

bm 3/5 6/5 6/5 3

Cj 1 0 0

Xj X1 S1 S3 Zj Zj − C j

bm 3/2 3/2 3/2 3/2

1 X1 1 0 0 1 0 1 X1 1 0 0 1 0

2 X2 0 1 0 2 0 2 X2 3/4 5/4 1/4 3/4 -5/4

0 S1 -3/5 4/5 -1/5 1 1 0 S1 0 1 0 0 0

0 S2 1/5 -3/5 2/5 -1 -1 0 S2 -1/4 -3/4 1/4 -1/4 -1/4

0 S3 0 0 1 0 0 0 S3 0 0 1 0 0

Respuestas:

3 2 X2 = 0     M in(Z) = 3 2      

X1 =

b) Soluci´ on Gr´ afica:

Page 4 of 18

Fig. 2.- Ejercicio resuelto mediante Geogebra.

3. Maximizar Z = X1 +X2 sujeto a: X1 + 2X2 ≤ 6 2X1 + X2 ≥ 9 a) M´ etodo de dos fases:

(

X1 + 2X2 + S1 = 6 2X1 + X2 − S2 + m2 = 9

Min Z = m2 Cj 0 1

Xj S1 m2 Zj Zj − C j

bm 6 9 9

Cj 0 0

Xj S1 X1 Zj Zj − C j

bm 3/2 9/2 0

0 X1 1 2 2 2 0 X1 0 1 0 0

0 X2 2 1 1 1 0 X2 3/2 1/2 0 0

0 S1 1 0 0 0 0 S1 1 0 0 0

0 S2 0 -1 -1 -1 0 S2 1/2 -1/2 0 0

1 m2 0 1 1 0 1 m2 -1/2 1/2 0 -1

Page 5 of 18

 3   X2 + S1 + 2  X1 + 1 X2 − 2 Cj 1 0

Xj X1 S1 Zj Zj − Cj

bm 9/2 3/2 9/2

1 X1 1 0 1 0

1 X2 1/2 3/2 1/2 -1/2

Xj X1 X2 Zj Zj − C j

bm 4 1 5

1 X1 1 0 1 0

1 X2 0 1 1 0

Cj 1 1

Cj 1 0

1 3 S2 = 2 2 1 9 S2 = 2 2

Xj X1 S2 Zj Zj − C j

bm 6 3 6

1 X1 1 0 1 0

1 X2 2 3 2 1

0 S1 0 1 0 0

0 S2 -1/2 1/2 -1/2 -1/2

0 S1 -1/3 2/3 1/3 1/3

0 S2 -2/3 1/3 -1/3 -1/3

0 S1 1 2 1 1

0 S2 0 1 0 0

Respuestas:

  

X1 = 6

X2 = 0   M ax(Z) = 6 b) Soluci´ on Gr´ afica:

Page 6 of 18

Fig. 3.- Ejercicio resuelto mediante Geogebra.

4. Maximizar Z = 2X1 +3X2 sujeto a: X1 + 3X2 ≤ 6 3X1 + 2X2 ≤ 6 a) M´ etodo de dos fases:

(

X1 + 3X2 + S1 = 6 3X1 + 2X2 + S2 = 6

Debido a que no existen variables artificiales, se prosigue a la fase 2. Cj 0 0

Xj S1 S2 Zj Zj − C j

bm 6 6 0

Cj 3 0

Xj X2 S2 Zj Zj − C j

bm 2 2 6

2 X1 1 3 0 -2

3 X2 3 2 0 -3

0 S1 1 0 0 0

2 X1 1/3 7/3 1 -1

3 X2 1 0 3 0

0 S1 1/3 -2/3 1 1

0 S2 0 1 0 0 0 S2 0 1 0 0

Page 7 of 18

Cj 3 2

Xj X2 X1 Zj Zj − Cj

bm 12/7 6/7 48/7

2 X1 0 1 2 0

3 X2 1 0 3 0

0 S1 3/7 -2/7 5/7 5/7

0 S2 -1/7 3/7 3/7 3/7

Respuestas:

6 7 12 X2 =  7    48  M ax(Z) = 7       

X1 =

b) Soluci´ on Gr´ afica:

Fig. 4.- Ejercicio resuelto mediante Geogebra.

5. Maximizar Z = 6X1 +4X2 +2X3 sujeto a: 6X1 + 2X2 + 6X3 ≥ 6 6X1 + 4X2 = 12 2X1 - 2X2 ≤ 2 Se comprob´ o mediante el programa QM que el sistema no tiene soluci´on.

Page 8 of 18

Fig. 5.- Ejercicio resuelto mediante QM.

Fig. 6.- Ejercicio resuelto mediante QM.

6. Maximizar Z = 4X1 -2X2 +2X3 sujeto a: 2X1 + 2X2 + 2X3 + 2X4 ≤ 16 4X2 - 2X3 ≤ 8 4X1 - 2X2 - X4 ≤ 4 El ejercicio no se puede resolver mediante el m´etodo Dual o el de Dos Fases, por lo que se prosigue a resolverlo por el m´etodo Simplex.

  2X1 + 2X2 + 2X3 + 2X4 + S1 = 16 4X2 − 2X3 + S2 = 8   4X1 − 2X2 − X4 + S3 = 4

Page 9 of 18

Cj 0 0 0

Xj S1 S2 S3 Zj Zj − Cj

bm 16 8 4 0

Cj 0 0 4

-2 X2 2 4 -2 0 2

2 X3 2 -2 0 0 -2

0 X4 2 0 -1 0 0

0 S1 1 0 0 0 0

0 S2 0 1 0 0 0

0 S3 0 0 1 0 0

0 S2 0 1 0 0 0

0 S3 -1/2 0 1/4 1 1

Xj S1 S2 X1 Zj Zj − Cj

bm 14 8 1 4

4 X1 0 0 1 4 0

-2 X2 3 4 -1/2 -2 0

2 X3 2 -2 0 0 -2

0 X4 5/2 0 -1/4 -1 -1

0 S1 1 0 0 0 0

Xj X3 S2 X1 Zj Zj − Cj

bm 7 22 1 18

4 X1 0 0 1 4 0

-2 X2 3/2 7 -1/2 1 3

2 X3 1 0 0 2 0

0 X4 5/4 5/2 -1/4 3/2 3/2

0 S1 1/2 1 0 1 1

Cj 2 0 4

4 X1 2 0 4 0 -4

0 S2 0 1 0 0 0

0 S3 -1/4 -1/2 1/4 1/2 1/2

Respuestas:

              

X1 = 1 X2 = 0 X3 = 7 X4 = 0 M ax(Z) = 18

b) Soluci´ on en QM:

Page 10 of 18

Fig. 7.- Ejercicio resuelto mediante QM.

7. Minimizar Z = 3X1 -9X2 -5X3 + 4X4 sujeto a: X1 + 4X2 + 5X3 + 8X4 ≤ 8 X1 + 2X2 + 6X3 + 4X4 ≤ 4 El ejercicio no se puede resolver mediante el m´etodo Dual o el de Dos Fases, por lo que se prosigue a resolverlo por el m´etodo Simplex.

(

X1 + 4X2 + 5X3 + 8X4 + S1 = 8 X1 + 2X2 + 6X3 + 4X4 + S2 = 4

Cj 0 0

Xj S1 S2 Zj Zj − Cj

Cj -9 0

Xj X2 S2 Zj Zj − Cj

bm 2 0 -18

3 X1 1 1 0 -3

-9 X2 4 2 0 9

-5 X3 5 6 0 5

3 X1 1/4 1/2 -9/4 -21/4

-9 X2 1 0 -9 0

-5 X3 5/4 7/2 -45/4 -25/4

bm 8 4 0

4 X4 8 4 0 -4 4 X4 2 0 -18 -22

0 S1 1 0 0 0

0 S2 0 1 0 0

0 S1 1/4 -1/2 -9/4 -9/4

0 S2 0 1 0 0

Respuestas:

Page 11 of 18

       

X1 = 0 X2 = 2

X3 = 0    X4 = 0     M in(Z) = −18 b) Soluci´ on en QM:

Fig. 8.- Ejercicio resuelto mediante QM.

8. Minimizar Z = 2X1 + 9X2 + 6X3 + 8X4 sujeto a: X1 + X2 + X3 - X4 = 1 X1 + 2X2 - X3 + 2X4 = 0 a)M´etodo Dual: Maximizar Z = Y1 - Y2

 Y1 − Y2 + Y3 − Y4     Y − Y + 2Y − 2Y 1 2 3 4  Y − Y − Y + Y 1 2 3 4    −Y1 + Y2 + 2Y3 − 2Y4

≤2 ≤9 ≤6 ≤8

 Y1 − Y2 + Y3 − Y4 + S1     Y − Y + 2Y − 2Y + S 1 2 3 4 2  Y1 − Y2 − Y3 + Y4 + S3    −Y1 + Y2 + 2Y3 − 2Y4 + S4

=2 =9 =6 =8

Page 12 of 18

Cj 0 0 0 0

Xj S1 S2 S3 S4 Zj Zj − C j

bm 2 9 6 8 0

1 Y1 1 1 1 -1 0 -1

-1 Y2 -1 -1 -1 1 0 1

0 Y3 1 2 -1 2 0 0

0 Y4 -1 -2 1 -2 0 0

0 S1 1 0 0 0 0 0

0 S2 0 1 0 0 0 0

0 S3 0 0 1 0 0 0

0 S4 0 0 0 1 0 0

Xj Y1 S2 S3 S4 Zj Zj − C j

bm 2 7 4 10 2

1 Y1 1 0 0 0 1 0

-1 Y2 -1 0 0 0 -1 0

0 Y3 1 1 -2 3 1 1

0 Y4 -1 -1 2 -3 -1 -1

0 S1 1 -1 -1 1 1 1

0 S2 0 1 0 0 0 0

0 S3 0 0 1 0 0 0

0 S4 0 0 0 1 0 0

0 S1 1/2 -3/2 -1/2 -1/2 1/2 1/2

0 S2 0 1 0 0 0 0

0 S3 1/2 1/2 1/2 3/2 1/2 1/2

Cj 1 0 0 0

Cj 1 0 0 0

Xj Y1 S2 S3 Y4 Zj Zj − Cj

bm 4 9 2 16 4

1 Y1 1 0 0 0 1 0

-1 Y2 -1 0 0 0 -1 0

0 Y3 0 0 -1 0 0 0

0 Y4 0 0 1 0 0 0

0 S4 0 0 0 1 0 0

Respuestas:

 1   X1 = |S1 | =   2     X = 0  2  1 X3 = |S3 | =   2     X4 = 0     M in(Z) = 4 b) Soluci´ on en QM:

Page 13 of 18

Fig. 9.- Ejercicio resuelto mediante QM.

9. Minimizar Z = 0.5X1 + 1.5X2 - 0.5X3 sujeto a: -0.5X1 - 0.5X2 + X3 ≤ 2.5 X1 - 0.5X2 + 0.5X3 ≤ 3 0.5X1 - 1.5X2 + 2.5X3 ≥ 10 a)M´etodo de Dos Fases: Minimizar Z = m3

  

−0,5X1 − 0,5X2 + X3 + S1 = 2,5

 

0,5X1 − 1,5X2 + 2,5X3 − S3 + m3 = 10

X1 − 0,5X2 + 0,5X3 + S2 = 3

Cj 0 0 1

Xj S1 S2 m3 Zj Zj − C j

bm 2.5 3 10 10

Cj 0 0 1

Xj X3 S2 m3 Zj Zj − C j

bm 2.5 1.75 3.75 3.75

0 X1 -0.5 1 0.5 0.5 0.5

0 X2 -0.5 -0.5 -1.5 -1.5 -1.5

0 X3 1 0.5 2.5 2.5 2.5

0 X1 -0.5 1.25 1.75 1.75 1.75

0 X2 -0.5 -0.25 -0.25 -0.25 -0.25

0 X3 1 0 0 0 0

0 S1 1 0 0 0 0 0 S1 1 -0.5 -2.5 -2.5 -2.5

0 S2 0 1 0 0 0 0 S2 0 1 0 0 0

0 S3 0 0 -1 -1 -1 0 S3 0 0 -1 -1 -1

1 m3 0 0 1 1 0 1 m3 0 0 1 1 0

Page 14 of 18

Cj Xj X3 X1 m3 Zj Zj − C j

0 0 1

0 X1 0 1 0 0 0

bm 3.2 1.4 1.3 1.3

Cj Xj X3 X1 X2 Zj Zj − C j

0 0 0

bm 11 4 13 0

0 X2 -0.6 -0.2 0.1 0.1 0.1

0 X3 1 0 0 0 0

0 S1 0.8 -0.4 -1.8 -1.8 -1.8

0 X2 0 0 1 0 0

0 X3 1 0 0 0 0

0 S1 -10 -4 -18 0 0

0 X1 0 1 0 0 0

0 S2 0.4 0.8 -1.4 -1.4 -1.4 0 S2 -8 -2 -14 0 0

0 S3 0 0 -1 -1 -1 0 S3 -6 -2 -10 0 0

1 m3 0 0 1 1 0 1 m3 6 2 10 0 -1

   X3 − 10S1 − 8S2 − 6S3 = 11 X1 − 4S1 − 2S2 − 2S3 = 4   X2 − 18S1 − 14S2 − 10S3 = 13 Cj 0 0 0

Xj X3 X1 X2 Zj Zj − C j

0.5 X1 0 1 0 0.5 0

bm 11 4 13 16

1.5 X2 0 0 1 1.5 0

-0.5 X3 1 0 0 -0.5 0

0 S1 -10 -4 -18 -24 -24

0 S2 -8 -2 -14 -18 -18

0 S3 -6 -2 -10 -13 -13

Respuestas:

        

X1 = 4 X2 = 13 X3 = 11 M in(Z) = 16

b) Soluci´ on en Excel:

Page 15 of 18

Fig. 10.- Ejercicio resuelto mediante Excel.

10. Maximizar Z = X1 + 2X2 - X3 + 4X4 sujeto a: X1 + 2X2 - 3X3 + X4 = 4 X1 + 2X2 + X3 + 2X4 = 4 a)M´etodo de Dos Fases: Minimizar Z = m1 + m2

( X1 + 2X2 − 3X3 + X4 + m1 = 4 X1 + 2X2 + X3 + 2X4 + m2 = 4 Cj 1 1

Xj m1 m2 Zj Zj − C j

bm 4 4 8

Cj 0 1

0 X2 2 2 4 4

0 X3 -3 1 -2 -2

Xj X2 m2 Zj Zj − C j

bm 2 0 0

0 X1 1/2 0 0 0

0 X2 1 0 0 0

0 X3 -3/2 4 4 4

Xj X2 X3 Zj Zj − Cj

bm 2 0 0

0 X1 1/2 0 0 0

0 X2 1 0 0 0

0 X3 0 1 0 0

Cj 0 0

0 X1 1 1 2 2

0 X4 1 2 3 3 0 X4 1/2 1 1 1 0 X4 7/8 1/4 0 0

1 m1 1 0 1 0 1 m1 1/2 -1 -1 -2 1 m1 1/8 -1/4 0 -1

1 m2 0 -1 1 0 1 m2 0 1 1 0 1 m2 3/8 1/4 0 -1

Page 16 of 18

 1   X1 + X2 + 2   X3 + Cj 1 -1

Xj X1 X3 Zj Zj − Cj

bm 2 0 2

1 X1 1/2 0 1/2 -1/2

2 X2 1 0 1 -1

-1 X3 0 1 -1 0

Xj X1 X4 Zj Zj − C j

bm 2 0 2

1 X1 1/2 0 1/2 -1/2

2 X2 1 0 1 -1

-1 X3 -7/2 4 25/2 27/2

1 X1 1/2 0 1 0

2 X2 1 0 2 0

-1 X3 -7/2 4 9 10

Cj 1 4

Cj 2 4

7 X4 = 2 8 1 X4 = 0 4

Xj X2 X4 Zj Zj − C j

bm 2 0 4

4 X4 7/8 1/4 5/8 -27/8 4 X4 0 1 4 0 4 X4 0 1 4 0

Respuestas:

       

X1 = 0 X2 = 2

X3 = 0    X4 = 0     M ax(Z) = 4 b) Soluci´ on en QM:

Page 17 of 18

Fig. 11.- Ejercicio resuelto mediante QM.

Page 18 of 18