2015212 22954 MET PESQ OPERAC I 03

Prévia do material em texto

Métodos de Pesquisa Operacional I
1Aula 04
Métodos Pesquisa Operacional I
Aula04.ppt
56 slides
Gerson Lachtermacher, Ph.D.
Paulo Sérgio Coelho, M.Sc.
Algoritmo Simplex
Método do Dicionário
2 / 56
Aula04.ppt
Fluxograma Simplex
Início
Determine
uma solução viável
Determine uma solução 
viável melhor
Não
Fim
SimSolução
Ótima?
O método de solução 
de um problema de 
programação linear é 
chamado de Simplex.
Este método repete a 
busca de uma solução 
melhor até encontrar a 
ótima. 
Isto significa que são 
encontradas várias 
soluções antes da 
ótima.
3 / 56
Aula04.ppt
Programação Linear 
Solução Analítica
Max x x x
s r
x x x
x x
x x x
x x x
x x x
 
 
 
 
 
5 5 3
3 3
3 2
2 2 4
2 3 2
0
1 2 3
1 2 3
1 3
1 2 3
1 2 3
1 2 3
+ +
+ + ≤
− + ≤
− + ≤
+ − ≤
≥
. .
, ,
Vamos buscar a solução 
ótima do problema ao lado.
Observe, antes de mais nada, 
que o problema está na forma 
padrão.
Nós manusearemos apenas 
problemas na forma padrão.
Métodos de Pesquisa Operacional I
2Aula 04
4 / 56
Aula04.ppt
c é chamada de 
folga, ou variável de folga
Transformando Inequação
em Equação
ba ≤
¾¾ Quando afirmamos:Quando afirmamos:
¾¾ Certamente podemos dizer que existe algum valor Certamente podemos dizer que existe algum valor 
cc, que pode ser desconhecido, tal que:, que pode ser desconhecido, tal que:
bca =+
5 / 56
Aula04.ppt
Transformando Inequação
em Equação
¾¾ Isto pode ser verificado, por exemplo, com dois copos Isto pode ser verificado, por exemplo, com dois copos 
d’águad’água
ba ≤
c
a
b
b
0≥c
=+ ca
onde:
6 / 56
Aula04.ppt
Transformando Inequação
em Equação
¾¾ Usando o raciocínio anterior para as Usando o raciocínio anterior para as 
primeiras restrições do problema dado:primeiras restrições do problema dado:
3 3 321 ≤++ xxx
3 3 4321 =+++ xxxx
23 31 ≤+− xx
23 531 =++− xxx
¾¾ As folgas em cada restrição não são As folgas em cada restrição não são necessanecessa--
riamenteriamente iguais, logo as variáveis de folga são iguais, logo as variáveis de folga são 
variáveis diferentes!variáveis diferentes!
Métodos de Pesquisa Operacional I
3Aula 04
7 / 56
Aula04.ppt
Determinando a Folga
¾¾ Reescrevendo:Reescrevendo:
3 3 4321 =+++ xxxx
3214 3 3 xxxx −−−=
¾¾ Obtemos a expressão que determina a Obtemos a expressão que determina a 
quantidade da folga necessáriaquantidade da folga necessária
8 / 56
Aula04.ppt
Dicionário Inicial
0,,
2 32
42 2
23 
3 3 
..
355 
321
321
321
31
321
321
≥
≤−+
≤+−
≤+−
≤++
++
xxx
xxx
xxx
xx
xxx
rs
xxxMax 3214 3 3 xxxx −−−=
315 3 2 xxx −+=
3216 2 24 xxxx −+−=
3217 322 xxxx +−−=
321 355 xxxz ++=
0,,,,,, 7654321 ≥xxxxxxx
Variáveis de Folga
9 / 56
Aula04.ppt
Classificação das Variáveis
¾Variáveis Básicas são as variáveis 
que se encontram do lado esquerdo 
das expressões de um dicionário;
¾¾Variáveis BásicasVariáveis Básicas são as variáveis são as variáveis 
que se encontram do lado esquerdo que se encontram do lado esquerdo 
das expressões de um dicionário;das expressões de um dicionário;
Métodos de Pesquisa Operacional I
4Aula 04
10 / 56
Aula04.ppt
Classificação das variáveis do 
problema proposto
x x x x
x x x
x x x x
x x x x
z x x x
x x x x x x x
4 1 2 3
5 1 3
6 1 2 3
7 1 2 3
1 2 3
1 2 3 4 5 6 7
3
2 3
4 2 2
2 2 3
5 5 3
0
= − − −
= + −
= − + −
= − − +
= + +
≥
3 
 
 
 
 
, , , , , ,
básicas
11 / 56
Aula04.ppt
Classificação das Variáveis
¾Variáveis Não Básicas são as que se 
encontram do lado direito das 
expressões do dicionário;
¾¾Variáveis Não BásicasVariáveis Não Básicas são as que se são as que se 
encontram do lado direito das encontram do lado direito das 
expressões do dicionário;expressões do dicionário;
12 / 56
Aula04.ppt
Classificação das variáveis do 
problema proposto
x x x x
x x x
x x x x
x x x x
z x x x
x x x x x x x
4 1 2 3
5 1 3
6 1 2 3
7 1 2 3
1 2 3
1 2 3 4 5 6 7
3
2 3
4 2 2
2 2 3
5 5 3
0
= − − −
= + −
= − + −
= − − +
= + +
≥
3 
 
 
 
 
, , , , , ,
Não básicas
Métodos de Pesquisa Operacional I
5Aula 04
13 / 56
Aula04.ppt
Classificação das Variáveis
¾A classificação das variáveis em 
básicas e não básicas fornece uma 
solução inicial viável, relacionada 
ao dicionário atual.
¾¾A classificação das variáveis em A classificação das variáveis em 
básicas básicas e e não básicasnão básicas fornece uma fornece uma 
solução inicialsolução inicial viávelviável, relacionada , relacionada 
ao dicionário atual.ao dicionário atual.
14 / 56
Aula04.ppt
Considerações sobre a 
classificação das variáveis
¾ A quantidade de variáveis não básicas 
coincide com a quantidade de variáveis do 
problema como foi fornecido, 
e a quantidade de variáveis básicas coincide 
com a quantidade de restrições;
¾ A cada nova solução, uma variável básica
trocará de lugar com uma não básica; as 
quantidades se manterão fixas.
¾¾ A quantidade de variáveis não básicas A quantidade de variáveis não básicas 
coincide com a coincide com a quantidade de variáveis do quantidade de variáveis do 
problema como foi fornecidoproblema como foi fornecido, , 
e ae a quantidade de variáveis básicasquantidade de variáveis básicas coincide coincide 
com a com a quantidade de restriçõesquantidade de restrições;;
¾¾ A cada nova solução, A cada nova solução, uma variável básicauma variável básica
trocará de lugar trocará de lugar com uma não básicacom uma não básica; ; as as 
quantidades se manterão fixasquantidades se manterão fixas..
15 / 56
Aula04.ppt
Classificação das variáveis do 
problema proposto
x x x x
x x x
x x x x
x x x x
z x x x
x x x x x x x
4 1 2 3
5 1 3
6 1 2 3
7 1 2 3
1 2 3
1 2 3 4 5 6 7
3
2 3
4 2 2
2 2 3
5 5 3
0
= − − −
= + −
= − + −
= − − +
= + +
≥
3 
 
 
 
 
, , , , , ,
não 
básicas
básicas
As variáveis não básicasAs variáveis não básicas
do dicionário inicial são 
as próprias variáveis do as próprias variáveis do 
problemaproblema;
As variáveis básicasAs variáveis básicas do 
dicionário inicial são as as 
variáveis de folgavariáveis de folga, e 
existe uma variável de 
folga para cada restrição.
Métodos de Pesquisa Operacional I
6Aula 04
16 / 56
Aula04.ppt
A leitura da solução a partir 
de um dicionário inicial
¾¾ Em cada dicionário é Em cada dicionário é possível determinar possível determinar 
quais são as variáveis básicas e quais são quais são as variáveis básicas e quais são 
as não básicasas não básicas;;
¾¾ A solução imposta pelo dicionário inicial A solução imposta pelo dicionário inicial 
pode ser encontrada da seguinte forma:pode ser encontrada da seguinte forma:
•• As variáveis não básicas são zeroAs variáveis não básicas são zero;;
•• As As variáveis básicasvariáveis básicas, bem como o valor de , bem como o valor de ZZ, , 
terão seu valor indicado nas restrições pelo terão seu valor indicado nas restrições pelo 
termo independente (termo independente (constanteconstante))
17 / 56
Aula04.ppt
A Solução Inicial do
problema proposto
Dicionário Inicial
x x x x
x x x
x x x x
x x x x
z x x x
x x x x x x x
4 1 2 3
5 1 3
6 1 2 3
7 1 2 3
1 2 3
1 2 3 4 5 6 7
3
2 3
4 2 2
2 2 3
5 5 3
0
= − − −
= + −
= − + −
= − − +
= + +
≥
3 
 
 
 
 
, , , , , ,
0
0
0
3
2
1
=
=
=
x
x
x
Z=0
2
4
2
3
7
6
5
4
=
=
=
=
x
x
x
x
18 / 56
Aula04.ppt
PrimeiraEtapa
Início
Determine
uma solução viável
Solução
Ótima?
Determine uma solução 
viável melhor
Não
Fim
Sim
Uma solução 
viável a ser 
determinada é a 
solução viável solução viável 
inicialinicial, através 
do Dicionário 
Inicial;
Métodos de Pesquisa Operacional I
7Aula 04
19 / 56
Aula04.ppt
Verificação da Solução Atual
¾ Lembrando que desejamos maximizar¾¾ Lembrando que desejamos maximizarLembrando que desejamos maximizar
Z x x x= + +5 5 31 2 3
¾ E ainda que:¾¾ E ainda que:E ainda que:
0
0
0
3
2
1
=
=
=
x
x
x ¾ Podemos notar que a solução 
não é ótima.
¾ Devemos escolher uma das 
variáveis para ser 
incrementada!
¾¾ Podemos notar que a solução Podemos notar que a solução 
não é ótima.não é ótima.
¾¾ Devemos escolher uma das Devemos escolher uma das 
variáveis para ser variáveis para ser 
incrementada!incrementada!
20 / 56
Aula04.ppt
Passo de Decisão
Início
Determine
uma solução viável
Solução
Ótima?
Determine uma solução 
viável melhor
Não
Fim
Sim
Na expressão da 
função objetivo só 
aparece o termo 
independente e as 
variáveis não básicas 
(zero).
Enquanto dentre estas 
variáveis alguma tiver 
coeficiente positivo, 
significa que a 
solução pode ser 
melhorada.
21 / 56
Aula04.ppt
Escolha da variável para 
entrar na base
¾ Uma regra geralmente usada para se determinar a 
variável a ser incrementada é a de se escolher a 
com maior coeficiente positivo, 
¾¾ Uma regra geralmente usada para se determinar a Uma regra geralmente usada para se determinar a 
variável a ser incrementada é a de se escolher a variável a ser incrementada é a de se escolher a 
com maior coeficiente positivocom maior coeficiente positivo, , 
z x x x= + +5 5 31 2 3
¾ Em nosso caso tanto x1 como x2 podem ser 
escolhidas. Escolheremos ao acaso x1.
¾¾ Em nosso caso tanto Em nosso caso tanto xx11 como como xx22 podem ser podem ser 
escolhidas. Escolheremos ao acaso escolhidas. Escolheremos ao acaso xx11..
isto é, a que mais 
rápido irá incrementar o valor de z.
isto é, a que isto é, a que mais mais 
rápido irá incrementar o valor de z.rápido irá incrementar o valor de z.
Métodos de Pesquisa Operacional I
8Aula 04
22 / 56
Aula04.ppt
Estudo do impacto – escolha 
da variável a sair da base
¾ Se x1 aumentar de valor z irá 
aumentar, porém
• x5 aumenta
• x4 , x6 e x7 diminuem
¾ Porém x4 , x6 e x7 devem 
continuar ≥ 0, 
¾ Se x1 aumentar de valor z irá 
aumentar, porém
• x5 aumenta
• x4 , x6 e x7 diminuem
¾ Porém x4 , x6 e x7 devem 
continuar ≥ 0, 
Solução Atual
x x x x
x x x
x x x x
x x x x
z x x x
x x x x x x x
4 1 2 3
5 1 3
6 1 2 3
7 1 2 3
1 2 3
1 2 3 4 5 6 7
3
2 3
4 2 2
2 2 3
5 5 3
0
= − − −
= + −
= − + −
= − − +
= + +
≥
3 
 
 
 
 
, , , , , ,
( ) 0 e 2,4,2,3,0,0,0 =Z
portanto 
devemos encontrar qual 
destas variáveis impõe a 
maior restrição ao 
aumento de x1
portanto 
devemos encontrar qual 
destas variáveis impõe a 
maior restrição ao 
aumento de x1
23 / 56
Aula04.ppt
Relação entre variáveis 
imposta pelas restrições
¾ Observando a primeira restrição:¾¾ Observando a primeira restrição:Observando a primeira restrição:
3214 3 3 xxxx −−−=
¾ Considerando que x2 e x3 são zero (não 
básicas), e que vão continuar assim, 
podemos retirá-las do processo:
¾¾ Considerando que Considerando que xx22 e e xx33 são zero (não são zero (não 
básicas), e que vão continuar assim, básicas), e que vão continuar assim, 
podemos retirápodemos retirá--las do processolas do processo::
14 3 xx −=
¾ Vamos observar o que esta expressão 
guarda de importante
¾¾ Vamos observar o que esta expressão Vamos observar o que esta expressão 
guarda de importanteguarda de importante
24 / 56
Aula04.ppt
¾¾ A expressão acima encerra uma relação A expressão acima encerra uma relação 
clara entre as variáveisclara entre as variáveis xx11 e e xx44. . Temos queTemos que
xx11=0=0, e logo, e logo xx44=3=3. Queremos reduzir o valor . Queremos reduzir o valor 
de de xx11, mas para tanto, temos que garantir que, mas para tanto, temos que garantir que
xx44 continue não negativacontinue não negativa, ou seja:, ou seja:
Relação entre variáveis 
imposta pelas restrições
14 3 xx −=
⎩⎨
⎧
≤
≥−⇒≥
3
0 3
0
1
1
4 x
x
x Limite ao crescimento de x1.
Métodos de Pesquisa Operacional I
9Aula 04
25 / 56
Aula04.ppt
Relação entre variáveis 
imposta pelas restrições
¾ Restrições impostas ao crescimento de x1, 
considerando x2 e x3 iguais a zero
¾¾ Restrições impostas Restrições impostas ao crescimentoao crescimento de xde x11, , 
considerando xconsiderando x22 e xe x33 iguais a zeroiguais a zero
mais rigorosa
sem restrição
x x x
x x x
x x x
x x x
4 1 1
5 1 1
6 1 1
7 1 1
0 3
2 0 2
4 2 0 2
2 2 0 1
= − ≥ ⇒ ≤
= + ≥ ⇒ ≥ −
= − ≥ ⇒ ≤
= − ≥ ⇒ ≤
3
26 / 56
Aula04.ppt
Variável Escolhida para 
entrar
¾¾ A busca da restrição A busca da restrição mais rigorosamais rigorosa ao ao 
crescimento da variável que entra crescimento da variável que entra é é 
oferecida pela oferecida pela variável que vai sairvariável que vai sair, pois:, pois:
•• Desejamos que a variável que entre cresça o Desejamos que a variável que entre cresça o 
máximo possível;máximo possível;
•• Para tanto, a variável que sai terá que decrescer Para tanto, a variável que sai terá que decrescer 
o máximo possível.o máximo possível.
¾¾ Precisamos agora reescrever todo do Precisamos agora reescrever todo do 
problema para obter o dicionário atualizado.problema para obter o dicionário atualizado.
27 / 56
Aula04.ppt
Em busca do novo dicionário
¾ Podemos portanto expressar x1 como função 
de x7:
¾¾ Podemos portanto expressar Podemos portanto expressar xx11 como função como função 
de de xx77::
3217 322 xxxx +−−=
7321 5,05,05,11 xxxx −+−=
Reescrevendo
Dicionário
Inicial
Novo
Dicionário
Métodos de Pesquisa Operacional I
10Aula 04
28 / 56
Aula04.ppt
Propagando a mudança nas 
outras restrições
Dicionário Inicial
Novo Dicionário
3214 3 3 xxxx −−−=
( )
7324
327324
5,05,15.12
35,05,05,113
xxxx
xxxxxx
+−−=
−−−+−−=
7321 5,05,05,11 xxxx −+−=Decidimos que
Logo:
29 / 56
Aula04.ppt
Propagando a mudança nas 
outras restrições
( )
7325
37325
5,05,25.13
35,05,05,112
xxxx
xxxxx
−−−=
−−+−+=
Dicionário Inicial
Novo Dicionário
315 3 2 xxx −+=
7321 5,05,05,11 xxxx −+−=Decidimos que
Logo:
30 / 56
Aula04.ppt
( )
7326
327326
342
25,05,05,1124
xxxx
xxxxxx
+−+=
−+−+−−=
Propagando a mudança nas 
outras restrições
Dicionário Inicial
Novo Dicionário
7321 5,05,05,11 xxxx −+−=
3216 2 24 xxxx −+−=
Decidimos que
Logo:
Métodos de Pesquisa Operacional I
11Aula 04
31 / 56
Aula04.ppt
( )
732
32732
5,25,55,25
355,05,05,115
xxxz
xxxxxz
−+−=
++−+−=
Propagando a mudança na 
Função Objetivo
Dicionário Inicial
Novo Dicionário
7321 5,05,05,11 xxxx −+−=
321 355 xxxz ++=
Decidimos que
Logo:
32 / 56
Aula04.ppt
Novo Dicionário
Solução Inicial
(0,0,0,3,2,4,2) e Z=0
x x x x
x x x
x x x x
x x x x
z x x x
x x x x x x x
4 1 2 3
5 1 3
6 1 2 3
7 1 2 3
1 2 3
1 2 3 4 5 6 7
3
2 3
4 2 2
2 2 3
5 5 3
0
= − − −
= + −
= − + −
= − − +
= + +
≥
3 
 
 
 
 
, , , , , ,
x x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4 2 3 7
5 2 3 7
6 2 3 7
1 2 3 7
2 3 7
1 2 3 4 5 6 7
15 15 0 5
3 15 2 5 0 5
2 4 3
1 15 0 5 0 5
5 2 5 5 5 2 5
0
= − − +
= − − −
= + − +
= − + −
= − + −
≥
2
 
 
. , ,
, . ,
, , ,, , ,
, , , , , ,
Solução após 1a Iteração
(1,0,0,2,3,2,0) e Z=5
33 / 56
Aula04.ppt
Uma análise do Primeiro 
Passo Iterativo
¾¾ Ao montarmos um novo dicionário Ao montarmos um novo dicionário 
conseguimos um aumento do valor de Z, que conseguimos um aumento do valor de Z, que 
passou depassou de 00, na solução inicial, para , na solução inicial, para 55. . BomBom!!
¾¾ No método Simplex, cada iteração No método Simplex, cada iteração devedeve
representarrepresentar uma melhora na função uma melhora na função 
objetivo. objetivo. 
Raramente a função objetivo manterRaramente a função objetivo manter--sese--á. á. 
Nunca pioraráNunca piorará!!
Métodos de Pesquisa Operacional I
12Aula 04
34 / 56
Aula04.ppt
Passo Iterativo
Início
Determine
uma solução viável
Solução
Ótima?
Determine uma solução 
viável melhor
Não
Fim
Sim
A determinação de 
uma solução melhor 
foi feita em três 
etapas:
• Escolha da variável 
que entra;
• Escolha da variável 
que sai;
• Alterações no 
dicionário gerando o 
dicionário novo.
35 / 56
Aula04.ppt
Uma análise do Primeiro 
Passo Iterativo
¾¾ O novo dicionário representa um acréscimo O novo dicionário representa um acréscimo 
de 5 unidades para a função objetivo.de 5 unidades para a função objetivo.
¾¾ Entretanto, esta solução obtida agora é a Entretanto, esta solução obtida agora é a 
melhor possívelmelhor possível??
732 5,25,55,25 xxxz −+−=
¾¾ Fácil perceber que Fácil perceber que xx33 pode melhorar a pode melhorar a 
função objetiva, pois atualmente é igual a função objetiva, pois atualmente é igual a 
zerozero, e tem , e tem coeficiente positivo na função coeficiente positivo na função 
objetivoobjetivo
36 / 56
Aula04.ppt
Solução
Ótima?
Não
Passo Iterativo
Início
Determine
uma solução viável
Solução
Ótima?
Determine uma solução 
viável melhor
Não
Fim
Sim
Determine uma solução 
viável melhor
Métodos de Pesquisa Operacional I
13Aula 04
37 / 56
Aula04.ppt
Escolha da variável que sai
¾ Se x3 aumenta de valor Z 
aumenta
• x1 aumenta
• x4 , x5 e x6 diminuem
¾ Porém x4 , x5 e x6 devem 
continuar ≥ 0, portanto 
devemos encontrar qual 
destas variáveis impõe a 
maior restrição ao 
aumento de x3
¾¾ Se xSe x33 aumenta de valor Z aumenta de valor Z 
aumentaaumenta
•• xx11 aumentaaumenta
•• xx44 , x, x55 e xe x66 diminuemdiminuem
¾¾ Porém Porém xx44 , x, x55 e xe x66 devem devem 
continuar continuar ≥ ≥ 00, portanto , portanto 
devemos encontrar qual devemos encontrar qual 
destas variáveis impõe a destas variáveis impõe a 
maior restrição ao maior restrição ao 
aumento de xaumento de x33Solução Atual( ) 5;0,2,3,2,0,0,1 =Z
x x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4 2 3 7
5 2 3 7
6 2 3 7
1 2 3 7
2 3 7
1 2 3 4 5 6 7
15 15 0 5
3 15 2 5 0 5
2 4 3
1 15 0 5 0 5
5 2 5 5 5 2 5
0
= − − +
= − − −
= + − +
= − + −
= − + −
≥
2
 
 
. , ,
, . ,
, , ,
, , ,
, , , , , ,
38 / 56
Aula04.ppt
Escolha da variável que sai
¾ Restrições impostas ao crescimento de x3, 
considerando x2 e x7 iguais a zero
¾¾ Restrições impostas ao crescimento de xRestrições impostas ao crescimento de x33, , 
considerando xconsiderando x22 e xe x77 iguais a zeroiguais a zero
mais rigorosa
sem restrição
5/605.23 335 ≤⇒≥−= xxx
3/405,12 334 ≤⇒≥−= xxx
205,01 331 −≥⇒≥+= xxx
3/2032 336 ≤⇒≥−= xxx
39 / 56
Aula04.ppt
Isolando a variável que vai 
entrar
¾ Podemos portanto expressar x3 como função 
de x6
Dicionário Atual
¾¾ Podemos portanto expressar xPodemos portanto expressar x33 como função como função 
de xde x66
Dicionário AtualDicionário Atual
73
1
63
1
23
4
3
2
3 xxxx +−+=
7326 342 xxxx +−+=
Novo DicionárioNovo DicionárioNovo Dicionário
Métodos de Pesquisa Operacional I
14Aula 04
40 / 56
Aula04.ppt
Reescrevendo as outras 
restrições
¾ As outras equações devem refletir esta 
mudança:
¾¾ As outras equações devem refletir esta As outras equações devem refletir esta 
mudança:mudança:
Dicionário Atual
Novo Dicionário62
1
22
7
4 1 xxx +−=
7324 5,05,15.12 xxxx +−−=
73
1
63
1
23
4
3
2
3 xxxx +−+=
( ) 72173163123432232234 2 xxxxxx ++−+−−=
Lembrando que
Temos:
Logo:
41 / 56
Aula04.ppt
Reescrevendo as outras 
restrições
7325 5,05.25,13 xxxx −−−=
Novo Dicionário
Dicionário Atual
( )
73
4
66
5
26
29
3
4
5
72
1
73
1
63
1
23
4
3
2
2
5
22
3
5 3
xxxx
xxxxxx
−+−=
−+−+−−=
73
1
63
1
23
4
3
2
3 xxxx +−+=Lembrando que
Temos:
42 / 56
Aula04.ppt
Reescrevendo as outras 
restrições
73
1
63
1
23
4
3
2
3 xxxx +−+=
Novo Dicionário
Dicionário Atual
7321 5,05,05,11 xxxx −+−=
( )
73
1
66
1
26
5
3
4
1
72
1
73
1
63
1
23
4
3
2
2
1
22
3
1 1
xxxx
xxxxxx
−−−=
−+−++−=
Lembrando que
Temos:
Métodos de Pesquisa Operacional I
15Aula 04
43 / 56
Aula04.ppt
Reescrevendo função objetivo
73
1
63
1
23
4
3
2
3 xxxx +−+=
Novo Dicionário
Dicionário Atual
732 5,25,55,25 xxxz −+−=
( )
73
2
66
11
26
29
3
26
72
5
73
1
63
1
23
4
3
2
2
11
22
55
xxxz
xxxxxz
−−+=
−+−++−=
Lembrando que
Temos:
44 / 56
Aula04.ppt
3
26= e )0,0,,1,,0,( 343234 Z
Novo Dicionário
x x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4 2 3 7
5 2 3 7
6 2 3 7
1 2 3 7
2 3 7
1 2 3 4 5 6 7
15 15 0 5
3 15 2 5 0 5
2 4 3
1 15 0 5 0 5
5 2 5 5 5 2 5
0
= − − +
= − − −
= + − +
= − + −
= − + −
≥
2
 
 
. , ,
, . ,
, , ,
, , ,
, , , , , ,
Solução após 1a Iteração
(1,0,0,2,3,2,0) e Z=5
x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4
7
2 2
1
2 6
5
29
6 2
5
6 6
4
3 7
3
2
3
4
3 2
1
3 6
1
3 7
1
5
6 2
1
6 6
1
3 7
29
6 2
11
6 6
2
3 7
1 2 3 4 5 6 7 0
= − +
= − + −
= + − +
= − − −
= + − −
≥
1
4
3
4
3
26
3
, , , , , ,
Solução após 2a Iteração
45 / 56
Aula04.ppt
Uma análise do Segundo 
Passo Iterativo
¾¾ Ao montarmos o novo dicionário Ao montarmos o novo dicionário 
conseguimos um aumento do valor de Z, que conseguimos um aumento do valor de Z, que 
passou de 5, na solução inicial, para passou de 5, na solução inicial, para 
aproximadamente 8,7. aproximadamente 8,7. BomBom!!
¾¾ Entretanto, esta solução obtida agora é a Entretanto, esta solução obtida agora é a 
melhor possível?melhor possível?
73
2
66
11
26
29
3
26 xxxZ −−+=
Métodos de Pesquisa Operacional I
16Aula 04
46 / 56
Aula04.ppt
Escolha da variável que sai
¾ Se x2 aumenta de valor Z 
aumenta
• x3 aumenta
• x4 , x5 e x1 diminuem
¾ Porém x4 , x5 e x1 devem 
continuar ≥ 0, portanto 
devemos encontrar qual 
destas variáveis impõe a 
maior restrição ao 
aumento de x3
¾¾ Se xSe x22 aumenta de valor Z aumenta de valor Z 
aumentaaumenta
•• xx33 aumentaaumenta
•• xx44 , x, x55 e xe x11 diminuemdiminuem
¾¾ Porém Porém xx44 , x, x55 e xe x11 devem devem 
continuar continuar ≥ ≥ 00, portanto , portanto 
devemos encontrar qual devemos encontrar qual 
destas variáveis impõe a destas variáveis impõe a 
maior restrição ao maior restrição ao 
aumento de xaumento de x33
x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4
7
2 2
1
2 6
5
29
6 2
5
6 6
4
3 7
3
2
3
4
3 2
1
3 6
1
3 7
1
5
6 2
1
6 6
1
3 7
29
6 2
11
6 6
2
3 7
1 2 3 4 5 6 7 0
= − +
= − + −
= + − +
= − − −
= + − −
≥
1
4
3
4
3
26
3
, , , , , ,
3
26= e )0,0,,1,,0,( 343234 Z
Solução após 2a Iteração
47 / 56
Aula04.pptEscolha da Variável que 
entra
¾ Restrições impostas ao crescimento de x2, 
con-siderando x6 e x7 iguais a zero
¾¾ Restrições impostas ao crescimento de xRestrições impostas ao crescimento de x22, , 
concon--siderandosiderando xx66 e xe x77 iguais a zeroiguais a zero
mais rigorosa
sem restrição
29/80 22629345 ≤⇒≥−= xxx
7/201 22274 ≤⇒≥−= xxx
5/80 2265341 ≤⇒≥−= xxx
20 2234323 −≥⇒≥+= xxx
48 / 56
Aula04.ppt
Isolando a variável que vai 
entrar
¾ Podemos portanto expressar x2 como função 
de x5
Dicionário Atual
¾¾ Podemos portanto expressar xPodemos portanto expressar x22 como função como função 
de xde x55
Dicionário AtualDicionário Atual
729
8
629
5
529
6
29
8
2 xxxx −+−=
73
4
66
5
26
29
3
4
5 xxxx −+−=
Novo DicionárioNovo DicionárioNovo Dicionário
Métodos de Pesquisa Operacional I
17Aula 04
49 / 56
Aula04.ppt
Reescrevendo as outras 
restrições
¾ Porém as outras equações devem refletir 
esta mudança
¾¾ Porém as outras equações devem refletir Porém as outras equações devem refletir 
esta mudançaesta mudança
Dicionário Atual
Novo Dicionário
729
8
629
5
529
6
29
8
2 xxxx −+−=
62
1
22
7
4 1 xxx +−=
( )
729
28
629
3
529
21
29
1
4
62
1
729
8
629
5
529
6
29
8
2
7
4 1
xxxx
xxxxx
+−+=
+−+−−=
Lembrando que
Temos:
50 / 56
Aula04.ppt
( )
729
1
629
3
529
8
29
30
3
3
1
63
1
729
8
629
5
529
6
29
8
3
4
3
2
3
xxxx
xxxxxx
−−−=
+−−+−+=
Novo Dicionário
Dicionário Atual
729
8
629
5
529
6
29
8
2 xxxx −+−=
Reescrevendo as outras 
restrições
73
1
63
1
23
4
3
2
3 xxxx +−+=
Lembrando que
Temos:
51 / 56
Aula04.ppt
( )
729
3
629
9
529
5
29
32
1
73
1
66
1
729
8
629
5
529
6
29
8
6
5
3
4
1
xxxx
xxxxxx
−−+=
−−−+−−=
Reescrevendo as outras 
restrições
Novo Dicionário
Dicionário Atual
729
8
629
5
529
6
29
8
2 xxxx −+−=
73
1
66
1
26
5
3
4
1 xxxx −−−=
Lembrando que
Temos:
Métodos de Pesquisa Operacional I
18Aula 04
52 / 56
Aula04.ppt
( )
765
3
2
66
11
729
8
629
5
529
6
29
8
6
29
3
26
201 xxxz
xxxxxz
−−−=
−−−+−+=
Reescrevendo a função 
objetivo
Novo Dicionário
Dicionário Atual
73
2
66
11
26
29
3
26 xxxz −−+=
729
8
629
5
529
6
29
8
2 xxxx −+−=Lembrando que
Temos:
53 / 56
Aula04.ppt
Novo Dicionário
x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4
7
2 2
1
2 6
5
29
6 2
5
6 6
4
3 7
3
2
3
4
3 2
1
3 6
1
3 7
1
5
6 2
1
6 6
1
3 7
29
6 2
11
6 6
2
3 7
1 2 3 4 5 6 7 0
= − +
= − + −
= + − +
= − − −
= + − −
≥
1
4
3
4
3
26
3
, , , , , ,
x x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4
21
29 5
3
29 6
28
29 7
2
8
29
6
29 5
5
29 6
8
29 7
3
8
29 5
3
29 6
1
29 7
1
5
29 5
9
29 6
3
29 7
5 6 7
1 2 3 4 5 6 7
2
0
= + − +
= − + −
= − − −
= + − −
= − − −
≥
1
29
30
29
32
29
10
, , , , , ,
Solução após 3a Iteração
( , , , , , , )3229 829 3029 129 0 0 0 
e z = 103
26= e )0,0,,1,,0,( 343234 Z
Solução após 2a Iteração
54 / 56
Aula04.ppt
Passo de Decisão
x x x x
x x x x
x x x x
x x x x
z x x x
x x x x x x x
4
21
29 5
3
29 6
28
29 7
2
8
29
6
29 5
5
29 6
8
29 7
3
8
29 5
3
29 6
1
29 7
1
5
29 5
9
29 6
3
29 7
5 6 7
1 2 3 4 5 6 7
2
0
= + − +
= − + −
= − − −
= + − −
= − − −
≥
1
29
30
29
32
29
10
, , , , , ,
Solução após 3a Iteração
( , , , , , , )3229 829 3029 129 0 0 0 
e z = 10
¾ Como z não pode mais 
ser aumentado pois x5, 
x6 e x7 tem coeficientes 
negativos
¾ Esta é a solução ótima
¾¾ Como z não pode mais Como z não pode mais 
ser aumentado pois xser aumentado pois x55, , 
xx66 e xe x77 tem coeficientes tem coeficientes 
negativosnegativos
¾¾ Esta é a solução ótimaEsta é a solução ótima
Métodos de Pesquisa Operacional I
19Aula 04
55 / 56
Aula04.ppt
Programação Linear 
Solução Analítica – Resumo
Início
Determine
uma solução viável
Solução
Ótima?
Determine uma solução 
viável melhor
•Variável que entra
•Variável que sai
•Novo Dicionário
•Todos Coeficientes
de Z são negativos?
•Determine o 
dicionário Inicial
Não
Fim
Sim
56 / 56
Aula04.ppt
Exercício
0,,
732
532
42..
423
321
321
31
321
321
≥
≤++
≤+
≤++
++
xxx
xxx
xx
xxxts
xxxMax