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.
| Página siguiente |