View
1.838
Download
1
Category
Preview:
Citation preview
Análisis de Sensibilidad
O análisis post optimal
IO1 RDA 2
Análisis de Sensibilidad
Tópicos
Definición
Análisis de sensibilidad de los coeficientes de la F.O. cj
Análisis de sensibilidad vector b
Análisis de sensibilidad de los aij
Adición/Eliminación de una variable
Adición/eliminación de una restricción
IO1 RDA 3
Análisis de Sensibilidad
Se denomina análisis de sensibilidad a las investigaciones que tratan los cambios en la solución óptima debido a los cambios en los datos
El análisis de sensibilidad en cierto sentido convierte la solución estática de P.L. En un instrumento dinámico que evalúa las condiciones cambiantes
IO1 RDA 4
Análisis de Sensibilidad
Objetivo:
Como se ve afectada la solución, si se modifica las condiciones iniciales; esto es hay cambios en los costos, recursos, coeficientes tecnológicos.
Cual es el rango de valores en que se puede trabajar sin afectar la solución.
IO1 RDA 5
Sensibilidad de los coeficientes de la F.O. (Cj)
Sí C C’ ¿cuál será la nueva solución
óptima?
Recordemos que:
(P) max Z=CX (D) min w=Yb
s.a. AX=b s.a. YA C
x>0 Y libre
IO1 RDA 6
Sensibilidad de los coeficientes de la F.O. (Cj)
Que ocurre con las condiciones? Se mantienen?
La condición de factibilidad
si se mantiene, i.e. B es base primal
La condición de optimalidad
no! se
sabe
Pues solamente se cumple para las VB.
01 bBXB
,...,1 ? 0 njzc jj
IO1 RDA 7
Sensibilidad de los coeficientes de la F.O. (Cj)
Entonces sí:
=> sol. óptima
se mantiene
en caso contrário la sol óptima es
afectada => utilizar Simplex para
encontrar la nueva solución
0 Njj Ijzc
IO1 RDA 8
Sensibilidad de los coeficientes de la F.O. (Cj)
Ejemplo:
Sea el tablero óptimo
2
1
82
62 .
23
2
21
21
21
21
x
xx
xx
xxas
xxzmax
38/3- 0 0 4/3- 1/3- 0 0
2/3 1 0 1/3 2/3- 0 0
3 0 1 1 1- 0 0
10/3 0 0 2/3 1/3- 0 1
4/3 0 0 1/3- 2/3 1 0
6
5
1
2
654321
z
x
x
x
x
xxxxxx
IO1 RDA 9
Sensibilidad de los coeficientes de la F.O. (Cj)
Sí se cambia por
la solución permanece óptima?
Solución: Nos interesa calcular solamente
21 45' xxz 21 23 xxz
básicas
básicas no
donde
0 pues 0
B
N
BjjNjj
I
I
IjzcIjzc
IO1 RDA 10
Sensibilidad de los coeficientes de la F.O. (Cj)
Como:
Veamos la Base
1 0 0 1
0 1 1- 1
0 0 2 1
0 0 1 2
B
1 0 1/3 2/3-
0 1 1 1-
0 0 2/3 1/3-
0 0 1/3- 3/2
1B
11 e BCYNBCz BBN
IO1 RDA 11
Sensibilidad de los coeficientes de la F.O. (Cj)
Ahora, con el cambio de coeficientes:
Necesitamos conocer N
0 0
0 0
1 0
0 1
donde de
4,3 6,5,1,2 que dado
N
II NB
)0,0,2,1()0,0,5,4(
)0,0,5,4( )0,0,3,2(
11''
'
BBCY
CC
B
BB
IO1 RDA 12
Sensibilidad de los coeficientes de la F.O. (Cj)
Luego
Cumple con la condición de optimalidad
0)2,1(
)2,1(
0 0
0 0
1 0
0 1
)0,0,2,1()0,0(),( 4433
zczc
IO1 RDA 13
Sensibilidad de los coeficientes de la F.O. (Cj)
Esto es el punto óptimo es el mismo pero el valor de Z varia
En la tabla ahora se tiene:
22)3/4(4)3/10(5
)3/4,3/10( 21
z
xx
22- 0 0 2- 1- 0 0
654321
z
xxxxxx
IO1 RDA 14
Sensibilidad de los coeficientes de la F.O. (Cj)
¿Cuál es el rango de variación de cj
para que la base se mantenga óptima?
ahora:
esto es:
y),.....,....,(' 21 nk ccccC
keCC '
kk cc'
I matriz la dek filaek
IO1 RDA 15
Sensibilidad de los coeficientes de la F.O. (Cj)
1. Sí corresponde a una VNB
Se cumple que:
entonces basta verificar que:
de donde: costo reducido
BC , 0 -1B YKjzc jj
kc
kkk zcc '
kk cz
IO1 RDA 16
Sensibilidad de los coeficientes de la F.O. (Cj)
Ejemplo: Hallar el rango de variación de c3 para que la base siga siendo óptima
Basta mirar el tablero óptimo a nivel de -z y
tomar el valor contrario de c3-z3=-1/3=>
De donde , esto es,
VNBesxc 0 33
3/1
3/13'3 CC 3/1,'
3 C
IO1 RDA 17
Sensibilidad de los coeficientes de la F.O. (Cj)
1. Sí corresponde a una VB, se tiene:
se debe verificar que:
de donde:
0'' NIjjaYjcjzjc
kc
pj
0ypj
0y ymin
ymax
pjpj
jjjj aYcaYc
pfYBpeBCBBCY 1)(1''
deAjcolumnaja
Bfilapf
enkdepos
defilape
1 de P
BI VB . P
I p
IO1 RDA 18
Sensibilidad de los coeficientes de la F.O. (Cj)
Ejemplo: Hallar el rango de variación de c1 para que la base siga siendo óptima
Observe que , , la posición de en la base es 2
=> Según la formula esto corresponde a los valores de y de
=>
y como
VBxC es 3 11
3/1
3/1min
3/2
3/4max
00 pjpj yy
4,3NI 6,5,1,2BI
2423 y , y4433 , zczc
1x
12 41 '11
'1 ccc
IO1 RDA 19
Sensibilidad del vector b
Sí b b’ ¿Cuál es la nueva solución Óptima?
¿Qué ocurre con las condiciones?
Factibilidad: no se sabe
Optimalidad: se mantiene, pues b’ no interviene
=> B es Base dual posible
=> Y es solución dual posible
?0'1 bBXB
0YAC
IO1 RDA 20
Sensibilidad del vector b
Entonces, Sí
=>Sol. Óptima del
problema primal (e Y óptima del dual)
En otro caso solución es afectada
=>aplicar simplex dual para la hallar la solución
0'1 bBXB
IO1 RDA 21
Sensibilidad del vector bEjemplo: que pasa si
Debemos verificar
la base permanece
y ahora
1x
2
1
8
6
b
2
3
8
7
'b
0'1 bBXB
0
0
4
3
2
2
3
8
7
1 0 1/3 2/3-
0 1 1 1-
0 0 2/3 1/3-
0 0 1/3- 3/2
1
bB
13
0,4
3,2
65
12
z
xx
xx
IO1 RDA 22
Sensibilidad del vector b
¿Cuál es el rango de variación de b para que B siga siendo óptima?
En particular para la fila s, tenemos:
0
0''
111'
iBB
iB
XX
eBbBbBX
iebb '
si
B
si
B S
si
S
si
XX
00minmax
1 i
I i
Bcolumna
decolumnae
i
i
IO1 RDA 23
Sensibilidad del vector bEjemplo: rango de variación de b1
b1=6 => vemos en la columna 1 de y para cada fila S = 1, 2,3,4 según fórmula se tiene
=>
1B
2
1
8
6
b
3/2
3
3/10
3/4
BX
1 0 1/3 2/3-
0 1 1 1-
0 0 2/3 1/3-
0 0 1/3- 3/2
1B
3/2
3/4min
3/2
3/2,
1
3,
3/1
3/10max
21
1626 1 b
7'4 1b
IO1 RDA 24
Sensibilidad de los coeficientes aij
Caso en que cambie, que ocurre con la solución solución óptima?
C. de Factibilidad:
se mantiene
C. de optimalidad:
No se sabe
Naij
01 bBXB
?0YNCN
IO1 RDA 25
Sensibilidad de los coeficientes aij
Entonces, dado
Sí,
entonces la solución permanece
caso contrário solución cambia
=> aplicar simplex
Naij
0YNCN
IO1 RDA 26
Sensibilidad de los coeficientes aij Ejemplo:
Sea el tablero óptimo
2
1
82
62 .
23
2
21
21
21
21
x
xx
xx
xxas
xxzmax
38/3- 0 0 4/3- 1/3- 0 0
2/3 1 0 1/3 2/3- 0 0
3 0 1 1 1- 0 0
10/3 0 0 2/3 1/3- 0 1
4/3 0 0 1/3- 2/3 1 0
6
5
1
2
654321
z
x
x
x
x
xxxxxx
IO1 RDA 27
Sensibilidad de los coeficientes aij
Ejemplo: Que pasa si ,
ahora es
=>debemos verificar , como
y , obtenemos
de donde
113 a
033 zc
)0,0,3/4,3/1(1 BCY B
VNBxa 313
03 c
413 a
3/4
0
0
0
4
)0,0,3/4,3/1(33
aYz
03/43/4033 zc
IO1 RDA 28
Sensibilidad de los coeficientes aij
Rango de variación de
la base permanece óptima sí,
esto es:
Pero como
para un j
Naij
0YNCN
Njj IjaYc 0
ijj eaa '
IO1 RDA 29
Sensibilidad de los coeficientes aij
=> el rango de variación de
0
0
i
i
Yi
jj
Yi
jj
Y
aYc
Y
aYc
IO1 RDA 30
Sensibilidad de los coeficientes aij
Ejemplo: rango de variación de
=>nos interesa y la variable dual,
obtenido a partir de
ahora reemplazando, en la formula se tiene:
113 a
33 zc
)0,0,3/4,3/1(1 BCY B
13/1
3/1
VNBxa 313
3/11 Y
0'' 131313 aaa
IO1 RDA 31
Sensibilidad de los coeficientes aij
Caso en que cambie, que ocurre con la solución solución óptima?
La modificación de un elemento de la base afecta las condiciones:
de factibilidad:
de optimalidad (factibilidad dual):
de complementaridad:
Baij
bBXB1
0YNCN
1 BCY B
IO1 RDA 32
Sensibilidad de los coeficientes aij
Rango de variación de
En este caso se calculará el rango de variación respecto a las condiciones de factibilidad y de optimalidad para cada caso particular
Nota: A veces es mejor resolver el nuevo problema generado con el cambio.
Baij
IO1 RDA 33
Adición de una variable
¿Qué posibilidad hay de lanzar un nuevo producto al mercado?
El problema ahora es:
El número de restricciones ha variado?
0,
Zmax
1
11
11
n
nn
nn
xX
bxaAX
xcCX
IO1 RDA 34
Adición de una variable
Como el número de restricciones no varia B tiene el mismo número de VB
esto es: es una base posible
Ahora Sí, B sigue siendo óptimo, debemos de verificar que:
en caso contrário aplicar el Simplex
bBXB1
11 nn aYc
IO1 RDA 35
Adición de una variable
La variable que entra es
Para la tabla simplex es necesario calcular
11
1ny
naB
1nx
IO1 RDA 36
Adición de una variable
Ejemplo: Suponga que se desea añadir una
variable x7,
debemos de verificar que:
Como
11 nn aYc
2
1
8)4/3(2
6)4/3(2 .
)2/3(23 max
2
721
721
721
721
x
xxx
xxx
xxxas
xxxz
)0,0,3/4,3/1(Y )0,1,4/3,4/3(1 na
IO1 RDA 37
Adición de una variable
tenemos
=> Aplicar simplex
Calcular y el nuevo tablero es:
2/34/3
2/3)0(0)1(0)4/3(3/4)4/3(3/1
11
1
nn aBy
4/1
1
4/1
4/1
0
1
4/3
4/3
1 0 1/3 2/3-
0 1 1 1-
0 0 2/3 1/3-
0 0 1/3- 3/2
38/3- 3/4 0 0 4/3- 1/3- 0 0
2/3 1/4- 1 0 1/3 2/3- 0 0
3 1- 0 1 1 1- 0 0
10/3 1/4 0 0 2/3 1/3- 0 1
4/3 1/4 0 0 1/3- 2/3 1 0
6
5
1
2
7654321
z
x
x
x
x
xxxxxxx
IO1 RDA 38
Eliminación de una variable
La eliminación de una variable implica que este tome un valor fijo:
Caso de una VNB
En el óptimo:
como :
kx j
y
)(
BjsjaBB
Njjja
IsxXX
IjxzcZZ
ss
kx
IO1 RDA 39
Eliminación de una variable
se tiene:
entonces, sí:
la base sigue siendo óptima
en otro caso aplicar dual simplex
y)y(
)())((
Bkj
jsjskaBB
Nkj
jjjkka
IsxXX
IjxzczcZZ
ss
0y skBsX
IO1 RDA 40
Eliminación de una variable
Ejemplo: Suprimir es VNB
verificar
4/3 – (2/3) 2 = 0
10/3 –(-1/3) 2 = 12/3 Z= 38/3 +(-1/3)2 =36/3 = 12
3 – (-1) 2 = 5
2/3- (-2/3) 2 =2
0y skBsX
,23 x 3x
38/3- 0 0 4/3- 1/3- 0 0
2/3 1 0 1/3 2/3- 0 0
3 0 1 1 1- 0 0
10/3 0 0 2/3 1/3- 0 1
4/3 0 0 1/3- 2/3 1 0
6
5
1
2
654321
z
x
x
x
x
xxxxxx
IO1 RDA 41
Eliminación de una variable
ahora la tabla óptima queda así:
12- 0 0 4/3- --- 0 0
2 1 0 1/3 --- 0 0
5 0 1 1 --- 0 0
12/3 0 0 2/3 --- 0 1
0 0 0 1/3- --- 1 0
6
5
1
2
654321
z
x
x
x
x
xxxxxx
IO1 RDA 42
Eliminación de una variable Caso de una VB
La eliminación de una variable de la Base, modifica de forma compleja el problema; esto es la base ya no es más base óptima.
Una forma de abordar el problema es hacer que la VB a ser eliminada pase a ser una VNB
IO1 RDA 43
Eliminación de una variable
ejemplo: Suprimir es VB
Forcemos a salir de la base y luego eliminémosla.
,22 x 2x
38/3- 0 0 4/3- 1/3- 0 0
2/3 1 0 1/3 2/3- 0 0
3 0 1 1 1- 0 0
10/3 0 0 2/3 1/3- 0 1
4/3 0 0 1/3- 2/3 1 0
6
5
1
2
654321
z
x
x
x
x
xxxxxx
2x
IO1 RDA 44
Eliminación de una variable
38/3- 0 0 4/3- 1/3- 0 0
2/3 1 0 1/3 2/3- 0 0
3 0 1 1 1- 0 0
10/3 0 0 2/3 1/3- 0 1
4/3 0 0 1/3- 2/3 1 0
6
5
1
2
654321
z
x
x
x
x
xxxxxx
18- 0 0 0 3- 4- 0
2 1 0 0 0 1 0
7 0 1 0 1 3 0
6 0 0 0 1 2 1
4- 0 0 1 2- 3- 0
6
5
1
4
z
x
x
x
x
10- 0 0 0 3- -- 0
0 1 0 0 0 -- 0
1 0 1 0 1 -- 0
2 0 0 0 1 -- 1
2 0 0 1 2- -- 0
6
5
1
4
21
z
x
x
x
x
xx
Haciendo: x2= 2,-4-(-3)2 =26-(2)2=27-(3)2=12-(1)2=0Z= 18+(-4)2= 10Se tiene :
IO1 RDA 45
Adición o eliminación de una restricción Al eliminar una restricción la región factible
queda inalterada o aumenta
La Adición de restriciones hace que la región factible quede inalterada o se reduzca
Efectos sobre la FO.
La adición de una restricción al modelo empeora o no altera el valor de la FO.
La eliminación de una restricción al modelo mejora o no altera el valor de la FO.
Recommended