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–4G=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 x0 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 = D1 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 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 x0 Repetindo o procedimento até a convergência. Algoritmo de Karmarkar max {f(x) = cT x} {x} sujeito a: A x b x0 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 ?