Download - 04 metodo grafico 2
Método Gráfico
Análisis de sensibilidad
IO1 R.Delgadillo 2
Método gráfico
Regiones
Clasificación de problemas PL.
Análisis de sensibilidad.
IO1 R.Delgadillo 3
Regiones
Según sea el conjunto de restricciones del modelo de programación linea, se puede tener los siguientes casos:
Región limitada (cerrada)
Región ilimitada (abierta)
Región vacia
IO1 R.Delgadillo 4
Región limitada
Max 2x1 + 7x2
sujeto a:
3x1 + 4x2 <= 12
x1 + 8x2 <= 8
6x1 + x2 <= 15
x1, x2 >= 0
IO1 R.Delgadillo 5
Región limitada
0 1 2 3
0
1y
x
: 3.0 x + 4.0 y = 12.0
: 1.0 x + 8.0 y = 8.0
: 6.0 x + 1.0 y = 15.0
Payoff: 2.0 x + 7.0 y = 9.6
Optimal Decisions(x,y): ( 2.4, 0.7)
: 3.0x + 4.0y <= 12.0
: 1.0x + 8.0y <= 8.0
: 6.0x + 1.0y <= 15.0
IO1 R.Delgadillo 6
Región ilimitada
Min 50 x1 + 100 x2
Sujeto a:
7 x1 + 2 x2 >= 28
2 x1 + 12 x2 >= 24
x1, x2 >= 0
IO1 R.Delgadillo 7
Región ilimitada
0 1 2 3 4 5 6 7 8 9 10 11 12
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14x2
x1
: 7.0 x1 + 2.0 x2 = 28.0
: 2.0 x1 + 12.0 x2 = 24.0
Payoff: 50.0 x1 + 100.0 x2 = 320.0
Optimal Decisions(x1,x2): ( 3.6, 1.4)
: 7.0x1 + 2.0x2 >= 28.0
: 2.0x1 + 12.0x2 >= 24.0
IO1 R.Delgadillo 8
Región vacia
Min 50 x1 + 100 x2
Sujeto a:
7 x1 + 2 x2 >= 28
2 x1 + 12 x2 >= 24
x1 <= 2.5
x2 <= 5
x1, x2 >= 0
IO1 R.Delgadillo 9
Región vacia
0 1 2 3 4 5 6 7 8 9 10 11 12
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14x2
x1
: 7.0 x1 + 2.0 x2 = 28.0
: 2.0 x1 + 12.0 x2 = 24.0
Payoff: 50.0 x1 + 100.0 x2 = 320.0
Optimal Decisions(x1,x2): ( 3.6, 1.4)
: 7.0x1 + 2.0x2 >= 28.0
: 2.0x1 + 12.0x2 >= 24.0
IO1 R.Delgadillo 10
Ejercicio
Max 3x1 + 2 x2
sujeto a:
1/40 x1 + 1/60 x2 <= 1
1/50 x1 + 1/50 x2 <= 1
x1 >= 30
x2 >= 20
x1, x2>= 0
IO1 R.Delgadillo 11
Tipos de problemas lineales
Se pueden presentar cuatro tipos de problemas lineales según sea su solución
Problemas que admiten una única solución
Problemas que admiten multiples soluciones (óptimas alternativas)
Problemas que no tienen solución (problemas inviables)
Problemas con solución ilimitada.
IO1 R.Delgadillo 12
Tipos de problemas lineales
Problemas que admiten una única solución
Se presenta cuando la región es limitada y la solución cae en un vertice de la región.
IO1 R.Delgadillo 13
Tipos de problemas lineales
Problemas que admiten multiples soluciones (óptimas alternativas)
Se presenta cuando la solución cae en un extremo (lado o rayo) de la región
esto es, todos los puntos (infinitos) que se encuentran en el extremo óptimo hacen máximo (o minímo) el valor de la función
Se presenta cuando la linea de la F.O. Es paralela a una de las restricciones.
IO1 R.Delgadillo 14
Tipos de problemas lineales
Problemas que no tienen solución (problemas inviables)
Se presenta cuando la región que describe el problema es vacio.
Esta clase de problemas se presenta cuando existe incongruencia en los datos y/o especificaciones; o cuando el problema no esta bien formulado.
IO1 R.Delgadillo 15
Tipos de problemas linealesProblemas con solución ilimitada
(Problemas ilimitados).
Se presenta cuando la región es ilimitada y la solución no cae en ningún extremo de la región. Esto es posible encontrar puntos en la región factible con valores de la función objetivo muy grandes (∞ en caso de problema de máx.) o muy pequeños (-∞ en caso de problemas de min)
Se presenta en caso de que la formulación del problema no es correcto.
IO1 R.Delgadillo 16
Tipos de problemas lineales
En Resumen:
Región limitada P.L. solución única
P.L.óptimas alternativas
P.L.solución única
Región ilimitada PL óptimas alternativas
P.L. ilimitado
Región vacia P.L. Inviable.
IO1 R.Delgadillo 17
Análisis de sensibilidad
¿ Qué es análisis de sensibilidad?
Es el estudio del efecto de los cambios en los parámetros del modelo de programación lineal en la solución óptima.
Da al modelo una característica dinámica.
IO1 R.Delgadillo 18
Análisis de sensibilidad
¿ Porqué es importante?
Permite incorporar factores omitidos
Corregir Datos inexactos
Corregir Ingresos y costos inciertos.
IO1 R.Delgadillo 19
Análisis de sensibilidad
Cambios en el coeficiente de la F.O.
Cambiando los coeficientes de la función objetivo se cambia la pendiente de los contornos de esta.
Esto puede o no afectar a la solución óptima y al valor óptimo de la función
IO1 R.Delgadillo 20
Ejemplo.
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
8
9x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 50624.7
Optimal Decisions(x1,x2): ( 4.5, 7.0)
: 1.0x1 + 1.0x2 >= 5.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 160.0
: 30.0x1 + 10.0x2 >= 135.0
5000x1 + 10000x2
4000x1 + 5000x2
5000x1 + 4000x2
IO1 R.Delgadillo 21
Cambio en las restricciones
El cambio en el valor de un lado derecho produce un desplazamiento paralelo de la restricción modificada.
Esto puede afectar tanto a la solución óptima como al valor objetivo. El efecto dependerá precisamente de cuál lado derecho se haya cambiado y en qué medida.
IO1 R.Delgadillo 22
Ejemplo.
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
8
9x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 50624.7
Optimal Decisions(x1,x2): ( 4.5, 7.0)
: 1.0x1 + 1.0x2 >= 5.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 160.0
: 30.0x1 + 10.0x2 >= 135.0
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 49000.0
Optimal Decisions(x1,x2): ( 5.0, 6.0)
: 1.0x1 + 1.0x2 >= 5.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 160.0
: 30.0x1 + 10.0x2 >= 210.0
LD 135 LD 210
IO1 R.Delgadillo 23
Estrechamiento de una restricción
Estrechar una desigualdad significa hacerla más difícil de satisfacer.
Para una restricción >= esto significa aumentar el lado derecho de la desigualdad
Para una restricción <= significa disminuir el lado derecho de la desigualdad
IO1 R.Delgadillo 24
Relajación de una restricción
Relajar una restricción de desigualdad significa hacerla más fácil de cumplir
Para una restricción >= esto significa disminuir el lado derecho
Para una restricción <= significa aumentar el lado derecho de la desigualdad
IO1 R.Delgadillo 25
Efectos sobre la región factible
Al estrechar una restricción de desigualdad, o bien se contrae el conjunto factible o posiblemente quede inalterado.
Al relajar una restricción de desigualdad, o bien se expande el conjunto factible o posiblemente quede inalterado.
IO1 R.Delgadillo 26
Ejemplo
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
8
9x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 50500.0
Optimal Decisions(x1,x2): ( 4.5, 7.0)
: 1.0x1 + 1.0x2 >= 8.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 160.0
: 30.0x1 + 10.0x2 >= 135.0
IO1 R.Delgadillo 27
Restricciones redundantes
Una restricción es redundante si al ser eliminada no cambia la región factible
Es muy posible que una restricción redundante para un conjunto de datos no lo sea cuando se cambian algunos datos.
IO1 R.Delgadillo 28
Ejemplo
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
8
9x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 50500.0
Optimal Decisions(x1,x2): ( 4.5, 7.0)
: 1.0x1 + 1.0x2 >= 5.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 160.0
: 30.0x1 + 10.0x2 >= 135.0
Restricción redundante
IO1 R.Delgadillo 29
Restricciones activas Las restricciones importantes son aquellas
que determinan o definen el conjunto factible.
Dentro de las restricciones importantes las restricciones activa (o limitantes) son aquellas que determinan la solución óptima.
Se determina porque al reemplazar los valores optimos en las restricciones ambos lasdos de la restricción son de igualdad
Las restricciones inactivas (no limitantes) verifican la desigualdad al reemplazarse los valores óptimos.
IO1 R.Delgadillo 30
Ejemplo
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
8
9x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 50500.0
Optimal Decisions(x1,x2): ( 4.5, 7.0)
: 1.0x1 + 1.0x2 >= 5.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 159.4
: 30.0x1 + 10.0x2 >= 135.0
Restricciones Activas
Restricciones inactivas
IO1 R.Delgadillo 31
Adición o eliminación de restricciones
Al eliminar restricciones la región factible queda inalterada o aumenta
La adición restricciones hace que la región factible quede inalterada o se reduzca.
IO1 R.Delgadillo 32
Efecto sobre el valor objetivo
La adición de restricciones en un modelo o bien empeora el valor objetivo o lo deja inalterado.
La eliminación de restricciones en el modelo o bien mejora el valor objetivo o lo deja inalterado.
IO1 R.Delgadillo 33
Ejemplo
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
8
9x2
x1
Payoff: 5000.0 x1 + 4000.0 x2 = 47112.0
Optimal Decisions(x1,x2): ( 3.0, 8.0)
: 1.0x1 + 1.0x2 >= 5.0
: 1.0x1 - 3.0x2 <= 0.0
: 10.0x1 + 15.0x2 <= 150.0
: 20.0x1 + 10.0x2 <= 159.4
: 30.0x1 + 10.0x2 >= 135.0
: 15.0x1 + 10.0x2 <= 125.4
Punto óptimo anterior
Nuevo punto óptimo
Adición de una nueva restricción
IO1 R.Delgadillo 34
Ejercicios
Resolver gráficamente los siguientes modelos
Max 5000 x1 + 3000 x2
S.a: 3 x1 + 5 x2 <= 15
500 x1 + 200 x2 <= 1000
x1 , x2 >= 0
IO1 R.Delgadillo 35
Ejercicios
Max 4 x1 + 4 x2
S.a: -2 x1 + 2 x2 <= 2
- x1 + 2 x2 <= 4
x1 , x2 >= 0
Max 2 x1 + 2 x2
S.a: x1 - x2 <= 2
x1 + x2 >= 4
x1 , x2 >= 0
IO1 R.Delgadillo 36
Ejercicios
Min 3 x1 + 5 x2
S.a: 3 x1 + 2 x2 <= 18
x1 <= 4
x2 <= 6
x1 + 4x2 <= 10
x1 , x2 >= 0