Story Transcript
Tema 3: El M´etodo Simplex. Algoritmo de las Dos Fases. 3.1 Motivaci´ on Gr´ afica del m´etodo Simplex. 3.2 El m´etodo Simplex. 3.3 El m´etodo Simplex en Formato Tabla. 3.4 Casos especiales en la aplicaci´ on del algoritmo. 3.4.1 Degeneraci´ on. ´ 3.4.2 Optimos alternativos. 3.4.3 Problema no acotado. 3.4.4 Problema Imposible. 3.5 El Algoritmo de las dos Fases. 3.5.1 Problema imposible. 3.5.2 Problema posible. 1
3.1 Motivación Gráfica del Método Simplex Región de soluciones posibles acotada Existe al menos una solución óptima, que es un vértice
Región de soluciones posibles no acotada Problema no acotado
z=+ ∞
c, dirección de mejora
Problema Acotado Existe una solución óptima única
Problema acotado
Infinitas soluciones óptimas (Segmento)
c, dirección de mejora
Problema acotado
Infinitas soluciones óptimas (Semirrecta)
c, dirección de mejora
3.1 Motivaci´on Gr´afica del M´etodo Simplex 1. Si el PPL tiene una u ´nica soluci´ on ´ optima, ser´ a necesariamente un v´ertice de S. 2. Si el PPL tiene m´ as de una soluci´ on ´ optima y S es acotado, al menos dos de ellas son v´ertices adyacentes de S. Si S es no acotada, solo podemos garantizar que al menos una de las soluciones ´ optimas es un v´ertice. 3. Existe un n´ umero finito de v´ertices en S. 4. Si un v´ertice proporciona un valor objetivo mejor o igual que el resto de v´ertices adyacentes entonces proporciona un valor objetivo mejor o igual que cualquier otra soluci´ on posible del problema, luego es una soluci´ on ´ optima para el problema.
2
E
+
D
+
H1
=
10
−E
+
D
+
H2
=
1
D
+
H3
=
4
Si hacemos H1 = H2 = 0, nos queda: E
+
D
=
10
−E
+
D
=
1
=
4
D
+
H3
cuya soluci´ on es: E = 9/2, D = 11/2, H3 = −3/2
No puede ser soluci´ on del PPL incumple la restricci´ on de no negatividad.
3
( E,
D,
H1 ,
H2 ,
H3 )
0
0
10
1
4
(0,0) Soluci´ on posible
0
10
0
-9
-6
(0,10) no es soluci´ on posible
0
1
9
0
3
(0,1) Soluci´ on posible
0
4
6
-3
0
(0,4) no es soluci´ on posible
10
0
0
11
4
(10,0) Soluci´ on posible
?
0
?
?
0
Sistema Incompatible
-1
0
11
0
4
(-1,0) no es soluci´ on posible
9/2
11/2
0
0
-3/2
6
4
0
3
0
(6,4) Soluci´ on posible
3
4
3
0
0
(3,4) Soluci´ on posible
(9/2,11/2) no es soluci´ on posible
4
´ mo obtener los ve ´rtices Co del conjunto de soluciones de un PPL Para un problema cuya forma est´andar incluya un sistema de m ecuaciones linealmente independientes y n inc´ognitas, los v´ertices del poliedro se obtienen resolviendo los sistemas de m ecuaciones con m inc´ognitas que resultan al igualar a cero subconjuntos de n − m variables. Solo ser´an soluciones posibles (v´ ertices) aqu´ellos puntos cuyas variables, tanto de holgura como originales sean no negativas.
5
3.2 El M´etodo Simplex Desarrollado por George Dantzig en 1947. Primera aplicaci´ on importante: J. Laderman resolvi´ o un problema de elaboraci´ on de una dieta en la que hab´ıa 9 restricciones de igualdad y 27 variables. Necesit´ o ´el trabajo de 120 d´ıas-hombre. Dado un PPL expresado en forma est´ andar con m ecuaciones y n inc´ ognitas, m ≤ n, podemos dividir las variables en dos grupos: 1. n − m variables a las cu´ ales les damos el valor 0, y que denominaremos variables no b´ asicas. 2. m variables cuyo valor se determinar´ a resolviendo el sistema de m ecuaciones y m inc´ ognitas resultante de igualar a cero el resto de variables. Si dicho sistema tiene una u ´ nica soluci´ on, diremos que las m variables son variables b´ asicas. Soluci´ on del sistema −→ soluci´ on b´ asica Si adem´ as las variables ≥ 0 −→ soluci´ on posible b´ asica 6
´ n algebra ´ ica Formalizacio PPL
Min
z = ct x
s.a.:
Ax = b x ≥ 0n
B := {columnas de A de coeficientes de las variables b´ asicas} N := A \ B := { columnas de A coeficientes de las variables no b´ asicas} xB cB , c= A = (B, N ), x = xN cN Min
z
s.a.:
z−
ctB xB − ctN xN = 0 BxB + N xN = b xB ≥ 0, xN ≥ 0
7
B −1 (BxB + N xN ) = B −1 b ↓ (B −1 B)xB + (B −1 N )xN = B −1 b ↓ xB + (B −1 N )xN = B −1 b ¯b1 . .. ¯b := B −1 b = ¯bi , yj := B −1 aj . . . ¯bm ¯bi := valor de la variable b´ asica asociada a la ecuaci´ on i-´esima yij := coeficiente de la variable no b´ asica j-´esima en la ecuaci´ on i-´esima 8
z = ctB xB + ctN xN ↓ xB = B −1 b − (B −1 N )xN ↓ z = ctB (B −1 b − (B −1 N )xN ) + ctN xN ↓ z=
ctB (B −1 b) − (ctB B −1 N − cN ) xN | {z } | {z } valor objetivo costes reducidos
9
En cualquier iteraci´on del Simplex el problema est´a expresado como: Min z = ctB (B −1 b) − (ctB B −1 N − cN )xN xB + B −1 N xN = B −1 b xB ≥ 0 xN ≥ 0 Y tiene asociada la siguiente Soluci´on Posible B´asica: xB B −1 b x= = xN 0 Cuyo valor objetivo es: z = ctB (B −1 b)
10
Costes Reducidos: coeficientes de las variables en la expresi´on de la funci´ on objetivo dada en una iteraci´on del Simplex. Variable B´asica: 0 Variable No B´asica: zj − cj := ctB B −1 aj − cj Importancia: Criterio de Optimalidad: una soluci´ on es ´ optima sii zj − cj ≤ 0 ∀j. ´ sica: aqu´ella que Criterio para Elegir la Nueva Variable Ba tiene el mayor coste reducido. znuevo := zactual − (zj − cj )xj
Si xj > 0 y zj − cj > 0 → znuevo < zactual Si xj > 0 y zj − cj < 0 → znuevo > zactual 11
Algoritmo del Simplex Consideremos el Problema de Programaci´ on Lineal: PL
Min
z = ct x
s.a.:
x∈S
en donde, S 6= ∅. Inicializaci´ on Escr´ıbase el Problema de Programaci´ on Lineal en forma est´ andar. Sea PL
Min
z = ct x
s.a.:
Ax = b x ≥ 0n
el problema resultante. En donde, A es una matriz m × n, b ∈ IRm , c ∈ IRn , rango(A, b) = rango(A) = m (es decir, sistema compatible, tiene soluci´ on). 12
Obtener una Soluci´ on Posible B´ asica Inicial (SPB) Si en S todas las restricciones eran del tipo “≤” y el “rhs ≥ 0”, al a˜ nadir las variables de holgura se obtiene autom´aticamente una SPB tomando las variables originales como no b´asicas y las variables de holgura como b´asicas. en otro caso aplicaremos el algoritmo de las dos fases. Sea B la submatriz de A formada por las columnas asociadas a las variables b´asicas y N el conjunto de ´ındices de las variables no b´asicas. xB := B −1 b ≥ 0m xN := 0n−m
13
Iteraci´ on Paso 1: Sea, xB = B −1 b, y xN = 0n−m , la SPB actual. Hacer, ¯b = B −1 b, y z = ct xB . Ir al Paso 2. B Paso 2: Calcular los costes reducidos de las variables no b´asicas. zj − cj = ctB B −1 aj − cj , ∀j ∈ N siendo aj la columna asociada a la variable xj en A. a) Si zj − cj ≤ 0, ∀j ∈ N , Stop. x∗B := B −1 b y x∗N := 0n−m z ∗ = ctB B −1 b. b) En otro caso, elegir xk como nueva variable b´asica entrante, siendo k el ´ındice para el que se alcanza el m´aximo de los costes reducidos, zk − ck = m´ax{zj − cj }. j∈N
Ir al Paso 3. 14
Paso 3: Obtener la columna asociada a la variable que se hace b´asica en el sistema actual. Sea yk := B −1 ak a) Si yk ≤ 0m , Stop. Podemos incrementar el valor de xk tanto como queramos sin que se haga cero ninguna variable b´asica i.e., sin alcanzar ning´ un otro v´ertice del poliedro adyacente al actual. El problema es No Acotado y el valor ´optimo es z ∗ = −∞. b) En otro caso. Ir al Paso 4. Paso 4: Elegir la variable que deja de ser b´asica (Criterio de la raz´on m´ınima). ¯br ¯bi = m´ın { : yik > 0} 1≤i≤m yrk yik B := B \ {ar }
S
{ak }, N := N \ {k} 15
S
{r}. Ir al Paso 1.
3.3 El M´etodo Simplex en Formato Tabla Dado el PPL, Min z = ct x
Min z
s.a.:
s.a.: Ax = b
−→
x ≥ 0n
z − ct x = 0 Ax = b x ≥ 0n
Si lo escribimos en t´erminos de una SPB asociada a una base B: Min z s.a.:
z − ctB xB − ctN xN = 0 BxB + N xN = b xB ≥ 0m , xN ≥ 0n−m 16
xB = B −1 b − B −1 N xN , z+ 0xB
+
(ctB B −1 N − ctN )xN
xB
+
B −1 N xN
xB
z
1
0
xB
0
Im
xN
= ctB B −1 b = B −1 b RHS
ctB B −1 N − ctN (zj − cj = ctB B −1 aj − cj )
B −1 N , (yk = B −1 ak )
17
ctB B −1 b
B −1 b, (¯bi )
Fila 0 z = ctB B −1 b
Fila 1-m xB = B −1 b
Tabla antes de pivotar xB1
...
xBr
...
xBm
...
xj
...
xk
...
RHS
z
0
...
0
...
0
...
zj − c j
...
zk − ck
...
cB ¯b
xB1 . ..
1 . ..
...
0 . ..
...
0 . ..
...
y1j . ..
...
y1k . ..
...
xBr . ..
0 . ..
...
1 . ..
...
0 . ..
...
yrj . ..
...
yrk . ..
...
¯b1 . .. ¯br
xBm
0
...
0
...
1
...
ymj
...
ymk
...
Variable de entrada, zk − ck = m´ ax{zj − cj } −→ xk j∈N
¯br ¯bi Variable de salida, = m´ın { : yik > 0} −→ xBr 1≤i≤m yik yrk
18
. .. ¯bm
Tabla despu´ es de pivotar xB1
. . . xBr . . .
xBm
. . . xj . . .
ck −zk yrk
. . . (zj − cj ) - y rj (zk − ck ) . . .
z
0
...
...
0
xB1
1
. . . − yy1k . . .
0
.. .
.. .
.. .
.. .
xk
0
.. .
.. .
.. .
.. .
xBm
0
. . . − yymk . . .
1
rk
...
1 yrk
rk
...
0
xk . . .
y
rk
. . . y1j −
yrj y yrk 1k
...
.. . ...
yrj yrk
...
1 ...
rk
¯b1 −
S
... {ak }
0 ...
y1k ¯ b yrk r
.. . ¯ br yrk
.. .
yrj y yrk mk
Nueva Base B = B \ {ar } 19
0 ...
¯
cB ¯b − (zk − ck ) ybr
.. .
.. . . . . ymj −
0 ...
RHS
.. . ¯bm −
ymk ¯ b yrk r
3.4 Casos especiales en la aplicaci´on del algoritmo. ´ ´ Ejemplo: Optimo Unico Min
−3x1 + x2
sa:
x1 + 2x2 + x3 = 4 −x1 + x2 + x4 = 1 xi ≥ 0, ∀i = 1, 2, 3, 4
Dada,
B = {a1 , a4 } =
1
0
−1
1
−→ B −1 b =
ctB = (−3, 0) zj − cj = ctB B −1 aj − cj =
4 5
−→ xt = (4, 0, 0, 5)
1 z2 − c2 = (−3, 0) 1 1 z − c = (−3, 0) 3 3 1
20
0
1
2 1
0 1
− 1 = −7
1 0
− 0 = −3
´ Ejemplo: Optimos Alternativos Min
−2x1 − 4x2
sa:
x1 + 2x2 + x3 = 4 −x1 + x2 + x4 = 1 xi ≥ 0, ∀i = 1, 2, 3, 4
Dada,
B = {a1 , a4 } =
1
0
−1
1
−→ B −1 b =
ctB = (−2, 0) zj − cj = ctB B −1 aj − cj =
4 5
−→ xt = (4, 0, 0, 5)
1 z2 − c2 = (−2, 0) 1 1 z − c = (−2, 0) 3 3 1
¢¤ £ ¡ ´ Optimos: (4, 0, 0, 5), 32 , 53 , 0, 0 , z ∗ = −8 21
0
1
2 1
0 1
− (−4) = 0
1 0
− 0 = −2
´n Ejemplo: No Acotacio Min
−x1 − 3x2
sa:
x1 − 2x2 ≤ 4 −x1 + x2 ≤ 3 x1 ≥ 0, x2 ≥ 0
Dada, B = (a2 , a3 ), B −1 =
0
1
1
2
−→ B −1 b =
0 z − c = (−3, 0) 1 1 1 zj − cj ==
0 z − c = (−3, 0) 4 4 1
22
3
−→ xt = (0, 3, 10, 0)
10
1
2
1 −1
1 2
− (−1) = 4> 0
0 1
− 0 = −3
“x1 podr´ıa entrar en la base” Sin embargo, como
y1 = B −1 a1 =
−1 −1
≤ 02
“Ninguna variable cumple el criterio de salida” ct
1 1 = (−1, −3, 0, 0) on < 0 −→ Criterio de No Acotaci´ 1 0
−y1 e1
El problema es No acotado a lo largo de la semirrecta: 1 0 3 1 l´ım z = 9 − 4x1 = −∞ x1 , x1 ≥ 0 , + x − →−∞ 1 10 1 0 0
23
3.5 El Algoritmo de las Dos Fases Escr´ıbase el PPL en forma est´ andar: Min
z = ct x
s.a.:
x∈S
−→
Min
z = ct x
s.a.:
Ax = b x ≥ 0n
En donde A es una matriz m × n de rango completo por filas. Si A contiene una submatriz identidad m × m y b ≥ 0m B = Im y N = A \ B permiten definir una SPB inicial para aplicar el algoritmo del Simplex: xB = B −1 b y xN = 0n−m En otro caso, A se completa con tantas columnas (variables artificiales) como sea necesario para conseguir dicha situaci´ on, y se aplica el algoritmo de las 2 fases. 24
Fase 1: Construir el problema auxiliar resultante de a˜ nadir las variables artificiales: Min z = ct x →
Min z = 1t xa
s.a.:
s.a.:
Ax = b x≥0
Ax + xa = b x, xa ≥ 0
Resolver el problema auxiliar con el algoritmo del Simplex. Sea (x∗ , x∗a ) la soluci´on ´optima. Si x∗a = 0
−→
Ir a la Fase 2.
Si x∗a 6= 0
−→
Problema original Imposible
25
Fase 2: Utilizar la SPB obtenida al final de la Fase 1 para resolver el problema inicial. Sean xB las variables b´asicas en dicha soluci´on. Consideremos la tabla ´optima al final de la Fase 1. Si en xB no hay variables artificiales: eliminando las columnas asociadas a las variables artificiales y actualizando convenientemente la fila asociada a la funci´on objetivo obtenemos la tabla inicial para resolver el problema original con el algoritmo Simplex. Si en xB hay variables artificiales: tratamos de obtener una SPB sin variables artificiales.
26
¿C´omo? 1. Eliminar de la tabla las columnas asociadas a las variables artificiales no b´asicas. 2. Actualizar la fila asociada a la funci´on objetivo considerando que los coeficientes en la funci´on objetivo de las variables artificiales en el problema original son 0. 3. Eliminar secuencialmente variables artificiales b´asicas pivotando sobre elementos de la tabla yij 6= 0, en donde: i := fila asociada a la variable b´asica artificial j := columna asociada a la variable no artificial Si yij = 0, ∀j 6= i la ecuaci´on i-´esima es redundante. Eliminar la ecuaci´on y la variable artificial.
27
Óptimo
3x1 + x2 = 3
Fase1
x1 + 2x2 ≤ 4 4x1 + 3x2 ≥ 6