Método Dual-Simplex para Programação Linear

Prévia do material em texto

Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 51 Alberto Mulenga 
 
 
Para x1: 1*3 + 1*0 + 7*0 – 5 = -2, logo 1 = -2 
Para x2: 2*3 + 1*0 + 4*0 – 6 = 0, logo 2 = 0 
 
O que confere com os resultados obtidos na resolução do problema. Como 1 < 0, isto 
significa que a solução ainda não é óptima, x1 deve entrar na base e por outro lado a 
solução do dual não é viável, o que nos leva a concluir que: 
 
 Enquanto o primal não for óptimo, o dual será inviável; 
 
 As restrições do dual, correspondentes às variáveis básicas, são satisfeitas como 
equações, o que significa que a respectiva variável de excesso é nula; 
 
 O problema primal começa com uma solução viável não óptima que deve ser 
optimizada, enquanto o dual começa com uma solução inviável com valor superior ao 
óptimo e continua inviável até que a solução óptima seja atingida. 
 
 
3.2 MÉTODO SIMPLEX DUAL – SIMPLEX 
 
Até agora, nos problemas de programação linear que consideramos era obrigatório que 
todos os elementos do lado direito da tabela simplex fossem positivos. Isto significa que 
todas as soluções eram viáveis. Pela propriedade 4, sabemos que as soluções duais são 
inviáveis até que a solução óptima seja obtida. No entanto é possível que durante o 
processo de solução, venhamos a ter uma solução dual viável, o que significa inviável no 
primal. 
 
O método Dual – Simplex se destina a resolver esse tipo de problema. As diferenças em 
relação ao método simplex se resumem nas regras de entrada e saída de variáveis na base. 
 
 
3.2.1 Regras de entrada e saída de variáveis na base 
 
Dado um problema de minimização para resolvé-lo pelo método Dual - Simplex deve-se 
transformar as inequações do tipo  para  , em seguida aplicar as regras 1 e 2 para o 
problema de minimização. 
 
Regra 1. Variável que sai: é a variável básica com o menor valor negativo. Se todas as 
variáveis básicas tiverem valores positivos, a solução é óptima. 
 
Regra 2. Variável que entra: é escolhida entre as variáveis fora da base, da seguinte 
forma: 
 Dividir os coeficientes do lado esquerdo da equação z transformada (coeficientes da 
função objectivo) pelos correspondentes coeficientes negativos da equação da 
variável que sai 0a ; 
a
c
α ij
ij
i
ij  
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 52 Alberto Mulenga 
 
 
 A variável que entra é a que tem o menor valor entre os quocientes encontrados (para 
o problema de minimização) ou o menor valor absoluto (para o problema de 
maximização). 
 
Quando, em ambos os casos, não houver coeficientes negativos na linha da variável que 
sai da base, o problema não tem solução viável. 
 
Exemplo 3.5. Resolver o seguinte problema pelo método dual - simplex. 
Minimizar W = 2x1 + 1x2 
 Sujeito à 








0
321
634
21
21
ix
xx
xx
 
Resolução 
Para resolver o problema sem usar o método de duas fazes nem do grande M, vamos 
escrever o problema na forma padrão e introduzimos depois as variáveis de folga. 
 
 Minimizar W = 2x1 + 1x2 Min W = 2x1 + 1x2 + 0x3 + 0x4 
 Sujeito à 








0
321
634
21
21
ix
xx
xx
 Suj. à 








0
3021
6034
4321
4321
ix
xxxx
xxxx
 
 
 Tabela inicial simplex 
Base x1 x2 x3 x4 bi 
x3 
x4 
-4 -3 1 0 
 1 2 0 1 
-6 
 3 
W -2 -1 0 0 
(1/2) (1/3) 
 0 
A variável que sai é x3 porque x3 = -6; e x2 entra na base porque 1/3 < 1/2. 
 
1
a
 iteração 
Base x1 x2 x3 x4 bi 
x2 
x4 
 4/3 1 -1/3 0 
-5/3 0 2/3 1 
 2  l1’=-1/3l1 
-1  l2’=l2-2l1
’
 
W -2/3 0 -1/3 0 
(2/5) 
 2  l3’=l3+l1
’
 
2
a
 iteração 
Base x1 x2 x3 x4 Bi 
x2 
x1 
 0 1 1/5 4/5 
 1 0 -2/5 -3/5 
6/5  l1’=l1- 4/3l’2 
3/5  l2’=-3/5l2 
W 0 0 -3/5 -2/5 12/5 l3’=l3+2/3l2
’
 
 
Solução X = {3/5; 6/5; 0; 0} Wmin = 12/5 
Para a solução dual temos Y = (3/5; 2/5; 0; 0} Zmax = 12/5 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 53 Alberto Mulenga 
 
 
Exemplo 3.6. Resolver o problema de programação linear. 
(a) pelo método gráfico (b) pelo método dual - simplex. 
 
Minimizar W = 3x1 +2x2 
Sujeito à 











0
3
634
33
21
21
21
ix
xx
xx
xx
54
3
2
1
,
...
...
...
rr
r
r
r
 
 
a) Resolução pelo método gráfico 
 R1: x1 x2 R2 : x1 x2 R3: x1 x2 recta W: x1 x2 
 0 3 0 2 0 3 0 0 
 1 0 3/2 0 3 0 1 -3/2 
 
 
1
1
432
4
3
2
-1
x1
x2
r1
r2
r3
W
 
 
 
Do gráfico o ponto extremo e mínimo é P = r1 r2 
 
Resolvendo o sistema das rectas 





634
313
21
21
xx
xx
 teremos a solução 
 
X = (3/5; 6/5) com Wmin = 21/5 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 54 Alberto Mulenga 
 
 
b) Resolvendo pelo método dual – simplex, temos: 
 
Minimizar W = 3x1 +2x2 + 0x3 +0x4 +0x5 
Sujeito à 











0
310011
60034
30013
54321
54321
54321
ix
xxxxx
xxxxx
xxxxx
 
Tabela inicial simplex 
Base x1 x2 x3 x4 x5 bi 
x3 
x4 
x5 
 -3 -1 1 0 0 
 -4 -3 0 1 0 
 1 1 0 0 1 
-3 
-6 
 
 3 
W -3 -2 0 0 0 
(3/4) (2/3) 
 0 
1
a
 Iteração 
Base x1 x2 x3 x4 x5 bi 
x3 
x2 
x5 
-5/3 0 1 -1/3 0 
 4/3 1 0 -1/3 0 
-1/3 0 0 1/3 1 
-1  l1’=l1+l2
’ 
 2  l2’=-1/3l2
’ 
 1  l3’=l3 -l2
’
 
W -1/3 0 0 -2/3 0 
(1/5) (2) 
 4  l4’=l4+2l2
’
 
2
a
 Iteração 
Base x1 x2 x3 x4 x5 Bi 
x1 
x2 
x5 
 1 0 -3/5 1/5 0 
 0 1 4/5 -3/5 0 
 0 0 -1/5 2/5 1 
3/5  l1’=-3/5l1
 
6/5  l2’=l2 -4/3l1
’ 
6/5 l3’=l3 +1/3l1
’
 
W 0 0 -1/5 -3/5 0 21/5 l4’=l4+1/3l1
’
 
 
Solução X = (3/5; 6/5; 0;0;6/5) com Wmin = 21/5 
 
 
3.2.2 EXERCÍCIOS PROPOSTOS 
 
 
Exercício 3.1. Escreva os problemas na forma canónica e transforme – os em duais. 
 
a) Minimizar W = 9y1 + 2y2 b) Maximizar Z = 16x1 + 12x2 
 Sujeito à 








0
123
134
21
21
iy
yy
yy
 Sujeito à 











0
213
9
16
21
21
21
ix
xx
xx
xx
 
 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 55 Alberto Mulenga 
 
 
Exercício 3.2. Considere o seguinte problema de programação linear: 
 
Minimizar W = 5x1 + 2x2 
Sujeito à 












0
4
2
1
6
82
21
21
21
ix
xx
xx
xx
 
 
a) Escreva o problema dual correspondente. 
b) Obtenha a solução do primal a partir da resolução do dual pelo método simplex. 
(Resp. X = (0; 8; 0; 2; 4) com Wmin = 16 u.m) 
 
 
Exercício 3.3. Considere o seguinte problema de programação linear. 
Maximizar Z = 12x1 + 15x2 
Sujeito à 








0
1052
1234
21
21
ix
xx
xx
 
 
Usando o método simplex resolva o problema e apresente as soluções do primal e dual. 
(Primal: Resp. X = (15/7; 8/7; 0; 0) com Zmax = 300/7) 
(Dual : Resp: Y = (15/7; 12/7; 0; 0) com Wmin = 300/7) 
 
 
Exercício 3.4. Nos seguintes casos transformar em duais e depois resolver os problemas. 
a) Min W = 5y1 + 2y2b) Min W = 2y1 + 1y2 + 3y3 
 Sujeito à 








0
712
632
21
21
iy
yy
yy
 Sujeito à 








0
50012
100111
321
321
iy
yyy
yyy
 
 
c) Min W = 7y1 + 5y2 d) Min W = 2y1 + 1y2 
 Sujeito à 











0
82
821
412
21
21
21
iy
yy
yy
yy
 Sujeito à 








0
1012
2012
21
21
iy
yy
yy
 
 
a) Resp. Y = (0; 7; 15; 0) com Wmin = 14 
b) Resp. Y = (0; 100; 0; 0; 50) com Wmin = 100 
c) Resp. Y = (2; 0; 0; 10; 4) com Wmin = 14 
d) Resp. Y = (10; 0; 0; 0; 10) com Wmin = 20 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 56 Alberto Mulenga 
 
 
Exercício 3.5. Uma empresa de transporte dispõe de dois tipos de camiões que podem 
operar em três percursos diferentes. A capacidade semanal de transporte em cada um dos 
tipos de camiões e a procura semanal mínima de serviços de carga, expressos em 
toneladas estão indicados no quadro seguinte. 
 
Percursos Tipos de camiões Procura mínima 
Tipo A Tipo B 
1 
2 
3 
10 
12 
10 
10 
15 
10 
180 
200 
220 
 
Sabendo que os custos de operação de cada camião são 50 e 80 u.m por semana 
respectivamente, quantos veículos de cada tipo deve a empresa utilizar nos percursos 
indicados, de modo a minimizar os custos. (use o procedimento dual se necessário). 
(Resp. Y = (22; 0; 40; 64; 0) com Wmin = 1100 u.m.) 
 
 
Exercício 3.6. Resolva o seguinte problema de programação linear, primeiro 
graficamente e depois pelo algoritmo dual do método simplex. 
Minimizar W = 4y1 + 5y2 
Sujeito à 








0
753
802
21
21
iy
yy
yy
 
(Resp. Y = (14; 33; 0; 0) com Wmin = 221) 
 
 
Exercício 3.7. Resolva os seguintes problemas pelo método dual simplex, se necessário 
apresente a solução pelo método gráfico. Nota: substituir as equações por duas 
inequações. 
 
a) Min W = 4x1 + 2x2 
suj. à 








0
23
1
21
21
ix
xx
xx
 
 
b) Min W = 2x1+3x2 
suj. à 








0
211
312
21
21
ix
xx
xx
 
Respostas: 
a) X = (3/4; 1/4 ; 0; 0; 0) Wmin = 7/2 
b) X = (2; 0; 1; 0; 0) Wmin = 4