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.
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 os seguintes 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.
Explicação: As funções SUMIF 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.
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.
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.
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.
6. Clique em Adicionar para inserir a seguinte restrição.
7. Marque 'Tornar variáveis irrestritas não negativas' e selecione 'Simplex LP'.
8. Finalmente, clique em Solve.
Resultado:
A solução ideal:
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.
