Lista de Exercícios de PO_2012_1_DUAL_DUAL SIMPLEX_PI_OTIM CLÁSSICA

Prévia do material em texto

LISTA DE EXERCÍCIOS
Exercícios de PO 2 = Capítulos 5 e 7
1) Escreva o dual do seguinte problema de programação linear:
0 x, x, x,x 
 500 x 2x 4x 3x 
400 x40 3x x x 
600 x10 7x 9x 4x a Sujeito
20x 9x 10x 6x ZMax 
4321
4321
4321
4321
4321
≥
≤+++
≤+++
≤+++
+++=
Solução:
Min D = 600 y1 + 400 y2 + 500 y3
Sujeito a 4y1 + y2 + 3y3 ≥ 6
 9y1 + y2 + 4y3 ≥ 10
 7y1 + 3y2 + 2y3 ≥ 9
10y1 + y2 + 3y3 ≥ 20
y1, y2, y3 ≥ 0
2) Escreva o dual do problema abaixo:
qualquer xe 0 x, x, x, x 
 6 9x 2x 3x x 2x 
2 x 5x 8x 7x 3x a Sujeito
5x 7x xx46x ZMax 
54321
54321
54321
54321
≥
=++++
=++−+
++++=
Solução:
Min D = 2 y1 + 6 y2
Sujeito a 3y1 + 2y2 ≥ 6
 7y1 + y2 ≥ 4
 -8y1 + 3y2 ≥ 1
 5y1 + 2y2 ≥ 7
 y1 + 9y2 = 5
y1, y2 irrestrito em sinal
3) Seja o seguinte problema primal:
0 x, x, x 
prima)-(matéria 30 5x 4x 3x 
obra) de (mão 45 5x 3x 6x a Sujeito
5x x3x ZMax 
321
321
321
321
≥
≤++
≤++
++=
cuja solução ótima é:
Professor André Gandolpho
LISTA DE EXERCÍCIOS
Base z X1 X2 X3 X4 X5 b
MAX 1 0 3 0 0 1 30
X1 0 1 −1/3 0 1/3 −1/3 5
X3 0 0 1 1 −1/5 2/5 3
Escreva o Dual e identifique sua solução ótima;
Solução:
Dual: 
Min D = 45 y1 + 30 y2 
Sujeito a 6 y1 + 3 y2 ≥ 3
 3y1 + 4 y2 ≥ 1
5y1 + 5 y2 ≥ 5
 y1, y2 ≥ 0
Solução ótima do Dual:
D = 30; y1 = 0; y2 = 1.
4) Resolva o seguinte problema de programação linear:
(P) Minimizar Z = 3y1 + 4y2 + 9y3
Sujeito a y1 + y3 ≥ 5
 y2 + 2y3 ≥ 2
y1 ≥ 0, y2 ≥ 0 e y3 ≥ 0
Adicionado as variáveis de folga em cada uma das restrições do problema (P), obter-se-á:
(P) Minimizar Z = 3y1 + 4y2 + 9y3
Sujeito a y1 + y3 − y4 = 5
 y2 + 2y3 − y5 = 2
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0 e y5 ≥ 0
Transformando para maximização a função objetivo do primal e multiplicando as duas 
restrições por (−1), para se obter um sistema canônico, o problema (P) se torna:
(P) Maximizar Z = −3y1 − 4y2 − 9y3
Sujeito a − y1 − y3 + y4 = − 5
 − y2 − 2y3 + y5 = − 2
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0 e y5 ≥ 0
E o quadro inicial para a aplicação do método Dual-Simplex está representado a seguir, onde 
y4 = −5 e y2 = −2.
Professor André Gandolpho
LISTA DE EXERCÍCIOS
z y1 y2 y3 y4 y5 b
Base 1 3 4 9 0 0 0
y4 0 −1 0 −1 1 0 -5
y5 0 0 −1 −2 0 1 −2
Note que a linha dos custos reduzidos indica otimalidade primal. Entretanto, a solução 
básica correspondente é infactível. Assim, é possível aplicar-se o método Dual Simplex neste 
quadro.
1. A variável a sair da base:
5)2,5min(1 −=−−=b ,
cuja variável correspondente é y4 e a primeira linha é a linha do pivot.
2. Variável a entrar na base:
Max ( )1913 , −− = Max ( ) 39,3 −=−− e a variável a entra na base é y1, enquanto o pivot é o 
elemento a11 = −1.
3. Para pivotar, tem-se que dividir a linha 1 por (-1). Em seguida, tem-se que somar à linha 
(0) a primeira linha multiplicada por (-3). O resultado destas operações pode ser visto no seguinte 
quadro:
z y1 y2 y3 y4 y5 b
Base 1 0 4 6 3 0 -15
y1 0 1 0 1 −1 0 5
y5 0 0 −1 −2 0 1 −2
O quadro acima indica que a otimalidade primal foi mantida, ou seja, os elementos da linha 
(0) são não negativos. Entretanto, como y5 = −2, a solução não é primal factível e há que se retornar 
ao passo 1, como explicado a seguir.
1. Variável a sair da base: y5
2. Variável a entrar na base:
Máx ( )2614 , −− = Max ( ) 33,4 −=−− e a variável a entrar na base é y3. O elemento pivot é a23 = 
−2.
3. Para fazer a variável y3 básica, há que multiplicar a segunda linha por (− 21 ), somar à 
linha (0) a segunda linha multiplicada por (-3) e somar à primeira linha a segunda multiplicada por(-
1). O resultado destas operações fornece o seguinte quadro:
z y1 y2 y3 y4 y5 b
Base 1 0 1 0 3 3
−21
y1 0 1 − 21 0 −1 21 4
y3 0 0 21 1 0 − 21 1
Note que a otimalidade primal foi mantida e, agora, foi alcançada a factibilidade primal. 
Desta forma, temos que esta solução é a ótima.
Z = −(−21) = 21 e y1 = 4, y2 = 0, y3 = 1, y4 = 0, y5 = 0.
Professor André Gandolpho
LISTA DE EXERCÍCIOS
5) Resolva o seguinte problema de Programação Linear:
Minimizar z = 2x1 + x2
Sujeito a 4x1 + 3x2 ≥ 6
 x1 + 2x2 ≤ 3
Solução:
Introduzindo as variáveis de folga nas restrições temos:
Minimizar z = 2x1 + x2
Sujeito a − 4x1 − 3x2 + x3 = −6
 x1 + 2x2 + x4 = 3
Montando o tableau inicial temos:
z x1 x2 x3 x4 b
Base 1
−2 −1 0 0 0
x3 0 −4 −3 1 0 −6
x4 0 1 2 0 1 3
Note que a linha dos custos reduzidos indica otimalidade primal, entretanto, a solução 
inicial deste problema é primal infactível, já que:
( ) ( )3643 −=xx
Utilizando o método dual simplex tem-se que a variável a sair da base é a x3.
Para determinar a variável que deve entrar na base usaremos o teste da razão:
Máximo { }3142 −−−− = 1/3 
Neste caso, a variável que entra na base é a x2.
Fazendo as operações necessárias no quadro inicial temos o seguinte quadro:
z x1 x2 x3 x4 b
Base 1
− 3
2 0
− 3
1 0 2
x2 0 34 1 − 31 0 2
x4 0 − 35 0 32 1 −1
Note no quadro acima que a solução ainda continua sendo primal infactível. Desta forma, 
temos que escolher a variável que deve sair da base, que neste caso é x4, pois é a única que está 
negativa.
Em seguida temos que escolher qual a variável que deve entrar na base no lugar de x 4. Neste 
caso não é necessário fazer o teste da razão, sendo x1 a variável candidata a entrar na base.
Fazendo os cálculos necessários temos:
Professor André Gandolpho
LISTA DE EXERCÍCIOS
z x1 x2 x3 x4 b
Base 1 0 0
− 5
3
− 5
2
− 5
12
x2 0 0 1 51 54 56
x1 0 1 0 − 52 − 53 53
Agora o tableau tem uma solução básica factível, que é ótima. Assim, temos:
( ) ( )565321 =xx e 512=z
6) Resolva o seguinte problema descrito no tableau abaixo. Utilize o método Simplex Primal-Dual.
Base z X1 X2 X3 X4 X5 X6 b
MIN 1 0 0 0 1 3 2 0
X1 0 1 0 0 4 -5 7 8
X2 0 0 1 0 −2 4 -2 -2
X3 0 0 0 1 1 3 2 2
Solução:
Neste caso, (x1, x2, x3) constitui um vetor dual básico factível. Aqui está o tableau canônico 
com respeito a este vetor básico.
z X1 X2 X3 X4 X5 X6 b
Base 1 0 0 0 1 3 2
X1 0 1 0 0 4 −5 7 8
X2 0 0 1 0 −2 4 −2 −2 Linha pivot
X3 0 0 0 0 1 3 2 2
razão ½ 2/2 
Desde que 2b = –2, a segunda linha é determinada como a linha pivot. A razão mínima 



−
j
j
a
c
2
 para j tal que ja 2 < 0 ocorre na coluna da variável não básica x4. Então x4 é a variável 
que deve entrar na base, entrando no lugar de x2 no vetor básico. Assim, depois de terem sido feitas 
as atualizações necessárias, temos o seguinte tableau canônico:
z X1 X2 X3 X4 X5 X6 b
Base 1 0 21 0 0 5 1 -1
X1 0 1 2 0 0 3 3 4
X4 0 0 − 21 0 1 -2 1 1
X3 0 0 21 0 0 -1 1 1
Professor André Gandolpho
LISTA DE EXERCÍCIOS
Observando este tableau podemos notar que todas as variáveis básicas são positivas, e a 
otimalidade primal está mantida, assim, esta base é ótima agora. Sendo assim, a solução ótima é 
dada pelo vetor:
(x1, x2, x3, x4, x5, x6) = (4, 0, 1, 1, 0, 0)
Valor da Função Objetivo Z(x) = 1
7) 
Professor André Gandolpho
	Exercícios de PO 2 = Capítulos 5 e 7
	Base
	Base
	MIN
	Linha pivot
	Base