PROGRAMAÇÃO LINEAR
17 DE SETEMBRO DE 2008
1. Definição
2. Aplicações
3. Problema Ilustrativo
3.1 Enunciado
3.2 Dados Físicos e Econômicos
3.3 Modelo Matemático
3.4 Balanço de Informação e Varáveis de Projeto
3.5 Critério e Função Objetivo
3.6 Restrições
3.7 Região Viável
3.8 Resolução
3.9 Algoritmo SIMPLEX (conjuntos ativos)
3.10 Algoritmo Karmarkar (ponto interior)
1. DEFINIÇÃO
O Problema de Programação Linear
é um tipo especial de problema de otimização em que
a Função Objetivo é linear
F(x) = c1 x1 + c2 x2 + ... + cn xn
todas as Restrições são lineares
a11 x1 + a12 x2 + ... + a1n xn  b1
a21 x1 + a22 x2 + ... + a2n xn  b2
...
am1 x1 + am2 x2 + ... + amn xn  bm
2. APLICAÇÕES
planejamento de produção industrial
transportes: rodoviário, ferroviário, fluvial, marítimo, aéreo
logística
produção e distribuição de energia
militar
etc...
3. PROBLEMA ILUSTRATIVO
Planejamento da Produção de uma Refinaria
(adaptado de Edgar & Himmelblau, pg. 254)
3.1 ENUNCIADO
Uma refinaria pode receber dois tipos de óleo cru: O1 e O2.
A partir de cada um deles, pode-se produzir:
- gasolina (G)
- querosene (Q)
- óleo combustível (C)
- óleo residual (R).
Determinar
- quantos barris/dia (b/d) a refinaria deve adquirir de cada óleo
cru (x1, x2).
- a partir de cada óleo, quanto a refinaria deve produzir de
- gasolina (x31, x32)
- querosene (x41, x42)
- óleo combustível (x51, x52)
- óleo residual (x61, x62)
Para se resolver este problema, é preciso conhecer:
Preço de cada óleo cru
Custo do processamento
Perfil de produção: quanto se pode produzir de gasolina,
querosene, óleo combustível e óleo residual a partir de cada óleo
cru.
Preços de venda dos produtos
Limites de produção
3.2 DADOS FÍSICOS E ECONÔMICOS
Processamento do Óleo O1:
- preço do óleo: p1 = 24 $/b
- custo de processamento: c1 = 0,50 $/b
- perfil de produção: gasolina 80%, querosene 5%, óleo combustível
10% e óleo residual 5%.
Processamento do Óleo O2:
- preço do óleo: p2 = 15 $/b
- custo de processamento: c2 = 1,0 $/b
- perfil de produção: gasolina 44%, querosene 10%, óleo combustível
35% e óleo residual 10%.
Preço de venda
dos produtos
p3 = 36 $/b (gasolina)
p4 = 24 $/b (querosene)
p5 = 21 $/b (óleo combustível)
p6 = 10 $/b (óleo residual)
Produção máxima de cada produto
x3max = 24.000 b/d (x3 = x31 + x32)
x4max = 2.000 b/d (x4 = x41 + x42)
x5max = 6.000 b/d (x5 = x51 + x52)
Dados resumidos em Fluxograma
C1 = 0,50 $/b
O1
p1 = 24 ($/b)
x1 (b/d)
0,80 b3/b1
0,05 b4/b1
0,10 b5/b1
0,05 b6/b1
x31
x41
x51
x61
PRODUTOS
CRÚS
C2 = 1 $/b
O2
p2 = 15 ($/b)
x2 (b/d)
x32
G x3(b/d) p3 = 36($/b); x3max= 24.000(b/d)
x42
Q x4(b/d) p4 = 24($/b); x4max= 2.000(b/d)
x52
C x5(b/d) p5 = 21($/d); x5max= 6.000(b/d)
x62
R x6(b/d) p6=10($/b)
0,44 b3/b2
0,10 b4/b2
0,36 b5/b2
0,10 b6/b2
Como em qualquer problema de Análise de Processos
Modelo Matemático ?
Balanço de Informação ?
Variáveis de Projeto ?
Critério ?
Função Objetivo ?
Restrições ?
Região Viável ?
3.3 MODELO MATEMÁTICO
C1 = 0,50 $/b
O1
p1 = 24 ($/b)
x1 (b/d)
0,80 b3/b1
0,05 b4/b1
0,10 b5/b1
0,05 b6/b1
x31
x41
x51
x61
PRODUTOS
CRÚS
C2 = 1 $/b
O2
0,44 b3/b2
p2 = 15 ($/b)
0,10 b4/b2
x2 (b/d)
0,36 b5/b2
x32
G x3(b/d)
p3 = 36($/b); x3max= 24.000(b/d)
x42
Q x4(b/d)
p4 = 24($/b); x4max= 2.000(b/d)
x52
C x5(b/d)
p5 = 21($/d); x5max= 6.000(b/d)
x62
R x6(b/d)
p6=10($/b)
0,10 b6/b2
Balanços de Massa
Gasolina
: 0,80 x1 + 0,44 x2 = x3
Querosene : 0,05 x1 + 0,10 x2 = x4
Combustível: 0,10 x1 + 0,36 x2 = x5
Residual
: 0,05 x1 + 0,10 x2 = x6
3.4 BALANÇO DE INFORMAÇÃO E VARIÁVEIS DE PROJETO
Balanço de Informação
C1 = 0,50 $/b
O1
p1 = 24 ($/b)
x1 (b/d)
0,80 b3/b1
0,05 b4/b1
0,10 b5/b1
0,05 b6/b1
x31
x41
x51
G=V–N=6–4G=2
Variáveis de Projeto: x1 e x2
x61
PRODUTOS
CRÚS
C2 = 1 $/b
O2
0,44 b3/b2
p2 = 15 ($/b)
0,10 b4/b2
x2 (b/d)
0,36 b5/b2
x32
G x3(b/d)
p3 = 36($/b); x3max= 24.000(b/d)
x42
Q x4(b/d)
p4 = 24($/b); x4max= 2.000(b/d)
x52
C x5(b/d)
p5 = 21($/d); x5max= 6.000(b/d)
x62
R x6(b/d)
p6=10($/b)
0,10 b6/b2
Balanços de Massa
Gasolina
: 0,80 x1 + 0,44 x2 = x3
Querosene : 0,05 x1 + 0,10 x2 = x4
Combustível: 0,10 x1 + 0,36 x2 = x5
Residual
: 0,05 x1 + 0,10 x2 = x6
3.5 CRITÉRIO E FUNÇÃO OBJETIVO
C1 = 0,50 $/b
0,80 b3/b1
O1
p1 = 24 ($/b)
x1 (b/d)
0,05 b4/b1
0,10 b5/b1
0,05 b6/b1
Critério
x31
x41
Maximização do Lucro
x51
x61
PRODUTOS
CRÚS
C2 = 1 $/b
O2
0,44 b3/b2
p2 = 15 ($/b)
0,10 b4/b2
x2 (b/d)
0,36 b5/b2
x32
G x3(b/d)
p3 = 36($/b); x3max= 24.000(b/d)
x42
Q x4(b/d)
p4 = 24($/b); x4max= 2.000(b/d)
x52
C x5(b/d)
p5 = 21($/d); x5max= 6.000(b/d)
x62
R x6(b/d)
p6=10($/b)
0,10 b6/b2
Função Objetivo
L = R – CMP - CP
Receita (R): 36 x3 + 24 x4 + 21 x5 + 10 x6
Custos de MatPrim (CMP) : 24 x1 + 15 x2
Custos Processamento (CP): 0,50 x1 + x2
L = 36 x3 + 24 x4 + 21 x5 + 10 x6 - 24 x1 - 15 x2 - 0,50 x1 - x2
3.6 RESTRIÇÕES
C1 = 0,50 $/b
O1
p1 = 24 ($/b)
x1 (b/d)
0,80 b3/b1
0,05 b4/b1
0,10 b5/b1
0,05 b6/b1
x31
x41
Min f(x)
x
s.a.: g(x)  0
h(x) = 0
Função Objetivo
Variáveis de Projeto
Restr. desigualdade
Restr. igualdade
x51
x61
PRODUTOS
CRÚS
C2 = 1 $/b
O2
0,44 b3/b2
p2 = 15 ($/b)
0,10 b4/b2
x2 (b/d)
0,36 b5/b2
x32
G x3(b/d)
p3 = 36($/b); x3max= 24.000(b/d)
x42
Q x4(b/d)
p4 = 24($/b); x4max= 2.000(b/d)
x52
C x5(b/d)
p5 = 21($/d); x5max= 6.000(b/d)
x62
R x6(b/d)
p6=10($/b)
0,10 b6/b2
Restrições de Igualdade (modelo)
Gasolina
: 0,80 x1 + 0,44 x2 = x3
Querosene : 0,05 x1 + 0,10 x2 = x4
Combustível : 0,10 x1 + 0,36 x2 = x5
Residual
: 0,05 x1 + 0,10 x2 = x6
Restrições de Desigualdade
Gasolina
: x3  24.000
Querosene : x4  2.000
Combustível : x5  6.000
Óleos crus : x1  0 e x2  0
Incorporando as Restrições de Igualdade
à Função Objetivo
Gasolina
: 0,80 x1 + 0,44 x2 = x3
Querosene : 0,05 x1 + 0,10 x2 = x4
Combustível : 0,10 x1 + 0,36 x2 = x5
Residual
: 0,05 x1 + 0,10 x2 = x6
L = 36 x3 + 24 x4 + 21 x5 + 10 x6 - 24 x1 - 15 x2 - 0,50 x1 - x2
Resulta
L(x) = 8,1 x1 + 10,8 x2
Enunciado Formal do Problema
max L(x) = 8,1 x1 + 10,8 x2
{x1, x2}
s.a.: 0,80 x1 + 0,44 x2  24.000
0,05 x1 + 0,10 x2  2.000
0,10 x1 + 0,36 x2  6.000
x1  0
x2  0
Função Objetivo
L(x) = 8,1 x1 + 10,8 x2 (linear)
x2 = L/10,8 – (8,1/10,8) x1
(família de retas)
20
L=648.000
L=324.000
x2
L=243.000
10
L=162.000
(1.000 b/d)
L=81.000
0
0
10
20
x1 (1.000 b/d)
30
40
3.7 REGIÃO VIÁVEL
0,80 x1 + 0,44 x2  24.000 (gasolina)
0,05 x1 + 0,10 x2  2.000 (querosene)
0,10 x1 + 0,36 x2  6.000 (combustível)
x1  0
x2  0
20
B
Qualquer ponto no interior ou sobre a fronteira
da Região Viável é uma Solução Viável
óleo
x2
10
C
querosene
D
região convexa !
(1.000 b/d)
0
A
gasolina
0
10
20
x1 (1.000 b/d)
E
30
40
3.8 RESOLUÇÃO
Solução Ótima
É a solução viável correspondente ao valor máximo do Lucro
Em duas dimensões, a identificação visual da Solução Ótima é
imediata.
20
B
243.000
324.000
C
162.000
x2
óleo
10
querosene
D
81.000
(1.000 b/d)
Solução (D):
(26.207, 6.897)
(L=286.764)
gasolina
0
A
E
0
10
20
x1
(1.000 b/d)
30
40
Com outros valores dos parâmetros físicos e econômicos, a
inclinação da Função Objetivo seria outra e a solução seria outra.
A Solução Ótima se localiza em pelo menos um dos Vértices
da Região Viável
20
B
óleo
x2
10
C
Solução (C):
(14.000, 13.000)
(L = 637.000)
querosene
D
(1.000 b/d)
gasolina
0
A
E
0
10
20
x1 (1.000 b/d)
30
40
Como automatizar a busca pelo o vértice ótimo?
Busca Exaustiva
Método do Ponto
Interior
Método dos
Conjuntos Ativos
Métodos da busca exaustiva e dos conjuntos ativos
Ignorando os pontos interiores, restringindo a busca à fronteira da
região viável e, na fronteira, restringindo a busca aos vértices.
20
B
243.000
C
324.000
óleo
x2
10
querosene
162.000
D
(1.000 b/d)
81.000
0
A
Solução:
(26.207, 6.897)
(L=286.764)
gasolina
E
0
0
10
20
x1
(1.000 b/d)
30
(como???)
40
Para tanto, os passos são os seguintes:
1. Restringir a busca à fronteira da região viável
Transformando as restrições de desigualdade em
restrições de igualdade
2. Restringir a busca, na fronteira, aos vértices
Busca exaustiva: examinar
todos os vértices das restrições

explosão combinatória
Conjuntos Ativos: examinar os
vértices da região viável

método Simplex
Transformando as restrições de desigualdade em
restrições de igualdade
No método dos conjuntos ativos, pode ser operada
com o auxílio do conceito de
Variável de Folga
Folga
Qualquer ponto (x1, x2) no interior da Região Viável corresponde a
uma produção inferior à máxima de cada produto (folga, fi).
Exemplo: ponto I (folgas na produção de gasolina, querosene e óleo)
F
20
B
Gasolina
: 0,80 x1 + 0,44 x2 = x3=12.400 (24.000)
Querosene : 0,05 x1 + 0,10 x2 = x4 = 1.500 (2.000)
Combustível: 0,10 x1 + 0,36 x2 = x5 = 4.600 (6.000)
óleo
C
G
x2
I
10
querosene
D
f1 = 11.600 b/d
f2 =
500 b/d
f3 = 1.400 b/d
(1.000 b/d)
0
A
0
10
gasolina
20
x1 (1.000 b/d)
E
30
H
40
Folga
Qualquer ponto (x1, x2) localizado sobre um restrição corresponde à
produção máxima do produto respectivo.
Exemplo: ponto J (produção máxima de óleo = 6.000 b/d: f3 = 0)
Gasolina
: 0,80 x1 + 0,44 x2 = x3=14.111 (24.000)
F Querosene : 0,05 x + 0,10 x = x = 1.889 (2.000)
1
2
4
20 Combustível : 0,10 x1 + 0,36 x2 = x5 = 6.000 (6.000)
B
óleo
13,9
x2
C
f1 = 9.889 b/d
querosene
f2 =
111 b/d
f3 =
0 b/d
10
(1.000 b/d)
0
A
J
G
D
gasolina
0
10
20
x1 (1.000 b/d)
E
30
H
40
Folga
Qualquer ponto (x1, x2) localizado sobre um vértice corresponde à
produção máxima dos 2 produtos respectivos.
Exemplo: ponto D (produção máxima de gasolina e de querosene:
f1 = 0, f2 = 0) Gasolina
: 0,80 x1 + 0,44 x2 = x3=24.000 (24.000)
F Querosene : 0,05 x1 + 0,10 x2 = x4 = 2.000 (2.000)
20
Combustível : 0,10 x1 + 0,36 x2 = x5 = 3.459 (6.000)
B
óleo
C
G
x2
10
querosene
D f1 =
0 b/d
f2 =
0 b/d
f3 = 2.541 b/d
(1.000 b/d)
0
A
gasolina
0
10
20
x1 (1.000 b/d)
E
30
H
40
A desejada transformação das restrições de desigualdade em
restrições de igualdade é obtida
incorporando as folgas às restrições de desigualdade
Incorporando as folgas fi às restrições de desigualdade
Max L(x) = 8,1 x1 + 10,8 x2
{x1, x2}
s.a.: 0,80 x1 + 0,44 x2  24.000 (gasolina)
0,05 x1 + 0,10 x2  2.000 (querosene)
0,10 x1 + 0,36 x2  6.000 (combustível)
x1  0
x2  0
Max L(x) = 8,1 x1 + 10,8 x2
{x1, x2}
s.a.: 0,80 x1 + 0,44 x2 + f1
0,05 x1 + 0,10 x2 + f2
0,10 x1 + 0,36 x2 + f3
x1  0
x2  0
= 24.000 (gasolina)
= 2.000 (querosene)
= 6.000(combustível)
As restrições de igualdade formam agora um sistema de
equações lineares.
0,80 x1 + 0,44 x2 +f1 = 24.000 (gasolina)
0,05 x1 + 0,10 x2 +f2 = 2.000 (querosene)
0,10 x1 + 0,36 x2 +f3 = 6.000(combustível)
V = 5 : N = 3 : G = 2 !!!
A qualquer par de valores das variáveis de projeto, corresponde
uma solução. Logo, o problema exibe uma infinidade de soluções
viáveis.
Mas, agora, todas localizadas na fronteira da região viável
Uma solução trivial é: x1 = 0, x2 = 0
Corresponde a uma vértice especial: a origem, onde L = 0
20
B
243.000
C
324.000
óleo
x2
10
querosene
162.000
D
(1.000 b/d)
81.000
0
A
Solução:
(26.207, 6.897)
(L=286.764)
gasolina
E
0
0
10
x1
(1.000 b/d)
20
30
40
2. Na fronteira, restringir a busca aos vértices.
Parte-se do fato de que o sistema de restrições de igualdade
pode ser re-escrito sob diversas formas.
Forma Original
0,80 x1 + 0,44 x2 +f1 = 24.000 (gasolina)
0,05 x1 + 0,10 x2 +f2 = 2.000 (querosene)
0,10 x1 + 0,36 x2 +f3 = 6.000(combustível)
Com x1 = 0 e x2 = 0  vértice A (origem)
Uma das formas alternativas
0,68 x1 – 1,22 f3 + f1 = 16.667 (gasolina)
0,02 x1 – 0,78 f3 + f2 =
333 (querosene)
0,28 x1 + 2,78 f3 + x2 = 16.667(combustível)
Com x1 = 0 e f3 = 0  vértice B
Portanto...
Uma forma de examinar apenas os vértices da região viável
consiste em reescrever o sistema sob formas diferentes e atribuir
o valor zero às variáveis de projeto correspondentes
Examinando os valores de x1, x2, f1, f2 e f3 em cada vértice
20
B
243.000
C
óleo
x2
10
324.000
querosene
162.000
D
(1.000 b/d)
81.000
0
A
A
x1 = 0
x2 = 0
f1 = 24.000
f2 = 2.000
f3 = 6.000
Solução:
(26.207, 6.897)
(L=286.764)
gasolina
E
0
0
B
x1 = 0
x2 = 16.667
f1 = 16.667
f2 =
333
f3 = 0
10 x1 (1.000 b/d) 20
C
x1 = 15.000
x2 = 12.500
f1 = 6.500
f2 = 0
f3 = 0
30
D
x1 = 26.207
x2 = 6.897
f1 = 0
f2 = 0
f3 =
897
40
E
x1 = 30.000
x2 = 0
f1 = 0
f2 =
500
f3 = 3.000
3.9 Algoritmo SIMPLEX (Dantzig, 1947)
O SIMPLEX parte da origem e visita vértices adjacentes na busca da
solução ótima, invertendo sucessivamente o papel de 2 variáveis: uma
do problema (básica) e uma de projeto (não-básica).
Inverter os papéis de duas variáveis, consiste em reescrever o sistema
de equações em termos de uma outra base.
A
x1 = 0
x2 = 0
f1 = 24.000
f2 = 2.000
f3 = 6.000
B
x1 = 0
x2 = 16.667
f1 = 16.667
f2 =
333
f3 = 0
C
x1 = 15.000
x2 = 12.500
f1 = 6.500
f2 = 0
f3 = 0
D
x1 = 26.207
x2 = 6.897
f1 = 0
f2 = 0
f3 =
897
E
x1 = 30.000
x2 = 0
f1 = 0
f2 =
500
f3 = 3.000
A mudança de base é executada aplicando o Algoritmo de
Gauss-Jordan à Matriz Aumentada (Tableau) do sistema de
equações lineares.
0,80 x1 + 0,44 x2 + f1 = 24.000 (gasolina)
0,05 x1 + 0,10 x2 + f2 = 2.000 (querosene)
0,10 x1 + 0,36 x2 + f3 = 6.000(combustível)
L(x) = 8,1 x1 + 10,8 x2
x1
x2
f1
f2
f3
b
0,80
0,44
1
0
0
24.000
0,05
0,10
0
1
0
2.000
0,1
0,36
0
0
1
6.000
8,10
10,80
0
0
0
L
O Lucro é incluído na matriz para que os seus coeficientes sofram as
mesmas transformações e fique expresso automaticamente na nova
base.
Critério para a troca de papéis (PIVOTAMENTO)
Projeto  Problema
Identifica-se a variável de projeto de maior coeficiente positivo
na expressão do Lucro (a que mais contribui para o aumento do
Lucro). OBS: coeficiente mais negativo no caso de minimização.
L(x) = 8,1 x1 + 10,8 x2 : x1 = x2 = 0  L = 0
aumento em x2  contribui mais para o aumento de L
Problema  Projeto
Identifica-se o menor valor positivo de b/a, sendo b o vetor dos
termos independentes (coluna da direita) e a o vetor dos
coeficientes na coluna da variável de projeto escolhida acima.
(corresponde a restrição mais próxima ao aumentar a variável de projeto)
f3  f 3
x1
x2
f1
f2
f3
0,80
0,05
0,44
0,10
1
0
0
1
0
0
24.000
2.000
54.545
0,1
0,36
0
0
1
6.000
16.667
8,10
10,80
0
0
0
L
x2  x2
b/ai2
20.000
Pivô = a32 = 0,36
Divide-se a linha do pivô pelo pivô.
Em seguida: aij = aij – ai2 a3j Ex.: a11=0,80 – 0,44 x 0,28 = 0,68
x1
x2
0,68
0,00
0,28
1
f1
f2
f3
1,00
0,00
-1,22
16.667
0
0
2,78
16.667
f3  f 3
x1
x2
f1
f2
f3
0,80
0,05
0,44
0,10
1
0
0
1
0
0
24.000
2.000
0,1
0,36
0
0
1
6.000
8,10
10,80
0
0
0
L
x2  x2
Resultado da eliminação Gaussiana: Ponto B
x1
x2
f1
f2
f3
0,68
0,02
0
0
1
0
0
1
-1,22
-0,28
16.667
333
0,28
1
0
0
2,78
16.667
5,10
0
0
0
-30
L - 180.000
Com x1 = f3 = 0  L = 180.000
Ponto B
Com x1 = f3 = 0
L = 180.000
x1
x2
f1
f2
f3
0,68
0
1
0
-1,22
16.667
0,02
0
0
1
-0,28
333
0,28
1
0
0
2,78
16.667
5,10
0
0
0
-30
L - 180.000
20
B
243.000
óleo
x2
10
C
324.000
querosene
162.000
D
(1.000 b/d)
81.000
0
A
gasolina
E
0
0
10 x
20
(1.000 b/d)
30
40
f2  f2
x1
x2
f1
f2
f3
0,68
0,02
0
0
1
0
0
1
-1,22
-0,28
16.667
333
24.510
0,28
1
0
0
2,78
16.667
59.525
5,10
0
0
0
-30
L - 180.000
x1  x1
b/ai1
16.650
Pivô = a21 = 0,02
Divide-se a linha do pivô pelo pivô.
Em seguida: aij = aij – ai1 a2j
x1
x2
f1
f2
f3
0
1
0
0
1
0
-30,5
45
7,25
-12,5
6.500
15.000
0
1
0
-12,5
6,25
12.500
0
0
0
-229,5 33,75
Com f2 = f3 = 0  L = 256.500
L - 256.500
x1
x2
f1
f2
f3
Ponto C
0
1
0
0
1
0
-30,5
45
7,25
-12,5
6.500
15.000
Com f2 = f3 = 0
L = 256.500
0
1
0
-12,5
6,25
12.500
0
0
0
-229,5 33,75
20
B
243.000
óleo
x2
L - 256.500
10
C
324.000
querosene
162.000
D
(1.000 b/d)
81.000
0
A
gasolina
E
0
0
10 x
20
(1.000 b/d)
30
40
f1  f1
x1
x2
f1
f2
f3
0
1
0
0
1
0
-30,5
45
7,25
-12,5
6.500
15.000
896,55
0
1
0
-12,5
6,25
12.500
2.000
0
0
0
-229,5 33,75 L - 256.500
Pivô = a15 = 7,25
Divide-se a linha do pivô pelo pivô.
b/ai5
-1.200
f3  f3
Em seguida: aij = aij – ai5 a1j
x1
x2
f1
f2
f3
0
0
0,14
4,21
1
897
1
0
1,72
-7,59
0
26.207
0
1
-0,86
13,79
0
6.897
0
0
-4,66
-87,52
0
L - 286.765
Com f1 = f2 = 0  L = 286.765
Ponto D
Com f1 = f2 = 0
L = 286.765
20
B
x1
x2
f1
f2
f3
0
0
0,14
4,21
1
897
1
0
1,72
-7,59
0
26.207
0
1
-0,86
13,79
0
6.897
0
0
-4,66
-87,52
0
L - 286.765
243.000
óleo
x2
10
C
324.000
querosene
162.000
D
(1.000 b/d)
81.000
0
A
gasolina
E
0
0
10 x
20
(1.000 b/d)
30
40
Ponto D
Com f1 = f2 = 0
L = 286.765
x1
x2
f1
f2
f3
0
0
0,14
4,21
1
897
1
0
1,72
-7,59
0
26.207
0
1
-0,86
13,79
0
6.897
0
0
-4,66
-87,52
0
L - 286.765
Projeto  Problema
Identifica-se a variável de projeto de maior coeficiente
POSITIVO na expressão do Lucro (a que mais contribui
para o aumento do Lucro)
Nenhuma para entrar  FIM
Ponto D
Com f1 = f2 = 0
0
0
0,14
4,21
1
x1
897
1
0
1,72
-7,59
0
x2
26.207
0
1
-0,86
13,79
0
f1
0
0
-4,66
-87,52
0
f2
f3
x1= 26.207
x2 = 6.897
f3 = 897
L = 286.764
=
6.897
L - 286.765
Solução: Ponto D
x1= 26.207
x2 = 6.897
gasolina = 24.000 (f1 = 0)
querosene = 2.000 (f2 = 0)
óleo = 5.103 (f3 = 897)
L = 286.764
20
B
243.000
óleo
x2
10
C
324.000
querosene
162.000
D
(1.000 b/d)
81.000
0
A
gasolina
E
0
0
10 x
20
(1.000 b/d)
30
40
Análise de Sensibilidade
Pode ser efetuada através dos valores implícitos (“shadow prices”
ou “custos marginais”) dos produtos, que aparecem na última linha
do Tableau Final, com sinal trocado. Corresponde aos multiplicadores
de Lagrange das restrições ativas.
x1
x2
f1
f2
f3
0
0
0,14
4,21
1
897
1
0
1,72
-7,59
0
26.207
0
1
-0,86
13,79
0
6.897
0
0
-4,66
-87,52
0
L - 286.765
bL = -
Por ex.: um aumento de 100 b/d de gasolina (restrição
ativa f1) implicaria em um aumento de 100 * 4,66 =
466 $/d no lucro da unidade.
Ou seja, cada b/d produzido de gasolina contribui
internamente com 4,66 $/d para o lucro, enquanto que
seu preço de venda no mercado externo é de 36 $/b.
Métodos do Ponto Interior
Restringe a busca aos pontos interiores da região viável.
20
B
243.000
C
324.000
óleo
querosene
x2
10
162.000
D
(1.000 b/d)
81.000
0
A
Solução:
(26.207, 6.897)
(L=286.764)
gasolina
E
0
0
10
20
x1
(1.000 b/d)
30
(como???)
40
3.10 Algoritmo de Karmarkar (1984, Dikin, 1967)
max {f(x) = cT x}
{x}
sujeito a: A x  b
x0
d
dr
origem 
dp

Aplica uma projeção do vetor direção (d = f = c) no
espaço nulo das restrições transformadas em igualdade.
A busca segue então na direção projetada até as
proximidades de uma restrição, obtendo o ponto xk.
O problema é então normalizado por:
xk+1 = D1 x , onde D = diag(xk)
e reformulado para que o ponto de partida do próximo
estágio esteja eqüidistante de todos os hiperplanos que formam
o poliedro (ou seja, o centróide):
A x = A DD1 x = A D xk+1
f(x) = cT DD1 x = cT D xk+1
resultando no novo problema:
max f(x) = cT D x
{x}
sujeito a: A D x  b
x0
Repetindo o procedimento até a convergência.
Algoritmo de Karmarkar
max {f(x) = cT x}
{x}
sujeito a: A x  b
x0
Entrada: A, b, c, x0, critério de parada e 
Solução do problema no MATLAB
c=[8.1; 10.8];
A=[0.8 0.44
0.05 0.1
0.1 0.36];
b=[24000; 2000; 6000];
lb=zeros(2,1);
x0=[0; 0];
% conjuntos ativos: simplex
op=optimset('LargeScale','off','Display','final');
[x,S,eflag,out,lambda]=linprog(-c,A,b,[],[],lb,[],x0,op)
x = [26206.90; 6896.55]
S = -286758.62
out = iterations: 3
algorithm: 'medium-scale: activeset'
lambda.ineqlin = [4.66; 87.52; 0.00]
Solução do problema no MATLAB
c=[8.1; 10.8];
A=[0.8 0.44
0.05 0.1
0.1 0.36];
b=[24000; 2000; 6000];
lb=zeros(2,1);
x0=[0; 0];
% ponto interior: S. Mehrotra, 1992
op=optimset('LargeScale','on','Display','iter','MaxIter',100,'TolFun',1e-4);
[x,S,eflag,out,lambda]=linprog(-c,A,b,[],[],lb,[],[],op)
x = [26206.89; 6896.55]
S = -286758.55
out = iterations: 4
algorithm: 'lipsol‘
lambda.ineqlin = [4.66; 87.52; 0.00]
PROBLEMA
Uma empresa possui duas plantas de alquilados (A1 e A2), cujos
produtos são distribuídos a 3 clientes (C1, C2 e C3).
Custos de Transporte ($/ton)
A1
A2
C1
25
C2
60
C3
75
20
50
85
A produção máxima (ton/d) de cada planta é:
A1 = 1,6 : A2 = 0,8
A demanda mínima (ton/d) de cada cliente é:
C1 = 0,9 : C2 = 0,7 : C3 = 0,3
O custo de produção da planta A1 é de $30/ton até 0,5 ton/d ou
de $40/ton acima de 0,5 ton/d.
O custo de produção da planta A2 é de $35/ton (qualquer nível).
Qual deve ser o esquema de produção e de distribuição da
empresa que minimiza o seu custo total ?