/ / Maksimivirtaongelma Excelissä

Maksimivirtaongelma Excelissä

Määritä malli | Yritys ja erehdys | Ratkaise malli

Käytä ratkaisijaa sisään kunnostautua löytää maksimivirtaus solmusta S solmuun T suunnatussa verkossa. Verkon pisteitä kutsutaan solmuiksi (S, A, B, C, D, E ja T). Verkossa olevia viivoja kutsutaan kaavoiksi (SA, SB, SC, AC, jne.).

Määritä malli

Malli, jota aiomme ratkaista, näyttää Excelissä seuraavalla tavalla.

Maksimivirtaongelma Excelissä

1. Laatia tämä maksimivirtaongelma, vastaa kolmeen kysymykseen.

a. Mitä päätöksiä on tehtävä? Tätä ongelmaa varten Excel tarvitsee virtauksen kullekin kaarelle. Esimerkiksi jos SB: n virtaus on 2, solu D5 on 2.

b. Mitkä ovat näiden päätösten rajoitukset? Solmun A, B, C, D ja E nettovirtauksen (Flow Out Flow In) tulee olla 0. Toisin sanoen Flow Out = Flow In. Lisäksi kullakin kaarella on kiinteä kapasiteetti. Kunkin valokaaren virtauksen pitäisi olla pienempi kuin tämä kapasiteetti.

C. Mikä on suorituskyvyn yleinen suorituskyky?nämä päätökset? Suorituskyky on maksimivirta, joten tavoitteena on maksimoida tämä määrä. Suurin virtaus vastaa solmun S virtausta.

2. Mallin ymmärtämisen helpottamiseksi nimeä seuraavat alueet.

Alue-nimi solut
alkaen B4: B15
jotta C4: C15
Virtaus D4: D15
kapasiteetti F4: F15
Tarjonta ja kysyntä K5: K9
MaximumFlow D17

3. Aseta seuraavat toiminnot.

Lisää toiminnot

Selitys: SUMIF-funktiot laskevat kunkin solmun nettovirtauksen. Solmulle A ensimmäinen SUMIF-funktio summaa Flow-sarakkeen arvot A-sarakkeessa From-sarakkeesta (Flow Out). Toinen SUMIF-funktio summaa Flow-sarakkeen arvot A-sarakkeessa To-sarakkeessa (Flow In). Maksimivirta on sama kuin solun I4 arvo, joka on solmun S virtaus. Koska solmun A, B, C, D ja E solmun nettovirta on 0, solmun S ulosvirtaus vastaa solmun T virtausta.

Yritys ja erehdys

Tämän muotoilun avulla on helppo analysoida minkä tahansa kokeilulatkaisun.

1. Esimerkiksi SADT-polku, jonka virtaus on 2. Polku SCT ja virtaus 4. Polku SBET ja virtaus 2. Nämä polut antavat kokonaisvirtauksen 8.

Trial Solution

Ei ole tarpeen käyttää kokeilua ja virheitä. Seuraavaksi kuvataan miten Excel Solver voidaan löytää optimaalisen ratkaisun löytämiseksi nopeasti.

Ratkaise malli

Optimaalisen ratkaisun löytämiseksi suorita seuraavat vaiheet.

1. Valitse Tietojen välilehden Analysoi-ryhmästä Solver.

Napsauta Solver

Huomaa: et löydä Solver-painiketta? Napsauta tätä ladataksesi Solver-apuohjelman.

Anna ratkaisijaparametrit (lue lisää). Tuloksen on oltava seuraavan kuvan mukainen.

Solver-parametrit

Voit valita alueen nimiä tai napsauttamalla laskentataulukon soluja.

2. Syötä MaximumFlow-arvo tavoitteeseen.

3. Napsauta Maks.

4. Syötä Muuttuvien muuttuvien solujen virtaus.

5. Syötä seuraava rajoitin napsauttamalla Lisää.

Net Flow Rajoitus

6. Syötä seuraava rajoitin napsauttamalla Lisää.

Kapasiteettirajoitukset

7. Valitse "Tee rajoittamattomia muuttujia ei-negatiivisia" ja valitse "Simplex LP".

8. Napsauta lopuksi Ratkaise.

Tulos:

Solverin tulokset

Optimaalinen ratkaisu:

Suurin virtausongelma

Päätelmä: SADT-polku, jonka virtaus on 2. Reitti SCT, jonka virtaus on 4. Polku SBET ja virtaus 2. Polku SCET ja virtaus 2. Polku SACET virtauksella 1. Polku SACDT virtauksella 1. Nämä polut antavat maksimi virtaus 12.

Lue myös: