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  |