Tarea 2 - Ejercicios resueltos de programación entera. PDF

Preview

Summary

Ejercicios resueltos de programación entera....

Description

John Mora Carrillo

Programación Entera - Tarea 02 Jenny Gutierrez López Término II 2018 – 2019 Ejercicio 1 Resuelva los siguientes problemas de optimización discreta utilizando el método de enumeración exhaustiva. (Nota: Recuerde que en problemas enteros mixtos tendrá que ayudarse del método simplex para la resolución, para ello puede hacer uso de alguna herramienta informática de su elección. O si prefiere puede realizar el procedimiento manual de simplex) a) min 2 40 = 21 + 2 + 43 + 1 04 Sujeto a 1 + 2 + �3 ≤ 2 31 79+ 72 + 1 93 + 4 ≥ 20 1, 2, �3 = 0 ó 1 �4 ≥ 0 Para llevar a cabo el método de enumeración exhaustiva se debe empezar otorgando valores a las variables binarias y cubrir todas las combinaciones posibles, al tener 3 variables binarias el número de combinaciones que se deben hacer está dado por 23 =8 . Luego se procede a resolver el PL para las variables sobrantes. Para este ejercicio se ha hecho uso del complemento Solver de Excel obteniendo lo siguientes resultados. El valor óptimo para el PL es Z=5. X 1=0, X 2=1, X 3=1, X 4=0 .

b) max 0245= 301 + 122 + 243 + 554 Sujeto a 3 0005 01 + 202 + 403 + 354 ≤ 60 2 + 3 + �4 ≥ 2 �1 ≥ 0 2, 3, �4 = 0 ó 1 Se procede de la misma forma que el literal anterior, para este problema en particular se han obtenido sub problemas no factibles. El valor óptimo para este ejercicio es Z =72 con X 1=0,17, X 2=1, X 3=0, X 4=1 .

John Mora Carrillo

Ejercicio 2 Suponga que un problema entero de minimización es resuelto utilizando el algoritmo de ramificación y acotamiento sobre las variables de decisión �1, �2, �3 = 0 ó 1, �4 ≥ 0. Muestre como el proceso continuaría a partir del nodo con �2 = 1 y todas las demás variables libres si el relajado del PL que le corresponde a ese nodo tuviera los siguientes resultados. Asuma que la solución incumbent es 100. a) (1, 2, 3, 4) = (0.9, 1, 0, 6) � � = 97 Al realizar el sondeo a fondo se verifica que � ≤ � * → 97 ≤ 100 pero no todas las variables binarias tienen valores 0 o 1, no puede ser considerada una nueva solución incumbent. b) ( 1, 2, 3, 4) = (0.2, 1, 0.77, 4.5) � � = 102 No se cumple la desigualdad que � ≤ � * variables binarias tienen valores 0 o 1.

→

102 ≤

100, además no todas las

c) ( 1, 2, 3, 4) = (1, 1, 0, 4.2) � � = 75 Se verifica que � ≤ � * → 75 ≤ 100 y todas las variables binarias tienen valores 0 o 1. Se ha encontrado una nueva solución incumbent � *=75 d) �� �������� ��� �� �� �� �������� Debido a que el PL relajado no tiene solución factible el sub problema queda descartado. e) ( 1, 2, 3, 4) = (1, 1, 0.6, 0) = 100 Se verifica que se cumple la desigualdad � ≤ � * → 100 ≤ 100, pero no todas las variables binarias tienen valores 0 o 1. No puede ser considerada como una nueva solución incumbent. f) ( 1, 2, 3, 4) = (0.4, 1, 0.1, 5.9) = 97 Se verifica que se cumple la desigualdad � ≤ � * → 97 ≤ 100, pero no todas las variables binarias tienen valores 0 o 1. No puede ser considerada como una nueva solución incumbent. Ejercicio 3 Considere el siguiente problema de programación entera mixta sobre �1 = 0, y �2, �3, �4 = 0 ó 1.

John Mora Carrillo

a)

Resuelva el problema utilizando el algoritmo de ramificación y acotamiento, para ello utilice los resultados que se presentan en la tabla y presente el árbol de soluciones. Durante el desarrollo del algoritmo considere: si más de un nodo está activo continúe resolviendo en profundidad, es decir continúe en la misma rama; de existir empates seleccione la rama que tenga el valor óptimo más cercano al óptimo del relajado del PL anterior. Ramifique la variable del PL más reciente que está más cercana a un valor entero. Empiece sin ninguna solución incumbent y no redondee para crear solución incumbent inicial.

Al inicio todas las variables son libres, PL relajado

La solución óptima para el problema es la del subproblema PL2, con Z =230 .

( x 1 , x 2 , x 3 , x 4 ) =( 0,1,0,0.25)

John Mora Carrillo

b) Explique por qué la lógica del algoritmo de ramificación y acotamiento asegura que la solución final es óptima. El algoritmo de ramificación y acotamiento consiste en dividir el problema en subproblemas donde en cada nodo se va fijando una variable de manera que se arman combinaciones de soluciones para las variables de decisión hasta encontrar una solución óptima. c) La tabla usada para el literal a) se la usa para facilitar la aplicación del algoritmo, sin embargo, si no se la diera, la aplicación del algoritmo de ramificación y acotamiento requeriría que se resuelvan varios problemas relajados. ¿Cuántos de ellos se habrían necesitado resolver para este ejercicio? Se deberían resolver 2k problemas, donde k es la cantidad de variables binarias. Para este problema se deberían resolver 23=8 PL relajados más el PL inicial. Total=9 PL relajados. Ejercicio 4 min � = 16�1 + 14�2 + 15�3 Sujeto a �1 + �2 ≥ 1 �2 + �3 ≥ 1 �1 + �3 ≥ 1 �1, �2, �3 = 0 ó 1 El modelo presentado tiene la siguiente solución óptima para su modelo relajado

1 2 2

1 1 ( x 1 , x 2 , x 3 )=( , , 2 )

. Determine para cada una de las siguientes desigualdades si podrían

considerarse desigualdades válidas, y de ser así, indique si estas harían más robusto el relajado del PL original al agregarle dicha restricción. 10 x 1+10 x 2+ 10 x 3 ≥ 25 a)

1 1 1 10( )+10( )+10( )≥30 2 2 2 15 ≥25 Robustece el modelo, pero no es válida, obliga a las variables tomar el valor de 1, por lo tanto, provoca perder soluciones.

x 1+ x 2 + x 3 ≥ 1 1 1 1≥1 + + 2 2 2

b)

1.5 ≥ 1 No robustece el modelo. c)

x 1+ x 2 + x 3 ≥ 2 1 1 1 + + ≥2 2 2 2 1.5 ≥ 2 Si es válida y robustece el modelo

d)

14 x 1+ 20 x 2 +16 x 3 ≥ 30

14

( 12 ) +20 ( 12 )+16( 12 ) ≥30

John Mora Carrillo

25 ≥30 Si es válida y robustece el modelo Ejercicio 5 El siguiente árbol presenta la solución de un problema binario de maximización sobre �1, 2, 3 = 0 ó 1 utilizando el algoritmo de ramificación y corte. Las soluciones para cada subproblema se presentan junto al nodo de la siguiente manera: (�1, 2, 3) .

Brevemente explique el proceso aplicado a través del algoritmo de ramificación y corte, incluya cómo y por qué se ramificaron los nodos y qué criterios se fueron aplicando para descartar o considerar cada solución. Indique también cuando se encontraron soluciones incumbent y qué solución se seleccionó como óptima. Asuma que todas las desigualdades agregadas son válidas para el problema binario original. Nodo 0: Se procede a resolver el PL relajado obteniéndose como solución ( x 1 , x 2 , x 3 ) =( 0.3,0 .5,0 ) con Z =95 . Como se obtuvieron valores no enteros (0 o 1) se añade una restricción para hacer el PL más robusto y eliminar la solución factible del PL relajado. A continuación, se procede a resolver el nuevo PL. Nodo 1: Se obtuvo como solución al PL ( x 1 , x 2 , x 3 ) =(0.375,0 .5,0) con Z =91 . Se ramifica el PL tomando la variable x 1 y se procede a resolver el nuevo PL para cada rama. Nodo 2: Se obtuvo como solución de la rama x 1=1 , ( x 1 , x 2 , x 3 ) =( 1,0.2,0 .9) con Z =84 . Se añade una restricción para hacer el PL mas robusto para eliminar la solución factible del nuevo PL relajado. Nodo 3: El nuevo PL relajado no tiene solución factible. Nodo 4: Se obtuvo como solución de la rama x 1=0 , ( x 1 , x 2 , x 3 ) =( 0,1,0.6 ) con Z =78 . Se ramifica usando la variable x 3 y se procede a resolver el nuevo PL para cada rama. Nodo 5: Se obtuvo como solución de la rama x 3=1 , ( x 1 , x 2 , x 3 )=( 1,1,1) con Z =75 . Se añade una restricción para hacer el PL más robusto para eliminar la solución factible del nuevo PL relajado. Después del sondeo a fondo se ha encontrado la primera solución incumbent. * Z =75 .

John Mora Carrillo

Nodo 6: Para la rama x 3=0 el PL no tiene solución factible. Conclusión: La solución optima para el problema binario de maximización es la solución incumbent encontrada en el subproblema PL del nodo 5....