Formulare il modello | Prove ed errori | Risolvi il modello
Usa il risolutore in Eccellere per trovare il flusso massimo dal nodo S al nodo T in una rete diretta. 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 di flusso massimo, rispondi alle seguenti tre domande.
un. Quali sono le decisioni da prendere? Per questo problema, abbiamo bisogno di Excel per trovare il flusso su ciascun arco. Ad esempio, se il flusso su SB è 2, la cella D5 è uguale a 2.
B. Quali sono i vincoli a queste decisioni? Il Net Flow (Flow Out - Flow In) del nodo A, B, C, D ed E dovrebbe essere uguale a 0. In altre parole, Flow Out = Flow In. Inoltre, ogni arco ha una capacità fissa. Il flusso su ciascun arco dovrebbe essere inferiore a questa capacità.
C. Qual è la misura complessiva delle prestazioni per queste decisioni? La misura complessiva delle prestazioni è il flusso massimo, quindi l'obiettivo è massimizzare questa quantità. Il flusso massimo è uguale al flusso in uscita del nodo S.
2. Per rendere il modello più comprensibile, creare i seguenti intervalli denominati.
| Nome intervallo | cellule |
|---|---|
| A partire dal | B4: B15 |
| a | C4: C15 |
| Flusso | G4: G15 |
| Capacità | F4: F15 |
| Domanda e offerta | K5: K9 |
| Flusso massimo | D17 |
3. Inserire le seguenti funzioni.
Spiegazione: Le funzioni SOMMA.SE calcolano il flusso netto di ciascun nodo. Per il nodo A, la prima funzione SOMMA.SE somma i valori nella colonna Flusso con una "A" nella colonna Da (Flow Out). La seconda funzione SOMMA.SE somma i valori nella colonna Flusso con una "A" nella colonna A (Flow In). Il flusso massimo è uguale al valore nella cella I4, che è il flusso in uscita dal nodo S. Poiché i nodi A, B, C, D ed E hanno un flusso netto pari a 0, il flusso in uscita dal nodo S sarà uguale al flusso in ingresso del nodo T.
Prova ed errore
Con questa formulazione, diventa facile analizzare qualsiasi soluzione di prova.
1. Ad esempio, il percorso SADT con un flusso di 2. Il percorso SCT con un flusso di 4. Il percorso SBET con un flusso di 2. Questi percorsi danno un flusso totale di 8.
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 Flusso massimo per l'obiettivo.
3. Fare clic su Massimo.
4. Immettere il flusso per le celle variabili modificate.
5. Fare clic su Aggiungi per immettere il seguente vincolo.
6. Fare clic su Aggiungi per immettere il seguente vincolo.
7. Selezionare 'Rendi variabili non vincolate non negative' e selezionare 'Simplex LP'.
8. Infine, fai clic su Risolvi.
Risultato:
La soluzione ottimale:
Conclusione: il percorso SADT con flusso 2. Il percorso SCT con flusso 4. Il percorso SBET con flusso 2. Il percorso SCET con flusso 2. Il percorso SACET con flusso 1. Il percorso SACDT con un flusso di 1. Questi percorsi danno un flusso massimo di 12.
