Optimización de Modelos Lineales

OPTIMIZACIÓN Y SIMULACIÓN PARA LA EMPRESA

Tema 2Programación Lineal

ORGANIZACIÓN DEL TEMA

• Sesiones:

• Introducción, definición y ejemplos

• Propiedades y procedimientos de solución

• Interpretación económica

ORÍGENES DE LA PL• George Dantzig fue el fundador de la Programación Lineal

(PL)

• Desarrolló el método Simplex en 1947

• Algoritmo inteligente que busca la solución óptima entre un conjunto muy reducido de alternativas

• Coincide con el inicio de la informática

• Durante mucho tiempo constituyó el núcleo de la computación científica

ORÍGENES DE LA PL• El primer problema de PL que se resolvió fue el problema de la dieta (9

restricciones y 77 variables)

• Se necesitaron 9 personas trabajando durante 15 días para completar los cálculos del método Simplex

• La primera implementación en ordenador del Simplex se realizó en 1952

• Se pudo resolver un problema de PL de 48 restricciones y 71 variables en 18 horas

• Actualmente se pueden resolver PLs de millones de variables y restricciones en horas o incluso minutos

MODELOS LINEALES: PROPIEDADES

• En un modelo lineal, tanto la función objetivo como las restricciones son funciones lineales de las variables x, a + bTx

• El modelo básico de PL es:

donde c es un vector de n componentes, x es el vector de variables de decisión, A es una matriz m x n y b es un vector de m componentes

• Un vector x que satisface las restricciones se conoce como una solución factible (aunque quizás no sea la solución) o un punto factible

• El conjunto de todas las soluciones factibles es la región factible


• Los PLs se pueden analizar algebraicamente o geométricamente

• Ambos enfoques son equivalentes

• Enfoque algebraico: escribir la representación matemática del PL, por ejemplo,

• Analizar las propiedades matriciales de sus componentes, en nuestro caso


• Enfoque geométrico:

• Analizar la geometría de la región factible

2000 20 40 60 80 100 120 140 160 180

175

0

20

40

60

80

100

120

140

160

x1

x 2

x1≤180

3x1+2x2≤300

2x2≤150

3x1+5x2=3603x1+5x2=480

EJEMPLO 1: DIETA NUTRICIONAL

• Problema clásico

• Descripción:

• Preparar una dieta diaria para un grupo de personas asegurando una ingesta mínima de varios componentes nutricionales (vitaminas, proteínas, calcio, grasas, carbohidratos, etc.)

• Se dispone de n alimentos básicos (huevos, leche, pan, pollo) de donde se obtienen los nutrientes

• Objetivo:

• Diseñar una dieta que garantice una alimentación saludable (mínimo de nutrientes)

• Con coste mínimo


• Datos del problema:

• Alimentos básicos:

• Con costes unitarios c1,…, cn

• Componentes nutricionales:

• Se necesitan al menos b1,…, bm unidades de cada nutriente

• Relación entre alimentos y nutrientes:

• Cada unidad de alimento j contiene aij unidades del nutriente i


• Modelo:

• Variables: encontrar un vector dieta x = (x1,…, xn) que especifique las cantidades de cada alimento a comprar cada día

• Función objetivo: minimizar el coste de la compra de alimentos

• Restricciones: satisfacer requerimientos nutricionales


• Datos:

• Solución: x1 = 3.7209, x2 = 2.0930, coste = 22.7907

• Multiplicadores: 0.0930 (Hidratos de c.), 0 (Proteínas), 0.3023 (Grasas)

AlimentoCarne Patatas Req. diarios

Hidratos de c. 5 15 50Proteínas 20 5 40Grasas 15 2 60

Coste por ración 5 2


• Formulación del problema:

• Variables:

• Cantidades de alimentos básicos en la dieta

• Función objetivo:

• Coste total

• Restricciones:

• Cumplir con los requisitos mínimos de la dieta

• Variables no negativas

min 5x1 + 2x2

5x1 + 15x2 � 50, 20x1 + 5x2 � 40, 15x1 + 2x2 � 60

x1 : carne, x2 : patatas.

120 1 2 3 4 5 6 7 8 9 10 11

10

0

1

2

3

4

5

6

7

8

9

x1

x 2

5x1+15x2≥5020x1+5x2≥40

15x1+2x2≥60

5x1+2x2=50

5x1+2x2=40


• Problema de dieta:

• Región factible

• Función objetivo

EJEMPLO 2: CAMPAÑA DE MARKETING

• Descripción:• Para vender un nuevo producto, una empresa dispone de 100000 euros/semana• El producto se puede publicitar en cuatro medios:

TV, Periódicos, Radio e Internet• Los clientes potenciales captados por cada anuncio y semana, y en cada medio, son:

5000, 8500, 2400 y 2800, respectivamente• El coste semanal de un anuncio en cada medio es:

600, 925, 290 y 380, respectivamente• Cada medio impone unos límites semanales sobre los anuncios a contratar :

30, 60, 60 y 80, respectivamente• ¿Cómo repartir el presupuesto semanal en publicidad para conseguir la mayor

audiencia (potenciales clientes)?


• Modelo:

• Variables: Encontrar, para cada medio, el número de anuncios a contratar por semana, x = (x1, x2, x3, x4)

• Función objetivo: conseguir la máxima audiencia posible

• Restricciones:

• Límites presupuestarios

• Número máximo de anuncios permitido en cada medio

• No negatividad


• Modelo:

• Solución:

• Contratar cada semana 30 anuncios en TV, 60 en Periódicos, 60 en Radio, y 24 en Internet

MODELOS LINEALES: SOLUCIÓN

• Posibles soluciones de un PL:

• Existe una única solución óptima (en un vértice)

• Existen infinitas soluciones óptimas (en aristas, caras o incluso la región factible completa)

• La solución óptima es no acotada

• La región factible es vacía (problema infactible)


• Si un PL es factible y acotado, entonces tiene al menos una solución óptima que estará en un vértice de la región factible• Como el número de vértices de la región es finito, basta con

buscar la solución en ese reducido número de puntos• Esta es la base del algoritmo Simplex:

• Algoritmo computacional basado en un procedimiento iterativo para calcular una solución de los PLs

• Desarrollado por G.B. Dantzig en 1947, marca el origen de la optimización moderna


• Cómo funciona el método Simplex?

1. Encontrar una solución inicial factible (vértice)

• Se puede obtener resolviendo un problema auxiliar más sencillo

2. Comprobar si la solución (vértice) es óptima

• Analizando el cambio en la función objetivo a lo largo de las aristas que se alejan del vértice

3. Si no es óptima, seleccionar la arista con mayor mejora en la función objetivo

4. Moverse, a lo largo de esa arista, al vértice adyacente

5. Repetir 2-4 hasta encontrar una solución óptima (en un número finito de pasos)

• ¿Cómo representar estos pasos en términos algebraicos (programables)?

INTERPRETACIÓN ECONÓMICA DE LA SOLUCIÓN

• Para obtener información útil extra de la solución del problema, necesitamos obtener no solo los valores de la solución, sino también los valores de parámetros asociados

• Multiplicadores de Lagrange

• Nos permiten asignar precios a los recursos y límites de la solución

• Y además entender por qué un conjunto de valores es óptimo

• También podemos realizar un análisis de sensitividad:

• ¿Qué le pasa a la solución si cambiamos algún parámetro (dato) del problema?


• Los precios sombra proporcionan información relevante para el análisis económico de la solución de un PL

• Cada restricción tiene asociado un precio sombra

• Representa el cambio en la función objetivo debido a un cambio unitario en el lado derecho de la restricción

• Se puede entender cómo el valor de una unidad adicional de recurso:

• Si pagamos el precio sombra por esta unidad, nuestro beneficio no cambia

• El método Simplex calcula los precios sombra a la vez que calcula la solución del PL


• Para entender el significado de los precios sombra, consideramos de nuevo el problema de la dieta:

• Cuya solución óptima es:

x1 = 3.7209, x2 = 2.0930, coste = 22.7907

• Con multiplicadores:

0.0930 (Hidratos de c.), 0 (Proteínas), 0.3023 (Grasas)


• Imaginemos que necesitamos proporcionar 51 gramos de hidratos de c., en lugar de 50• El problema a resolver es:

• La nueva solución óptima es:x1 = 3.7116, x2 = 2.1628, coste = 22.8837

• El coste se ha incrementado en 0.093 euros, el precio sombra asociado con la primera restricción


• También disponemos de los precios sombra correspondientes a los requerimientos de proteínas y grasas:

• La dieta óptima recomienda 84.8837 gramos de proteínas, más del doble de la cantidad mínima requerida (40)

• La solución no cambia si incrementamos dicho límite, y su precio sombra es 0

• Si el mínimo requerido de grasas se incrementa hasta 61 gramos, el coste sube a 23.093 euros

• El incremento del coste es 0.3023 euros (que es su precio sombra)


• Para obtener estos valores en Excel, necesitamos llamar a la herramienta Solver

• Una vez obtenemos la solución, seleccionamos ”Sensitividad” en la ventana de diálogo

• Obtenemos una nueva hoja con la información que se muestra:


• Otros valores relevantes en la solución de un PL son los costes reducidos• Un coste reducido se asocia a una variable con valor óptimo 0, o en su cota

inferior• Representa el cambio en la función objetivo cuando la variable pasa a valer 1 (o

una unidad superior que su cota inferior)• Interpretación del coste reducido:

• Coste de empezar una nueva actividad (no llevada a cabo previamente)• Si las variables tienen cotas superiores ub, los costes reducidos se asocian a las

mismas:• Representan el cambio en el objetivo si la variable toma el valor ub + 1,• Representan el beneficio asociado a un incremento unitario en esa variable,

que ya estaba en su nivel máximo


• Para el problema de la campaña de marketing:

• Maximizar audiencia, elegir número de anuncios en cada medio

• Informe obtenido a través de la opción “Sensitividad”:


• De los anteriores valores, se deduce que:• El precio sombra asociado al presupuesto es 7.3684

• Cada euro adicional de presupuesto incrementaría la audiencia en 7.3684 clientes• El número óptimo de anuncios de Internet es 0 < 23,9474 < 80

• Su coste reducido es 0• El óptimo de anuncios en TV está en su cota superior (=30) y su coste reducido es 578.9474

• Cada anuncio adicional incrementaría la audiencia en 578.9474 clientes• El óptimo de anuncios en Periódicos está en su cota superior (=60) y su coste reducido es

1684.2105• Cada anuncio adicional incrementaría la audiencia en 1684.2105 clientes

• El óptimo de anuncios en Radio está en su cota superior (=60) y su coste reducido es 263.1579

• Cada anuncio adicional incrementaría la audiencia en 263.1579 clientes


• Finalmente, también podemos obtener información extra sobre los máximos cambios permitidos en los parámetros que no afectarían a la solución

• En problema dieta, seleccionamos “Sensitividad” y obtenemos:


• Observemos los valores de las columnas “Allowable increase” y “Allowable decrease”

• Para cambios en los parámetros de la función objetivo se tiene:

• El valor del coste de la carne podría subir hasta 5 + 10 y la solución no cambiaría, sí el coste de la dieta (más cara)

• Se podría reducir hasta 5 - 4.33 y la solución no cambiaría

• La solución también se mantendría para precios de patatas en el intervalo [0.67,15]


• Para el lado derecho de las restricciones se tiene:• Los límites de grasa se podrían incrementar hasta 60 + 90 y disminuir hasta 60 - 35.09

sin afectar la solución• Consideremos el caso para el que el límite de grasa se fija en 61. La nueva solución es:

• En este caso, la solución ha cambiado. ¿Por qué?• Qué restricciones están activas en la solución• Qué valores valores toman los multiplicadores de Lagrange

Documents

Optimización de Modelos Lineales