Programación lineal: Administración de múltiples objetivos con programación de objetivos

Esta es la (y probablemente la última) parte de una serie de programación lineal que he estado escribiendo. Con los conceptos centrales cubiertos por los artículos anteriores, este artículo se centra en la programación de objetivos, que es un caso de uso de programación lineal (LP) menos frecuente. La programación de objetivos es una configuración de programación lineal específica que puede manejar la optimización de múltiples objetivos en un solo problema de LP.

Al final de este artículo, entenderá:
1. Definición de programación de objetivos y cuándo debe usarse
2. El enfoque de programación de objetivos ponderado, ilustrado con un ejemplo
3. El enfoque de programación de objetivos preventivos, ilustrado con un ejemplo

Definición y caso de uso de la programación de objetivos

La programación de objetivos es un caso especial de programación lineal que permite que los objetivos múltiples, a menudo conflictivos, sean equilibrados. Con problemas de LP regulares, elige una sola métrica para optimizar (minimizar o maximizar) y establecer restricciones para garantizar que la solución óptima sea factible. La programación de objetivos es una técnica que permite que múltiples métricas objetivas sean dirigidas al mismo tiempo.

La 'mentalidad' de la programación de objetivos es fundamentalmente diferente de los problemas de LP de vainilla. LP básico busca formas de obtener tan poco o tanto soltero Métrica como sea posible, por ejemplo, maximizar las ganancias o minimizar los residuos, sujeto a restricciones. A menudo se encontrarán prioridades conflictivas en la función objetivo o las limitaciones. Por ejemplo, maximice la ganancia (objetivo) sujeto a una cantidad máxima de residuos (restricción). Con la programación de objetivos, podemos mover métricas de restricción importantes a la función objetivo para que podamos optimizarlas en lugar de simplemente limitarlas. ¡Podemos maximizar las ganancias y minimizar los desechos al mismo tiempo!

Ahora es un buen momento para establecer el ejemplo que exploraremos para el resto del artículo:

Imaginemos que manejamos una fábrica que hace ropa. Nuestra fábrica puede hacer pantalones, camisas y vestidos. Cada artículo de ropa tiene costos, ganancias y desechos asociados con su producción. Queremos crear un plan de producción que obtenga un cierto nivel de ganancia y también desperdiciará por debajo de una cierta cantidad debido a un compromiso ambiental. Digamos que queremos obtener un mes de $ 150ka en ganancias y también queremos desperdiciar menos de 20k yardas de tela. Además de nuestros objetivos, no podemos gastar más de $ 50k en materiales y mano de obra.

El ejemplo anterior suena muy parecido a un problema de programación lineal regular, ¿verdad? Bueno, el giro es que no podemos obtener $ 150k en ganancias y desperdiciar menos de 20k de yardas al mismo tiempo. En otras palabras, no habría una solución factible si tuviéramos que conectar esto a un problema de programación lineal regular. Por lo general, los objetivos establecidos en los problemas no se pueden lograr con una sola solución, de lo contrario no habría un punto en el uso de la programación de objetivos. Simplemente usaríamos una programación lineal antigua regular con nuestros objetivos como restricciones. El valor real de la programación de objetivos es que puede crear un compromiso entre los objetivos conflictivos cuando la programación lineal regular produciría una solución inviable.

El valor real de la programación de objetivos es que puede crear un compromiso entre los objetivos conflictivos cuando la programación lineal regular produciría una solución inviable.

¿Cómo se equilibra la programación de objetivos y el compromiso con los objetivos conflictivos? Hay dos enfoques populares: (1) ponderado y (2) preventivo. Los cubriremos en detalle en las siguientes secciones.

El enfoque de pesas

Aquí, nos sumergiremos en los detalles del enfoque de pesas. ¡El método de pesas tiene una sola función objetivo y ejecuta una sola optimización basada en (lo adivinó) pesos! El hecho de que solo una optimización se ejecute bajo el método de pesas puede parecer un hecho, pero el método preventivo en realidad ejecuta múltiples optimizaciones de programación lineal. Llegaremos a eso en la siguiente sección …

El método de pesas tiene objetivos o objetivos específicos para múltiples métricas, por ejemplo, gane al menos $ 150k en ganancias vendiendo ropa o no desperdicie más de 20k yardas de tela. Para LP regular, queremos optimizar completamente. Para el método de peso de la programación de objetivos, queremos acercarnos lo más posible a los objetivos de la batalla: después de alcanzar una meta, la optimización no ve más beneficio en una mayor maximización o minimización, por lo que prioriza la llegada del siguiente objetivo más importante. Si esto parece confuso ahora, no se preocupe, tendrá más sentido a medida que entramos en el ejemplo.

El Función de objetivos para el enfoque de pesas está especialmente formulado para minimizar el ponderado Diferencias entre el objetivo de una métrica y el valor real de la métrica. Saltemos a nuestro ejemplo desde arriba: es decir, queremos ganar $ 150k en ganancias y desperdiciar menos de 20k yardas de materia prima. Nuestro objetivo es minimizar qué tan lejos estamos de ambos objetivos.

Aquí está la formulación matemática para este objetivo:

Con nuestra función objetivo configurada, necesitamos definir nuestras restricciones. Tendremos dos tipos de restricciones (1) restricciones relacionadas con el objetivo y (2) restricciones de programación lineal regular (el mismo tipo de restricciones que encontraría en LP de vainilla lisa). Hablemos primero sobre las limitaciones relacionadas con el objetivo.

Tendremos que crear dos cosas para establecer nuestras limitaciones relacionadas con el objetivo, (1) funciones de ganancias y residuos y (2) múltiples variables flojas. Pasemos por estos a la vez.

Las funciones de ganancias y desechos son muy sencillos. Combinan nuestras variables de decisión juntas para calcular las ganancias totales y los desechos totales dan una solución específica. A continuación se muestran las fórmulas que atan ganancias y desechos a la cantidad de pantalones, camisas y vestidos que producimos:

Con nuestras funciones de ganancias y residuos establecidas, comencemos a hablar sobre nuestras variables flojas. En la programación de objetivos, las variables flojas se utilizan para medir qué tan lejos está una solución de alcanzar una meta. En nuestro ejemplo, las variables PAG y W Ambas son variables flojas: representan cuánto más bajo se comparan nuestras ganancias con nuestro objetivo de ganancia y cuánto más alto se compara nuestros desechos con nuestro objetivo de desechos. Las variables flojas están integradas en restricciones. A continuación se presentan las funciones de restricción para nuestros objetivos de ganancias y residuos: nuevamente, el PD y el W son nuestras variables flojas:

Tenga en cuenta que tenemos variables más y menos flojas: esto nos permite perder el objetivo en cada extremo. Solo queremos penalizar la variable floja que va en la dirección opuesta de nuestro objetivo (por ejemplo, no queremos penalizar más ganancias que nuestro objetivo, solo queremos penalizar menos Beneficio) – Por eso solo una variable floja por objetivo está en la función objetivo. Con esta nueva notación, reescribamos nuestra función objetivo:

Ahora hemos realizado todo el trabajo especial para la programación de objetivos. Lo último que debemos hacer es agregar rápidamente nuestra limitación de presupuesto de vainilla. Estamos utilizando una restricción regular para nuestro presupuesto porque, en nuestro ejemplo, es una restricción difícil. A diferencia de las ganancias y el desperdicio, no podemos violar el presupuesto.

Ahora, tenemos un problema de programación de objetivos totalmente especificado. ¡Vamos a configurarlo en Python y resolver!

# $150,000 in profit
problem += profit + profit_deviation_neg - profit_deviation_pos == 150000, "Profit_Goal"

# Waste goal: No more than 20,000 yards of waste
problem += waste + waste_deviation_neg - waste_deviation_pos == 20000, "Cost_Goal"

# Budget constraint
problem += cost <= 50000

# Solve the problem
problem.solve()

# Display the results
print("Status:", pulp.LpStatus(problem.status))
print("Pants produced:", pulp.value(pants))
print("Shirts produced:", pulp.value(shirts))
print("Dresses produced:", pulp.value(dresses))
print("Cost :", pulp.value(cost))
print("Profit :", pulp.value(profit))
print("Profit deviation (positive):", pulp.value(profit_deviation_pos))
print("Profit deviation (negative):", pulp.value(profit_deviation_neg))
print("Waste :", pulp.value(waste))
print("Waste deviation (positive):", pulp.value(waste_deviation_pos))
print("Waste deviation (negative):", pulp.value(waste_deviation_neg))

Esta optimización recomienda que hagamos 0 pantalones, 5,000 camisas y 0 vestidos. Ganamos $ 150k en ganancias que coinciden exactamente con nuestro objetivo y desperdiciamos 50k yardas de tela que excede nuestros desechos máximos en 30k yardas. Los resultados completos se imprimen por el código y se muestran a continuación:

Ahora que tenemos la estructura básica del enfoque de los pesos, hablemos realmente de la pesas! En nuestro primer ejemplo, dimos el mismo peso a un dólar de ganancias y un patio de desechos. Esto probablemente no tenga mucho sentido porque son unidades diferentes. Establecer los pesos es una decisión subjetiva para ser tomada por el practicante. Para nuestro ejemplo, decidiremos que perder 1.5 yardas de tela es tan malo como ganar $ 1 de ganancias es bueno. En otras palabras, aumentaremos el peso de los desechos de tela a 1.5 en nuestra función objetivo.

problem += profit_deviation_neg + 1.5*waste_deviation_pos

La optimización con las tarifas actualizadas recomienda que hagamos alrededor de 8,572 pantalones, 7,143 camisas y 0 vestidos. Con esta solución, generamos $ 107k en ganancias (que es una falta de $ 43k) y desperdiciamos 20,000 yardas de tela que coinciden exactamente con nuestro objetivo. Los resultados completos se imprimen por el código y se muestran a continuación:

Claramente, cambiar los pesos de los objetivos puede tener un gran impacto en los resultados de la optimización. ¡Necesitamos establecer cuidadosamente nuestros pesos para equilibrar adecuadamente la importancia relativa de nuestros objetivos!

Ahora que tenemos una sólida comprensión de cómo funciona el enfoque ponderado, cambiemos a hablar sobre la programación de objetivos con el enfoque preventivo.

Enfoque preventivo

Si bien el método de pesas equilibra los objetivos utilizando pesos en la función objetivo, el método preventivo da prioridad jerárquica a los objetivos a través de optimizaciones iterativas. Eso es muchas palabras, no te preocupes, ¡lo desglosaremos!

Estos son los pasos para el enfoque preventivo:

1. Ejecute una optimización de programación lineal regular en su primer objetivo: por ejemplo, maximizar las ganancias
2. Guarde el valor objetivo de esa ejecución
3. Ejecute otra programación lineal regular sobre el siguiente objetivo más importante, por ejemplo, minimice los desechos, pero agregue el valor objetivo de la última ejecución como una restricción
4. Repita el proceso hasta que haya pasado por todas las métricas de objetivos

Dos características importantes del método preventivo son (1) prioriza los objetivos por rango y (2) el valor objetivo de un objetivo de mayor importancia no puede disminuir (debido a la restricción dura) al optimizar los objetivos de menor prioridad. Pasemos un ejemplo para construir intuición.

Para nuestro ejemplo, digamos que la ganancia es el objetivo más importante y minimizar el desperdicio es el segundo. Comenzaremos ejecutando una optimización simple de vainilla que maximice las ganancias:

# Define the problem
problem = pulp.LpProblem("Clothing_Company_Goal_Programming", pulp.LpMaximize)

# Decision variables: number of pants, shirts, and dresses produced
pants = pulp.LpVariable('pants', lowBound=0, cat='Continuous')
shirts = pulp.LpVariable('shirts', lowBound=0, cat='Continuous')
dresses = pulp.LpVariable('dresses', lowBound=0, cat='Continuous')

# Profit and cost coefficients
profit = 10 * pants + 3 * shirts + 15 * dresses
cost = 5 * pants + 1 * shirts + 10 * dresses
waste = 1.5 * pants + 1 * shirts + 3 * dresses

# Objective function: Maximize profit
problem += profit

# Constraints
# Budget constraint
problem += cost <= 50000

# Solve the problem
problem.solve()

# Display the results
print("Status:", pulp.LpStatus(problem.status))
print("Pants produced:", pulp.value(pants))
print("Shirts produced:", pulp.value(shirts))
print("Dresses produced:", pulp.value(dresses))
print("Cost :", pulp.value(cost))
print("Profit :", pulp.value(profit))

Los resultados del problema de maximización de ganancias LP están a continuación:

Entonces, nuestra función objetivo dice hacer 50k camisas y recoger una ganancia de $ 150k. ¡Esta fue solo la primera optimización que vamos a ejecutar! Después del algoritmo descrito anteriormente, ahora ejecutaremos otro LP que minimiza los desechos, pero agregaremos una restricción de ganancias ≥ $ 150k para garantizar que no obtengamos una ganancia peor.

# Define the problem
problem = pulp.LpProblem("Clothing_Company_Goal_Programming", pulp.LpMinimize)

# Decision variables: number of pants, shirts, and dresses produced
pants = pulp.LpVariable('pants', lowBound=0, cat='Continuous')
shirts = pulp.LpVariable('shirts', lowBound=0, cat='Continuous')
dresses = pulp.LpVariable('dresses', lowBound=0, cat='Continuous')

# Profit and cost coefficients
profit = 10 * pants + 3 * shirts + 15 * dresses
cost = 5 * pants + 1 * shirts + 10 * dresses
waste = 1.5 * pants + 1 * shirts + 3 * dresses

# Objective function: Minimize the fabric waste
problem += waste

# Budget constraint
problem += cost <= 50000

problem += profit >= 150000

# Solve the problem
problem.solve()

# Display the results
print("Status:", pulp.LpStatus(problem.status))
print("Pants produced:", pulp.value(pants))
print("Shirts produced:", pulp.value(shirts))
print("Dresses produced:", pulp.value(dresses))
print("Cost :", pulp.value(cost))
print("Profit :", pulp.value(profit))

Y aquí están los resultados de esta optimización final:

El astuto observador notará que la optimización es exactamente la misma . Este a menudo puede ser el caso con el método preventivo. La restricción de objetivos previamente optimizados puede ser muy restrictiva. El único momento en que las optimizaciones iterativas son diferentes es si hay múltiples formas de obtener los valores óptimos para objetivos anteriores. Por ejemplo, si hubiera dos formas de obtener $ 150k en ganancias; Uno tenía más desechos y el otro tenía menos, nuestra segunda iteración devolvería los resultados de la solución con los desechos más bajos. En el método preventivo, no hay compensación entre los objetivos. Incluso si hubiera una solución que obtuviera $ 149K en ganancias con 0 yardas de desechos, el método preventivo siempre elegiría $ 150k en ganancias con 50k yardas de desechos. Los $ 1000 adicionales de ganancias son infinitamente más importantes que cualquier cantidad de tela desperdiciada.

El método preventivo debe usarse cuando los objetivos se priorizan claramente, y no hay sustitución entre ellos, lo que significa que ninguna cantidad de éxito en los objetivos de menor prioridad puede compensar la optimización reducida en las de mayor prioridad. Cuando se usa correctamente, el método preventivo puede ayudar a optimizar un objetivo primario al intentar encontrar buenas soluciones para objetivos de menor prioridad de manera muy efectiva.

Conclusión

La programación de objetivos proporciona un marco que extiende la programación lineal tradicional para optimizar múltiples métricas al mismo tiempo. El enfoque ponderado equilibra las prioridades a través de los pesos en la función objetivo y es apropiado cuando las métricas objetivas tienen una importancia relativa que se puede cuantificar. El método preventivo es un enfoque iterativo que da prioridad a las métricas basadas en la jerarquía. Es apropiado cuando algunos objetivos son totalmente más importantes que otros. ¡Ambos enfoques pueden ser técnicas de optimización potentes cuando se aplican en el contexto correcto!

¡Feliz optimización!

Artículos anteriores de esta serie: