Pesquisa Operacional 2

Prévia do material em texto

Pesquisa Operacional
Modelos de Otimização em Redes
Hillier Cap. 9 – Taha cap. 6.
Modelos de Otimização de Redes
As redes surgiram em diversos ambientes e de muitas formas distintas. 
Redes de transportes, elétricas e de comunicações são uma constante em nosso dia a dia.
As apresentações em formato de rede são amplamente usadas para problemas em diversas áreas, como produção, distribuição, planejamento de projetos, posicionamento de instalações, administração de recursos e planejamento financeiro.
Muitos modelos de otimização em redes, são na verdade problemas de programação linear, como os problemas de transporte e designação.
Grafos e Redes
Está contida na área da pesquisa operacional. Pode ser considerada como uma teoria baseada na interligação de pontos e linhas, utilizada principalmente na solução de problemas de roteamento.
Um grafo é definido como sendo um par ordenado (V, A).
Os elementos de V são denominados de vértices ou nós do grafo e os pares ordenados de A, denominados de arestas ou arcos do grafo
Exemplo protótipo
O Seervada Park foi reservado recentemente para visitação e excursões limitadas (mochileiros). Não se permite o ingresso de carros no parque porém há um sistema de estradinhas estreitas e tortuosas por onde podem trafegar pequenos carros elétricos e jipes dirigidos pelos guardas florestais. Esse sistema de estradas é mostrado (sem as curvas) na figura a baixo.
 
4
Exemplo protótipo
Grafos e Redes
Alguns aspectos importantes devem ser considerados em relação aos grafos:
Quando um arco é incidente a um único vértice é denominado de laço
Dois vértices são considerados “adjacentes” se eles estão interligados por um arco
Uma cadeia é uma sequência de arcos (orientados ou não). O tamanho da cadeia está relacionada ao número de arcos que a compõe.
Grafos e Redes
Um caminho é uma cadeia em que todos os arcos tem a mesma direção (não confundir com sentido).
Um ciclo é uma cadeia cujo vértice inicial e final é o mesmo (cadeia fechada).
Quanto as características de seus arcos, um grafo pode ser:
Direcionado ou não direcionado: Se o fluxo através do arco for permitido apenas em uma direção o arco é dito direcionado. A direção é indicada adicionando-se uma seta na extremidade da reta representando um arco. Se o fluxo através do arco for permitido em ambas as direções, o arco é chamado de não direcionado, neste caso os arcos podem ser chamados pelo nome de ligações.
Componentes de uma rede típica
Arcos e Grafos
Caminhos direcionado nó i para o nó j é uma sequência de arcos conectados cuja direção (se houver alguma) será no sentido do nó j. de modo que o fluxo do nó i para o nó j ao longo desse caminho seja viável. 
Um caminho não direcionado do nó i para o nó j é uma sequência de arcos conectados cuja direção (se existir alguma) pode ser tanto no sentido, como afastando-se do nó j. (Observe que um caminho direcionado também satisfaz a definição de um caminho não direcionado todavia, o inverso não é verdadeiro.) 
Frequentemente um caminho não direcionado terá alguns arcos direcionados no sentido do nó j porém outros direcionados no sentido de se afastar (isto é no sentido do nó i).
Exemplo
Rede, Árvore e Árvore de Expansão
Considere uma rede conectada com n. nós (por exemplo, os n = 5 nós na Figura 9.2). em que todos os arcos foram eliminados. Uma “árvore" pode ser "expandida” adicionando-se um arco (ou “ramificação”) por vez a partir da rede original de algum modo. O primeiro arco pode ir para qualquer lugar para conectar algum par de nós. A partir daí. cada arco novo deve estar entre um nó. que já esteja conectado a outros nós. e um novo nó não previamente conectado a qualquer outro nó.
Crescimento de uma árvore
Problemas de Otimização de Rede
1. Projeto de uma rede de tubulações marítimas para ligar as bocas de poço de uma plataforma offshore de gás natural no golfo do México a um ponto de entrega em terra. O objetivo e minimizar o custo de construção da rede de tubulações. 
Árvore Geradora Mínima
2. Determinação do caminho mais curto entre duas cidades em uma rede de rodovias existentes
Algoritmo do Caminho mais Curto
3. Determinação da capacidade máxima (em toneladas por ano) de uma tubulação de lama de carvão que liga as minas de carvão no Wyoming com as usinas geradoras de energia elétrica em Houston. (Esse tipo de tubulação transporta lama de carvão por meio do bombeamento de água por tubulações especialmente projetadas)
Algoritmo do Fluxo Máximo
4. Determinação de um cronograma (datas de início e de conclusão) para as atividades de um projeto de construção civil.
Algoritmo de Caminho Crítico
Exercícios
1. Para cada rede da abaixo determine: (a) um caminho: (b) um ciclo: (e) uma árvore: e (d) uma árvore geradora.
2. Determine os conjuntos N e A para as redes da Figura 6.5.
3. Desenhe a rede definida por
N : [1.2.3.4.5.6]
A = [(1,2), (1,5), (2, 3), (2,4), (3,4), (3, 5), (4, 3), (4, 6). (5,2). (5,6)]
Árvore Geradora Mínima
O algoritmo da árvore geradora mínima trata de conectar os nós de uma rede. direta ou indiretamente. usando o comprimento total mais curto de ramos conectores. Uma aplicação típica ocorre na construção de estradas pavimentadas que ligam várias cidades rurais. A estrada entre duas cidades deve passar por uma ou mais outras cidades. O projeto mais econômico do sistema rodoviário recomenda minimizar o comprimento total da estrada pavimentada, um resultado que é obtido por meio da implementação do algoritmo da árvore geradora mínima.
As etapas do procedimento são dadas a seguir. Seja N = [1, 2,...,n]
o conjunto de nós da rede é definida
Ck = conjunto de nós que foram conectados permanentemente na iteração k
Ck =conjunto de nós que ainda terão de ser conectados permanentemente após a iteração k
Definição de Etapas
Exemplo
A Midwest TV Cable Company está em vias de fornecer serviços por cabo a cinco novas áreas onde estão em desenvolvimento projetos residenciais. A Figura 6.6 mostra as possíveis conexões de TV entre as cinco áreas. As extensões (em milhas) dos cabos são mostradas em cada arco. Determine a rede mais econômica.
Resolução
Exercício
1. Resolva o Exemplo 6.2-1 começando no nó 5 (em vez de no nó 1) e mostre que o algoritmo produz a mesma solução.
2. Determine a árvore geradora mínima da rede do Exemplo 6.2-1 sob cada uma das seguintes condições específicas:
(a) Os nós 5 c 6 são conectados por um cabo de 2 milhas.
(b) Os nós 2 e 5 não podem ser conectados.
(c) Os nós 2 e 6 são conectados por um cabo de 4 milhas.
(d) O cabo entre os nós 1 e 2 tem 8 milhas de comprimento.
(e) Os nós 3 e 5 são conectados por um cabo de 4 milhas.
(f) O nó 2 não pode ser conectado diretamente aos nós 3 e 5.
Exercício
Em transporte intermodal. caminhões-reboque carregados são despachados entre terminais ferroviários sobre vagões-plataformas especiais.
 A Figura 6.8 mostra a localização dos principais terminais ferroviários nos Estados Unidos e as ferrovias existentes. O objetivo é decidir quais ferrovias devem ser “revitalizadas' para enfrentar o tráfego intermodal. Em particular o terminal de Los Angeles (LA) deve ser conectado diretamente ao de Chicago (CH) para dar conta do esperado tráfego pesado. Fora estes todos os terminais restantes podem ser conectados direta ou indiretamente de modo que o comprimento total (em milhas) das ferrovias selecionadas seja minimizado. Determine os trechos das ferrovias que devem ser incluídos no programa de revitalização.
O problema de caminho mínimo
O problema do caminho mínimo determina o caminho mais curto entre um destino e uma origem em uma rede de transporte. Outras situações podem ser representadas pelo mesmo problema.
Exemplo 1 – Reposição de equipamentos
A RentCar está desenvolvendo uma política de reposição para sua frota de carros considerando uma projeção de planejamento de quatro anos. No início de cada ano é tomada uma decisão sobre a conservação em operação ou reposição de um carro.
Umcarro deve permanecer em serviço no mínimo por um ano e no máximo três anos. A seguir temos a tabela com o custo da reposição como uma função do ano em que o carro foi adquirido e do número de anos em operação.
O problema pode ser formulado como uma rede na qual os nós 1 a 5 representam o início dos anos 1 a 5. Os arcos provenientes do nó 1 (ano 1) podem chegar somente aos nós 2, 3 e 4 porque um carro deve estar em operação entre 1 e 3 anos. Os arcos que vêm de outros nós podem ser interpretados de maneira semelhante. O comprimento de cada arco é igual ao custo de reposição. A solução equivale a achar o caminho mais curto entre os nós 1 e 5.
Exemplo 2 – Rota mais confiável
Espertinho vai trabalhar de carro todos os dias. Como acabou de concluir um curso de análise de reder espertinho sabe determinar o caminho mais curto até seu local de trabalho. Infelizmente, a rota escolhida é muito bem policiada e, com todas as multas por excesso de velocidade que ele recebe, o caminho mais curto pode não ser a melhor opção. Por isso, Espertinho decidiu escolher uma rota que maximize a probabilidade de ele não ser multado por um policial.
A rede a seguir mostra as possíveis rotas entre sua casa e seu trabalho, e as probabilidades de ele não ser parado associadas a cada trecho. A probabilidade dele não ser parado em um rota é o produto das probabilidades associadas aos segmentos.
Exemplo 3 – Charada dos 3 jarros
Um jarro de 8 galões é enchido com fluido. Dados dois jarros vazios de 5 e 3 galões, queremos dividir os 8 galões de fluido em duas partes iguais usando os três jarros. Não é permitido nenhum outro instrumento de medida. Qual é o menor número de transferências (despejamentos) necessários para obter esse resultado?
É provável que você possa adivinhar a solução dessa charada.
De qualquer maneira. o processo de solução pode ser sistematizado com a representação da questão como um problema de caminho mínimo.
Deline-se um nó para representar a quantidade de fluido nos jarros de 8,5 e 3 galões. respectivamente. o que significa que a rede inicia com o nó (8, 0, 0) e termina com o nó de solução desejado (4, 4, 0). Um novo nó é gerado com base no nó atual ao se despejar fluido de um jarro para o outro.
A Figura 6.13 mostra diferentes rotas que levam do nó inicial (8,0, 0) ao nó final (4, 4, 0). O arco entre dois nós sucessivos representa uma única transferência e portanto podemos considerar que tem um comprimento de uma unidade. Assim o problema se reduz a determinar o caminho mais curto entre o nó (8, 0, 0) e o nó (4, 4, 0).
Exercício
1. Reconstrua o problema de reposição de equipamento do Exemplo da RentCar considerando que um carro deve ser mantido em serviço no mínimo por dois anos, com uma vida útil máxima em serviço de quatro anos o horizonte de planejamento é do início do ano 1 ao final do ano 5. A Tabela B apresenta os dados necessários.
2. A Figura abaixo apresenta a rede de comunicação entre duas estações 1 e 7. A probabilidade de uma conexão operar sem falhas é mostrada em cada arco. Mensagens são enviadas da Estação 1 à Estação 7. e o objetivo é determinar a rota que maximizará a probabilidade de uma transmissão bem-sucedida. Formule a situação como um problema de caminho mínimo e determine a solução ótima.
3. Planejamento de produção. A DirectCo vende um item cujas demandas nos próximos quatro meses são 100, 140, 210 e 180 unidades. respectivamente. A empresa pode estocar apenas o suficiente para atender à demanda de cada mês ou então pode manter excesso de estoque para satisfazer a demanda de dois ou mais meses subsequentes e consecutivos. No último caso é cobrado um custo de permanência de $ 1,20 por unidade de excesso de estoque por mês. A DirectCo estima que os preços de compra por unidade para os próximos quatro meses serão $15, $12, $10 e $14. respectivamente. Um custo de preparação de $ 200 é incorrido toda vez que um pedido de compra é colocado. A empresa quer desenvolver um plano de compra que minimizará os custos totais de colocação de pedido, compra e permanência do item em estoque. Formule a questão como um problema de caminho mínimo.
Algoritmos para resolução de problema do caminho mínimo
Dois algoritmos para resolução de redes cíclicas ou acíclicas.
1. O algoritmo de Dijkstra.
2. O algoritmo de Floyd.
O algoritmo de Dijkstra foi desenvolvido para determinar o caminho mais curto entre o nó de origem e qualquer outro nó da rede.
O algoritmo de Floyd é mais abrangente porque permite a determinação do caminho mais curto entre quaisquer dois nós da rede.
Algoritmo de Dijkstra
Exemplo
A rede da Figura abaixo dá as rotas possíveis e seus comprimentos em milhas entre a Cidade 1 (nó 1) e quatro outras cidades (nós 2 a 5). Determine os caminhos mais curtos entre a Cidade 1 e cada uma das outras quatro cidades.
Resolução
Iteração 0. Designe o rótulo permanente [0, -] no nó1. 
Iteração 1. Os nós 2 e 3 podem ser alcançados com base no nó 1 (último nó rotulado permanentemente). Assim. a lista de nós rotulados (temporários e permanentes) fica como demonstrado na Tabela 6.2.
Para os dois rótulos temporários [100, 1] e [30, 1]. o nó 3 resulta na menor distância (u3 = 30). Assim, o status do nó 3 muda para permanente.
Iteração 2. Os nós 4 e 5 podem ser alcançados com base no nó 3, e a lista de nós fica como demonstrado na Tabela 6.3.
O status do rótulo temporário [40, 3] no nó 4 muda para permanente (u4 = 40).
Iteração 3. Nós 2 e 5 podem ser alcançados com base no nó 4. Assim, a lista de nós rotulados é atualizada como demonstrado na Tabela 6.4.
O rótulo temporário do nó 2 [100, 1] obtido na iteração 1 muda para [55, 4] na iteração 3 a fim de indicar que foi encontrada uma rota mais curta que passa pelo nó 4. Além disso, na iteração 3, o nó 5 tem dois rótulos alternativos com a mesma distância u8 = 90.
A lista para a iteração 3 mostra que o rótulo para o nó 2 agora permanente.
Iteração 4. Só o nó 3 pode ser alcançado com base no nó 2. Contudo, o nó 3 tem um rótulo permanente e não pode ser rotulado novamente. A nova lista de rótulos permanece a mesma da iteração 3, exceto que o rótulo no nó 2 agora é permanente. Isso deixa o nó 5 como o único rótulo temporário. Como o nó 5 não leva a outros nós seu status é convertido em permanente. e o processo termina.
Os cálculos do algoritmo podem ser executados com mais facilidade na rede.
Resultado
O caminho mais curto entre o nó 1 e qualquer outro nó da rede é determinado começando no nó de destino desejado e percorrendo a rota inversa a partir desse ponto, usando a informação dada pelos rótulos permanentes. Por exemplo, a seguinte sequência determina a rota mais curta do nó 1 ao nó 2:
(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1)
Assim. a rota desejada é 1 -> 3 -> 4 -> 2 com um comprimento total de 55 milhas.
Exercício
A rede da Figura 6.17 dá as distâncias em milhas entre pares de cidades 1, 2,..., e 8. Use o algoritmo de Dijkstra para achar o caminho mais curto entre as seguintes cidades:
(a) Cidades 1 e 8.
(b) Cidades 1 e 6
(c) Cidades 4 e 8
2. Use o algoritmo de Dijkstra para achar o caminho mais curto entre o nó 1 e todos os outros nós da rede da Figura 6.18.
Algoritmo de Floyd
O algoritmo de Floyd é mais geral que do que o de Dijkstra porque determina o caminho mínimo entre quaisquer dois nós da rede.
O algoritmo representa uma rede de n nós como uma matriz quadrada com n linhas e n colunas. A entrada (i,j) da matriz dá a distância dij do nó i ao nó j, que é finita se i estiver ligado diretamente a j, caso contrário é infinita.
Exemplo
Para a rede da Figura abaixo encontre os caminhos mais curtos entre todos os conjuntos de dois nós As distâncias (em milhas) são dadas nos arcos. O arco (3, 5) é direcional, de modo que nenhum tráfego é permitido do nó 5 ao nó 3.Todos os outros arcos permitem tráfego nos dois sentidos.
Iteração 0. As matrizes D0 e S0 dão a representação inicial darede. D0 é simétrica. exceto por d53 = ∞. porque nenhum tráfego é permitido do nó 5 ao nó 3.
Iteração l. Determine k = 1. A linha pivô e a coluna pivô são mostradas pela primeira linha e pela primeira coluna sombreadas em tom mais claro na matriz D0. As células sombreadas em tom mais escuro, d23 e d32, são as únicas que podem ser melhoradas pela operação tripla. Assim. D1 e S1 são obtidas de D0 e S0 da seguinte maneira:
1. Substitua d23 por d21 + d13 = 3 + 10 = 13 e determine s23, = 1.
2. Substitua d32 por d31 + d12: = 10 + 3 = 13 e determine s22 = 1.
 
Iteração 2. Determine k = 2, como mostram a linha e a coluna sombreadas em tom mais claro em D1, A operação tripla é aplicada às células sombreadas em tom mais escuro em D1 e S1. As mudanças resultantes são representadas em negrito em D2 e S2.
 
Iteração 3. Determine k = 3, como mostram a linha e a coluna sombreadas em D2. As novas matrizes são dadas por D3 e S1.
Iteração 4. Determine k = 4,eomo mostram a linha e a coluna sombreadas em D3. As novas matrizes são dadas por D4 e S4.
Iteração 5. Determine k = 5, como mostram a linha e a coluna sombreadas em D4. Nenhuma melhoria adicional é possível nessa iteração. 
As matrizes finais D4 e S4 contêm todas as informações necessárias para determinar a rota mais curta entre quaisquer dois nós da rede. Por exemplo. partindo de D4. a distância mais curta do nó 1 ao nó 5 é d15 = 12 milhas.
O problema do fluxo máximo
Considere uma rede de tubulações que transporte petróleo cru de poços de petróleo a refinarias Estações intermediárias de impulsores auxiliares e de bombeamento são instalados a distâncias adequadas para transportar o petróleo em pela rede. Cada segmento de tubulação tem uma taxa de descarga máxima finita (ou capacidade) de fluxo de petróleo cru. Um segmento de tubulação pode ser unidirecional ou bidirecional, dependendo de seu projeto. A Figura 6.27 mostra uma rede de tubulações típica. Como podemos determinar a capacidade máxima da rede entre os poços e as refinarias?
A solução do problema proposto requer equipar a rede com uma única origem e um único sorvedouro usando arcos unidirecionais de capacidade infinita representados pelos arcos tracejados da Figura 6.27.
Fluxo Máximo
Dado o arco (i, j) com i < j,. usamos a notação ( Cij, Cji) para representar as capacidades de fluxo nas duas direções, i → j e j → i, respectivamente. Para eliminar ambiguidades, colocamos Cij no arco próximo ao nó i e Cji no arco próximo ao nó j, como mostra a Figura 6.28.
Exemplo
Considere a rede da Figura 6.29. As capacidades bidirecionais são mostradas nos respectivos arcos usando a convenção da Figura 6.28. Por exemplo. para o arco (3, 4), o limite de fluxo é dez unidades de 3 para quatro e cinco unidades de 4 para 3.
A Figura 6.29 ilustra três cortes cujas capacidades estão calculadas na Tabela 6.6.
Resolução
A única informação que podemos captar dos três cortes é que o fluxo máximo na rede não pode ultrapassar 60 unidades Para determinar o fluxo máximo. é necessário enumerar todos os cortes uma tarefa difícil para a rede geral. Por isso. a necessidade de um algoritmo eficiente é imperativa.
Algoritmo de fluxo máximo
O algoritmo de fluxo máximo é baseado em achar rotas de passagem com fluxo líquido positiva entre os nós de origem e sorvedouro. Cada rota compromete parte ou toda a capacidade de seus arcos ao fluxo na rede.
Considere o arco (i. j) inicialmente com capacidade (Cij, Cji). Á medida que porções dessas capacidades são comprometidas ao fluxo no arco, as capacidades residuais (ou capacidades restantes) do arco são atualizadas. Usamos a notação (cij. cji) para representar essas capacidades residuais.
Para um nó j que recebe fluxo do nó i, anexamos um rótulo
[aj, i]. no qual aj é o fluxo do nó i ao nó j. Assim. as etapas do algoritmo são resumidas no exemplo a seguir.
Exemplo
Determine o fluxo máximo na rede do exemplo da figura 6.29. 
Resolução
Resolução
Exercício
Determine o fluxo máximo para cada arco da rede abaixo.