8.2: Optimización lineal
- Page ID
- 85409
La optimización lineal es un método aplicable para la solución de problemas en los que la función objetiva y las restricciones aparecen como funciones lineales de las variables de decisión. Las ecuaciones de restricción pueden ser en forma de igualdades o desigualdades [1]. En otras palabras, la optimización lineal determina la manera de lograr el mejor resultado (por ejemplo, para maximizar el beneficio o minimizar el costo) en un modelo matemático dado y dadas algunas listas de requisitos representados como ecuaciones lineales [2].
Aplicaciones
La optimización lineal se puede aplicar a numerosos campos, en situaciones empresariales o económicas, y también en la resolución de problemas de ingeniería. Es útil para modelar diversos tipos de problemas en planeación, enrutamiento, programación, asignación y diseño [2].
Algunos ejemplos de aplicaciones en diferentes industrias
Refinerías de petróleo
Una de las primeras aplicaciones industriales de optimización lineal se ha realizado en las refinerías de petróleo. Una refinería de petróleo tiene la opción de comprar petróleo crudo de diferentes fuentes con diferentes composiciones a diferentes precios. Puede fabricar diferentes productos, como el combustible diesel, la gasolina y el combustible de aviación, en cantidades variables. Se busca una mezcla del crudo comprado y los productos manufacturados que dé el máximo beneficio.
Firmas manufactureras
Las ventas de una firma suelen fluctuar, por lo tanto, una empresa tiene varias opciones. Puede ya sea construir un inventario de los productos manufacturados para llevarlo a través del período de pico de ventas, o para pagar tarifas de horas extras para lograr una mayor producción durante períodos de alta demanda. La optimización lineal toma en cuenta los diversos factores de costo y pérdida y llega al plan de producción más rentable.
Industria de procesamiento de alimentos
La optimización lineal se ha utilizado para determinar el plan de envío óptimo para la distribución de un producto en particular desde diferentes plantas de fabricación a diversos almacenes.
Telecomunicaciones
El enrutamiento óptimo de mensajes en una red de comunicación y el enrutamiento de aeronaves y barcos también se pueden determinar mediante el método de optimización lineal.
Características de la Optimización Lineal
Las características de un problema de optimización lineal son:
- La función objetiva es del tipo de minimización
- Todas las restricciones son del tipo de igualdad
- Todas las variables de decisión son no negativas
Cualquier problema de optimización lineal se puede expresar en la forma estándar usando la siguiente transformación:
1) La maximización de una función\(f\left(x_{1}, x_{2}, \ldots, x_{n}\right)\) equivale a la minimización del negativo de la misma función.
Por ejemplo:
Minimizar
\[f=c_{1} x_{1}+c_{2} x_{2}+\ldots+c_{n} x_{n}\nonumber \]
es equivalente a
Maximizar
\[f^{\prime}=-f=-c_{1} x_{1}-c_{2} x_{2}-\ldots-c_{n} x_{n}\nonumber \]
En consecuencia, la función objetiva se puede afirmar en forma de minimización en cualquier problema de optimización lineal.
2) Si una restricción aparece en forma de un tipo de desigualdad “menor o igual a” como
\[a_{k 1} x_{1}+a_{k 2} x_{2}+\ldots+a_{k n} x_{n} \leq b_{k}\nonumber \]
se puede convertir en la forma de igualdad agregando una variable de holgura no negativa de la
siguiente manera:
\[a_{k 1} x_{1}+a_{k 2} x_{2}+\ldots+a_{k n} x_{n}+x_{n+1}=b_{k}\nonumber \]
De igual manera, si la restricción es en forma de un tipo de desigualdad “mayor que o igual a”, se puede convertir en la forma de igualdad restando la variable excedente.
3) En la mayoría de los problemas de optimización de ingeniería, las variables de decisión representan algunas dimensiones físicas, de ahí que las variables no
sean negativas.
Sin embargo, una variable puede ser irrestricta en el signo en algunos problemas. En tales casos, una variable sin restricciones (que puede tomar un valor positivo, negativo o cero) puede escribirse como la diferencia de dos variables no negativas.
Así, si es irrestricto en signo, se puede escribir como\(x_{j}=x_{j}^{\prime}-x_{j}^{\prime \prime}\), donde
\(0 \leq x_{j}^{\prime}\)y\(0 \leq x_{j}^{\prime \prime}\)
Se puede ver que será negativo, cero o positivo, dependiendo de si
es mayor que, igual o menor que
Este ejemplo viene de Seborg, Edgar y Mellinchamp (con algunas correcciones). Una compañía química está mezclando componentes químicos,\(A\) y\(B\) para producir producto,\(E\) y\(F\). La reacción química se enumera a continuación:
\[A+B=E\nonumber \]
\[A+2 B=F\nonumber \]
Las condiciones de esta producción se enumeran a continuación:
| Costo de Materiales | Máximo disponible por día | Costo Fijo | |
|---|---|---|---|
| A | $0.15/lbs | 40,000lbs | 350 |
| B | $0.20/lbs | 30,000lbs | 200 |
| Valor de los productos | Tasa máxima de producción | ||
| E | $0.40/lbs | 30,000lbs | |
| F | $0.33/lbs | 30,000lbs |
El beneficio de esta producción puede describirse simplemente como la función a continuación:
Beneficio
| = | ∑ | F s V s − | ∑ | F r V r − C. P. − F. C. |
| s | r |
Caudales de Productos
Caudales de Materias Primas
Valores de los Productos
Valores de las Materias Primas
Costo de Producción
Costo Fijo
Restricciones
- :
- :
- :
- :
- :
≥ 
Solución
\[F_{A}=\frac{1}{2} F_{E}+\frac{1}{3} F_{F} \nonumber \]
\[F_{B}=\frac{1}{2} F_{E}+\frac{2}{3} F_{F} \nonumber \]
\[\text { Profit }=\sum_{s} F_{s} V_{s}-\sum_{r} F_{r} V_{r}-C . P .-F . C . \nonumber \]
\[=\left(0.4 \psi_{F_{j}}+0.33 F_{F^{-}}\right)-\left(0.15 F_{A}^{\prime}-0.2 F_{H}^{\prime}\right)-\left(0.15 F_{F_{i}}+0.05 F_{F}^{\prime}\right)-(350+200 i \nonumber \]
0 "src=”/@api /deki/files/18014/image-717.png “>
0 "src=”/@api /deki/files/18016/image-718.png “>
-\ frac {3} {2} F_E... (1) "src=”/@api /deki/files/18018/image-719.png “>
0 "src=”/@api /deki/files/18025/image-723.png “>
0 "src=”/@api /deki/files/18027/image-724.png “>
-\ frac {3} {4} F_E... (3) "src=”/@api /deki/files/18029/image-725.png “>
Solución usando Mathematica
ENTRADA:
beneficio = 0.25 FE + 0.28 FF - 0.15 FA - 0.2 FB - 350 - 200
sol = Maximizar [ganancia, {FA > 0, FB > 0, FA < 40000, FB < 30000, FE > < 30000, FF > 0, FE 0, FF < 30000, FA == (1/2) FE + (1/3) FF, FB == (1/2) FE + (2/3) FF}, {FE, FF}]
SALIDA: {3875., {FE -> 30000., FF -> 22500.}}
Solución usando “Solver” en Excel.
El resultado es FE = 30,000, FF = 22500.
¡Si tan solo procese! o proceso 2 estaban funcionando a plena capacidad, la ganancia sería menor.
Optimización Lineal
Lo anterior es un ejemplo de optimización lineal. A menudo se usa en la refinería de petróleo para calcular el beneficio máximo en respuesta a la competencia del mercado.
2.4.4 Gráfica
Ejemplo 2
Ejemplo de Problema de Optimización Lineal en Excel
Escrito por: Jennifer Campbell, Katherine Koterba, MaryANN Winsemius
Parte 1: Organizar la información dada
Como se indicó en el ejemplo de la sección Optimización Lineal anterior, hay tres categorías de información necesarias para resolver un problema de optimización en Excel: una función objetiva, restricciones y variables de decisión.
Utilizaremos el siguiente ejemplo para demostrar otra aplicación de optimización lineal. Estaremos optimizando las ganancias para el negocio de camiones de la Compañía X.
Para alcanzar su capacidad, la Compañía X debe mover 100 toneladas de carga por día en camión. La tarifa de camiones de la Compañía X es de $250/ton. Además de la restricción de peso, la compañía solo puede mover 50,000 ft^3 de carga por día debido a la limitada capacidad de transporte por volumen. Los siguientes montos de carga están disponibles para su envío cada día:
Parte 2: Configurar el problema usando Excel
Solver es un complemento para Microsoft Excel. Se utilizará para optimizar las ganancias de la Compañía X. Si 'Solver' no está en el menú 'Herramientas' en Excel, entonces use los siguientes pasos para habilitarlo:
Para Windows 2007:
- Haga clic en el botón de Office en la esquina superior izquierda de la pantalla. Haga clic en el botón “Opciones de Excel” en la parte inferior derecha del menú.
- Seleccione “Complementos”. Asegúrese de que “Complementos de Excel” esté seleccionado en la lista desplegable “Administrar”. Haga clic en “Ir”.
- Aparecerá una nueva ventana titulada “Complementos”. Seleccione “Complemento de Solver” marcando la casilla. Haga clic en “Ir”.
- Aparecerá una ventana de Configuración. Permitir que Office instale el complemento.
- El solucionador se ha instalado correctamente. (Consulte la Ayuda de Windows para obtener más instrucciones.)
Usa la siguiente figura para configurar tu hoja de cálculo de Excel.
Ingrese en las siguientes fórmulas a las celdas como se muestra a continuación:
Parte 3: Running Solver
- Haga clic en la pestaña “Datos” y seleccione “Solver”. Aparecerá un cuadro de diálogo.
- Ingresa los parámetros como se muestra en la siguiente figura.
Los pasos detallados son los siguientes:
- En “Establecer celda objetivo”, ingrese la celda correspondiente a la ganancia de la compañía (B4).
- Seleccione “Max” en “Igual a”.
- Haga clic en la pestaña “Opciones” y marque la casilla “Asumir modelo lineal”.
- Para “Cambiando Celdas:” seleccione las celdas de la columna B correspondientes a los montos de carga (B9, B10, B11).
- Para agregar restricciones, seleccione “Agregar” en “Sujeto a las restricciones” Se abrirá un cuadro de diálogo.
- En el campo “Referencia de celda:”, ingrese la ubicación de celda del valor de decisión que está sujeto a restricción (es decir, B9).
- Use el menú desplegable en el medio para seleccionar la relación de desigualdad apropiada (es decir, <=)
- En el campo “Restricción:”, ingrese la ubicación de celda del valor de restricción (es decir, D17).
- Continúe haciendo clic en el botón “Agregar”.
- Repita los pasos anteriores hasta que se ingresen todas las restricciones. Luego haga clic en “Aceptar”.
- Cuando se hayan ingresado todos los ajustes adecuados, haga clic en “Resolver”.
- Aparecerá una caja de “Resultados de Solver”. Seleccione “Keep Solver Solution” y haga clic en “Aceptar”.
La hoja de trabajo resuelta está a continuación.
Reporte de Sensibilidad
Escrito por Michael Chisholm y Doug Sutherland, Dic. 2009
El programa solucionador de Excel nos permite analizar cómo cambiaría nuestra ganancia si tuviéramos una alteración en nuestros valores de restricción. Estos valores pueden cambiar debido a una variedad de razones como recursos más fácilmente disponibles, avances tecnológicos, desastres naturales que limitan recursos, etc.
En primer lugar, analiza si las restricciones son vinculantes o no vinculantes. Las restricciones vinculantes limitan la producción de ganancias donde las restricciones no vinculantes no limitan el proceso general. Si se cambiaran las restricciones no vinculantes, el beneficio no se efectuaría siempre y cuando el cambio en estas restricciones se encuentre dentro del incremento y disminución permisibles que se indica dentro del reporte de sensibilidad. Si se modifican las restricciones vinculantes, la ganancia se verá directamente afectada. El efecto sobre la ganancia se muestra con valores de precio sombra, también mostrados en el reporte de sensibilidad. El precio sombra es el aumento o disminución resultante en la ganancia por unidad de aumento o disminución en la restricción. Esto se aplica siempre y cuando el cambio en la restricción permanezca dentro del aumento o disminución permisible donde se pueda asumir una relación lineal.
El precio sombra solo analiza el cambio en una variable a la vez. Para hacer dos, debe tapar el nuevo valor de restricción para una de las variables y resolver usando solver. Utilizando el nuevo reporte de sensibilidad, analice el efecto que tendría el cambio de la segunda variable con el cambio que se realiza en la primera restricción.
Mirando el Ejemplo 1 anterior, ahora recorreremos los pasos sobre cómo crear un reporte de sensibilidad.
Después de hacer clic en “resolver” en excel, aparece un cuadro de diálogo de resultados del solver como se ve a continuación.
Hay una lista de tres opciones a la derecha; respuesta, sensibilidad y límites. Seleccione la opción de sensibilidad antes de hacer clic en Aceptar. Se generará una nueva pestaña en la hoja de trabajo titulada “sensibilidad 1”. A continuación se muestra una vista del informe de sensibilidad dentro de la pestaña. Como puede ver, se generan dos tablas. Para este ejemplo, el recurso A y el producto F no son vinculantes como se muestra con un precio sombra de 0 y un incremento infinito permisible. La disminución permisible es la cantidad que cambia la capacidad hasta alcanzar el valor final. Pasado este punto, la restricción se convertiría en una restricción vinculante. Para las variables restrictivas (recurso B y producto E), sus restricciones son vinculantes. En cuanto al recurso B, si su restricción se incrementara hasta en 5000 o disminuyera hasta en 15000, esto tendría un efecto lineal sobre el beneficio dentro de este rango. Por cada incremento o disminución de unidades, la ganancia cambiará en 12 centavos por unidad, respectivamente. Lo mismo ocurre si nuestra capacidad para el producto E cambia con sus valores permitidos y el precio sombra sobre la mesa.
Si la restricción sobre B aumentara 5,000 lbs, nuestra nueva ganancia sería de $8,600/día (8,000+.12*5,000). En cambio, si nuestra instalación pudiera aumentar la producción de E en 30,000 lb/día, la ganancia resultante sería de $12,950/día (8,000+.165*30,000).
Solución de problemas de optimización lineal utilizando el algoritmo Primal Simplex
Escrito por: Tejas Kapadia y Dan Hassing [Nota: necesita referencia específica, y también la solución al problema anterior por este método sería buena — R.Z.]
En lugar de resolver problemas de optimización lineal utilizando métodos gráficos o informáticos, también podemos resolver estos problemas usando un proceso llamado Algoritmo Simplex Primal. El Algoritmo Primal Simplex parte de una Solución Básica Factible (BFS), que es una solución que se encuentra en un vértice del subespacio contenido por las restricciones del problema. En la Gráfica del Ejemplo 1, este subespacio se refiere a la región sombreada de la parcela. Esencialmente, después de determinar un BFS inicial, el Algoritmo Simplex Primal se mueve a través de los límites de vértice a vértice hasta que se determina un punto óptimo.
El procedimiento básico es el siguiente:
- Encuentra una base de unidad.
- Configurar el problema en forma estándar usando un cuadro canónico.
- Comprobar criterio de optimalidad.
- Si el criterio pasa, entonces deténgase, se ha encontrado la solución.
- Seleccione una variable de entrada entre las variables elegibles.
- Realizar paso de pivote.
- Volver a 1.
Por simplicidad, haremos los siguientes supuestos:
- El óptimo se encuentra en un vértice y no es ilimitado en una media línea extrema.
- Las restricciones son ecuaciones y no también desigualdades.
- En el caso de que las restricciones sean desigualdades, habrá que introducir variables de holgura. Aunque el proceso no es muy diferente en este caso, ignoraremos esto para hacer que el algoritmo sea un poco menos confuso.
- Se requiere que las variables de decisión no sean negativas.
- El problema es un problema de minimización. Para convertir un problema de maximización en un problema de minimización, multiplique la función objetiva por -1 y siga el proceso para resolver un problema de minimización.
Comenzaremos con el siguiente ejemplo:
Función Objetivo: Minimizar\(z=-x_{5}-8 x_{6}\)
Sujeto a las limitaciones:
\ [\ begin {align}
x_ {1} -x_ {5} +x_ {6} &=2\\ [4pt]
x_ {2} +x_ {5} +x_ {6} &=1\\ [4pt] x_ {3} +2 x_ {5}
+x_ {6} &=5\\ [4pt] x_ {4} +x_ {6}
+x_ {6} &=5\\ [4pt] x_ {4} +x_ {6}} &=0\\ [4pt]
x_ {i} &
\ geq 0\ end {align}\ nonumber\]
Primero comenzamos por encontrar una base unitaria:
Un método de acceso directo para encontrar esta base de unidad es poner números para cada variable para que se satisfaga cada ecuación de restricción.
En este caso, establecer
, y
satisfará la ecuación final y también establecerá los valores para
, y
en 2, 1 y 5, respectivamente. Recuerde, estas variables de decisión deben ser no negativas.
Configura el cuadro canónico de la siguiente forma:
Como puede ver, las primeras cuatro filas corresponden a las restricciones, mientras que la fila final corresponde a la función objetiva. La columna “b” corresponde al lado derecho (RHS) de las restricciones. Como puede ver, la columna “-z” está en el lado izquierdo (LHS) de la ecuación, en lugar del RHS.
Primero, debemos realizar pasos de pivote para que el cuadro corresponda a la base unitaria que encontramos anteriormente. Al realizar pasos de pivote en,,
, y, llegaremos al punto factible donde (,,,
, y
) =
. Porque,, y todos iguales a cero, el paso del pivote en realidad se puede hacer en o, pero en este ejemplo, usamos. Estos pasos de pivote se pueden realizar en cualquier fila siempre que sean todas filas diferentes. En este ejemplo, realizamos pasos de pivote en
,
,
usando la herramienta Pivot y Gauss-Jordan en people.hofstra.edu/stefan_waner/realworld/tutorialsf1/scriptPivot2.html. Para utilizar esta herramienta, coloque el cursor sobre la celda sobre la que desea pivotar y presione “pivote”.
Después de cuatro pasos de pivote, el cuadro se verá así:
Como puede ver, esto es idéntico al cuadro inicial, as,,, y se configuraron de tal manera que ya se eligió un punto inicial factible.
El criterio de optimalidad establece que si el vector en la parte inferior izquierda del cuadro es todo positivo, entonces existe una solución óptima en el vector de columna “b”, con el valor en la parte inferior del vector de columna “b” como el negativo del valor de la función objetivo en esa solución óptima. Si esto no es cierto, entonces se debe realizar un paso de pivote. En este ejemplo, claramente, se debe realizar un paso de pivote.
A continuación, tenemos que elegir una variable de entrada. Queremos elegir una variable de entrada que tenga un elemento negativo en la fila inferior, lo que significa que el valor objetivo podría mejorarse si esa variable fuera distinta de cero en la solución. Entonces, elegiremos en este ejemplo. Ahora, debemos calcular las proporciones de cada coeficiente RHS dividido por el coeficiente de la variable entrante en esa fila. En este caso, el vector correspondiente a este cálculo sería igual. No podemos pivotar sobre un elemento cero, así que no podemos pivotar en la cuarta fila. Queremos mantener el RHS positivo, así que no podemos pivotar en la primera fila. Debemos elegir la relación mínima no negativa para quedarnos en una solución factible, por lo que elegimos la segunda fila de la
columna, que tiene una relación de 1/1.
Después del paso de pivote:
Como podemos ver, tiene un coeficiente negativo en la fila inferior, indicando que el mismo paso debe repetirse en esa columna. Calculamos proporciones para esa columna, y obtenemos:. En consecuencia, elegimos pivotar en la cuarta fila porque corresponde a la relación mínima no negativa de 0.
Después de otro paso de pivote:
Debido a que la fila inferior es toda positiva, ahora estamos en una solución óptima. Para entender este cuadro final, miramos en cada columna las variables que solo tienen un “1” en la columna. Si la columna tiene solo un “1”, el valor RHS en esa fila es el valor de esa variable. En este caso,
,
, y
. Cualquier variable que no tenga un solo “1” en la columna es igual a cero. Entonces, la solución óptima es (,,,, y) =
, y el valor óptimo es
(z estaba en el LHS en el cuadro).
Ahora, hemos resuelto con éxito un problema de optimización lineal utilizando el Algoritmo Primal Simplex. La verificación de la solución se puede realizar fácilmente en Microsoft Excel.
Referencias
- D. E. Seborg, T. F. Edgar, D. A. Mellichamp: Dinámica y Control de Procesos, 2ª Edición, John Wiley & Sons.
- Rao, Singiresu S. Optimización de Ingeniería - Teoría y Práctica, 3a Edición, 129-135, John Wiley & Sons.