Maksimalni problem protoka u programu Excel
Formulirajte model | Pokušaj i pogreška | Riješite model
Koristite rješavača u sustavu nadmašiti pronaći maksimalni protok od čvora S do čvora T u usmjerenoj mreži. Točke u mreži nazivaju se čvorovi (S, A, B, C, D, E i T). Linije u mreži nazivaju se lukovi (SA, SB, SC, AC, itd.).
Formulirajte model
Model koji ćemo riješiti izgleda kako slijedi u Excelu.
1. formulirati ovo najveći problem protoka, odgovorite na sljedeća tri pitanja.
a. Koje odluke treba donijeti? Za ovaj problem potreban nam je Excel za pronalaženje toka na svakom luku. Na primjer, ako je protok na SB je 2, stanica D5 jednaka je 2.
b. Koje su ograničenja ovih odluka? Net Flow (Flow Out - Flow In) čvora A, B, C, D i E mora biti jednaka 0. Drugim riječima, Flow Out = Flow In. Također, svaki luk ima fiksni kapacitet. Protok na svakom luku trebao bi biti manji od ovog kapaciteta.
c. Koja je ukupna mjera izvedbe zaove odluke? Ukupna mjera izvedbe je maksimalni protok, pa je cilj maksimizirati ovu količinu. Maksimalni protok jednak je protoku iz čvora S.
2. Da biste model lakše razumjeli, navedite sljedeće raspone.
| Naziv raspona | Stanice |
|---|---|
| Iz | B4: B15 |
| Do | C4: C15 |
| Teći | D4: D15 |
| Kapacitet | F4: F15 |
| Zahtjev za nabavu | K5: K9 |
| MaximumFlow | D17 |
3. Umetnite sljedeće funkcije.
Obrazloženje: SUMIF funkcije izračunavaju neto protok svakog čvora. Za čvor A, prva SUMIF funkcija zbraja vrijednosti u stupcu Tijek s "A" u stupcu Od izlaza (Flow Out). Druga funkcija SUMIF zbraja vrijednosti u stupcu Protok s "A" u stupcu U (Flow In). Maksimalni protok jednak je vrijednosti u ćeliji I4, što je protok iz čvora S. Budući da čvorovi A, B, C, D i E imaju neto protok od 0, izlazni protok iz čvora S jednak će ulazu u čvoru T.
Pokušaj i pogreška
Ovom formulacijom postaje lako analizirati sva probna rješenja.
1. Na primjer, put SADT s protokom 2. Put SCT s protokom 4. Staza SBET s protokom 2. Ovi putovi daju ukupni protok od 8.
Nije potrebno koristiti probnu i pogrešku. Sada ćemo opisati kako Excel Solver može se koristiti za brzo pronalaženje optimalnog rješenja.
Riješite model
Da biste pronašli optimalno rješenje, izvršite sljedeće korake.
1. Na kartici Podaci u grupi Analiziraj, kliknite Rješivač.
Napomena: ne možete pronaći gumb Solver? Kliknite ovdje za učitavanje dodatka Solvera.
Unesite parametre solvera (čitaj dalje). Rezultat bi trebao biti u skladu s donjom slikom.
Možete odabrati upisivanje naziva dometa ili klikom na ćelije u proračunskoj tablici.
2. Unesite MaximumFlow za Cilj.
3. Kliknite Max.
4. Unesite tijek promjena varijabilnih ćelija.
5. Kliknite Dodaj da biste unijeli sljedeće ograničenje.
6. Kliknite Dodaj da biste unijeli sljedeće ograničenje.
7. Označite "Unesi nepotrebne varijable ne-negativne" i odaberite "Simplex LP".
8. Konačno, kliknite Rješi.
Proizlaziti:
Optimalno rješenje:
Zaključak: put SADT s protokom od 2. Put SCT s protokom 4. Staza SBET s protokom 2. Put SCET s protokom 2. Put SACET s protokom 1. Put SACDT s protokom 1. Ovi putevi daju maksimum protok od 12.
