382 Apostila Pesquisa Operacional Parte 1

  • Published on
    23-Aug-2014

  • View
    135

  • Download
    21

Transcript

Ementa Pesquisa OperacionalINTRODUO 1. Programao Matemtica 2. Reviso de lgebra Linear 3. Uso de pacotes computacionais na soluo de problemas PROGRAMAO LINEAR 1. Introduo Programao Linear 2. O algoritmo Simplex

Engenharia de Produo DEPROT / UFRGS Profs. Flavio Fogliatto, Ph.D.

Prof. Fogliatto

Pesquisa Operacional

2

EmentaMODELOS DE REDES 1. O problema do transporte 2. O problema da designao 3. O problema do transbordo 4. Modelos de Redes TPICOS AVANADOS 1. Programao Inteira

Referncias BibliogrficasLIVRO-TEXTO: Operations Research, Applications and Algorithms, de Wayne L. Winston, 3a. Ed., Duxburry Press. Adicionais (no mesmo nvel): 1. Pesquisa Operacional, de Harvey Wagner, 2a. Ed., Prentice-Hall do Brasil. 2. Pesquisa Operacional, de Pierre J. Ehrlich, Ed. Atlas.

Prof. Fogliatto

Pesquisa Operacional

3

Prof. Fogliatto

Pesquisa Operacional

4

INTRODUO PROGRAMAO LINEAR Programao Linear uma ferramenta para soluo de problemas de otimizao. Em 1947, George Dantzig desenvolveu o algoritmo SIMPLEX, extremamente eficiente na soluo de problemas de PL. A partir de ento, PL passou a ser utilizada em diversos segmentos da atividade produtiva: Bancos Instituies Financeiras Empresas de Transportes, etc. Vamos introduzir a PL a partir de um exemplo.Prof. Fogliatto Pesquisa Operacional 5 Prof. Fogliatto

EXEMPLO: O caso PolitoyA Politoy S/A fabrica soldados e trens de madeira. Cada soldado vendido por $27 e utiliza $10 de matria-prima e $14 de mo-de-obra. Duas horas de acabamento e 1 hora de carpintaria so demandadas para produo de um soldado. Cada trem vendido por $21 e utiliza $9 de matria-prima e $10 de mo-de-obra. Uma hora de acabamento e 1 h de carpintaria so demandadas para produo de um trem.

Pesquisa Operacional

6

EXEMPLO: O caso PolitoyA Politoy no tem problemas no fornecimento de matria-primas, mas s pode contar com 100 h de acabamento e 80 h de carpintaria. A demanda semanal de trens ilimitada, mas no mximo 40 soldados so comprados a cada semana. A Politoy deseja maximizar seus ganhos semanais. Formule um modelo matemtico a ser utilizado nessa otimizao.

Ao desenvolver um modelo para a Politoy, investigaremos caractersticas comuns a todos os problemas de PL VARIVEIS DE DECISO O primeiro passo na formulao de um problema de PL a definio das variveis de deciso relevantes. Estas variveis devem descrever completamente as decises a serem tomadas. A Politoy deve decidir sobre: x1 = nm. de soldados produzidos a cada semana x2 = nm. de trens produzidos a cada semana

Prof. Fogliatto

Pesquisa Operacional

7

Prof. Fogliatto

Pesquisa Operacional

8

FUNO OBJETIVO Em qualquer problema de PL, o analista sempre vai desejar maximizar (ex., lucro) ou minimizar (ex., custo) alguma funo das variveis de deciso. A funo a ser maximizada (ou minimizada) a funo objetivo. A Politoy deseja maximizar seus ganhos semanais. Ou seja: ganho semanal = ganho semanal oriundo da venda de soldados + ganho semanal oriundo da venda de trens. = ($/soldado).(soldados/sem) + ($/trem).(trem/sem) = 27x1 + 21x2 Tambm devemos considerar: custo semanal com matria-prima: 10x1 + 9x2 custo semanal com mo-de-obra: 14x1 + 10x2

FUNO OBJETIVO O que a Politoy deseja maximizar : (27x1 + 21x2) - (10x1 + 9x2) - (14x1 + 10x2) = 3x1 + 2x2 Usaremos a varivel z para designar o valor assumido pela funo objetivo. Assim: Max z = 3x1 + 2x2 Os nmeros 3 e 2 so chamados coeficientes da funo objetivo. Eles indicam a contribuio de cada varivel nos ganhos da empresa.

Prof. Fogliatto

Pesquisa Operacional

9

Prof. Fogliatto

Pesquisa Operacional

10

RESTRIES A medida que x1 e x2 crescem, o valor da funo objetivo aumenta. Mas x1 e x2 no podem crescer indefinidamente. Trs restries limitam seu crescimento: Restrio 1 - 100 h de acabamento / semana. Restrio 2 - 80 h de carpintaria / semana Restrio 3 - no mais que 40 soldados / semana, devido a limitaes na prpria demanda. Restries 1 3 devem ser expressas em termos das variveis de deciso x1 e x2.

RESTRIES Restrio 1: (total hs acabamento/sem.) = (hs.acab./sold.).(sold. produzidos/sem.) + (hs.acab./trem).(trens produzidos/sem.) (total hs acabamento/sem.) = 2(x1) + 1(x2) = 2x1 + x2 A restrio 1 ser dada por: 2x1 + x2

100

Observe que todos os termos de uma restrio devem ter a mesma unidade de medida. Os valores 2 e 1 na restrio so denominados coeficientes tecnolgicos.

Prof. Fogliatto

Pesquisa Operacional

11

Prof. Fogliatto

Pesquisa Operacional

12

Restrio 2 (determinada de maneira similar): (total hs carpintaria/sem.) = (hs.carp./sold.).(sold. produzidos/sem.) + (hs.carp./trem).(trens produzidos/sem.) (total hs carpintaria/sem.) = 1(x1) + 1(x2) = x1 + x2 A restrio 2 ser dada por: x1 + x2 Restrio 3: A restrio 3 definida pela limitao do nmero de soldados produzidos por semana (devido a limitaes na demanda): x1Prof. Fogliatto

RESTRIES DE SINAL Identificam os tipos de valores que as variveis podem assumir. Podem ser de trs tipos: 0 0 irrestrita

80

Combinando a funo objetivo e as restries, chega-se a formulao matemtica do problema da Politoy: max z = 3x1 + 2x2 Sujeito a: 2x1 + x2 x1 + x2

4013 Prof. Fogliatto

100 80 40 x1 x1, x2 0

Restrio de horas de acabamento Restrio de horas de carpintaria Restrio de demandaPesquisa Operacional 14

Pesquisa Operacional

PRTICA 1:Um fazendeiro deseja determinar quantos acres de milho e trigo ele deve plantar esse ano. Um acre de trigo rende 25 sacas e requer 10 horas de trabalho/semana. A saca vale $4 no mercado. Um acre de milho rende 10 sacas e requer 4 horas de trabalho/semana. A saca vale $3 no mercado. O governo garante a compra de pelo menos 30 sacas de milho/ano. O fazendeiro dispe de 7 acres de terra e pode trabalhar 40 horas/semana. Formule o problema tal que os ganhos do fazendeiro sejam maximizados.

Soluo - Prtica 1 Variveis de Deciso: x1 = no de acres de milho a serem plantados x2 = no de acres de trigo a serem plantados

Prof. Fogliatto

Pesquisa Operacional

15

Prof. Fogliatto

Pesquisa Operacional

16

ESPAO DE SOLUES E SOLUO TIMA O espao de solues formado por todos os pontos que satisfazem as restries do problema. A soluo tima em um problema de maximizao corresponde ao ponto no espao de solues onde o valor da funo objetivo mximo.

Representao grfica Representao da restrio 2x1 + 3x2 = 6:x24 3 2

2x1 + 3x2 6

(0,0)

x12 3 4

2x1 + 3x2 6Prof. Fogliatto Pesquisa Operacional 17 Prof. Fogliatto Pesquisa Operacional

2x1 + 3x2 = 618

Representao grfica do problema Politoyx2100 (2) 80 (4) 60 Ponto timo: (20,60) O espao de solues encontra-se hachurado. (2) - (4) denotam as restries. As restries de sinal restringem o problema ao primeiro quadrante do espao bi-dimens.

Restries crticas (binding) e no-crticasUma restrio crtica (binding) se, substituindo os valores correspondentes ao ponto timo na restrio, a igualdade de verifica. Ex.: restries (2) e (3) no grfico anterior.

Soluo tima: (1) Desenhe o vetor z. (2) Desenhe linhas ortogonais ao vetor z. Essas so as linhas de isocusto. (3) Calcule o valor de z no ponto timo.

40

Todas as demais restries so consideradas no-crticas. Ex.: restrio (4) e restries de sinal no grfico anterior.

20

z

(3)

z = 3(20) + 2(60) = 180

Prof. Fogliatto

20

40

Pesquisa Operacional

60

80

100

x119 Prof. Fogliatto Pesquisa Operacional 20

Outro exemplo:Solucione graficamente o problema e identifique o tipo de conjunto de solues resultante. Um empresa de eletrodomsticos planeja veicular seus produtos em comerciais de TV durante a novela das 8 e os jogos da seleo na Copa. Comerciais na novela so vistos por 7 milhes de mulheres e 2 milhes de homens e custam $50000. Comerciais nos jogos so vistos por 2 milhes de mulheres e 12 milhes de homens, e custam $100000. Qual a distribuio ideal de comerciais se a empresa deseja que eles sejam vistos por 28 milhes de mulheres e 24 milhes de homens a um menor custo possvel? Variveis de deciso: x1 = num. de comerciais veiculados durante a novela. x2 = num. de comerciais veiculados durante os jogos Funo objetivo: Min z = 50x1 + 100x2 A soluo grfica ... Restries: Pblico feminino: 7x1 + 2x2 28 Pblico masculino: 2x1 + 12x2 24 x 1, x 2 0 Soluo tima: (3.6, 1.4) com z = $320. A soluo nica.Prof. Fogliatto Pesquisa Operacional 21 Prof. Fogliatto Pesquisa Operacional 22

x2 10

Ponto timo no inteiro: Testar pontos (4,1), (3,2), (4,2), checando restries e z. Usar programao inteira.

CASOS ESPECIAIS:(1) Problemas com solues alternativas (vrias solues so simultaneamente timas). Nestes casos, a linha de isocusto, ao abandonar o espao de solues viveis, intersecciona com uma linha inteira (e no somente um ponto) desse conjunto.

8

6

Ponto timo: (3.6, 1.4)

4

2

zProf. Fogliatto

2

4

6

8

10

x123 Prof. Fogliatto Pesquisa Operacional 24

Pesquisa Operacional

CASOS ESPECIAIS:(2) Problemas com soluo tendendo ao infinito.

CASOS ESPECIAIS:(3) Problemas sem soluo

Nestes casos, as restries formam um espao aberto de solues viveis. Se a funo objetivo for do tipo max, z e a formulao do problema pode estar incorreta. Se for do tipo Min, uma ou mais solues sero encontradas.

Nestes casos, as restries no formam nenhum espao de solues viveis.

Prof. Fogliatto

Pesquisa Operacional

25

Prof. Fogliatto

Pesquisa Operacional

26

Outro exerccioResolva graficamente o problema formulado na Prtica 1 Um fabricante deseja maximizar a receita. A tabela mostra as composies das ligas, seus preos e as limitaes na disponibilidade de matria-prima:

Formule o problema e encontre a soluo tima graficamente.

Prof. Fogliatto

Pesquisa Operacional

27

Prof. Fogliatto

Pesquisa Operacional

28

Problemas Tpicos de Formulao

FORMULAO 1: Escolha de dietaQuatro tipos de alimentos esto disponveis na elaborao da merenda de um grupo de crianas: biscoito de chocolate, sorvete, refrigerante e torta de queijo. A composio desses alimentos e seus preos so:

Escolha da dieta

Scheduling de pessoal Deciso Financeira Problema da Mistura Programao da ProduoAs crianas devem ingerir pelo menos 500 calorias, 6 g de chocolate, 10 g de acar, e 8 g de gordura. Formule o problema tal que o custo seja minimizado.Prof. Fogliatto Pesquisa Operacional 29 Prof. Fogliatto Pesquisa Operacional 30

Variveis de deciso: x1 = pores de biscoitos; x2 = pores de sorvete; x3 = pores de refrigerante; x4 = pores de torta de queijo;

Restries: (1) Ingesto mnima de 500 calorias; (2) Ingesto mnima de 6 g de chocolate; (3) Ingesto mnima de 10 g de acar; (4) Ingesto mnima de 8 g de gordura. (1) 400 x1 + 200 x2 + 150 x3 + 500 x4 500

Funo objetivo: (custo total) = (custo dos biscoitos) + (custo do sorvete) + (custo do refrigerante) + (custo da torta de queijo) Min z = 50 x1 + 20 x2 + 30 x3 + 80 x4

(2) 3 x1 + 2 x2 3 (3) 2 x1 + 2 x2 + 4 x3 + 4 x4 10 (4) 2 x1 + 4 x2 + x3 + 5 x4 8 Variveis 0.

Prof. Fogliatto

Pesquisa Operacional

31

Prof. Fogliatto

Pesquisa Operacional

32

FORMULAO 2: Otimizao da Fora de TrabalhoUma agncia de correios necessita de um nmero diferente de funcionrios, de acordo com o dia da semana:

Variveis de deciso: xi = nm. de empregados trabalhando no dia i; Funo objetivo: Min z = x1 + x2 + x3 + x4 + x5 + x6 + x7

Por exigncia sindical, cada trabalhador trabalha cinco dias consecutivos e descansa dois. Formule o problema tal que o nmero de empregados contratados seja o mnimo necessrio para atender s necessidades de mo-deobra.

Restries: x1 x2 x3 x4 x5 x6 17 13 15 19 14 16 x7 11 xi 0 Qual o problema com essa formulao?

Prof. Fogliatto

Pesquisa Operacional

33

Prof. Fogliatto

Pesquisa Operacional

34

PROBLEMAS(1) A funo-objetivo no o nmero de funcionrios, como se imagina. Cada funcionrio est sendo computado 5 vezes. Por ex.: um funcionrio que comea a trabalhar na segunda, trabalha de segunda a sexta e est includo nas variveis x1, x2, x3, x4, x5. (2) A inter-relao entre as variveis x1, x2, ..., x5 no est capturada na formulao. Por ex.: alguns funcionrios que trabalham na segunda estaro trabalhando na tera. Ou seja x1 e x2 esto inter-relacionadas mas isso no aparece na formulao.Prof. Fogliatto Pesquisa Operacional 35

FORMULAO CORRETA Variveis de deciso: xi = nm. de empregados comeando a trabalhar no dia i; Cada empregado comea a trabalhar em um nico dia, no sendo assim contados mais de uma vez.

Funo objetivo: Min z = x1 + x2 + x3 + x4 + x5 + x6 + x7

Prof. Fogliatto

Pesquisa Operacional

36

17 funcionrios devem estar trabalhando na segunda. Quem estar trabalhando segunda? xi = trabalham nos dias i, i+1, i+2, i+3, i+4; i = 1 (segunda). Assim, estaro trabalhando na segunda os empregados x1 + x4 + x5 + x6 + x7. Assim, a restrio referente ao nmero de empregados trabalhando na segunda ser: x1 + x4 + x5 + x6 + x7 17 Os demais dias sero formulados de maneira similar.

Restries: x1 x1 x1 x1 x1 x2 x3 + + + + + + + x4 x2 x2 x2 x2 x3 x4 + + + + + + + x5 x5 x3 x3 x3 x4 x5 + + + + + + + x6 x6 x6 x4 x4 x5 x6 + + + + + + + x7 x7 x7 x7 x5 x6 x7 xi 17 13 15 19 14 16 11 0

A soluo tima x1 = 4/3; x2 = 10/3; x3 = 2; x4 = 22/3 x5 = 0; x6 = 10/3; x7 = 5. xi fracionrio no faz sentido. Arredondando-se chegamos a uma soluo que, quando checada via otimizao inteira, resulta completamente sub-tima. Para esses problemas precisamos de programao inteira.37 Prof. Fogliatto Pesquisa Operacional 38

Prof. Fogliatto

Pesquisa Operacional

FORMULAO: Deciso Financeira O conceito de valor lquido presente: Considere que $1 investido hoje valer mais de $1 daqui h um ano. O novo valor depender da taxa anual de juros, r. Assim: $1 hoje = $(1 + r)k em k anos ou $ 1 recebidos em k anos = $ (1 + r)-k hoje $ x recebidos em k anos = $x / (1 + r)k hoje O valor lquido presente (VLP) de um investimento determinado descontando o fluxo de caixa de um investimento at o tempo atual, ou tempo 0.Prof. Fogliatto Pesquisa Operacional 39

EXEMPLO:Investim. 1 = requer um investimento de $10,000 no tempo 0 e de $14,000 em 2 anos e tem um retorno de $24,000 em 1 ano. Investim. 2 = requer um investimento de $6,000 no tempo 0 e de $1,000 em 2 anos e tem um retorno de $8,000 em 1 ano. Qual o melhor investimento (r = 0.2)? VLP (Inv. 1) = = VLP (Inv. 2) = = -10,000 + (24,000/1+0.2) - [14,000/(1+0.2)2] $277.78 -6,000 + (8,000/1+0.2) - [1,000/(1+0.2)2] - $27.78 O investimento 1 bem melhor!Prof. Fogliatto Pesquisa Operacional 40

EXEMPLO DE FORMULAO: Formulao 3 Uma empresa est considerando 5 oportunidades de investimento, com caractersticas dadas a seguir:

Varivel de deciso: A empresa deseja determinar qual frao de cada investimento deve ser comprada: xi = frao do investimento i comprada pela empresa.

A empresa tem $40 disponveis para investimento no tempo t = 0 e estima dispor de $20 no tempo t = 1. Capital no investido em t=0 no estar disponvel em t = 1. Fraes de cada investimento podem ser compradas. Formule o problema tal que o VLP da companhia seja maximizado.

Funo objetivo: Consiste em maximizar os VLP dados na tabela: Max z = 13x1 + 16x2 + 16x3 + 14x4 + 39x5

Prof. Fogliatto

Pesquisa Operacional

41

Prof. Fogliatto

Pesquisa Operacional

42

Restries: (1) A empresa no pode investir mais de $40 no tempo 0: 11x1 + 53x2 + 5x3 + 5x4 + 29x5 40 (2) A empresa no pode investir mais de $20 no tempo 1: 3x1 + 6x2 + 5x3 + x4 + 34x5 20 Falta alguma restrio? (3) A empresa no pode comprar mais que 100% de nenhum investimento: xi 1 (4) Todas as variveis devem ser positivas.Prof. Fogliatto Pesquisa Operacional 43

PRTICA 2:A empresa X deseja determinar quanto dinheiro investir e quanto dinheiro tomar emprestado no prximo ano. Cada real investido pela empresa reduz o VLP em 10 centavos e cada real tomado em emprstimo aumenta o VLP em 50 centavos (vale mais a pena tomar emprestado do que investir). X pode investir no mximo $1000000. O dbito pode somar at 40% do que for investido. X dispe de $800000 em caixa. Todo o investimento deve ser pago com o dinheiro em caixa ou com dinheiro emprestado. Formule o problema tal que o VLP de X seja maximizado. Resolva o problema graficamente.

Prof. Fogliatto

Pesquisa Operacional

44

FORMULAO: Problema da MisturaSituaes onde vrias matrias-primas devem ser misturadas em propores ideais so modelveis via programao linear. Alguns exemplos: (1) Mistura de vrios tipos de leos para produzir diferentes tipos de gasolina. (2) Mistura de compostos qumicos para gerar outros compostos. (3) Mistura de ingredientes para produo de raes. (4) Mistura de diferentes tipos de papis para produzir um papel reciclado.

EXEMPLO (Formulao 4): O caso TexacoA Texaco produz at 14000 barris/dia de 3 tipos de gasolina misturando 3 tipos de leos. Dados a respeito das gasolinas e leos so:

Prof. Fogliatto

Pesquisa Operacional

45

Prof. Fogliatto

Pesquisa Operacional

46

EXEMPLO (Formulao 4): O caso TexacoAs gasolinas tm especificaes de octanagem e contedo de enxofre dadas abaixo. A mistura de leos para produo de gasolina deve satisfazer essas especificaes.

Variveis de deciso: A Texaco deve decidir sobre (i) quanto dinheiro gastar na publicidade de cada tipo de gasolina e (ii) qual a mistura apropriada de leos. ai = $/dia gasto na publicidade da gasolina i. xij = barris de leo i gastos/dia para produzir gasolina j.

Funo objetivo: Cada $/dia gasto em publicidade c/ qualquer tipo de gasolina, aumenta em 10 barris a venda daquele tipo de gasolina. Formule este problema tal que a Texaco maximize seus lucros dirios (= receita-despesa). Primeiro, note que: x11 +x12 + x13 = bar.leo 1 consum./dia. x21 +x22 + x23 = bar.leo 2 consum./dia. x31 +x32 + x33 = bar.leo 3 consum./dia.

x11 +x21 + x31 = bar.gas.1 prod./dia. x12 +x22 + x32 = bar.gas.2 prod./dia. x13 +x23 + x33 = bar.gas.3 prod./dia.48

Prof. Fogliatto

Pesquisa Operacional

47

Prof. Fogliatto

Pesquisa Operacional

Funo objetivo: (1) Ganhos/dia com vendas de gasolina: 70(x11 +x21 + x31) + 60(x12 +x22 + x32) + 50(x13 +x23 + x33) (2) Custo/dia da compra de leo: 45(x11 +x12 + x13) + 35(x21 +x22 + x23) + 25(x31 +x32 + x33) (3) Custo/dia com propaganda: a1 + a2 + a3 (4) Custo/dia produo: 4(x11 +x12 + x13 + x21 +x22 + x23+ x31 +x32 + x33) Lucro dirio: (1) - (2) - (3) - (4)Prof. Fogliatto Pesquisa Operacional 49

Funo objetivo: Max z = 21x11 +11x12 + x13 + 31x21 + 21x22 + 11x23 + 41x31 + 31x32 + 21x33 - a1 - a2 - a3 Restries: (1-3) Gas 1-3 produzida diariamente deve ser igual a demanda (no queremos estocar gasolina). Demanda diria gas 1: 3000 + demanda gas 1 gerada por publicidade = 3000 + 10a1 Demanda gas 2: 2000 + 10a2 Demanda gas 3: 1000 + 10a3 Assim: x11 + x21 + x31 - 10a1 = 3000 x12 + x22 + x32 - 10a2 = 2000 x13 + x23 + x33 - 10a3 = 1000Prof. Fogliatto Pesquisa Operacional 50

Restries: (4-6) Compra diria de leo 1-3 no deve exceder 5000 barris. x11 + x12 + x13 5000 x21 + x22 + x23 5000 x31 + x32 + x33 5000 (7) Produo/dia de gas no deve exceder 14000 barris. x11 +x12 + x13 + x21 +x22 + x23+ x31 +x32 + x33 14000 (8) Mistura de leos p/produzir gas 1 deve ter uma octanagem mdia de pelo menos 10 graus.

(9) Mistura de leos p/produzir gas 2 deve ter uma octanagem mdia de pelo menos 8 graus. 4x12 - 2x22 0 (10) Mistura de leos p/produzir gas 3 deve ter uma octanagem mdia de pelo menos 6 graus. 6x13 + 2x33 0 A restrio (10) redundante e no precisa ser includa no modelo. Por qu?

Para linealizar essa inequao, multiplica-se os dois lados pelo denominador: 2x11 - 4x21 - 2x31 0Prof. Fogliatto Pesquisa Operacional 51

Porque x13 e x33 0 por definio. Verifique a octanagem dos leos crus para entender o porqu desta redundncia.Prof. Fogliatto Pesquisa Operacional 52

(11) Mistura de leos p/produzir gas 1 deve ter um teor de enxofre menor ou igual a 1%. -0.005x11 + 0.01x21 + 0.02x13 0 (12) Mistura de leos p/produzir gas 2 deve ter um teor de enxofre menor ou igual a 2%. -0.015x12 + 0.01x32 0 (13) Mistura de leos p/produzir gas 3 deve ter um teor de enxofre menor ou igual a 1%. -0.005x13 + 0.01x23 + 0.02x33 0Prof. Fogliatto Pesquisa Operacional 53

FORMULAES MULTIPERODO (Formulao 5) O problema do estoque - O caso da empresa RegataA Regata S/A quer decidir quantos barcos produzir nos prximos 4 trimestres, de modo a satisfazer sua demanda a um menor custo:

Prof. Fogliatto

Pesquisa Operacional

54

FORMULAES MULTIPERODO (Formulao 5) O problema do estoque - O caso da empresa RegataA Regata deve atender seus pedidos em dia. No incio do trimestre, 10 barcos esto em estoque. No incio de cada trimestre, a Regata deve decidir quantos barcos sero produzidos naquele trimestre. Barcos produzidos num trimestre podem ser usados para atender pedidos naquele mesmo trimestre (pedidos so atendidos no final do trimestre). A Regata por produzir at 40 barcos/trim, a um custo de $400/barco. Para aumentar a produo, pode usar horas-extra, a um custo de $450/barco. Estocar um barco de um trim. para outro custa $20/barco. Formule o problema tal que a demanda seja atendida um mnimo custo.Prof. Fogliatto Pesquisa Operacional 55

Variveis de deciso: A Regata deve determinar quantos barcos produzir usando mo-de-obra normal e horas-extra a cada trimestre: xt = barcos produzidos por m.o. normal durante trim. t. yt = barcos produzidos por horas-extra durante trim. t. Variveis de estoque tambm devem ser definidas: it = barcos em estoque no final do trimestre t. Assim: Custo total = custo produo normal + custo produo hora-extra + custo estocagem = 400 (x1 + x2 + x3 + x4) + 450(y1 + y2 + y3 + y4) + 20 (i1 + i2 + i3 + i4)Prof. Fogliatto Pesquisa Operacional 56

1o

Funo objetivo: Min z = 400x1 + 400x2 + 400x3 + 400x4 + 450y1 + 450y2 + 450y3 + 450y4 + 20i1 + 20i2 + 20i3 + 20i4 Estoque no final de cada trimestre: it = it-1 + (xt + yt) - dt , t = 1,,4 onde dt = demanda no trimestre t. Para satisfazer a demanda ao final de cada trimestre: it-1 + (xt + yt) dt ou it = it-1 + (xt + yt) dt 0Prof. Fogliatto Pesquisa Operacional 57

Restries: (1-4) Produo normal em cada trimestre no deve exceder 40 barcos: x1 40 x2 40 x3 40 x4 40

(5-8) Demanda deve ser satisfeita a cada trimestre: i1 = 10 + x1 + y1 - 40 i3 = i2 + x3 + y3 - 75 i2 = i1 + x2 + y2 - 60 i4 = i3 + x4 + y4 - 25

Todas as variveis so do tipo 0.Prof. Fogliatto Pesquisa Operacional 58

PRTICA 3: Modelos Financeiros com mltiplos perodos.Uma empresa precisa definir sua estratgia financeira para os prximos trs anos. No tempo t = 0, $100000 esto disponveis para investimento. Planos A, B, C, D e E esto disponveis. Investir $1 em cada um desses planos gera o fluxo de caixa abaixo:

Utilizao do Whats Best na soluo de problemas de PL Whats Best um programa da famlia Lindo para otimizao linear, no-linear e inteira. Vantagens:

No mximo $75000 podem ser investidos num mesmo plano. A empresa pode ganhar 8% de juros se investir no mercado financeiro ao invs dos planos. Lucros gerados em qualquer perodo podem ser imediatamente reinvestidos (no mesmo perodo). A empresa no pode tomar dinheiro emprestado. Formule o problema tal que $ no ltimo priodo seja mximo.Prof. Fogliatto Pesquisa Operacional 59

implementado na planilha Excel; vrias funes algbricas do Excel so aceitas na formulao do problema: ABS, ACOS, AND, ASIN, ATAN, ATAN2, AVERAGE, COS, EXP, FALSE, IF, INT, LN, LOG, MAX, MIN, MOD, NOT, NPV, OR, PI, SIN, SQRT, SUM, SUMPRODUCT, TAN, TRUE, TRUNC, NORMINV, TRIAINV, EXPOINV, UNIFINV, MULTINV.Prof. Fogliatto Pesquisa Operacional 60

Outras vantagens do Whats Best Programa permite alterar coeficientes da formulao facilmente: formulao fica explicita na planilha. Facilidade de uso: princpio de programao o mesmo do Excel. Gratuito para download da rede:www.lindo.com Opo: Whats BestProf. Fogliatto Pesquisa Operacional 61

Como utilizar o programa Abra o Excel. O Whats Best deve carregar-se como uma Macro daquela planilha. Abra o arquivo XYZPort, que contm o exemplo.

Este o arquivo.

Prof. Fogliatto

Pesquisa Operacional

62

Os comandos do programa esto na barra de ferramentas e no menu

O Problema do Mix de Produo A XYZ Corporation monta dois modelos de computador. O modelo Padro gera um lucro por unidade produzida de $300, enquanto o modelo Luxo gera um lucro por unidade de $500. Os dois modelos utilizam trs componentes para sua montagem: o chassis Padro (60), o chassis de Luxo (50) e o drive de disquete (120). Disponveis em estoque

Prof. Fogliatto

Pesquisa Operacional

63

Prof. Fogliatto

Pesquisa Operacional

64

Necessidades de componentes em cada modelo O modelo Padro utiliza um chassis Padro e um drive de disquete. O modelo Luxo utiliza um chassis Luxo e dois drives de disquete. Problema: qual combinao de modelos Padro e Luxo maximiza os lucros da XYZ, considerando os componentes atualmente em estoque?Prof. Fogliatto Pesquisa Operacional 65

Determinar as variveis de deciso (adjustable cells) Variveis de deciso: Padro = quantidd de computadores padro a serem produzidos. Luxo = quantidd de computadores luxo a serem produzidos.

Prof. Fogliatto

Pesquisa Operacional

66

Determinar as variveis de deciso (adjustable cells)

Identifique as clulas como variveis de deciso (adjustable cells)

Identificao das variveis de deciso

Tela resultante Valor inicial das variveis de deciso (pode ser qualquer valor). Na busca pelo timo, o programa permitir que essas clulas assumam qualquer valor nonegativo.Prof. Fogliatto Pesquisa Operacional 67

Selecione as clulas onde foram escritos os zeros.Prof. Fogliatto

Na opo WB! do menu, selecione adjustable.Pesquisa Operacional 68

Caso as variveis de deciso sejam no-negativas, clique OK. Opo caso as variveis de deciso sejam irrestritas no sinal.

Variveis de deciso so identificadas em azul pelo WB.

Identificao das clulas selecionadas como ajustveis. Nomeie as variveis irrestritas no sinal (qualquer nome serve).

Caso as variveis sejam irrestritas no sinal, siga os passos abaixo.

Existe um cone de atalho p/ identificao de variveis de deciso no-negativas, conforme apresentado abaixo. Selecione as variveis de deciso. Clique no cone . Clulas passam a ser apresentadas em azul.

Clique em OK.

Clique em Add.

WBFree identifica variveis irrestritas

Prof. Fogliatto

Pesquisa Operacional

69

Prof. Fogliatto

Pesquisa Operacional

70

Escreva a funo objetivo (best)Coeficientes de custo da funo objetivo.

Funo objetivo: Lucro Total = (Lucro por unidade do Modelo Padro) (Qtdd de Modelos Padro produzidos) + (Lucro por unidade do Modelo Luxo) (Qtdd de Modelos Luxo produzidos) Lucro Total = 300 Padro + 500 LuxoProf. Fogliatto Pesquisa Operacional 71 Prof. Fogliatto Pesquisa Operacional 72

Frmula da funo objetivo.

Identifique a clula que contm a frmula como funo objetivo (best)Clique na clula onde a frmula da funo objetivo foi escrita. Identificao das clulas selecionadas como ajustveis.

Identifique se o problema de Minimizao ou Maximizao (default Minimizao).

Confirme clicando OK.

Selecione WB! no menu e a opo Best. Este a tela correspondente opo Best.Prof. Fogliatto Pesquisa Operacional 73 Prof. Fogliatto Pesquisa Operacional

Clula contendo funo objetivo passar a ser identificada como clula a ser maximizada (WBMAX).

74

Selecione a clula contendo a frmula da funo objetivo.

Especifique as restries (constraints) Restries informam que total de componentes utilizados deve ser quantidade disponvel em estoque. Restrio p/ componente chassis padro:(Qtdd de Modelos Padro produzidos) (No de chassis padro por modelo) + (Qtdd de Modelos Luxo produzidos) (No de chassis padro por modelo) Qtdd de chassis padro em estoque Padro 1 + Luxo 0 60

Confira se clula passou a ser identificada por WBMAX.

Clique no cone

.

Prof. Fogliatto

Pesquisa Operacional

75

Prof. Fogliatto

Pesquisa Operacional

76

Demais restries (constraints) Restrio p/ componente chassis luxo:Padro 0 + Luxo 1 50

Organizao das restries na planilha do WBFrmula da 1a restrio. Coeficientes tecnolgicos das restries.

Restrio p/ componente drive de disquete:Padro 1 + Luxo 2 120

Restrio de no-negatividade: o default do WB.

Lado direito das restries.

Prof. Fogliatto

Pesquisa Operacional

77

Prof. Fogliatto

Pesquisa Operacional

Clulas c/ as frmulas das restries. 78

Restries devem ser identificadas no WB Restries podem ser de trs tipos: , , =. Ao escrever-se o sentido da restrio numa clula da planilha: a clula adjacente esquerda passa a ser identificada como aquela que contm a frmula da restrio; a clula adjacente direita passa a ser identificada como aquela que contm a disponibilidade do recurso.Selecione a clula onde ser escrito o sentido da 1a restrio.79 Prof. Fogliatto

Identifique restries

Na opo WB! do menu, selecione constraints.

Tela resultante

Prof. Fogliatto

Pesquisa Operacional

Pesquisa Operacional

80

Confirme clicando OK.

Identificao do tipo da restrio e clulas consideradas.

Identificao da clula que deve conter a frmula da restrio.

Identificao da clula que deve conter o lado direito da restrio.

Identificao do tipo da restrio. Identificao do tipo de restrio (default ).

Repita o procedimento para as demais restries.Prof. Fogliatto Pesquisa Operacional 81 Prof. Fogliatto Pesquisa Operacional 82

Selecione a clula onde o tipo da restrio deve ser escrito.

Clique emConfira se clula passou a ser identificada como restrio.

para rodar a otimizao

Valor das variveis de deciso no ponto timo.

Valor da funo objetivo no ponto timo. Clique no cone apropriado. Situao das restries no ponto timo.Prof. Fogliatto Pesquisa Operacional 83 Prof. Fogliatto Pesquisa Operacional 84

Situao especial: Variveis de deciso devem ser inteiras

Escolha um nome para as variveis inteiras (qualquer nome serve).

Clique em OK p/ confirmar. Identificao das clulas selecionadas como ajustveis e inteiras. Identifique se variveis de deciso so inteiras binrias (0 ou 1) ou qualquer nmero inteiro no-negativo (opo General). Ateno: default do programa binrio

Tela resultante

Selecione as clulas onde foram escritos os zeros.Prof. Fogliatto

Na opo WB! do menu, selecione integer.Pesquisa Operacional 85 Prof. Fogliatto

Pesquisa Operacional

86

Outros programas de otimizao Solver do Excel Vantagem: suporta todas as funes matemticas do Excel. Desvantagem: esconde a formulao.

I. REVISO DE LGEBRA LINEARI.1. MATRIZES E VETORES Uma matriz qualquer arranjo retangular de nmeros. Uma matriz A com m linhas e n colunas uma matriz m x n. m x n a ordem de A. Forma geral: O nmero na isima linha e jsima coluna da matriz denominado aij.

Lindo Vantagem: executa anlise de sensibilidade e pode ser baixado gratuitamente da rede. Desvantagem: formulao deve ser escrita como texto.Tutorial do Lindo disponvel na apostilaProf. Fogliatto Pesquisa Operacional 87 Prof. Fogliatto

Pesquisa Operacional

88

I.1 Matrizes e Vetores Uma matriz com uma nica coluna um vetor de coluna. Uma matriz com uma nica linha um vetor de linha. Vetores, por definio, so de coluna; um vetor de linha um vetor de coluna transposto. Um vetor de zeros designado por 0. Produto Escalar de Vetores: Sejam u = [ u1,,un ] um vetor (transposto) de linha e v = [ v1,,vn ] um vetor de coluna de igual dimenso. Seu produto escalar ser o nmero: u . v = u1v1 + u2v2 ++ unvn

I.1 Matrizes e Vetores O produto escalar:

no definido.

Prof. Fogliatto

Pesquisa Operacional

89

Prof. Fogliatto

Pesquisa Operacional

90

OPERAES COM MATRIZESTransposto de uma Matriz: Seja uma matriz qualquer de ordem (m x n) :

MATRIZES E SISTEMAS DE EQUAES LINEARESa11x1 + a12x2 + . + a1nxn = b1 a21x1 + a22x2 + . + a2nxn = b2 am1x1 + am2x2 + . + amnxn = bm

O transposto de A, designado por A, ser uma matriz de ordem (n x m):

x1, x2,, xn = variveis desconhecidas (incgnitas). aij , bi = constantes Soluo para um sistema de equaes lineares com m equaes e n incgnitas = conjunto de valores para x1, x2,, xn que satisfaa as m equaes do sistema.

Prof. Fogliatto

Pesquisa Operacional

91

Prof. Fogliatto

Pesquisa Operacional

92

SISTEMAS DE EQUAES LINEARESRepresentao Matricial

INVERSO DE UMA MATRIZDefinies: A uma matriz (m x n). Se m = n, ento A uma matriz quadrada. A = [aij]. Os elementos diagonais de A so aqueles aij para os quais i = j.

(m x n)

(n x 1)

(m x 1) = matriz identidade (Im)

Ax = b

Prof. Fogliatto

Pesquisa Operacional

93

Prof. Fogliatto

Pesquisa Operacional

94

MTODO DE GAUSS-JORDAN DE INVERSO DE MATRIZESIdia Central: Determine A-1 tal que A.A-1 = I.

EXEMPLO 1:

Procedimento: Transformar A em I atravs de operaes elementares com linhas. As mesmas operaes transformaro I em A-1.

Prof. Fogliatto

Pesquisa Operacional

95

Prof. Fogliatto

Pesquisa Operacional

96

EXEMPLO 2:

Prtica 4Resolva o seguinte sistema de equaes lineares usando a matriz inversa de A:

A soluo do sistema ser dada por x = A-1.b B-1 no existe! Note que a segunda linha uma combinao linear da primeira. Prticas adicionais: inverta as matrizes abaixo (utilize a funo matriz.inv do Excel para checar o resultado)

Prof. Fogliatto

Pesquisa Operacional

97

Prof. Fogliatto

Pesquisa Operacional

98

Considere o seguinte problema:Um fabricante de mveis deseja determinar o mix ideal de produo, levando em conta preos-de-venda dos produtos e quantidade disponvel de insumos. A situao atual vem dada na tabela abaixo:

A formulao matemtica deste problema Max z = 60x1 + 30x2 s.a: 8x1 + 6x2 4x1 + 2x2 2x1 + 1.5x2 x2, x1, + 20x3 + x3 48 + 1.5 x3 20 + 0.5 x3 8 x3 0 Restrio das Tbuas Restrio de Acabamento Restrio de Carpintaria

No escrivaninhas produzidas No mesas produzidas No cadeiras produzidasProf. Fogliatto Pesquisa Operacional 99 Prof. Fogliatto Pesquisa Operacional 100

Para resolver o problema pelo Simplex, temos que adicionar variveis de folgaMax z = 60x1 + 30x2 + 20x3 s.a: 8x1 + 6x2 + x3 + f 1 + f2 4x1 + 2x2 + 1.5 x3 + f3 2x1 + 1.5x2 + 0.5 x3 x1, x2, x3, f1, f2, f3 = = = 48 20 8 0

Conceitos-chave no mtodo Simplex Variveis de folga e excesso. Folgas introduzidas em restries do tipo . Excessos introduzidos em restries do tipo .

Variveis bsicas e no-bsicas. Bsicas = var. p/ as quais o sistema de equaes resolvido.

Uma vez adicionadas variveis de folga e excesso, o problema dito no formato padro, pronto para ser resolvido atravs do mtodo Simplex!Prof. Fogliatto Pesquisa Operacional 101

No-bsicas = var. zeradas para que o sistema de equaes apresente uma soluo (equaes=variveis).Prof. Fogliatto Pesquisa Operacional 102

Solucionando problemas de otimizao linear no tableau do simplex O tableau inicial tem a seguinte estrutura:

Montagem do tableau passo a passo A montagem do tableau sempre pressupe variveis de folga formando a base inicial O no de variveis na base igual ao no de restries no problema Se no houver variveis de folga em quantidade suficiente para formar a base inicial, utilizaremos variveis de folga artificiais (vistas mais adiante)

Prof. Fogliatto

Pesquisa Operacional

103

Prof. Fogliatto

Pesquisa Operacional

104

Montagem do tableau passo a passo

Lista das variveis no cabealho das colunas Para um problema com n variveis, o tableau ter n + 2 colunas Cada varivel ser posicionada em uma coluna do tableau: Inicie pelas variveis estruturais (x1, x2, ...) Depois lista folgas, excessos e artificiais na ordem em que aparecerem nas restriesProf. Fogliatto Pesquisa Operacional 105

Primeira coluna do tableau A primeira coluna a coluna z: Ali so listadas as variveis bsicas do tableau Exemplo:

Base inicial formada por f1, f2 e f3

Prof. Fogliatto

Pesquisa Operacional

106

ltima coluna do tableau a coluna RHS (right hand side): Ali aparecem o valor atual da funo objetivo (no cruzamento entre coluna RHS e linha z) e o valor das variveis que esto na base No primeiro tableau (se as var. de folga forem a base inicial), o valor atual da funo objetivo zero e o valor das variveis na base correspondem ao lado direito das restriesProf. Fogliatto Pesquisa Operacional 107

ltima coluna do tableauExemploValor da f.o. para a base atual

Valor de f1, f2 e f3 na baseProf. Fogliatto Pesquisa Operacional 108

Linhas do tableau O tableau do simplex constitudo de m + 1 linhas (m = no de restries do problema): A primeira linha denominada linha z: Analisando a linha z se verifica se o tableau timo ou se h melhorias possveis na funo obj.

Linha z No tabelau inicial, a linha z dada pelos coeficientes de cada varivel na funo objetivo, com o sinal invertido: Variveis de folga e de escesso tm coeficientes zero, pois nunca esto na f.o. original Embaixo das variveis bsicas, na linha z do tableau, s pode-se ter o valor 0!Prof. Fogliatto Pesquisa Operacional 110

As demais linhas esto associadas s variveis que esto na base, uma por varivelProf. Fogliatto Pesquisa Operacional 109

Exemplo de montagem da linha zMax z = 60x1 + 30x2 + 20x3 s.a: 8x1 + 6x2 + x3 + f 1 + f2 4x1 + 2x2 + 1.5 x3 + f3 2x1 + 1.5x2 + 0.5 x3 x1, x2, x3, f1, f2, f3 = = = 48 20 8 0

Demais linhas do tableau Copia-se literalmente o sistema de restries do problema:

Prof. Fogliatto

Pesquisa Operacional

111

Prof. Fogliatto

Pesquisa Operacional

112

Prtica 5Considere o problema abaixo: Min z = 3x1 - x2 + 5x3 s.a

ALGORITMO SIMPLEX NO TABLEAU Passo 1 Verifique se a base atual a base tima do problema: Um problema de Minimizao est na base tima se todos os valores abaixo das variveis na linha z do tableau so negativos ou zeroEx.:

Transforme as inequaes em equaes introduzindo var. de folga. Monte o tableau inicial do problema.O algoritmo encerra aqui!Prof. Fogliatto Pesquisa Operacional 113 Prof. Fogliatto Pesquisa Operacional 114

ALGORITMO SIMPLEX NO TABLEAU Passo 1 Verifique se a base atual a base tima do problema: Um problema de Maximizao est na base tima se todos os valores abaixo das variveis na linha z do tableau so positivos ou zeroEx.:

ALGORITMO SIMPLEX NO TABLEAU

Passo 2 Identifique a varivel a entrar na base: Em problema de Minimizao, o valor mais positivo abaixo das variveis na linha z do tableau denota a varivel entrante Em problema de Maximizao, o valor mais negativo na linha z denota a varivel entrante

O algoritmo encerra aqui!Prof. Fogliatto Pesquisa Operacional 115 Prof. Fogliatto Pesquisa Operacional 116

ALGORITMO SIMPLEX NO TABLEAU

ALGORITMO SIMPLEX NO TABLEAU

Passo 3 Identifique a varivel que sai da base atravs do teste da mnima razo: Divida os nos (abaixo da linha z) no lado direito do tableau pelos nos positivos em posies correspondentes na coluna da varivel entrante (abaixo da linha z) A menor razo indica a varivel que sai da baseProf. Fogliatto Pesquisa Operacional 117

Passo 3 Exemplo (Minimizao)varivel entrante

Elemento de pivot Razes: 4/2=2 8/1=8 Menor razo! Varivel x1 sai da base para que x2 possa entrar No 2 na coluna do x2 o elemento de pivot!Pesquisa Operacional 118

Prof. Fogliatto

ALGORITMO SIMPLEX NO TABLEAU

ALGORITMO SIMPLEX NO TABLEAU

Passo 3 Exemplo (Maximizao)varivel entrante

Passo 3 Nota importante O critrio de entrada na base depende da funo objetivo do problema (maximizao ou minimizao) O teste da mnima razo, entretanto, o mesmo, independente do tipo de funo objetivo!

Razes: 4 / -2 = No vale! 8/2=4

Elemento de pivot

nica razo (menor por definio!) Varivel f2 sai da base para que f1 possa entrar No 2 na coluna do f1 o elemento de pivot!Pesquisa Operacional 119 Prof. Fogliatto Pesquisa Operacional 120

Prof. Fogliatto

ALGORITMO SIMPLEX NO TABLEAU

ALGORITMO SIMPLEX NO TABLEAU

Passo 4 Realize o pivot para a troca de base: Atravs de operaes elementares com linhas do tableau, faa com que a coluna da varivel entrante fique igual a coluna da varivel que est saindo da base Inicie as operaes pelo elemento de pivot

Passo 4 Exemplovarivel entrante

Elemento de pivot

Coluna da varivel f1 deve ficar igual coluna da varivel f2

Prof. Fogliatto

Pesquisa Operacional

121

Prof. Fogliatto

Pesquisa Operacional

122

ALGORITMO SIMPLEX NO TABLEAU

ALGORITMO SIMPLEX NO TABLEAU

Passo 4 ExemploInicie pelo elemento de pivot: ele deve virar 1

Passo 4 Exemplo

A linha de trabalho ser usada nas operaes que transformaro os demais nos da coluna da varivel entrante em zeroProf. Fogliatto Pesquisa Operacional 123

Como o problema de minimizao e no h mais valores negativos na linha z do tableau abaixo das variveis, esta a base tima do problema! Prof. Fogliatto Pesquisa Operacional 124

ALGORITMO SIMPLEX NO TABLEAU

ALGORITMO SIMPLEX NO TABLEAU

Passo 5 Volte ao passo 1

Alguns comentrios Cada tableau do simplex corresponde a uma base diferente do problema. Assim: O valor da funo objetivo nunca deve piorar a medida que a troca de bases ocorre As variveis bsicas no podem assumir valores negativos (ou houve erro no teste da mnima razo!)

Prof. Fogliatto

Pesquisa Operacional

125

Prof. Fogliatto

Pesquisa Operacional

126

ALGORITMO SIMPLEX NO TABLEAU

ALGORITMO SIMPLEX NO TABLEAU

Alguns comentrios Problemas de maximizao podem apresentar valores negativos de funo objetivo (depende da funo) e vice-versa Atualize as variveis na base: aps cada pivot, certifique-se de que o cabealho das linhas est correto

Alguns comentrios As colunas das variveis bsicas no tableau abaixo da linha z devem sempre corresponder a colunas de uma matriz identidade

Prof. Fogliatto

Pesquisa Operacional

127

Prof. Fogliatto

Pesquisa Operacional

128

Situaes especiais:

Exemplo c/ solues timas alternativasMin z = -2x1 - 4x2 s.a: x1 + 2x2 4 -x1 + x2 1 x2 0 x1,

6

1. Solues timas alternativas; 2. Soluo infinita (tendendo ao infinito). 3. Base inicial no disponvel (problema c/ variveis de excesso ou restries do tipo =).

4 B3 2 B2 B1

Reta de solues timas alternativas

zProf. Fogliatto Pesquisa Operacional 129 Prof. Fogliatto

2

4

6130

Pesquisa Operacional

Tableau

Exemplo c/ soluo tendendo ao infinitoMin z = - x1 - 3x2 s.a: x1 - 2x2 4 -x1 + x2 3 x2 0 x1,B2 2

6

Soluo tima

4

zProf. Fogliatto Pesquisa Operacional 131 Prof. Fogliatto

B1

2

4

6132

Pesquisa Operacional

Tableau

Ex. c/ base inicial no disponvelMin z = x1 - 2x2 s.a: - x1 + x2 1 x2 4 x2 0 x1,Adicionando excesso e folga6 B3 (Base tima) 4

Min z = x1 - 2x2 s.a: x1 + x2 - e1 = 1 + f1 = 4 x2 0 x1, x2, e1, f1Adicionando artificial

2 B2 B1

Min z = x1 - 2x2 + Ma1 s.a: x1 + x2 - e1 + a1 = 1 + f1 = 4 x2 x1, x2, e1, f1, a1 0Prof. Fogliatto Pesquisa Operacional 133 Prof. Fogliatto

2

4

6

z134

Pesquisa Operacional

Tableau

Prtica 6A Soluo tima nicaMax z = 60x1 + 30x2 s.a: 8x1 + 6x2 4x1 + 2x2 2x1 + 1.5x2 x 2, x1, + 20x3 + x3 48 + 1.5 x3 20 + 0.5 x3 8 x3 0

Prof. Fogliatto

Pesquisa Operacional

135

Prof. Fogliatto

Pesquisa Operacional

136

Prtica 6B Soluo Max z = 36x1 + 30x2 - 3x3 - 4x4 s.a: x1 + x2 - x3 5 - x4 10 6x1 + 5x2 x2, x 3, x4 0 x 1,

Prtica 6C Solues timas alternativas

Max z = -3x1 + 6x2 s.a 5x1 + 7x2 35 -x1 + 2x2 2 x2 0 x1,

Prof. Fogliatto

Pesquisa Operacional

137

Prof. Fogliatto

Pesquisa Operacional

138

Prtica 6D Base Inicial no-disponvel

Prtica 6E Base Inicial no-disponvel

Max z = -x1 - 2x2 s.a 3x1 + 4x2 12 2x1 - x2 2 x2 0 x1,

Min z = -x1 s.a x1 -x1 + x1,

x2 x2 1 x2 1 x2 0

Este problema no possui solues viveis (confira graficamente). Verifique como o mtodo do M-Grande vai sinalizar a ausncia de solues viveis.Prof. Fogliatto Pesquisa Operacional 139 Prof. Fogliatto Pesquisa Operacional 140

Prticas AdicionaisMax z = 2x1 + x2 - x3 s.a x1 + x2 + 2 x3 6 x1 + 4x2 - x3 4 x1, x2, x3 0 Min z = 3x1 - 3x2 + x1 + 2x2 -3x1 - x2 + x1, x2, x3 x3 5 x3 4 x3 0

O PROBLEMA DUAL Todo o problema de programao linear possui um problema dual correspondente. Chamaremos o problema original de primal e o problema dual de dual.

s.a

s.a

Max z = 2x1 - x2 x1 + x2 3 -x1 + x2 1 x1, x2, 0Pesquisa Operacional 141

Variveis do problema primal z, x1, x2,,xn. Variveis do problema dual w, y1, y2,,ym.

Prof. Fogliatto

Prof. Fogliatto

Pesquisa Operacional

142

Escrevendo o dual de um problema de progr. linearMax z = c1x1 + c2x2 + + cnxn s.a: a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 am1x1 + am2x2 + + amnxn bm

EXEMPLOMax z = 60x1 + 30x2 + 20x3 s.a: 8x1 + 6x2 + 1x3 48 4x1 + 2x2 + 1.5x3 20 2x1 + 1.5x2 + 0.5x3 8 x2, x3 0 x1, P r i m a l

Min w = b1y1 + b2y2 + + bmym s.a: a11y1 + a21y2 + + am1ym c1 a12y1 + a22x2 + + am2ym c2 a1ny1 + a2ny2 + + amnym cn

Min w = 48y1 + 20y2 + 8y3 s.a: 8y1 + 4y2 + 2y3 60 6y1 + 2y2 + 1.5y3 30 1y1 + 1.5y2 + 0.5y3 20 y1, y2, y3 0

D u a l

Prof. Fogliatto

Pesquisa Operacional

143

Prof. Fogliatto

Pesquisa Operacional

144

A isima restrio do dual corresponde isima varivel do primalUsando a tabela abaixo, pode-se achar o dual de qualquer primal:

OUTRO EXEMPLOMax z = 2x1 + x2 s.a: 2x1 + x2 = 2 2x1 - x2 3 x1 - x2 1 x1 0, x2 irrestr. P r i m a l

Variveis

Restries

Restries

Variveis

Min w = 2y1 + 3y2 + 1y3 s.a: 2y1 + 2y2 + y3 2 y1 - y2 - y3 = 1 y1 irrestr., y2 0, y3 0

D u a l

Prof. Fogliatto

Pesquisa Operacional

145

Prof. Fogliatto

Pesquisa Operacional

146

INTERPRETAO ECONMICA DO PROBLEMA DUALO exemplo visto anteriormente: Max z = 60x1 + 30x2 + 20x3 s.a: 8x1 + 6x2 + 1x3 48 4x1 + 2x2 + 1.5x3 20 2x1 + 1.5x2 + 0.5x3 8 x2, x3 0 x1, Corresponde modelagem matemtica do seguinte problema:

O DUAL DESTE PROBLEMA :Min w = 48y1 + 20y2 + 8y3 s.a: 8y1 + 4y2 + 2y3 60 6y1 + 2y2 + 1.5y3 30 1y1 + 1.5y2 + 0.5y3 20 y2, y3 0 y1, Escrivaninha Mesa Cadeira

Restries associadas com escrivaninhas, mesas e cadeiras, respectiv. y1 associado com tbuas; y2 com acabamto; y3 com carpintaria. Suponha uma situao onde exista escassez de insumos. Um outro fabricante de mveis deseja comprar os insumos disponveis na fbrica de escrivaninhas, mesas e cadeiras. A pergunta-chave : qual o gio mximo a ser cobrado pelos insumos?

Prof. Fogliatto

Pesquisa Operacional

147

Prof. Fogliatto

Pesquisa Operacional

148

Definindo as variveis do problema dual y1 = gio mximo cobrado por uma tbua de madeira; y2 = gio mximo cobrado por 1 hora de acabamento; y3 = gio mximo cobrado por 1 hora de carpintaria O gio total a ser cobrado por estes insumos corresponder funo objetivo: Min w = 48y1 + 20y2 + 8y3

O comprador deseja o menor preo, mas o preo deve ser atraente o suficiente para induzir o fabricante de escrivaninhas a vender seus insumosAssim: 8y1 + 4y2 + 2y3 60Restrio das escrivaninhas

Ou seja, se comprarmos todos os insumos nas quantidades necessrias para produzir uma escrivaninha, o gio a ser pago deve ser, no mnimo, o que o fabricante lucraria com a venda daquele produto. O mesmo ocorre com as outros produtos: 6y1 + 2y2 + 1.5y3 30 1y1 + 1.5y2 + 0.5y3 20Restr. das mesas

Note que a funo objetivo busca minimizar o custo de compra: este o ponto de vista do comprador.

Restr. das cadeiras150

Prof. Fogliatto

Pesquisa Operacional

149

Prof. Fogliatto

Pesquisa Operacional

Para determinarmos o menor gio de compra dos insumos que mantenha a venda desses insumos interessantes para o fabricante, devemos resolver o problema dual

ExerccioDetermine o dual do seguinte problema de programao linear: Max z = x1 + s.t.: 3x1 + 2x1 + x 1,151 Prof. Fogliatto

As variveis y1, y2, y3 so normalmente denominadas preossombra dos insumos.

restrio corresponde Por definio, o preo-sombra da melhoria no valor z da funo objetivo ocasionada pelo incremento de uma unidade no lado direito da restrio [ou seja, de bi para (bi + 1)].Prof. Fogliatto Pesquisa Operacional

isima

2x2 x2 6 x2 = 5 x2 0Pesquisa Operacional 152

Como ler a soluo tima do dual a partir da linha 0 (ou linha z) do tableau timo do primal Caso 1 - Primal = MaxPara resolver o problema abaixo: Max z = 3x1 + s.a: 1x1 + 2x2 + 5x3 3x2 + 2x3 15 x3 5 2x2 2x1 + x2 - 5x3 = 10 x2, x3 0 x 1,

Tableau timo

Adicionar var. folga f1 Adicionar var. excesso e2 e art. a2 Adicionar var. artificial a3

A base inicial ser formada por B = { f1, a2, a3}. Usaremos o Mtodo do M-Grande para solucionar este problema. O tableau timo vem dado a seguir...Prof. Fogliatto Pesquisa Operacional 153 Prof. Fogliatto Pesquisa Operacional 154

Regras para identificao da soluo tima dual na linha 0 (ou z) do tableau timo do primal (Max)Valor timo da var. dual yi qdo restrio i do tipo

No tableau timo do exemplo anterior:y1 -y2 y3-M

Coeficiente de fi na linha 0 do tableau timo

Valor timo da var. dual yi qdo restrio i do tipo

-(Coeficiente de ei) na linha 0 do tableau timo

Valor timo da var. dual yi qdo restrio i do tipo =

(Coeficiente de ai na linha 0 do tableau timo) - M

Ou seja, o problema dual possui a seguinte soluo tima: y1 =51/ 23;

y2 = -58/23; y3 = 9/23Pesquisa Operacional 156

Prof. Fogliatto

Pesquisa Operacional

155

Prof. Fogliatto

Conferindo o resultado na funo objetivo do problema dualMin w = 15y1 + 5y2 + 10y3 y1 =51/ 23;

Regras para identificao da soluo tima dual na linha 0 (ou z) do tableau timo do primal (Min)Valor timo da var. dual yi qdo restrio i do tipo

Coeficiente de fi na linha 0 do tableau timo

y2 = -58/23; y3 = 9/23

Valor timo da var. dual yi qdo restrio i do tipo

-(Coeficiente de ei) na linha 0 do tableau timo

w = 565/23 Valor timo da var. dual yi qdo restrio i do tipo = (Coeficiente de ai na linha 0 do tableau timo) + M

Prof. Fogliatto

Pesquisa Operacional

157

Prof. Fogliatto

Pesquisa Operacional

158

Exerccio

Prof. Fogliatto

Pesquisa Operacional

159