Programación Lineal Entera

El problema con la programación lineal entera, es que no existe un algoritmo rápido para hallar la solución. El método más frecuentemente utilizado, se llama Branch and Bound (ramificar y acotar), y es una adaptación de la solución continua.
 
 Este algoritmo toma la solución del programa continuo y la divide en dos problemas si ésta no fue entera (si lo hubiera sido ya habríamos terminado, pero eso sólo sucede en las películas), cada uno con una restricción de más.  Por   ejemplo, si la solución continua fue X1 = 7.25, se dividiría en dos problemas, uno con la restricción X1<=7 y el otro con la restricción X1 >= 7 . Se encuentran las soluciones, para estos problemas y se comparan, le mejor gana; si no es entera se repite el proceso de nuevo.
 
Como se puede ver, éste método consume muchos más recursos de máquina; en un problema de Planeación Agregada, con unas cien variables y unas sesenta restricciones, y algo de  mala suerte, se podrían estar resolviendo unos cuantos miles de problemas continuos asociados, y cada uno de estos podría consumir bastante tiempo. Tal vez con los nuevos estudios en métodos de punto interior, como el de Karmakar, se pueda derivar un método mucho más eficiente que el de branch and bound.

 

A propósito, Solver utiliza branch and bound para la programación lineal entera.

Resolver:

 

Max Z = 3 X1 + 4X2
               4 X1 + 2X <=  8
               2X1   + 5X2  <=  10       

X1, X2 enteros positivos.

Lo modelamos de igual manera que el ejemplo continuo, y en las restricciones especificamos que X1 y X2 son enteros. No es más.

 

 

Y en las restricciones...

 

 

 

 

Para los programas Lineales enteros es muy importante que Solver, esté debidamente configurado para un número suficiente de iteraciones, de tiempo,  de precisión y de convergencia, para esto ver los detalles de Solver.

Contenido :

Social