PROGRAMACION ENTERA

Caracterización de la PLE

La programacion lineal también conocida como optimización lineal, es la maximización o minimización de una función lineal sobre un poliedro convexo definido por un conjunto de restriccioneslineales no negativas. La teoria de la programación lineal caede operaciones.

La programación lineal entera (PLE) es el conjunto deproblemas  de programación lineal para los cuales todas o parte de sus variables pertenecen a los números enteros.

Un problema de PLE puede describirse de la siguiente forma:

Optimizar una función objetivo z=c.x

Bajo las restricciones Ax = ó = b, x = 0
Donde:
x -Vector con variables enteras
c -Vector de coeficientes de la función objetivo

A -Matriz de coeficientes de las restricciones

b -Vector de términos independientes

Los modelos de programación lineal entera pudieran clasificarse en tres grupos:

Entero completamente. Todas las variables de decisión son enteras.

• Mixto. Algunas de las variables son enteras, las otras no.
• Binario. Las variables solo toman los valores  0 ó 1.

Métodos de solución

Pudiera pensarse que los métodos de obtención de soluciones a problemas de programación lineal entera pudieran ser menos difíciles que los de programación lineal generales, pero resulta lo contrario. Los algoritmos que permiten resolver los problemas restringidos a enteros son más complejos y requieren mucho más tiempode los problemas de programación lineal entera existen diferentes métodos. Los métodos exactos son los que encuentran, si existe, el óptimo absoluto. Muchos de estos métodos parten de la resolución del modelo dejando a un lado las restricciones enteras y buscando el mejor valor para las variables reales. A partir del supuesto de que la solucion entera no debe estar muy lejos, se aplican diferentes técnicas que permiten llegar al óptimo entero.

Una breve introducción a los métodos de la programación lineal: Simplex y Punto interior , permitirá tener una idea  de cómo operan los mismos.

El método del simplex se utiliza para hallar las soluciones óptimas de un problema de programación lineal con tres o más variables. Este se basa en el hecho de que la solución óptima se encuentra siempre en uno de los vértices del poliedro formado por el conjunto de restricciones. Su forma de buscar la solución es recorrer sobre estos vértices hasta encontrar el óptimo. Aun cuando no corre en tiempo polinomial en el caso peor, su mayor valor radica en su capacidad de revolver nuevos problemas y resulta muy útil cuando no se tiene un algoritmo eficiente de solución.

Los métodos de punto interior se denominan así precisamente porque los puntos generados por estos algoritmos se hallan en el interior de la región factible. Esta es una clara diferencia respecto al método del simplex. En la actualidad los métodos de punto interior más eficientes tienen una complejidad de orden T(nL), donde n es el numerode variables y L una medida del tamaño del problema (el número de bits necesarios para representar los datos).

En la modelación lineal no entera se demuestra que el óptimo es un vértice de la región factible. En los modelos enteros, esto no tiene porque ser así, de manera general los vértices no tienen que ser números enteros. Por ello la solución óptima se encontrará en el interior de la región factible, por lo que los métodos exactos, como el simplex o punto interior, empleado de forma directa no aportarán la solución óptima en la generalidad de los casos.

Modelos especiales

Existen ciertos problemas de PLE que por las características del modelo han sido enfrentados con métodos particulares de solucion atendiendo a estas peculiaridades. Entre estos se encuentran los modelos de asignación y de transporte. Estos resultan significativos porque se ajustan a muchos problemas de diversos sectores y especialidades.

El clásico problema de asignación (variables binarias 0 no se asigna, 1 se asigna) se caracteriza por tener n personas y n objetos donde hay que hacer correspondencia uno a uno entre los dos conjuntos. En el mismo existe un beneficio o un costo para cada asignación persona -objeto, y se quiere obtener la asignación donde ese beneficio sea máximo o el costo mínimo. La asignación puede ser resuelta por métodos diversos, entre ellos destaca el método Húngaro de orden T(n3) por ser el más antiguo de los conocidos para enfrentar los problemas de asignación.

El problema del  transporte consiste en satisfacer de forma óptima (costos mínimos de transportación) n destinos desde m orígenes, donde están definidos los costos de transportación de cada origen a cada destino, la demanda  de los destinos y la oferta  de cada origen. Los métodos para hallar la solución se basan en una metaheurística que consiste en buscar una solución factible inicial, e ir mejorándola hasta llegar a la solución óptima. Existe gran diversidad de técnicas  para obtener la solución inicial y de formas para las mejoras iterativas.

Estos problemas son casos particulares de PLE en los que métodos especiales de solución resultan más eficientes que los métodos tradicionales.

La PLE es una rama de la investigacion de operaciones  que está presente en muchos problemas reales, entre ellos resultan muy interesantes los de organizacion de tiempos de trabajo  que existen en diferentes ramas de la producción y los servicios. La selección de los métodos de solución más eficientes depende en gran medida de las particularidades del escenario que se ha modelado.