Investigacion opertaiva

Vista previa del material en texto

PROGRAMACIÓN LINEAL ENTERA
INVESTIGACIÓN OPERATIVA I
Objetivos
Conocer el problema del redondeo.
Aprender el algoritmo de ramificación y acotamiento.
Consideremos el siguiente problema de programación lineal.
Min X1 - 11X2
S.T.
	− X1 +10X2 ≤ 40
	10X1 +10X2 ≤ 205
END
X1, X2 ≥ 0 y enteras
Cuya solución en el software LINDO es:
Programación Entera. 
El Problema del Redondeo
LP OPTIMUM FOUND AT STEP 2
 OBJECTIVE FUNCTION VALUE
 1) -45.50000
 VARIABLE VALUE REDUCED COST
 X1 15.000000 0.000000
 X2 5.500000 0.000000
 ROW SLACK OR SURPLUS DUAL PRICES
 2) 0.000000 1.090909
 3) 0.000000 0.009091
 NO. ITERATIONS= 2
¿Porque no redondeamos y ya?
¿Porque no redondeamos y ya?
¿Porque no redondeamos…y listo?
Veamos, la región factible (conjunto solución) del caso anterior es:
Posibles redondeos:
X1 = 15 y X2 = 6: no verifica la primera restricción.
X1 = 15 y X2 = 5: es factible y Z = −40.
0
X1
X2
Solución Óptima
Solución Óptima
Solución por Redondeo
6
Algoritmo de Ramificación y 	Acotamiento
En la práctica, la mayoría de los problemas de programación entera se resuelven mediante el uso de la técnica de ramificar y acotar. 
Los métodos de ramificar y acotar encuentran la solución óptima para un problema de programación entera mediante la enumeración eficiente de los puntos en la región factible 
Le método de ramificar y acotar consiste en descomponer el problema original en una sucesión de sub problemas hasta identificar la solución óptima. 
Para darse cuenta de la validez de esta observación, consideremos el siguiente problema de programación entera: 
Ahora lo pasamos a lindo sin considerar la restricción entera.
Max 3X1 + 2X2 
ST 
	2X1 + X2 ≤ 6 
END
X1,X2≥0 y enteros
Y la solución en LINDO es:
LP OPTIMUM FOUND AT STEP 1
 OBJECTIVE FUNCTION VALUE
 1) 12.00000
 VARIABLE VALUE REDUCED COST
 X1 0.000000 1.000000
 X2 6.000000 0.000000
 ROW SLACK OR SURPLUS DUAL PRICES
 2) 0.000000 2.000000
 NO. ITERATIONS= 1
Esta solución da valores enteros a cada variable, la observación anterior implica que:
 
también es la solución óptima para el problema de programación entera (comprobar usando LINDO). 
Obsérvese que la región factible para la programación entera es un subconjunto de todos los puntos en la región factible de la relajación por programación lineal. 
X1=0, X2=6 con Z=12
Así, el valor óptimo de Z para la programación entera no puede ser mayor que el valor óptimo de Z para la relajación de programación lineal, es decir, 
Esto significa que el valor óptimo de Z para la programación entera (para el ejemplo previo) debe ser Z≤12 . 
Zoptimo(PL) ≥ Zoptimo (PLE) 
Pero el punto X1=0, X2=6 con Z=12 es factible para la programación entera y tiene Z=12. Por lo tanto, X1=0, X2=6 con Z=12 debe ser óptimo para la programación entera. 
En forma resumida, los pasos del algoritmo de Ramificar y Acotar, para un problema de maximización, son:
1.- Definimos Z como la cota inferior de la solución entera óptima del problema de programación lineal entera. Hacemos inicialmente Z=- e i=0 (subproblema i-ésimo). Para problemas de minimización, reemplace la cota inferior con una cota superior inicial z =-.
2.- Estudio y ramificación. Seleccione SPi (subproblema i-ésimo) como el próximo subproblema por investigarse. Resuelva el SPi y trate de estudiarlo utilizando las condiciones apropiadas.
Pasos
Si el SPi se ha estudiado (solución inferior, no factible o entera), actualice la cota inferior Z si se encuentra una mejor solución del programación lineal entera; si no es así, seleccione un nuevo subproblema 1 y repita el paso 2. 
Si todos los subproblemas se han investigado, deténgase; la solución óptima del problema de PLE está asociada con la última cota inferior Z, en caso de que ésta exista
Si no es así, si el SPi no está estudiado, siga con el paso 3 para efectuar la ramificación del SPi. 
3.- Ramificación. Seleccione una de las variables Xj. cuyo valor óptimo X*j en la solución del SPi no satisfaga la restricción de valor entero. Elimine la región [X*j] < Xj < [X*j] + 1 (donde [a] define al mayor entero ≤ a), 
creando dos subproblemas SP que correspondan a las dos siguientes restricciones mutuamente excluyentes:
 
Xj ≤ [X*j] y Xj ≥ [X*j]+1 Volver al paso 2. 
Veamos el siguiente caso.
Considere el siguiente problema de programación lineal entera: 
Max 5X1 + 4X2 
st 
 X1 + X2 ≤ 5 
10X1 + 6X2 ≤ 45
end
X1, X2 ≥ 0 y enteras 
La solución óptima SP0 da: X1 = 3.75, X2 = 1.25 con Z = 23.75 
El procedimiento ramificar y acotar se basa en tratar sólo con el problema PL. 
Como la solución óptima no satisface la necesidad de valores enteros, el algoritmo de ramificar y acotar exige “modificar” el espacio de soluciones PL en forma tal que nos permita identificar, finalmente, la solución óptima del problema de programación lineal entera. 
Primero, seleccionamos una de las variables cuyo valor corriente en la solución óptima SP0 infringe el requisito de valor entero. 
Seleccionando X1=3.75 arbitrariamente, observamos que la región (3 < X1 < 4) del espacio de soluciones SP0 no puede, por definición, incluir ninguna solución factible del problema de programación lineal entera. 
Entonces, podemos modificar el espacio de soluciones de PL eliminando esta región no prometedora, lo que, en realidad, es equivalente a reemplazar el espacio original SP0 por dos subproblemas de programación lineal, los SP1 y SP2, definidos de la manera siguiente:
 
1. Espacio SP1 = espacio SP0 + (X1 ≤ 3) 
2. Espacio SP2 = espacio SP0 + (X1 ≥ 4) 
Los dos espacios contienen los mismos puntos enteros factibles del modelo programación lineal entera. Esto significa que, desde el punto de vista del problema original de programación lineal entera, tratar con SP1 y SP2 es igual que tratar con el subproblema original SP0. 
La diferencia principal es que la selección de las nuevas restricciones de acotamiento (X1 ≤ 3 y X1 ≥ 4) mejorarán la oportunidad de forzar a los puntos extremos óptimos de SP1 y SP2 hacia la satisfacción del requisito de valor entero. 
Además, el hecho de que las restricciones de acotamiento estén en la “vecindad inmediata” del óptimo continuo del SP0 incrementará las posibilidades de producir “buenas” soluciones enteras. 
Las nuevas restricciones X1 ≤ 3 y X1≥ 4 son mutuamente excluyentes, SP1 y SP2 deben tratarse como dos problemas de programación lineal separados. 
Esto da lugar al método de ramificar y acotar. En efecto, ramificar significa subdividir un espacio de soluciones en subespacios mutuamente excluyentes. Las ramas asociadas se definen por las restricciones X1 ≤ 3 y X1 ≥ 4, donde X1 se denomina variable de ramificación. 
La solución óptima de la programación lineal entera debe encontrarse en el SP1 o en el SP2. Sin embargo, en ausencia del espacio gráfico de soluciones, no se sabe dónde puede encontrarse la solución óptima, por lo que la única opción es investigar ambos problemas. Se hace esto trabajando con un problema SP1 o SP2. Escojamos arbitrariamente al SP1, asociado con X1≤3. En efecto, ahora debemos resolver el siguiente problema: 
Como se indicó antes, el SP1 es el mismo que el SP0 con la restricción adicional de acotamiento superior, X1≤3. Así, podemos aplicar el método simplex de acotamiento superior para resolver el problema. Esto da la nueva solución óptima: X1 = 3, X2 = 2 y Z=23. 
Max 5X1 + 4X2 
st 
 X1 + X2 ≤ 5 
10X1 + 6X2 ≤ 45 
 X1 ≤ 3 
end
X1, X2 ≥ 0 y enteras 
Esto significa que cualquier solución entera mejorada debe tener un valor de Z mayor que 23. Sin embargo, como la solución óptima del problema SP0 (original) tiene Z = 23.75 y como todos los coeficientes de la función objetivo son enteros, se infiere que ningún subproblema queproceda del SP0 puede producir un valor de Z mejor que 23. En consecuencia, sin alterar la investigación, podemos descartar al SP2. 
En este caso se dice que el SP2 está agotado porque no puede dar una mejor solución entera.
Del análisis anterior vemos que un subproblema está agotado si se satisface una de las siguientes condiciones: 
 
Condiciones
i) El subproblema da una solución factible entera del problema programación lineal entera. 
ii) El subproblema no puede dar una mejor solución que la mejor cota inferior disponible (valor de Z) del problema programación lineal entera. (Un caso especial de esta condición es que el subproblema no tendrá ninguna solución factible)
Si la función objetivo ha de minimizarse, el procedimiento es el mismo, excepto que se emplean cotas superiores. Así, el valor de la primera solución entera se vuelve una cota superior para el problema y se eliminan los SPi cuando sus valores Z de primera aproximación son mayores que la cota superior actual. 
Caso 2. Aplicar el método de ramificar y acotar e indique la solución optima
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
end
X1, X2 ≥ 0 y enteras 
	SP0:
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
End
	 Z= 41.25 
 X1 =3.75 
 X2 =2.25 	
	SP1=SP0+ X1≥4 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
End
	Resolviendo con LINDO
	SP2 =SP0+ X1≤3 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≤3
End
	Resolviendo con LINDO
 X1≥4
 X1≤3
	SP0:
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
End
	 Z= 41.25 
 X1 =3.75 
 X2 =2.25 	
	SP1=SP0+ X1≥4 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
End
	 Z= 41 
 X1 = 4 
 X2 =1.8 		
	SP2 =SP0+ X1≤3 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≤3
End
	En forma semejante	
 X1≥4
 X1≤3
LP OPTIMUM FOUND AT STEP 2
 OBJECTIVE FUNCTION VALUE
 1) 41.00000
 VARIABLE VALUE REDUCED COST
 X1 4.000000 0.000000
 X2 1.800000 0.000000
 ROW SLACK OR SURPLUS DUAL PRICES
 2) 0.200000 0.000000
 3) 0.000000 1.000000
 4) 0.000000 -1.000000
 NO. ITERATIONS= 2
	SP0:
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
End
	 Z= 41.25 
 X1 =3.75 
 X2 =2.25 	
	SP1=SP0+ X1≥4 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
End
	 Z= 41 
 X1 = 4 
 X2 =1.8 		
	SP2 =SP0+ X1≤3 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≤3
End
	 Z= 39 
 X1 =3 
 X2 =3 		
 X1≥4
 X1≤3
	SP3=SP1+ X2≥2 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
 X2 ≥2
End
	 INFACTIBLE	
	SP4=SP1+ X2≤1 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
 X2≤1
End
	 Z= 40.55556
 X1 = 4.444445 X2 =1.0000 	
 X2≥2
 X2≤1
	SP4=SP1+ X2≤1 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
 X2≤1
End
	 Z = 40.55556
 X1 = 4.444445 X2 =1.0000 	
 X2≤1
	SP5=SP4+ X1≥5 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 ! X1 ≥4
 X2≤1
 X1 ≥5
End
	 Z* = 40.000
 X1 = 5.000 X2 =0.0000 	
	SP6=SP4+ X1≤4 	
Max 8X1 + 5X2 
st 
 X1 + X2 ≤6 
9X1 + 5X2 ≤45
 X1 ≥4
 X2≤1
 X1 ≤4
End
	 Z = 37
 X1 = 4.000 X2 =1.0000 	
 X1≥5
 X1≤4
Caso 3. Aplicar el método de ramificar y acotar e indique la solución optima.
Min 3X1 + X2 
st 
 X1 + 5X2 ≥ 8 
 X1 + 2X2 ≥ 4
end
X1, X2 ≥ 0 y enteras 
Algoritmo de Ramificación y Acotamiento
Programación Lineal Entera Mixta
Para resolver un PE mezclado, se requiere que algunas variables sean enteros y se permite que otras sean enteros o no enteros. Para ello se tiene que ramificar sólo sobre variables que deban asumir necesariamente valores enteros. Se tiene el PLEM:
Max 2X1 + X2 
st 
5X1 + 2X2 <= 8 
 X1 + X2 <= 3
end
X1, X2 ≥ 0; X1 entera 
Como antes, se empieza por resolver la relajación del PL del PE. La solución óptima de la relajación del PL es z=11/3, x1=2/3, x2=7/3. Como se permite que x2 sea fraccionaria, no se hace ramificación alguna sobre x2 entre 2 y 3, puesto que se estarían excluyendo y el procedimiento sería incorrecto. Por lo tanto se tiene que ramificar sobre x1. Así se originan los subproblemas 1 y 2.
Enseguida se elige resolver el subproblema 1. La solución para el subproblema 1 es la solución probable z=3, x1=0, x2=3. 
Entonces se resuelve el subproblema 2 y se obtiene la solución probable z=7/2, x1=1, x2=3/2. El valor de z de la solución probable del subproblema 2 excede el valor de z para la solución probable del subproblema 1, por eso el subproblema 1 se puede dejar de considerar, y la solución probable del subproblema 2 (z=7/2, x1=1, x2=3/2) es la solución óptima para el PLEM. 
	SP0:
Max 2X1 + X2 
st 
5X1 + 2X2 ≤8 
 X1 + X2 ≤3
End
	 Z= 11/3 
 X1 =2/3
 X2 =7/3	
	SP1=SP0+ X1≤0 	
Max 2X1 + X2 
st 
5X1 + 2X2 ≤8 
 X1 + X2 ≤3
 X1 ≤0 End
	Z= 3 
X1 =0
 X2 =3	
	SP2 =SP0+ X1≥1 	
Max 2X1 + X2 
st 
5X1 + 2X2 ≤8 
 X1 + X2 ≤3
 X1 ≥1 End
	 Z= 7/2 
X1 =1
 X2 =3/2	
 X1≤0
 X1≥1
Caso 5. Aplicar el método de ramificar y acotar e indique la solución optima.
Min 3X1 + X2 
st 
 X1 + 5X2 ≥ 8 
 X1 + 2X2 ≥ 4
end
X1, X2 ≥ 0 y X1 entera 
GRACIAS
“Cuidemos la 
vida”
¡Cuidemos nuestro futuro!