Download Optimización de Modelos Lineales

OPTIMIZACIÓN Y SIMULACIÓN
PARA LA EMPRESA
Tema 2
Programació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)
•
•
La primera implementación en ordenador del Simplex se realizó en 1952
•
•
Se necesitaron 9 personas trabajando durante 15 días para completar
los cálculos del método Simplex
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
T
lineales de las variables x, a + b x
•
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
MODELOS LINEALES:
PROPIEDADES
•
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
MODELOS LINEALES:
PROPIEDADES
Enfoque geométrico:
•
Analizar la geometría de la región factible
175
160
140
3x1+2x2≤300
x1≤180
120
100
x2
•
2x2≤150
80
60
40
3x1+5x2=480
3x1+5x2=360
20
0
0
20
40
60
80
100
x1
120
140
160
180
200
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
EJEMPLO 1:
DIETA NUTRICIONAL
•
Datos del problema:
•
Alimentos básicos:
•
•
Componentes nutricionales:
•
•
Con costes unitarios c1,…, cn
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
EJEMPLO 1:
DIETA NUTRICIONAL
•
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
EJEMPLO 1:
DIETA NUTRICIONAL
•
Datos:
Alimento
Hidratos de c.
Proteínas
Grasas
Coste por ración
Carne
Patatas
Req. diarios
5
20
15
15
5
2
50
40
60
5
2
•
Solución: x1 = 3.7209, x2 = 2.0930, coste = 22.7907
•
Multiplicadores: 0.0930 (Hidratos de c.), 0 (Proteínas), 0.3023
(Grasas)
EJEMPLO 1:
DIETA NUTRICIONAL
•
Formulación del problema:
•
Variables:
•
Cantidades de alimentos básicos en la dieta
x1 : carne,
•
x2 : patatas.
Función objetivo:
•
Coste total
min 5x1 + 2x2
•
Restricciones:
•
Cumplir con los requisitos mínimos de la dieta
5x1 + 15x2
•
Variables no negativas
50,
20x1 + 5x2
40,
15x1 + 2x2
60
MODELOS LINEALES:
PROPIEDADES
Problema de dieta:
10
9
8
7
5x1+2x2=50
6
5x1+2x2=40
x2
•
•
Región factible
15x1+2x2≥60
5
4
3
•
Función objetivo
2
20x1+5x2≥40
1
0
0
1
5x1+15x2≥50
2
3
4
5
6
x1
7
8
9
10
11
12
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)?
EJEMPLO 2:
CAMPAÑA DE MARKETING
•
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
EJEMPLO 2:
CAMPAÑA DE MARKETING
•
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)
MODELOS LINEALES:
SOLUCIÓN
•
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
MODELOS LINEALES:
SOLUCIÓN
•
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
•
•
Nos permiten asignar precios a los recursos y límites de la solución
•
•
Multiplicadores de Lagrange
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?
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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)
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓ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)
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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:
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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”:
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
De los anteriores valores, se deduce que:
•
El precio sombra asociado al presupuesto es 7.3684
•
•
El número óptimo de anuncios de Internet es 0 < 23,9474 < 80
•
•
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
•
•
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 euro adicional de presupuesto incrementaría la audiencia en 7.3684 clientes
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
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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:
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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]
INTERPRETACIÓN ECONÓMICA
DE LA SOLUCIÓN
•
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