Programación lineal

La Optimización es una de las metodologías más importante para formular y resolver diversos problemas orientados a la toma de decisiones en las diferentes áreas de la Ingeniería, la Economía y en particular, en la Investigación Operativa.
Programación Lineal
 
Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la funciónobjetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.
 
Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos Estocásticos (ME). En el primer caso (MD)se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Lasaplicaciones de los modelos de Programación Lineal abarcan diversas áreas de la Ingeniería. A continuación un breve compendio de alguna de sus aplicaciones y referencias de interés para el lector:
 
1. Problema de Transporte: (Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947). El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (platas, ciudades,etc) a ciertos puntos de destino (centros de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.
 
Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:
 
  | C.Dist. 1 | C.Dist.2 | C.Dist.3 |
Planta 1 | 21 | 25 | 15 |
Planta 2 | 28 | 13 | 19 |
 
Se requiere formular un modelo de Programación Lineal que permita satisfacer losrequerimientos de demanda al mínimo costo.
 
Solución:
Variables de Decisión: Xij : Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)
Función Objetivo: Minimizar el costo de transporte dado por la función: 21X11 + 25X12 + 15X13 + 28X21 + 13X22 + 19X23
Restricciones:
Satisfacer los requerimientos de Demanda:
X11+ X21 = 200
X12 + X22 = 200
X13+ X23 = 250
Sujeto a la Oferta de las plantas::
X11+ X12 + X13 = 250
X21 + X22+ X23 = 400
No Negatividad: Xij >= 0
El siguiente diagrama permite una visualización de la situación anterior:

 
 
 
 
 
 
 
 
 
 
 
 
 
Resolución utilizando el complemento Solver de Microsoft Excel:
 
1. Abrir una Planilla de Cálculo de Excel. Asegurese de tener instalado el complementoSolver (Opción Herramientas - Complementos)
Luego construya una planilla como la de la imagen de referencia. Se han marcado con amarillo las celdas cambiantes (variables de decisión) y función objetivo. Para facilitar el seguimiento se ha escrito en rojo las fórmulas asociadas a cada celda.

 
 
 
 
 
 
 
 
 
 
 
 
 
2. Ingrese la función objetivo, celdas cambiantes y restricciones enla ventana de "Parámetros de Solver". Si utiliza la mismas celdas de la imagen anterior, usted debería obtener lo siguiente:

 
 
 
 
 
 
 
 
 
 
 
 
 
3. Ingrese a "Opciones". Luego selecione "Adoptar modelo lineal" y "Asumir no negativos". Finalmente presione "Aceptar". Luego de esto usted volverá a la pantalla principal (Parámetros de Solver)

 
 
 
 
 
 
 
 
 
 
 ...