Caracterización de la PLE
La programación 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 restricciones lineales no negativas. La teoría de la programación lineal cae dentro de la teoría de la optimización convexa y es también considerada como parte importante de la investigación de operaciones.
La programación lineal entera (PLE) es el conjunto de problemas 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 tiempo computacional.
Para la resolución de 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 solución 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 número de 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.
Como el conjunto de soluciones enteras factibles es un número finito pudiera pensarse en recorrerlas todas en busca de la solución pero esto puede resultar ineficiente pues según el número de variables el conjunto de soluciones se incrementa exponencialmente. Para enfrentar esto se han desarrollado un conjunto de técnicas basadas en la lógica de que la solución entera no debe encontrarse muy lejos de la óptima del modelo con variables reales, conocidas como Ramificar y Podar (Branch and Bound).[1]
Este método se basa en que existe un número finito de soluciones posibles, no todas factibles, para un problema con enteros, que pueden representarse mediante un diagrama de árbol. Pero no es necesario enumerar todas las soluciones posibles si se pueden eliminar algunas ramas. Para eliminar una rama basta demostrar que no contiene una solución factible que sea mejor que una ya obtenida.
| Página siguiente |