382 Apostila Pesquisa Operacional Parte 1

  • Published on
    23-Aug-2014

  • View
    203

  • Download
    36

Transcript

<p>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</p> <p>Engenharia de Produo DEPROT / UFRGS Profs. Flavio Fogliatto, Ph.D.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>2</p> <p>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</p> <p>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.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>3</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>4</p> <p>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</p> <p>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.</p> <p>Pesquisa Operacional</p> <p>6</p> <p>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.</p> <p>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</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>7</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>8</p> <p> 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</p> <p> 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.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>9</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>10</p> <p> 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.</p> <p> 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</p> <p> 100</p> <p>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.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>11</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>12</p> <p>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</p> <p> RESTRIES DE SINAL Identificam os tipos de valores que as variveis podem assumir. Podem ser de trs tipos: 0 0 irrestrita</p> <p> 80</p> <p>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</p> <p> 4013 Prof. Fogliatto</p> <p> 100 80 40 x1 x1, x2 0</p> <p>Restrio de horas de acabamento Restrio de horas de carpintaria Restrio de demandaPesquisa Operacional 14</p> <p>Pesquisa Operacional</p> <p>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.</p> <p>Soluo - Prtica 1 Variveis de Deciso: x1 = no de acres de milho a serem plantados x2 = no de acres de trigo a serem plantados</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>15</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>16</p> <p>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.</p> <p>Representao grfica Representao da restrio 2x1 + 3x2 = 6:x24 3 2</p> <p>2x1 + 3x2 6</p> <p>(0,0)</p> <p>x12 3 4</p> <p>2x1 + 3x2 6Prof. Fogliatto Pesquisa Operacional 17 Prof. Fogliatto Pesquisa Operacional</p> <p>2x1 + 3x2 = 618</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>40</p> <p>Todas as demais restries so consideradas no-crticas. Ex.: restrio (4) e restries de sinal no grfico anterior.</p> <p>20</p> <p>z</p> <p>(3)</p> <p>z = 3(20) + 2(60) = 180</p> <p>Prof. Fogliatto</p> <p>20</p> <p>40</p> <p>Pesquisa Operacional</p> <p>60</p> <p>80</p> <p>100</p> <p>x119 Prof. Fogliatto Pesquisa Operacional 20</p> <p>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</p> <p>x2 10</p> <p>Ponto timo no inteiro: Testar pontos (4,1), (3,2), (4,2), checando restries e z. Usar programao inteira.</p> <p>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.</p> <p>8</p> <p>6</p> <p>Ponto timo: (3.6, 1.4)</p> <p>4</p> <p>2</p> <p>zProf. Fogliatto</p> <p>2</p> <p>4</p> <p>6</p> <p>8</p> <p>10</p> <p>x123 Prof. Fogliatto Pesquisa Operacional 24</p> <p>Pesquisa Operacional</p> <p>CASOS ESPECIAIS:(2) Problemas com soluo tendendo ao infinito.</p> <p>CASOS ESPECIAIS:(3) Problemas sem soluo</p> <p>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.</p> <p>Nestes casos, as restries no formam nenhum espao de solues viveis.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>25</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>26</p> <p>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:</p> <p> Formule o problema e encontre a soluo tima graficamente.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>27</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>28</p> <p>Problemas Tpicos de Formulao</p> <p>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:</p> <p>Escolha da dieta</p> <p> 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</p> <p> Variveis de deciso: x1 = pores de biscoitos; x2 = pores de sorvete; x3 = pores de refrigerante; x4 = pores de torta de queijo;</p> <p> 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</p> <p> 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</p> <p>(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.</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>31</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>32</p> <p>FORMULAO 2: Otimizao da Fora de TrabalhoUma agncia de correios necessita de um nmero diferente de funcionrios, de acordo com o dia da semana:</p> <p> Variveis de deciso: xi = nm. de empregados trabalhando no dia i; Funo objetivo: Min z = x1 + x2 + x3 + x4 + x5 + x6 + x7</p> <p>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.</p> <p> Restries: x1 x2 x3 x4 x5 x6 17 13 15 19 14 16 x7 11 xi 0 Qual o problema com essa formulao?</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>33</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>34</p> <p>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</p> <p>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.</p> <p> Funo objetivo: Min z = x1 + x2 + x3 + x4 + x5 + x6 + x7</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>36</p> <p> 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.</p> <p> 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</p> <p>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</p> <p>Prof. Fogliatto</p> <p>Pesquisa Operacional</p> <p>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</p> <p>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</p> <p>EXEMPLO DE FORMULAO: Formulao 3 Uma empresa est considerando 5 oportunidades de investimento, com caractersticas dadas a seguir:</p> <p> Varivel de deciso: A empresa deseja determinar qual frao de cada investimento deve ser comprada: xi = frao do investimento i comprada pela empresa.</p> <p>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 disponv...</p>