Formulare il modello | Prove ed errori | Risolvi il modello
Usa il risolutore in Eccellere per trovare il percorso più breve dal nodo S al nodo T in una rete non orientata. I punti in una rete sono chiamati nodi (S, A, B, C, D, E e T). Le linee in una rete sono chiamate archi (SA, SB, SC, AC, ecc.).
Formulare il modello
Il modello che andremo a risolvere appare come segue in Excel.
1. Per formulare questo problema del percorso più breve, rispondi alle seguenti tre domande.
un. Quali sono le decisioni da prendere? Per questo problema, abbiamo bisogno di Excel per scoprire se un arco si trova sul percorso più breve o meno (Sì=1, No=0). Ad esempio, se SB fa parte del percorso più breve, la cella F5 è uguale a 1. In caso contrario, la cella F5 è uguale a 0.
B. Quali sono i vincoli a queste decisioni? Il Net Flow (Flow Out - Flow In) di ogni nodo dovrebbe essere uguale a Offerta/Domanda. Il nodo S dovrebbe avere un solo arco in uscita (Net Flow = 1). Il nodo T dovrebbe avere un solo arco in entrata (Net Flow = -1). Tutti gli altri nodi dovrebbero avere un arco in uscita e un arco in entrata se il nodo si trova sul percorso più breve (Net Flow = 0) o nessun flusso (Net Flow = 0).
C. Qual è la misura complessiva delle prestazioni per queste decisioni? La misura complessiva delle prestazioni è la distanza totale del percorso più breve, quindi l'obiettivo è ridurre al minimo questa quantità.
2. Per rendere il modello più comprensibile, creare i seguenti intervalli denominati.
| Nome intervallo | cellule |
|---|---|
| A partire dal | B4: B21 |
| a | C4: C21 |
| Distanza | G4: G21 |
| andare | F4: F21 |
| Flusso netto | I4:I10 |
| Domanda e offerta | K4: K10 |
| Distanza totale | F23 |
3. Inserire le seguenti funzioni.
Spiegazione: Le funzioni SOMMA.SE calcolano il flusso netto di ciascun nodo. Per il nodo S, la funzione SOMMA.SE somma i valori nella colonna Vai con una "S" nella colonna Da. Di conseguenza, solo la cella F4, F5 o F6 può essere 1 (un arco in uscita). Per il nodo T, la funzione SOMMA.SE somma i valori nella colonna Vai con una "T" nella colonna A. Di conseguenza, solo la cella F15, F18 o F21 può essere 1 (un arco in entrata). Per tutti gli altri nodi, Excel cerca nella colonna Da e A. Distanza totale è uguale al prodotto della somma di Distanza e Andata.
Prova ed errore
Con questa formulazione, diventa facile analizzare qualsiasi soluzione di prova.
1. Ad esempio, il percorso SBET ha una distanza totale di 16.
Non è necessario utilizzare tentativi ed errori. Descriveremo in seguito come il Risolutore Excel può essere utilizzato per trovare rapidamente la soluzione ottimale.
Risolvi il modello
Per trovare la soluzione ottimale, eseguire i seguenti passaggi.
1. Nella scheda Dati, nel gruppo Analizza, fare clic su Risolutore.
Nota: non riesci a trovare il pulsante Risolutore? Fare clic qui per caricare il componente aggiuntivo Risolutore.
Immettere i parametri del risolutore (continua a leggere). Il risultato dovrebbe essere coerente con l'immagine qui sotto.
Puoi scegliere di digitare i nomi degli intervalli o fare clic sulle celle nel foglio di calcolo.
2. Immettere TotalDistance per l'obiettivo.
3. Fare clic su Min.
4. Immettere Vai per Modificare le celle delle variabili.
5. Fare clic su Aggiungi per immettere il seguente vincolo.
6. Selezionare 'Rendi variabili non vincolate non negative' e selezionare 'Simplex LP'.
7. Infine, fai clic su Risolvi.
Risultato:
La soluzione ottimale:
Conclusione: SADCT è il percorso più breve con una distanza totale di 11.
