Hálózatszámítási modellek

Hálózatszámítási modellek Dr. Rácz Ervin egyetemi docens Óbudai Egyetem, Kandó Kálmán Villamosmérnöki Kar Villamosenergetikai Intézet

HÁLÓZATBELI FOLYAM VAGY ÁRAMLÁS ÁLTALÁNOS PROBLÉMÁJA

Általános feladat Meghatározás (hálózatbeli folyam): A termelő helytől (forrástól, pl. erőműtől) a felhasználói piacig (célállomásokig, pl. fogyasztókig) terjedő, valamely egyszerű, homogén anyag vagy termék elosztására ill. szétosztására szolgáló feladat. Feltételek: 1. A megtermelt termék teljes mennyisége vagy száma ismert minden egyes termelési helyre (minden forrásra) nézve. (Pl. minden erőmű termelési mennyisége ismert) 2. A fogyasztók számára (fogyasztói piac számára) szükséges termékek mennyisége vagy száma ismert minden egyes felhasználóra vetítve. (Pl. minden fogyasztó szükséglete ismert) 3. A terméket a forrástól a célállomásig szállítják úgy, hogy a szállítás során a termék közbenső pontokon ill. elosztási helyeken (raktárakon, elosztási csomópontokon) megy keresztül. 4. A szállításra vonatkozóan vannak, vagy lehetnek ún. kapacitási előírások vagy határértékek.

Általános feladat Célfeladat meghatározása: A termék előállításának és szállításának várható és esetleg változó költségeinek a minimalizálása a fogyasztói igények figyelembe vételével. Elnevezések és jelölések a rendszerben:  Csomópontok: források, célállomások és a szállítás közbeeső pontjainak (raktárak, elosztási helyek) együttes neve.  Ívek, utak: Szállítási útvonalak (utak, csővezetékek hálózatai, távvezetékek ,...) együttes neve.  A csomópontok számozott körökkel 1 vagy betűkkel (A, B, C,...) vannak jelölve.  Az utak vagy ívek nyilakkal (irányított vonalakkal) jelöltek. 1 2

Általános feladat Példák az elnevezésekre: Tömegközlekedés

Kommunikációs rendszerek

Víz erőforrás

termék

Buszok, autók, vonat, stb.

Üzenetek, stb.

víz

csomópontok

Buszmegállók, Kommunikációs útkereszteződések, központok, vasutak relé állomások, stb. kereszteződései, stb.

Tavak, tározók, szivattyú állomások, stb.

ívek vagy utak

Utak, utcák, vasútvonalak, stb.

Csővezetékek, csatornák, folyók, stb.

Kommunikációs csatornák

Általános feladat gráfja •

Pl. (15, $4) Az adott szállítás költsége termék egységre vonatkoztatva ($4/termék)

Az áramlás kapacitása (ami lehet 0, 1, 2, ... 15.) a  végtelen átfolyási kapacitást jelöl. • A csúcspont melleti szám zárójelben: pl. (20)

Megadja a kibocsájtott (forrástól) vagy befogadott (fogyasztó) termék mennyiségét az adott csúcspontra nézve. Pl. (20): 20 termék elszállítható a forrásból. (-5): 5 terméket vár a célállomás, vagy az elosztóhely 5 terméket fogadhat.

• Xij: Az i-edik csomópontból a j-edik csomópontba az i-j íven vagy úton átszállított termék egységek száma • (Csomópontból ki) •

•

•



•

- (Csomópontba be) = (Csomópont netto ellátmánya) Az 1–2-re az egyensúly egyenletei: 1 x12 + x13 = 20 2 X23 + x24 + x25 – x12 = 0 +1 együttható: kifolyás a csomópontból -1 együttható: befolyás a csomópontba 0 együttható: semmi

A gráf táblázata Az átfolyási egyensúly egyenleteinek táblázata: CSOMÓPONT – ÚT ESEMÉNY MÁTRIX x12

x13

Csúcs 1

1

1

Csúcs 2

-1

Csúcs 3

x23

x25

x34

x35

x45

x53

Össz. 20

1 -1

x24 1

1

-1

Csúcs 4

0 1

-1

Csúcs 5

1

-1 -1

-1 1

0 -5

-1

-1

1

Kap.

15

8



4

10

15

5



4

Ár

4

4

2

2

6

1

3

2

1

-15 MIN

Minden egyes kettős indexű változó pontosan két egyensúlyi egyenletben jelenik meg egyszer +1 együtthatóval mint kifolyó mennyiség, egyszer -1 együtthatóval mint befolyó vagy beérkező mennyiség.

A VÉGCÉL MATEMATIKAI MEGFOGALMAZÁSA • A 𝒛=

𝒋 𝒄𝒊𝒋 𝒙𝒊𝒋

𝒊

= 𝒎𝒊𝒏𝒊𝒎𝒖𝒎 ,

Figyelembe véve, hogy 𝑥𝑖𝑗 − 𝑗

𝑙𝑖𝑗 : alsó korlát 𝑢𝑖𝑗 : felső korlát 𝑏𝑖𝑗 : egyensúlyi szám

𝑥𝑘𝑖 = 𝑏𝑖 (𝑖 = 1, 2, … , 𝑛) 𝑘

𝑙𝑖𝑗 ≤ 𝑥𝑖𝑗 ≤ 𝑢𝑖𝑗

SPECIÁLIS PROBLÉMÁK

1. A szállítási feladat Feladat: A szállítási feladat egy olyan hálózati modell probléma, amelyben nincsenek közbenső, közbeeső csomóponti helyek az útvonalban. Valamilyen forráshelyekről, valamiket, valamilyen célállomásokra el kell szállítani. Cél: A bekerülési költség minimális legyen.

1. A szállítási feladat – matematikai alak 𝑎𝑖𝑗 : Az i forráshelyen rendelkezésre álló termékek száma (𝑖 = 1, 2, … , 𝑚) 𝑏𝑗 : A j célállomáson szükséges termékek száma (𝑗 = 1, 2, … , 𝑛) 𝑐𝑖𝑗 : az egyes termékek szállítási költsége az i-edik forrástól a j-edik célállomásig Az egyszerűség kedvéért tegyük fel azt, hogy éppen annyi termék van a forráshelyeken, mint amennyi termékre a célállomásokon szükség van, azaz: 𝑚

𝑛

𝑎𝑖 = 𝑖=1

𝑏𝑗 𝑗=1

Legyen 𝑥𝑖𝑗 az i-edik forrástól a j-edik célállomásig szállított (terjesztett) termékek száma.

1. A szállítási feladat – matematikai alak Formulával: 𝒎

𝒏

𝒛=

𝒄𝒊𝒋 𝒙𝒊𝒋 = 𝒎𝒊𝒏𝒊𝒎𝒖𝒎 𝒊=𝟏 𝒋=𝟏

Ahol,

𝑛

𝑥𝑖𝑗 = 𝑎𝑖 , 𝑚

𝑗=1

−𝑥𝑖𝑗 = −𝑏𝑗 , 𝑖=1

𝑖 = 1, 2, … , 𝑚

𝑥𝑖𝑗 ≥ 0,

𝑗 = 1, 2, … , 𝑛

𝑖 = 1, 2, … , 𝑚. 𝑗 = 1, 2, … , 𝑛

2. Maximális folyam feladat Feladat: Amennyi terméket csak lehet el szeretnénk küldeni az s forrásból egy másik t-jelű helyre ill. célállomásra. Itt a t helyet nyelőnek nevezzük. Az átfolyásnak nincsen költsége. Ha v jelenti az s forrásból a t nyelőbe küldött anyag mennyiségét, és 𝑥𝑖𝑗 jelenti a folyamot az i csomópontból a j csomópontba az i-j úton vagy íven haladva, akkor formulákkal felírva: Keressük a 𝑣 minimumát, ahol: 𝑥𝑖𝑗 − 𝑗

𝑥𝑘𝑖 𝑘

0 ≤ 𝑥𝑖𝑗 ≤ 𝑢𝑖𝑗 ,

𝑣, ℎ𝑎 𝑖 = 𝑠 (𝑎 𝑓𝑜𝑟𝑟á𝑠) = −𝑣, ℎ𝑎 𝑖 = 𝑡 (𝑎 𝑛𝑦𝑒𝑙ő) 0, 𝑘ü𝑙ö𝑛𝑏𝑒𝑛 𝑖 = 1, 2, … , 𝑛. 𝑗 = 1, 2, … , 𝑛

AZ összegzés csak a hálózatban szereplő utakra vonatkozik. 𝑢𝑖𝑗 : a felső korlát az i-ből a j-be való folyam során 𝑣: egységek, amelyek az s csomópontban készleten vannak és t nyelőben elfogyasztásra kerülnek.

2. Maximális folyam feladat Vezessük be a t-ből az s-be vezető utat, és legyen 𝑢𝑡𝑠 = ∞ kapacitású. Ekkor 𝑥𝑡𝑠 reprezentálja a 𝑣 változót. Ekkor az előző feladattal analóg feladat a következő: Maximalizáljuk 𝑥𝑡𝑠 -et, ahol:

𝑥𝑖𝑗 − 𝑗

0 ≤ 𝑥𝑖𝑗 ≤ 𝑢𝑖𝑗 ,

𝑥𝑘𝑖 = 0, 𝑘

𝑖 = 1, 2, … , 𝑛

𝑖 = 1, 2, … , 𝑛.,

𝑗 = 1, 2, … , 𝑛

3. A legrövidebb út feladat Olyan hálózati modell, amely a praktikus és az elméleti okokat gyűjti egybe. Feladat: Adott egy hálózat a 𝑐𝑖𝑗 távolságokkal (ha nem távolság, akkor utazási idő, vagy utiköltség adatokkal, stb.) úgy, hogy 𝑐𝑖𝑗 minden egyes i-j úthoz vagy ívhez adva van. A feladat egy forrásból indítva egy nyelővel befejezve megtalálni azt az utat a hálózatban, amelyre a megtett távolság legrövidebb (megtett idő legrövidebb, vagy költség legkisebb).

A feladat egyszerűsége megtévesztő!

3. A legrövidebb út feladat matematikai alakban Matematikailag: 𝑧=

𝑐𝑖𝑗 𝑥𝑖𝑗 = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 𝑖

𝑗

legyen, ahol

𝑥𝑖𝑗 − 𝑗

𝑥𝑘𝑖 𝑘

1, ℎ𝑎 𝑖 = 𝑠 (𝑎 𝑓𝑜𝑟𝑟á𝑠) = −1, ℎ𝑎 𝑖 = 𝑡 (𝑎 𝑛𝑦𝑒𝑙ő) 0, 𝑘ü𝑙ö𝑛𝑏𝑒𝑛

„Valamit, valahová a legalacsonyabb költséggel el akarunk juttatni.”

3. A legrövidebb út feladat megoldása – Kruskal-algoritmus • A Kruskal-algoritmus egy súlyozott gráfokat feldolgozó mohó algoritmus. Ha a gráf összefüggő, akkor minimális feszítőfa megalkotására szolgál, ha nem, akkor minimális feszítő erdőt hoz létre. • Feszítőfa: Olyan fa, amely a gráf összes pontját tartalmazza. • A mohó algoritmus vagy greedy algoritmus az a problémamegoldó algoritmus, amely helyi optimumok megvalósításával próbálja megtalálni a globális optimumot. Pl: „az utazó ügynök problémája”: Adva van n város, illetve az útiköltség bármely két város között, keressük a legolcsóbb utat egy adott városból indulva, amely minden várost pontosan egyszer érint, majd a kiindulási városba ér vissza.

3. A legrövidebb út feladat megoldása – Kruskal-algoritmus • Az algoritmus lépései a következőek: – Válasszuk ki a legkisebb súlyú élt. – Amennyiben az él a részgráfhoz való hozzáadása kört alkot, dobjuk azt el. – Ha van még nem vizsgált él, folytassuk az előző lépésekkel. • Az algoritmus Joseph Kruskal (1928–2010) amerikai matematikustól és informatikustól származik, aki 1956-ban írta le.

3. A legrövidebb út feladat megoldása – Kruskal-algoritmus Rendezzük súly szerinti növekvő sorrendbe a gráf éleit: {A,D}, {C,E}, {D,F}, {A,B}, {B,E}, {B,C}, {E,F}, {B,D}, {E,G}, {F,G}, {D,E}

Kiindulő halmazok: {A}, {B}, {C}, {D}, {E}, {F}, {G}

Az első él: {A,D}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,D}, {B}, {C}, {E}, {F}, {G}

3. A legrövidebb út feladat megoldása – Kruskal-algoritmus A következő él: {C,E}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba.

{A,D}, {B}, {C,E}, {F}, {G}

A következő él: {D,F}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,D,F}, {B}, {C,E}, {G}

3. A legrövidebb út feladat megoldása – Kruskal-algoritmus A következő él: {A,B}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,B,D,F}, {C,E}, {G}

A következő él: {B,E}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,B,C,D,E,F}, {G}

3. A legrövidebb út feladat megoldása – Kruskal-algoritmus

{B,C}, {E,F}, {B,D} egyike sem jöhet szóba, mert végpontjuk ugyanazon halmazban van, tehát kör zárulna be (az ábrán piros színnel vannak jelölve). A következő él {E,G}; a két végpont két különböző halmazból van, tehát az él bevehető a megoldásba. {A,B,C,D,E,F,G} A zöld élek megadják a keresett feszítő fát.

3. A legrövidebb út feladat megoldása – Prim-algoritmus A Prim-algoritmus egy összefüggő súlyozott gráf minimális feszítőfáját határozza meg mohó stratégia segítségével. • Az algoritmus lépésenként építi fel a minimális feszítőfát, minden lépésben egy csúcsot adva hozzá. • Az algoritmus lépései a következők: – Válasszuk ki a gráf egy tetszőleg csúcsát, legyen ez egy egycsúcsú fa. – Ameddig van a gráfnak olyan csúcsa, amelyik nincs benne a fában, végezzük el a következőket: – Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút. – A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.

3. A legrövidebb út feladat megoldása – Prim-algoritmus Az algoritmust először Vojtěch Jarník írta le 1930-ban, de ez az eredmény ismeretlen maradt. Tőle függetlenül Robert C. Prim 1957-ben és Edsger Dijkstra 1959-ben újra felfedezték. Ezért az algoritmust nevezik még DJPalgoritmusnak, Jarník-algoritmusnak vagy Prim−Jarník-algoritmusnak is.

3. A legrövidebb út feladat megoldása – Prim-algoritmus

Kiválasztjuk az a csúcsot, kezdetben ez a fa. Kiválasztjuk a hozzá illeszkedő élek közül a legkisebb súlyút. Ez a c csúcs. Most az a és c csúcs, valamint az ezeket összekötő él képezi az új fát. A fa és a gráf többi csúcsa közötti élek közül a {c,h} él a legkisebb súlyú.


A h csúcs és a {c,h} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {h,g} él a legkisebb súlyú.


A g csúcs és a {h,g} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {g,e} él a legkisebb súlyú.


Az e csúcs és a {g,e} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {c,d} és {h,d} élek mindegyike legkisebb súlyú. Bármelyiket választhatjuk. Válasszuk a {c,d} élt!


A d csúcs és a {c,d} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {c, b} él a legkisebb súlyú.


A b csúcs és a {c,b} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül az {a, f} él a legkisebb súlyú.


Az f csúcs és az {a,f} él átkerül a fába, amely feszítőfa, mivel a gráf minden csúcsát tartalmazza.


Az eredmény az eredeti gráf csúcselrendeződése szerint. Amennyiben minden lépésben csupán egy legkisebb súlyú él van, a megoldás egyértelmű. Különben több minimális értékű feszítőfa létezhet.

Példa •

Egy gáztársaságnak saját csővezeték hálózata van, amelyet arra használ, hogy földgázt pumpáljon a földgázlelő területéről a fő elosztóközpontba. A hálózat gráfját az alábbi ábra mutatja, amelyen a nyilak iránya a gáz csővezetékbeli terjedési irányát jelenti. A csővezeték rendszer 1 – 6 részből áll az ábra szerint. A forrás és a célállomás közötti pontok a nagy szivattyú állomások. Jelenleg a társaság 1200 millió köbdeciméter gázt termel ki havonta. Ezt a gázmennyiséget kell elszállítani a lelőhelyről a központi elosztó helyre. A következő áramlási ráták és költségek vannak csővezetékenként:

Ráta millió dm3/hó •

1

2

3

4

5

6

500

900

700

400

600

1000

10

15

20

40

Költség 20 25 3 Adja meg a minimális költségű szállítási útvonalat! ($/milliódm )

1 5 3 2

4 6

Hálózatszámítási modellek

Recommend Documents