Aula10_Simplex4

Prévia do material em texto

PESQUISA OPERACIONAL
Algoritmo Simplex- Métodos das Duas 
Fases
Algoritmo Simplex
Fase 1- Tem como objetivo encontrar uma solução 
básica inicial para o problema Original.
Fase 2 - Tem como propósito encontrar uma 
solução ótima para o problema original, a partir da 
solução ótima obtida na fase 1.
Exercicio de transporte carga
Uma companhia de transporte tem 3 tipos de 
caminhões o tipo “A” tem 2m3 de espaço 
refrigerado e 3m3 de espaço não refrigerado. O 
tipo “B” tem 2m3 de espaço refrigerado e 1m3 de 
espaço não refrigerado e o tipo “C” tem 5m3 de 
espaço refrigerado e 5m3 de espaço não 
refrigerado. O cliente quer transportar um produto 
que necessitará >= de 20m3 de área refrigerada e a 
área não refrigerada seja igual = a 10m3. 
Algoritmo Simplex
A companhia calcula entre 1.700 litros o combustível 
para uma viagem com o caminhão “A” e 750 
litros para o caminhão “B” e “C” 800 litros. Quantos 
caminhões de cada tipo deverão ser usados no 
transporte do produto com o menor consumo de 
combustível ? 
Min Z = 1700 X1 + 750 X2 + 800 X3
20522 321  xxx
0,00 321  xxx
1053 321  xxx
321
,,
800750700.1
321
xxxZMin
xxx

Função Objetivo
Matriz Tecnológica
Variáveis de Decisão
Limitações
Conjunto das 
Possibilidades 
de Produção
321
,, xxx
Algoritmo Simplex
Algoritmo Simplex
Repare que as restrições são de igual (=) e de maior 
ou igual ( ). Desta forma, é necessário realizar 
transformações lineares nestas restrições.
A restrições do tipo ( ) é equilibrada com a adição 
de uma variável de folga por excesso E1
A segunda restrição já está equilibrada. -E1

 0,
1053
20522
3
3
1321
21
21
 x,xx
xxx
Exxx




20522 1321  Exxx
7
Os vetores das variáveis básicas VB formam sempre 
uma Matriz Identidade;
Às VB tem sempre coeficiente nulo na equação de Z;
Algoritmo Simplex
O Valor das VB, f1, f2, f3, f4, f5, fn é lido diretamente 
na coluna VSM;
O valor de Z é lido diretamente na coluna VSM.
Algoritmo Simplex
Algoritmo Simplex
Quadro inicial do Simplex
VB X1 X2 X3 E1 VSM
? 2 2 5 -1 20
? 3 1 5 0 10
Repare que não temos uma matriz identidade para
uma solução inicial Porquê?
Na 1ª restrição a variável de folga tem coeficiente -1,
e a 2ª restrição já está equilibrada e, portanto, não
precisa de variável auxiliar. A saída e utilizar variáveis
artificiais.
321
,,
800750700.1
321
xxxZMin
xxx

 0,
1053
20522
3
3
1321
21
21
 x,xx
xxx
Exxx



Algoritmo Simplex
 0,
1053
20522
3
23
11321
21
21
 x,xx
Axxx
AExxx



VB X1 X2 X3 E1 A1 A2 VSM
A1 2 2 5 -1 1 0 20
A2 3 1 5 0 0 1 10
Temos a matriz identidade, contudo a soma entre X1,
X2 e X3 igual a 20 só se mantém quando a variável
artificial A1 for igual a zero. Idem para 2ª restrição.
Algoritmo Simplex
VB X1 X2 X3 E1 A1 A2 VSM
A1 2 2 5 -1 1 0 20
A2 3 1 5 0 0 1 10
Vamos criar uma função objetivo artificial (W) que
será dada pela soma das variáveis artificiais, sendo o
objetivo a minimização desta função W.
VB X1 X2 X3 E1 A1 A2 VSM
A1 2 2 5 -1 1 0 20
A2 3 1 5 0 0 1 10
W 5 3 10 -1 1 1 30
Algoritmo Simplex
Entra na base a variável X3, pois apresenta o
maior coeficiente positivo, visto que,
desejamos minimizar a função W. Sai da base a
variável auxiliar A2, pois apresenta o menor
quociente { 20/5= 4; 10/5= 2}
VB X1 X2 X3 E1 A1 A2 VSM
A1 2 2 5 -1 1 0 20
A2 3 1 5 0 0 1 10
W 5 3 10 -1 1 1 30
20 /5 =4
10/5 = 2
Algoritmo Simplex
Divide-se toda a linha A2 por 5. Depois multiplica-se a
linha A2 por -5 e soma-se com a linha A1. Finalmente
multiplica-se a linha A2 por -10 e soma-se com a linha W.
VB X1 X2 X3 E1 A1 A2 VSM
A1 -1 1 0 -1 1 -1 10 
X3 3/5 1/5 1 0 0 1/5 2 
W -1 1 0 -1 1 -1 10 
VB X1 X2 X3 E1 A1 A2 VSM
A1 2 2 5 -1 1 0 20
A2 3 1 5 0 0 1 10
W 5 3 10 -1 1 1 30
Algoritmo Simplex
Essa solução ainda não é a ótima, pois ainda há
coeficiente positivos na linha W. Entra X2 na base e
sai A1.
Divide-se toda a linha A1 por 1. Depois multiplica-se
a linha A1 por -1/5 e soma-se com a linha X3.
Finalmente multiplica-se a linha A1 por -1 e soma-se
com a linha W.
VB X1 X2 X3 E1 A1 A2 VSM
A1 -1 1 0 -1 1 -1 10 
X3 3/5 1/5 1 0 0 1/5 2 
W -1 1 0 -1 1 -1 10 
Algoritmo Simplex
Solução ótima, visto que, não há coeficiente positivos na
linha W. Fim da Fase 1.
Fase 2 - Essa fase tem como objetivo determinar a
solução ótima para o problema original. Combina-se a
função objetivo original com as
restrições da forma tabular ótima obtida na Fase 1.
VB X1 X2 X3 E1 A1 A2 VSM
X2 -1 1 0 -1 1 -1 10 
X3 4/5 0 1 1/5 - 1/5 2/5 0 
W 0 0 0 0 0 0 0 
750
800
321
,,
800750700.1
321
xxxZMin
xxx

VB X1 X2 X3 E1 A1 A2 VSM
A1 -1 1 0 -1 1 -1 10 
X3 3/5 1/5 1 0 0 1/5 2 
W -1 1 0 -1 1 -1 10 
Algoritmo Simplex
Elimina-se as coluna X1, pois a mesma não está na
base na solução ótima da Fase 1. Multiplica-se por
750 a linha X2 e por 800 a linha X3.
VB X2 X3 E1 F1 F2 VSM
X2 1 0 -1 1 -1 10 
X3 0 1 1/5 - 1/5 2/5 0 
W 0 0 0 0 0 0 
750
800
VB X2 X3 F1 F2 VSM
X2 1 0 1 -1 10 
X3 0 1 -1/5 2/5 0 
Z 750 800 
750 . (1)+ 800 . (-
1/5) = -590 
750 . (-1)+ 800 x 
(2/5) = -430 
750 x 10+ 800 x 0 = 
7.500
321
,,
800750700.1
321
xxxZMin
xxx

Algoritmo Simplex
Solução já é a ótima, pois o coeficiente da variável
não básica F1 e F2 é não positivo, pois o objetivo
da função é de minimização.
VB X2 X3 F1 F2 VSM
X2 1 0 -1 -1 10 
X3 0 1 1/5 2/5 0 
Z 0 0 
750 x 1+ 800 x -1/5
= -590 
750 x -1+ 800 x 
2/5 = -430 
750 x 10+ 800 x 0 = 
7.500
PESQUISA OPERACIONAL
Algoritmo Simplex :
Problemas de Minimização
Algoritmo Simplex
Há duas formas de resolver problemas de 
minimização pelo algoritmo Simplex.
A primeira forma é transformar um problema de 
minimização em problema de maximização.

MinZ  x i 
iI
 Max Z   x i
iI

Min
x1 ,x2 ,x3
Z 1.700x1  750x2  800x3  Max
x1 ,x2 ,x3
 Z  1.700x1  750x2  800x3
Algoritmo Simplex
Há duas formas de resolver problemas de 
minimização pelo algoritmo Simplex.
A segunda forma é adotar o mesmo procedimento 
visto na aula 9. Em outras palavras, o mesmo 
processo de cálculo visto na Fase 1.

2x1  x2 10

x1 0, x2 0.

x1  x2  8

Min
x1 ,x2 ,x3
Z  4x1 2x2
Função Objetivo
Matriz 
Tecnológica
Variáveis de Decisão
Limitações
Condições de não 
negatividade
x
1
, x
2
Algoritmo Simplex
 Os vetores das variáveis básicas VB formam sempre 
uma Matriz Identidade;
 Às VB tem sempre coeficiente nulo na equação de Z;
Algoritmo Simplex
 O Valor das VB, f1, f2, f3, f4, f5, fn é lido diretamente 
na coluna VSM;
 O valor de Z é lido diretamente na coluna VSM.
Algoritmo Simplex
Modelo Forma padrão do simplex
As variáveis de folga transformam às
inequações em equações.
Min Z  4x
1
 2x
2
sujeito a :
2x
1
 x
2
10 
x
1
 x
2
 8
x
1
,x
2
 0 ,f,f,xx
fxx
 fxx
ffxx ZMax
1
0
8
102
:a sujeito
0024- - 
2121
221
121
212




Algoritmo Simplex
Algoritmo Simplex
Quadro inicial do Simplex
VB X1 X2 F1 F2 VSM
F1 2 1 1 0 10
F2 1 -1 0 1 8
Z 4 -2 0 0 0

Max Z  4x1 2x2 Z 4x1 2x2
VB X1 X2 F1 F2 VSM 
X2 2 1 1 0 10
F2 3 0 1 1 18
Z 8 0 2 0 20
 Os resultados 
desta iteração 
são os ótimos, 
visto que, não 
há coeficientes 
negativos 
associados as 
variáveis não 
básicas (X1,F1)
na linha Z.
Algoritmo Simplex
VB X1 X2 F1 F2 VSM 
X2 2 1 2 0 10
F2 3 0 2 1 18
Z 8 0 2 0 20
Solução ótima: X2= 10, X1=0, F2= 18; Z=20
Modelo Forma padrão do simplex
 Segunda maneira de resolver problemas de
minimização pelo algoritmo Simplex.
 0
8
102
:a sujeito
2421
21
21
2
 ,xx
xx
 xx
xx ZMin
1




 ,f,f,xx
fxx
 fxx
ffxx ZMin
1
0
8
102
:a sujeito
0024- 
2121
221
121
212




Algoritmo Simplex
Algoritmo Simplex
VB X1 X2 F1 F2 VSM
F1 2 1 1 0 10
F2 1 -1 0 1 8
Z -4 2 0 0 0
2121 2424 xxZxxZMin 
VB X1 X2 F1 F2 VSM 
X2 2 1 1 0 10
F2 3 0 1 1 18
Z -8 0 -2 0 -20
Os resultados 
desta iteração 
são os ótimos, 
visto que, não 
há coeficientes 
positivos
associados as 
variáveis não 
básicas na 
linha Z.
PESQUISA OPERACIONAL
Algoritmo Simplex :
Casos Especiais
Algoritmo Simplex
Múltiplas soluções ótima ocorre quando na última 
iteração do algoritmo simplex uma variável não 
básica possui valor nulo (0) na linha Z.
Em outras palavras, não há o custo reduzido.
0,
621
1624
:.
816
21
21
21




xx
xx
xx
as
xxZMax
 Os vetores das variáveis básicas VB formam sempre 
uma Matriz Identidade;
 Às VB tem sempre coeficiente nulo na equação de Z;
Algoritmo Simplex
 O Valor das VB, f1, f2, f3, f4, f5, fn é lido diretamente 
na coluna VSM;
 O valor de Z é lido diretamente na coluna VSM.
Algoritmo Simplex
Modelo Forma padrão do simplex
 As variáveis de folga transformam as
inequações em equações.
 0
6
1624
:a sujeito
861 
21
21
21
21
 ,xx
xx
 xx
xx ZMax




 ,f,f,xx
fxx
 fxx
xx ZMax
0
6
1624
:a sujeito
816- 
2121
221
121
21




Algoritmo Simplex 
Algoritmo Simplex
VB X1 X2 F1 F2 VSM
F1 4 2 1 0 16
F2 1 1 0 1 6
Z -16 -8 0 0 0
VB X1 X2 F1 F2 VSM 
X1 1 1/2 1/4 0 4
F2 0 1/2 - 1/4 1 2 
Z 0 0 4 0 64 
Algoritmo Simplex
VB X1 X2 F1 F2 VSM 
X1 1 1/2 1/4 0 4 
F2 0 1/2 - 1/4 1 2 
Z 0 0 4 0 64 
Apenas as variáveis básicas apresentam coeficientes 
nulos na linha Z. Se a variável X2 entrar na base, a função 
objetivo não se altera, porém obteremos outra solução 
ótima alternativa.
Algoritmo Simplex
Quadro inicial do Simplex
VB X1 X2 F1 F2 VSM 
X1 1 0 1/2 -1 2 
X2 0 1 - 1/2 2 4 
Z 0 0 4 0 64 
Apenas as variáveis básicas apresentam 
coeficientes nulos na linha Z. Se a variável X2 
entrar na base, a função objetivo não se altera, 
porém obteremos outra solução ótima alternativa.
Algoritmo Simplex
VB X1 X2 F1 F2 VSM 
X1 1 0 1/2 -1 2 
X2 0 1 - 1/2 2 4 
Z 0 0 4 0 64 
VB X1 X2 F1 F2 VSM 
X1 1 1/2 1/4 0 4 
F2 0 1/2 - 1/4 1 2 
Z 0 0 4 0 64 
Algoritmo Simplex
Solução ilimitada => uma variável não básica 
candidata a ficar na base fica impossibilitada
de entrar na base. Isso acontece porque as 
linhas de todas as variáveis básicas possuem 
coeficientes não positivos na coluna pivô. 
0,
81
1652
:.
34
21
21
21




xx
x
xx
as
xxZMax
Algoritmo Simplex
 0,
8
2052
:a sujeito
3
2
1121
21
1
 x,xx
fx
AExx
WMin



VB X1 X2 E1 A1 F2 VSM
A1 2 5 -1 1 0 20
A2 1 0 0 0 1 8
W 3 5 -1 1 1 28
Algoritmo Simplex
 0,
8
2052
:a sujeito
3
2
1121
21
1
 x,xx
fx
AExx
WMin



VB X1 X2 E1 A1 A2 VSM
A1 2 5 -1 1 0 20
F2 1 0 0 0 1 8
W 3 5 -1 1 0 20
Algoritmo Simplex
VB X1 X2 E1 A1 A2 VSM
A1 2 5 -1 1 0 20
F2 1 0 0 0 1 8
W 2 5 -1 1 0 20
VB X1 X2 E1 A1 A2 VSM
X2 2/5 1 - 1/5 1/5 0 4 
F2 1 0 0 0 1 8 
W 0 0 0 0 0 0 
Algoritmo Simplex
VB X1 X2 E1 A1 F2 VSM
X2 2/5 1 - 1/5 1/5 0 4 
F2 1 0 0 0 1 8 
W 0 0 0 0 0 0 
Solução ótima, pois os coeficientes da variáveis 
não básica, X1, E1, A1 na linha W são não 
positivos. Fim da Fase 1.
Fase 2- elimina-se a coluna da variável artificial A1. 
Além disso, a variável básica X2 da solução ótima 
da Fase 1 deve ser eliminada 
21 34 xxZMax 
21 34 xxZ 
Algoritmo Simplex
VB X1 X2 E1 A1 F2 VSM
X2 2/5 1 - 1/5 1/5 0 4 
F2 1 0 0 0 1 8 
W 0 0 0 0 0 0 
21 34 xxZ 
VB X1 X2 E1 F2 VSM
X2 2/5 1 - 1/5 0 4 
F2 1 0 0 1 8 
Z -3 x (2/5)= 
-6/5
-3 (1)= -3
-3 (-1/5)= 
0,6
0 
-3. (4) =
-12
Z = 4X1 + 3X2
Algoritmo Simplex
VB X1 X2 E1 F2 VSM
X2 2/5 1 - 1/5 0 4 
F2 1 0 0 1 8 
Z 6/5 3 -0,6 0 12
Solução não ótima, pois os coeficientes das 
variáveis não básicas (X1,E1) na linha Z possuem 
coeficientes negativos. Observa-se que a função 
deve ser maximizada.
Algoritmo Simplex
VB X1 X2 E1 F2 VSM
X2 2/5 1 - 1/5 0 4 
F2 1 0 0 1 8 
Z 6/5 3 -0,6 0 12
Problema sem solução!!!
Algoritmo Simplex
Algoritmo Simplex
Atividades!
• Pesquise sobre solução ótima degenerada.
• Problemas que não existe uma solução ótima.