Programación lineal entera (página 2)

Existen otros métodos de
resolución de la PLE, como el procedimiento de
los cortes de Gomory. En esta técnica, se resuelve el
problema original relajado en el que se incluyen restricciones
adicionales, que reducen la región factible sin excluir
soluciones que
cumplen las condiciones de optimalidad. En cada iteración
se añade una restricción que se denomina corte de
Gomory. Este procedimiento genera progresivamente una envoltura
convexa de la región factible entera, lo que origina
soluciones que cumplen las condiciones de integralidad. Este
método se
explica más en detalle por Castillo et
al[2]

En los modelos de PLE
es importante valorar el número de variables a
manejar pues si el modelo tiene
algunos cientos de variables y no tiene una estructura
especial, puede resultar demasiado costoso de resolver. Los
modelos enteros son no polinomiales, o sea el tiempo de
resolución es exponencial con respecto al número de
restricciones y especialmente con respecto al número de
variables de decisión enteras, como expone Castillo et
al[3]En los casos en que los métodos
generales de PLE, por las dimensiones del problema, resultan
ineficientes, resulta válido introducir métodos
heurísticos que obtienen soluciones aproximadas
satisfactorias.

Modelos
especiales

Existen ciertos problemas de
PLE que por las características del modelo han sido
enfrentados con métodos particulares de solución
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 investigación
de operaciones que está presente en muchos problemas
reales, entre ellos resultan muy interesantes los de organización 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.

Bibliografía

Castillo, E; AJ Conejo; P Pedregal; R
García y N Alguacil. Formulación y
Resolución de Modelos de Programación Matemática
en Ingeniería y Ciencia;
Ciudad Real, España,
2002. Disponible en:
.

Castillo, E, AJ Conejo, P Pedregal, R
García, y N Alguacil. Formulación y
Resolución de Modelos de Programación
Matemática en Ingeniería y Ciencia. Capítulo
2. Modelización; Ciudad Real, España, 2002.
Disponible en:
http://www.investigacion-operaciones.com/Libro/modelizacion.pdf.

Hillier, FS y GJ Lieberman. Introduction to
Operations Research; Singapore: McGraw-Hill Internacional,
2005.

Vanderbei, RJ. Linear Programming:
Foundations and Extensions; New Jersey, USA: Princenton
University, 2001.

Autor:

Ana E.
Hernández

[1] Vanderbei, RJ;"Linear Programming:
Foundations and Extensions", New Jersey, USA: Princenton
University; 2001, pág. 380.

[2] Castillo, E, AJ Conejo, P Pedregal, R
García, y N Alguacil; "Formulación y
Resolución de Modelos de Programación
Matemática en Ingeniería y Ciencia", Ciudad Real,
España; 2002. Disponible en: http://www.investigacion-operaciones.com/Libro/LibroCompleto.pdf.

[3] Castillo, E, AJ Conejo, P Pedregal, R
García, y N Alguacil; "Formulación y
Resolución de Modelos de Programación
Matemática en Ingeniería y Ciencia.
Capítulo 2. Modelización", Ciudad Real,
España; 2002. Disponible en:
http://www.investigacion-operaciones.com/Libro/modelizacion.pdf,
pág. 20.