300 Esimerkkejä

Lyhin polkuongelma

Shortest Path Problem

Muotoile malli | Yritys ja erehdys | Ratkaise malli





Käytä ratkaisijaa sisään Excel löytää lyhin tie solmusta S solmuun T suunnattomassa verkossa. Verkon pisteitä kutsutaan solmuiksi (S, A, B, C, D, E ja T). Verkon linjoja kutsutaan kaariksi (SA, SB, SC, AC jne.).

Muotoile malli

Malli, jonka aiomme ratkaista, näyttää seuraavalta Excelissä.





Lyhin polkuongelma Excelissä

kuinka löytää NPV Excelistä

1. Tämän muotoilemiseksi lyhimmän reitin ongelma , vastaa seuraaviin kolmeen kysymykseen.



a. Mitä päätöksiä on tehtävä? Tätä ongelmaa varten tarvitsemme Excelin selvittääksesi, onko kaari lyhyimmällä polulla vai ei (Kyllä = 1, Ei = 0). Jos esimerkiksi SB on osa lyhyintä polkua, solu F5 on 1. Jos ei, solu F5 on 0.

b. Mitä rajoituksia näillä päätöksillä on? Kunkin solmun nettovirran (virtaus ulos - virtaus) tulee olla sama kuin tarjonta/kysyntä. Solmulla S pitäisi olla vain yksi lähtevä kaari (nettovirtaus = 1). Solmulla T pitäisi olla vain yksi sisääntuleva kaari (nettovirtaus = -1). Kaikilla muilla solmuilla pitäisi olla yksi lähtevä valokaari ja yksi sisääntuleva kaari, jos solmu on lyhyimmällä reitillä (nettovirtaus = 0) tai ei virtausta (nettovirtaus = 0).

c. Mikä on näiden päätösten yleinen suorituskykymitta? Suorituskyvyn kokonaismitta on lyhyimmän polun kokonaismatka, joten tavoitteena on minimoida tämä määrä.

2. Jotta malli olisi helpompi ymmärtää, luo seuraava nimettyjä alueita .

Alueen nimi Solut
Alkaen B4: B21
Vastaanottaja C4: C21
Etäisyys D4: D21
Mennä F4: F21
Nettovirta I4: I10
Tarjonta ja kysyntä K4: K10
Kokonaismatka F23

3. Lisää seuraavat toiminnot.

Lisää toimintoja

Selitys: SUMIF funktiot laskevat kunkin solmun nettovirran. Solmun S tapauksessa SUMIF -funktio summaa Siirry -sarakkeen arvot ja S -arvon Lähettäjä -sarakkeessa. Tämän seurauksena vain solu F4, F5 tai F6 voi olla 1 (yksi lähtevä kaari). Solmun T osalta SUMIF -funktio summaa Siirry -sarakkeen arvot ja T -sarakkeen Vastaanottaja. Tämän seurauksena vain solu F15, F18 tai F21 voi olla 1 (yksi saapuva valokaari). Kaikkien muiden solmujen osalta Excel etsii Lähettäjä- ja Vastaanottaja -saraketta. Kokonaismatka on yhtä suuri kuin sumproduct etäisyydestä ja menosta.

Yritys ja erehdys

Tämän koostumuksen avulla on helppoa analysoida mitä tahansa koeratkaisua.

1. Esimerkiksi polun SBET kokonaispituus on 16.

Kokeiluratkaisu

Kokeilua ja erehdystä ei tarvitse käyttää. Seuraavassa kuvataan, miten Excel -ratkaisija voidaan käyttää nopeasti löytämään optimaalinen ratkaisu.

Ratkaise malli

Löydä optimaalinen ratkaisu suorittamalla seuraavat vaiheet.

1. Valitse Data -välilehden Analysoi -ryhmästä Ratkaisu.

Napsauta Ratkaisu

Huomautus: et löydä Ratkaisija -painiketta? Lataa tämä napsauttamalla tätä Ratkaisulaajennus .

Syötä ratkaisijaparametrit (lue). Tuloksen tulee olla alla olevan kuvan mukainen.

Excel-funktio, joka palauttaa nykyisen päivämäärän sarjanumeron.

Ratkaisuparametrit

Voit valita kirjoittamalla alueiden nimet tai napsauttamalla laskentataulukon soluja.

2. Syötä tavoitteen TotalDistance.

3. Napsauta Min.

4. Kirjoita Vaihda muuttuvat solut -näppäimellä Siirry.

luoda yhden muuttujan tietotaulukko

5. Napsauta Lisää syöttääksesi seuraavan rajoituksen.

Nettovirtausrajoitus

6. Valitse 'Make Unconstrained Variables Non-Negative' ja valitse 'Simplex LP'.

7. Napsauta lopuksi Ratkaise.

Tulos:

Ratkaisijan tulokset

Optimaalinen ratkaisu:

Lyhin polkuongelman tulos

Johtopäätös: SADCT on lyhin reitti, jonka kokonaismatka on 11.

4/7 valmis! Lue lisää ratkaisusta>
Siirry seuraavaan lukuun: Analysis ToolPak



^