Problemas Lineares Especiais Fluxo em Redes-2020 1

14 Problemas Lineares Especiais – Fluxo em Redes © 2020 Prof. Sérgio F. Mayerle 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 25  Descrição do problema  Formulação matemática do problema  Equivalência entre problemas de redes  Algoritmo simplex especializado  Exemplo 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 25 Descrição do problema O problema do fluxo de mínimo custo em redes ocupa uma posição relevante entre os modelos de otimização aplicados à logística. Dada uma rede   , G  N A , onde N é o conjunto de nós e A o conjunto de arcos, o problema é caracterizado como:  Pelo menos um dos nós de N é de oferta (produção); pelo menos um dos nós de N é de demanda (consumo); os demais são de transbordo;  O fluxo através de um arco  ,i j  A , que conecta os nós ,i j  N é permitido apenas na direção de i para j (se o fluxo puder ocorrer nas duas direções, isso é representado por um par de arcos em direções opostas);  A quantidade máxima de fluxo permitida no arco  ,i j  A é limitada pela capacidade ij q do arco;  Cada unidade de fluxo que atravessa o arco  ,i j  A custa ijc ;  A rede   , G  N A é conexa, direcionada, e possui capacidade suficiente para alocar todo fluxo gerado nos nós de oferta aos nós de demanda;  O objetivo é minimizar o custo total de envio, através da rede, da oferta disponível para satisfazer toda a demanda (ou alternativamente, maximizar o lucro total). 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 25 Formulação matemática do problema A formulação matenática do problema de fluxo de mínimo custo em redes (NP – network flow problem) é dada por: ( , ) |( , ) |( , ) . : 0 ( , ) (1.a) (1.b) (1.c) ij ij i j A kj ik k j k j A i i k A ij ij Min z c x s a x x b k N x q i j A                onde: ijx fluxo no arco  ,i j  A ; ij q capacidade máxima do arco  ,i j  A ; ijc custo unitário de transporte associado ao arco  ,i j  A ; kb parâmetro associado ao nó k  N ; se kb  0 , trata-se da quantidade ofertada pelo nó; se kb  0 , trata-se da demanda do; se kb  0 trata-se de um nó de transbordo. Figura 01 – Grafo Caso exista um nó de transbordo com custo ic e capacidade iq , deve-se modelar como: ic iq iq ic Figura 02 – Representação de custos e capacitades em nós 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 25 Equivalência entre problemas de redes Problema de caminho mínimo Consiste em encontrar um caminho de mínimo custo entre dois vértices dados, ,s t  N . Resolve-se com as seguintes adaptações no modelo (1.a)-(1.c):   0 ( , ) 1 1 0 , ij s t k x i j A b b b k N s t              Problema de atribuição Pode-se resolver o problena de atribuição considerando o grafo bipartido   , G N N A     e as seguintes adaptações no modelo (1.a)-(1.c): 0 1 1 e ij i j x i N j N b i N b j N                    Problema de transportes Pode-se resolver o problema de transportes considerando o grafo bipartido   , G N N A     , com as seguintes adaptações no modelo (1.a)-(1.3): 0 ( ) ( ) e ij i i j j x i N j N b O i N oferta b D j N demanda                  Problema de máximo fluxo Neste problema se considera um par de vértices, ,s t  N , entre os quais deseja-se alocar o máximo fluxo possível. Para resolver este problema inclui-se um arco adicional que conecta o nó t  N ao nó s  N , com as seguintes adaptações ao modelo (1.a)-(1.c): 0 ( , ) 1 0 ij ts k c i j A c b k N         14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 25 Algoritmo simplex especializado P1 Incialização: para cada nó k  N com kb  0 inclua um arco artificial ( , ) s k com capacidade sk k q  b e custo 0 csk  (ou igual ao custo de produção, se for o caso); para cada nó k  N com kb  0 inclua um arco artificial ( , ) k t com capacidade kt k q  b e custo 0 kt c  ; inclua um arco ( , ) t s com capacidade ts q   e custo ts c   . Faça ijx  0 , ( , ) i j A   P2 Expansão da árvore básica: enraize em s  N uma árvore básica T . Expanda T , usando arcos que satisfaçam a condição ij ij x  q , até que todos os nós estejam cobertos por T . P3 Rotulação do árvore básica: associe ao nó s  N o rótulo 0 s   , e repita até que todos os nós estejam rotulados: a) para arcos ( , ) i j na árvore, com i rotulado e j não rotulado faça j i ijc     ; b) para arcos ( , ) i j na árvore, com i não rotulado e j rotulado faça i j ijc     ; P4 Cálculo dos preços duais: para cada arco ( , ) i j T calcule os preços duais ij i ij j z c       ; P5 Seleção do arco entrante: encontre um arco ( , ) m n T tal que: i) mn mn x  q e 0 zmn  , e faça 1    ; ou ii) 0 xmn  e 0 zmn  , e faça 1    . Se não existe arco que satisfaça (i) ou (ii), pare. A solução maximiza o atendimento da demanda ao menor custo total possível. 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 25 P6 Determine o ciclo formado pelo arco entrante ( , ) m n T e a árvore T . Neste ciclo, caso 1    faça circular um fluxo incremental  no sentido do arco entrante; caso 1    , faça o fluxo incremental  circular no sentido contrário do arco entrante. P7 Atualização dos fluxos: aumente ou diminua o fluxo nos arcos do ciclo, de acordo com o sentido do fluxo incremental . P8 Atualização da base: inclua em T o arco entrante ( , ) m n , e exclua o arco ( , ) i j pertencente ao ciclo, tal que ij ij x  q ou ijx  0 . Se mais de um arco atender este requisito, escolha apenas um para ser retirado. Volte ao passo P3. 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 25 Exemplo numérico Considere a rede e seus respectivos dados apresentados abaixo. Determine a solução ótima. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 100 Q  2 110 Q  4 90 D  5 100 D  Figura 03 – Dados do problema de fluxo de custo mínimo em redes 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 25 Solução Considerando o passo P1 do algoritmo, são incluídas na rede dois nós artificiais, denotados por s e t , além de cinco arcos artificiais: ( ,1) s , ( ,2) s , (4, )t , (5, )t e ( , ) t s . Estes nós e arcos artificiais encontram-se representados na rede estendida por linhas tracejadas, com os respectivos custos e capacidades especificados em conformidade com as instruções de P1. O passo P2 determina a expansão de uma árvore enraizada em s ; esta árvore é formada pelos arcos desenhados com linhas mais espessas. O passo P3 determina o cálculo dos rótulos ( i ) associados aos nós, enquanto que P4 determina o cálculo dos custos duais (  ijz ) como mostra a figura 03. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 0   3 2   4 7   5 9   7 t  25 2 z  14 3 z  13 1 z  45 1 z  5 2 z t  993  tsz   25 3 z  Figura 03 – Rede estendida rotulada 1ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 25 Nesta situação, é selecionado o arco   ,t s para ter seu fluxo incrementado ( 1    ), pois 0  tsz  e ts ts x  q . Com isto fecha-se o ciclo  s,2,3,4, ,  t s , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (s,2) +1 0 0 110 110 67 (2,3) +1 0 0 70 70 67 (3,4) +1 0 0 67 67 67 (4,t) +1 0 0 90 90 67 (t,s) +1 0 0 1000 1000 67 Máximo Fluxo Incremental do Ciclo 67 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 25 Com isto tem-se uma nova árvore básica, na qual entra   ,t s e sai   3,4 , como mostra a figura 04. Nesta figura já se tem a nova rotulação da árvore. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 0   3 2   4 1000   5 9   1000 t  25 3 z  14 990 z   13 1 z  45 994 z  5 991 z t   67 67 67 67 34 993 z   Figura 04 – Rede estendida rotulada 2ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 25 Nesta situação, é selecionado o arco   1,4 para ter seu fluxo incrementado ( 1    ), pois 14 0 z  e 14 14 x  q . Com isto fecha-se o ciclo  s,1,4, ,  t s , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (s,1) +1 0 0 100 100 23 (1,4) +1 0 0 80 80 23 (4,t) +1 67 0 90 23 90 (t,s) +1 67 0 1000 933 90 Máximo Fluxo Incremental do Ciclo 23 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 25 Com isto tem-se uma nova árvore básica, na qual entra   1,4 e sai   4,t , como mostra a figura 05. Nesta figura já se tem a nova rotulação da árvore. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 0   3 2   4 10   5 9   1000 t  25 3 z  13 1 z  45 4 z  5 991 z t   67 67 67 90 34 3 z   23 4 990 z t   Figura 05 – Rede estendida rotulada 3ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 25 Nesta situação, é selecionado o arco   5,t para ter seu fluxo incrementado ( 1    ), pois 5 0 z t  e 5 5 t t x  q . Com isto fecha-se o ciclo  s,2,3,5, ,  t s , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (s,2) +1 67 0 110 43 70 (2,3) +1 67 0 70 3 70 (3,5) +1 0 0 60 60 3 (5,t) +1 0 0 100 100 3 (t,s) +1 90 0 1000 910 93 Máximo Fluxo Incremental do Ciclo 3 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 15 of 25 Com isto tem-se uma nova árvore básica, na qual entra   5,t e sai   2,3 , como mostra a figura 06. Nesta figura já se tem a nova rotulação da árvore. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 0   3 993   4 10   5 1000   1000 t  25 988 z   13 990 z   45 987 z   70 34 988 z  23 4 990 z t   25 991 z   Figura 06 – Rede estendida rotulada 4ª iteração 23 991 z   14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 16 of 25 Nesta situação, é selecionado o arco   2,5 para ter seu fluxo incrementado ( 1    ), pois 25 0 z  e 25 25 x  q . Com isto fecha-se o ciclo  s,2,5, ,  t s , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (s,2) +1 70 0 110 40 110 (2,5) +1 0 0 63 63 40 (5,t) +1 3 0 100 97 43 (t,s) +1 93 0 1000 907 133 Máximo Fluxo Incremental do Ciclo 40 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 17 of 25 Com isto tem-se uma nova árvore básica, na qual entra   2,5 e sai  s,2 , como mostra a figura 07. Nesta figura já se tem a nova rotulação da árvore. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 988   3 993   4 10   5 1000   1000 t  2 988  sz   13 990 z   45 987 z   110 34 988 z  23 4 990 z t   23 3 z   Figura 07 – Rede estendida rotulada 5ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 18 of 25 Nesta situação, é selecionado o arco   1,3 para ter seu fluxo incrementado ( 1    ), pois 13 0 z  e 13 13 x  q . Com isto fecha-se o ciclo  s,1,3,5, ,  t s , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (s,1) +1 23 0 100 77 53 (1,3) +1 0 0 30 30 30 (3,5) +1 3 0 60 57 33 (5,t) +1 43 0 100 57 73 (t,s) +1 133 0 1000 867 163 Máximo Fluxo Incremental do Ciclo 30 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 19 of 25 Com isto tem-se que a árvore básica atual é mantida, pois o arco entrante   1,3 passa de seu limite inferior para o superior sem permanecer na base. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 988   3 993   4 10   5 1000   1000 t  2 988  sz   13 990 z   45 987 z   110 34 988 z  53 4 990 z t   23 3 z   Figura 08 – Rede estendida rotulada 6ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 20 of 25 Nesta situação, é selecionado o arco   4,5 para ter seu fluxo incrementado ( 1    ), pois 45 0 z  e 45 45 x  q . Com isto fecha-se o ciclo  s,1,4,5, ,  t s , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (s,1) +1 53 0 100 47 80 (1,4) +1 23 0 80 57 50 (4,5) +1 0 0 55 55 27 (5,t) +1 73 0 100 27 100 (t,s) +1 163 0 1000 837 190 Máximo Fluxo Incremental do Ciclo 27 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 21 of 25 Com isto tem-se uma nova árvore básica, na qual entra   4,5 e sai   5,t , como mostra a figura 09. Nesta figura já se tem a nova rotulação da árvore. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 1   3 6   4 10   5 13   1000 t  2 1  sz   13 3 z   110 34 1 z  80 4 990 z t   23 3 z   4 987 z t   Figura 09 – Rede estendida rotulada 7ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 22 of 25 Nesta situação, é selecionado o arco   3,4 para ter seu fluxo decrementado ( 1    ), pois 34 0 z  e 34 0 x  . Com isto fecha-se o ciclo   4,3,5,4 , ao longo do qual um fluxo incremental  circula, até que um dos arcos que compõe este ciclo fique saturado ou se anule. Calculando , tem-se: Fluxo Arco do Ciclo Direção Atual Mínimo Máximo Increm Novo ( , ) i j  ijx ij q  ijx (3,4) -1 67 0 67 67 40 (3,5) +1 33 0 60 27 60 (4,5) -1 27 0 55 27 0 Máximo Fluxo Incremental do Ciclo 27 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 23 of 25 Com isto tem-se uma nova árvore básica, na qual entra   3,4 e sai   3,5 , como mostra a figura 10. Nesta figura já se tem a nova rotulação da árvore. 13 13 3 30 c q   35 35 7 60 c q   14 14 10 80 c q   25 25 12 63 c q   45 45 3 55 c q   23 23 2 70 c q   34 34 5 67 c q   1 1 0 100 s s c q   4 4 0 90 t t c q   5 5 0 100 t t c q   1000 1000 ts ts c q    2 2 0 110 s s c q   0 s   1 0   2 1   3 5   4 10   5 13   1000 t  2 1  sz   13 2 z   110 70 40 90 35 1 z   80 4 990 z t   60 100 23 2 z   30 4 987 z t   Figura 10 – Rede estendida rotulada 8ª iteração 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 24 of 25 Nesta situação todos os arcos não básicos encontram-se no limite máximo da capacidade e apresentam 0  ijz  . Desta forma não é possível melhorar a solução do problema. Todos as demanda foram satisfeitas. O nó 1 ainda dispõe de capacidade ociosa. Segue um resumo da solução: ( , ) i j ijc ij q ijx i j   ijz Status (1,3) 3 30 30 0 5 -2 UB (1,4) 10 80 50 0 10 0 BS (2,3) 2 70 70 1 5 -2 UB (2,5) 12 63 40 1 13 0 BS (3,4) 5 67 40 5 10 0 BS (3,5) 7 60 60 5 13 -1 UB (4,5) 3 55 0 10 13 0 BS O custo total desta solução é z 1830 14 Problemas Lineares Especiais – Fluxo em Redes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 25 of 25 F I M (© 2020 Prof. Sérgio Mayerle)