Formulirajte model | Pokušaj i pogreška | Riješite model
Upotrijebite rješavač u Excel pronaći maksimalni protok od čvora S do čvora T u usmjerenoj mreži. Točke u mreži zovu 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 ovako u Excelu.
1. Da to formuliramo problem maksimalnog protoka, odgovorite na sljedeća tri pitanja.
a. Koje se odluke trebaju donijeti? Za ovaj problem potreban nam je Excel da pronađe tok na svakom luku. Na primjer, ako je protok na SB 2, ćelija D5 jednaka je 2.
b. Koja su ograničenja za ove odluke? Neto protok (Flow Out - Flow In) čvora A, B, C, D i E trebao bi biti jednak 0. Drugim riječima, Flow Out = Flow In. Također, svaki luk ima fiksni kapacitet. Protok na svakom luku trebao bi biti manji od tog kapaciteta.
c. Koja je ukupna mjera uspješnosti ovih odluka? Sveukupna mjera izvedbe je maksimalni protok, pa je cilj maksimizirati ovu količinu. Maksimalni protok jednak je istjecanju iz čvora S.
2. Da biste model lakše razumjeli, stvorite sljedeće imenovane raspone.
| Naziv raspona | Stanice |
|---|---|
| Iz | B4: B15 |
| Do | C4: C15 |
| Teći | D4: D15 |
| Kapacitet | F4: F15 |
| Zahtjev za nabavu | K5: K9 |
| Maksimalni protok | D17 |
3. Umetnite sljedeće funkcije.
Objašnjenje: SUMIF funkcije izračunavaju neto protok svakog čvora. Za čvor A, prva funkcija SUMIF zbraja vrijednosti u stupcu Protok s "A" u stupcu Od (Istjecanje). Druga funkcija SUMIF zbraja vrijednosti u stupcu Protok s "A" u stupcu Do (Ulaz). Maksimalni protok jednak je vrijednosti u ćeliji I4, što je protok iz čvora S. Budući da čvor A, B, C, D i E imaju neto protok 0, protok iz čvora S bit će jednak protoku In čvora T.
Pokušaj i pogreška
S ovom formulacijom postaje lako analizirati bilo koje pokusno rješenje.
1. Na primjer, put SADT s protokom od 2. Put SCT s protokom od 4. Put SBET s protokom od 2. Ove staze daju ukupni protok od 8.
Nije potrebno koristiti pokušaj i pogrešku. Dalje ćemo opisati kako je Riješivač programa Excel može se koristiti za brzo pronalaženje optimalnog rješenja.
Riješite model
Da biste pronašli optimalno rješenje, izvedite sljedeće korake.
1. Na kartici Podaci, u grupi Analiza kliknite Solver.
Napomena: ne možete pronaći gumb Solver? Kliknite ovdje za učitavanje programskog dodatka Solver.
Unesite parametre rješavača (čitajte dalje). Rezultat bi trebao biti u skladu sa donjom slikom.
Imate izbor upisivanja naziva raspona ili klikanja ćelija u proračunskoj tablici.
2. Unesite MaximumFlow za cilj.
3. Pritisnite Max.
4. Unesite protok za mijenjanje promjenjivih ćelija.
5. Pritisnite Dodaj za unos sljedećeg ograničenja.
6. Pritisnite Dodaj za unos sljedećeg ograničenja.
7. Označite "Učini neograničene varijable negativnim" i odaberite "Simplex LP".
8. Na kraju kliknite Riješi.
Proizlaziti:
Optimalno rješenje:
Zaključak: put SADT s protokom od 2. Put SCT s protokom od 4. Put SBET s protokom od 2. Put SCET s protokom od 2. Put SACET s protokom od 1. Put SACDT s protokom od 1. Ovi putovi daju maksimalni protok od 12.
