Introdução à Programação Linear
Parte II
Elementos de
Economia Matemática 2
Prof. Alexandre Stamford
O modelo do problema
Max
x1 ,x2
s.a
H .H .
H .M .
L  4 x1  x2
9 x1  x2  18
3x1  x2  12
x1  0
x2  0
O Método SIMPLEX
Forma-se um sistema de equações
lineares introduzido as variáveis de folga:
L  4 x1  x2
 0
9 x1  x2  x3
 18
3x1  x2
 x4  12
O Método SIMPLEX
Um quadro pode ser formado com os
coeficientes das variáveis.
L
x3
x4
x1
-4
9
3
x2
-1
1
1
x3
0
1
0
x4
0
0
1
Observe o formato das colunas de x3 e x4
Observe os coeficientes de x1 e x2 na linha da
função objetivo.
Para auxiliar pode-se utilizar uma coluna para
destacar os valores das variáveis básicas.
0
18
12
O Método SIMPLEX
A primeira pergunta é qual a variável que,
saindo da base, aumentaria mais rapidamente
o valor da função objetivo.
L
x3
x4
x1
-4
9
3
x2
-1
1
1
x3
0
1
0
x4
0
0
1
A pergunta é respondida observando-se qual a
variável que tem o coeficiente mais negativo na
linha referente à função objetivo.
No caso, a variável x1
0
18
12
O Método SIMPLEX
 Como x1 aumenta a função objetivo mais rapidamente, qual o
valor máximo que x1poderá assumir sem romper as restrições?
L
x3
x4
x1
-4
9
3
x2
-1
1
1
x3
0
1
0
x4
0
0
1
0
18
12
Na primeira restrição x1aumenta até 2 (18/9) fazendo com
que x3 se anule, saindo da base.
Na segunda restrição x1aumenta até 4 (12/3) fazendo com
que x4 se anule, saindo da base.
x1 toma então o lugar de x3 na base, entrando na linha
desta mesma variável básica.
O Método SIMPLEX
Com a decisão tomada, a linha de x3 deve
refletir agora o valor de x1, consegue-se isto
fazendo o coeficiente de x1 igual a 1 naquela
linha e trocando-se o nome à direita do quadro.
L
x1
x4
x1
-4
1
3
x2
-1
1/9
1
x3
0
1/9
0
x4
0
0
1
Para que o quadro fica passível de análise é
necessário escaloná-lo sendo a linha de x1 a pivô.
0
2
12
O Método SIMPLEX
O novo quadro será:
L
x1
x4
x1
0
1
0
x2
- 5/9
1/9
2/3
x3
4/9
1/9
- 1/3
x4
0
0
1
8
2
6
Observe o formato das colunas de x1 e x4
Observe os coeficientes de x2 e x3 na linha da
função objetivo.
A coluna à direita destaca os valores das novas
variáveis básicas e do lucro.
O Método SIMPLEX
A primeira pergunta pode ser repetida: qual a
variável que, saindo da base, aumentaria mais
rapidamente o valor da função objetivo?
L
x1
x4
x1
0
1
0
x2
- 5/9
1/9
2/3
x3
4/9
1/9
- 1/3
x4
0
0
1
A pergunta é respondida observando-se que a
única variável que tem coeficiente negativo na
linha referente à função objetivo é x2.
Até quanto o valor x2 pode aumentar?
8
2
6
O Método SIMPLEX
 Pode-se automaticamente localizar o mínimo das razões
dos valores das variáveis básicas com os coeficientes de x2.
L
x1
x4
x1
0
1
0
x2
- 5/9
1/9
2/3
x3
4/9
1/9
- 1/3
2
Nova linha pivô
1
x4
0
0
1
 18
9
6
2
3
 9 Mínimo
8
2
6
O Método SIMPLEX
 Multiplicando-se a linha de x2 por 3/2, trocando-se o
nome da variável e escalonando resulta em:
L
x1
x2
x1
0
1
0
x2
0
0
1
x3
1/6
1/6
- 1/2
x4
5/6
- 1/6
1 1/2
13
1
9
Observe novamente as colunas de x1 e x2 (as VB’s)
Observe também os coeficientes de x3 e x4 (as VNB’s ) na
linha da função objetivo.
A coluna à direita destaca os valores das novas variáveis
básicas e do lucro.
A solução é ótima dado os coeficientes positivos.
O Algoritmo SIMPLEX
1. Acrescentar variáveis
de folga ao problema.
2. Achar uma solução viável
definindo as VB e as VNB
3. Identificar a VNB com
coeficiente mais negativo
na função objetivo (VBE)
4. Escolher a menor das
razões entre os
coeficientes da VBE e os
valores das VB’s
5. Identificar a linha em que isto
ocorre e nominar a VB como VBS
6. Tornar o coeficiente da
VBE igual a 1 na linha da
VBS e escalonar o sistema
7. A VBE torna-se VB e a
VBS torna-se VNB
SIM 8. Existe alguma VB com
coeficiente negativo na
função objetivo?
NÃO
9. Solução Ótima
Aplicando o SIMPLEX
no Exemplo 2
Uma grande fábrica de móveis dispõe em estoque
de 300m de tábuas, 600m de pranchas e 500m de
painéis de aglomerado.
Oferece normalmente 4 modelos de móveis:
Escrivaninha, Mesa, Armário e Prateleira.
Os modelos são vendidos respectivamente por
$100,00; $80,00; $120,00; $30,00.
E consomem:
Escrivaninha: 1m tábua, 3m de painéis.
Mesa: 1m tábua, 1m prancha, 2m painéis.
Armário: 1m tábua, 1m prancha, 4 painéis.
Prateleira: 4m tábua, 2 de prancha.
O modelo do problema
Max L  100 xE  80 xM  120 x A  30 xP
x E , xM , x A , x P
Tb
xE  xM  x A  4 xP  300
Pr
xM  x A  2 x P  600
Pa 3x E  2 xM  4 x A
xE  0
xM  0
xA  0
 500
xP  0
O Método SIMPLEX
Introduzido as variáveis de folga.
L 100 xE  80 xM 120 xA  30 xP  0
xE  xM  xA  4 xP  xF1  300
xM  xA  2 xP  xF 2  600
3xE  2 xM  4 x A  xF 3  500
O Método SIMPLEX
O quadro é:
xE
L
-100
xF1
1
xF2
0
xF3
3
xM xA
-80 -120
1
1
1
1
2
4
xP xF1 xF2 xF3
-30
0
0
0
4
1
0
0
2
0
1
0
0
0
0
1
Observe as colunas das variáveis básicas e os
coeficientes das variáveis não básicas .
Os valores das VB’s estão a direita.
Quem entra na base é xA e quem sai é xF3
A linha pivô é a linha da VBS xF3.
0
300
600
500
O Método SIMPLEX
O novo quadro é:
L
xF1
xF2
xA
xE
-10
1/4
- 3/4
3/4
xM
-20
1/2
1/2
1/2
xA
0
0
0
1
xP
-30
4
2
0
xF1
0
1
0
0
xF2
0
0
1
0
xF3
30
15000
- 1/4 175
- 1/4 475
1/4 125
xP é a variável que entrará na base no lugar de
xF1
Dividindo-se por 4 e escalonando....
O Método SIMPLEX
O novo quadro é:
L
xP
xF2
xA
xE
-8,125
0,0625
-0,875
0,75
xM
-16,25
0,125
0,25
0,5
xA
0
0
0
1
xP
0
1
0
0
xF1
7,5
0,25
-0,5
0
xF2
0
0
1
0
xF3
28,13 16312,5
-0,06
43,75
-0,13
387,5
0,25
125
xM é a variável que entrará na base no lugar de
xA, pois
43,75/0,125=350
387,5/0,25=1550 e
125/0,5=250
O Método SIMPLEX
O novo quadro é:
L
xP
xF2
xM
xE
16,25
-0,125
-1,25
1,5
xM
0
0
0
1
xA
32,5
-0,25
-0,5
2
xP
0
1
0
0
xF1
7,5
0,25
-0,5
0
xF2
0
0
1
0
A solução é ótima, não há coeficientes
negativos.
xF3
36,25
-0,13
-0,25
0,5
20375
12,5
325
250