Antecedentes históricos
Durante
la Segunda Guerra Mundial se mantuvo en secreto y fue utilizada como mecanismo
para poder gestionar y planificar todos los gastos. De esta manera se
pretendía, gestionar mejor los recursos propios y reducir lo máximo posible lo
que eran los costos del ejército.
La programación lineal
La
programación lineal es el campo de la optimización matemática dedicado a optimizar
(maximizar o minimizar) una función lineal, denominada función objetivo, de tal
forma que las variables de dicha función estén sujetas a una serie de
restricciones expresadas mediante un sistema de inecuaciones también lineales.
La
programación lineal, en esencia, da respuesta a situaciones en las que se exige
optimizar funciones que se encuentran sujetas a determinadas limitaciones
llamadas restricciones.
Puede
ser:
1. Lineal entera
Todas las variables únicamente pueden tomar valores enteros. También se distinguen dentro de estos los problemas totalmente enteros como aquellos en que tanto las variables como todos los coeficientes que intervienen en el problema han de ser enteros.
2. Lineal mixta
Son aquellos en los que hay al mismo tiempo variables continuas y variables que sólo pueden tomar valores enteros.
3. Lineal binaria
Una variable entera binaria es aquella que solamente puede adoptar los valores 0 ó 1. Este tipo de variable se emplea para resolver situaciones del tipo inclusión o exclusión.
¿Cómo resolver un problema mediante la programación lineal?
El
primer paso para la resolución de un problema de programación lineal consiste
en la identificación de los elementos básicos de un modelo matemático.
1. Definir el objetivo:
Consiste en definir un criterio de optimización el cual puede ser Maximización o Minimización dependiendo del problema que se desee resolver, el cual es una función lineal de las diferentes actividades del problema. Bajo el criterio de optimización definido se pretende medir la contribución de las soluciones factibles que puedan obtenerse y determinar la óptima. La función objetivo tiene una estrecha relación con la interrogante general que se desea responder.
2. Identificar las variables de decisión
Son factores controlables del sistema que se está modelando, y como tal, estas pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor óptimo, que contribuya con la consecución del objetivo de la función general del problema.
3. Identificar los datos del problema
La finalidad de resolución de un problema es proporcionar los valores reales para las variables de decisión, pero se requiere de cierta información adicional para ayudar a determinar esos valores.
4.
Identificar
la función objetivo
Hay
que expresar el objetivo global en forma matemática usando las variables de
decisión y los datos conocidos del problema.
5. Identificación de las restricciones
Son los diferentes requisitos que debe cumplir cualquier solución para que pueda llevarse a cabo. En cierta manera son las limitantes en los valores de los niveles de las diferentes actividades.
Cuando hablamos de las restricciones en un problema de programación lineal, nos referimos a todo aquello que limita la libertad de los valores que pueden tomar las variables de decisión. Entre los tipos de restricción se encuentran:
Restricción de
capacidad: limitan el valor de las variables debido a la
disponibilidad de horas-hombre, horas-máquina, espacio, etc.
Restricción de mercado: Surgen de los valores máximos y mínimos en las ventas o el uso del producto o actividad a realizar.
Restricción de entradas: Son limitantes debido a la escasez de materias primas, mano de obra, dinero, etc.
Restricción de calidad: Son las restricciones que limitan las mezclas de ingredientes, definiendo usualmente la calidad de los artículos a manufacturar.
Restricciones de balance de material: Estas son las restricciones que definen las salidas de un proceso en función de las entradas, tomando en cuenta generalmente cierto porcentaje de merma o desperdicio.
Restricciones Internas: Son las que definen a una variable dada, en la formulación interna del problema, un ejemplo tipo, es el de inventario.
Condición de no – negatividad: En la programación lineal las variables de decisión sólo pueden tomar valores de cero a positivos. No se permiten valores negativos.
Las
restricciones de la PL toma forma de ecuación o inecuación, como se presenta a
continuación.
Métodos para resolver problemas de programación lineal
El
método gráfico es un procedimiento de solución de
problemas de programación
lineal. Este consiste en representar cada una de las
restricciones y encontrar en la medida de lo posible el polígono factible,
comúnmente llamado el conjunto solución o región factible.
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor
valor posible, según el caso, para el que se satisfacen todas las restricciones).
Partiendo
del valor de la función objetivo en un punto cualquiera, el procedimiento
consiste en buscar otro punto que mejore el valor anterior. Como se verá en el
método Gráfico, dichos puntos son los vértices del polígono que constituye la región determinada por las
restricciones a las que se encuentra sujeto el problema (llamada región
factible). La búsqueda se realiza mediante desplazamientos por las aristas del
polígono, desde el vértice actual hasta uno adyacente que mejore el valor de la
función objetivo. Siempre que exista región factible, como su número de
vértices y de aristas es finito, será posible encontrar la solución.
Uso de software: WinQSB
WinQSB es un sistema interactivo de ayuda a la toma de decisiones que contiene herramientas muy útiles para resolver distintos tipos de problemas en el campo de la investigación operativa. El sistema está formado por distintos módulos, uno para cada tipo de modelo o problema. Para la resolución de problemas de PL, se utiliza Lineal programmig and integer lineal programming.
Este
módulo incluye los programas necesarios para resolver el problema de programación
lineal gráficamente o utilizando el algoritmo del Simplex; también permite
resolver los problemas de programación lineal entera. Al introducir los datos
de la función objetivo y las restricciones en el software, se formará un cuadro
resumen con los siguientes datos:
Solution value: Valor solución, es el valor que toman las variables de decisión en nuestra solución óptima.
Unit Cost or Profit: El costo unitario o contribución es el valor que les fue asignado a las variables por nosotros en la función objetivo.
Total Contribution: Es la contribución total a la solución objetivo, es el producto del valor solución * costo unitario o contribución.
Basic Status: Después de que el problema se resuelve, esto representa si la variable es una variable de base, en el límite inferior, o en el límite superior en la tabla simplex final.
Allowable MIN, MAX C(j): Para un coeficiente de la función objetivo en particular. Este es el rango en que la base actual de la solución sigue siendo la misma.
Objective Function: Nos muestra el resultado de nuestra función objetivo.
Left Hand Side: Del lado izquierdo, es el valor que toma la ecuación de cada restricción luego de reemplazar las variables que la componen por los valores solución.
Right Hand Side: Del lado derecho, es el valor asignado por nosotros a las restricciones como máximo o mínimo recurso disponible.
Slack o Surplus: Cuando la restricción en cuestión tiene el operador <=, corresponde a una holgura, es decir, se puede interpretar como el recurso no utilizado. Cuando la restricción en cuestión tiene el operador >=, corresponde a un exceso, es decir, se puede interpretar como el recurso utilizado por encima de la restricción de mínimo uso.
Shadow Price: El precio sombra de una restricción, es el cambio marginal de la función objetivo cuando el valor del lado derecho de la restricción aumenta en una unidad.
Suscríbete
ConversionConversion EmoticonEmoticon