382 Apostila Pesquisa Operacional Parte 2

Embed Size (px)

Text of 382 Apostila Pesquisa Operacional Parte 2

  • Pesquisa Operacional

    Parte 2

    Graduao em Engenharia de Produo

    DEPROT / UFRGS Prof. Flavio Fogliatto, Ph.D.

    Prof. Fogliatto PO - Graduao 2

    O Problema do TransporteDescrio Geral de um problema de transporte:

    1. Um conjunto de m pontos de fornecimento a partir dos quais uminsumo embarcado ou remetido.O ponto de fornecimento i pode fornecer no mximo si unidades.

    2. Um conjunto de n pontos de demanda para os quais o insumo remetido.O ponto de demanda j deve receber pelo menos dj unidades do insumo.

    Prof. Fogliatto PO - Graduao 3

    Descrio Geral de um problema de transporte

    3. Cada unidade produzida no ponto de fornecimento i e remetida ao ponto de demanda j incorre num custo de cij.

    Prof. Fogliatto PO - Graduao 4

    Formulao do ProblemaSeja xij = no de unidades despachadas do ponto de fornecimento i para

    o ponto de demanda j.

    A formulao genrica do problema do transporte ser:

    Restries de fornecimento

    Restries de demanda

  • Prof. Fogliatto PO - Graduao 5

    Problema Balanceado

    Um problema de transporte considerado balanceado se:

    Ou seja, o fornecimento supre toda a demanda.

    Num problema balanceado, as restries so todas igualdades.

    Prof. Fogliatto PO - Graduao 6

    Como balancear um problema de transporte quando a capacidade de fornecimento excede a

    demandaCria-se um ponto fictcio de demanda. A demanda nesse ponto ser igualao excedente da capacidade.

    Como balancear o problema quando a demanda maior que a capacidadede fornecimento?

    Neste caso, o problema no possui solues viveis.

    Como alternativa, pode-se adicionar um ponto fictcio de fornecimento.O custo de fornecimento daquele ponto ser igual penalizao incorridapelo no fornecimento do insumo.

    Prof. Fogliatto PO - Graduao 7

    O Tableau de Transporte

    c11 c12 c1n

    c21 c22 c2n

    cm1 cm2 cmn

    Demanda d1 d2 dn

    Fornecimento

    s1

    s2

    sm

    Prof. Fogliatto PO - Graduao 8

    ExemploDois reservatrios de gua abastecem trs cidades. Cada reservatrio pode abastecer at 50 milhes de litros de gua por dia. Cada cidade necessita receber 40 milhes de litros de gua por dia.

    Associado a cada milho de litros de gua no fornecido por dia existe uma multa. A multa na cidade 1 de $20; na cidade 2 de $18; na cidade 3 de $23.

    Os custos do transporte entre reservatrios e cidades vemdado ao lado...

    Reserv. 1

    Reserv. 2

    Cid.1 Cid.2 Cid.3

    $7 $8 $8

    $9 $7 $8

  • Prof. Fogliatto PO - Graduao 9

    Tableau do Simplex

    7 8 8

    9 7 8

    Cid. 1 Cid. 2 Cid. 3

    20 18 23

    Res. 1

    Res. 2

    Res. Artif.

    Demanda 40 40 40

    Capacidade

    50

    50

    20

    Prof. Fogliatto PO - Graduao 10

    Prtica:

    Prof. Fogliatto PO - Graduao 11

    Mtodo do Extremo Noroeste para Determinao da Soluo Vivel Inicial de um

    problema de TransporteInicie o mtodo considerando a clula (1,1) do tableau. Faa com quex11 seja o maior valor possvel.

    Obviamente, x11 = Min (d1, s1).

    Se x11 = s1, desconsidere as demais clulas na primeira linha do tableau,j que nenhuma outra varivel bsica vir desta linha. Atualize o valorde d1 para d1 - s1.

    Se x11 = d1, desconsidere as demais clulas na primeira coluna do tableau,j que nenhuma outra varivel bsica vir desta coluna. Atualize o valorde s1 para s1 - d1.

    Prof. Fogliatto PO - Graduao 12

    Mtodo do Extremo Noroeste para Determinao da Soluo Vivel Inicial de um

    problema de Transporte

    Se x11 = s1 = d1, desconsidere as demais clulas na primeira linha ouna primeira coluna do tableau (mas no ambas). Se voc escolher descon-siderar a linha 1, mude d1 para 0. Se voc escolher desconsiderar acoluna 1, mude s1 para 0.

    Repita o procedimento, sempre escolhendo a clula posicionada noextremo noroeste do tableau (desde que ela no esteja em uma linhaou coluna eliminada anteriormente).

    Ao cabo de (m + n - 1) iteraes chega-se a uma base vivel inicialpara o problema.

  • Prof. Fogliatto PO - Graduao 13

    ExemploO mtodo do extremo noroeste no utiliza os custos, omitidos nos tableausabaixo:

    6

    5

    10

    15

    4812

    x11 = Min {12, 5} = 5

    5

    7

    0

    Prof. Fogliatto PO - Graduao 14

    Exemplo

    6

    0

    10

    15

    48

    7

    x21 = Min {10, 7} = 7

    5

    0

    7

    3

    Prof. Fogliatto PO - Graduao 15

    Exemplo

    6

    0

    3

    15

    48

    7

    x22 = Min {8, 3} = 3

    5

    0

    0

    5

    3

    Prof. Fogliatto PO - Graduao 16

    Exemplo

    6

    0

    0

    15

    45

    7

    x32 = Min {15, 5} = 5

    5

    0

    10

    0

    3

    5

  • Prof. Fogliatto PO - Graduao 17

    Exemplo

    6

    0

    0

    10

    40

    7

    x33 = Min {10, 4} = 4

    5

    0

    6

    0

    3

    5 4

    Prof. Fogliatto PO - Graduao 18

    Exemplo

    6

    0

    0

    6

    40

    7

    x34 = Min {6, 6} = 6

    5

    00

    3

    5 4 06

    BaseInicialVivel

    Prof. Fogliatto PO - Graduao 19

    Prtica:Determine uma base inicial para o problema anterior.

    Prof. Fogliatto PO - Graduao 20

    O Mtodo Simplex para problemas de transporte

    Precisamos calcular os valores correspondentes a linha z do tableau do simplex.

    Decidindo qual varivel no-bsica deve entrar na base

    O clculo desses valores envolve determinar um menor circuito ou loopcontendo algumas variveis bsicas e a varivel no-bsica em questo.

    Existe um loop nico possvel para cada varivel no-bsica.

  • Prof. Fogliatto PO - Graduao 21

    Exemplo

    2 3 4

    14 12 5

    12 15 9

    10 10

    0 20 10

    9

    1

    3

    10 10 20 50

    20

    30

    4040

    Capacidd

    Demanda

    Base inicial determinada pelo mtodo do extremo noroeste.

    Prof. Fogliatto PO - Graduao 22

    Determine a varivel no-bsica a entrar na base

    Calcule os valores correspondentes linha z para cada varivel no-bsica:

    2 3 4

    14 12 5

    12 15 9

    10 10

    0 20 10

    9

    1

    340

    1. Determine um loopde var. bsicas quecontenha a var. no-bsica.

    Iniciando com x14:

    2. Alterne sinais pos. e neg. nas var. bs.extremas.+-

    +

    3. Some os cij de acordo com os sinais.

    (+1-12+3) = -8

    4. Subtraia o coef. de custo da var. no-bs. em questo do resultado(-8) - 9 = -17

    -17

    Prof. Fogliatto PO - Graduao 23

    Clculo para x13

    2 3 4

    14 12 5

    12 15 9

    10 10

    0 20 10

    9

    1

    340

    +-

    +

    (+5-12+3) = -4 (-4) - 4 = -8

    -17-8

    Prof. Fogliatto PO - Graduao 24

    Repetindo o clculo p/ as demais var. no-bsicas

    2 3 4

    14 12 5

    12 15 9

    10 10

    0 20 10

    9

    1

    340

    -17-8

    -2-1+1

    -3

    Num problema de minimizao a varivel mais positiva entra na base.

  • Prof. Fogliatto PO - Graduao 25

    Para verificar qual varivel deve sair da base, determine um loop contendo a var. entrante e

    algumas variveis bsicas

    2 3 4

    14 12 5

    12 15 9

    10 10

    0 20 10

    9

    1

    340

    -17-8

    -2-1+1

    -3

    Prof. Fogliatto PO - Graduao 26

    A primeira clula bsica do loop recebe um sinal positivo, a segunda um sinal negativo, e

    assim por diante...Dentre as clulaspositivas, selecioneaquela de menorvalor: esta a var.que sair da base. 2 3 4

    14 12 5

    12 15 9

    10 10

    0 20 10

    9

    1

    340

    -17-8

    -2-1+1

    -3

    + -

    +-

    +A varivel entranteassumir o valorda varivel que saida base.

    Prof. Fogliatto PO - Graduao 27

    Atualize o valor das demais clulas do loop: clulas com sinal + tm seu valor decrescido em ; clulas

    com sinal -, tm seu valor acrescido de . A varivel entrante entra na base com valor .

    2 3 4

    14 12 5

    12 15 9

    10 10

    20 10

    9

    1

    340

    + -

    +-

    +0

    Prof. Fogliatto PO - Graduao 28

    Novo tableau

    2 3 4

    14 12 5

    12 15 9

    10 10

    20 10

    9

    1

    3400

    -4

    -7 -16

    -1

    -2 -2

    Nenhuma var. no-bs. com zij - cij > 0 tableau timo!

  • Prof. Fogliatto PO - Graduao 29

    Prtica:

    Resolva o problema proposto no Slide 9. Resolva o problema do ao.

    Prof. Fogliatto PO - Graduao 30

    O Problema do Transbordo

    Ponto de fornecimento - pode remeter insumos para outros pontosmas no pode receber.

    Ponto de demanda - pode receber insumos de outros pontosmas no pode remeter.

    Ponto de transbordo - remete e recebe insumos de outros pontos.

    Prof. Fogliatto PO - Graduao 31

    Exemplo

    A BITCO monta PCs em Manaus (150 PCs/dia) e Assuncin do Paraguai (200 PCs/dia) e remete para suas lojas em So Paulo e Recife, totalizando 130 PCs por loja.

    Os PCs so remetidos via area. A BITCO suspeita que devido promoes e uso de outras empresas areas, seja mais econmico usar Braslia e Curitiba como pontos de transbordo.

    Os custos de transporte por PC vm dados a seguir.

    Prof. Fogliatto PO - Graduao 32

    Custos

  • Prof. Fogliatto PO - Graduao 33

    ExemploDeseja-se minimizar o custo do frete:

    Manaus

    Assuncin

    Braslia

    Curitiba

    SPaulo

    Recife

    Prof. Fogliatto PO - Graduao 34

    O problema do transbordo resolvido como um problema balanceado de transportes

    PASSO 1 - Balanceie o problema, se necessrio.

    Por exemplo:

    Capacidade > Demanda

    Acrescente pto de demanda artificial

    Capacidade = 0

    Demanda =