Mtodo Simplex
Simplex Tableau
Introduccin
El mtodo simplex como fue descrito anteriormente
resulta muy ineficiente computacionalmente: Muchas
operaciones redundantes y algunas operaciones
computacionalmente costosas como invertir la matrix
B.
La "Simplex Tableau" es una forma de realizar todas
las operaciones del mtodo simplex de forma muy
eficiente.
Simplex Tableau
La estructura general es la siguiente:
Negacin
del valor
ptimo
Reduccin
del costo
-Z
ck - cBB-1Ak
xiB
B-1Ak
Valores
de las
variables
bsicas
xiB
Descripcin
n: Nmero de variables
m: Nmero de restricciones
La "Tableau" tiene n+1 columnas y m+1 filas.
Filas y columnas se numeran desde 0.
Inicializacin
Se debe determinar una base inicial (ms
detalles posteriormente).
Se inicializan las entradas Tij con los valores
correspondientes:
Reduccin de costo en fila 0
Valores de la base inicial columna 0
B-1Ak las columnas k=1..n (cuando B es la matriz
identidad, estas son las mismas columnas de A).
-Z=0
5
Iteracin
Si todas las reducciones de costo son positivas,
terminar.
Seleccionar una xk correspondiente a la columna k
con reduccin de costo negativa para que entre a la
base.
Se calculan las razones xi/xi para la columna k en las
filas con xi>0. La mnima es el valor que toma xk.
Se actualizan los costos reducidos y los componentes
B-1Ak.
6
Actualizacin de la Tablaeu:
Forma cannica
Forma cannica: La submatriz B es la matriz
identidad.
Supongamos que xk entra a la base, y xh sale.
Se divide la fila h por Thk. Esto garantiza que Thk
sea uno.
Para todas las filas ih, se multiplica la fila h
por Tik y se resta de la fila i. Esto hace los
valores Tik=0. (Pivotar)
7
Justificacin fila 0 - (2)
Al llevar a la forma cannica la columna de la variable
z, la fila cero equivale a la ecuacin:
Se observa adems que T0i=0 para i correspondiente
a las variables bsicas, y que xj=0 para las variables
bsicas. Por lo tanto la canolizacin arroja el valor
z=Z
que es solucin de (*), y que por lo tanto corresponde
al negativo del valor ptimo correspondiente a la base
actual.
9
Ejemplo
Retomemos el problema previamente
analizado:
10
Configuracin inicial
La base inicial es {x4, x5, x6}
-Z
x1
x2
x3
x4
x5
x6
-10
x4
10
x5
20
-2
x6
-1
10
(Observar que cB son ceros, por lo tanto las reducciones de costo coinciden con ck)
11
Primera iteracin
T02=-10 es el nico coeficiente que reduce el costo:
Entra x2
Las razones xi/xi correspondientes a k=2 y xi>0 son
10/3 y 20/4. El mnimo es =3.33 y la variable que
sale es x4.
-Z
x1
x2
x3
x4
x5
x6
-10
x4
10
x5
20
-2
x6
-1
10
12
Actualizacin del Tableau
fila1=fila1/3
fila0=fila0-T0k*fila2
fila2=fila2-T2k*fila2
fila3=fila3-T3k*fila2
Base = { x2, x5, x6 }
-Z
x1
x2
x3
x4
x5
x6
33.3
8.33
-1.33
3.33
x2
3.33
0.33
0.67
0.33
x5
6.67
-3.33
-2.67
-1.33
x6
8.33
1.33
10.67
0.33
1
13
Segunda iteracin
Si x3 entra a la base, se reduce el costo.
Las razones xi/xi son 3.33/0.67=5 y 8.33/10.67=0.78.
El mnimo es =0.78 y sale x6.
Se actualizan el Tableau y se obtiene
-Z
x1
x2
x3
x4
x5
x6
34.37
8.5
3.38
0.13
x2
2.81
0.25
0.31
-0.06
x5
8.75
-3.00
-1.25
0.25
x3
0.78
0.13
0.03
0.09
Por lo tanto el valor ptimo es -34.37 y el optimizador es x=(0, 2.81, 0.78, 0, 8.75, 0)
14
Obtencin de una BFS inicial
Cuando se agregan m variables slack
adicionales la eleccin de la base inicial es
trivial. Qu hacer cuando no?
Una solucin general a este problema es el
mtodo de las variables artificiales, o de las dos
fases.
15
Mtodo de las variables artificiales
Fase 1
Se agregan m variables artificiales al Tableau, xia.
Fase 1: Se resuelve el problema minimizando la funcin
16
Mtodo de las variables artificiales
Se pueden presentar 3 casos:
=0 y todas las xia se hacen 0 (se remueven de la base), y la base
restante es una base del problema original.
>0, indicando que el problema original no es factible. Si el
problema original es factible, el mnimo valor de es cero.
=0 pero algunas xia aparecen en la solucin.
Se se da el 1er caso, se borran las columnas correspondientes a xia
(estas variables son ceros), se reemplaza la fila 0 y se continua el
mtodo simplex.
En el 3er caso, se puede "pivotar" una variable original (tal que
xi0) no presente en la base para reemplazar xia. La nueva variable
toma el valor =0, por lo que no afecta el valor de la fila 0.
17
Mtodo de las variables artificiales
Fase 2
Si el problema es factible, la fase 1 siempre
arroja como resultado una BFS para el
problema original con sus valores.
Con esta base se procede a resolver el
problema original.
18
Situaciones Especiales
19
Base Degenerada
Si la columna 0 contiene valores 0, se dice que
la base actual es una base degenerada.
xk
-Z
xi
xi>0
En este caso, xk=0 puede entrar a la base
reemplazando a xi, aunque el punto xn sigue
siendo el mismo.
20
Columna k es negativa
Si todos los valores de xi son negativos,
entonces la variable xk se puede hacer tan
grande como se quiera sin violar ninguna
restriccin.
x
k
-Z
xi
xi<0
En este caso, el espacio factible no est
acotado y se dice que el valor ptimo es -.
21
Solucin Numrica
Matlab Optimization Toolbox ofrece la siguiente
funcin para resolver problemas de
optimizacin lineal:
[x,fval] = linprog(c,A,b,Aeq,beq,lb,ub,x0,options)
Para detalles completos visitar:
[Link]
22
El ejemplo anterior
Asi se puede codificar
A= [ 1
3
2
-2
4
0
1
-1
10 ];
b = [ 10 20 5 ]';
c = [ 5
-10
-8 ];
lb = zeros(3,1);
[x, fval, exitflag] = linprog(c,A,b,[],[],lb)
y retorna el resultado:
x =
0.0000
2.8125
0.7812
fval =
-34.3750
23