300 Exemplos

Problema de fluxo máximo

Maximum Flow Problem

Formule o modelo | Tentativa e erro | Resolva o modelo





Use o solucionador em Excel para encontrar o fluxo máximo do nó S ao nó T em uma rede direcionada. Os pontos em uma rede são chamados de nós (S, A, B, C, D, E e T). As linhas em uma rede são chamadas de arcos (SA, SB, SC, AC, etc).

Formule o modelo

O modelo que vamos resolver é o seguinte no Excel.





Problema de fluxo máximo no Excel

1. Para formular isso problema de fluxo máximo , responda às três perguntas a seguir.



uma. Quais são as decisões a serem tomadas? Para este problema, precisamos do Excel para encontrar o fluxo em cada arco. Por exemplo, se o fluxo em SB for 2, a célula D5 é igual a 2.

b. Quais são as restrições a essas decisões? O fluxo líquido (fluxo de saída - fluxo de entrada) do nó A, B, C, D e E deve ser igual a 0. Em outras palavras, fluxo de saída = fluxo de entrada. Além disso, cada arco tem uma capacidade fixa. O fluxo em cada arco deve ser inferior a esta capacidade.

c. Qual é a medida geral de desempenho para essas decisões? A medida geral de desempenho é o fluxo máximo, portanto, o objetivo é maximizar essa quantidade. O fluxo máximo é igual ao fluxo de saída do nó S.

2. Para tornar o modelo mais fácil de entender, crie o seguinte intervalos nomeados .

Nome do intervalo Células
A partir de B4: B15
Para C4: C15
Fluxo D4: D15
Capacidade F4: F15
SupplyDemand K5: K9
MaximumFlow D17

3. Insira as seguintes funções.

Inserir funções

Explicação: SUMIF funções calculam o fluxo líquido de cada nó. Para o nó A, a primeira função SUMIF soma os valores na coluna Flow com um 'A' na coluna From (Flow Out). A segunda função SUMIF soma os valores na coluna Fluxo com um 'A' na coluna Para (Fluxo de entrada). O fluxo máximo é igual ao valor na célula I4, que é o fluxo de saída do nó S. Como os nós A, B, C, D e E têm um fluxo líquido de 0, o fluxo de saída do nó S será igual ao fluxo de entrada do nó T.

Tentativa e erro

Com esta formulação, torna-se fácil analisar qualquer solução de teste.

1. Por exemplo, o caminho SADT com um fluxo de 2. O caminho SCT com um fluxo de 4. O caminho SBET com um fluxo de 2. Esses caminhos fornecem um fluxo total de 8.

Solução de teste

como usar o preenchimento automático no excel 2013

Não é necessário usar tentativa e erro. Descreveremos a seguir como o Excel Solver pode ser usado para encontrar rapidamente a solução ideal.

Resolva o modelo

Para encontrar a solução ideal, execute as seguintes etapas.

1. Na guia Dados, no grupo Analisar, clique em Solver.

Click Solver

Nota: não consegue encontrar o botão Solver? Clique aqui para carregar o Suplemento Solver .

Insira os parâmetros do solucionador (continue lendo). O resultado deve ser consistente com a imagem abaixo.

Parâmetros do Solver

Você tem a opção de digitar os nomes dos intervalos ou clicar nas células da planilha.

2. Insira MaximumFlow para o objetivo.

3. Clique em Max.

4. Insira o fluxo para as células variáveis ​​variáveis.

5. Clique em Adicionar para inserir a seguinte restrição.

Restrição de fluxo líquido

6. Clique em Adicionar para inserir a seguinte restrição.

Restrição de capacidade

7. Marque 'Tornar variáveis ​​irrestritas não negativas' e selecione 'Simplex LP'.

8. Finalmente, clique em Solve.

Resultado:

Resultados do Solver

A solução ideal:

Resultado de problema de fluxo máximo

Conclusão: o caminho SADT com um fluxo de 2. O caminho SCT com um fluxo de 4. O caminho SBET com um fluxo de 2. O caminho SCET com um fluxo de 2. O caminho SACET com um fluxo de 1. O caminho SACDT com um fluxo de 1. Esses caminhos fornecem um fluxo máximo de 12.

5/7 concluído! Saiba muito mais sobre o solucionador>
Vá para o próximo capítulo: Analysis ToolPak



^