• Author / Uploaded
• Héctor F Bonilla

Citation preview

Examen Prueba 2 1. Describa la estructura del problema artificial que se utiliza en la Fase I del m´etodo s´ımplex. Demuestra que el valor objetivo o´ptimo del problema artificial es positivo si y s´olo si el problema original es infactible. 2. Si durante la utilizaci´on del algoritmo s´ımplex dual se obtiene una soluci´on que verifica la ¯ = B−1 b = 0, entonces ... condici´on b (a) nos hemos equivocado en los c´alculos. (b) (Correcta) hemos llegado a la soluci´on o´ptima del problema primal. (c) la soluci´on es primal factible, aunque puede no ser dual factible. (d) ninguna de las otras opciones. 3. Dadas las soluciones o´ptimas de los problemas primal y dual, una consecuencia del teorema de holguras complementarias es que ... (a) si una variable de holgura del problema primal es distinta de cero, entonces la restricci´on primal correspondiente es redundante. (b) (Correcta) si una variable de holgura del problema primal es distinta de cero, entonces la variable dual asociada tiene valor cero. (c) si una variable de holgura del problema primal es distinta de cero, entonces no se puede decir nada sobre la variable dual asociada. (d) si una variable de holgura del problema primal es distinta de cero, entonces existen variables de holgura duales con valor cero. 4. Indique cu´al es el dual del siguiente problema lineal: M ax s.a.

x1 + 3x2 + 2x3 x1 − x2 + 2x3 3x1 + 2x2 − x3 x1 , x2 x3

59 =3 =0 50

(a) min{9u1 + 3u2 s.a. u1 + 3u2 5 1, −u1 + 2u2 5 3, 2u1 − u2 = 2, u1 = 0, u2 5 0}. (b) min{9u1 + 3u2 s.a. u1 + 3u2 5 1, −u1 + 2u2 5 3, 2u1 − u2 = 2, u1 5 0, u2 = 0}. (c) min{9u1 + 3u2 s.a. u1 + 3u2 = 1, −u1 + 2u2 = 3, 2u1 − u2 5 2, u1 5 0, u2 = 0}. (d) (Correcta) min{9u1 + 3u2 s.a. u1 + 3u2 = 1, −u1 + 2u2 = 3, 2u1 − u2 5 2, u1 = 0, u2 5 0}. 5. Al minimizar la funci´on x1 − x2 + 2x3 sobre una regi´on poli´edrica se ha obtenido la siguiente tabla o´ptima: x1 x2 x3 x4 x5 LD x2 −2 1 0 −2 3 1 x3 −1 0 1 −2 1 2 −1 0 0 −2 −1 3 Entonces, el rango de variaci´on del coeficiente de costo de x2 que mantiene la optimalidad de esta tabla es ... (a) c2 = −2/3.

(b) (Correcta) −3/2 5 c2 5 −2/3. (c) −2/3 5 c2 5 3/2. (d) c2 5 −3/2. 6. Al aplicar la Fase I del m´etodo s´ımplex a tabla: x1 x2 x3 0 2 x1 1 −3 x5 0 −1

un problema lineal (P) se ha obtenido la siguiente x3 x4 x5 LD 1 3 0 2 0 4 0 3 0 0 1 0

donde x5 es la u ´nica variable artificial. Entonces ... (a) (P) es factible y su tercera restricci´on es redundante. (b) (P) es infactible. (c) (P) es factible y al pasar a la Fase II la base estar´a formada por {x 3 , x1 , x4 }. (d) (Correcta) (P) es factible y al pasar a la Fase II la base estar´a formada por {x 3 , x1 , x2 }. 7. Al maximizar la funci´on 2x1 + 2x2 + x3 sobre una regi´on poli´edrica se ha obtenido la siguiente tabla o´ptima, en la que las variables x4 y x5 son de holgura: x1 x3

x1 x2 x3 x4 x5 LD 1 2 0 2 −1 2 0 −1 1 −2 −1 5 0 1 0 2 3 9

Entonces, si se desea obtener la m´axima mejora posible en el valor objetivo o´ptimo, convendr´ıa ... (a) (Correcta) Aumentar el t´ermino independiente de la primera restricci´on. (b) Aumentar el t´ermino independiente de la segunda restricci´on. (c) Disminuir el t´ermino independiente de la primera restricci´on. (d) Disminuir el t´ermino independiente de la segunda restricci´on. 8. La soluci´on o´ptima del problema lineal M ax s.a.

2x1 + 3x2 x1 − 2x2 x1 + x 2 2x1 + x2 x1 , x2

52 55 58 =0

es el punto x∗ = (0, 5). Entonces, si u∗ = (u∗1 , u∗2 , u∗3 ) denota la soluci´on o´ptima del problema dual, seg´ un el teorema de holgura complementaria se verificar´a necesariamente que ... (a) (Correcta) u∗1 = 0, u∗3 = 0. (b) u∗2 = 0, u∗3 = 0. (c) u∗2 = 0. (d) u∗1 6= 0, u∗2 6= 0, u∗3 6= 0.

Soluci´ on. La tabla del s´ımplex inicial ser´ıa: M ax h1 h2 h3

2 3 0 0 0 ¯ x1 x2 h1 h2 h3 b 1 −2 1 0 0 2 1 1 0 1 0 5 2 1 0 0 1 8 −2 −3 0 0 0 0

La tabla o´ptima es: M ax h3 h1 x2

2 3 0 0 0 ¯ x1 x2 h1 h2 h3 b 1 0 0 −1 1 3 3 0 1 2 0 12 1 1 0 1 0 5 1 0 0 3 0 15

Soluci´on o´ptima x∗ = (0, 5) con z ∗ = 15. 9. Dado el siguiente problema de programaci´on lineal: max s.a.

2x1 + x2 3x1 + 2x2 = 6 4x1 + 5x2 5 20 x1 , x2 = 0

(a) Obtener la soluci´on o´ptima del problema aplicando el m´etodo de las dos fases. (b) Escribir el problema dual asociado a este problema. (c) La tabla o´ptima asociada a este problema es: x1 x3

¯ x1 x2 x3 x4 b 1 5/4 0 1/4 5 0 7/4 1 3/4 9 0 3/2 0 1/2 10

A partir de esta tabla obtener la soluci´on o´ptima del problema dual. ¿Cu´al es el recurso m´as influyente en el valor objetivo o´ptimo? (d) Usando el an´alisis de sensibilidad, encontrar la nueva soluci´on o´ptima si c 2 se cambia a 4? (e) Usando el an´alisis de sensibilidad, ¿cu´ales son los posibles valores de b2 para los que esta tabla sigue siendo o´ptima? (f) Supongamos que se a˜ nade la restricci´on x1 + x2 5 4. Encontrar la soluci´on o´ptima usando el an´alisis de sensibilidad. (g) Sup´ongase que se propone una nueva variable x5 con c5 = 2 y vector en las restricciones at5 = (1, 1). Encontrar la nueva soluci´on o´ptima. Soluci´ on. Apartado (a) M´etodo de las dos fases: M in a1 h2

0 0 0 0 1 ¯ x1 x2 h1 h2 a1 b ∗ 3 2 −1 0 1 6 2 4 5 0 1 0 20 5 3 2 −1 0 0 6

M in

0 0 0 0 1 ¯ x1 x2 h1 h2 a1 b 1 2/3 −1/3 0 1/3 2 0 7/3 4/3 1 −4/3 12 0 0 0 0 −1 0

x1 h2 M ax

2 1 0 0 ¯ x1 x2 h1 h2 b 1 2/3 −1/3 0 2 −1 0 7/3 4/3∗ 1 12 9 0 1/3 −2/3 0 4

x1 h2

M ax x1 h1

2 1 0 0 ¯ x1 x2 h1 h2 b 1 5/4 0 1/4 5 0 7/4 1 3/4 9 0 3/2 0 1/2 10

La soluci´on o´ptima u ´nica es x∗ = (5, 0) con z ∗ = 10. Apartado (b) El dual asociado a este problema ser´ıa: M in s.a.

6u1 + 20u2 3u1 + 4u2 = 2 (x1 ) 2u1 + 5u2 = 1 (x2 ) u1 5 0, u2 = 0

Apartado (c) Al existir la soluci´on o´ptima del problema primal, sabemos que tambi´en existe la soluci´on o´ptima del problema dual (es finita). Sabemos que la soluci´on o´ptima dual asociada se determina por u∗ = c∗B B−1 , informaci´on que se puede obtener directamente de los zj −cj asociados a las variables de holgura (variables de exceso cambiados de signo): ∗ = 10 u∗ = (u∗1 , u∗2 ) = (0, 1/2), zD Apartado (d) Se trata del coeficiente de costo asociado a una variable no b´asica, por lo que lo u ´nico que se modifica es su z2 − c2 = −3/2, por tanto: M ax x1 h1

2 4 0 0 ¯ x1 x2 h1 h2 b ∗ 1 5/4 0 1/4 5 4 0 7/4 1 3/4 9 36/7 0 −3/2 0 1/2 10

M ax x2 h1

2 4 0 0 ¯ x1 x2 h1 h2 b 4/5 1 0 1/5 4 −7/5 0 1 2/5 2 6/5 0 0 4/5 16

La nueva soluci´on o´ptima es x∗ = (0, 4) con z ∗ = 16. µ ¶ 6 Apartado (e) Consideramos que el vector b original es . Por lo que la tabla del s´ımplex b2 ¯ = B−1 b, y debe tener todas sus componentes no negativas, es decir: o´ptima tendr´ıa b ¶µ ¶ µ 1 µ ¶ 6 0 1/4 b2 −1 4 ¯ = b=B b= =0 b2 −1 3/4 −6 + 34 b2 De donde:

b2 = 0 ⇔ b2 = 8 b2 = 8

Apartado (f ) La soluci´on x∗ = (5, 0) no verifica la restricci´on x1 +x2 5 4, por lo que tendremos introducir esta restricci´on en la tabla del s´ımplex o´ptima para obtener la nueva soluci´on o´ptima. Las variables no b´asicas son x2 y x4 , luego en primer lugar escribimos esta nueva restricci´on en funci´on de ellas. Para ello obtenemos la expresi´on de x1 (variable b´asica) en funci´on de las variables b´asicas de la tabla o´ptima: 1 5 1 5 x1 + x2 + x4 = 5 ⇔ x 1 = 5 − x2 − x4 4 4 4 4 Por lo que la restricci´on ser´ıa: 5 1 1 1 5 − x2 − x4 + x2 5 4 ⇔ − x2 − x4 5 −1 4 4 4 4 A˜ nadimos una nueva variable de holgura x5 para escribir la restricci´on como una ecuaci´on (formato est´andar): 1 1 − x2 − x4 + x5 = −1 4 4 Y la introducimos en la tabla o´ptima, para inmediatamente resolver con el algoritmo dual del s´ımplex: M ax x1 h1 x5

2 1 0 0 0 ¯ x1 x2 h1 h2 x5 b 1 5/4 0 1/4 0 5 0 7/4 1 3/4 0 9 0 −1/4 0 −1/4∗ 1 −1 0 3/2 0 1/2 0 10 −1 6 −1 2 −1

M ax x1 h1 h2

2 1 0 0 0 ¯ x1 x2 h1 h2 x5 b 1 1 0 0 1 4 0 1 1 0 3 6 0 1 0 1 −4 4 0 1 0 0 2 8

La nueva soluci´on o´ptima es x∗ = (4, 0) con valor objetivo o´ptimo z ∗ = 8. Apartado (g) A˜ nadir una nueva variable al problema supone a˜ nadir una nueva columna a la tabla o´ptima y5 = B−1 a5 : µ ¶µ ¶ µ ¶ 0 1/4 1 1/4 y5 = B−1 a5 = = −1 3/4 1 −1/4 El valor de z5 − c5 = −3/2 por lo que se ha perdido la optimalidad y tenemos que iterar con el algoritmo del s´ımplex: M ax x1 h1

2 1 0 0 2 ¯ x1 x2 h1 h2 x5 b ∗ 1 5/4 0 1/4 1/4 5 20 0 7/4 1 3/4 −1/4 9 −1 0 3/2 0 1/2 −3/2 10 M ax x5 h1

2 1 0 0 2 ¯ x1 x2 h1 h2 x5 b 4 5 0 1 1 20 1 3 1 1 0 14 6 9 0 2 0 40

La nueva soluci´on o´ptima ser´ıa x∗ = (0, 0, 14, 0, 20) con valor objetivo o´ptimo z ∗ = 40.

10. Un agricultor cultiva girasol y trigo en su granja de 45 Ha. Puede vender como m´aximo 140 kg de trigo y 120 kg de girasol. Cada Ha de trigo produce 5 kg de trigo, y cada Ha de girasol produce 4 kg de girasol. El trigo se vende a 30 euros/kg y el girasol a 50 euros/kg. La cosecha de una Ha lleva 6 horas y la de girasol 10. Se pueden conseguir hasta 350 horas de trabajo a 10 euros/hora. Formule el problema de programaci´on lineal para maximizar las ganancias y obtenga la soluci´on o´ptima con ayuda de Excel. Soluci´ on. Las datos en forma de tabla son:

Girasol Trigo

Venta m´axima (kg) 120 140

Producci´on/Ha (kg) 4 5

Precio venta (euros/kg) 50 30

Horas/Ha (horas) 10 6

Sea x1 =“n´ umero de Ha de granja dedicadas al cultivo de trigo”, x2 =“n´ umero de Ha de granja dedicadas al cultivo de girasol”. Tenemos que maximizar ganancias; siendo ganancias = ganancias en ventas-costes. Las ganancias por las ventas son: 150x1 + 200x2 y lo perdido por costes es: 60x1 + 100x2 . As´ı la funci´on objetivo es: z = 150x1 + 200x2 − (60x1 + 100x2 ) = 90x1 + 100x2 . La formulaci´on de programaci´on lineal es: M ax s.a.

90x1 + 100x2 x1 + x2 5x1 4x2 6x1 + 10x2 x1 , x2

5 45 5 140 5 120 5 350 =0

Aplicando el algoritmo del s´ımplex, la soluci´on obtenida es: z = 4250 con x 1 = 25, x2 = 20.