Uso de la programación lineal para resolver problemas

¿Por qué utilizar la programación lineal?

La mayoría de las decisiones requieren que consideremos objetivos múltiples, generalmente contradictorios. Por ejemplo, los ingenieros civiles enfrentan decisiones con múltiples objetivos cuando intentan ubicar una carretera para equilibrar los viajes eficientes, la reducción del ruido, la calidad del aire, el costo y la proximidad a las áreas residenciales. Históricamente, el enfoque para encontrar soluciones a problemas multiobjetivo ha sido un análisis de costo-beneficio, donde todos los objetivos se convierten a una moneda común única, generalmente dinero, y luego gana la alternativa con el mayor beneficio.

La optimización multiobjetivo es una alternativa al análisis de costo-beneficio que nos permite analizar decisiones que tienen múltiples objetivos en conflicto sin conversión a una moneda común. La programación lineal (LP) es una forma especial de optimización multiobjetivo, donde los objetivos y las restricciones que describen una decisión se representan mediante ecuaciones lineales, que luego se utilizan para encontrar las mejores (óptimas) soluciones.

Pasos de programación lineal

La programación lineal se puede dividir en siete pasos. Los primeros cinco tratan de definir el problema a resolver, que puede ser más importante que las matemáticas. En los dos últimos pasos, construimos las ecuaciones del programa lineal y las resolvemos. Hagamos un ejemplo sencillo.

Paso 1. Establezca el contexto de decisión:

Definir y limitar el problema a abordar. El ejemplo simple aquí será que queremos un presupuesto de tiempo para nuestras actividades diarias.

Paso 2. Identifique las partes interesadas:

¿Quién debería tener voz en esta decisión? ¿Quién tiene interés en el resultado? Tal vez tu madre quiera ser una de las partes interesadas en esta decisión porque le gusta verte productivo. Pero, centrémonos en usted como único interesado.

Paso 3. Identifique los objetivos:

Haga una lista de los objetivos a alcanzar. Algunos objetivos comunes son minimizar los costos o maximizar la productividad. Aquí, nuestros objetivos son maximizar nuestro nivel de energía y maximizar el tiempo que tenemos para relajarnos. ¡Tenga en cuenta que estos dos objetivos se miden en monedas diferentes!

• La energía ( Z 1 ) se puede medir por la cantidad de calorías disponibles para comer.
• El tiempo para relajarse ( Z 2 ) se mide en una unidad de tiempo, como horas.

Ésta es la belleza de la programación lineal . No necesitamos convertir la energía y el tiempo en una moneda común. Suponga que cada hora de compra de alimentos produce 5 calorías de comida y que cada hora de relajación cuesta 2 calorías. Además, suponga que cada hora que pasa comprando alimentos es una hora que no se puede pasar relajándose y que cada hora que se dedica a buscar sofás produce 4 horas de descanso.

Paso 4. Identifique las variables de decisión:

Los objetivos son lo que se quiere lograr. Las variables de decisión son las variables que podemos controlar para lograr los objetivos. Aquí, solo tenemos que tomar dos decisiones:

1. La cantidad de tiempo para comprar alimentos (esto hace que la energía esté disponible: x 1 ).
2. La cantidad de tiempo que se dedica a buscar sofás (esto hace que haya oportunidades de relajación disponibles: x 2 ).

Paso 5. Identifique las limitaciones:

Siempre hay límites para las alternativas. Para este problema:

• Restricción n. ° 1: las tiendas de alimentos solo abren durante 6 horas
• Restricción n. ° 2: los sofás se vuelven incómodos después de 4 horas
• Restricción n. ° 3: solo hay 8 horas para comprar o buscar sofás en un día
• Restricción n. ° 4: nunca queremos buscar en el sofá más de 3 horas más de lo que compramos alimentos (para no parecer perezosos)

Paso 6. Formule las ecuaciones lineales:

Ahora cree las ecuaciones lineales tanto para los objetivos como para las restricciones.

Los objetivos:

Las limitaciones:

Tenga en cuenta que la última restricción dice que no se permiten valores negativos para las variables de decisión. (No podemos pasar horas negativas comprando comida o buscando sofás).

Paso 7. Encuentre las soluciones óptimas:

El algoritmo que se utiliza para resolver LP se llama Método Simplex y hay muchas herramientas de software disponibles para ello. Las soluciones producidas por el algoritmo del Método Simplex son soluciones óptimas , lo que significa que no existen otras opciones factibles que puedan ofrecer niveles más altos de todos los objetivos. La representación gráfica de nuestro problema de ejemplo es una forma visual de ver las soluciones óptimas generadas por el Método Simplex.

Solución al ejemplo LP

La primera representación visual de las soluciones se denomina Espacio de decisión para el problema LP porque muestra todas las combinaciones de decisiones (tiempo dedicado a buscar sofás versus tiempo a comprar alimentos) que son factibles, dadas las limitaciones. Solo para orientarse:

Espacio de decisión

• El segmento de línea CD muestra la restricción n. ° 1
• el segmento de línea BC muestra la restricción # 2
• el segmento de línea EF muestra la restricción # 3
• el segmento de línea DE muestra la restricción # 4

El área sombreada es el conjunto factible de soluciones, basado en las restricciones.

La segunda representación visual de las soluciones se llama Espacio Objetivo para el problema LP, porque muestra todas las combinaciones de los objetivos (cuánto tiempo podríamos relajarnos frente a cuántas calorías podríamos ganar) que son factibles, dadas las restricciones. .

Espacio objetivo

Nuevamente, el área sombreada es el conjunto factible de soluciones, basado en las restricciones. Las soluciones a lo largo del borde sombreado BCDE son soluciones óptimas . Para entender esto, considere la opción N. No es necesario considerar opciones como N porque podemos obtener más calorías y más descanso eligiendo una alternativa que esté al noreste de N. Pero las soluciones a lo largo de BCDE son óptimas porque es imposible para obtener un nivel más alto de un objetivo sin sacrificar parte del otro objetivo.

Ahora, eche un vistazo a las soluciones óptimas C y D. Usando el espacio de decisión y el espacio objetivo juntos, vemos que si pasamos 6 horas al día comprando alimentos y 2 horas al día buscando en el sofá, obtenemos 26 calorías y 2 horas de relajación ( alternativa C.) Si pasamos 4 horas al día comprando alimentos y 4 horas al día buscando en el sofá, obtenemos 12 calorías y 12 horas de relajación (alternativa D) Podríamos intercambiar 14 calorías por 10 horas más de relajación.

Resumen de la lección

A diferencia del análisis de costo-beneficio, donde los objetivos deben convertirse a una moneda común, como el dinero, la optimización multiobjetivo nos permite analizar decisiones que tienen múltiples objetivos en conflicto sin conversión a una moneda común. La programación lineal es una forma especial de optimización multiobjetivo, donde los objetivos y las restricciones que describen una decisión se representan mediante ecuaciones lineales, que luego se utilizan para encontrar soluciones óptimas.

Rodrigo Ricardo Editor y fundador