La Programación Lineal (PL) es una de las principales ramas de la Investigación Operativa. En ésta categoría se consideran todos aquellos modelos de optimización donde las funciones que lo componen, es decir, función objetivo y restricciones, son funciones lineales en las variables de decisión.
Los modelos de Programación lineal por su sencillez son frecuentemente usados para abordar una gran variedad de problemas de naturaleza real en ingienería y ciencias sociales, lo que ha permitido a empresas y organizaciones importantes beneficios y ahorros asociados a su utilización.
Ejemplo 1:
- Se desea obtener la mezcla de petróleo a partir de crudos de distinta procedencia, cada uno de los cuales tienen distintas características. En la tabla adjunta se detallan los distintos crudos - cuatro en total - y sus características más importantes: el tanto por ciento de azufre, la densidad y el precio por Tm.
Se exige a la mezcla que tenga unas características concretas, que se traducen en un porcentaje del 0.40 % de contenido de azufre y una densidad igual a 0.91. Se desea que el precio de la mezcla sea mínimo.
Los elementos fundamentales de este problema, y que caracterizan cualquier problema de programación matemática, son los siguientes:
• Variable de decisión:
Permite caracterizar matemáticamente la decisión a adoptar. En general es un vector de Rn, en el ejemplo debe identificar la mezcla y puede ser el porcentaje o la proporción de cada uno de los crudos en la mezcla. Supondremos que es la proporción (xi). Se introducen las variables (x1, x2, x3, x4) ∈ R4 que representan la proporción con que intervendrán en la mezcla los crudos procedentes de Kuwait, Arabia, Noruega y Venezuela respectivamente.
• Conjunto de restricciones:
La variable de decisión debe verificar una serie de restricciones de forma que una decisión válida debe pertenecer a un subconjunto de Rn. En los problemas de programación lineal las restricciones se identificarán por un conjunto de ecuaciones lineales en la variable de decisión y se supondrá que todas las componentes de la variable de decisión son mayores o iguales que 0. En el ejemplo hay tres restricciones, aparte de la restricción natural de que cualquier proporción no debe ser negativa
xi ≥ 0
- La suma de proporciones debe ser igual a 1.
x1 + x2 + x3 + x4 = 1
- El contenido (en %) de Azufre de la mezcla debe ser 0.4.
0.45 x1 + 0.40 x2 + 0.38 x3 + 0.41 x4 = 0.40
- La densidad de la mezcla debe ser 0.91
0.91 x1 + 0.95 x2 + 0.89 x3 + 0.92 x4 = 0.91
• Función objetivo
Existe una función que evalúa todas las decisiones válidas y el problema es elegir aquella decisión que minimiza dicha función. En los problemas de P.L. esta función también depende linealmente de la variable de decisión. En el ejemplo, cada mezcla válida tiene asociado un coste de forma que la función objetivo es el precio de cada Tm. de mezcla:
35.000 x1 + 31.000 x2 + 39.000 x3 + 34.000 x4
La mezcla óptima verificando las restricciones anteriores se obtiene mezclando los crudos procedentes de Noruega y Venezuela en las proporciones 1/3 y 2/3 respectivamente y el precio de esta mezcla es de 35.667’67 ptas./Tm. La variable de decisión toma los valores
(x1, x2, x3, x4) = (0,0,1/3,2/3)
Como realizar ejercicios usando Solver.- Es un excelente complemento de MS Excel que prmite la resolución de de pequeños y medianos problemas de programación Lineal. En la mayoría de las aplicaciones con fines estundiatiles es suficiente para resolver dichas instancias.
Max Z = 10 X1 + 8 X2 [Ecuación 1]
Sujeto a:
30X1 + 20X2 ≤ 120 [Ecuación 2]
2X1 + 2X2 ≤ 9 [Ecuación 3]
4X1 + 6X2 ≤ 24 [Ecuación 4]
y X1, X2 ≥ 0 [Ecuación 5]
Paso 1: Se abre Excel
2. En una hoja, se ubican las celdas que se corresponderán con el valor de las variables de decisión; en éste caso, las celdas B6 y C6, se les da un formato para diferenciarlas de las demás, aquí azul oscuro (ver captura abajo). Se ubican también, las celdas que contendrán los coeficientes de las variables de decisión, B4 y C4, y se llenan con sus respectivos valores, 10 y 8. Este último paso se podría omitir y dejar los coeficientes definidos en la celda de la función objetivo, lo cual es mejor para los análisis de sensibilidad y para que la hoja quede utilizable para otro programa.
3. Se ubica la celda B3 que corresponderá a la función objetivo (celda objetivo). En ella se escribe la función correspondiente, en éste caso la Ecuación 1: el coeficiente de X1 (en B4) por el valor actual de X1 (en B6) mas el coeficiente de X2 (en C4) por el valor actual de X2 (en C6). Es decir, =$B$4*$B$6+$C$6*$C$4
4. Coeficientes para la primera restricción los podemos escribir en la misma columna de las variables de decisión; en las celdas B7 y C7, con los valores 30 y 20, seguido del sentido de la desigualdad (<=) y de su correspondiente RHS: 120.
5. A la derecha ubicaremos el valor actual de consumo de la restricción que se escribirá en función de las variables de decisión y de los coeficientes de la restricción. Esta celda, la utilizará Solver como la real restricción, cuando le digamos que el valor de ésta celda no pueda sobrepasar la de su correspondiente RHS. De nuevo será el valor del coeficiente por el de la variable: =B7*$B$6+C7*$C$6. Nótese que ahora B7 y C7 no tienen el signo $. Esto nos permitirá que luego que se haya escrito esta celda, se podrá arrastrar hacia abajo para que Excel escriba la fórmula por nosotros (¡la comodidad de Excel!), pero tomando los valores relativos a los coeficientes que corresponda a los mismos valores de las variables de decisión.
6. Se repite los pasos anteriores para las otras restricciones, pero ahora la fórmula será: =B8*$B$6+C8*$C$6 y =B9*$B$6+C9*$C$6.
Resolución:
1. Hacer click en Herramientas > Solver y se tendrá una pantalla como la siguiente:
2. Lo primero que hay que hacer es especificar la celda objetivo y el propósito: maximizar. Se escribe B3 (o $B3 ó B$3 ó $B$3 como sea, da igual), en el recuadro "cambiando las celdas", se hace un click en la flechita roja, para poder barrer las celdas B6 y C6 es exactamente lo mismo si se escriben directamente los nombres).
3. Y ahora para las restricciones se hace click en agregar. En F7 está la primera restricción, como se puede ver en la captura. Se especifica el sentido de la restricción <=, >= ó =. Aquí también se puede especificar el tipo de variable, por defecto es continua, pero se puede escoger "Int" para entera o "Bin" para binaria. En el recuadro de la derecha establecemos la cota. Aquí podemos escribir 120 pero mejor escribimos $E$7 para que quede direccionado a la celda que contiene el 120, y después lo podríamos cambiar y volver a encontrar la respuesta a manera de análisis de sensibilidad. Se presiona Aceptar.
Se obtiene el siguiente resultado:
4. Se repite el paso anterior para las otras dos restricciones.
5. La condición de no negatividad hay que incluirla manualmente, así:
Finalmente, el cuadro de diálogo deberá lucir así:
METEDO GRÁFRICO
El método gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo.
El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.
Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos.
Los pasos necesarios para realizar el método son nueve:
1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea.
2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles.
3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta.
4. trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada.
5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.
6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo.
7. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.
Ejemplo.
Maximizar Z = 3X1 + 2X2
restricciones : X1 + 2X2 <=6 (1)
2X1 + X2 <=8 (2)
-X1 + X2 <=1 (3)
X2 <= 2 (4)
X1 >= 0 (5)
X2 >= 0 (6)
Convirtiendo las restricciones a igualdad y representandolas gráficamente se tiene:
X1 + 2X2 = 6 (1)
2X1 + X2 = 8 (2)
-X1 + X2 = 1 (3)
X2 = 2 (4)
X1 = 0 (5)
X2 = 0 (6)
Grafica
