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

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

a Função Objetivo é linear

F(x) = c1 x1 + c2 x2 + ... + cn xn

O Problema de Programação Linear

é um tipo especial de problema de otimização em que

2. APLICAÇÕES

etc...

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

3. PROBLEMA ILUSTRATIVO

Planejamento da Produção de uma Refinaria(adaptado de Edgar & Himmelblau, pg. 254)

A partir de cada um deles, pode-se produzir:

- gasolina (G)- querosene (Q)- óleo combustível (C)- óleo residual (R).

Uma refinaria pode receber dois tipos de óleo cru: O1 e O2.

- 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)

Determinar

- quantos barris/dia (b/d) a refinaria deve adquirir de cada óleo cru (x1, x2).

3.1 ENUNCIADO

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

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 produtosp3 = 36 $/b (gasolina)p4 = 24 $/b (querosene)p5 = 21 $/b (óleo combustível)p6 = 10 $/b (óleo residual)

Produção máxima de cada produtox3max = 24.000 b/d (x3 = x31 + x32)x4max = 2.000 b/d (x4 = x41 + x42)x5max = 6.000 b/d (x5 = x51 + x52)

3.2 DADOS FÍSICOS E ECONÔMICOS

0,80 b3/b1

0,05 b4/b1

0,10 b5/b1

0,05 b6/b1

C1 = 0,50 $/b

C2 = 1 $/b

0,44 b3/b2

0,10 b4/b2

0,36 b5/b2

0,10 b6/b2

x32

x42

x52

x62

x31

x41

x51

x61

G

Q

C

R

p2 = 15 ($/b)

p1 = 24 ($/b)

x1 (b/d)

x2 (b/d)

CRÚS

x3(b/d)

x4(b/d)

x5(b/d)

x6(b/d)

PRODUTOS

p3 = 36($/b); x3max= 24.000(b/d)

p4 = 24($/b); x4max= 2.000(b/d)

p5 = 21($/d); x5max= 6.000(b/d)

p6=10($/b)

O1

O2

Dados resumidos em Fluxograma

Modelo Matemático ?Balanço de Informação ?Variáveis de Projeto ?Critério ?Função Objetivo ?Restrições ?Região Viável ?

Como em qualquer problema de Análise de Processos

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

Balanços de Massa

0,80 b3/b1

0,05 b4/b1

0,10 b5/b1

0,05 b6/b1

C1 = 0,50 $/b

C2 = 1 $/b

0,44 b3/b2

0,10 b4/b2

0,36 b5/b2

0,10 b6/b2

x32

x42

x52

x62

x31

x41

x51

x61

G

Q

C

R

p2 = 15 ($/b)

p1 = 24 ($/b)

x1 (b/d)

x2 (b/d)

PRODUTOSCRÚS

x3(b/d)

x4(b/d)

x5(b/d)

x6(b/d)

p3 = 36($/b); x3max= 24.000(b/d)

p4 = 24($/b); x4max= 2.000(b/d)

p5 = 21($/d); x5max= 6.000(b/d)

p6=10($/b)

O1

O2

3.3 MODELO MATEMÁTICO

Balanço de Informação

G = V – N = 6 – 4 G = 2

Variáveis de Projeto: x1 e x2

0,80 b3/b1

0,05 b4/b1

0,10 b5/b1

0,05 b6/b1

C1 = 0,50 $/b

C2 = 1 $/b

0,44 b3/b2

0,10 b4/b2

0,36 b5/b2

0,10 b6/b2

x32

x42

x52

x62

x31

x41

x51

x61

G

Q

C

R

p2 = 15 ($/b)

p1 = 24 ($/b)

x1 (b/d)

x2 (b/d)

PRODUTOSCRÚS

x3(b/d)

x4(b/d)

x5(b/d)

x6(b/d)

p3 = 36($/b); x3max= 24.000(b/d)

p4 = 24($/b); x4max= 2.000(b/d)

p5 = 21($/d); x5max= 6.000(b/d)

p6=10($/b)

O1

O2

3.4 BALANÇO DE INFORMAÇÃO E VARIÁVEIS DE PROJETO

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

Balanços de Massa

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

Função Objetivo

L = R – CMP - CP

L = 36 x3 + 24 x4 + 21 x5 + 10 x6 - 24 x1 - 15 x2 - 0,50 x1 - x2

0,80 b3/b1

0,05 b4/b1

0,10 b5/b1

0,05 b6/b1

C1 = 0,50 $/b

C2 = 1 $/b

0,44 b3/b2

0,10 b4/b2

0,36 b5/b2

0,10 b6/b2

x32

x42

x52

x62

x31

x41

x51

x61

G

Q

C

R

p2 = 15 ($/b)

p1 = 24 ($/b)

x1 (b/d)

x2 (b/d)

PRODUTOSCRÚS

x3(b/d)

x4(b/d)

x5(b/d)

x6(b/d)

p3 = 36($/b); x3max= 24.000(b/d)

p4 = 24($/b); x4max= 2.000(b/d)

p5 = 21($/d); x5max= 6.000(b/d)

p6=10($/b)

O1

O2

3.5 CRITÉRIO E FUNÇÃO OBJETIVO

Critério

Maximização do Lucro

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 DesigualdadeGasolina : x3 24.000Querosene : x4 2.000 Combustível : x5 6.000

Óleos crus : x1 0 e x2 0

0,80 b3/b1

0,05 b4/b1

0,10 b5/b1

0,05 b6/b1

C1 = 0,50 $/b

C2 = 1 $/b

0,44 b3/b2

0,10 b4/b2

0,36 b5/b2

0,10 b6/b2

x32

x42

x52

x62

x31

x41

x51

x61

G

Q

C

R

p2 = 15 ($/b)

p1 = 24 ($/b)

x1 (b/d)

x2 (b/d)

PRODUTOSCRÚS

x3(b/d)

x4(b/d)

x5(b/d)

x6(b/d)

p3 = 36($/b); x3max= 24.000(b/d)

p4 = 24($/b); x4max= 2.000(b/d)

p5 = 21($/d); x5max= 6.000(b/d)

p6=10($/b)

O1

O2

3.6 RESTRIÇÕES

Min f(x) Função Objetivo x Variáveis de Projetos.a.: g(x) 0 Restr. desigualdade h(x) = 0 Restr. igualdade

Incorporando as Restrições de Igualdade

à Função Objetivo

Resulta

L(x) = 8,1 x1 + 10,8 x2

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

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

Enunciado Formal do Problema

x2 = L/10,8 – (8,1/10,8) x1 (família de retas)

Função Objetivo

L(x) = 8,1 x1 + 10,8 x2 (linear)

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)L=81.000

L=162.000

L=243.000L=324.000

L=648.000

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 0x2 0

região convexa !

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

Egasolina

querosene

óleo

Qualquer ponto no interior ou sobre a fronteira da Região Viável é uma Solução Viável

3.7 REGIÃO VIÁVEL

3.8 RESOLUÇÃO

Solução Ótima

Solução (D):(26.207, 6.897)

(L=286.764)

É a solução viável correspondente ao valor máximo do Lucro

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina

81.000

162.000

243.000 324.000

Em duas dimensões, a identificação visual da Solução Ótima é imediata.

Solução (C):(14.000, 13.000)

(L = 637.000)

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina

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

Como automatizar a busca pelo o vértice ótimo?

Busca Exaustiva

Método dos Conjuntos Ativos

Método do Ponto Interior

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.

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina

Solução:(26.207, 6.897)

(L=286.764)

81.000

162.000

243.000

324.000

0

(como???)

Para tanto, os passos são os seguintes:

1. Restringir a busca à fronteira da região viável

2. Restringir a busca, na fronteira, aos vértices

Transformando as restrições de desigualdade em restrições de igualdade

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

Variável de Folga

No método dos conjuntos ativos, pode ser operada com o auxílio do conceito de

Transformando as restrições de desigualdade em restrições de igualdade

Folga

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

F

G

Hgasolina

querosene

óleo

Exemplo: ponto I (folgas na produção de gasolina, querosene e óleo)

f1 = 11.600 b/df2 = 500 b/df3 = 1.400 b/d

I

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)

Qualquer ponto (x1, x2) no interior da Região Viável corresponde a uma produção inferior à máxima de cada produto (folga, fi).

Folga

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

F

G

Hgasolina

querosene

óleo

Qualquer ponto (x1, x2) localizado sobre um restrição corresponde à produção máxima do produto respectivo.

f1 = 9.889 b/df2 = 111 b/df3 = 0 b/d

J13,9

Gasolina : 0,80 x1 + 0,44 x2 = x3=14.111 (24.000)Querosene : 0,05 x1 + 0,10 x2 = x4 = 1.889 (2.000)Combustível : 0,10 x1 + 0,36 x2 = x5 = 6.000 (6.000)

Exemplo: ponto J (produção máxima de óleo = 6.000 b/d: f3 = 0)

Folga

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

F

G

Hgasolina

querosene

óleo

Qualquer ponto (x1, x2) localizado sobre um vértice corresponde à produção máxima dos 2 produtos respectivos.

f1 = 0 b/df2 = 0 b/d

f3 = 2.541 b/d

Gasolina : 0,80 x1 + 0,44 x2 = x3=24.000 (24.000)Querosene : 0,05 x1 + 0,10 x2 = x4 = 2.000 (2.000)Combustível : 0,10 x1 + 0,36 x2 = x5 = 3.459 (6.000)

Exemplo: ponto D (produção máxima de gasolina e de querosene: f1 = 0, f2 = 0)

A desejada transformação das restrições de desigualdade em restrições de igualdade é obtida

incorporando as folgas à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

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 + 0,05 x1 + 0,10 x2 + 0,10 x1 + 0,36 x2 + x1 0 x2 0

f1f2

f3

= 24.000 (gasolina) = 2.000 (querosene) = 6.000(combustível)

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.

V = 5 : N = 3 : G = 2 !!!

As restrições de igualdade formam agora um sistema de equações lineares.

0,80 x1 + 0,44 x2 + 0,05 x1 + 0,10 x2 + 0,10 x1 + 0,36 x2 +

f1f2

f3

= 24.000 (gasolina) = 2.000 (querosene) = 6.000(combustível)

Mas, agora, todas localizadas na fronteira da região viável

10 20 30 400

10

20

0

x1

(1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina

Solução:(26.207, 6.897)

(L=286.764)

81.000

162.000

243.000

324.000

0

Uma solução trivial é: x1 = 0, x2 = 0

Corresponde a uma vértice especial: a origem, onde L = 0

2. Na fronteira, restringir a busca aos vértices.

0,80 x1 + 0,44 x2 + 0,05 x1 + 0,10 x2 + 0,10 x1 + 0,36 x2 +

f1f2

f3

= 24.000 (gasolina) = 2.000 (querosene) = 6.000(combustível)

0,68 x1 – 1,22 f3 + 0,02 x1 – 0,78 f3 + 0,28 x1 + 2,78 f3 +

f1f2

x2

= 16.667 (gasolina) = 333 (querosene) = 16.667(combustível)

Parte-se do fato de que o sistema de restrições de igualdade pode ser re-escrito sob diversas formas.

Forma Original

Uma das formas alternativas

Com x1 = 0 e x2 = 0 vértice A (origem)

Com x1 = 0 e f3 = 0 vértice B

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

Portanto...

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina

Solução:(26.207, 6.897)

(L=286.764)

81.000

162.000

243.000

324.000

0

Ax1 = 0x2 = 0f1 = 24.000f2 = 2.000f3 = 6.000

Bx1 = 0x2 = 16.667f1 = 16.667f2 = 333f3 = 0

Cx1 = 15.000x2 = 12.500f1 = 6.500f2 = 0f3 = 0

Dx1 = 26.207x2 = 6.897f1 = 0f2 = 0f3 = 897

Ex1 = 30.000x2 = 0f1 = 0f2 = 500f3 = 3.000

Examinando os valores de x1, x2, f1, f2 e f3 em cada vértice

Ax1 = 0x2 = 0f1 = 24.000f2 = 2.000f3 = 6.000

Bx1 = 0x2 = 16.667f1 = 16.667f2 = 333f3 = 0

Cx1 = 15.000x2 = 12.500f1 = 6.500f2 = 0f3 = 0

Dx1 = 26.207x2 = 6.897f1 = 0f2 = 0f3 = 897

Ex1 = 30.000x2 = 0f1 = 0f2 = 500f3 = 3.000

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.

3.9 Algoritmo SIMPLEX (Dantzig, 1947)

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

0,80 x1 + 0,44 x2 + 0,05 x1 + 0,10 x2 + 0,10 x1 + 0,36 x2 +

L(x) = 8,1 x1 + 10,8 x2

f1f2

f3

= 24.000 (gasolina) = 2.000 (querosene) = 6.000(combustível)

A mudança de base é executada aplicando o Algoritmo de Gauss-Jordan à Matriz Aumentada (Tableau) do sistema de

equações lineares.

O Lucro é incluído na matriz para que os seus coeficientes sofram as mesmas transformações e fique expresso automaticamente na nova

base.

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.

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)

Critério para a troca de papéis (PIVOTAMENTO)

L(x) = 8,1 x1 + 10,8 x2 : x1 = x2 = 0 L = 0

aumento em x2 contribui mais para o aumento de L

x1 x2 f1 f2 f3

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

x1 x2 f1 f2 f3

x2 x2

f3 f3

Pivô = a32 = 0,36

Divide-se a linha do pivô pelo pivô. Em seguida: aij = aij – ai2 a3j

0,68 0,00 1,00

0,28 2,78 16.6671 0 0

Ex.: a11=0,80 – 0,44 x 0,28 = 0,68

0,36

b/ai2

54.545

20.000

16.667

0,00 -1,22 16.667

x1 x2 f1 f2 f3

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

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

Com x1 = f3 = 0 L = 180.000

x2 x2

f3 f3

Resultado da eliminação Gaussiana: Ponto B

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina81.000

162.000

243.000

324.000

0

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

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

x1 x2 f1 f2 f3

0 0 1 -30,5 7,25 6.500

1 0 0 45 -12,5 15.000

0 1 0 -12,5 6,25 12.500

0 0 0 -229,5 33,75 L - 256.500

Com f2 = f3 = 0 L = 256.500

x1 x1

f2 f2

Divide-se a linha do pivô pelo pivô. Em seguida: aij = aij – ai1 a2j

b/ai1

24.510

16.650

59.525

Pivô = a21 = 0,02

0,02

x1 x2 f1 f2 f3

0 0 1 -30,5 7,25 6.500

1 0 0 45 -12,5 15.000

0 1 0 -12,5 6,25 12.500

0 0 0 -229,5 33,75 L - 256.500

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina81.000

162.000

243.000

324.000

0

Ponto C

Com f2 = f3 = 0 L = 256.500

x1 x2 f1 f2 f3

0 0 1 -30,5 7,25 6.500

1 0 0 45 -12,5 15.000

0 1 0 -12,5 6,25 12.500

0 0 0 -229,5 33,75 L - 256.500

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

f3 f3

f1 f1

Divide-se a linha do pivô pelo pivô. Em seguida: aij = aij – ai5 a1j

b/ai5

896,55

-1.200

2.000

Pivô = a15 = 7,25

7,25

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

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina81.000

162.000

243.000

324.000

0

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

Ponto D

Com f1 = f2 = 0 L = 286.765

Nenhuma para entrar FIM

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)

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 = 6.897

0 0 -4,66 -87,52 0 f2 L - 286.765

f3

Ponto D

Com f1 = f2 = 0

x1= 26.207x2 = 6.897

f3 = 897

L = 286.764

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleo

querosene

gasolina81.000

162.000

243.000

324.000

0

Solução: Ponto Dx1= 26.207x2 = 6.897

gasolina = 24.000 (f1 = 0)querosene = 2.000 (f2 = 0)

óleo = 5.103 (f3 = 897)

L = 286.764

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

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.

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.

10 20 30 400

10

20

0

x1 (1.000 b/d)

x2

(1.000 b/d)

A

B

C

D

E

óleoquerosene

gasolina

Solução:(26.207, 6.897)

(L=286.764)

81.000

162.000

243.000

324.000

0

(como???)

3.10 Algoritmo de Karmarkar (1984, Dikin, 1967)

max {f(x) = cT x} {x}sujeito a: A x b x 0

origem

d

dp

dr

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.

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 DD1 x = A D xk+1

f(x) = cT DD1 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.

O problema é então normalizado por:

xk+1 = D1 x , onde D = diag(xk)

Algoritmo de Karmarkar

Entrada: A, b, c, x0, critério de parada e

max {f(x) = cT x} {x}sujeito a: A x b x 0

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: simplexop=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, 1992op=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).

C1 C2 C3

A1 25 60 75

A2 20 50 85

Custos de Transporte ($/ton)

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 ?