300 Esimerkkejä

Suurin virtausongelma

Maximum Flow Problem

Muotoile malli | Yritys ja erehdys | Ratkaise malli



Käytä ratkaisijaa sisään Excel löytää suurin virtaus solmusta S solmuun T suunnatussa 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ää Excelissä seuraavalta.



Suurin virtausongelma Excelissä

1. Tämän muotoilemiseksi suurin virtausongelma , vastaa seuraaviin kolmeen kysymykseen.



a. Mitä päätöksiä on tehtävä? Tätä ongelmaa varten tarvitsemme Excelin löytääksesi virtauksen jokaisesta kaaresta. Jos esimerkiksi virtaus SB: llä on 2, solu D5 on 2.

b. Mitä rajoituksia näillä päätöksillä on? Solmujen A, B, C, D ja E nettovirtauksen (virtaus ulos - virtaus sisään) pitäisi olla 0. Toisin sanoen virtaus ulos = virtaus sisään. Lisäksi jokaisella kaarella on kiinteä kapasiteetti. Kunkin kaaren virtauksen tulisi olla tätä kapasiteettia pienempi.

c. Mikä on näiden päätösten yleinen suorituskykymitta? Suorituskyvyn kokonaismitta on suurin virtaus, joten tavoitteena on maksimoida tämä määrä. Suurin virtaus on yhtä suuri kuin solmun S virtaus.

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

Alueen nimi Solut
Alkaen B4: B15
Vastaanottaja C4: C15
Virtaus D4: D15
Kapasiteetti F4: F15
Tarjonta ja kysyntä K5: K9
Suurin virtaus D17

3. Lisää seuraavat toiminnot.

Lisää toimintoja

Selitys: SUMIF funktiot laskevat kunkin solmun nettovirran. Solmulle A ensimmäinen SUMIF -funktio summaa Flow -sarakkeen arvot ja A -sarakkeen From -sarakkeesta (Flow Out). Toinen SUMIF -toiminto summaa Flow -sarakkeen arvot ja A -kirjaimen Vastaanottaja -sarakkeeseen (Flow In). Suurin virtaus on yhtä suuri kuin solun I4 arvo, joka on virtaus solmusta S. Koska solmujen A, B, C, D ja E nettovirta on 0, virtaus solmusta S vastaa solmun T virtausta.

Yritys ja erehdys

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

1. Esimerkiksi polku SADT, jonka virtaus on 2. Reitti SCT, jonka virtaus on 4. Reitti SBET, jonka virtaus on 2. Nämä reitit muodostavat kokonaisvirran 8.

Kokeiluratkaisu

tyhjien rivien poistaminen Excel 2010: ssä

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

Ratkaise malli

Löydä optimaalinen ratkaisu suorittamalla seuraavat vaiheet.

1. Valitse Tiedot -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.

Ratkaisuparametrit

Voit valita kirjoittamalla alueiden nimet tai napsauttamalla laskentataulukon soluja.

2. Anna tavoitteelle MaximumFlow.

3. Napsauta Max.

4. Anna muuttuvien solujen muutosvirta.

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

Nettovirtausrajoitus

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

Kapasiteettirajoitus

7. Valitse 'Tee rajoittamattomista muuttujista ei-negatiivisia' ja valitse 'Simplex LP'.

8. Napsauta lopuksi Ratkaise.

Tulos:

Ratkaisijan tulokset

Optimaalinen ratkaisu:

Suurin virtausongelman tulos

Johtopäätös: polku SADT, jonka virtaus on 2. Reitti SCT, jonka virtaus on 4. Reitti SBET, jonka virtaus on 2. Reitti SCET, jonka virtaus on 2. Reitti SACET, jonka virtaus on 1. Polku SACDT virtaus 1. Näiden reittien suurin virtaus on 12.

5/7 valmis! Lue lisää ratkaisusta>
Siirry seuraavaan lukuun: Analyysityökalupakki



^