• Author / Uploaded
• Josue

Citation preview

Practica Nª1 MODELOS DE PROGRAMACIÓN LINEAL 1. La Company está tratando de encontrar la mejor manera de utilizar el exceso de capacidad en particular, 20000 horas –hombre. La compañía está considerando dos tipos de llantas: normal y radial. Cada llanta radial ocupa 2,5 horas –hombre y tiene una contribución de $20. Una llanta normal requiere 2 horas – hombre y contribuye con $16. El departamento de comercialización estima que pueden venderse hasta 6000 llantas radiales y 8000 llantas normales. a) b) c) d) e) f)

Formúlese este como un problema de PL. Resolver por el método gráfico. Marque con un círculo los vértices de la gráfica. Para cada solución EFV, identifique sus soluciones FEV adyacentes. ¿Cuántas llantas de cada tipo deben producirse? Cuál es la contribución total.

SOLUCIÓN

a) Datos para la formulación del modelo de PL La company, exceso de capacidad 2000 horas/ hombre Dos tipos de llantas: Normal x1 = 2 horas/ hombre, $16 Radial x2 =2,5 horas/ hombre, y tiene una contribución $20 El departamento vende 6000 llantas radiales El departamento vende 8000 llantas normales Max Z=16x1 + 20x1 2x1 + 2,5x2 ≤ 2000 x1 ≤ 8000 x2 ≤ 6000 (x1, x2) ≥0

b)

x2 ecua ci ón 2

8 7 (0, 600)

(2500, 6000)

6 A

ecua ci ón 3

B

5

4 3 2

REGIÓN FACTIBLE

(8000, 1600) C

1 (0, 0)

D

(8000, 0)

0

x1 1

2

3

4

5

6

7

8

9

10 ecua ci ón 1

c) d) SOLUCION FEV (0, 0) (0, 6000)

SOLUCION FEV ADYACENTE (0, 6000) y (8000,0) (2500, 6000) y (0,0)

e) Normal x1 = 2500 Radial x2 =6000 f) Max Z=16x1 + 20x1 =16(2500) + 20(6000) =40000) + 120000 =160000 2. La Cincinnati Chemical Company debe producir 10000 libras de una mezcla especial para un cliente. La mezcla se compone de los ingredientes X1, X2, y X3. X1, cuesta 8 dólares la libra, X2, 10 dólares la libra, y X3 11 dólares la libra. No pueden usarse

más de 3000 libras de X1 y por lo menos deberán usarse 1500 libras de X2. Además, se requieren por lo menos 2000 libras de X3. a) Calcúlese el número de libras de cada ingrediente que habrá que emplear, a fin de reducir al mínimo el costo total de las 10000 libras. b) Calcúlese el costo total más bajo posible. c) ¿Hay libras sobrantes en el problema? SOLUCIÓN a)

Datos Cantidad producida 10000 libras x1 = número de libras de ingrediente 1 x2 = número de libras de ingrediente 2 x3 = número de libras de ingrediente 3 x1 , cuesta 8 dólares x2 , cuesta 10 dólares x3 , cuesta 11 dólares No pueden usarse más de 3000 libras de x1 Por lo menos deberán usarse 1500 libras de x2 Por lo menos deberán usarse 2000 libras de x3 Función objetivo: Minimizar costo de la dieta Z= 8x1 +10x2 +11x3 Restricciones: x1 +x2 +x3 =10000 Requerimientos para x1, x2 y x3 x1 ≤ 3000 x2 ≥ 1500 x3 ≥ 200 Min Z= 8x1 +10x2 +11x3 s.a. x1 +x2 +x3 =10000 x1 ≤ 3000 x2 ≥ 1500 x3 ≥ 200 (x1, x2 ,x3 ) ≥ 0

Estandarizando el problema PL Min Z= 8x1 +10x2 +11x3 -Ma1 +0x4 +0x5 +0x6 x1 +x2 +x3 +xa1 +0 +0 +0 x1 +0 +0 +0 +x4 +0 +0 x2 +0 +0 +0 -x5 +0 x3 +0 +0 +0 -x6

Cj

→

CB

Base

b

-M 0

a1 X4

10000 3000

-M -M

a2 a3

1500 2000

-8

+Ma2 +0 +0 +ax1 +0

+Ma3 +0 = 10000 +0 = 3000 +0 = 1500 +ax2 = 200

-10

-11

-Ma1

0

0

0

x2

x3

q1

x4

x5

x6

q2

q3

1 1

1 0

1 0

1 0

0 1

0 0

0 0

0 0

0 0

1 0 -2M 10 0 0 1

0 1 2M 11 1 0 0

0 0

0 0

-1 0

0 -1

1 0

0 1

0

0

M

M

0

0

1 0 0

0 1 0

1 0 -1

0 0 0

-1 0 1

0 0 0

x1

-Ma2 -Ma3

M 0 -10

a1 X4 X2

8500 3000 1500

0 0 -M 8 1 1 0

-M

a3 10500M 15000

2000

0

0

1

0

0

0

-1

0

1

-M 8

0

-2M 11

0

0

M 10

M

-10

0

a1 X4 a2 X3 Z= -6500 -37000 a1

6500 3000 1500 2000

0 0 1 0

0 0 0 1

1 0 0 0

0 1 0 0

0

0

0

-10

-11

0

0

1

-1

1 0 0 -1 -M 11 1

-1 0 0 1

0

1 0 -1 0 -M 10 1

-1 0 1 0

3500

1 1 0 0 -M 8 0

-1

-1

X1 X2 X3 Z=-3500M -37000 0 X4 8 X1 -10 X2

3000 1500 2000

1 0 0

0 1 0

0 0 1

0 0 0

0

0

-10

-11

3500 3000 5000

0 1 0

0 0 1

0 0 0

1 0 0

0 0 -1 -M 11 1 0 0

0 0 1

0

0 -1 0 -M 10 1 0 0

0 1 0

0

1 0 0 -M 8 -1 1 0

-1 0 0

-1 0 0

-11

2000

0

0

1

0

0

-1

0

1

0

0

0

0 -M -10

18

0

1

0

-1

Z= - 13500M

Z= M 0 -10 -11

.-M -8 -10 -11

X3 Z = - 96000

a) El número de libras de cada ingrediente X1=3000 libras X2=5000 libras X3=2000 libras b) El costo total más bajo dólares 96000 c) Libra sobrantes en el problema es de 3500 libras, en la última tabla x4.

3. Supongamos que se cuenta con dos alimentos: pan y queso; cada uno de ellos contiene calorías y proteínas en diversas proporciones. Un kilogramo de pan contiene 2000 calorías y 50 gramos de proteínas, y un kilogramo de queso contiene 4000 calorías y 200 gramos de proteínas. Supongamos que un dieta normal requiere cuando menos 6000 calorías y 200 gramos de proteínas diariamente. Por tanto, si el kilogramo de pan cuesta $6 y $21 el queso, ¿Qué cantidad de pan y queso debemos comprar para satisfacer los requisitos de la dieta normal, gastando la menor cantidad de dinero? a) Use el método gráfico para resolver este problema. b) Marque con un círculo los vértices de la gráfica. c) Para cada solución FEV, identifique el par de ecuaciones de fronteras de restricción que satisfaga. d) Para cada solución EFV, identifique sus soluciones FEV adyacentes. e) Calcule Z para cada solución FEV. Use esta información para identificar la solución óptima. SOLUCIÓN

a). Formulación del problema de PL Datos 2 alimentos Pan = x1 número de kilogramos Queso = x2 número de kilogramos Un kilogramo de pan contiene 2000 calorías y 50 gramos de proteínas Un kilogramo de queso contiene 4000 calorías y 200 gramos de proteínas Dieta normal requiere cuando menos 6000 calorías 200 gramos de proteínas diariamente Pan cuesta $6 Queso cuesta $21 Min Z= 6x1 +21x2 s.a. 2000x1 +4000x2 ≥ 6000 50x1 +200x2 ≥ 200 (x1 ,x2) ≥ 0 Solución Gráfica Min Z= 6x1 +21x2 2000x1 +4000x2 =6000 50x1 +200x2 = 200 Ecuación 1 X1=3 X2=1,5 Ecuación 2 X1=4 X2=1 Al resolver el sistema de ecuaciones 1 y 2 Se tiene: X1=2 X2=1/2

x2 5 4 3 2 2 A

REGIÓN FACTIBLE

1

B

1 C

1

2

3

4

5

x1

b) vértice de la grafica Punto A (O, 1,5) Punto B (2, 1/2) Punto C (4,0) c) frontera de restricción que satisfaga Punto B (2, 1/2) d) e) Min Z= 6x1+21x2 Pan = x1 = 2 número de kilogramos Queso = x2 =1/2 número de kilogramos =6(2)+21(1/2) =22,5 Bolivianos 4. Considere el siguiente problema. Max Z = 3 x1 + 5 x2 s.a. x1 ≤4 2 x2 ≤ 12 3 x1 + 2 x2 ≤ 18 (x1, x2 ) ≥ 0 a) Use el método gráfico para resolver este problema. b) Marque con un círculo los vértices de la gráfica. c) Para cada solución FEV, identifique el par de ecuaciones de fronteras de restricción que satisfaga. d) Para cada solución EFV, identifique sus soluciones FEV adyacentes. e) Calcule Z para cada solución FEV. Use esta información para identificar la solución óptima. SOLUCIÓN

a)

Max Z = 3 x1 + 5x2 + 0x3+ 0x4 + 0x5 x1 +x3 +0 +0 = 4 2 x2 +0 +x4 +0 = 12 3x1 + 2x2 +0 +0 +x5 = 18 SIB

x3 =4 x4 =12 x5 =18

CB 0 0 0 0 5 0 0 5 3

Cj Base X3 X4 X5 Z=0 X3 X2 X5 Z = 30 X3 X2 X1 Z = 36

→ b 4 12 18 300 6 6 -2 6 2

3 x1 1 450 3 -3 1 0 3 -3 0 9 -15 0

5 x2 0 2 2 -5 0 1 0 0 0 6 -9 0

0 x3 1 0 0 0 1 0 0 1 0 0 0

0 x4 0 1 0 0 0 1/2 -1 5/2 1/3 ½ -1/3 3/2

0 x5 0 0 1 0 0 0 1 0 -1/3 0 1/3 1

6 9 4 2

Max Z = 36 x1 = 2 x2 = 6 5. Cierto modelo de programación lineal con dos actividades tiene la región factible que se muestra. El objetivo es maximizar la ganancia total de las dos actividades. La ganancia unitaria de la actividad 1 es $1000 y de la actividad 2 es $2000.

a) Calcule la ganancia total para cada solución FEV. Use esta información para encontrar la solución óptima. SOLUCIÓN

La primera restricción: Para ello tiene dos puntos P1 (0,20/3); P2 (5,5) P1 (x1,x2); P2 (x1,x2)

(x-x1 )

(x - 0) ( )

La ecuación de la recta 1 La segunda restricción: Para ello tiene dos puntos P1 (5, 5); P2 (6, 4) P1 (x1,x2); P2 (x1,x2)

(

)

(

) La ecuación de la recta 2

La tercera restricción: Para ello tiene dos puntos P1 (6, 4); P2 (8, 0) P1 (x1,x2); P2 (x1,x2)

(

)

(

) La ecuación de la recta 3

Calcular valor de Z Actividad 1, beneficio unitario 1000 Actividad 2 beneficio unitario 2000 Max Z=1000x1+2000x2 s.a.

(

)

Max Z=1000x1+2000x2 Verificar para cada vértice Punto (0, 20/3) Max Z = 1000(0)+2000(20/3) =13333,333 Max Z=1000x1+2000x2 Punto (5,5) =1000(5)+2000(5) =15000 Max Z=1000x1+2000x2 Punto (6, 4) =1000(6)+2000(4) =14000 Max Z=1000x1+2000x2 Punto (8,0) =1000(8)+2000(0) =8000 Mediante grafica optimizamos en el punto (5,5) Max Z=1000x1+2000x2 Punto (5,5) =1000(5)+2000(5) =15000 6. Considerar el siguiente problema: Max Z = 3 x1 + x2 s.a. 7 x1 + 2 x2 ≤ 30 3 x1 + 2 x2 ≥ 10 (x1, x2 ) ≥ 0 a) Resolver este problema por el Método Simplex

b) Encontrar en la tabla óptima la solución del primal x1 ,x2 ,Z y del Dual y1 ,y2 ,Y. SOLUCIÓN Cj

→

3

1

0

0

CB

Base

b

x1

x2

x3

x4

0 0

X3 X4

30 -10

7 -3

2 -2

1 0

0 1

3 0

Z=0 X1 X4

30/7 -20/7

-3 1 0

-1 2/7 -8/7

0 1/7 3/7

0 0 1

1 0

Z = 90/7 X2 X4

15 100/7

0 7/2 4

-1/7 1 O

3/7 ½ 1

0 0 1

7/2

0

1/2

0

Z = 15

Problema primal Max Z= 15 X1=0 X2=15 Problema Dual MinY=15 Y1=1/2 Y2=0 7. Resolver el siguiente problema de PL aplicando el dual por el método simplex. Max Z = 3 x1 + 2x2 s.a. x1 + x2 ≥ 1 -5 x1 - x2 ≥ 0 x1 - 5 x2 ≤ 0 -x1 + x2 ≤ 1 x1 + x2 ≤ 6 x1 ≤ 3 (x1, x2 ) ≥ 0 a) Resolver este problema por el Método Simplex b) Encontrar en la tabla óptima la solución del primal Z y del Dual Y. SOLUCIÓN

Max Z = 3 x1 + 2x2 s.a. x1 + x2 ≥ 1 -5 x1 - x2 ≥ 0 x1 - 5 x2 ≤ 0 -x1 + x2 ≤ 1 x1 + x2 ≤ 6 x1 ≤ 3 (x1, x2 ) ≥ 0 Max Z = 3 x1 + 2x2 s.a. x1 + x2 ≥ 1

-x1 + x2 ≤ 1 x1 + x2 ≤ 6 x1 ≤ 3 (x1, x2 ) ≥ 0 Problema Prima Max Z = 3 x1 + 2x2 s.a. - x1 - x2 ≤ -1 -x1 + x2 ≤ 1 x1 + x2 ≤ 6 x1 ≤ 3 Problema Dual Min Y = 3 y1 + y2+ y2+ y2 s.a. -y1 - y2 +y3 +y4 ≥ 3 -y1 + y2 +y3 ≥ 2 Problema Dual Estándar Min Y = 3 y1 + y2+ y2+ y2 s.a. -y1 - y2 +y3 +y4 -y5 +0 +ya1+0 = 3 y1 + y2 +y3 +0 +0 -y6 +0 +ya2 = 2

CB -M -M

-M -6

-3 -6

Cj Base ya1 ya2 Z =-5M ya1 y3 Z = -M -12 y4 y3 Z = -15

→ b 3 2

1 2

1 2

1 y1 -1 1 2M -1 0 -1 5 0 -1 5

-1 y2 -1 1 1 -2 1 2M -5 -2 1 1

-6 y3 1 1 -2M 6 0 1 0 0 1 0

-3 y4 1 0 -M 3 1 0 -M 3 1 0 0

0 y5 -1 0 M -1 0 M -1 0 3

0 y6 0 -1 M 1 -1 -M 6 1 -1 3

-M ya1 1 0

-M ya2 0 1

0 1 0

0 -1 1 2M -6 -1 1 -3

0 1 0 -3

Problema Dual p Min Y= -y1+y2+6y3+3y4 = 0+0+6(2)+3(1) =15 Y3=2 Y4=1 Problema Primal Max Z=3x1+2x2 =3(3)x+2(3) =9+6 =15 X1=3 x2=3 8. Con el método simplex resuelva el siguiente problema. Max Z = 3 x1 + 8x2 s.a.

3x1 +4x2 ≤ 20 x1 + 3x2 ≥ 6 (x1 ,x2) ≥ 0 Solución. Forma estándar: Max Z = 3 x1 + 8x2 +0x3+ 0x4 – Mxa1 3x1 +4x2 +4x2 = 20 x1 + 3x2 -x4 +ax2 = 6 Operación auxiliar para la fila 1

(-4/3)

20

3

4

1

0

0

(6

1

3

0

-1

1)

12

5/3

0

1

-

4/3

4/3

Operación auxiliar para la fila 2

(1/4)

2

1/3

1

0

-1/3

1/3

(12

5/3

0

1

4/3

-4/3)

5

3/4

1

1/4

0

0

Cj

→

3

8

0

0

-M

CB

Base

b

x1

x2

x3

x4

xa1

0

X3

20

3

4

1

0

0

-M

xa1

6

-1

1

0

12

3 -8 -3M 0

0

Z = -6M X3

1 -3 -M 5/3

0 1

M 4/3

0 -4/3

8

X2

2

1/3

1

0

-1/3 -8/3

0

Z = 16 X4

9

-1/3 5/4

0 0

0 3/4

1

1/3 8/3 M -1

8

X2

5

¾

1

1/4

0

0

3

0

2

0

M

Z = 40 X1=0 X2=5 Max Z = 3 x1 + 8x2 = 3 (0) + 8(5) = 40