Aula 6 Método Simplex

Prévia do material em texto

Reinaldo F. Santos 11
Pesquisa Operacional
Pesquisa Operacional
CURSO SUPERIOR DE TECNOLOGIA EM LOGÍSTICA E 
TRANSPORTE
Professor: REINALDO FAGUNDES DOS SANTOS
Reinaldo F. Santos 22
Pesquisa Operacional
Semana Assunto
01 Apresentação da Disciplina e Introdução à Pesquisa Operacional;
02 Modelagem de Problemas de Otimização;
03 Modelagem de Problemas de Otimização (continuação)
04 Programação Linear;
05 Solução Gráfica;
06 Método Simplex;
07 Método Simplex (continuação);
08 A ferramenta Solver (laboratório);
09 Prova 1;
10 Correção e Comentários da Prova 1;
11 O problema de Transporte;
12 O problema de Transporte (continuação);
13 Simulação ( O método Monte Carlo);
14 Fundamentos da teoria das Restrições e solução de um problema;
15 Apresentação dos Trabalhos em Grupo;
16 Apresentação dos Trabalhos em Grupo;
17 Prova 2;
18 Correção e comentários da Prova 2; Prova ou Trabalho Substitutivo.
Reinaldo F. Santos 33
Pesquisa Operacional
MÉTODO SIMPLEX
O modelo de programação linear pode ser 
resolvido por um método de solução de sistema de 
equações lineares. 
O processo que será apresentado no exemplo a 
seguir, retirado de ANDRADE (2000), é bastante 
intuitivo e tem por finalidade apresentar a 
metodologia utilizada pelo método Simplex.
Reinaldo F. Santos 44
Pesquisa Operacional
"Uma marcenaria deseja estabelecer uma 
programação diária de produção. Atualmente, a 
oficina faz apenas dois produtos: mesa e armário, 
ambos de um só modelo.
(Para efeito de simplificação)
Reinaldo F. Santos 55
Pesquisa Operacional
A marcenaria tem limitações em somente dois 
recursos: madeira e mão-de-obra
As disponibilidades diárias são mostradas na 
tabela a seguir.
Recurso Disponibilidade
Madeira 12m2
Mão-de-obra 8 H.h
Reinaldo F. Santos 66
Pesquisa Operacional
•O processo de produção é tal que, para fazer uma 
mesa a fábrica gasta 2 m2 de madeira e 2 H.h de 
mão-de-obra. 
•Para fazer um armário, a fábrica gasta 3 m2 de 
madeira e 1 H.h de mão de obra.
•Além disso, o fabricante sabe que cada mesa dá
uma margem de contribuição para o lucro de $ 4 e
cada armário de $ 1.
Reinaldo F. Santos 77
Pesquisa Operacional
Fases do Estudo de Pesquisa Operacional
(1) definição do problema;
(2) construção do modelo;
(3) solução do modelo;
(4) validação do modelo;
(5) implementação da solução.
Reinaldo F. Santos 88
Pesquisa Operacional
•Qual o programa de produção que maximiza a
margem de contribuição total para o lucro."
Reinaldo F. Santos 99
Pesquisa Operacional
Fases do Estudo de Pesquisa Operacional
(1) definição do problema;
(2) construção do modelo;
(3) solução do modelo;
(4) validação do modelo;
(5) implementação da solução.
Reinaldo F. Santos 1010
Pesquisa Operacional
A função objetivo é:
Lucro: z = 4 M + A
As variáveis de decisão envolvidas no problema são:
M: quantidade a produzir de mesas
A: quantidade a produzir de armários
Para as restrições:
Madeira: 2 M + 3 A <= 12
Mão-de-obra: 2 M + A <= 8
M, A >= 0
Reinaldo F. Santos 1111
Pesquisa Operacional
Introduzindo as variáveis de folga, o problema a ser 
resolvido passa a ser:
Maximizar: z = 4 M + A
Sujeito a:
2 M + 3 A + s1 = 12
2 M + A + s2 = 8
M, A, s1, s2 >= 0
Reinaldo F. Santos 1212
Pesquisa Operacional
O problema se transformou em encontrar a solução do 
sistema de equações lineares que maximiza o lucro. 
Como neste caso o número de variáveis (m = 4) é superior 
ao número de equações (n = 2), o sistema é 
indeterminado, apresentando infinitas soluções.
No entanto, todas as variáveis devem ser maiores ou 
iguais a zero. Atribuir zero a uma variável significa não 
produzir um dos produtos (se a variável for M ou A) ou 
utilizar toda a disponibilidade de recursos (se a variável for 
f1 ou f2). 
Reinaldo F. Santos 1313
Pesquisa Operacional
Desta forma, podemos encontrar soluções para o sistema 
de equações zerando duas variáveis (n - m = 2) e 
encontrando o valor para as duas variáveis restantes. 
Teremos que resolver então
sistemas de equações lineares.
Reinaldo F. Santos 1414
Pesquisa Operacional
c.1) Variáveis não-básicas: M = 0 ; A = 0
temos as variáveis básicas f1 = 12 ; f2 = 8
dando o lucro z = 0
c.2) Variáveis não-básicas: M = 0 ; f1 = 0
temos as variáveis básicas A = 4 ; f2 = 4
dando o lucro z = 4
c.3) Variáveis não-básicas: M = 0 ; f2 = 0
temos as variáveis básicas A = 8 ; f1 = -12
como f1 < 0, a solução obtida é INVIÁVEL.
Reinaldo F. Santos 1515
Pesquisa Operacional
c.4) Variáveis não-básicas: A = 0 ; f1 = 0
temos as variáveis básicas M = 6 ; f2 = -4
como f2 < 0, a solução obtida é INVIÁVEL.
c.5) Variáveis não-básicas: A = 0 ; f2 = 0
temos as variáveis básicas M = 4 ; f1 = 4
dando o lucro z = 16
c.6) Variáveis não-básicas: f1 = 0 ; f2 = 0
temos as variáveis básicas M = 3 ; A = 2
dando o lucro z = 14
Reinaldo F. Santos 1616
Pesquisa Operacional
Procedimento do Método Simplex 
(Problemas de Maximização)
•Passo 1: Monta-se o tableau que corresponde à origem; 
•Passo 2: O primeiro tableau é transformado em um segundo, que 
apresenta uma solução melhorada, por meio de uma série de 
cálculos; 
•Passo 3: Quando da criação de cada tableau, existe um teste para 
verificar se a solução ótima foi ou não atingida;
•Passo 4: Esse procedimento se repete até que se chegue a um 
tableau que reflita a solução ótima;
Reinaldo F. Santos 1717
Pesquisa Operacional
Introduzindo as variáveis de folga, o problema a ser 
resolvido passa a ser:
Maximizar: z = X + 2Y
Sujeito a:
3X + 4Y <=24
5X + 2Y <= 20
X,Y >= 0
Reinaldo F. Santos 1818
Pesquisa Operacional
Introduzindo as variáveis de folga, o problema a ser 
resolvido passa a ser:
Maximizar: z = X + 2Y
Sujeito a:
3X + 4Y + 1S1=24
5X + 2Y + 1S2= 20
X,Y ,S1,S2>= 0
Reinaldo F. Santos 1919
Pesquisa Operacional
Introduzindo as variáveis de folga, o problema a ser 
resolvido passa a ser:
Maximizar: z = X + 2Y + 0S1 + 0S2
Sujeito a:
3X + 4Y + 1S1 + 0S2=24
5X + 2Y + 0S1 + 1S2= 20
X,Y ,S1,S2>= 0
Reinaldo F. Santos 2020
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24
0 S2 5 2 0 1 20
Linha Z
Linha C-Z
Primeiro Tableau
Reinaldo F. Santos 2121
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3(0) 4(0) 1(0) 0(0) 24(0)
0 S2 5(0) 2(0) 0(0) 1(0) 20(0)
Linha Z 0 0 0 0 0
Linha C-Z
Primeiro Tableau
multiplicado por X, Y, Cj multiplicado por X, Y, 
S1 e S2 (que são zero) 
Linha Z
Reinaldo F. Santos 2222
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24
0 S2 5 2 0 1 20
Linha Z 0 0 0 0
Linha C-Z 1 2 0 0
Primeiro Tableau
Linha de Objetivo 
Subtraído da Linha Z
 Linha C-Z
Reinaldo F. Santos 2323
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24
0 S2 5 2 0 1 20
Linha Z 0 0 0 0
Linha C-Z 1 2 0 0
Primeiro Tableau
Reinaldo F. Santos 2424
Pesquisa Operacional
Qual a Variável que entra 
noTableau?
Reinaldo F. Santos 2525
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24
0 S2 5 2 0 1 20
Linha Z 0 0 0 0Linha C-Z 1 2 0 0
Primeiro Tableau
Variável Y é a que oferece Variável Y é a que oferece 
maior Margem
Reinaldo F. Santos 2626
Pesquisa Operacional
Qual a Variável que sai do 
Tableau?
Reinaldo F. Santos 2727
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24 24/4
0 S2 5 2 0 1 20 20/2
Linha Z 0 0 0 0
Linha C-Z 1 2 0 0
Primeiro Tableau
Dividir bj pelo coeficiente Dividir bj pelo coeficiente 
da variável que sairá.
Reinaldo F. Santos 2828
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24 6
0 S2 5 2 0 1 20 10
Linha Z 0 0 0 0
Linha C-Z 1 2 0 0
Primeiro Tableau
S1 oferece o menor valor, S1 oferece o menor valor, 
portanto deve sair
Reinaldo F. Santos 2929
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24
0 S2 5 2 0 1 20
Linha Z 0 0 0 0
Linha C-Z 1 2 0 0
Primeiro Tableau
PivôPivô
Reinaldo F. Santos 3030
Pesquisa Operacional
Determinar a nova linha 
principal
Reinaldo F. Santos 3131
Pesquisa Operacional
Variável X Y S1 S2 bj
Antiga Linha 
Principal 3 4 1 0 24
dividida pelo pivô 3/4 4/4 1/4 0/4 24/4
Nova linha 
principal 3/4 1 1/4 0 6
Reinaldo F. Santos 3232
Pesquisa Operacional
Determinar a nova linha da 
variável S2
Reinaldo F. Santos 3333
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
0 S1 3 4 1 0 24
0 S2 5 2 0 1 20
Linha Z 0 0 0 0
Linha C-Z 1 2 0 0
Primeiro Tableau
IntersecçãoIntersecção
Reinaldo F. Santos 3434
Pesquisa Operacional
Variável X Y S1 S2 bj
Nova Linha 
Principal 3/4 1 1/4 0 6
dividida pela 
intersecção de Y 
com S2 (2) 3/4 (2) 1 (2) 1/4 (2) 0 (2) 6 (2)
Resultante 3/2 2 1/2 0 12
Reinaldo F. Santos 3535
Pesquisa Operacional
Variável X Y S1 S2 bj
Antiga Linha de S2 5 2 0 1 20
(Menos resultante) 3/2 2 1/2 0 12
Nova linha de S2 7/2 0 -1/2 1 8
Reinaldo F. Santos 3636
Pesquisa Operacional
Segundo Tableau Incompleto
Reinaldo F. Santos 3737
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
2 Y 3/4 1 1/4 0 6
0 S2 7/2 0 -1/2 1 8
Linha Z
Linha C-Z
Primeiro Tableau
Reinaldo F. Santos 3838
Pesquisa Operacional
Calcular linha Z e linha C-Z 
do Segundo Tableau
Reinaldo F. Santos 3939
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
2 Y 3/4 (2) 1(2) 1/4 (2) 0 (2) 6 (2)
0 S2 7/2 (0) 0 (0) -1/2 (0) 1 (0) 8 (0)
Linha Z 3/2 2 1/2 0 12
Linha C-Z
Primeiro Tableau
multiplicado por X, Y, Cj multiplicado por X, Y, 
S1 e S2) (que são 2 e 0) 
 Linha Z
Reinaldo F. Santos 4040
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
2 Y 3/4 (2) 1(2) 1/4 (2) 0 (2) 6 (2)
0 S2 7/2 (0) 0 (0) -1/2 (0) 1 (0) 8 (0)
Linha Z 3/2 2 1/2 0 12
Linha C-Z -1/2 0 -1/2 0
Primeiro Tableau
Linha de Objetivo 
Subtraído da Linha Z
 Linha C-Z
Reinaldo F. Santos 4141
Pesquisa Operacional
O Segundo Tableau 
completo
Reinaldo F. Santos 4242
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
2 Y 3/4 1 1/4 0 6 
0 S2 7/2 0 -1/2 1 8 
Linha Z 3/2 2 1/2 0 12
Linha C-Z -1/2 0 -1/2 0
Primeiro Tableau
Reinaldo F. Santos 4343
Pesquisa Operacional
Verificamos que na linha C-Z 
todos os valores são 
negativos ou iguais a zero 
portanto chegamos na 
solução ótima.
Reinaldo F. Santos 4444
Pesquisa Operacional
Variáveis de Decisão
1 2 0 0 Objetivo
Cj
Variáveis 
na 
Solução
X Y S1 S2 bj bj/aij
2 Y 3/4 1 1/4 0 6 
0 S2 7/2 0 -1/2 1 8 
Linha Z 3/2 2 1/2 0 12
Linha C-Z -1/2 0 -1/2 0
Primeiro Tableau
Portanto a solução ótima é 
Y=6 e X=0 (X está fora do 
Portanto a solução ótima é 
Y=6 e X=0 (X está fora do 
Tableau)
Reinaldo F. Santos 4545
Pesquisa Operacional
Observamos que:
z = X + 2Y = 0 + 2(6) = 12
Sujeito a:
3X + 4Y <=24 [3(0) + 4(6) <=24]
5X + 2Y <= 20 [5(0) + 2(6) <=20]
X,Y >= 0
Reinaldo F. Santos 4646
Pesquisa Operacional
Observamos que Z=