Programacion lineal entera

PROGRAMACION LINEAL ENTERA

INTRODUCCION

En muchos problemas reales no siempre es posible que las variables puedan tomar valores continuos. Así, existen problemas en los cuales las variables solo pueden tomar valor enteros, como por ejemplo cuantos viajes diarios debe realizar cada camión de una determinada empresa si sus capacidades son distintas, para cubrir una determinada demanda con un coste mínimo, en este caso si cada variable representa cada viaje que debe realizar cada camión, es evidente que solo podrán tomaran valores enteros. Incluso existen determinados problemas de decisión (de forma si o no) en los cuales las variables solo pueden tomar valores de uno o cero, por ejemplo si se instala un almacén en un determinado lugar la variable tomara valor uno y si no se instala valor cero.

En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado esta lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero.

CLASIFICACION

ATENDIENDIENDO AL TIPO DE VARIABLE

1. PROBLEMAS ENTEROS PUROS

Se denominan así todos aquellos problemas en que todas las variables son enteras.

También es frecuente dentro de este tipo de problemas distinguir los problemas totalmente enteros como aquellos en que además de las variables, también todos los coeficientes y el valora de la función objetivo han de ser enteros

2. PROBLEMAS ENTEROS MIXTOS

Se denominan así los problemas en los cuales existen al mismo tiempo variables continuas y variables que solo pueden tomar valores enteros.

3. PROBLEMAS BINARIOS

Es un caso particular de los anteriores, en los cuales las variables que han de ser enteras solo pueden tomar los valores cero o uno.

ATENDIENDIENDO AL MODELO

1. DIRECTO

Si el problema de decisión involucra variable entera

2. CODIFICADO

Cuando incluye alguna consideración de tipo cualitativo y para tratarla se requiere el uso de variables enteras o binarias (escalas)

3. TRANSFORMADO

Cuando el problema no incluye variables enteras pero para ser tratado analíticamente requiere el uso de variables enteras artificiales.

METODOS DE RESOLUCION

Cuando la solución al PLA no verifica las condiciones de integridad es cuando hay que plantearse algún método para obtener la solución entera, pensándose en primer lugar en obtener dicha solución por redondeo de la solución al problema continuo.

La obtención de una solución por redondeo puede presentar dos graves inconvenientes que son:

• La solución así obtenida puede no verificar las restricción, en cuyo caso no solo no sería la solución optima sino que además será infactible

• Aunque el redondeo se efectué de forma inteligente para evitar soluciones infactibles , la solución así obtenida no tiene porque ser la optima e incluso puede diferir mucho de ella.

Vamos a ver estos dos inconvenientes a partir del siguiente ejemplo:

Representando gráficamente:

La solución a dicho problema se encuentra en el punto A con valores:

Por lo que podríamos pensar que la solución optima entera podría ser el punto

...