Problema de Transbordo - Modelo de Otimizacao e Restricoes

S3 S1 S2 A1 A2 D4 D3 D2 D1 Problema de Transbordo Problema de Transbordo S3 S1 S2 A1 A2 D4 D3 D2 D1 1200 1000 800 1100 400 750 750 15 42 6 9 20 15 xS1D3 xS2D1 xS2A1 xS2A2 Problema de Transbordo MODELO FUNÇÃO OBJETIVO MIN 35xS1D1 30xS1D2 40xS1D3 32xS1D4 15xS1A1 12xS1A2 37xS2D1 40xS2D2 42xS2D3 25xS2D4 8xS2A1 9xS2A2 40xS3D1 15xS3D2 20xS3D3 28xS3D4 7xS3A1 6xS3A2 12xA1D1 11xA1D2 15xA1D3 18xA1D4 17xA2D1 15xA2D2 20xA2D3 9xA2D4 S3 S1 S2 A1 A2 D4 D3 D2 D1 1200 1000 800 1100 400 750 750 15 42 6 9 20 15 xS1D3 xS2D1 xS2A1 xS2A2 Problema de Transbordo RESTRIÇÕES DE CAPACIDADES xS1D1 xS1D2 xS1D3 xS1D4 xS1A1 xS1A2 1200 xS2D1 xS2D2 xS2D3 xS2D4 xS2A1 xS2A2 1000 xS3D1 xS3D2 xS3D3 xS3D4 xS3A1 xS3A2 800 S3 S1 S2 A1 A2 D4 D3 D2 D1 1200 1000 800 1100 400 750 750 15 42 6 9 20 15 xS1D3 xS2D1 xS2A1 xS2A2 Problema de Transbordo RESTRIÇÕES DE ATENDIMENTO ÀS DEMANDAS xS1D1 xS2D1 xS3D1 xA1D1 xA2D1 1100 xS1D2 xS2D2 xS3D2 xA1D2 xA2D2 400 xS1D3 xS2D3 xS3D3 xA1D3 xA2D3 750 xS1D4 xS2D4 xS3D4 xA1D4 xA2D4 750 S3 S1 S2 A1 A2 D4 D3 D2 D1 1200 1000 800 1100 400 750 750 15 42 6 9 20 15 xS1D3 xS2D1 xS2A1 xS2A2 Problema de Transbordo RESTRIÇÕES DE ABASTECIMENTO DOS C DE DISTRIBUIÇÃO A1 E A2 xS1A1 xS2A1 xS3A1 xA1D1 xA1D2 xA1D3 xA1D4 xS1A2 xS2A2 xS3A2 xA2D1 xA2D2 xA2D3 xA2D4 S3 S1 S2 A1 A2 D4 D3 D2 D1 1200 1000 800 1100 400 750 750 15 42 6 9 20 15 xS1D3 xS2D1 xS2A1 xS2A2 Problema de Transbordo RESTRIÇÕES DE ABASTECIMENTO DOS C DE DISTRIBUIÇÃO A1 E A2 SUPONDO CAPACIDADE MÁXIMA DO CENTRO A1 700 CAPACIDADE MÁXIMA DO CENTRO A2 500 xS1A1 xS2A1 xS3A1 700 xS1A2 xS2A2 xS3A2 500 S3 S1 S2 A1 A2 D4 D3 D2 D1 1200 1000 800 1100 400 750 750 15 42 6 9 20 15 xS1D3 xS2D1 xS2A1 xS2A2 Problema de Transbordo MIN 35xS1D1 30xS1D2 40xS1D3 32xS1D4 15xS1A1 12xS1A2 37xS2D1 40xS2D2 42xS2D3 25xS2D4 8xS2A1 9xS2A2 40xS3D1 15xS3D2 20xS3D3 28xS3D4 7xS3A1 6xS3A2 12xA1D1 11xA1D2 15xA1D3 18xA1D4 17xA2D1 15xA2D2 20xA2D3 9xA2D4 ST RESTRIÇÕES DE CAPACIDADES xS1D1 xS1D2 xS1D3 xS1D4 xS1A1 xS1A2 1200 xS2D1 xS2D2 xS2D3 xS2D4 xS2A1 xS2A2 1000 xS3D1 xS3D2 xS3D3 xS3D4 xS3A1 xS3A2 800 RESTRIÇÕES DE ATENDIMENTO ÀS DEMANDAS xS1D1 xS2D1 xS3D1 xA1D1 xA2D1 1100 xS1D2 xS2D2 xS3D2 xA1D2 xA2D2 400 xS1D3 xS2D3 xS3D3 xA1D3 xA2D3 750 xS1D4 xS2D4 xS3D4 xA1D4 xA2D4 750 RESTRIÇÕES DE ABASTECIMENTO DOS C DE DISTRIBUIÇÃO A1 E A2 xS1A1 xS2A1 xS3A1 xA1D1 xA1D2 xA1D3 xA1D4 0 xS1A2 xS2A2 xS3A2 xA2D1 xA2D2 xA2D3 xA2D4 0 RESTRIÇÕES DE ABASTECIMENTO DOS C DE DISTRIBUIÇÃO A1 E A2 xS1A1 xS2A1 xS3A1 700 xS1A2 xS2A2 xS3A2 500 END Problema de Transbordo Solução LINDO Otimização do Fluxo em redes Fluxo em Redes ESTA REPRESENTAÇÃO PODE SER USADA PARA PROBLEMAS DE Custo mínimo Percurso mais curto Duração mínima os valores dos arcos representam o custo ou a distância ou a duração entre dois nós 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino Custo Distância ou Tempo do nó 1 até o nó 2 x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Se o caminho de 1 para 3 for escolhido x131 Se não for escolhido x130 3 x13 x32 x35 Nós Intermediários 2 3 4 5 e 6 Em cada nó as entradas devem ser iguais às saídas Ex do nó 3 x13 x32 x35 x12 x13 1 7 x27 x47 x67 Nó Inicial 1 1 x12 x13 Nó Final 7 x27 x47 x67 1 Fluxo em Redes 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Formulação Matemática do Problema Caminho mais curto Min cijxij todos os arcos St xij 1 arco de origem i1 xij Xjk 0 arco intermediário j xtf 1 arco final f Variáveis binárias Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 X13 X32 X35 0 NÓ 3 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 X13 X32 X35 0 NÓ 3 X24 X45 X47 0 NÓ 4 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 X13 X32 X35 0 NÓ 3 X24 X45 X47 0 NÓ 4 X35 X45 X56 0 NÓ 5 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 X13 X32 X35 0 NÓ 3 X24 X45 X47 0 NÓ 4 X35 X45 X56 0 NÓ 5 X56 X67 0 NÓ 6 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 X13 X32 X35 0 NÓ 3 X24 X45 X47 0 NÓ 4 X35 X45 X56 0 NÓ 5 X56 X67 0 NÓ 6 X27 X47 X67 1 NÓ 7 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Fluxo em Redes Custo Mínimo FUNÇÃO OBJETIVO MIN 15X12 10X13 8X32 6X24 17X27 4X35 5X47 4X45 2X56 6X67 SUJEITO A X12 X13 1 NÓ 1 X12 X32 X24 X27 0 NÓ 2 X13 X32 X35 0 NÓ 3 X24 X45 X47 0 NÓ 4 X35 X45 X56 0 NÓ 5 X56 X67 0 NÓ 6 X27 X47 X67 1 NÓ 7 1 2 4 3 6 5 7 15 17 10 8 6 4 5 4 2 6 origem destino x12 x13 x32 x27 x24 x35 x45 x47 x56 x67 Minimizar Caminho Custo Tempo Solução pelo LINDO Maximizar Caminho Custo Tempo Solução pelo LINDO Fluxo em Redes Máximo Fluxo O QUE SE QUER Determinar o máximo fluxo possível entre a origem nó 1 e o destino nó 7 Fluxo Máximo do Nó 4 ao nó 7 capacidade dos Arcos Fluxo Calculado do Nó 5 ao nó 7 1 3 2 6 4 5 7 F F 12 8 2 1 1 X23 X32 X35 X67 X24 Fluxo em Redes Máximo Fluxo Função Objetivo Maximizar Z F Restrições origem nó 1 X12 X13 F destino nó 7 X47 X57 X67 F nós intermediários nó 2 X12 X32 X23 X24 X26 nó 3 X13 X23 X63 X32 X35 X36 nó 4 X24 X64 X47 X46 nó 5 X35 X65 X56 X57 nó 6 X26 X36 X46 X56 X63 X64 X65 X67 1 3 2 6 4 5 7 F F 12 8 2 1 1 X23 X32 X35 X67 X24 Fluxo em Redes Máximo Fluxo Restrições das capacidades dos arcos X12 10 X46 3 X13 10 X47 7 X23 1 X56 2 X24 8 X57 8 X26 6 X63 4 X32 1 X64 3 X35 12 X65 2 X36 4 X67 2 1 3 2 6 4 5 7 F F 12 8 2 1 1 X23 1 X32 1 X35 12 X67 2 X24 8 Fluxo em Redes Máximo Fluxo Função Objetivo Maximizar Z F Restrições origem nó 1 X12 X13 F destino nó 7 X47 X57 X67 F nós intermediários nó 2 X12 X32 X23 X24 X26 nó 3 X13 X23 X63 X32 X35 X36 nó 4 X24 X64 X47 X46 nó 5 X35 X65 X56 X57 nó 6 X26 X36 X46 X56 X63 X64 X65 X67 capacidades dos arcos X12 10 X26 6 X46 3 X63 4 X13 10 X32 1 X47 7 X64 3 X23 1 X35 12 X56 2 X65 2 X24 8 X36 4 X57 8 X67 2 Fluxo em Redes Máximo Fluxo Resolução pelo LINDO 1 3 2 6 4 5 7 F F 12 8 2 1 1 X23 X32 X35 X67 X24 Fluxo em Redes Máximo Fluxo Resolução pelo LINDO