Programación lineal

Programación Lineal

La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables.

El nombre de programación lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa 'realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate'.

Aunque parece ser que la programación lineal fue utilizada por G. Monge en 1776, se considera a L. V. Kantoróvich uno de sus creadores. La presentó en su libro Métodos matemáticos para la organización y la producción (1939) y la desarrolló en su trabajo Sobre la transferencia de masas (1942). Kantoróvich recibió el premio Nobel de economía en 1975 por sus aportaciones al problema de la asignación óptima de recursos humanos.

La investigación de operaciones en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de momentos más importantes fue la aparición del método del simplex. Este método, desarrollado por G. B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas. Partiendo de uno de los vértices de la región factible, por ejemplo el vértice A, y aplicando la propiedad: si la función objetivo no toma su valor máximo en el vértice A, entonces existe una arista que parte del vértice A y a lo largo de la cual la función objetivo aumenta. se llega a otro vértice.

El procedimiento es iterativo, pues mejora los resultados de la función objetivo en cada etapa hasta alcanzar la solución buscada. Ésta se encuentra en un vértice del que no parta ninguna arista a lo largo de la cual la función objetivo aumente.

Aunque a lo largo de esta unidad únicamente se resuelven problemas de programación lineal bidimensional, este tipo de análisis se utiliza en casos donde intervienen cientos e incluso miles de variables.

Objetivos:

• Resolver gráficamente inecuaciones y sistemas de inecuaciones lineales con dos incógnitas

• Conocer la programación lineal y sus aplicaciones a la vida cotidiana.

• Plantear y resolver situaciones con programación lineal.

La programación lineal en la logística.

El estudio de la distribución física de una empresa tiene como objetivo optimizar el flujo de productos desde los centros de producción hasta los clientes finales. Concretamente, la programación de la distribución se encarga de optimizar la asignación de las tareas a realizar (entrega de pedidos) a los recursos disponibles (vehículos).

En los últimos años la mayor parte de los estudios desarrollados en el ámbito de la distribución física de una empresa se concentra en el diseño de la estructura general de la distribución ampliándolo en muchos casos a otros procesos logísticos de la empresa. Así Laporte (1992) aplica la programación matemática y resume los principales algoritmos exactos y heurísticos desarrollados en problemas de vehículos. Baita et al (1998) presentan una clasificación de los problemas de rutas considerando también los costos de almacenaje. Hal et al (2001) presentan el estado del arte de las herramientas existentes y de los paquetes de programas disponibles para el estudio global de la cadena logística y apuntan sus limitaciones. En esta misma línea están los trabajos de Jayramman y Pirkul (2001). Las limitaciones de los estudios globales se hacen más evidentes en el caso de empresas cuyas características hacen necesaria una programación en un horizonte a corto plazo y que pueden variar considerablemente de otras programaciones anteriores y futuras.

En este trabajo se presenta la optimización de la distribución mediante programación matemática para empresas que necesiten una programación a corto plazo y que tienen las siguientes características:

(i) Distribución entre un origen y diferentes destinos.

(ii) Distribución basada en transporte directo origen-destino.

(iii) Flota de vehículos disponibles conocida.

(iv) Disponibilidad de un listado de pedidos a entregar, en un cierto horizonte temporal, con fechas de entrega mínima y máxima ("ventanas" en las fechas de entrega).

Esta caracterización considera algunos aspectos no contemplados usualmente en la programación de la distribución, como son las ventanas en las fechas de entrega de los pedidos. Tener en cuenta este margen que existe sobretodo en el transporte entre centros de almacenaje, puede reducir significativamente los costes de transporte ya que permite realizar menos viajes con los vehículos más llenos. Para ello se ha utilizado una analogía entre la programación de la distribución y la programación y la secuenciación de piezas a máquinas. La analogía se establece entre vehículos y máquinas y entre viajes y piezas. Con ello se han aplicado los procedimientos de penalización de tiempo de retraso en las entregas utilizados en programación y secuenciación de piezas a máquinas como presentan Backer y Scudder (1990) y se ha aplicado la programación lineal entera. (Verma y Dessouky, 1998)

El proceso global de distribución se considera dividido en sucesivos

...