Formule o modelo | Tentativa e erro | Resolva o modelo
Use o solucionador em Excel para encontrar o caminho mais curto do nó S ao nó T em uma rede não 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 do caminho mais curto, responda às três perguntas a seguir.
uma. Quais são as decisões a serem tomadas? Para este problema, precisamos do Excel para descobrir se um arco está no caminho mais curto ou não (Sim = 1, Não = 0). Por exemplo, se SB fizer parte do caminho mais curto, a célula F5 será igual a 1. Caso contrário, a célula F5 será igual a 0.
b. Quais são as restrições a essas decisões? O fluxo líquido (fluxo de saída - fluxo de entrada) de cada nó deve ser igual a oferta / demanda. O nó S deve ter apenas um arco de saída (fluxo líquido = 1). O nó T deve ter apenas um arco de entrada (Fluxo líquido = -1). Todos os outros nós devem ter um arco de saída e um arco de entrada se o nó estiver no caminho mais curto (Fluxo líquido = 0) ou nenhum fluxo (Fluxo líquido = 0).
c. Qual é a medida geral de desempenho para essas decisões? A medida geral de desempenho é a distância total do caminho mais curto, portanto, o objetivo é minimizar essa quantidade.
2. Para tornar o modelo mais fácil de entender, crie os seguintes intervalos nomeados.
| Nome do intervalo | Células |
|---|---|
| A partir de | B4: B21 |
| Para | C4: C21 |
| Distância | D4: D21 |
| Ir | F4: F21 |
| NetFlow | I4: I10 |
| SupplyDemand | K4: K10 |
| Distância total | F23 |
3. Insira as seguintes funções.
Explicação: As funções SUMIF calculam o fluxo líquido de cada nó. Para o nó S, a função SUMIF soma os valores na coluna Go com um "S" na coluna From. Como resultado, apenas a célula F4, F5 ou F6 pode ser 1 (um arco de saída). Para o nó T, a função SUMIF soma os valores na coluna Go com um "T" na coluna To. Como resultado, apenas a célula F15, F18 ou F21 pode ser 1 (um arco de entrada). Para todos os outros nós, o Excel procura na coluna De e Para. Distância total é igual à soma do produto Distância e Avanço.
Tentativa e erro
Com esta formulação, torna-se fácil analisar qualquer solução de teste.
1. Por exemplo, o caminho SBET tem uma distância total de 16.
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 TotalDistance para o objetivo.
3. Clique em Min.
4. Insira Go para as células variáveis variáveis.
5. Clique em Adicionar para inserir a seguinte restrição.
6. Marque 'Tornar variáveis irrestritas não negativas' e selecione 'Simplex LP'.
7. Finalmente, clique em Solve.
Resultado:
A solução ideal:
Conclusão: SADCT é o caminho mais curto com uma distância total de 11.
