Formulirajte model | Pokušaj i pogreška | Riješite model
Upotrijebite rješavač u Excel pronaći najkraći put od čvora S do čvora T u neusmjerenoj 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 najkraćeg puta, odgovorite na sljedeća tri pitanja.
a. Koje se odluke trebaju donijeti? Za ovaj problem potreban nam je Excel da bismo saznali je li luk na najkraćoj putanji (Da = 1, Ne = 0). Na primjer, ako je SB dio najkraćeg puta, ćelija F5 je jednaka 1. Ako nije, ćelija F5 je jednaka 0.
b. Koja su ograničenja za ove odluke? Neto protok (Flow Out - Flow In) svakog čvora trebao bi biti jednak ponudi/potražnji. Čvor S trebao bi imati samo jedan odlazni luk (neto protok = 1). Čvor T trebao bi imati samo jedan ulazni luk (neto protok = -1). Svi ostali čvorovi trebali bi imati jedan odlazni luk i jedan ulazni luk ako je čvor na najkraćoj stazi (neto protok = 0) ili bez protoka (neto protok = 0).
c. Koja je ukupna mjera uspješnosti ovih odluka? Ukupna mjera izvedbe je ukupna udaljenost najkraćeg puta, pa je cilj minimizirati ovu količinu.
2. Da biste model lakše razumjeli, stvorite sljedeće imenovane raspone.
| Naziv raspona | Stanice |
|---|---|
| Iz | B4: B21 |
| Do | C4: C21 |
| Udaljenost | D4: D21 |
| Ići | F4: F21 |
| NetFlow | I4: I10 |
| Zahtjev za nabavu | K4: K10 |
| Ukupna udaljenost | F23 |
3. Umetnite sljedeće funkcije.
Objašnjenje: SUMIF funkcije izračunavaju neto protok svakog čvora. Za čvor S, funkcija SUMIF zbraja vrijednosti u stupcu Idi s "S" u stupcu Od. Kao rezultat toga, samo ćelija F4, F5 ili F6 može biti 1 (jedan odlazni luk). Za čvor T, funkcija SUMIF zbraja vrijednosti u stupcu Idi s "T" u stupcu Do. Kao rezultat toga, samo ćelija F15, F18 ili F21 može biti 1 (jedan ulazni luk). Za sve ostale čvorove Excel gleda u stupcu Od i Do. Ukupna udaljenost jednaka je suproizvodu udaljenosti i kretanja.
Pokušaj i pogreška
S ovom formulacijom postaje lako analizirati bilo koje pokusno rješenje.
1. Na primjer, staza SBET ima ukupnu udaljenost 16.
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 TotalDistance za cilj.
3. Pritisnite Min.
4. Unesite Go za promjenu promjenjivih ćelija.
5. Pritisnite Dodaj za unos sljedećeg ograničenja.
6. Označite "Neka neograničene varijable budu negativne" i odaberite "Simplex LP".
7. Na kraju kliknite Riješi.
Proizlaziti:
Optimalno rješenje:
Zaključak: SADCT je najkraći put s ukupnom udaljenošću 11.
