382 Apostila Pesquisa Operacional Parte 1

Embed Size (px)

Text of 382 Apostila Pesquisa Operacional Parte 1

  • Pesquisa Operacional

    Engenharia de ProduoDEPROT / UFRGS

    Profs. Flavio Fogliatto, Ph.D.

    Prof. Fogliatto Pesquisa Operacional 2

    EmentaINTRODUO1. Programao Matemtica2. Reviso de lgebra Linear 3. Uso de pacotes computacionais na soluo de problemas

    PROGRAMAO LINEAR1. Introduo Programao Linear 2. O algoritmo Simplex

    Prof. Fogliatto Pesquisa Operacional 3

    Ementa

    MODELOS DE REDES1. O problema do transporte2. O problema da designao3. O problema do transbordo4. Modelos de Redes

    TPICOS AVANADOS1. Programao Inteira

    Prof. Fogliatto Pesquisa Operacional 4

    Referncias Bibliogrficas

    LIVRO-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 5

    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:

    BancosInstituies Financeiras

    Empresas de Transportes, etc.

    Vamos introduzir a PL a partir de um exemplo.

    Prof. Fogliatto Pesquisa Operacional 6

    EXEMPLO: O caso Politoy

    A 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.

    Prof. Fogliatto Pesquisa Operacional 7

    EXEMPLO: O caso Politoy

    A 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.

    Prof. Fogliatto Pesquisa Operacional 8

    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 semanax2 = nm. de trens produzidos a cada semana

  • Prof. Fogliatto Pesquisa Operacional 9

    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 + 9x2custo semanal com mo-de-obra: 14x1 + 10x2

    Prof. Fogliatto Pesquisa Operacional 10

    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 funoobjetivo.

    Assim:Max z = 3x1 + 2x2

    Os nmeros 3 e 2 so chamados coeficientes da funo objetivo. Elesindicam a contribuio de cada varivel nos ganhos da empresa.

    Prof. Fogliatto Pesquisa Operacional 11

    RESTRIES

    A medida que x1 e x2 crescem, o valor da funo objetivo aumenta.

    Mas x1 e x2 no podem crescer indefinidamente. Trs restrieslimitam 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 dedeciso x1 e x2.

    Prof. Fogliatto Pesquisa Operacional 12

    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 100Observe que todos os termos de uma restrio devem ter a mesmaunidade de medida.Os valores 2 e 1 na restrio so denominados coeficientes tecnolgicos.

  • Prof. Fogliatto Pesquisa Operacional 13

    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 80

    Restrio 3:

    A restrio 3 definida pela limitao do nmero de soldados produ-zidos por semana (devido a limitaes na demanda):

    x1 40

    Prof. Fogliatto Pesquisa Operacional 14

    RESTRIES DE SINAL

    Identificam os tipos de valores que as variveis podem assumir.

    Podem ser de trs tipos: 0 0 irrestritaCombinando a funo objetivo e as restries, chega-se a formulaomatemtica do problema da Politoy:

    max z = 3x1 + 2x2

    Sujeito a:2x1 + x2 100

    x1 + x2 80x1 40

    x1, x2 0

    Restrio de horas de acabamento

    Restrio de horas de carpintaria

    Restrio de demanda

    Prof. Fogliatto Pesquisa Operacional 15

    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.

    Prof. Fogliatto Pesquisa Operacional 16

    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 17

    ESPAO DE SOLUES E SOLUO TIMA

    O espao de solues formado por todos os pontos quesatisfazem as restries do problema.

    A soluo tima em um problema de maximizao corresponde ao ponto no espao de solues onde o valor dafuno objetivo mximo.

    Prof. Fogliatto Pesquisa Operacional 18

    Representao grfica

    Representao da restrio 2x1 + 3x2 = 6:

    (0,0) 2 3 4

    2

    3

    4

    2x1 + 3x2 = 62x1 + 3x2 6

    2x1 + 3x2 6

    x1

    x2

    Prof. Fogliatto Pesquisa Operacional 19

    Representao grfica do problema Politoy

    20

    20

    40

    40

    60

    60

    80

    80

    100

    100

    (2)

    (4)

    (3)

    O espao de solues encontra-sehachurado.

    (2) - (4) denotam as restries.

    As restries de sinal restringem o problemaao primeiro quadrante do espao bi-dimens.

    Soluo tima:(1) Desenhe o vetor z.

    z

    (2) Desenhe linhas ortogonais ao vetor z. Essas so as linhas de isocusto.

    Ponto timo: (20,60)

    (3) Calcule o valor de z no ponto timo.

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

    x1

    x2

    Prof. Fogliatto Pesquisa Operacional 20

    Restries crticas (binding) e no-crticas

    Uma 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.

    Todas as demais restries so consideradas no-crticas.

    Ex.: restrio (4) e restries de sinal no grfico anterior.

  • Prof. Fogliatto Pesquisa Operacional 21

    Solucione graficamente o problema e identifique o tipo de conjuntode solues resultante.

    Um empresa de eletrodomsticos planeja veicular seus produtos emcomerciais 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 milhesde homens e custam $50000.Comerciais nos jogos so vistos por 2 milhes de mulheres e 12 milhesde 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 menorcusto possvel?

    Outro exemplo:

    Prof. Fogliatto Pesquisa Operacional 22

    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

    Restries: Pblico feminino: 7x1 + 2x2 28 Pblico masculino: 2x1 + 12x2 24 x1, x2 0

    Soluo tima: (3.6, 1.4) com z = $320. A soluo nica.

    A soluo grfica ...

    Prof. Fogliatto Pesquisa Operacional 23

    2

    2

    4

    4

    6

    6

    8

    8

    10

    10z

    Ponto timo: (3.6, 1.4)

    x1

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

    Prof. Fogliatto Pesquisa Operacional 24

    CASOS ESPECIAIS:

    (1) Problemas com solues alternativas (vrias solues sosimultaneamente timas).

    Nestes casos, a linha de isocusto, ao abandonar o espao desolues viveis, intersecciona com uma linha inteira (e no somente um ponto) desse conjunto.

  • Prof. Fogliatto Pesquisa Operacional 25

    (2) Problemas com soluo tendendo ao infinito.

    Nestes casos, as restries formam um espao aberto de soluesviveis.

    Se a funo o