Mtodo Simplex Dual

Mtodo Simplex Dual
Prof. Fernando Augusto Silva Marins

Departamento de Produo
Faculdade de Engenharia Campus de Guaratinguet
UNESP
www.feg.unesp.br/~fmarins
[email protected]
1
Pesquisa Operacional Aplicada Produo - UNESP / Campus de Guaratinguet
Introduo
Algoritmo proposto por C. E. Lemke baseando-se em observaes
da aplicao do Mtodo Simplex (Primal) tradicional ao Dual de um
modelo de Programao Linear.
til em algoritmos de programao inteira, algoritmos de
Programao No-linear, e Algoritmos Primais-Duais.
Pode ser til como alternativa ao Mtodo das Duas Fases ou do Big
M para inicializao do Mtodo Simplex Primal .
til para alguns casos que ocorrem na Anlise de Sensibilidade e
na Programao Paramtrica.
2
Observaes
1. Sabe-se que o vetor formado pelos coeficientes de custo relativo na
aplicao do Simplex Primal, dado por (onde
o vetor dos multiplicadores do Simplex) independe do vetor de
constantes das restries, dado por b.
2. Em geral, para um modelo de Minimizao, nem toda Soluo Bsica que
tenha ser vivel (isto , satisfaz as restries), mas qualquer
Soluo Bsica Vivel com ser uma soluo tima para o
modelo sob anlise.
C = C - A
= C B
B
-1
C 0
C 0
3
Idia do mtodo:
Iniciar com alguma soluo bsica, no vivel, com . Procurar
efetuar mudanas nas solues bsicas de modo que seja mantido para
cada uma delas , e no repetindo solues j analisadas, pode-se
achar uma soluo tima para o modelo num nmero finito de iteraes.
C 0
C 0
Definies importantes
Considere os problemas Primal e Dual abaixo:
(Primal) Min Z = CX sujeito a: {AX = b , X > 0}
(Dual) Max W = Yb sujeito a: {YA s C, Y variveis livres}
Seja B a submatriz da matriz de coeficientes tecnolgicos do Primal formada
pelas colunas dos coeficientes das variveis bsicas nas restries
(denominadas colunas bsicas).
Definio 1:( Base Primal Vivel)
B uma Base Primal Vivel para esta Base tem-se a seguinte Soluo Bsica
Vivel associada:
4
b B C = Z e 0 = X , b B = X
-1
B N
-1
B
Observaes importantes
Condio de otimalidade do Simplex Revisado:
B Base tima se > 0, com (I)
Para uma dada soluo tima para o Primal o vetor de
multiplicadores do Simplex correspondente a soluo tima para o
Dual associado, satisfazendo portanto suas restries:
(II)
Definio 2: (Base Dual Vivel)
B uma Base Dual vivel (III)
Analisando conjuntamente as expresses (I), (II), (III) vem:
Se B Base Primal vivel e Dual vivel ento B Base tima.
5
C = C - A
= C B
B
-1
C - A 0
C - C B 0
B
-1
A
Caracterizao dos mtodos:
Simplex Primal:
Base Primal vivel Base Primal viavel .... Base Primal
viavel tima = Base Dual vivel.
Simplex Dual :
Base Dual vivel Base Dual viavel .... Base Dual vivel
tima = Base Primal vivel.
6
Fundamentos do Mtodo Simplex Dual:
aplicado para um modelo de Minimizao
Inicia com Base Dual vivel garantindo que as novas Bases
tambm so duais viveis.
Utiliza a mesma Tabela do Simplex Primal, com regras para
escolha do pivot diferentes.
Em todas as Tabelas so mantidos os coeficientes de custo relativo
no-negativos.
As constantes das restries no precisam se manter no-
negativas.
Termina quando todas as constantes das restries ficam no-
negativas.
7
Fases de aplicao do algoritmo
Passo 1: Montar uma Tabela para os dados do Primal, contendo uma Soluo Bsica com as seguintes
caractersticas:
Var. Bas. X
1
X
r
X
m
X
m+1
X
s
X
n
b
X
1
1 ... 0 ... 0
. . . . . . . .
. . . . . . . .
. . . . . . . .
X
r
0 ... 1 ... 0
. . . . . . . .
. . . . . . . .
. . . . . . . .
X
m
0 ... 0 ... 1
0 ... 0 ... 1
Importante:
8
quaisquer b e 0 C os j
j
> Todos
1 n 1, s 1, 1 , 1
b A ... A ...
+ m
A
r n r, s r, 1 ,
b A ... A ...
+ m r
A
m n m, s m, 1 ,
b A ... A ...
+ m m
A
n
s
1
C ... C ...
+ m
C
Passo 2: Escolha da varivel que sai (linha do pivot)
(a) se Soluo Bsica atual tima. Fim
(b) Caso contrrio: seja sai da Soluo Bsica e a linha r a linha
do pivot.
Passo 3: Escolha da varivel no-bsica que entra (coluna do pivot)
(a) Primal invivel. Fim
(b) caso contrrio: achar
Passo 4: Atualizao dos coeficientes da Tabela
Efetuar o pivoteamento em e voltar ao Passo 2.
9
0 b >
{ }
r j
X 0 < b min =
r
b
-/ 0 < A
j r,
bsicas. variveis das conjunto no X substitui X S, coluna pivot do coluna
, A = pivot 0 < A para
A
C
max =
r s
s r, j r,
j r,
j
,
=
s r
s
A
C
s r
A
,
Fases de Aplicao do Algoritmo
Exemplo de aplicao do Mtodo Simplex
Dual
Min Z =
Colocando as variveis de folga percebe-se que no h uma Soluo Bsica inicial.
Multiplicando-se cada restrio por (-1), obtm-se uma Soluo Bsica inicial para o
Mtodo Simplex Dual (que no Primal vivel, mas Dual vivel).
Passo 1: Tabela 1
Var. Bas. X
1
X
2
X
3
X
4
X
5
X
6
b
X
5
-1 -2 1 -1 1 0 -3
X
6
2 1 -4 -1 0 1 -2
1 4 0 3 0 0
10
>
>
>
4 1, = i 0, X
2 X + 4X + X - 2X -
3 X + X - 2X + X
: a s. 3X + 4X +
i
4 3 2 1
4 3 2 1
4 2 1
X
Exemplo
Soluo Bsica (Dual vivel):
Passo 2: Escolha da varivel que sai
Como
Passo 3: Escolha da varivel que entra
Como
11
( ) 0 0 0 3 0 4 1 = C
0 = X = X = X = X 2, - = X 3, - = X
4 3 2 1 6 5
>
{ } 1 linha pivot do linha a e sai X b Min = 3 - = b
5 j 1
=
1 11
11
1
X entra 1 - = A = Pivot
1 = pivot do coluna
1 -
1
=
A
C
=
1 -
3
,
2 -
4
,
1 -
1
= Max : 1 linha Para

)
`

Exemplo
Passo 4: Efetuando o pivoteamento obtm-se a nova Soluo Bsica (Dual vivel) dada na
Tabela 2.
Tabela 2
Var. Bas. X
1
X
2
X
3
X
4
X
5
X
6
b
X
1
1 2 - 1 1 -1 0 3
X
6
0 -3 -2 -3 2 1 -8
0 2 1 2 1 0
Varivel que sai: x
6
linha do pivot = 2
Varivel que entra:
12
3
23
j 2,
j 2,
j
23
3
X entra
2 - = A = pivot
3 = pivot coluna
0 < A para
A
C
Max =
2 -
1
=
)
`
A
C
Exemplo
Efetuando o pivoteamento obtm-se a Soluo Bsica (Dual vivel ) da Tabela 3.
Tabela 3
Var. Bas. X
1
X
2
X
3
X
4
X
5
X
6
b
X
1
1 7/2 0 5/2 -2 -1/2 7
X
3
0 3/2 1 3/2 -1 -1/2 4
0 1/2 0 1/2 2 1/2
Como tem-se soluo da Tabela 3 Base Primal vivel e Dual vivel
soluo tima:
Se o Primal for de Maximizao:
Manter
13
0
4
7
= b >
|
|
.
|
\
|
7 = 0 . 3 + 0 . 4 + 7 = 3X + 4X + X = Z
0 = X = X X = X 4, = X 7, = X
*
4
*
2
*
1
*
*
6
*
5
*
4
*
2
*
3
*
1
=
s 0 < A para ,
A
C
Min = Pivot como fazer e 0 C
j r,
j r,
j
j

Mtodo Simplex Dual

Enviado por

Direitos autorais:

Formatos disponíveis

Mtodo Simplex Dual

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Mtodo Simplex Dual

Enviado por

Direitos autorais:

Formatos disponíveis

Mtodo Simplex Dual

Prof. Fernando Augusto Silva Marins

Pesquisa Operacional Aplicada Produo - UNESP / Campus de Guaratinguet

Você também pode gostar