Programación Lineal Entera

Divide y Vencerás... o te vencerán las $#"$"%&$&$& iteraciones!!!

Uno puede llegar a pensar que es más fácil encontrar la solución a un programa lineal entero que a uno continuo (los programas continuos son los que admiten soluciones decimales), después de todo, el número de soluciones continuas son infinitas mientras que las enteras serán finitas...
 
...Pero desafortunadamente no es así. Cuando se tiene un problema de dos variables se puede encontrar la solución óptima entera muy fácil a partir de la solución óptima continua utilizando el método gráfico y explorando las soluciones enteras cercanas dentro del área de soluciones factibles. Pero resulta que en la vida real (o sea aquella que está más allá de los problemas introductorios de los textos guías) los problemas muy pocas veces, tienen dos variables pues en un fenómeno por sencillo que sea tendrá muchísimas variables relevantes dentro de su comportamiento y el modelo matemático entre más se simplifique menos representativo será.
 
Los problemas enteros son más difíciles de resolver que los continuos, aún no existe un algoritmo que sea rápido, el más popular -por ahora- es este algoritmo, el de Branch And Bound, pero hay buenas esperanzas en el desarrollo de Algoritmos Rápidos, basados en los Algoritmos de Punto Interior (aquellos dónde no se itera a través de las soluciones extremas al volumen de soluciones factibles, sino por dentro).
 
 

Aviso Antipedagógico

 
  Si usted es un estudiante de IO de pregrado le voy a hacer una revelación que usted siempre intuyó, como cuando se dio cuenta que el niño Dios realmente era su papá...

...En problemas de la vida real uno nunca los hace a mano, uno siempre utiliza un software que le ayude a hacer los cálculos... Bueno, entonces cuál es la utilidad de ver esto en clase -a parte de darle trabajo a los profesores- y hacer cientos de cálculos manuales con las tablas Simplex o de punto interior? Pues que aunque saber modelar y utilizar el software es "suficiente" para sacar buen provecho de la Investigación de Operaciones, no es suficiente para Crear nuevo conocimiento en Investigación de Operaciones, además que crea una lucidez mental al utilizar el software no se hace como una caja negra sino que se sabe que es lo que se está haciendo tras bambalinas. Otra razón -que yo no dimensioné cuando estaba en la universidad- pero que se puede presentar, como me ha pasado a mi, es que Uno Tenga Que Desarrollar Software que utilicen estos métodos. Yo por ejemplo, en estos momentos estoy haciendo un módulo de Planeación Agregada que utiliza Programación Lineal Mixta (continua y Entera), si no hubiera tenido juicio con esta materia en la universidad y me hubiera dejado contagiar por la perecita de aprender el algoritmo -y sus fundamentos- no habría podido estar haciendo este software en este momento. 
 
 

El Algoritmo

 
 
En palabras es lo siguiente:


Resolver el Problema Lineal Continuo Asociado

 

  • Si la respuesta es entera, para las variables que se desean que sean enteras, se ha terminado (una vez me dijo mi papá que cuando algo parece demasiado bueno para ser cierto, es por que no es cierto, así es que si le sucede lo de este punto, revise de nuevo, por que tiene que estar muyyyyyyyyyy de buenas para que eso lo pase)
 
  • Si la respuesta no es entera para las variables que se desea que sean enteras, entonces tome cualquiera de ellas  (no importa cual), y divida el problema original en dos subproblemas (a esto se llama ramificar, cada subproblema nueva representa una nueva rama), a cada subproblema se le va a agregar una restricción de la siguiente manera: Supongamos una de las variables  que se desea que sea entera es X7 y su valor óptimo continuo fue de 6.8 entonces a un subproblema se le agrega la restricción X7<=6 y al otro subproblema se le agrega la restricción X7>=7. (Ud se puede preguntar, bueno, y eso como por que o que? Rta: Resulta que todos los valores mayores a 6 y menos de 7 no son enteros, si no son enteros no nos sirven, pero como no podemos colocar ambas restricciones en el mismo problema por que no sería factible, toca abrir dos problemas...)
  • Cada subproblema se soluciona: En caso que la solución de uno de los subproblemas sea entera para todas las variables que se desean enteras, ya no se sigue subdividiendo por esa rama y se tiene en cuenta cuanto da Zeta. (Pues todavía no podemos cantar victoria, por que alguna solución entera de la otra rama puede tener un mejor Zeta. Que triste que es la vida, cierto?)     
  • Cuando una rama ya encuentra todas las soluciones enteras para las variables que se desea que sean enteras (Que pena por la repetición, es que trato en lo posible que sea lo más entendible, o sea Max Z = Entendimiento de mis enredadas explicaciones), O si encontró una solución continua, pero el Zeta de esa solución continua es menor que el Zeta de alguna solución entera que ya se había encontrado en otra rama, O si el problema le dio no factible... pues esa rama queda agotada y no se sigue ramificando. Ahí para y sigue con otra rama.
  • Si agotó todas las ramas y ... no encontró solución entera al problema......pues mala suerte guerrero. No hay solución entera para su problema, tiene que trabajar con tres operarios y medio... jajaja.
  • No entendió ni jota del algoritmo? No se preocupe, que yo tampoco lo entendí al principio, sólo lo entendí cuando vi los árboles dibujados con los ejemplos...

 

 

15 de Septiembre del 2001.
 

Social