HÁLÓZATI FOLYAMOK

Dr. Nagy, Tamás

Új Széchenyi Terv logó.

Miskolci Egyetem

Kelet-Magyarországi Informatika Tananyag Tárház

Kivonat

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Lektor

Dr. Mályusz Levente

tanszékvezető egyetemi docens, Budapesti Műszaki és Gazdaságtudományi Egyetem, Építéskivitelezési Tanszék

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.


Tartalom

1. Bevezetés
2. Gráfelméleti alapfogalmak
2.1. Digráf fogalma
2.2. Az út és a vágás fogalma
2.3. Az út és a vágás dualitása. Címkézési technika
2.4. Címkézési technika
2.5. A hálózat fogalma
2.6. Feladatok
3. Minimális út-maximális potenciál feladatpár
3.1. A feladatpár megfogalmazása
3.2. A feladatpár matematikai vizsgálata
3.3. Algoritmus a minimális út - maximális potenciál feladatpár megoldására
3.4. Példamegoldás
3.5. Feladatok
4. Időtervezési feladat (CPM/time)
4.1. A feladat megfogalmazása
4.2. A feladat matematikai vizsgálata
4.3. Algortimus az időtervezési feladatra
4.4. Példamegoldás
4.5. Feladatok
4.6. Időtervezési feladat (PERT)
5. Maximális folyam - minimális vágás feladatpár
5.1. A feladatpár megfogalmazása
5.2. A feladatpár matematikai vizsgálata
5.3. Algoritmus a maximális folyam-minimális vágás feladatpár megoldására
5.4. Példamegoldás
5.5. Feladatok
6. Csúcskapacitásos folyamfeladat
6.1. A feladat megfogalmazása
6.2. A feladat matematikai vizsgálata és megoldási algoritmusa
6.3. Példamegoldás
6.4. Feladatok
7. Minimális költségű folyamfeladat
7.1. A feladat megfogalmazása
7.2. Algoritmus a minimális költségű folyamfeladat megoldására
7.3. Példamegoldás
7.4. Feladatok
8. Veszteséges-nyereséges folyamfeladat
9. Általános KŐNIG feladat
9.1. A feladat megfogalmazása
9.2. A feladat matematikai vizsgálata
9.3. Algoritmus az általános Kőnig feladat megoldására
9.4. Példamegoldás
9.5. Feladatok
10. Szűk-keresztmetszetű szállítási feladat
10.1. A feladat megfogalmazása
10.2. Algoritmus a szűk-keresztmetszetű szállítási feladat megoldására
10.3. Példamegoldás
10.4. FELADATOK
11. Ellátási feladat
11.1. A feladat megfogalmazása
11.2. A feladat matematikai vizsgálata és megoldási algoritmusa
11.3. Példamegoldás
11.4. Feladatok
12. „Házasság” feladat (Egyszerű KŐNIG feladat)
12.1. A feladat megfogalmazása
12.2. A feladat matematikai vizsgálata
12.3. Kőnig-Egerváry tétel
12.4. Algoritmus a „házasság” feladat megoldására
12.5. Példamegoldás
12.6. Feladatok
13. „Futószalag” feladat
13.1. A feladat megfogalmazása
13.2. Algoritmus a „futószalag” feladat megoldására
13.3. Példamegoldás
13.4. Feladatok
14. Szállítási feladat
14.1. A szállítási feladat megfogalmazása
14.2. A feladatpár matematikai vizsgálata
14.3. Algoritmus a szállítási feladat megoldására. A „magyar módszer”
14.4. Nem standard szállítási feladat kezelése
14.5. Példamegoldás
14.6. Feladatok
15. Trans-shipment feladat
15.1. A feladat megfogalmazása
15.2. A feladat matematikai vizsgálata és megoldási algoritmusa
15.3. Példamegoldás
15.4. Feladatok
16. Hozzárendelési feladat
16.1. A hozzárendelési feladat megfogalmazása
16.2. A „magyar módszer” eredetéről
16.3. Algoritmus a hozzárendelési feladat megoldására. A „magyar módszer”
16.4. Nem standard hozzárendelési feladat kezelése
16.5. Példamegoldás
16.6. Feladatok
17. Vegyes feladatok
Irodalomjegyzék

1. fejezet - Bevezetés

A hálózati folyamok témakörben olyan optimalizálási feladatokkal foglalkozunk, amelyek gráfok ill. hálózatok segítségével is megfogalmazhatók, ebből következőleg gráfelméleti eszközökkel is kezelhetők. Bevezetésképpen tekintsük az alábbi egyszerű szállítási feladatot. Három termelőtől (T) akarunk elszállítani bizonyos árut négy fogyasztóhoz (F). Valamilyen oknál fogva a , , viszonylatokban nem lehet szállítani. A termelőktől a fogyasztókhoz rendre 30, 50, 40 teherautónyi elszállítandó mennyiségű árut kell elszállítani. A fogyasztók igénye rendre 40, 20, 50, 30 teherautónyi mennyiségű áru. A fenti adatokat a termelők kínálatának ill. a fogyasztók keresletének szoktuk nevezni. Az alábbi táblázat mutatja, hogy a termelők telephelye és a megrendelőhelyek között egy teherautónyi mennyiségű árut mekkora költséggel szállíthatunk el. A tiltott viszonylatokat a táblázatban „-” jellel jelöltük.

Feladatunk a következő:

Adjuk meg azt a szállítási tervet, amelynél az áruk a termelőktől a fogyasztókhoz történő elszállítása a legkisebb költséggel valósul meg!

A feladat matematikai megfogalmazását az alábbiakban adjuk meg. A matematikai megfogalmazáshoz három dolgot kell meghatároznunk, ezek a következők: döntési változó megállapítása, a döntési változók lehetséges értékeit meghatározó feltételek felírása, végül annak a függvénynek a felírása, amelynek értéke szerint döntünk a lehetséges megoldások közül (ezt a függvényt célfüggvénynek nevezzük).

1. Döntési változó megállapítása:

Legyen a döntési változó az, hogy az egyes telephelyekről az egyes megrendelőhelyekre mennyi teherautónyi árumennyiséget szállítunk. Jelöljük ezeket az kétindexes változókkal, amely a termelőtől az fogyasztóhoz szállított mennyiséget mutatja. A döntési változókat az alábbi táblázatba foglalhatjuk.

2. Feltételek meghatározása:

Természetes feltétel, hogy az összes döntési változó nemnegatív. Először a kínálati feltételeket határozzuk meg. Az egyes termelőktől elszállítandó mennyiséget az egyes sorokban lévő döntési változók összege adja, amelynek egyenlőnek kell lenni a termelők kínálatával. A keresleti feltételek meghatározásánál figyelembe kell venni, hogy a termelők összkínálata kisebb, mint a fogyasztók összkereslete (), így a fogyasztók nem mindegyikének az igényét lehet teljes mértékben kielégíteni. Az egyes fogyasztókhoz szállítandó mennyiséget az egyes oszlopokban lévő döntési változók összege adja, amely kisebbnek vagy egyenlőnek kell lenni a fogyasztók keresletével.

3. Célfüggvény meghatározása:

Tegyük fel, hogy a szállítási költség lineárisan változik a szállítandó mennyiséggel. Jelölje a szállítási egységköltséget a termelőtől az fogyasztóhoz, ekkor a termelőtől az fogyasztóhoz az mennyiségű áru szállítási költsége . Itt vettük figyelembe a linearitási feltételezést. A szállítás összköltsége pedig az egyes viszonylatok szállítási költségének az összege.

A probléma matematikai modellje tehát a következő:

A termelőket, a fogyasztókat egy-egy „ponttal”, az egyes termelők és fogyasztók közötti szállítási kapcsolatot pedig egy-egy nyíllal reprezentálhatjuk a síkon. Ezt mutatja az alábbi ábra.

A fenti alakzatot gráfnak, pontosabban irányított gráfnak nevezzük. Amennyiben a kapcsolatokra ráírjuk a szállítási egységköltségeket, akkor hálózatot kapunk. A fentebb felírt szállítási feladat egy lineáris programozási feladat, így a lineáris programozás ismert módszereinek bármelyikével megoldható. Viszont azt is tudjuk, hogy ez egy rendkívül speciális szerkezetű lineáris programozási feladat, mivel az együtthatómátrixa csupán 0 és 1 értékeket tartalmaz és ezeket is megfelelő szabályossággal. A szállítási feladat tehát speciális szerkezeténél fogva gráfok segítségével is reprezentálható.

Természetesen a gráfok körében nem csupán optimalizálással kapcsolatos kérdéseket tehetünk fel, hanem kombinatorikai jellegűeket is. Szoros értelemben a gráfelmélet a kombinatorikai kérdések megválaszolásával foglalkozik. A gráfelmélet viszonylag fiatal része a matematikának. Születését a königsbergi hidak problémájának felvetődésétől számítják. Ennek története a XVIII. század 30-as éveire nyúlik vissza. A Szentpétervárhoz közeli Königsberg városát a Pregel nevű folyó átszeli és az akkori időben hét híd ívelte át, amelyet az alábbi ábra szemléltet.

A város polgárai szívesen sétálgattak a folyó partján és a hidakon, próbáltak olyan sétákat is tenni, amelynek alkalmával minden hídon pontosan egyszer haladnak át. Soha nem tudtak azonban ilyen sétautat találni. Ez időben a svájci származású matematikus, Leonard EULER (1707-1783) a szentpétervári akadémián dolgozott és Königsberg polgárai hozzá fordultak problémájuk megoldásában. Euler a problémára választ is adott az 1736-ban megjelent dolgozatában [3]. A matematikai szakirodalomban ezt a művet tekintjük az első gráfelméleti munkának és ezzel megszületett egy új matematikai diszciplína, a gráfelmélet. Euler a fenti ábrát leegyszerűsítve rajzolta le papírra. A két folyópartot (A, B) és a két szigetet (C, D) egy-egy ponttal, ezeket összekötő hidakat (a, b, c, d, e, f, g) egy-egy vonallal szemléltette, amelyet az alábbi ábra mutat. Egy gráf ábráján a gráf pontjait kis karikával szokás jelölni, de szokásos a körrel való jelölés is (a körbe írva a pont megnevezését), ez utóbbi ábrázolású a fejezet elején található digráf.

Euler a gráfban definiálta a gráf-vonalat, amely a gráf összes élének egy olyan egymásra kapcsolódó sorozata, amelyben a gráf élei nem ismétlődnek. Ha a sorozat első élének kezdőpontja megegyezik a sorozat utolsó élének végpontjával, akkor zárt gráf-vonalról, egyébként pedig nyitott gráf-vonalról beszélünk. Később a gráfelméletben a gráf-vonalat Euler-vonalnak, az olyan gráfot, amelynek van Euler-vonala Euler-gráfnak nevezték el. Euler a fent említett dolgozatában a „königsbergi hidak problémájaként” ismertté vált problémafelvetésre választ is adott. Mielőtt azonban a választ megfogalmazzuk, az Euler-vonal mellett még két fontos fogalomra van szükségünk. Egy gráf akkor összefüggő, ha bármely két pontját út köti össze, azaz élek sorozatával el tudunk jutni minden pontból minden pontba. A gráf pontjaihoz fokszámot rendelhetünk. Egy adott gráfpont fokszáma vagy röviden foka alatt a gráfponthoz illeszkedő élek darabszámát értjük.

EULER tétel:

  1. Ha egy gráf összefüggő és a gráf minden pontjának fokszáma páros, akkor létezik a gráfnak zárt Euler-vonala.

  2. Ha egy gráf összefüggő és a gráf két pontjának fokszáma páratlan, a többi pont fokszáma páros, akkor létezik a gráfnak nyitott Euler-vonala.

A második állítás az elsőből könnyen adódik, hiszen ha egy gráf összefüggő és a gráf két pontjának fokszáma páratlan, akkor kössük össze a két páratlan fokszámú pontot egy új éllel. Ekkor a bővített gráf összefüggő marad és minden pontja páros fokszámú, így az EULER tétel (1) része szerint létezik zárt Euler-vonal. Ha most elhagyjuk az új élet a zárt Euler-vonalból, akkor az eredeti gráf egy nyitott Euler-vonalát kapjuk.

Könnyen látható tehát, hogy a königsbergi sétát nem véletlenül nem sikerült megvalósítani a polgároknak, azt is látjuk, hogy bárhová megépítve a nyolcadik hidat, már megvalósítható a séta. A „königsbergi hidak problémája” úgy is felfogható, hogy lerajzolhatjuk-e a gráf éleit egyetlen ceruzavonással, úgy hogy a ceruzát nem emeljük fel a rajzolás során és egy élet csak egyszer rajzolunk le. Példaként az alábbi ábrán látható alakzatot rajzoljuk meg a fentiekben megfogalmazott egyetlen ceruzavonással.

Az alakzat gráfként is felfogható, annak ellenére, hogy a pontokat nem jelöltük be. Az EULER tétel szerint nyitott Euler-vonal van, így valamelyik páratlan fokszámú csúcspontból elindulva a második páratlan fokszámú csúcspontba megérkezve megrajzolható az ábra.

A görög mondából mindenki ismeri Ariadné fonalát, amelynek segítségével sikerült kijutnia Thészeusz athéni királyfinak a labirintusból, miután a labirintusban legyőzte Minótauroszt, a szörnyeteget. A monda szerint Ariadné Minósz krétai király leánya volt, Minótaurosz pedig a király félig bika, félig ember alakú szörnyszülött fia volt. Egy labirintust is kezelhetünk gráffal a következők szerint. A labirintusban az elágazási pontok és a zsákutcákat alkotó folyosók végei legyenek a gráf pontjai, a folyosószakaszok pedig legyenek a gráf élei.

Egy ország közút- vagy vasúthálózata is jellemezhető gráfokkal. A városokat ill. a falvakat a gráf pontjai, az összekötő útszakaszokat pedig a gráf élei reprezentálják. Nem ilyen egyszerű azonban egy város úthálózatának gráffal való azonosítása, mivel egyirányú utak is vannak. Ekkor az útkereszteződéseknek a gráf pontjait, az útszakaszoknak pedig az irányukat jelző ún. irányított éleknek feleltetjük meg. Az ilyen gráfokat irányított gráfoknak nevezzük. A későbbiekben csak irányított gráfokkal fogunk foglalkozni. Amennyiben egy útszakaszon mindkét irányban lehetséges a forgalom, azt két darab, iránnyal ellátott (oda-vissza) éllel fogjuk jellemezni. Az irányok használata valóban kijelöli az úthálózatban való haladási lehetőségeket, de azt nem kezeli, ha egy útkereszteződésben kanyarodási tilalmak is vannak. Ennek megvalósítását mutatjuk be az alábbiakban. Tekintsük az alábbi ábrán látható útkereszteződést, amelyben az a és b útszakaszon haladva balra is és jobbra is kanyarodhatunk, a c és d útszakaszon haladva pedig csak jobbra kanyarodhatunk.

Az útkereszteződés kanyarodási szabályát úgy tudjuk figyelembe venni, hogy az útkereszteződést nem egyetlen gráfponttal, hanem nyolc gráfponttal ábrázoljuk. Ezt mutatja az alábbi ábra.

Megjegyezzük, hogy amennyiben az a és b útszakaszokon haladóknak megengedjük az útkereszteződésben a megfordulást, akkor azt a felső két pontot összekötő jobbra irányuló ill. az alsó két pontot összekötő balra irányuló élek felvételével valósíthatjuk meg.

A gráfelméletet sok szaktudomány is alkalmazza egyszerűsége és könnyen kezelhetősége miatt. A fentebb látott példák mellett megemlítjük, hogy egy több tevékenységből álló feladat résztevékenységeit és a köztük fennálló logikai, technológiai kapcsolatokat is jellemezhetjük irányított gráffal. Ugyanígy egy elektromos hálózat is egy irányított gráf, amely különböző elektromos alkatrészek (ellenállások, tekercsek, kondenzátorok, fogyasztók, stb.) összekapcsolásával jön létre.

Ezen bevezető után a következő fejezetben a gráfokon történő optimalizáláshoz szükséges alapfogalmakat sajátítjuk el. Megismerkedünk egy nagyon fontos számolási eszközzel az ún. címkézési technikával, amely olyan fontos eszköz a gráfok esetében, mint a pivotálás a vektorok esetében. Az ezután következő fejezetekben optimalizálási modelleket tárgyalunk. A témakör kicsúcsosodását a hozzárendelési feladat megoldására 1955-ben H. W. KUHN [10] amerikai matematikus által kidolgozott „magyar módszer” jelenti. Végezetül megemlítjük, hogy az első összefoglaló mű a gráfokról 1936-ban KŐNIG DÉNES [9] magyar tudós tollából jelent meg.

2. fejezet - Gráfelméleti alapfogalmak

2.1. Digráf fogalma

A digráf fogalmához az egyszerűbb matematikai objektum, a gráf fogalmán keresztül juthatunk.

Gráf fogalma:

Véges sok pont és a pontok közötti kapcsolatokat kifejező élek összességét gráfnak nevezzük.

Irányított gráf fogalma:

Az olyan gráfot, amelynek élei irányítottak irányított gráfnak nevezzük.

Digráf fogalma:

Az olyan irányított gráfot, amely sem többszörös élt, sem hurokélt nem tartalmaz digráfnak nevezzük.

Az alábbi ábrán látható irányított gráfokban többszörös él és hurokél szerepel, így egyik sem tekinthető digráfnak:

Példaként tekintsük az alábbi ábrán látható digráfot, a következőkben ez lesz a minta digráfunk és ennek segítségével mutatjuk be a digráffal kapcsolatos fogalmakat:

Általában a digráf ponthalmazát N-el (Node), élhalmazát A-val (Arc) jelöljük. A digráf jelölésére az [N,A] szimbólumot használjuk. A pontokat általában a természetes számokkal jelöljük. Az éleket kerek zárójelbe írt pontpárral adjuk meg, az első helyen az él kezdőpontja, második helyen pedig az él végpontja szerepel.

A fenti példában szereplő digráf ponthalmaza és élhalmaza a következő:

Egy digráfot többféle módon is megadhatunk:

a) Ábrával

Ez a megadás a legtermészetesebb, az ábra alakja tetszőleges lehet, de ügyeljünk az áttekinthető ábrázolásra. Nem minden gráf rajzolható le úgy, hogy élei nem metszik egymást, csak az ún. síkbeli gráfokat lehet ilyen áttekinthető módon lerajzolni.

b) Az ponthalmaz és az élhalmaz tételes felsorolásával

Ez a megadási mód fentebb látható.

c) „Honnan-hova” táblázattal

Egy kétsoros táblázatban oszloponként felsoroljuk a digráf éleit. Az oszlop első eleme az él kezdőpontját (honnan), a második elem pedig az él végpontja (hova).

A minta digráf megadása „honnan-hova” táblázattal:

d) Szomszédossági mátrix segítségével

A szomszédossági mátrix egy pont-él mátrix, amelynek a sorai a digráf pontjait, oszlopai pedig a digráf éleit jelentik. Szokás ezt a mátrixot incidencia mátrixnak is nevezni. A mátrixot jelöljük S-el, elemei 1, -1, 0 számok és a mátrixelemeket az alábbiak szerint értelmezzük:

A minta digráf megadása ssomszédossági mátrix segítségével:

Megjegyzések:

Oszloponként vizsgálva a mátrixot, észrevehetjük, hogy minden oszlopban egyetlen egy 1-es és egyetlen egy (-1)-es van.

Soronként vizsgálva a mátrixot a következőket mondhatjuk:

A sorokban az 1-esek száma a sornak megfelelő pontból kifelé mutató élek darabszámát mutatja meg.

A sorokban a (-1)-esek száma a sornak megfelelő pontba befelé mutató élek darabszámát mutatja meg.

e) Struktúramátrix vagy struktúratáblázat segítségével

A struktúramátrix egy pont-pont mátrix, amelynek sorai és oszlopai is a digráf pontjait jelentik. Szokás ezt a mátrixot csúcsmátrixnak is nevezni. A mátrixot jelöljük C-vel, elemei 1, 0 számok és a mátrixelemeket az alábbiak szerint értelmezzük:

A minta digráf megadása struktúramátrix segítségével:

Észrevehetjük, hogy a mátrix négyzetes, a főátlójában zérus elemek állnak és az 1-esek száma a digráf éleinek a számát mutatja. Soronként és oszloponként vizsgálva a mátrixot a következőket mondhatjuk:

A sorokban az 1-esek száma a sornak megfelelő pontból kifelé mutató élek darabszámát mutatja meg.

Az oszlopokban az 1-esek száma az oszlopnak megfelelő pontba befelé mutató élek darabszámát mutatja meg.

A jobb szemléltetés miatt strukrúramátrix helyett inkább struktúratáblázattal adjuk meg a digráfot. A sorok és az oszlopok fejlécében felsoroljuk a digráf pontjait, a digráf éleit pedig úgy jellemezzük, hogy ahol él van a digráfban ott a táblázat megfelelő celláját megjelöljük valamilyen jellel (pl. a * szimbólummal), ahol nincs él ott üresen hagyjuk a táblázat celláját. A táblázat sorai az él kezdőpontját, az oszlopai pedig az él végpontját mutatják. A minta digráf megadása struktúratáblázat segítségével:

A struktúratáblázat főátlójában nem lehet * (mivel nincs hurokél), ezért a táblázat főátlójában egy -os egyenest szoktunk rajzolni, ezzel is segítjük a táblázatban történő könnyebb tájékozódást.

A digráfokon, majd később a hálózatokon az elvégzendő műveleteket mindig struktúratáblázaton valósítjuk meg. A mátrixos megadást a számítógépen történő megadáshoz ill. a matematikai kezeléshez szokás használni.

Megjegyzések:

  1. Egy gráfot egyszerűnek mondunk, ha a gráf nem tartalmaz sem többszörös élt, sem hurokélt. A digráf tehát egy egyszerű irányított gráf.

  2. Ha az ponthalmazból álló digráf minden élt tartalmaz, akkor azt mondjuk, hogy a digráf teljes és röviden -el jelöljük, éleinek száma: .

2.2. Az út és a vágás fogalma

Az alábbiakban a digráfokon két fontos fogalmat vezetünk be, az út és a vágás fogalmát, amelyeket először általánosan fogalmazunk meg, de majd mindig két kitüntetett ponttal kapcsolatban értelmezünk. Legyen adott az digráf és két kitüntetett pontja: (s=source (forrás), t=target (cél)).

Az út (-ből -be vezető út) fogalma:

Legyen az pontsorozat olyan, hogy minden esetén. Ekkor az pontsorozat által meghatározott élhalmazt az pontból az pontba vezető útnak nevezzük. Az út tehát nem más, mint azon élek összessége, amelyeken keresztül az egyik pontból a másikba irányított éleken eljuthatunk. Az utat matematikailag legegyszerűbben egy pontsorozattal adjuk meg, de valójában az út egymásba kapcsolódó élek halmaza. Jelölésére a

szimbólumot használjuk.

Ha az pontsorozat olyan, hogy az mellett és , akkor ezen pontsorozat által meghatározott élhalmazt a két kitüntetett pont közötti útnak vagy pontosabban s-ből t-be vezető útnak nevezzük.

A minta digráfban legyen és . Az -ból az -be vezető út (három ilyen út is van) a következőképpen adható meg:

Mint említettük, amikor az utat matematikai formában írjuk le, akkor a pontjai sorozatával () adjuk meg, de konkrét esetekben megadhatjuk természetesen más módon is az utat, mint élhalmazt, az élek felsorolásával is, például az utolsó utat így is megadhatjuk:

Szokásos az utat az alábbi szemléletes módon is jelölni, ezt fogjuk alkalmazni a példamegoldások során:

A vágás (az -et a -től elválasztó vágás) fogalma:

Legyen az ponthalmaz az és diszjunkt, nem üres ponthalmazokra felbontva, azaz , , , . Azon élek összességét, amelyek kezdőpontja -ben, végpontja -ben van vágásnak nevezzük, melynek jele . Képletben megfogalmazva az vágás:

Tehát a vágás is, mint ahogy az út is élek halmazát jelenti, az éleket azonban itt nem pontsorozattal, hanem két ponthalmaz segítségével határozzuk meg.

Ha az pontok olyanok, hogy és , akkor az vágást az pontokat elválasztó vágásnak nevezzük. Ekkor tehát a két kitüntetett pont el van választva, szeparálva van egymástól.

A minta digráfban legyen és , akkor az vágás az alábbi:

Ha a két kitüntetett pont: és , akkor ezt az vágást az pontot az ponttól elválasztó vágásnak is mondjuk. Ugyanezt a vágást lehet például az pontot az ponttól elválasztó vágásnak is nevezni. Ha előre megadjuk a két kitüntetett pontot, akkor általában többféle vágás is szóba jöhet, amely az és a pontokat elválasztja. Ha például és , akkor az -et az -től elválasztó vágások közül többek között az egyik lehet az és a ponthalmazokkal megadott vágás, ekkor az vágás élhalmazai az alábbiak:

Ez utóbbi vágást szemlélteti az alábbi ábra.

A későbbi vizsgálatainkban fontos lesz az alábbi fogalom. Egy vágást üresnek mondunk, ha az élhalmaz üres, azaz nincs olyan él, amely ponthalmaz valamelyik pontjából indulna és a ponthalmaz valamelyik pontjába érkezne.

Összefoglalva tehát az út és a vágás is egy-egy élsorozat, amelyet a matematikai leírásokban pontsorozattal ill. két ponthalmazzal szoktunk megadni.

Mind az utat mind a vágást illusztrálhatjuk a struktúratáblázatban is. Az út és a vágás éleit valamilyen módon „megjelöljük”, ezt a megjelölést az alábbiakban ismertetjük.

Út illusztrálása:

Az út éleit bekeretezéssel () szokás jelölni. Ilyenkor ugyan csak az út élei vannak feltüntetve, az élek egymásra kapcsolódása közvetlenül nem látszik. A későbbi alkalmazásokban látni fogjuk, hogy ez számunkra elegendő információ az útról. A minta digráfban az út illusztrálása bekeretezéssel:

Vágás illusztrálása:

A vágás éleit is nagyon egyszerűen szemléltethetjük, mégpedig a táblázat bizonyos sorainak és oszlopainak lefedésével. Egy-egy szaggatott vonallal lefedjük a struktúratáblázat azon oszlopait, amelyekhez tartozó pontok az ponthalmaz elemei és azon sorait, amelyhez tartozó pontok a ponthalmaz elemei. Ha a struktúratáblázatban egy élhez tartozó cella nincs lefedve, ez azt jelenti, hogy az él kezdőpontja -ben van, végpontja pedig -ben van. Tehát a fedetlen helyeken éppen az vágás élei vannak. Az olvasó könnyen ellenőrizheti, hogy a kétszer fedett helyeken a típusú élek vannak, azaz olyan élek, amelyek kezdőpontja a ponthalmazból, végpontja pedig az ponthalmazból való. Az egyszer fedett helyeken pedig az vagy a típusú élek vannak, azaz vagy -beli pontból indulnak és ott végződnek, vagy -beli pontból indulnak és ott végződnek. Nyilvánvaló, hogy az üres vágás is szemléltethető ilyen módon, ekkor a fedetlen helyeken nincs él, azaz nincs * jel.

A minta digráfban az vágás illusztrálása lefedéssel, ahol , ill. .

Az vágásbeli élhalmazok mellett a , és a élhalmazok is könnyen kiolvashatók a lefedés segítségével.

2.3. Az út és a vágás dualitása. Címkézési technika

Az út és a vágás fogalmak között szoros kapcsolat van, amelyet a fontosságára való tekintettel tétel formájában mondunk ki. A tételt az út és a vágás dualitási tételének vagy a megalkotójáról MINTY-tételnek nevezzük.

MINTY tétel (Út és vágás dualitási tétele):

Legyen digráf és benne az két kitüntetett pont. Az alábbi két állítás közül egyik és csak egyik igaz:

  1. van s-ből t-be vezető út,

  2. van az s-et t-től elválasztó üres vágás.

A tételre konstruktív bizonyítást adunk, amely vagy az utat, vagy az üres vágást adja meg. A bizonyításnak ezt a konstruktív (megoldást is szolgáltató) módját a későbbi tételeinkben is használjuk, így tulajdonképpen a tételeink bizonyítása egyben a megoldási algoritmust is megadja.

Bizonyítás.

Konstruáljuk meg (állítsuk elő) az halmazt a következőképpen:

• legyen ,

• legyen akkor, ha van olyan pont, hogy .

Ez a két részből álló, látszólag bonyolult matematikai megfogalmazás tulajdonképpen azt fejezi ki, hogy az halmaz álljon az pontból és az ebből a pontból úttal elérhető pontokból. Az megkonstruálása után két egymást kizáró esetet különböztethetünk meg.

  1. Ha , akkor konstrukcióját figyelembe véve van út -ből -be.

  2. Ha , akkor jelöljük -vel az úttal el nem érhető pontok halmazát, azaz . Mivel , így az egy vágás és ez az -t a -től elválasztja. Az konstrukciója miatt az így megalkotott vágás üres.

A bizonyításban szereplő halmaz meghatározására szolgáló eljárást címkézési technikának nevezik, amelyet a következő alfejezetben ismertetünk.

Az út és vágás dualitási tétele és a címkézési technika FORD L.R. Jr. [4] és MINTY G.J. [11] munkáiban szerepel először.

2.4. Címkézési technika

A címkézési technika tulajdonképpen nem más, mint azon pontok szisztematikus felkutatása, amelyek az s kitüntetett pontból éleken elérhetők. A pontok felkutatása során valamilyen módon megjelöljük azokat a pontokat, amelyekhez már elérkeztünk. Ezért célszerű a pontokhoz egy rekeszt rendelni. Ha egy ponthoz eljutottunk, akkor a pont rekeszébe valamilyen jelet írunk. Ez a jel szintén célszerűségi okokból a pontok azonosító címe (címkéje) legyen. Az S halmazt, azaz az pontból elérhető pontok halmazát ezek után a következő, programozásra is alkalmas eljárással építjük fel:

Kiválasztunk egy pontot, amelyről tudjuk, hogy az S halmazba tartozik. Induláskor ez csak az pont lehet. Az olyan eddig még nem vizsgált pontoknak a rekeszébe, amelyekhez az pontból vezet él, beírjuk az pont címét (címkézünk). Ezek a pontok most már az -hez tartoznak. Az így nyert pontokat sorra véve folytatjuk az eljárást. Hogy az ismétlődést elkerüljük, jelölnünk kell azt, ha egy pontot már megvizsgáltunk a továbbhaladás szempontjából. Ezt a címke előjelezésével oldjuk meg. Ha egy pontba eljutunk, akkor "negatív" címkével látjuk el és ha ebből a pontból továbbmentünk, ahová csak lehetett, akkor a címkét pozitívra változtatjuk át. A 0. lépésben (induláskor) az pont rekeszébe a „ ” címkét tesszük. Összefoglalva tehát a címkézési technika egy közbülső lépése abból áll, hogy:

Tekintünk egy negatív címkézett pontot (a pont már meg van címkézve, de címkéje negatív). Ennek a pontnak negatív címével címkézünk minden olyan üres rekeszű pontot, amelyek ebből a negatív címkézett pontból éllel közvetlenül elérhetők, majd utána (vagy akkor is, ha nem találtunk ilyen pontokat) a negatív címkézett pont címkéjét pozitívra váltjuk.

A címkézésből kiolvasható, hogy ha egy pont rendelkezik címkével (akár pozitív akár negatív címkével), akkor ez a pont -ből elérhető éleken. Ha a pont címkéje negatív, akkor még nem kíséreltük meg a pontból a továbbhaladást, ha viszont a pont címkéje pozitív, akkor már megkíséreltük a pontból a továbbhaladást.

Ha eljutottunk a ponthoz (), akkor -ből kiindulva visszafelé haladva a címkék segítségével megkapjuk az -ből a -be vezető utat.

Ha nem jutottunk el a ponthoz (), akkor a címkézett pontok tartoznak az -be, a címkézetlenek pedig a -be.

Az alábbiakban példákon keresztül mutatjuk be a címkézési technikát. Felhívjuk a figyelmet a példák tanulmányozására, mert néhány fontos jelölést is bevezetünk, amelyek hasznos alkalmazásoknak bizonyulnak a továbbiakban.

1. Példa:

Legyen adott az alábbi ábrával egy digráf hat ponttal és kilenc éllel. A digráf pontjait a további példákban is a sorszámaikkal jelöljük, nem pedig az eddig használt jelöléssel, amit leginkább az elmélet leírása során használunk. A digráf két kitüntetett pontja legyen és .

Határozzuk meg a digráfban a két kitüntetett pont közötti utat!

A címkézést a struktúra táblázaton végezzük és mindig balról az első negatív címkéjű pontból nézzük meg a továbbhaladást. A példában a címkézést lépésenként mutatjuk be. Az egyes lépésekben a pontok rekeszeit a táblázat fölött tüntettük fel (egyébként bárhol elhelyezhettük volna a rekeszeket). A későbbiekben természetesen csak egy rekeszsort fogunk használni. Az első példáknál azért írtunk minden továbbhaladási lépéshez rekeszsort, hogy a címkézési technika lépéseit nyomon tudjuk követni.

Az alábbiakban szavakban is leírjuk a címkézési technika lépéseit.

0. lépés:

Csupán abból áll, hogy a kezdőpont () címkéjeként „ ”-t írunk. Ezután megnézzük, hogy az pontból mely pontok érhetők el, ezt a 2. sorban található * szimbólumok jelzik. Látható, hogy elérhető közvetlenül a 4-es és a 6-os pont.

1. lépés:

A 4-es és a 6-os pont rekeszébe beírjuk a 2-es pont címét negatív előjellel. Az első lépéshez tartozik még a 2-es pont címkéjének pozitívra váltása. Ebben az állapotban tehát 3 darab pont tartozik a ponthalmazba, azaz az pontból úttal elérhető pontok halmazába.

2. lépés:

Tovább bővítjük az elérhető pontok halmazát. Az előző lépésből látható, hogy a 4-es és a 6-os pont címkéje negatív, tehát ezek közül valamelyikből nézzük meg a továbbhaladás lehetőségét. Javasoljuk a szisztematikus címkézés miatt, hogy mindig balról jobbra haladjunk, azaz balról az első negatív címkéjű pontot vizsgáljuk, példánkban ez a 4-es pont. Ebből a 4. sor alapján csak az 1-es pontba mehetünk, tehát az 1-es pontnak a „-4” címkét adjuk, a 4-es pont címkéjét pedig pozitívra változtatjuk.

3. lépés:

Az előző lépésből látható, hogy két negatív címkéjű pont van, ebből a balról az elsőt választjuk, azaz az 1-es pontot, ahonnan az 1. sor alapján a 3-as és a 6-os pontba mehetünk. A 3-as pontot megcímkézzük „-1”-el, az 1-es pont címkéjét pedig pozitívra változtatjuk. A 6-os pont címkéjét nem módosítjuk, hisz az már a ponthalmazba tartozik, tehát elérhető valamilyen úton az kezdőpontból.

4. lépés:

Az előző lépésből látható, hogy az első negatív címkéjű pont a 3-as pont, ebből a 3. sor és a már meglévő címkék alapján csak az 5-ös pontba mehetünk. Az 5-ös pontot megcímkézzük „-3”-al, a 3-as pont címkéjét pedig pozitívra változtatjuk. Ezzel befejeztük a címkézést, mert olyan állapothoz jutottunk, amikor a végpont is a megcímkézett pontok közé került, azaz az 5-ös pont úttal elérhető az kezdőpontból.

Az alábbi megjegyzést tesszük. A bizonyítás során a ponthalmazt az összes olyan pont halmazaként definiáltuk, amelyek a kezdőpontból elérhetők. Amennyiben a címkézés során olyan állapotba kerülünk, hogy a végpont is elérhető, akkor álljunk meg, mivel a kítűzött példában nem az volt a feladatunk, hogy az összes elérhető pontot felkutassuk, hanem utat keressünk. Ebben a példában egyébként nem is tudtuk volna tovább folytatni a címkézést, mivel minden pont meg lett címkézve. Könnyen látható, hogy az út megtalálásakor a címkének pozitívra változtatása felesleges munka. Természetesen folytathatjuk a címkézést egy nagyobb méretű feladat esetén, ha kíváncsiak vagyunk az összes elérhető pontra is.

A példánkban tehát azt kaptuk, hogy létezik út 2-ből 5-be. Azt azonban még nem tudjuk, hogy milyen úton lehet eljutni. Erre nagyon könnyű a válasz, hiszen az utat a címkéken visszafelé haladva határozhatjuk meg. A címkék definíciójából nyilvánvaló az út meghatározása, hisz egy adott pont címkéje azt mutatja, hogy közvetlenül honnan érkeztünk az adott ponthoz. Az 5-ös pont címkéje azt mutatja, hogy a 3-as pontból érkeztünk oda, a 3-as pont címkéje pedig azt, hogy az 1-es pontból érkeztünk oda, az 1-eshez a 4-esből, a 4-eshez pedig a 2-esből. A 2-es pont „+s” címkéje pedig azt mutatja, hogy visszafelé eljutottunk a kezdőponthoz. A címkézés alapján kapott út tehát a következő:

Írhattuk volna az utat fordított sorrendben is, de mindig a végpontból kell visszafelé haladni a címkéken. Az út másik leírása lehet például:

Természetesen létezhet más út is, de a címkézési technika egyetlen út meghatározására szolgál. Ha például a címkézés során jobbról balra vagy össze-vissza haladtunk volna, akkor másik utat kaphattunk volna.

Az alábbi struktúratáblázaton a fentebb meghatározott 2-ből az 5-be vezető „utat” (valójában csak az út éleit) illusztráljuk bekeretezéssel. Az út éleit a struktúratáblázatban úgy szemléltetjük, hogy a címkéken a végponttól visszafelé haladva az adott élet a táblázatban bekeretezzük.

2. Példa:

Keressünk az előző digráfban utat 1-ből a 2-be (, )! A címkézés lépéseit az alábbiakban közöljük, most már nem magyarázzuk meg az egyes lépéseket.

A címkézés során nem találtunk utat, viszont találtunk egy üres vágást, amely az 1-et és a 2-t elválasztja. Az üres vágást meghatározó ponthalmazok az alábbiak:

, amely a címkézett pontok összessége,

, amely a címkézetlen pontok összessége.

Az alábbi struktúratáblázaton a fentebb meghatározott üres vágást illusztráljuk lefedéssel. A vágás éleit a megismert lefedéssel szemléltetjük a struktúratáblázatban. A példabeli vágás üres, így olyan lefedő vonalrendszert kapunk, amelynél fedetlen helyeken nincs él, azaz nincs * jel.

3. Példa:

Határozzuk meg az előző digráfban a 3-ból a 4-be vezető utat! Célszerű a címkézésnél az és az pontokat megjelölni (pl. nyíllal), hogy a címkézést csak addig folytassuk, míg a pont rekeszébe címke kerül (ekkor van út) vagy addig, amikor már csak pozitív előjelű címkék vannak (nincs út, van üres vágás). E példában és a későbbiekben is csak egy rekeszsort használunk.

Megoldás: A 3-ból a 4-be vezető út: .

2.5. A hálózat fogalma

Tekintsünk egy digráfot, az éleihez rendeljünk hozzá egész számokat. A digráfot az éleire rendelt nemnegatív egész számokkal együtt hálózatnak nevezzük és -val jelöljük. A érték az él valamilyen számszerűsíthető tulajdonságát jelenti, általában időt, távolságot, költséget, kapacitást stb. jelent. A hálózatot a digráfhoz hasonlóan lehet megadni. A értékeket „honnan-hova” táblázat esetén egy harmadik sorban, struktúramátrix esetén pedig a mátrix elemeiként adjuk meg. Az alábbiakban az út és a vágás fogalmával kapcsolatban két optimalizálási feladatot fogalmazunk meg:

a) Minimális út feladat:

Legyen az hálózatnak két kitüntetett pontja .

Meghatározandó azon -ből -be vezető P út, amely mentén az élekre írt értékek összege, azaz a

mennyiség minimális.

A mennyiséget általánosan úthossznak szoktuk nevezzük. A minimális út a értékektől függően jelenthet legkisebb távolságú, legrövidebb idejű, legkisebb költségű, legkisebb kapacitású stb. utat.

b) Minimális vágás feladat:

Legyen az hálózatnak két kitüntetett pontja: .

Meghatározandó az -et a -től elválasztó vágások közül az, amelynél a vágásbeli élekre írt értékek összege, azaz a

mennyiség minimális.

A k(S,T) mennyiséget általánosan az (S,T) vágás kapacitásának szoktuk nevezni.

A jegyzetben két irányban indulunk el, a fentebb definiált két optimalizálási feladatnak megfelelően. Az első irány, a minimális út témakör sok érdekes feladathoz vezet, mi a minimális út problémával és az időtervezési feladatokkal (CPM/time, PERT) foglalkozunk. A második irány a minimális vágás feladat témaköre, erre fűzzük fel a további optimalizálási feladatainkat, így többek között a hozzárendelési és a szállítási feladatot is, amelyek megoldására a „magyar módszer”-t mutatjuk be.

2.6. Feladatok

  1. A fejezet elején adott minta digráfon keressünk

    a) -ből -be vezető utat,

    b) -ből -ba vezető utat!

  2. Adott az alábbi „honnan-hova” táblázattal egy digráf. Határozzuk meg a

    a) 4-ből a 8-ba vezető utat,

    b) 1-et a 10-től elválasztó üres vágást!

    Egy lehetséges megoldás:

    a) ,

    b) ,

  3. Adott egy digráf az alábbi ábrával. Keressünk utat 1-ből 9-be, ill. 8-ból 3-ba!

  4. Az alábbi „honnan-hova” táblázattal adott digráfon keressük meg a két kitüntetett pont közötti utat vagy a két kitüntetett pontot elválasztó üres vágást, ha a két kitüntetett pont:

    a) s=1, t=8,

    b) s=2, t=7.

3. fejezet - Minimális út-maximális potenciál feladatpár

3.1. A feladatpár megfogalmazása

Legyen adott egy hálózat. A hálózat éleihez rendelt nemnegatív egész számot az él hosszának nevezzük. Legyen a hálózatnak két kitüntetett pontja .

Minimális út feladat (primál feladat)

Meghatározandó azon s-ből t-be vezető

út, amely mentén a

mennyiség minimális.

A k(P) mennyiséget úthossznak nevezzük.

Maximális potenciál feladat (duál feladat)

Meghatározandó a hálózat minden pontjához egy , egész szám úgy, hogy

maximális legyen, feltéve, hogy

A értéket az x pont potenciáljának nevezzük. Az összes ponthoz rendelt értékeket együttesen () potenciálrendszernek szokás nevezni.

A feladatok jobb megértése érdekében jelentsen a hálózat egy éle egy útszakaszt, az élre írt szám pedig ezen útszakaszon történő szállítás költségét jelentse. Ez a költség arányos lehet az él hosszúságával, innen az úthossz elnevezés. Ezen értelmezés szerint a minimális út feladat nem más, mint a két kitüntetett pont közötti legkisebb költséggel megvalósítható szállítás útvonalának meghatározása.

A maximális potenciál feladatot pedig a következő okoskodással érthetjük meg leginkább. Tegyük fel, hogy egy vállalkozó felajánlja, hogy a szállítást elvégzi a szállíttató helyett és megad minden pontra egy értéket, amely azt jelenti, hogy az s-ből az x-be ennyiért hajlandó szállítani. A árajánlatnak nyilván olyannak kell lennie, hogy elfogadható legyen. Egyrészt tehát az s-be való szállítás zérus legyen, másrészt, ha s-ből az x-be a vállalkozó szállítana (ennek költsége: ), utána az élen pedig a szállíttató szállítana (ennek költsége: ), akkor az s-ből az y-ba történő szállítás költségére nyilvánvalóan fenn kell állnia, hogy

ez pedig átrendezéssel a duál feltétel. A fenti feltételeket kielégítő árajánlatok közül választhat a vállalkozó, hogy a s-ből t-be történő szállítási megbízást megkapja. A vállalkozó célja természetesen az, hogy olyan árajánlatot adjon, amelynél a legnagyobb bevételre tesz szert, azaz a t-be történő szállítás költsége a lehető legnagyobb legyen.

3.2. A feladatpár matematikai vizsgálata

A primál és a duál feladat között szoros kapcsolat van. Először a célfüggvények közötti kapcsolatra mutatunk rá. Ezt az összefüggést lemmában (segédtétel) mondjuk ki, amelyet a főtétel (a főtétel az optimális megoldások létezését és kapcsolatát mondja ki) bizonyításához használunk fel.

LEMMA:

Tetszőleges -ből -be vezető út és tetszőleges megengedett () potenciálrendszer esetén a úthossz nem lehet kisebb, mint a végponthoz tartozó potenciál, azaz a célfüggvények értékei között az alábbi összefüggés áll fenn:

Bizonyítás.

A duál feladat két feltételének felhasználásával és egyszerűsítéssel egyszerűen adódik, hogy

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha az -ből -be vezető út és a megengedett potenciálrendszer olyan, hogy a lemmában egyenlőség áll fenn, akkor a úthossz minimális értékű, a potenciál pedig maximális értékű, azaz az út és a potenciálrendszer optimális.

Bizonyítás.

Legyen a szóbanforgó út és a potenciálrendszer olyan, hogy .

Indirekte tegyük fel, hogy a út nem minimális, azaz létezik egy út, amelyre

Mivel a útra is igaz a lemma állítása, így

felhasználva a egyenlőséget, ebből adódik, hogy

ez pedig ellentmond a indirekt feltevésünknek, tehát nem létezik útnál jobb út, azaz a út optimális (minimális).

Most pedig indirekte tegyük fel, hogy a potenciálrendszer nem maximális, azaz létezik egy potenciálrendszer, amelyre

Mivel a potenciálrendszerre is igaz a lemma állítása, így

Az utóbbi két összefüggés ellentmond egymásnak, tehát a feltevésünk hamis volt, azaz nem létezik potenciálrendszernél jobb, tehát a potenciálrendszer optimális (maximális).

A soron következő második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (Optimalitási kritérium):

A lemmában egyenlőség akkor és csak akkor áll fenn, ha a út minden élén

Bizonyítás.

Rendezzük át a lemma bizonyításában szereplő egyenlőtlenséget, ekkor a lemmabeli egyenlőség fennállásához azt kell megvizsgálnunk, hogy mikor lesz az alábbi összefüggés zérus

A duál feltétel szerint az összeg minden tagja nemnegatív, így az összeg akkor és csak akkor lehet zérus, ha minden tagja zérus. Ez pedig azt jelenti, hogy a lemmabeli egyenlőség szükséges és elégséges feltétele, hogy minden útbeli élen .

FORD tétel:

Ha van -et -vel összekötő út, akkor létezik olyan út és potenciálrendszer, hogy a lemmában egyenlőség áll fenn, azaz létezik minimális út és maximális potenciál; a minimális úthossz és a maximális potenciál egyenlő egymással, képletben:

Bizonyítás.

A bizonyítás konstruktív jellegű, az optimális megoldáspár (primál és duál) meghatározásának menetét (algoritmusát) is szolgáltatja.

Legyen a potenciálrendszer megengedett, amely tehát a duál feltételeket kielégíti. Ilyen potenciálrendszer biztosan létezik, hiszen a értékek nemnegativitása miatt a megengedett potenciálrendszer. Konstruáljunk a hálózat éleiből egy digráfot, amelynek E élhalmaza azon élekből álljon, amelyekre

Keressünk utat s-ből t-be az digráfon. A Minty tétel értelmében két eset lehetséges:

1. eset: van út

Ez azt jelenti, hogy ezen út minden élén . A két következmény alapján optimális megoldást kaptunk, azaz a megtalált út is és a potenciálrendszer is optimális.

2. eset: nincs út

MINTY tétel szerint van olyan vágás, amely üres. Ez azt jelenti, hogy a vágásban nincs olyan él, amelyre , tehát a hálózatban ezen vágásbeli éleken . Képezzük a vágásban levő éleken az

értéket, azaz számítsuk ki a hálózat vágásbeli élein a és a mennyiségek különbségének minimumát. Könnyen ellenőrizhető, hogy , hisz pozitív számok minimuma is pozitív. Most határozzunk meg egy új potenciálrendszert az alábbi módon:

Ez az új potenciálrendszer kielégíti a duál feltételeket, amelyet az alábbiakban igazolunk.

A , mert .

A feltételek teljesülését az élhalmaz partícióra bontásával igazolhatjuk legkönnyebben.

Az partíciókban az alábbiak szerint alakul a duál feltétel teljesülése:

  1. Ha , akkor ,

  2. Ha ,

  3. Ha , mivel ,

  4. Ha .

Ez utóbbi állítás az érték definíciója miatt igaz, ugyanis minden vágásbeli élre és az utolsó partíció éppen a vágás.

Az új potenciálrendszerre megismételjük a fent leírtakat. A duál célfüggvény értéke értékkel növekszik, mivel . Az alapadatok egészértékűsége miatt egész szám és a lemma alapján a duál célfüggvény felülről korlátos, ezért az eljárás véges sok lépésben végetér, azaz eljutunk az 1. esethez (optimális megoldáshoz).

A minimális út probléma megoldása FORD L.R. Jr. [4] és MINTY G.J. [11] munkáiban szerepel.

3.3. Algoritmus a minimális út - maximális potenciál feladatpár megoldására

A bizonyításból kiolvasható, hogy a megoldás útkeresések sorozatából áll. Utat pedig azon éleken kell keresni, amelyeken . Az algoritmus megszervezhető úgy, hogy lépésenként nem számítjuk ki a potenciálrendszert, hanem az élekre számított értékekkel dolgozunk, amelyet az alábbiak szerint definiálunk:

Tehát a hálózat típusú élein kell utat keresni. Az számítása is könnyen megvalósítható a már megismert lefedéssel. A keletkező vágást az táblázat lefedésével szemléltetjük. A vágás definiciójánál ismertetett fedővonalrendszer megalkotásából tudjuk, hogy a fedetlen cellák az vágásbeli élek halmazát, a kétszer fedett cellák a élhalmazt, míg az egyszer fedett cellák az és a élhalmazokat jelölik ki.

Tehát a fedetlen értékek minimuma lesz az érték.

Ahelyett tehát, hogy új potenciálokat számolnánk, azonnal új értékeket határozunk meg, hisz a következő útkeresést ezen táblázaton kell elvégezni. A FORD tétel bizonyításából könnyen kiolvasható az új táblázat számítása, amely a következő:

Az algoritmus kiinduló lépése egy potenciálrendszer megválasztása. A gyakorlatban legtöbbször a kezdeti potenciálrendszert választjuk, így induláskor . A FORD tételből kiolvasható, hogy az algoritmus akkor fejeződik be, ha találunk utat, ez az út lesz a minimális út. Amennyiben a duál változók optimális értékére is kiváncsiak vagyunk, egy kis számolással azokat is megkaphatjuk az utolsó táblázatból. Célszerű az út éleire felírt egyenletekből számolni, hisz itt . Ekkor megkapjuk az uton lévő pontok potenciáljait, a többi pont potenciálját olyan élre írt egyenletből kell meghatározni, amely élen az egyik pont potenciálja ismert. A potenciál meghatározást számpéldán fogjuk bemutatni.

3.4. Példamegoldás

Az eljárás illusztrálására tekintsük az alábbi hálózatot és ezen keressük meg a 2-ből az 5-be vezető minimális utat.

A hálózat struktúra táblázata ():

0. lépés:

Kezdeti potenciálok ill. a kezdeti értékek meghatározása:

1. lépés:

Útkeresés 2-ből 5-be az típusú éleken

Nem találtunk utat. A kiadódó (S,T) halmazok segítségével elvégezzük a lefedést. A címkézett oszlopokat és a címkézetlen sorokat fedjük le egy-egy vonallal.

A lefedés után meghatározzuk az értéket, amely a fedetlen elemek minimuma:

Ezután pedig az új táblázatot határozzuk meg, a fedetlen helyeken csökkentünk, a kétszer fedett helyeken növelünk értékkel. Ezután újabb útkeresés következik, amelyet a 2. lépésben mutatunk be. Megjegyezzük, hogy a továbbiakban nem rajzoljuk fel a táblázatot kétszer, hanem a címkézés után azonnal elvégezzük a lefedést. Reméljük ez a rövidítés nem zavarja a kezdő olvasót.

2. lépés

Útkeresés 2-ből 5-be az típusú éleken.

3. lépés:

Útkeresés 2-ből 5-be az típusú éleken.

4. lépés:

Útkeresés 2-ből 5-be az típusú éleken

Vége az algoritmusnak, mert utat találtunk. A primál és a duál feladat optimális értékeinek meghatározása:

Minimális út feladat optimális megoldása:

A P minimális út:

A P minimális út hossza:

Maximális potenciál feladat optimális megoldása:

, a duál feltétel miatt.

Az útban lévő első élre ((2,1) él) felírt egyenletben csak a az ismeretlen, amelynek értéke:

Az útban lévő második élre ((1,4) él) felírt egyenletben csak a az ismeretlen, amelynek értéke:

Az útban lévő harmadik élre ((4,5) él) felírt egyenletben csak a az ismeretlen, amelynek értéke:

A nem útba eső 3 pont potenciálját például meghatározhatjuk az (3,5) élre felírt egyenletből, amelyben csak a az ismeretlen, ennek értéke:

Természetesen más élet is választhattunk volna, például a (2,3) élen könnyebb lett volna a számolás.

Összefoglalva, a potenciálok optimális értékei a következők:

A duál célfüggvény optimál értéke, .

Látható, hogy optimális esetben a célfüggvények értékei megegyeznek.

3.5. Feladatok

  1. Adott az alábbi „honnan-hova” táblázattal egy hálózat. Keressen olyan utat, amely útban az élek hosszúságának összege a legkisebb értékű!

    Megoldás:

    A minimális út: .

    A minimális úthossz:

  2. Határozza meg az alábbi hálózaton az 1-ből a 7-be vezető legrövidebb utat és a potenciálrendszert!

  3. Legyen adott egy városi úthálózat. Hogyan kell közlekednünk két útkereszteződés (s és t) között, hogy minél kevesebb útkereszteződést érintsünk útunk során?

    Útmutató a megoldáshoz:

    Ha az úthálózatot (amelyet digráffal reprezentáltunk) hálózattá alakítjuk úgy, hogy minden élre egységnyi értéket írunk, akkor ezzel a feladatot minimális út feladatra vezettük vissza. Nyilvánvaló, hogy a hálózat minimális útja a legkevesebb csomópontból álló útvonalat fogja kijelölni.

  4. Adott egy elektromos hálózat. Minden csomópontban van egy kapcsoló (K). A legkevesebb kapcsoló beiktatásával szeretnénk az s és a t jelű pontok között kapcsolatot teremteni. Mely kapcsolókat kell üzembe helyezni?

  5. Adott egy vállalat úthálózata, távolságokkal. Az 1 jelű munkahelytől kell eljutni az 5 jelű munkahely érintésével a 8 jelű raktárba úgy, hogy legkevesebb utat tegyünk meg. Milyen úton lehet ezt megvalósítani?

    Útmutató a megoldáshoz:

    Két minimális utat kell keresni, egyiket 1-ből 5-be, másikat 5-ből 8-ba!

  6. Legyen adott egy hírközlési há1ózat. Jelölje az i és a j pont közötti összeköttetés működőképességének valószínűségét. Feladatunk, hogy egy kijelölt pontból egy másikba olyan összeköttetéseket hozzunk létre, hogy a hírt a két csomópont között legmegbízhatóbban továbbíthassuk, azaz a két pont közötti összeköttetés működőképességének valószínűsége minél nagyobb legyen!

    Útmutató a megoldáshoz:

    Egy összeköttetés egy utat jelöl ki a hálózatban, mely összeköttetés működőképességének va1ószínűségét az egyes pontok közötti összeköttetési va1ószínűségek szorzata adja. Ezt a szorzatot kell tehát maximalizálni. Ez a feladat akkor válik a megismert minimális út problémává, ha minden va1ószínűséget a „hosszúsággal” helyettesítünk, ugyanis ekkor az útbeli

    célfüggvény helyett a

    célfüggvény használható. Ismert tény, hogy az összeg logaritmusa egyenlő a logaritmusok összegével, azaz

    Felhasználva a logaritmus függvény monoton növekedését és azt a tény, hogy egy függvény ott veszi fel minimumát, ahol a (-1)-szerese a maximumát, könnyen látható a két célfüggvény kapcsolata.

4. fejezet - Időtervezési feladat (CPM/time)

4.1. A feladat megfogalmazása

A termelési folyamat vagy egy gépsor leállítása, szétszedése, javítása, összeszerelése stb. egymás után és egymással párhuzamosan végezhető tevékenységekből áll. A tevékenységek logikai kapcsolatát egy digráffal lehet szemléltetni. A digráf élei a tevékenységeket, a csúcspontok pedig az eseményeket jelölik. Ezek az események bizonyos tevékenységek befejezését ill. belépő tevékenységek kezdését jelölik.

Például tekintsük egy csarnoképület szerelésének tevékenységlistáját és tevékenységidejét:

A következő ábra a tevékenységek kapcsolatának digráffal történő ábrázolását mutatja:

A szaggatott vonallal jelölt tevékenységet azért kellett beiktatni, hogy a helykitűzés (A) megelőzze az elemek helyszínre szállítását (E). Az ilyen tevékenységet, amely csupán a végrehajtás sorrendjét hivatott jelezni, látszattevékenységnek nevezzük és tevékenységidejét zérusnak vesszük. Mint a példából is kitűnik, egy munkafolyamat logikai ábrázolásaként egy speciális digráfot ún. tervütemhálót kapunk. A tervütemháló olyan digráf, amelynek

  1. létezik kezdőpontja és végpontja úgy, hogy bármely esetén vezet út s-ből x-be és x-ből t-be,

  2. körútmentes, azaz nincs önmagába visszatérő út.

Az eseményeket (csomópontokat) , amelyek a tevékenységeket fűzik össze, sorszámmal szoktuk ellátni és így a tevékenységeket a kezdő eseménye és a befejező eseménye sorszámával jelöljük: (x,y), a tevékenységidőt pedig egész szám jelöli. Mivel a tervütemháló speciális digráf, így az események sorszámozását mindig el lehet úgy végezni, hogy minden tevékenységre igaz legyen, hogy a kezdő eseményének sorszáma kisebb, mint a befejező eseményének sorszáma. A példa is ezt a sorszámozást követi és ezt a tárgyalásunkban is mindig feltesszük.

Nyilvánvaló, hogy egy ilyen munkafolyamat megtervezésénél egyik felmerülő kérdésünk, hogy mennyi az átfutási idő. Ezt a leghosszabb út hossza adja. Másik kérdésként felmerül az a probléma, hogyan kell ütemezni az egyes tevékenységek elvégzését. E szempontból fontos mozzanat az események bekövetkezése, mert ez a feltétele annak, hogy az eseményből kiinduló tevékenységek elkezdődhessenek. Ebből a szempontból tehát az események bekövetkezése a fontos, amelyet az eseményidővel jellemzünk. Ezekután fogalmazzuk meg a feladatokat matematikai formában.

Primál feladat:

Meghatározandó az tervütemhálóban az s-ből a t-be vezető

utak közül az, amelynél a

érték maximális.

Ezt a maximális utat kritikus útnak, a hozzátartozó maximális célfüggvényértéket átfutási időnek nevezzük.

Duál feladat:

Meghatározandó minden ponthoz egy eseményidő, amelyre az

feltételek fennállnak és az

érték minimális.

Az eseményidők együttesét ütemezésnek vagy időpolitikának nevezzük. Az értéket az ütemezés értékének nevezzük.

4.2. A feladat matematikai vizsgálata

A fent vázolt két feladat szoros kapcsolatát az alábbi lemma szemlélteti.

LEMMA:

Tetszőleges -ből -be vezető út és tetszőleges megengedett ütemezés esetén a célfüggvények értékei között az alábbi összefüggés áll fenn:

Bizonyítás.

A duál feladat feltételének felhasználásával és egyszerűsítéssel egyszerűen adódik, hogy

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha az -ből -be vezető út és a megengedett ütemezés olyan, hogy a lemmában egyenlőség áll fenn, akkor a úthossz maximális értékű, a ütemezés pedig minimális értékű, azaz az út és az ütemezés optimális.

Bizonyítás.

Legyen a szóbanforgó út és az ütemezés olyan, hogy .

Indirekte tegyük fel, hogy a út nem maximális, azaz létezik egy út, amelyre

Mivel a útra is igaz a lemma állítása, így

A fenti két összefüggés ellentmond egymásnak, így feltevésünk szerint nem létezik út, tehát a út maximális.

Most pedig indirekte tegyük fel, hogy az ütemezés nem minimális, azaz létezik egy ütemezés, amelyre

Mivel az ütemezésre is igaz a lemma állítása, így

Az utóbbi két összefüggés ellentmond egymásnak, tehát a feltevésünk hamis volt, azaz nem létezik ütemezésnél jobb, tehát az ütemezés optimális (minimális).

A soron következő második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (optimalitási kritérium):

A lemmában egyenlőség akkor és csak akkor áll fenn, ha a út minden élén

Bizonyítás.

Rendezzük át a lemma bizonyításában szereplő egyenlőtlenséget, ekkor a lemmabeli egyenlőség fennállásához azt kell megvizsgálnunk, hogy mikor lesz az alábbi összefüggés zérus

A duál feltétel szerint az összeg minden tagja nempozitív, így az összeg akkor és csak akkor lehet zérus, ha minden tagja zérus. Ez pedig azt jelenti, hogy a lemmabeli egyenlőség szükséges és elégséges feltétele, hogy minden útbeli élen .

TÉTEL:

A tervütemhálóban létezik olyan -ből -be vezető út és a feltételeket kielégítő ütemezés, hogy a lemmában egyenlőség áll fenn, azaz létezik maximális út és minimális ütemezés; a maximális úthossz (átfutási idő) és a minimális ütemezés (ütemezés értéke) egyenlő egymással, képletben:

Bizonyítás.

A bizonyítás konstruktív jellegű, az optimális megoldáspár (primál és duál) meghatározásának menetét (algoritmusát) is szolgáltatja. Két halmazt fogunk megkonstruálni.

A) Legyen egy halmaz a következőképpen megkonstruálva:

  • az S halmaz tartalmazza a kezdő eseményt, azaz ,

  • minden S-beli eseményhez vezessen kritikus út a kezdő eseményből.

Az S halmaz az események sorszámozása miatt legyen: , azaz az első k pont. Mint tudjuk a kritikus út mentén . Jelölje az S-beli pontokhoz tartozó eseményidőket .

Ha közelebbről megvizsgáljuk az eseményidőket, akkor azt tapasztaljuk, hogy az az idő, aminél korábban nem kezdhetők el az pontból kiinduló tevékenységek. Ezt az időt legkorábbi időnek nevezzük. Ennél az időnél azért nem kezdhetjük korábban a tevékenységeket, mert az ponthoz kritikus út vezet, ez pedig azt jelenti, hogy az pontba vezető valamelyik tevékenység éppen -ben fejeződött be.

Az S halmaz megkonstruálása után két eset adódhat:

  1. S = N, ez azt jelenti, hogy a t befejező eseményhez is vezet kritikus út, tehát optimális megoldáshoz jutottunk.

  2. , ekkor tekintsük a soron következő pontot. Ahhoz, hogy is S-be tartozzon, kritikus úton kell s-ből elérni, ehhez az eseményidőt az alábbiak szerint kell meghatározni:

    Tehát a maximumképzést azon élekre kell végezni, melyek végpontja . Meg kell nézni tehát, hogy mely élek vezetnek az pontba. Mivel az pontba már kritikus út vezet, így könnyen érthető, hogy a legnagyobb időértéket kell választani, hogy az pontba is kritikus út vezessen.

B) Legyen egy halmaz a következőképpen megkonstruálva:

  • a T halmaz tartalmazza a befejező eseményt, azaz ,

  • minden T-beli eseményből vezessen kritikus út a befejező eseménybe.

A T halmaz az események sorszámozása miatt legyen: , azaz az utolsó (n-m) pont. Mint tudjuk a kritikus út mentén . Jelölje a T-beli pontokhoz tartozó eseményidőket .

Ha közelebbről megvizsgáljuk az eseményidőket, akkor azt tapasztaljuk, hogy az az idő, aminél későbben nem fejezhetők be az pontba befutó tevékenységek. Ezt az időt legkésőbbi időnek nevezzük. Ennél az időnél azért nem fejezhetjük be későbben a tevékenységeket, mert az pontból kritikus út vezet t-be, ez pedig azt jelenti, hogy az pontból kiinduló tevékenységek közül valamelyik tevékenység éppen -ben kezdődik el.

A T halmaz megkonstruálása után két eset adódhat:

  1. T = N, ez azt jelenti, hogy az s kezdőeseményből is vezet kritikus út, tehát optimális megoldáshoz jutottunk.

  2. , ekkor tekintsük a soron következő pontot. Ahhoz, hogy is T-be tartozzon, kritikus úton kell tőle t-be jutni, ehhez az eseményidőt az alábbiak szerint kell meghatározni:

    Tehát a minimumképzést azon élekre kell végezni, melyek kezdőpontja . Meg kell nézni tehát, hogy mely élek indulnak ki az pontból. Mivel az pontból már kritikus út vezet t-be, így könnyen érthető, hogy a legkisebb időértéket kell választani, hogy az pontból is kritikus út vezessen.

Az legkorábbi idők meghatározásakor az kezdőértékkel, az legkésőbbi idők meghatározásakor pedig az kezdőértékekkel szokás dolgozni. Akár az S, akár a T halmazt konstruáljuk meg, mindig véges lépésben eljutunk az optimális megoldáshoz.

Ha rendelkezésünkre állnak az legkorábbi idők és az legkésőbbi idők, akkor az eseményidőkre mindig igaz, hogy

Azokat az eseményeket, amelyekre

kritikus eseményeknek nevezzük. A kritikus utat a kritikus eseményeket összekötő tevékenységek alkotják. A kritikus út tevékenységeit kritikus tevékenységeknek nevezzük.

Egy munkafolyamat kivitelezésének megtervezéséhez és irányításához a fentieken kívül ismerni kell a tevékenységek ütemezését is. Ezt az eseményidőkből egyszerűen számolhatjuk az alábbiak szerint:

  1. A tevékenység legkorábbi kezdési időpontja:

    Egy (x,y) tevékenység legkorábban az x esemény legkorábbi idejében kezdődhet az eseményidő definíciója miatt. Tehát az (x,y) tevékenység legkorábbi kezdési időpontja: .

  2. A tevékenység legkorábbi befejezési időpontja:

    Egy (x,y) tevékenység legkorábban akkor befejeződhet be, ha legkorábban lett elkezdve. Tehát a legkorábbi időhöz még hozzá kell adni a tevékenység idejét. Tehát az (x,y) tevékenység legkorábbi befejezési időpontja: .

  3. A tevékenység legkésőbbi befejezési időpontja:

    Egy (x,y) tevékenység legkésőbben az y esemény legkésőbbi idejében fejeződhet be az eseményidő definíciója miatt. Tehát az (x,y) tevékenység legkésőbbi befejezési időpontja: .

  4. A tevékenység legkésőbbi kezdési időpontja:

    Egy (x,y) tevékenység legkésőbben akkor kezdődhet, ha legkésőbb lett befejezve. Tehát a legkésőbbi időből még le kell vonni a tevékenység idejét. Tehát az (x,y) tevékenység legkésőbbi kezdési időpontja: .

Nyilvánvaló, hogy a kritikus tevékenységeknél a legkorábbi és a legkésőbbi kezdési (vagy befejezési) időpontok megegyeznek. A többi tevékenység legkorábbi és legkésőbbi kezdési (vagy befejezési) időpontjai eltérőek, tehát ezek tartalékidővel (lebegésseI) rendelkeznek. Az alábbiakban a tartalékidőket ismertetjük:

  1. Teljes (összes) tartalékidő:

    A legkedvezőbb körülmények között számított érték, azaz, ha az (x,y) tevékenység legkorábban kezdődhet és legkésőbben fejeződhet be, képletben:

  2. Szabad tartalékidő:

    Ha a tevékenység legkorábban kezdődhet és legkorábban fejeződhet be, képletben:

  3. Független tartalékidő:

    A legkedvezőtlenebb feltételek mellett számított érték, azaz ha az (x,y) tevékenység legkésőbb kezdődhet és legkorábban fejeződhet be, képletben:

    Ha a független tartalékidő pozitív, akkor ez a tartalékidő más tevékenységek lebegésétől függetlenül felhasználható. Ha negatív, akkor nincs független időtartalék, ezért zérusnak vesszük.

4.3. Algortimus az időtervezési feladatra

A számításokat a tervütemháló táblázatán szokás elvégezni. Ezt a táblázatot kiegészítjük egy oszloppal, ide fogjuk számítani az események legkorábbi idejét, továbbá kiegészítjük egy sorral, ahová az események legkésőbbi idejét fogjuk számolni. Ha az események sorszámozása olyan, hogy nagyobb sorszámú pontba vezet az él, akkor ez a táblázat ún. felső háromszög-táblázat lesz. A számolás a tétel bizonyításában adott összefüggések alapján történik.

  1. Az legkorábbi eseményidők számolása:

    Kiindulásként . Ezután a pontok sorrendjében számítjuk az értékeket.

    Az x pont értékét úgy határozzuk meg, hogy az értékek oszlopában (utolsó oszlop) és az x pont oszlopában levő számokat összeadjuk minden sorban és ezen összegek közül a maximumot vesszük.

  2. Az legkésőbbi eseményidők számolása:

    Kiindulásként . Ezután a pontok sorrendjében visszafelé haladva számítjuk az értékeket. Az x pont értékét úgy határozzuk meg, hogy az értékek sorában (utolsó sor) lévő elemből kivonjuk az x pont sorában levő elemet minden oszlopban és ezen különbségek közül a minimumot vesszük.

Megjegyzés:

Az időtervezési feladat megoldási módszerét kritikus út módszernek is szokás nevezni, ebből származik az időtervezési feladat CPM/time elnevezés is (Critical Path Method). Az időtervezési modelleket az 1950-es évek első felében dolgozták ki a RAND Corporation-nál. Ezeket a módszereket azonban titkosan kezelték, kezdetben nem hozták nyilvánoságra, FORD L.R. Jr. [4] és MINTY G.J. [11] munkáiban lettek nyivánosságra hozva.

4.4. Példamegoldás

Az algoritmus illusztrálására oldjuk meg a bevezetőben közölt feladatot.

Eredmények:

  1. Először az eseményidőket (ütemezést) adjuk meg, ezeket a táblázatból egyszerűen kiolvasunk, ha nem egyezik az esemény kétféle ideje, akkor az eseményidő a két érték közötti bármely érték lehet:

    Az ütemezés értéke: = 25.

  2. Kritikus út: 1

    Átfutási idő (kritikus út hossza) = 25

  3. Tevékenységidők és tartalékidők

4.5. Feladatok

  1. Adott a következő tevékenységsorozat:

    a) Rajzolja fel a tervütemhálót!

    b) Határozza meg az átfutási időt, a tevékenységekre vonatkozó időket és a tartalékidőket!

  2. Adott az alábbi tevékenységsorozat:

    a) Rajzolja fel a tervütemhálót!

    b) Határozza meg a kritikus utat, az átfutási időt és az ütemezést!

    c) Határozza meg a tevékenységekre vonatkozó időket és a tartalékidőket!

  3. Motort akarunk betonlapra felszerelni. Először betonágyat készítünk, hogy a közben legyártott fémalapot ide elhelyezhessük. Mire a betonágy és a fémalap elkészül, a motort a helyszínre szállítják és végül felszereljük. A részletes tevékenységek ill. tevékenységidők a következők:

    a) Rajzolja fel a tervütemhálót!

    b) Határozza meg a kritikus utat, az átfutási időt, a tevékenységekre vonatkozó időket és a tartalékidőket!

  4. Adott egy speciális hálózat távolságokkal. Határozza meg az 1 és az 5 jelű pontokat összekötő utak közül azt, amelynek hossza a legnagyobb!

    Útmutatás a megoldáshoz:

    Mivel a hálózat gráfja tervütemháló, így CPM-eljárással lehet megoldani a feladatot.

  5. Adott egy tervütemháló. Sorszámozza át a pontokat úgy, hogy minden pontból csak nagyobb sorszámú pontba vezessen éli. Gondolja végig az átsorszámozási eljárást és ez alapján adja meg az algoritmust, amelyet már számítógépre lehet programozni.

4.6. Időtervezési feladat (PERT)

Ha a tevékenységidők nem meghatározott (nem determinisztikus) értékek, hanem véletlentől függő, sztochasztikus változók, akkor az ún. PERT időtervezésről beszélünk. A gyakorlatban az alábbi három értékkel adjuk meg a tevékenységidő becslését. Minden (x,y) tevékenységhez megadjuk az , és a értékeket, amelyek a következő jelentéssel bírnak:

: a tevékenységidő optimista becslése,

: a tevékenységidő legvalószínűbb értéke,

: a tevékenységidő pesszimista becslése.

Az optimista becslés a bizonytalanságot okozó akadályokat nem veszi figyelembe, a pesszimista becslés minden lehetséges akadály fellépését számba veszi. A tevékenységidők eloszlása általában béta-eloszlásnak tekinthető. Egyrészt a béta-eloszlás várható értéke és szórása nehezen határozható meg, másrészt a gyakorlatban az értékek könnyen meghatározhatók, ezért a tevékenységidők várható értékét az

képlettel, az szórását pedig az

képlettel szokták becsülni.

Az időtervezés ezután a tevékenységidő várható értékével történik a már megismert CPM módszerrel. Az események idejére is és az átfutási időre is várható értékeket kapunk, amely körül a valóságos értékek ingadoznak. Bizonyos feltevésekkel az átfutási idő várható értékének az ingadozása, azaz a szórása is meghatározható. Az átfutási idő az tevékenységidők összege. A matematikai statisztikából ismert, hogy független változók összegének szórásnégyzete egyenlő a változók szórásnégyzetének összegével. Ha a tevékeységidők egymástól függetlenek, akkor az átfutási idő szórásnégyzetét a kritikus úton lévő tevékenységek szórásnégyzetének összegeként számíthatjuk ki. Ha a tervütemháló elég sok pontból áll, ill. a kritikus út sok eseményen vezet végig, akkor a központi határeloszlástétel alapján az átfutási idő közelítőleg normális eloszlást mutat. Ebben az esetben a normális eloszlás eloszlásfüggvényének segítségével választ kaphatunk olyan kérdésekre is, hogy mi a valószínűsége annak, hogy az átfutási idő egy adott értéken belül, kívül esetleg a kettő között marad?

Feladat:

Az alábbi PERT tervütemhálónál a tevékenységek időbecsléseiből határozza meg az átfutási idő várható értékét és szórását!

5. fejezet - Maximális folyam - minimális vágás feladatpár

Mint ahogy az előző fejezetekben is láttuk a hálózatokon többféle optimalizálási feladatot értelmezhetünk. A következő fejezetekben az ún. folyamproblémákkal fogunk foglalkozni, látni fogjuk, hogy ezek szorosan kapcsolódnak a vágással. Ezek a feladatok olyan lineáris programozási feladatok, amelyek speciális szerkezetüknél fogva sok hasznos tulajdonsággal rendelkeznek és egészértékű optimális megoldásuk van. Számos érdekes és a gyakorlatban fontos kombinatorikai feladat is megfogalmazható és megoldható folyamfeladatként. Némely esetben kevéssé kézenfekvő a kapcsolat a folyamok fizikai valóságával. Ebben a fejezetben a folyamproblémák standard modelljét a maximális folyam-minimális vágás feladatpárt és e feladatpárra vonatkozó ismereteket közöljük. A további fejezetekben röviden vázolunk további folyam modelleket is. A folyamfeladatokat követő fejezetek modelljeinek alapját is a maximális folyam - minimális vágás feladatpár fogja alkotni.

5.1. A feladatpár megfogalmazása

Legyen adott egy hálózat. A hálózat éleihez rendelt nemnegatív számot az él kapacitásának nevezzük. Ezt a kapacitást különbözőképpen foghatjuk fel attól függően, hogy milyen konkrét problémát fogalmazunk meg: valamely termékből egységnyi idő alatt legfeljebb mennyi tud az útszakaszon folyamatosan áthaladni vagy elektromos hálózat esetén a vezetékeken átfolyó áram maximális erőssége, stb. Legyen két pont kitüntetve, az egyik a forrás, amelyet jelöljünk -el, másik a nyelő, jele legyen . A folyamproblémát nagyon vázlatosan úgy fogalmazhatjuk meg, hogy keressük a forrásból a nyelőbe vezető maximális mennyiségű folyamot. Jelölje az élen átmenő folyam nagyságát. Általánosan folyamról beszélünk, amely egy konkrét feladat kapcsán lehet termékmennyiség, áramerősség, stb. A folyam a forrásból ered, a nyelőben elnyelődik és a hálózat éleire a kapacitáskorlátozásnak, a pontjaira pedig Kirchoff csomóponti törvényének kell teljesedni. Az utóbbi feltételt megmaradási szabályként is említhetnénk, amely azt fejezi ki, hogy a hálózat mindegyik közbülső (forrástól és nyelőtől különböző) pontjára érvényes, hogy egy adott pontba befolyó folyamok értéke azonos az onnan kifolyó folyamok értékével. Egy adott pontból kifolyó folyam mennyiségét az pontbeli folyamértéknek nevezzük és a összegzéssel írhatjuk le. Hasonlóan írható le a befolyó folyam is. A forráspontból kifolyó mennyiséget pedig a folyam értékének nevezzük. Ezekután a folyamprobléma matematikai megfogalmazása a következő:

Meghatározandó a hálózat minden élére az folyam úgy, hogy a

mennyiség maximális legyen feltéve, hogy

A folyamprobléma tehát a forrásból a nyelőbe irányuló legnagyobb értékű folyam meghatározása. A célfüggvényt a forrásból kifolyó folyam mennyiségeként fogalmaztuk meg, de nyilvánvalóan használhattuk volna a megmaradási törvény miatt a nyelőbe befolyó folyam mennyiséget is. Általában folyam alatt a feltételeknek eleget tevő értékek összességét értjük, de nem követünk el nagy hibát, ha az egyes éleken értelmezett értékeket (folyamkomponenseket) is egyszerűen folyamnak nevezzük. A legnagyobb értékű folyamot maximális folyamnak nevezzük.

Példa a folyamfeladat matematikai megfogalmazására:

Tekintsük az alábbi ábrán látható hálózatot és fogalmazzuk meg az 1-ből a 6-ba irányuló maximális folyam feladatot matematikai formában!

Maximális folyam feladat (Primál feladat)

Legyenek a feladat döntési változói az értékek, amelyek az i pontból a j pontba mutató élen a folyam mennyiségét jelentik. Ezek darabszáma a hálózat éleinek számával azonos, a feladat döntési változói tehát rendre:

A döntési változókra vonatkozó kapacitáskorlátozás azt írja elő, hogy a folyam egyik élen sem lehet negatív és nem lehet nagyobb, mint az él kapacitása, ezek a feltételek a következők:

A közbülső pontokra (nem forrás, nem nyelő) érvényesnek kell lenni a Kirchoff csomóponti törvényének, azaz minden közbülső pontból a kifelé mutató élen a folyamok összegének azonosnak kell lenni a pontba befelé mutató élen lévő folyamok összegével. Négy közbülső pont van, ezekre a feltételek rendre a következők:

A célfüggvény pedig a forráspontból kifolyó folyamok összege, azaz

Mint ahogy látható a folyamprobléma is egy lineáris programozási feladat, amelyet szimplex módszerrel meg tudunk oldani. A megoldáshoz célszerű az egyedi felsőkorlátos szimplex módszert használni, de még így is elég nagyméretű feladatot kell megoldani. A folyamprobléma minden feltételében és a célfüggvényben is 0 és 1 együtthatók szerepelnek, ez a speciális szerkezet indokolja, hogy a hálózaton működő megoldási módszert alkalmazzunk. A folyamproblémának, mint lineáris programozási feladatnak létezik a duál feladata is. A következőkben ezt határozzuk meg. A fenti primál lineáris programozási feladatnak felírjuk a duál feladatát és egy kis transzformáció után azt fogjuk tapasztalni, hogy a duál feladat a vágással hozható kapcsolatba.

A duál feladat egyszerűbb meghatározásához alakítsuk át a folyamfeladatot oly módon, hogy bevezetünk egy v-vel jelölt új változót, amely a folyam értékét jelentse. A feltételek közé vegyük fel a forrásra és a nyelőre vonatkozó előírásokat is, a célfüggvény pedig legyen a v folyamérték, amelynek maximumát keressük. A v változóra elvben nincs előjel megkötés, tudjuk ugyan, hogy a folyam nemnegativitása miatt szükségképpen pozitív, de ezt az előírást nem szerepeltetjük a modellben, mert nem előírás, hanem következmény. A feladat alakja a következő:

A fenti lineáris programozási feladat duál változói legyenek a következők:

A hálózat pontjaira vonatkozó egyenlőséges feltételekhez rendelt duál változók legyenek: .

A hálózat éleire vonatkozó kapacitáskorlátos egyenlőtlenséges feltételekhez rendelt duál változók legyenek: .

Ekkor a duál feladat a következő formában írható fel:

Ennek a duál feladatnak minden lehetséges megoldása és az optimális megoldása is megfeleltethető egy (S,T) vágásnak a következő módon. Legyen

Érdemes megfigyelni az átalakított folyamfeladatban a hálózat pontjaira felírt egyenleteket. Az ismeretlenek együtthatóiból képzett mátrix nem más mint a hálózat alapját képező digráf szomszédossági mátrixa. Az egyenlőséges feltételek mátrixos formában tehát így is írhatók:

ahol S a szomszédossági mátrix, az egységvektorok, az x pedig a döntési változókat magába foglaló vektor.

Ezekután a folyamfeladat duál feladata általánosan a következőképpen fogalmazható meg.

A folyamprobléma duál feladata:

Meghatározandó a forrást (s) a nyelőtől (t) elválasztó vágások közül az, amelyben a vágásbeli élekre írt kapacitás értékek összege, azaz a

mennyiség minimális.

A mennyiséget általánosan az vágás kapacitásának vagy a vágás átbocsátóképességének nevezzünk. A legkisebb átbocsátóképességű vágást egyszerűen minimális vágásnak nevezzük. A két szorosan összekapcsolódó feladat (primál – duál) együttesét maximális folyam-minimális vágás feladatpár néven szoktuk emlegetni.

Mielőtt rátérnénk a feladatok matematikai vizsgálatára, röviden szólunk a folyamfeladat megoldásáról. Egy nagyon kézenfekvőnek tűnő algoritmus lehet a következő: Legyen adott egy megengedett folyam, amely lehet az azonosan zérus is. Meghatározzuk minden élen, hogy mekkora az él szabad kapacitása. Egy él szabad kapacitása () alatt az élen még átfolyatható mennyiséget, azaz az mennyiséget értjük. Ha egy él szabad kapacitása zérus, akkor azt az élet telített élnek, ha pedig szabad kapacitása pozitív, akkor azt az élet telítetlen élnek nevezzük. Tekintsük csak a telítetlen éleket és csak ezeken a telítetlen éleken keressünk utat a forrásból a nyelőbe. Ha találtunk utat, akkor ezen út minden élén az élre előírt kapacitáskorlátozás miatt az él szabad kapacitásának megfelelő mértékben a folyam növelhető. Az út minden élén azonban csak egyforma mértékben növelhetjük a folyamot, mert egyébként az új folyam megsértené a csomóponti törvényt. Könnyen belátható, hogy az út szűk keresztmetszete dönti el a növelés maximális mértékét. Tehát meghatározzuk az út mentén a legkisebb szabad kapacitást, amelynél nagyobb mértékben nem javítható a folyam. Mivel a maximális folyam elérése a fő célunk, ezért ezzel a legkisebb szabad kapacitással érdemes növelni a folyamot. Jelöljük ezt a szabad kapacitást -val. A folyamnövelés után az eljárásunkat megismételjük. Tehát az algoritmus egy-egy lépésében három feladatot kell kell elvégeznünk:

  1. Útkeresés s-ből t-be a telítetlen éleken.

  2. Az út mentén a legkisebb szabad kapacitás () meghatározása.

  3. A legkisebb szabad kapacitással az út minden élén növeljük a folyamot.

A gyakorlati kivitelezés során nem érdemes az új folyamot kiszámítani, mivel az (1) és a ( 2) feladatban csupán a szabad kapacitás ismerete szükséges, így a (3) feladatban a folyamnövelés helyett a szabad kapacitásokat csökkentjük az út mentén. Akkor fejezzük be az algoritmust, ha már nem találunk utat. Az elmondottakra nézzünk egy példát. A példával az algoritmusra szeretnénk rámutatni, ezért az útkeresést most nem címkézéssel oldjuk meg.

Példa a kézenfekvő algoritmus bemutatására:

Tekintsük az alábbi hálózatot! Határozzuk meg az s-ből t-be irányuló maximális folyamot!

A probléma egyszerűsége miatt azonnal látható, hogy a maximális folyam értéke 7. Nézzük a megoldást lépésenként. A hálózat szabad kapacitásait a baloldali ábrán (a telített éleket szaggatottan jelöljük), az utat és az út mentén a folyamnövelés mértékét a jobb oldali ábrán tüntetjük fel. Induljunk ki az azonosan zérus folyamból. Ekkor az élek szabad kapacitása megegyezik az él kapacitásával.

1. útkeresés

2. útkeresés

3. útkeresés

4. útkeresés

A 4. útkeresés során nem tudtunk telítetlen éleken a forrásból a nyelőbe eljutni, így az algoritmus befejeződött. Az élek kapacitásának és szabad kapacitásának a különbsége a folyamot adja, amelyet az alábbi hálózaton szemléltetünk.

A fenti hálózatból kiolvasható, hogy a forrásból a nyelőbe vezető folyam értéke 6. E példán tapasztaltuk, hogy a kézenfekvő algoritmusunk nem jól működik, mert maximális folyamra a 7-et kellett volna eredményezni. Ha az útkeresések során először a felső két él által, utána pedig az alsó két él által meghatározott utat találjuk meg, akkor az algoritmus jól működik. Hol lehet a hiba az algoritmusban, amely egyszer működik, egyszer nem? A nem megfelelő működés az algoritmus merevségében van, ugyanis egy élen a folyamot csak növelni tudjuk. Amennyiben lehetőséget adtunk volna arra, hogy ha egy élen már átfolyattunk valamennyit, akkor szükség esetén legfeljebb ennyit vissza is folyathatunk, úgy az algoritmus minden esetben jól működik. Ahhoz, hogy a fenti algoritmust minden esetben sikerrel tudjuk alkalmazni az eredeti folyamfeladatot módosítani kell, természetesen az alapprobléma érintése nélkül.

A folyamprobléma módosítása az alábbiak szerint történik. Egészítsük ki a hálózatot teljes hálózattá. Az eredetileg nem létező éleket is vegyük fel és azok kapacitását zérusnak vegyük. A teljes hálózat élein az folyamra a nemnegativitást elvetjük, helyette a ferdeszimmetricitást írjuk elő, amely az alábbit jelenti:

Ez a matematikai előírás fogja megoldani a gondunkat. Hogy jobban megértsük, számítsuk ki a szabad kapacitásokat. Az élen , a élen pedig . A folyam ferdeszimmetricitása miatt azonban . Tehát ha egy élen a folyam nő, pl. -ről megváltozik -ra, akkor az élen a szabad kapacitás -val csökken. A „visszélen” pedig ugyanannyival, -val nő. Ez fordítva is igaz. A negatív folyam természetesen az optimális megoldásban nem fog érdekelni bennünket, csak a pozitív folyamok lesznek számunkra érdekesek. A módosított folyamra vonatkozó csomóponti törvény a ferdeszimmetricitás miatt úgy fogalmazható meg, hogy a közbülső pontokban a kilépő (vagy belépő) folyamok előjeles összege zérus legyen. A folyam értékét a továbbiakban jelöljük -el, amelynek értéke: . Matematikai értelemben folyamfeladat alatt a továbbiakban mindig e módosított folyamfeladatot értjük, amelynek matematikai megfogalmazása a következő:

Meghatározandó a teljes hálózat minden élére az folyam úgy, hogy

maximális legyen, feltéve, hogy

Nem nehéz kitalálni, hogy a duál feladat változatlan marad, csupán a teljes hálózatra vonatkozóan kell a minimális vágást keresni.

Mielőtt belekezdenénk a vizsgálatokba, bevezetünk néhány jelölést .

Legyen részhalmazok és az éleken értelmezett függvény (folyam esetén: vagy kapacitás esetén: ), továbbá jelölje az alábbi mennyiséget:

Könnyen ellenőrizhető, hogy fennállnak az alábbi addíciós összefüggések:

Ezen addíciós összefüggések figyelembevételével a folyamfeladatra felírt korlátozottsági előírások az

alakban, míg a ferdeszimmetricitási előírások az

alakban írhatók. A folyamfeladat megfogalmazására a fenti jelölésmód természetes, ugyanis az értéke a B ponthalmaz pontjaiból a C ponthalmaz pontjaiba irányuló folyam értékét, a értéke pedig a B ponthalmaz pontjaiból a C ponthalmaz pontjaiba irányuló élek teljes átbocsátóképessége.

A fentebb bevezetett jelölések alapján legyen:

amelyet az pontból kilépő folyamok összegének nevezünk. Az pont a folyamra nézve akkor forrás, ha , a pont pedig akkor nyelő, ha .

Az teljes hálózat egy folyamát s-ből t-be irányuló folyamnak nevezzük, ha , és minden (közbülső pont) esetén . Szemléletesen nyilvánvaló, de algebrailag is könnyen igazolható, hogy az s-ből t-be irányuló folyam esetén

az feltételből ugyanis levezethető, hogy

ebből pedig

Az hálózat s-ből t-be irányuló folyamánál az számot a folyam értékének nevezzük. A legnagyobb értékű folyamot maximális folyamnak nevezzük.

Ezekután a maximális folyam feladat a következő módon fogalmazható meg matematikai formában.

Maximális folyam feladat (primál feladat):

Meghatározandó a teljes hálózaton az s-ből t-be irányuló folyam úgy, hogy a folyam értéke az

maximális legyen, feltéve, hogy

Minimális vágás feladat (duál feladat):

Meghatározandó az s-et t-től elválasztó vágás úgy, hogy a vágás átbocsátó képessége a

minimális legyen.

5.2. A feladatpár matematikai vizsgálata

A folyam és a vágás közötti alapvető összefüggést a következő lemmában mondjuk ki:

LEMMA (A folyamprobléma alaplemmája):

A feltételeket kielégítő tetszőleges, s-ből t-be irányuló folyam (megengedett folyam) és tetszőleges, s-et t-től elválasztó vágás esetén a folyam értéke nem lehet nagyobb, mint a vágás átbocsátóképessége, azaz képletben

Bizonyítás.

Felhasználva a közbülső pontokra vonatkozó összefüggést és az addíciós összefüggéseket, egyszerűen adódik, hogy

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha a megengedett folyam és a vágás olyan, hogy a lemmában egyenlőség áll fenn, akkor a folyam maximális a vágás pedig minimális.

Bizonyítás.

Legyen a szóbanforgó folyam , a vágás pedig , amelyre . Indirekte tegyük fel, hogy az nem maximális, azaz létezik egy megengedett folyam, amelyre

Mivel az folyamra is igaz a lemma állítása, így

A fenti két összefüggés ellentmond egymásnak, így feltevésünk szerint nem létezik folyam, tehát az folyam maximális.

A vágás oldaláról történő bizonyítás hasonló módon végezhető, amelyet az olvasóra bízunk.

A második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (optimalitási kritérium):

A lemmában egyenlőség akkor és csak akkor áll fenn, ha az vágás minden élén

Bizonyítás.

A lemma bizonyításának utolsó lépése szerint

amely részletezve

és ebben az összefüggésben egyenlőség akkor és csak akkor állhat fenn, ha az egyenlőtlenség mindkét oldalán az összegben lévő megfelelő tagok megegyeznek, azaz minden vágásbeli élen .

FORD-FULKERSON tétel (a folyamprobléma főtétele):

Létezik olyan megengedett folyam és vágás, hogy a lemmában egyenlőség áll fenn, azaz lézezik -ből -be irányuló maximális folyam és -et -től elválasztó minimális vágás, továbbá a maximális folyam értéke egyenlő a minimális vágás átbocsátóképességével, azaz képletben

A folyamprobléma főtételét L. R. FORD és D. R. FULKERSON adták meg 1962-ben [5]. A FORD-FULKERSON néven ismertté vált jelentős tételt a további modelljeinkben is fel fogjuk használni.

Bizonyítás.

A tételre konstruktív bizonyítást adunk, amelyből a megoldás menete is kiolvasható.

Legyen egy tetszőleges s-ből t-be irányuló folyam. Konstruáljuk meg azt a digráfot, amelynek E élhalmazán . Az ilyen éleket telítetlen éleknek nevezzük, mivel még rajtuk növelhető a folyam. Az olyan éleket, amelyekben telített éleknek nevezzük. Keressünk az digráfban utat s-ből t-be. A MINTY tétel értelmében két eset állhat fenn:

1. eset: nincs út

MINTY tétel szerint ekkor van üres vágás. Ez pedig azt jelenti, hogy ebben a vágásban nincs telítetlen él. A hálózatra vonatkozóan pedig ebben a vágásban csak telített élek vannak, a lemma két következménye értelmében a folyam is és a vágás is optimális.

2. eset: van út

A hálózatban ennek a P útnak minden éle telítetlen, azaz rendelkezik szabad kapacitással. Ezt az utat folyamnövelő útnak nevezzük, hiszen minden élén valamennyivel növelhető a folyam.

Határozzuk meg az út mentén lévő élekre a szabad kapacitások minimumát, jelölje ezt az értéket , azaz legyen

A értéket az út kapacitásának nevezzük. Az út mindegyik élén ugyanannyivel kell növelni a folyamot a Kirchoff törvény miatt. Maximálisan tehát a értékkel növelhető a folyam az út mentén. Természetesen ennél kevesebbel is növelhető a folyam. Mivel a folyamfeladat célja a maximális folyam átáramoltatása, célszerű ezzel a maximális mennyiséggel növelni a folyamot. Egyébként, ha nem ezt tennénk, akkor a következő útkeresés során is ugyanezt az utat találnánk meg, hisz mindegyik útbeli élen lenne szabad kapacitás. Ezzel a növeléssel az út mentén bizonyos élek telítetté válnak. A folyamot tehát az út mentén a növeljük, a folyamfüggvény ferdeszimmetricitása miatt a „visszút” mentén ugyanennyivel csökkenteni kell. Az új folyam a következőképpen határozható meg:

Az új folyam értéke , azaz a folyam értéke nő. Az új folyam megengedett marad, hiszen teljesíti a folyamra vonatkozó összes feltételt. Az új folyamra megismételjük a fentebb leírt eljárást. Mivel az alapadatok miatt egész szám és a lemma miatt felülről korlátos, így véges lépésben eljutunk az optimális megoldáshoz, azaz az 1. esethez.

A FORD-FULKERSON tétel bizonyításából tehát kiolvasható, hogy maximális folyam és minimális vágás esetén igaz, hogy a minimális vágásban minden élen a kapacitásnak megfelelő folyam folyik, azaz a minimális vágásra az jellemző, hogy minden éle telített.

5.3. Algoritmus a maximális folyam-minimális vágás feladatpár megoldására

A FORD-FULKERSON tétel bizonyításából, a bizonyítás konstruktív jellege miatt kiolvasható az optimális megoldás megkeresésére szolgáló algoritmust. Ezt az algoritmust a működése miatt növelő út módszernek is nevezhetjük.

  1. A hálózat kiegészítése teljes hálózattá, zérus kapacitású élekkel.

  2. Az induló folyam meghatározása. Amennyiben van induló folyam vagy könnyen találunk ilyet, akkor célszerű abból kiindulni. Legtöbbször azonban az azonosan zérus folyamból indulunk ki, azaz minden élen.

  3. Az induló folyamhoz az éleken az induló szabad kapacitás () meghatározása.

  4. Útkeresés s-ből t-be a telítetlen, azaz éleken (címkézéssel keressük az utat a szabad kapacitású táblázaton, a címkézés során csak a pozitív szabad kapacitásokat kell figyelni).

    Ha nincs út, akkor megállunk, megtaláltuk az optimális megoldáspárt. A minimális vágás a megtalált üres vágás lesz, a maximális folyam pedig a kapacitás és a szabad kapacitás különbsége.

    Ha van út, akkor az (5) ponton folytatjuk az eljárást.

  5. Az út kapacitásának a meghatározása (). Ezt az út mentén a legkisebb szabad kapacitás értéke adja.

  6. Az út kapacitásával az út minden élén növeljük a folyamot. A ferdeszimmetricitás (a visszaáramoltatás biztosítása) miatt a visszút minden élén pedig csökkentjük a folyamot. Gyakorlatban azonban az élekre nem a folyamot, hanem az útkereséshez amúgy is szükséges szabad kapacitást () számítjuk. A szabad kapacitást az út mentén csökkentjük, a visszút mentén pedig növeljük.

5.4. Példamegoldás

Az algoritmus működésének bemutatására 2 számpéldát oldunk meg.

1. példa

Tekintsük mégegyszer a fejezet elején vázolt hálózatot és az ott megfogalmazottak szerint határozzuk meg a hálózaton az 1-ből a 6-ba irányuló maximális folyamot és az 1-et a 6-tól elválasztó minimális vágást! Most a megoldási algoritmust mutatjuk be, az előzőekben csupán a feladat matematikai megfogalmazását adtuk meg.

Először a hálózatot teljes hálózattá egészítjük ki. Induló folyamként a zérus folyamot választjuk. Ebben az esetben az élek szabad kapacitása a kapacitással azonos. Javasoljuk az olvasónak, hogy válasszon zérustól különböző induló folyamot és ezzel indulva is oldja meg a feladatot. A mindenkori szabad kapacitásokon történő útkereséseket az alábbiak mutatják:

1. útkeresés:

Az útkeresés során találtunk utat, amely az alábbi:

Ez az út folyamnövelő út, hiszen minden élén valamennyivel növelhető a folyam. Az úton az s-ből t-be maximálisan 3 mennyiségű folyam áramoltatható át a kapacitáskorlátok miatt. Az út kapacitása tehát az útbeli élek szabad kapacitásainak minimumaként adódik, azaz . Az út mindegyik élén ugyanannyivel kell növelni a folyamot a Kirchoff törvény miatt.

Javasoljuk, hogy a továbbiakban az út leírása helyett az út éleit (az út definiálása során már említett módon) a táblázatban szimbólummal jelöljük és ekkor az út kapacitása a szimbólummal jelölt számok minimumaként határozható meg, azaz = min{ }. A visszút éleit pedig jelöljük szimbólummal. Ezt mutatja az alábbi táblázat.

A táblázatban az élek ill. visszélek bejelölése esetén a szabad kapacitások módosítását az alábbiak szerint végezhetjük el:

  • a szimbólummal jelölt élen -val csökkentjük a szabad kapacitást,

  • a szimbólummal jelölt élen -val növeljük a szabad kapacitást.

2. útkeresés:

.

3. útkeresés:

.

4. útkeresés:

Vége az algoritmusnak, mert nem találtunk folyamnövelő utat. A táblázatból a maximális folyam és a minimális vágás feladatpár optimális megoldása az alábbiak szerint adódik.

A maximális folyamfeladat megoldása:

Az élekre adódó optimális mennyiségeket az eredeti kapacitástáblázat és az utolsó szabad kapacitás táblázat, mint mátrix különbsége adja.

A folyam maximális értékét többféle módon is kiolvashatjuk a táblázatból. Egyrészt a forrásból kifolyó folyamok összegeként, amelyet úgy kapunk, hogy a forrásnak megfelelő sorban lévő elemeket összeadjuk.

A folyam maximális értéke: .

Ugyanezt az eredmény kapjuk, ha a nyelőbe (t) befolyó folyamok összegét számoljuk, amelynél a nyelőnek megfelelő oszlopban lévő elemeket kell összeadni. Ha a forrásnak (s) megfelelő oszlopban ill. a nyelőnek megfelelő sorban lévő elemeket adjuk össze, akkor a folyam maximális értékének a (-1)-szeresét kapjuk. Ha a zérus folyamból indulunk ki, akkor az útkeresések során nyert folyamnövelő értékek összege is a folyam maximális értékét adja. Könnyen meggyőződhetünk arról, hogy a folyam valóban teljesíti a korlátozottsági, a ferde szimmetricitási feltételeket és a csomóponti megmaradási törvényt. Ez utóbbi akkor teljesedik, ha a közbülső (forrást és nyelőt kivéve) pontoknak megfelelő sorban és oszlopban lévő elemek összege zérus. Tekintsük például az 5 pontot és annak sorát. A sor pozitív számai azt mutatják, hogy az 5 pontból az és az éleken van kifolyás 1 ill. 2 mennyiségben, tehát összesen 3 mennyiségű folyam folyik ki az 5 pontból. A sor negatív értéke az , a ferdeszimmetricitás miatt , ez pedig az 5 pontba befolyó folyamot jelenti. Valóban igaz, hogy az 5 közbülső pontba befolyó és onnan kifolyó folyamösszegek megegyeznek.

A minimális vágás feladat megoldása:

Az utolsó címkézés során adódott vágás a minimális vágás. Az vágás ponthalmazai:

,

.

Mint ismert a címkézett pontok az ponthalmazt, a címkézetlen pontok pedig a ponthalmazt alkotják.

Az minimális vágás élei: .

Az minimális vágás átbocsátóképessége, vagyis a minimális értéke: .

Az vágás éleit a kapacitás táblázat lefedésével is ábrázolhatjuk. A értéke a fedetlen helyek kapacitásainak összegeként adódik.

Az s-ből -be irányuló folyam maximális értéke és az s-et t-től elválasztó vágás minimális átbocsátóképessége valóban megegyezik, amelyet a FORD-FULKERSON tétel állított. A folyamprobléma és a vágás feladat optimális megoldását a hálózaton is szemléltethetjük. Az eredeti (nem teljessé alakított) hálózaton a feladatpár megoldása egyszerűen adódik, mivel csupán a pozitív értékű folyamokat kell tekinteni. Az alábbi hálózaton az élekre írt számok a folyamot jelentik.

Láthatjuk azt is, hogy optimális esetben a vágás minden éle telített.

2. Példa:

Adott az alábbi „honnan-hova” táblázattal egy hálózat és abban egy induló folyam. Határozza meg az 5 pontból a 2 pontba irányuló maximális folyamot!

0. lépés:

A kapacitás táblázata (baloldalon) és az induló folyam táblázata (jobboldalon) az eredeti hálózaton az alapadatok alapján a következő:

            

A hálózatot kiegészítjük teljes hálózattá. Az eredetileg nem létező élek kapacitása zérus lesz.

A folyamot is elő kell készíteni, mivel az ferdeszimmetrikus, így a visszafelé mutató éleken ellenkező előjelű lesz a folyam.

A teljes hálózaton a kapacitás és a folyam táblázata az alábbi:

            

1. lépés:

Először az induló szabad kapacitás () táblázatot kell meghatározni, amely , tehát a fenti balodali táblázat elemeiből ki kell vonni a jobboldali táblázat elemeit. Természetesen a fenti táblázatok felrajzolása nélkül sem bonyolult a szabad kapacitás táblázat előállítása, táblázatelemenként kitölthető egy kis odafigyeléssel. Ezután elkezdhetjük az útkeresések sorozatát.

2. lépés:

Nem találtunk növelő utat a forrásból a nyelőbe, így megkaptuk az optimális megoldást. A primál és a duál feladat optimális megoldását az alábbiakban adjuk meg:

A maximális folyamfeladat megoldása:

Az élekre adódó optimális mennyiségeket az eredeti kapacitástáblázat és az utolsó szabad kapacitás táblázat, mint mátrix különbsége adja.

A folyam maximális értéke: .

A minimális vágás feladat megoldása:

Az utolsó címkézés során adódott vágás a minimális vágás. Az vágás ponthalmazai:

,

.

A vágást lefedéssel is ábrázolhatjuk a kapacitás táblázaton.

Az minimális vágás átbocsátóképessége, vagyis a minimális értéke: 11. Ez nem más mint a fedetlen helyeken lévő kapacitások összege.

Javasoljuk az olvasónak gyakorlás érdekében, hogy az induló folyam figyelembevétele nélkül is oldja meg a feladatot.

Megjegyzések:

  1. Előfordulnak olyan folyamfeladatok is, amelyeknél a hálózat élein a folyamra nemcsak felső korlátok (), hanem alsó korlátok is szerepelnek, ekkor a korlátozási feltétel

    Az alábbiakban megmutatjuk, hogy egyszerűen visszavezethető a standard zérus alsó korlátos (nemnegatív) feladatra. Az döntési változó helyett vezessük be az új változót a következőképpen

    Ekkor az változóra a szokásos nemnegativitási feltétel teljesül és a korlátozás pedig az alábbi lesz:

    A célfüggvényben is és a közbülső pontokra felírt egyenleteknél is a transzformáció elvégzése után egy standard folyamfeladatot kell megoldani, amelynek optimális megoldásából egyszerűen számítható az eredeti folyamfeladat optimális megoldása.

  2. Előfordulnak olyan folyamfeladatok is, amelyeknél több forrás és nyelő van. Ekkor a folyamot úgy értelmezzük, hogy az összes forrásból az összes nyelőbe áramló folyam maximális értékét keressük.

    Az alábbiakban megmutatjuk, hogy egyszerűen visszavezethető a standard (egy forrással és egy nyelővel rendelkező) feladatra. Vegyünk fel a hálózatban egy s és egy t pontot és ezeket tekintsük forrásnak ill. nyelőnek. Az s pontból mindegyik eredeti forráshoz vegyünk fel élet végtelen kapacitással. A t pontba mindegyik eredeti nyelőből vegyünk fel élet végtelen kapacitással. Most ezen a módosított hálózaton keressük meg az s-ből t-be irányuló maximális folyamot. Ennél a feladatnál nyilván az eredeti források és a nyelők közbülső pontoknak tekintendők, amelyekre szintén érvényes Kirchoff csomóponti törvénye. Nem nehéz belátni, hogy az így nyert feladat optimális megoldása az eredeti feladatnak is optimális megoldása lesz.

5.5. Feladatok

  1. Határozza meg az alábbi „honnan-hova” táblázattal adott hálózaton

    a) az 1-ből a 8-ba irányuló maximális folyamot,

    b) a 3-ból az 5-be irányuló maximális folyamot,

    c) a 2-t a 7-től elválasztó minimális vágást,

    d) a 4-et a 3-tól elválasztó minimális vágást!

  2. A , pontok között naponként (vasúton, közúton stb.) szállítható anyag mennyiségét az alábbiakban adjuk meg : : 100, : 10, : 50, : 70, : 30, : 140, : 30, : 20. Számitsa ki a és a pontok között átáramoltatható napi szállítás maximális értékét és adja meg mely pontok képezik a szűk keresztmetszetet!

  3. Adott az alábbi „honnan-hova” táblázattal egy hálózat. Határozza meg a 3 és a 4 pontokat elválasztó vágást úgy, hogy a vágásbeli élek összhosszúsága minél kisebb legyen!

  4. Adott az alábbi "honnan-hova" táblázattal egy digráf. Határozza meg a 3-as és a 4-es pontokat elválasztó vágások közül azt, amelynél a vágásban lévő élek száma a legkevesebb!

  5. Adott egy városi úthálózat-részlet: , , , , , , útszakaszokkal, ahol útkereszteződéseket jelöl. A pont a város nyugati, a pont pedig a keleti részén van. Hogyan kell a és a pontok között É-D irányú utat tervezni, hogy az új út minél kevesebb helyen keresztezze a meglevő útszakaszokat?

    Útmutatás a 4. és az 5. feladathoz:

    A digráfot hálózattá kell alakítani egységnyi kapacitásokkal és utána minimális vágást kell meghatározni.

  6. Határozza meg az 1-ből a 7-be irányuló maximális folyamot és az 1-et a 7-től elválasztó minimális vágást!

  7. Adott az alábbi hálózat, amelyben keressük az 1-ből a 4-be irányuló maximális folyamot.

    a) Írja fel a maximális folyam feladatot matematikai formában és adja meg a feladat duálisát is!

    b) Oldja meg a feladatot szimplex módszerrel!

    c) Oldja meg a feladatot duál módszerrel!

    d) Oldja meg a feladatot növelő út módszerrel!

6. fejezet - Csúcskapacitásos folyamfeladat

6.1. A feladat megfogalmazása

Tekintsünk egy olyan hálózatot, amelyben az élekre vonatkozó élkapacitásokon kívül a pontokra vonatkozó , egész értékű csúcskapacitások is adottak. A folyamfeladatot most úgy lehet megfogalmazni, hogy a csúcsokra vonatkozó megmaradási feltételeken és az élekre vonatkozó korlátozottsági megkötéseken kívül a csúcsokra kirótt megszorítások is teljesüljenek, azaz egyik közbülső pontban se haladja meg a kifolyó folyam (amely egyenlő a befolyó folyammal) a csúcs kapacitását. Az ilyen problémát csúcskapacitásos folyamfeladatnak nevezzük. Ha a csúcsokra kirótt csúcskapacitások mindegyike végtelen nagy érték, akkor nyilvánvaló, hogy az előző fejezetben ismertetett standard folyamfeladathoz jutunk. Bizonyos gyakorlati problémákban természetes követelmény a csúcskapacitás. Ilyen pontok lehetnek például az áruszállításnál az átrakodási pontok, csapatmozgásoknál az utánpótlási pontok, szárazföldi csővezetékeknél a tisztítóállomások vagy a hírközlési hálózatokban az erősítő berendezések. A csúcskapacitásos maximális folyamfeladathoz is rendelhető egy minimális vágás feladat. Itt azonban a vágást másképpen kell definiálni, ezt a vágást vegyes vágásnak nevezzük, amelynek elemei nemcsak élek, hanem pontok is lehetnek. A vegyes vágás átbocsátóképességét a vágásban szereplő élek és pontok kapacitásainak összege adja.

6.2. A feladat matematikai vizsgálata és megoldási algoritmusa

A csúcskapacitásos folyamfeladatra az alábbi ún. általánosított maximális folyam-minimális vágás tétel érvényes:

TÉTEL (Általánosított FORD-FULKERSON tétel):

Csúcs- és élkapacitásokkal is rendelkező hálózatban az -ből a -be irányuló folyam maximális értéke egyenlő az -et -től elválasztó vegyes vágás minimális átbocsátóképességével.

Bizonyítás.

Konstruktív jellegű a bizonyítás, kiolvasható belőle a megoldási algoritmus is.

Növeljük meg a hálózat méretét azáltal, hogy a csúcskapacitásokkal rendelkező pontokat duplázzuk meg és e két pont között vegyünk fel egy élet, amelynek élkapacitása legyen egyenlő a pont csúcskapacitásával. Legyen a csúcskapacitásos pont az i, ekkor a két pont legyen és , az élkapacitás pedig Az pontba érkeznek be azok az élek, amelyek az i pontba érkeztek be, az pontból pedig azok az élek indulnak ki, amelyek az i pontból indultak ki. Ezzel az átalakítással egy csúcskapacitás nélküli folyamfeladathoz jutottunk. Erre a feladatra érvényes a FORD-FULKERSON tétel és ismerjük a feladat megoldási algoritmusát is. Könnyen észrevehető, hogy a keletkező csúcskapacitás nélküli feladat minimális vágásában, ha van olyan él, amelyet most vezettünk be, akkor az a csúcskapacitásos feladathoz tartozó minimális vágásban pontot fog jelenteni. Így érthető, hogy a csúcskapacitásos folyamfeladatának duálisa minimális vegyes vágás feladat.

Algoritmus:

A megoldási algoritmus tehát megegyezik a standard folyamprobléma megoldási algoritmusával, csupán előkészületi munkákat (pontok duplázása és élek felvétele) kell végezni a standard alakra hozáshoz.

6.3. Példamegoldás

Határozzuk meg az alábbi hálózaton a csúcskapacitásos folyamfeladat és duálisának optimális megoldását!

Először végezzük el a hálózat kibővítését, vezessük be a „be” és „ki” pontokat.

1. lépés

2. lépés

3. lépés

Nem találtunk utat, vége az algoritmusnak.

Eredmények:

  1. A kibővített hálózaton:

    Maximális folyam értéke: 3

    Minimális vágás: , a vágás átbocsátóképessége: 3

  2. Az eredeti hálózaton:

    Maximális folyam értéke: 3

    Minimális vegyes vágás: élek: , pontok: 2, a vegyes vágás átbocsátóképessége: 3

6.4. Feladatok

  1. Adott az alábbi „honnan-hova” táblázattal egy gázvezeték hálózat. Határozza meg, hogy időegység alatt maximálisan mennyi gáz juttatható el a 4 jelű pontból a 2 jelű pontba, ha a 3 jelű ponton 2 mennyiségű gáznál több nem juttatható át! Mely kapacitások nem teszik lehetővé nagyobb mennyiségű gáz szállítását?

    honnan

    1

    2

    2

    3

    4

    4

    5

    5

    hova

    3

    1

    5

    2

    1

    5

    3

    2

    kapacitás

    4

    5

    3

    3

    5

    4

    5

    3

  2. Adott az alábbi „honnan-hova” táblázattal egy hálózat. Határozza meg az 5 pontból a 2 pontba irányuló maximális folyamot, ha a 4 ponton keresztül nem mehet 5 egységnél több folyam!

    honnan

    1

    1

    3

    3

    3

    4

    5

    5

    6

    6

    hova

    4

    6

    1

    4

    6

    2

    1

    3

    2

    4

    kapacitás

    6

    3

    6

    1

    3

    14

    2

    13

    2

    2

7. fejezet - Minimális költségű folyamfeladat

7.1. A feladat megfogalmazása

Tegyük fel, hogy a élkapacitáson kívül minden élhez egy , egész értékű költséget rendeltünk, amely egységnyi mennyiségű folyam áramoltatásának költségét jelenti. A hálózaton átfolyó folyam költségét az alábbiak szerint értelmezzük:

azaz feltesszük, hogy a hálózat minden élen a költség arányos a folyammal és ezen élköltségek összegét értjük folyamköltség alatt.

Minimális költségű folyamfeladat (primál feladat):

Áramoltassunk át a hálózaton az s-ből a t-be irányuló, adott értékű folyamot úgy, hogy a folyam költsége minimális legyen. A feladat matematikai megfogalmazása a következő:

Meghatározandó a hálózat minden élére az folyam úgy, hogy a

mennyiség minimális legyen feltéve, hogy

Megfigyelhetjük, hogy a feladat egyenlőséges feltételeinek együtthatómátrixa a szomszédossági mátrix.

Minimális költségű folyamfeladat duál feladata:

A hálózat pontjaira vonatkozó egyenlőséges feltételekhez rendelt duál változók legyenek: .

A hálózat éleire vonatkozó kapacitáskorlátos egyenlőtlenséges feltételekhez rendelt duál változók legyenek: .

Ekkor a duál feladat a következő formában írható fel:

Megjegyzés:

Ha minden kapacitás és , akkor a minimális költségű folyamfeladat minimális út feladattá válik.

7.2. Algoritmus a minimális költségű folyamfeladat megoldására

A feladatok matematikai vizsgálatával most nem foglalkozunk, csupán egy kézenfekvő algoritmust közlünk, amely segítségül hívja a minimális út feladat megoldását.

Az algoritmus leírásában a következő jelöléseket használjuk:

Jelölje a tényleges folyamértéket. Jelölje a hiányzó folyamértéket, amely megmutatja, hogy a megadott folyamérték () eléréséhez még mekkora folyamérték hiányzik, képlete: . Jelölje C a folyamköltséget, azaz a célfüggvény értékét.

  1. A hálózat kiegészítése teljes hálózattá, zérus kapacitású és végtelen költségű élekkel.

  2. Az induló folyam legyen a zérus folyam, azaz minden élen. Az induló szabad kapacitás: . Az induló folyamérték: . Az induló hiányzó folyamérték: . Az induló folyamköltség: .

  3. Minimális út meghatározása s-ből t-be a költségadatokon. A minimális út feladat célfüggvényének optimális értéke az út mentén lévő költségek összege, amelyet úgy is felfoghatjuk, mint egységnyi mennyiségű folyam úton való áramoltatásának folyamköltsége. Jelölje ezt .

  4. A minimális út kapacitásának a meghatározása (), amely az út mentén a szabad kapacitások minimuma.

    A hiányzó folyamérték meghatározása: .

    Az út kapacitásának tényleges értéke a és a értékek minimum, azaz . Ezzel az értékkel növelhetjük meg az út mentén a folyamot.

    A folyamérték meghatározása: .

    A folyamköltség meghatározása: Az út minden élén növeltük a folyamot -val, így a mennyiségű folyam áramoltatásának költsége , az új folyamköltség:

  5. A folyam ill. a szabad kapacitás módosítása:

    Az út kapacitásával az út minden élén növeljük a folyamot, a visszút mentén pedig csökkentjük. Ehelyett azonban a szabad kapacitásokat () módosítjuk az alábbiak szerint:

    Ha , vagy ami ugyanazt jeleni, hogy , akkor megállunk, mert ezzel a folyamnöveléssel a folyam értéke elérte az előírt értéket, hisz pontosan a hiányzó folyamértékkel javítottunk a folyamon. A szabad kapacitások segítségével meghatározhatjuk a minimális költségű folyamot a hálózat élein. A minimális folyamköltséget pedig C értéke adja.

    Ha , vagy , akkor újabb minimális út keresésére van szükség, de előtte módosítani kell a költségeket. A (6) pontban folytatjuk az eljárást.

  6. A költségek módosítása:

    A módosítás szemléletes, hisz, ha egy élen még van szabad kapacitás, akkor ott nem változtatunk a költségen. Ha egy él szabad kapacitása zérus, akkor azon már nem lehet további folyamot áramoltatni, így az útkeresésnél ezt az élet nem szabad figyelembe venni. Ezt úgy valósíthatjuk meg, hogy az él költségét végtelen nagyra választjuk, így ez az él biztosan nem kerül bele a minimális útba. Az út visszélein a szabad kapacitás nőtt, így ott lehet további folyamnövelés, viszont ha ezeken az éleken növeljük a folyamot, az azt jelenti, hogy az ellentétes élen csökken a folyam, így a folyamköltség is. Ezért ezeknek az éleknek negatív költséget adunk, mégpedig az ellentétes irányú él költségének (-1)-szeresét.

  7. Visszatérés a (3) ponthoz, azaz újabb minimális út feladatot kell megoldanunk.

Megjegyzés:

Az algoritmus során minden lépésben minimális utat kell meghatározni. A költségek között viszont lehetnek negatív számok is. A minimális út megkeresésének algoritmusának ismertetésekor feltettük, hogy a költségadatok nemnegatívok. Ezért a soron következő példamegoldásban a megoldási lépéseket csak vázlatosan hajtjuk végre, a minimális utat csupán közöljük. Fontos megjegyeznünk, hogy a feladat duálisának segítségével hatékony primál-duál algoritmus dolgozható ki, amelyet out-of-kilter néven ismerünk.

7.3. Példamegoldás

Határozzuk meg az alábbi hálózaton az 1-ből a 4-be irányuló, 7 folyamértékű minimális költségű folyamot! A hálózat élein két számot tüntettünk fel, az első a kapacitást, a második (zárójelben lévő) pedig a költséget jelenti.

0. lépés

Induló adatok: , , , ,

Az induló szabad kapacitás táblázat és költségtáblázat:

A minimális út (P):

Az út minimális költsége:

Az úton a minimális kapacitás:

A folyamnövelés értéke:

A folyamérték:

A hiányzó folyamérték:

A folyamköltség:

1. lépés

Az új szabad kapacitás táblázat és költségtáblázat:

A minimális út (P):

Az út minimális költsége:

Az úton a minimális kapacitás:

A folyamnövelés értéke:

A folyamérték:

A hiányzó folyamérték:

A folyamköltség:

2. lépés

Az új szabad kapacitás táblázat és költségtáblázat:

A minimális út (P):

Az út minimális költsége:

Az úton a minimális kapacitás:

A folyamnövelés értéke:

A folyamérték:

A hiányzó folyamérték:

A folyamköltség:

Vége az algoritmusnak, mert elértük az adott folyamértéket.

Megoldás:

Az eredeti hálózat élein a folyamok:

Az összes szállítási költség: , amelyet az algoritmus során is meghatároztunk.

7.4. Feladatok

  1. Adott az alábbi két táblázattal egy hálózat. Határozzuk meg az 1-ből az 5-be irányuló minimális költségű maximális értékű folyamot!

    Útmutató a megoldáshoz:

    Mivel a folyamértékre nincs előírás, így mindig értékkel kell növelni a folyamot.

  2. Határozzuk meg az alábbi hálózaton az 1-ből a 4-be irányuló, 5 folyamértékű minimális költségű folyamot! A hálózat élein két számot tüntettünk fel, az első a kapacitást, a második (zárójelben lévő) pedig a költséget jelenti.

    a) Írja fel a minimális költségű folyam feladatot matematikai formában és adja meg a feladat duálisát is!

    b) Oldja meg a feladatot szimplex módszerrel!

    c) Oldja meg a feladatot duál módszerrel!

    d) Oldja meg a feladatot a megismert módszerrel (minimális út sorozatos keresésével)!

8. fejezet - Veszteséges-nyereséges folyamfeladat

A hagyományos folyamproblémában a folyam az éleken megőrződött. A gyakorlatban elképzelhetők olyan feladatok is, amikor ez nem áll fenn. Rendeljünk minden élhez a kapacitáson kívül egy nemnegatív szorzót. A veszteséges-nyereséges folyamnál ha egy élen folyam megy be az él kezdetén, akkor folyam jön ki az él végén. Ha , akkor az él veszteséges, ha pedig , akkor nyereséges. Ha minden , akkor a standard folyamfeladatot nyerjük. A veszteségek és a nyereségek miatt nem szükségképpen egyenlő a forrásból kifolyó és a nyelőben elnyelődő folyam értéke. A folyam maga is lehet tehát veszteséges vagy nyereséges. A folyam veszteségét a forrásból kifolyó és a nyelőbe befolyó folyam értékének a különbségeként definiáljuk, képletben . Feladatunk olyan folyam keresése, amelynek a vesztesége a legkisebb.

A minimális veszteségű folyamfeladat alatt a következő problémák valamelyikét értjük:

  • Áramoltassunk át a hálózaton a forrásból kimenő adott értékű folyamot úgy, hogy a nyelőbe befolyó folyam értéke maximális legyen.

  • Áramoltassunk át a hálózaton a nyelőbe befolyó adott értékű folyamot úgy, hogy a forrásból kimenő folyam értéke minimális legyen.

A megfogalmazott feladatoknál is érvényesek az élekre írt kapacitáskorlátok, azaz

és a közbülső pontokban érvényes a Kirchoff csomóponti törvény, amely szerint

Ezeknek a feladatoknak a megoldásával nem foglalkozunk, csupán a továbbfejlesztési lehetőségekre kívántunk rámutatni.

9. fejezet - Általános KŐNIG feladat

9.1. A feladat megfogalmazása

Legyenek adottak a termelők, amelyek rendre kínálattal rendelkeznek és az fogyasztók, amelyek kereslete (igénye) rendre . A keresleti és a kínálati adatokról feltehetjük, hogy pozitív számok, mert ellenkező esetben nem érdemes szerepeltetni az illető termelőt ill. fogyasztót. Ismert továbbá, hogy mely termelőtől, mely fogyasztóhoz történhet szállítás, amelyet egy kvalifikációs táblázattal szoktunk megadni, amelynek (, ) cellájába *-ot teszünk, ha a termelő szállíthat árut az fogyasztóhoz. Ha a termelők és fogyasztók közötti szállítási viszonylatokat digráffal szemléltetnénk, akkor egy speciális digráfot kapnánk, a ponthalmaz két olyan részhalmazból áll, amelynél él csak az egyik részhalmazból vezet a másik részhalmazba. Az egyes részhalmazokon belül nincsenek élek. Az ilyen digráfot páros vagy kétrészes digráfnak nevezzük. Az általános Kőnig feladatot az alábbi sémával szoktuk jellemezni:

Az általános Kőnig feladatot kétféle formában is megfogalmazzuk, az egyiket egzisztencia formában, a másikat pedig optimalizálási feladat formájában.

Kőnig feladat egzisztencia formában:

Elszállítható-e az összes árú a termelőktől a fogyasztókhoz az alábbi feltételekkel:

  • csak olyan viszonylatban szállíthatunk, ami megengedett,

  • a fogyasztókhoz legfeljebb az igényüknek megfelelő mennyiségű árut szállíthatunk?

A legtöbb esetben azonban nem csak arra vagyunk kíváncsiak, hogy megoldható-e az elszállítás, amennyiben nem tudjuk az összes árut elszállítani, akkor jó lenne tudni, hogy maximálisan mennyi árú szállítható el. Ha a termelők összkínálata meghaladja a fogyasztók összkeresletét, akkor eleve nem lehet az összes árut elszállítani, tehát az egzisztencia formában megfogalmazott feladat megoldása triviális, azonban nem triviális a megoldása az olyan kérdésfelvetésnek, hogy maximálisan mennyi árú szállítható el a termelőktől.

Kőnig feladat optimalizálási formában:

Maximálisan mennyi árú szállítható el a termelőktől a fogyasztókhoz az alábbi feltételekkel:

  • csak olyan viszonylatban szállíthatunk, ami megengedett,

  • a termelőktől legfeljebb a kínálatuknak megfelelő mennyiségű árut szállíthatunk,

  • a fogyasztókhoz legfeljebb az igényüknek megfelelő mennyiségű árut szállíthatunk?

A részletes vizsgálat előtt néhány jelölést vezetünk be. Legyen a termelők, a fogyasztók halmaza. (A termelők halmazát azért nem T-vel jelöltük, mert a T-t már a vágás egyik ponthalmazára lefoglaltuk.) Jelölje a termelők egy tetszőleges részhalmazát és jelölje azon fogyasztók halmazát, amelyekhez a P-beli termelők együttesen szállíthatnak. Jelölje továbbá a P-beli termelők kínálatát, az -beli fogyasztók keresletét.

Példaként tekintsük az alábbi kvalifikációs táblázattal adott általános Kőnig feladatot:

Legyen . Könnyen meggyőződhetünk arról, hogy ekkor . A P-beli termelők kínálata , az -beli fogyasztók kereslete .

9.2. A feladat matematikai vizsgálata

Az általános Kőnig feladat megoldhatóságára (egzisztencia formára) vonatkozik az alábbi tétel.

KŐNIG tétel:

Adott kvalifikációs táblázat esetén

  • vagy az összes áru elszállítható a fogyasztókhoz,

  • vagy van a termelőknek olyan részhalmaza, hogy .

Más szavakkal megfogalmazva: vagy elszállítható az összes árú, vagy ha nem, akkor megadható a termelőknek olyan részhalmaza, hogy ezen termelők összkínálata meghaladja azon fogyasztók összkeresletét, amelyekhez a kiválasztott termelők együttesen szállíthatnak.

A következőkben a tétel bizonyítását közöljük. A tétel bizonyítására konstruktív bizonyítást adunk, ami azt jelenti, hogy a bizonyítással a feladat megoldásának módját is megadjuk.

Bizonyítás.

A tétel bizonyítása a maximális folyam-minimális vágás feladatpár alaptételén (FORD-FULKERSON tétel) alapszik.

Konstruáljunk egy hálózatot, amelynek csúcspontjai a termelők és a fogyasztók, ezenfelül vegyünk fel egy forrást (s) és egy nyelőt (t). Minden termelőhöz vezessen él az s forrásból, minden fogyasztótól vezessen él a t nyelőhöz. A többi él termelők és fogyasztók közötti, mégpedig olyan viszonylatban, ahol megengedett a szállítás. A hálózat éleit és a kapacitásait az alábbi ábra mutatja. Az ábrába berajzoltunk egy vágást és a P, R ponthalmazokat is, amelyek a bizonyítás során lesznek meghatározva.

Legyen az típusú él kapacitása a termelő kínálata, az típusú él kapacitása az fogyasztó kereslete és a típusú él kapacitása végtelen .

Az általános Kőnig feladatot ezáltal egy folyamatfeladatra vezettük vissza. A folyamfeladat megoldási algoritmusával a folyamproblémát megoldjuk. A maximális folyam megoldása a Kőnig feladattal kapcsolatban az alábbiakat jelenti:

Az a -ből elszállított összmennyiséget, az az -be szállított összmennyiséget, az pedig a -ből az -be szállított árúmennyiséget jelenti. Ha például valamely , akkor ez a csomóponti megmaradási törvény alapján azt jelenti, hogy a -ből az összes árut elszállítottuk a fogyasztókhoz. Két esetet különböztetünk meg attól függően, hogy az folyamérték maximális értékére milyen eredményt kapunk.

1. eset: A maximális folyam értéke .

Ez azt jelenti, hogy az s-ből kiinduló élek mindegyike telített, ugyanis csak így lehet a folyam értéke .

A csomóponti megmaradási törvény szerint pedig ekkor mindegyik termelőtől pontosan a kínálatának megfelelő mennyiségű árut szállítunk el. Tehát ebben az esetben az összes árú elszállítható a termelőktől. A folyamfeladat megoldásai adják meg azt, hogyan lehet elszállítani az árukat.

2. eset: A maximális folyam értéke .

Ez azt jelenti, hogy az s-ből kiinduló élek nem mindegyike telített, tehát az összes árút nem lehet elszállítani. A folyamprobléma tárgyalásakor megismertük, hogy a maximális folyamhoz tartozik egy minimális vágás, amelyet a fenti ábrában tüntettünk fel. A vágás S ponthalmazába tartozó termelők halmazát P-vel, a fogyasztók halmazát pedig R-el jelöltük. A vágás T ponthalmazába tartozó termelők ill. fogyasztók halmazát -vel ill. -el jelöljük. Az, hogy ez a vágás minimális, a következőket jelenti.

  • Nem vezethet él P-beli termelőktől -beli fogyasztókhoz. Ha lenne ilyen él, akkor ez a vágás nem lehetne minimális az él kapacitása miatt. Tehát a P-beli termelők csak az -beli fogyasztókhoz szállíthatnak.

  • Nem lehet szállítani -beli termelőktől R-beli fogyasztókhoz. Ha például a termelőtől az fogyasztóhoz valamennyit szállítanánk, akkor a vágásban lévő él szabad kapacitású lenne, ellentétben azzal, hogy a vágásban csak telített élek szerepelnek.

Ezekután meghatározhatjuk az (S,T) vágás minimális átbocsátóképességét. Az vágásban lévő élek kapacitásait kell összeadni, amely az ábráről leolvasva az alábbi:

A FORD-FULKERSON tétel értelmében . Viszont a maximális folyam esetünkben , ezért az alábbi egyenlőtlenség írható

amelyet átrendezve

adódik. Ezt a bevezetett jelölésekkel felírva a

bizonyítandó összefüggést kaptuk.

Végül néhány megjegyzést fűzünk a 2. esethez, amikor az összes árú nem szállítható el. Mint tudjuk, a folyamprobléma meghatározása során kiadódó minimális vágást lefedéssel is szemléltethetjük. Fedjük le a -beli termelőkhöz tartozó sorokat ill. az R-beli fogyasztókhoz tartozó oszlopokat. Rendezzük át a táblázatot sorok és oszlopok cseréjével úgy, hogy az első sorokban a P-beli termelők, az első oszlopokban R-beli fogyasztók legyenek. Ekkor az alábbi táblázat adódik. Megjegyezzük, hogy a gyakorlati példákban a sorok és oszlopok cseréjére nincs szükség, itt azért tettük meg, hogy szemléletesebben lássuk az alábbi megjegyzéseket.

Megjegyzések:

  1. A fedetlen helyen nincs *, azaz ezeken a helyeken az általános Kőnig feladatban tiltott a szállítás. Ez egyben azt is jelenti, hogy a fedővonalrendszer az összes *-ot lefedi.

  2. A kétszer fedett helyeken nincs szállítás. A szállítási lehetőség (*) nincs kizárva ezeken a helyeken, de a szállítás zérus.

  3. Minden -beli termelőtől elszállítottuk a kínálatuknak megfelelő mennyiségű árut.

  4. Minden R-beli fogyasztó igényét kielégítettük.

  5. A lehető legtöbb mennyiségű árú lett elszállítva a termelőktől a fogyasztókhoz.

Az első négy megjegyzés abból következik, hogy a minimális vágás minden éle telített. Az első két megjegyzés szerint szállítás csak az egyszer fedett helyeken lehet.

Felhívjuk a figyelmet arra, hogy a Kőnig feladat egzisztencia formájára mondtuk ki a KŐNIG tételt. Ezt a tételt át is fogalmazhatjuk a következőképpen:

KŐNIG tétel (más formában):

Adott kvalifikációs táblázat esetén az összes árú elszállíthatóságának szükséges és elégséges feltétele az, hogy minden termelő esetén

Természetesen a két egzisztencia tétel ekvivalens egymással, az először megfogalmazott viszont az alaptételünkhöz, a MINTY tételhez hasonló szerkezetű.

Az (1) megjegyzést mélyebben vizsgálva a következőket mondhatjuk. Legyen adott egy táblázatunk, amelyben *-ok szerepelnek. Minden sornak ill. oszlopnak adjunk egy súlyszámot. Fedővonalrendszer alatt a táblázat bizonyos sorainak ill. oszlopainak egy-egy vonallal való lefedését értjük. A fedővonalrendszer súlyszámát pedig a lefedett sorok ill. oszlopok súlyszámainak összegével definiáljuk.

Lefedési feladat:

Fedjük le a táblázatban szereplő összes *-ot a legkisebb súlyszámú fedővonalrendszerrel!

Ez az optimalizálási feladat a folyamfeladat duálisának, vagyis a minimális vágás feladatnak felel meg. A fedővonalak a vágásnak, a fedővonalak súlyszáma pedig a vágás átbocsátóképességének felel meg. Tehát ezen lefedési probléma megoldására is a Kőnig feladat megoldási módszere szolgál.

9.3. Algoritmus az általános Kőnig feladat megoldására

A KŐNIG tétel bizonyítása egyúttal módszert is adott mind az egzisztencia formájú, mind az optimalizációs formájú Kőnig feladat megoldására. Mivel a problémát a maximális folyam-minimális vágás feladatra vezettük vissza, így annak megoldási algoritmusát fogjuk használjuk.

Két lényeges észrevétel azonban megkönnyítheti a megoldást.

  1. A folyamprobléma kiinduló lépése egy lehetséges folyam (szállítás) meghatározása. Általában a zérus folyamból szoktunk kiindulni. Az általános Kőnig feladathoz konstruált folyamprobléma a kétrészes digráf szerkezet miatt nagyon speciális, így egyszerűen nyerhető az azonosan zérus szállítástól különböző induló szállítás is. Ezt az induló szállítást sokféleképpen meghatározhatjuk, azonban javasoljuk az ún. Észak-Nyugati sarok módszer szerint elvégezni. Ezt az egyszerű módszert majd a példamegoldás során fogjuk ismertetni.

  2. A megoldandó csúcspontú folyamfeladatot mint tudjuk egy méretű táblázaton kell megoldani. A folyamfeladat speciális szerkezetét azonban nemcsak az induláskor, hanem a megoldás során is kihasználhatjuk. Mivel bármely két termelő és bármely két fogyasztó között a kapacitás zérus, ezért ezeken az éleken nem folyhat folyam, így az eredeti méretű táblázaton is megoldhatjuk a feladatot, hisz a folyamprobléma címkézése során szükséges szabad kapacitású éleket ezen a kisebb méreten is tudjuk tárolni. Az alábbi ábra mutatja a megoldáshoz használt táblázatot.

    • Az típusú él szabad kapacitását a táblázat (i) részén tároljuk. Ez a szabad kapacitás tulajdonképpen a termelőtől még elszállítandó árúmennyiséget jelenti.

    • Az típusú él szabad kapacitását a táblázat (ii) részén tároljuk. Ez a szabad kapacitás az fogyasztó kielégítetlen igényét jelenti.

    • A tábla belsejében a szállítást tároljuk, itt a szabad kapacitás tárolása a kapacitás miatt értelmetlen lenne. Azokat a cellákat, ahol a szállítás nincs megengedve (tiltott hely) „-” jellel jelöljük.

    • Mivel a folyamproblémát teljes hálózaton oldjuk meg, így az élek is szerepelnek a hálózaton, amelyek szabad kapacitása nem más mint a él szállítása, hisz legfeljebb ennyit szállíthatunk vissza, más szóval legfeljebb ennyivel csökkenthetjük az él szállítását.

Ezekután a címkézésnek a csökkentett méretű táblázatra történő adaptálásáról kell szólnunk röviden.

A címkézéssel mindig a forrásból (s) a nyelőbe (t) keressük a szabad kapacitású utat, vagyis olyan utat, amelyen a folyam növelhető. Tehát a kínálattal rendelkező valamelyik termelőtől kell a kielégítetlen igénnyel rendelkező valamelyik fogyasztóhoz eljutni. Így „-s”-el azokat a fogyasztókat kell megcímkézni, amelyek még rendelkeznek elszállítandó áruval, vagyis amelyeknél az (i) részben pozitív szám áll. Az útkeresés végpontja azon fogyasztók valamelyike, amelynél az (ii) részben pozitív szám áll.

A hálózat többi éle és típusú. Az útkeresés során termelőtől minden olyan fogyasztóhoz mehetünk, ahol nincs tiltva a szállítás, azaz ahol a táblázatban zérus vagy pozitív szám áll. Viszont fogyasztótól termelőhöz csak olyan cellán mehetünk, amelyben pozitív szám áll.

9.4. Példamegoldás

1. Példa:

Oldjuk meg az alábbi általános Kőnig feladatot!

0. lépés: Kezdeti szállítás meghatározása.

Célszerű azzal kezdeni a megoldást, hogy a tiltott helyeket „-” jellel bejelöljük és ekkor az üres helyeket kell kitölteni.

Mint említettük az ún. Észak-Nyugati sarok módszerrel szokás egy induló szállítást előállítani. Az Észak-Nyugati sarok módszer lényege az, hogy a táblázat bal felső (É-Ny-i irányú) sarkából kiindulva balról jobbra és fentről lefelé haladva írjuk be a szabad helyekre a szállítási mennyiségeket. Mivel célunk a legtöbb árú elszállítása, ezért mindig a lehető legnagyobb szállítási értékkel töltjük fel a táblát.

Az Észak-Nyugati sarok módszer néhány lépését az alábbiakban közöljük:

A -ből az -be szállíthatunk (szabad hely), de legfeljebb 18-at (a 18 és a 32 minimumát) és ezt a 18-at írjuk a táblázatba, a kínálatát és az keresletét 18-al csökkentve. A -ből az -ba is szállíthatunk, de már csak zérus mennyiséget. Hasonlóan zérussal kell kitöltenünk a táblázat első sorának utolsó szabad helyét is. Most a második termelő következik. A -ből az -be szállíthatunk (szabad hely), de legfeljebb 14-et (a 22 és a 14 minimumát) és ezt a 14-et írjuk a táblázatba, a kínálatát és az keresletét 14-el csökkentve. A táblázat többi szabad helyét hasonlóan kell kitölteni, tehát az eredeti táblázat és a szállítási táblázat egyidejű figyelésével. Párhuzamosan töltjük ki a táblázat szegélyeit is, ahová mindig a megmaradó kínálatot ill. a kielégítetlen igényt írjuk. Nyilvánvalóan mindig igaz az, hogy a táblázat (szegélyeket is figyelembe véve) soraiban lévő számok összege a termelők kínálatát, az oszlopaiban lévő számok összege pedig a fogyasztók keresletét adja. A következő táblázat az induló szállítást mutatja.

Elvileg bármely módszerrel meghatározható egy lehetséges induló szállítás, sőt a szabad helyeket zérussal is feltölthetnénk. Láthatjuk, hogy a 86 kínálatból minden erőfeszítés nélkül 80-at sikerült indulásként elszállítani. Az is megállapítható, hogy még a és a termelőtől kellene szállítani az -be. Ezt egy út megkeresésével végezzük.

1. lépés: Útkeresés s-ből t-be címkézéssel.

A címkézés eredménye az alábbi táblázatban látható. Ahhoz, hogy könnyebben megértsük a címkézés lényegét, a címkézést lépésenként közöljük, ezt mutatja a fenti táblázat. A termelők címkéit a táblázat jobb, a fogyasztók címkéit pedig az alsó szegélyen tüntetjük fel.

0. lépés: A és címkéje induláskor „-s”, mert innen kell elszállítani árut és addig kell címkézni, amíg az -be nem érkezünk vagy azt kapjuk, hogy nincs út.

Most megnézzük, hogy a és termelőtől mely fogyasztókhoz mehetünk.

1.1. lépés: A -ból az -be és az -ba, mehetünk, így ezen fogyasztók címkéjeként beírjuk a -t.

1.2. lépés: A címkéjét „+s”-re változtatjuk.

2.1. lépés: A -ből az és -be mehetünk. Mivel -nek már van címkéje, így csak az -et címkézzük, mégpedig -el.

2.2. lépés: A címkéjét „+s”-re változtatjuk.

Mivel a kérdéses -be nem jutottunk el, ezért most a fogyasztóktól próbálunk a termelőkhöz szabad kapacitású úton visszamenni.

3.1. lépés: Az -ből -be haladhatunk, mivel a viszonylatban van szállítás, amit visszaszállíthatunk. A -t címkézzük -vel.

3.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

4.1. lépés: Az -ból nem tudunk továbbhaladni, mivel nem szállítottunk hozzá, nem címkézünk.

4.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

5.1. lépés: Az -ből nem tudunk továbbhaladni, mivel nem szállítottunk hozzá, nem címkézünk.

5.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

Most újra termelőktől próbálunk a fogyasztókhoz menni szabad kapacitású úton. A címkézésnél tehát felváltva címkézünk termelőtől fogyasztóhoz és fogyasztótól termelőhöz. Szisztematikusan címkézzünk, tehát amíg van negatív címke a függőleges ill. a vízszintes címkemezőkben, addig ne váltsunk a másik irányra.

6.1. lépés: A -ből az és -be mehetünk. Mivel -nek már van címkéje, így csak az -et címkézzük, mégpedig -vel.

6.2. lépés: A címkéjét „+” előjelűre változtatjuk.

Most újra fogyasztótól címkézünk.

7.1. lépés: Az -ből -be haladhatunk, mivel a viszonylatban van szállítás, amit visszaszállíthatunk. Az -et címkézzük -el.

7.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

Most újra termelőtől címkézünk.

8.1. lépés: A -ből az , és -be mehetünk. Mivel az , már címkézett, így csak az -be mehetünk és az -öt címkézzük -el.

Ezzel a lépéssel be is fejeztük a címkézést, hiszen olyan fogyasztóhoz jutottunk, amelyiknek még van igénye.

Az alábbi táblázat a címkézés eredményét mutatja, de nem lépésenkénti bontásban.

A címkézés eredményeképpen az alábbi út adódott. Az utat mint ismeretes a címkéken visszafelé haladva határozhatjuk meg.

Az út éleinek szabad kapacitását az út élei alatt tüntettük fel. A típusú élen a szabad kapacitás , mivel a kapacitás is az. Az típusú élen pedig a szabad kapacitás a megfelelő típusú él szállítása. Az út mentén a szállítás a szabad kapacitások minimumával () növelhető. Példában az út kapacitása . Észrevehető, hogy az első és utolsó élnek, valamint minden második élnek van véges szabad kapacitása. Jelöljük az út éleit és szimbólumokkal, mégpedig úgy, hogy -el az út azon éleit, amelyek közrejátszanak meghatározásában, -el pedig az út többi élét. Az út tehát -el kezdődik (ill. végződik) és felváltva és jeleket tartalmaz. Az utat a későbbiekben nem érdemes külön leírni, hanem az út felgöngyölítése során a táblázatba és jelekkel bejelöljük az út éleit. Ily módon a -t a szimbólummal jelölt számok minimumaként határozhatjuk meg, példánkban

A ismeretében folyamnövelést kell végrehajtani az út mentén. A jelöléseink segítségével ezt az alábbi egyszerű módon végezhetjük el:

  • szimbólummal jelölt értékeket csökkentjük -val,

  • szimbólummal jelölt értékeket növeljük -val.

A jobb érthetőség kedvéért az út megfelelő jelekkel való jelölésével mégegyszer megismételjük az előző táblázatot. A táblázatba bejelöltük félkövéren az út vonalát is. Ez mindig egy törtvonalnak adódik, amely vízszintes és függőleges vonalain is az egyik végpont -el, a másik pedig -el van jelölve.

Az alábbi ábra is az utat mutatja, de most az általános Kőnig feladat kétrészes gráfján:

A táblázatos útjelölésnél tehát minden vizszintes ill. függőleges vonal mentén egy növelést és egy csökkentést hajtunk végre. Azoknál a termelőknél ill. fogyasztóknál, ahol nincs elszállítandó árú ill. kielégítetlen igény ott egyszerűen átrendeződik a szállítás. Amennyivel egyik helyen többet szállítottunk, a másik helyen ugyanannyival kevesebbet. Kivételt csak az út első és utolsó éle képez, mert itt a szállítás növekszik. A gráfon látható utat alternáló útnak nevezzük, mert minden második éle és ezeken növelést ill. minden második éle típusú és ezeken csökkenést eszközlünk.

2. lépés: Folyamnövelés és útkeresés címkézéssel.

3. lépés: Folyamnövelés és útkeresés címkézéssel.

Vége az algoritmusnak, útkeresésre már nincs szükség, mert a termelőktől a kínálatuknak megfelelő mennyiségű árut elszállítottuk. Az eldöntendő kérdésre tehát a válasz igen, azaz az összes árú elszállítható a termelőktől. Azt is megkaptuk egyben, hogy milyen módon kell végrehajtani a szállítást. Az szállításokat a fenti szállítási táblázat mutatja. A -ből az -be 12 egységet, -ből az -be 6 egységet, stb. kell szállítani.

2. Példa:

Oldjuk meg az alábbi általános Kőnig feladatot!

1. lépés: Induló szállítás meghatározása Észak-Nyugati sarok módszerrel és útkeresés címkézéssel

2. lépés: Folyamnövelés és útkeresés címkézéssel.

Vége az algoritmusnak, mert nincs út, így nem tudjuk tovább növelni a szállítást. Arra az eldöntendő kérdésre, hogy az összes árú elszállítható-e, nem a válasz, mivel 2 mennyiséget semmiképpen nem lehet elszállítani. Arra a kérdésre, hogy maximálisan mennyi árú szállítható el a termelőktől, szintén megkaptuk a választ, 2 híján az összeset, azaz 87-et. Az algoritmus azt is megmutatja, hogy a maximális mennyiséget milyen módon kell elszállítani. A fenti szállítási táblából olvashatók ki az szállítások. Mivel az összes árut nem lehet elszállítani, így a KŐNIG tétel értelmében meghatározhatók a termelők és fogyasztók P és R halmazai. A P ill. R halmazba a megcímkézett termelők ill. fogyasztók tartoznak, azaz

A P-beli termelők összkínálata és az R-beli fogyasztók összkereslete pedig az alábbi

Tehát , ahogy ezt a KŐNIG tétel állította. Valóban nem lehet az összes terméket elszállítani, hiszen már a P-beli termelőktől sem tudjuk a kínálatuknak megfelelő 46 mennyiséget elszállítani, mert csupán 44-et képesek fogadni azok a fogyasztók, amelyekhez a P-beliek szállíthatnak.

Végezetül a lefedést is elvégezhetjük a szállítási táblázaton, mégpedig a nem P-beli (címkézetlen) sorokat és az R-beli (címkézett) oszlopokat fedjük le. Látható, hogy a fedetlen helyeken mindenhol tiltás van, így minden szabad hely lefedett. A kétszer fedett helyeken a szállítás zérus, így pozitív szállítás csak egyszer fedett helyen lehet. A fedővonalrendszer súlyszáma: 87, amely a lefedett sorokhoz és oszlopokhoz tartozó kínálatok és keresletek összege. A fedővonalrendszer olyan, hogy az összes szabad helyet (*-ot) lefedi és a súlyszáma a lehető legkisebb. Az elszállítható maximális árúmennyiség egyenlő a fedővonalrendszer súlyszámával. Ez a FORD-FULKERSON tételből következik.

9.5. Feladatok

  1. Az A ország városaiból rendre 40, 10, 20, 30 ezer tonnányi azonos terméket kell elszállítani a B ország 4 városaiba. A B ország mindegyik városába ugyanannyi mennyiséget kell szállítani és az összkínálat egyenlő az összkereslettel. Hogyan kell a szállítást lebonyolítani, ha a termékek szállítását csak az alábbi útvonalakon végezhetjük: ; ; ; ?

  2. Az műhelyek termelése rendre 9, 9, 9, 9, 12; az raktárak befogadóképessége pedig rendre 12, 8, 8, 7, 13. Az alábbi műhely-raktár viszonylatban történhet szállítás: ; ; ; ; ;. Az egyes gépek által megmunkált alkatrészeket mely raktárakba kell irányítani (egy gép termékét több raktárba is lehet irányítani), hogy minél kevesebb alkatrész maradjon raktáron kívül?

  3. Tegyük fel, hogy a befizetési rovatokon rendre 18, 22, 34, 12, 14, 21, 9 pénzmennyiség, a kifizetési rovatokon pedig rendre 32, 24, 14, 15, 30, 15 pénzmennyiség van. Az alábbiakban megadjuk, hogy a kifizetéseket mely befizetési rovatokból lehet eszközölni: ; ; ; ; ; . Az . A fentiek figyelembevételével milyen rovatokból kell a kifizetéseket lebonyolítani?

  4. Adottak az személyek, akik rendre 2, 3, 4, 7, 1 pénzegységgel rendelkeznek és adottak továbbá a bankok, amelyek befogadóképessége rendre 4, 3, 1, 3, 3, 3 pénzegység. A személyek az alábbi bankokba hajlandók pénzüket elhelyezni: ; ; ; ; . El tudják-e a személyek helyezni az összes pénzüket a szimpatikus bankokba, ha igen, akkor hogyan; ha nem, akkor mennyit tudnak maximálisan elhelyezni?

  5. Adott az alábbi táblázat. Fedje le az összes *-ot a lehető legkisebb súlyszámú fedővonalrendszerrel! A sorok súlyszámai rendre 18, 18, 18, 18, 24; az oszlopoké pedig rendre 24, 16, 16, 14, 26.

  6. Adott az alábbi számtáblázat és a sorok ill. oszlopok súlyszámai. Fedje le az összes 4-nél kisebb számot a lehető legkisebb súlyszámú fedővonalrendszerrel!

  7. Adott a termelők kínálata, a fogyasztók kereslete valamint a termelők és fogyasztók között a szállítási egységköltség. Milyen szállítás esetén tudjuk a lehető legtöbb árut elszállítani a termelőktől, ha nem vagyunk hajlandóak olyan helyen szállítani, ahol a szállítási egységköltség meghaladja a 20-at?

  8. Egy vállalat hat üzemegysége (Ü) rendre 10, 15, 8, 22, 14, 16 mennyiségben akar vásárolni öt másik vállalattól (V), amelyeknek 15, 25, 15, 15, 15 a készlete a vásárolandó anyagból. Ismertek az üzemegységek és a vállalatok között a fajlagos szállítási és értékesítési költségek összege. A vásároló vállalat csak legfeljebb 8 fajlagos költséggel akar vásárolni. Megoldható-e így a beszerzés, ha igen, akkor hogyan; ha nem, akkor maximum mennyit tud vásárolni a vállalat?

  9. Adottak a városok a 8, 9, 7, 6, 5 kínálattal és az falvak 6, 9, 5, 8, 7 kereslettel. Minden város és falu között van vasúti és közúti összeköttetés. Az alábbi viszonylatokban vasúti pályaépítés miatt a szállítás csak közúton oldható meg: ; ; ; ; . Hogyan kell a városok és a falvak közötti szállítást lebonyolítani, hogy minél kevesebb árút szállítsunk a drágább közúton?

  10. Adott a termelők (T) 9, 4, 3, 9 kínálata, a fogyasztók (F) 6, 8, 4, 7 kereslete és a fogyasztók csak az alábbi termelőktől kívánnak vásárolni: ; ; ; . Mennyi a fogyasztók által vásárolható mennyiségnek a legnagyobb értéke és ez milyen vásárlás esetén jön létre?

10. fejezet - Szűk-keresztmetszetű szállítási feladat

10.1. A feladat megfogalmazása

Legyenek adottak a termelők (vagy termelőhelyek), amelyek rendre kínálattal rendelkeznek és az fogyasztók (vagy fogyasztóhelyek), amelyek kereslete (igénye) rendre . Legyenek továbbá adottak a szállítási idők, amelyek a termelőtől az fogyasztóhoz történő szállítás időtartamát jelentik és függetlenek a szállított mennyiségtől. A megadott adatok legyenek nemnegatív egészek.

A szűk-keresztmetszetű szállítási feladat az alábbi sémával jellemezhető:

Tegyük fel, hogy az összkínálat egyenlő az összkereslettel, azaz

A szűk-keresztmetszetű szállítási feladat:

Határozzuk meg a keresletet és a kínálatot kielégítő szállítást úgy, hogy az a legrövidebb ideig tartson feltéve, hogy a szállítások egyidőben kezdődnek el.

A szállítás lebonyolításának idejét a szállításban eltöltött leghosszabb idő határozza meg.

A szokásos módon jelöljük -vel a döntési változót, amely a termelőtől az fogyasztóhoz szállítandó mennyiséget jelenti.

Matematikai megfogalmazás:

Jelölje egész szám a termelőtől az fogyasztóhoz szállítandó meennyiséget.

Meghatározandók a keresletet és a kínálatot kielégítő egész számok (a termelőktől a kínálatuknak megfelelő mennyiség legyen elszállítva és a fogyasztók a keresletüknek megfelelő mennyiséget kapjanak) úgy, hogy a

mennyiség minimális legyen.

Az olyan optimalizálási feladatokat, amelyekben a célfüggvény valamilyen maximális érték és ennek a maximális értéknek kell a minimumát keresni szűk-keresztmetszet feladatoknak nevezzük.

10.2. Algoritmus a szűk-keresztmetszetű szállítási feladat megoldására

Kézenfekvő az alábbi egyszerű algoritmus, amelynek lényege, hogy a szűk-keresztmetszetű szállítási feladatot általános Kőnig feladatok sorozatával oldjuk meg.

1. lépés: Kezdeti szállítás készítése.

Ezt végezhetjük például a legkisebb időértékeken keresztül.

2. lépés: A szállítás lebonyolítási idejének meghatározása.

Jelöljük -nal a szállítás lebonyolításának idejét, amely

tehát a tényleges szállításhoz tartozó időértékek maximuma.

3. lépés: Új szállítás készítése

Próbáljunk meg olyan új szállítást meghatározni, amelynek lebonyolítási ideje az előzőnél kisebb. Ez tulajdonképpen egy olyan általános Kőnig feladat, amelyben ott engedjük meg a szállítást, ahol . Az általános Kőnig feladat megoldhatósága szerint két esetet vizsgálunk:

  1. Ha nem tudtuk az összes árut elszállítani, akkor az előző szállítás a legjobb. Vége az algoritmusnak.

  2. Ha az összes árut elszállítottuk, akkor egy olyan új szállítást kaptunk, amelynek lebonyolítási ideje biztosan jobb (kisebb), mint az előző. A 2. és a 3. lépéseket addig ismételjük, amíg az (1) esetet nem kapjuk.

Nyilvánvaló, hogy az eljárás véges lépésben végetér.

10.3. Példamegoldás

Oldjuk meg az alábbi táblázattal adott szűk-keresztmetszetű szállítási feladatot!

1. Kezdeti szállítás és a hozzá tartozó lebonyolítási idő () meghatározása:

A kereslet-kínálatot kielégítő szállítást, úgy határozzuk meg, hogy termelőnként haladva mindig a sor legkisebb adatának cellájára, ha marad még elszállítandó a termelőtől, akkor a második legkisebb adatának cellájára, stb. programozzuk a szállítást.

2. Az általános Kőnig feladat kvalifikációs táblázata és a feladat megoldása:

Kezdeti szállítás és útkeresés címkézéssel:

Találtunk utat, a szállítás javítása:

Az összes árú el lett szállítva, ehhez a szállításhoz tartozó lebonyolítási idő () meghatározása:

3. Az általános Kőnig feladat kvalifikációs táblázata és a feladat megoldása:

Kezdeti szállítás és útkeresés címkézéssel:

Találtunk utat, a szállítás javítása:

Találtunk utat, a szállítás javítása:

Az általános Kőnig feladat nem oldható meg, nem tudjuk az összes árút elszállítani lebonyolítási időnél kevesebb idő alatt, így az lebonyolítási időhöz tartozó szállítás az optimális, amely a következő:

A szállítás legkisebb lebonyolítási ideje időegység.

10.4. FELADATOK

  1. Egy vállalat hat üzemegysége (Ü) rendre 10, 15, 8, 22, 14, 16 mennyiségben akar vásárolni öt másik vállalattól (V), amelyeknek 15, 25, 15, 15, 15 a készlete a vásárolandó anyagból. Ismertek az üzemegységek és a vállalatok között a fajlagos szállítási és értékesítési költségek összege. A vásároló vállalat úgy akarja a beszerzést megoldani, hogy a vásárlás legrosszabb fajlagos költsége is minél kisebb legyen.

  2. Adott az alábbi táblázattal az üzemek (Ü) termelése, raktárak (R) befogadóképessége, valamint az üzemek és a raktárak közötti távolság. Hogyan kell az áruknak a raktárakba történő szállítását megszervezni, hogy a szállítás során a leghosszabb út a legrövidebb legyen?

  3. Egy üzem területén négy raktárban (R) tűzveszélyes anyagot tárolnak rendre 18, 22, 34, 12 mennyiségben. Tűzriadó esetén öt pótraktárba (P) kell szállítani a tárolt anyagot, egyszerre indítva a mentést. A pótraktárak befogadóképessége rendre 32, 24, 14, 10, 6. Ismert az alábbi táblázattal, hogy az egyes raktárakból az egyes pótraktárakba mennyi idő alatt lehet eljutni. Határozza meg, hogy tűzriadó esetén 5 vagy annál rövidebb idő alatt a tűzveszélyes anyagok elszállíthatók-e a pótraktárakba? Adja meg azt a mentési stratégiát, amelynél a legrövidebb idő alatt befejeződik a mentés!

  4. Adott a termelők kínálata, a fogyasztók kereslete valamint a termelők és fogyasztók között a szállítási egységköltség. Milyen szállítás esetén tudjuk az árut elszállítani a termelőktől, ha azt akarjuk, hogy ahol tényleges szállítás van, ott a szállítási egységköltség minél kisebb legyen?

11. fejezet - Ellátási feladat

11.1. A feladat megfogalmazása

Egy beruházás során az eszközök közül választhatunk, amelyek beszerzési költsége rendre . Tudjuk azt, milyen eszközcsoportokat tud a vállalat hasznosan felhasználni. Legyenek ezek az eszközcsoportok , amelyek hasznossága rendre . Például , stb.

Az ellátási feladat megfogalmazása:

Melyik eszközöket vásárolja meg a vállalat, hogy az összhasznosság és az eszközök árának különbsége a lehető legnagyobb legyen?

11.2. A feladat matematikai vizsgálata és megoldási algoritmusa

Legyen R a megvásárlandó eszközök halmaza. Az R halmaz meghatározza a hasznos csoportokat, amelyeket jelöljön P. A maximalizálandó célfüggvény ekkor:

Ezt egyszerű átírással az alábbi minimalizálandó célfüggvénnyé alakíthatjuk:

A fenti összefüggés első tagja konstans, így azonnal adódik a minimalizálandó célfüggvény:

Ez a célfüggvény pedig nem más, mint az általános Kőnig feladat folyamproblémára visszavezetett hálózatában a vágás értéke, amit a folyamproblémában minimalizálni kell. Tehát a feladatot az általános Kőnig feladat megoldási algoritmusával oldhatjuk meg. Az ismert algoritmus az alábbi három eset valamelyikével áll meg.

  1. A minimális vágás olyan, hogy . Ekkor a Kőnig feladat megoldható és . Tehát egyik eszközt sem szabad megvenni.

  2. A minimális vágás olyan, hogy . Ekkor a Kőnig feladat nem oldható meg és . Tehát mindegyik eszközt meg kell venni.

  3. A minimális vágás az (1) és a (2) eset egyikébe sem tartozik. Ekkor a Kőnig feladat nem oldható meg és az eszközhalmaba tartozó eszközöket kell megvenni.

11.3. Példamegoldás

Egy beruházás során az eszközök közül választhatunk, amelyek beszerzési költsége rendre 6, 5, 4 pénzegység. Négy eszközcsoport hasznos a vállalatnak, ezek rendre . Az eszközcsoportok hasznossága rendre 3, 7, 4, 4 pénzegység.

Milyen eszközvásárlásnál lesz a vállalat nyeresége a legnagyobb, ha a nyereséget az elért összhasznosság és a beszerzett eszközök költségének különbségeként definiáljuk?

Megoldás:

Az ellátási feladatot az általános Kőnig feladatra vezetjük vissza, amelynek sémája az alábbi:

A megoldás lépései:

1. lépés: Induló folyam

2. lépés: Útkeresés címkézéssel

3. lépés: Folyamnövelés

Vége az algoritmusnak. A felső szegélyen csupa zérus áll, tehát a (2)-es esethez jutottunk. Eszerint mindegyik eszközt meg kell vásárolni, a tiszta nyereség pedig:

Módosítsuk a feladatot úgy, hogy az eszköz beszerzési költsége 4-ről 9-re, a eszközcsoport hasznossága pedig 4-ről 5-re változik. Természetes megoldás, hogy az elejéről elkezdjük az algoritmus végrehajtását. Mivel az adatok növekedtek, így az előző Kőnig feladat megoldását az új feladat induló megoldásaként felhasználhatjuk. Tehát az előző táblázattal folytatható az algoritmus. Módosítjuk a szegélyen az értékeket, majd címkézéssel folytatjuk a megoldást, ezt mutatja az alábbi táblázat.

Folyamnövelés és címkézést mutat az alábbi táblázat.

Vége az algoritmusnak. A (3) esethez jutottunk. A keresett R halmazt a megcímkézett eszközök adják. Tehát az eszközöket kell megvárárolni. A P halmazt a megcímkézett eszközcsoportok alkotják: . A tiszta nyereség:

11.4. Feladatok

  1. Oldja meg az alábbi sémával adott ellátási feladatot!

  2. Egy árubeszerzésnél az alkatrészekből választhatunk, amelyek beszerzési költsége rendre 9, 2, 8, 7, 5 pénzegység. Három alkatrészcsoport hasznos a vállalatnak, ezek rendre . Az alkatrészcsoportok hasznossága rendre 11, 12, 8 pénzegység. Melyik alkatrészeket vásároljuk meg, hogy az összhasznosság és az alkatrészek árának különbsége a lehető legnagyobb legyen?

12. fejezet - „Házasság” feladat (Egyszerű KŐNIG feladat)

12.1. A feladat megfogalmazása

Legyenek adottak az személyek és a munkák. Adott továbbá, hogy mely személy mely munkához ért (melyik munkára van kvalifikálva). Ezt szokás az ún. kvalifikációs táblázattal megadni oly módon, hogy az cellába *-ot teszünk, ha az személy el tudja végezni a munkát. Az egyszerű Kőnig feladatot („házasság” feladatot ) az alábbi sémával szoktuk jellemezni:

A „házasság” feladat egzisztencia formában:

Hozzárendelhető-e a összes személy a munkákhoz az alábbi feltételekkel:

  • a személy értsen a munkához,

  • egy munkát csak egy személy láthat el?

A feladatot az alábbi megfogalmazás miatt nevezik „házasság” feladatnak. Legyenek adottak férfiakat és nők, akik között ismert a rokonszenv (szimpátia) táblázat. A kérdés annak eldöntése, hogy minden férfi meg tud-e nősülni úgy, hogy rokonszenves nővel kössön házasságot, kizárva a poligámiát.

A legtöbb esetben azonban nem csak arra vagyunk kíváncsiak, hogy megoldható-e a hozzárendelés, amennyiben nem tudjuk az összes személyt hozzárendelni, akkor jó lenne tudni, hogy maximálisan hány személy rendelhető a munkákhoz. Ha a személyek száma meghaladja a munkák számát, akkor eleve nem lehet az összes személyt hozzárendelni a munkákhoz, tehát az egzisztencia formában megfogalmazott feladat megoldása triviális, nem triviális azonban az olyan kérdésfelvetésre, hogy maximálisan hány személy rendelhető a munkákhoz.

A „házasság” feladat optimalizálási formában:

Maximálisan hány személy rendelhető a munkákhoz az alábbi feltételekkel:

  • a személy értsen a munkához,

  • egy személy csak egy munkához rendelhető,

  • egy munkát csak egy egy személy láthat el?

Mielőtt a feladat megoldására vonatkozó fontos állítást kimondanánk, ennek előkészítésére vezessük be az alábbi jelöléseket.

Legyen a személyek, a munkák halmaza. Jelölje a személyek egy tetszőleges részhalmazát és jelölje azon munkák halmazát, amelyekhez a P-beli személyek együttesen értenek. Jelölje továbbá a P-beli személyek számát, a -beli munkák számát.

Példaként tekintsük az alábbi kvalifikációs táblázattal adott egyszerű Kőnig feladatot:

Ha , ekkor , , .

12.2. A feladat matematikai vizsgálata

A „házasság” feladat egzisztencia formájára vonatkozik az alábbi tétel.

KŐNIG tétel

Adott kvalifikációs táblázat esetén

  • vagy az összes személyt el lehet látni munkával,

  • vagy van a személyeknek olyan részhalmaza, hogy .

Más szavakkal megfogalmazva: vagy az összes személy hozzárendelhető a munkákhoz, vagy ha nem, akkor megadható a személyeknek olyan részhalmaza, hogy ezen személyek száma meghaladja azon munkák számát, amelyeket együttesen el tudnak látni.

Nem nehéz belátni, hogy a „házasság” feladat az általános Kőnig feladatnak olyan speciális eseteként fogható fel, ahol minden és minden . Ezért a tétel bizonyítását nem ismételjük meg. A bizonyításban szereplő folyamfeladatban az 1 értékű kapacitások miatt az típusú éleken a folyam csak 0 vagy 1 lehet. Ha az élen a folyam 1, akkor az személy hozzá van rendelve a munkához, 0 folyam esetén nincs.

A ”házasság” feladat egzisztencia formájára kimondott KŐNIG tétel átfogalmazható a következőképpen

KŐNIG tétel (más formában):

Adott kvalifikációs táblázat esetén az összes személy munkához való hozzárendelhetőségének szükséges és elégséges feltétele az, hogy minden személy esetén

Természetesen a két egzisztencia tétel ekvivalens egymással, az először megfogalmazott viszont a alaptételünkhöz, a MINTY tételhez hasonló szerkezetű.

12.3. Kőnig-Egerváry tétel

Az általános Kőnig feladatnál ismertetett lefedési probléma itt is értelmezhető a következők szerint. A „házasság” feladatban a fedővonalrendszer súlyszáma a fedővonalak számának, a folyamfeladat maximuma pedig a hozzárendelések maximális számának felel meg. Legyen adott egy táblázatunk, amelyben *-ok szerepelnek. Fedővonalrendszer alatt a táblázat bizonyos sorainak ill. oszlopainak egy-egy vonallal való lefedését értjük.

Lefedési feladat:

Fedjük le a táblázatban szereplő összes *-ot a legkevesebb számú fedővonalrendszerrel!

A FORD-FULKERSON tétel átfogalmazása szerint a fedővonalak minimális száma megegyezik a hozzárendelések maximális számával. Ezt a tételt KŐNIG-EGERVÁRY tétel [1], [9] néven ismeri a szakirodalom. A történeti hűséghez hozzátartozik, hogy a KŐNIG-EGERVÁRY tétel az 1930-as években keletkezett, míg a folyamokra vonatkozó FORD-FULKERSON tétel az 1960-as években lett kidolgozva. Mi tárgyalásmódunk fordított, az általánosabb tételből vezetjük le az egyébként nagy horderejű KŐNIG-EGERVÁRY tételt. Ennek a tételnek fontos szerepe volt a „magyar módszer” kidolgozásánál.

A történeti hűség miatt az alábbiakban közöljük az 1930-as években már ismert, vonatkozó eredményeket:

Tekintsünk egy -es mátrixot, amelynek elemei 0 és 1. Az 1-esek egy részhalmazát függetlennek nevezzük, ha nem fekszik kettő közülük ugyanazon sorban ill. oszlopban. Fedővonalrendszer alatt az összes 1-est lefedő vonalakat (vízszintes vagy függőleges) értjük.

LEMMA:

A független 1-esek száma nem lehet nagyobb az összes 1-est lefedő fedővonalak számánál.

KŐNIG-EGERVÁRY tétel:

A független 1-esek maximális száma megegyezik az összes 1-est lefedő fedővonalak minimális számával.

Tehát akár a maximális független 1-esek, akár az összes 1-est lefedő vonalak minimális számának meghatározása a feladatunk, az alábbiakban ismertetésre kerülő algoritmussal megkapjuk az eredményt.

12.4. Algoritmus a „házasság” feladat megoldására

Mivel a „házasság” feladat egy speciális általános Kőnig feladat, így a megoldási algoritmusa is ugyanaz. A feladat specialitása miatt az algoritmus kissé egyszerűsíthető, ezt az alábbiakban ismertetjük.

  • A folyamproblémában, amelyre visszavezettük a feladatot, a folyam csak 0 vagy 1 lehet, ezért az 1-nek megfelelő folyamot, azaz a hozzárendelést a * jel bekarikázásával () célszerű jelölni. A bal és a felső szegély elhagyható, hisz felesleges külön jelölni, hogy mely személyeknél ill. munkáknál nincs még hozzárendelés.

  • A kezdeti folyamot (kezdeti hozzárendelést) az Észak-Nyugati sarok módszeren kívül szokás úgy végezni, hogy a kevés *-ot tartalmazó sorokban ill. oszlopokban végezzük el először a hozzárendelést.

  • A címkézésnél pedig az alábbiakra ügyeljünk:

    • Induláskor azokat a személyeket címkézzük meg „-s”-el, akik még nincsenek hozzárendelve munkákhoz.

    • Azokhoz a munkákhoz kell eljutni az útkeresés során, amely munkákhoz még nincs személy hozzárendelve.

    • Az útkeresés során személytől minden olyan munkához mehetünk, ahol nincs tiltva a hozzárendelés, azaz ahol a táblázatban * vagy jel áll. Viszont munkától személyhez csak olyan cellán mehetünk, amelyben jel áll.

12.5. Példamegoldás

1. példa.

Oldjuk meg az alábbi „házasság” feladatot!

0. lépés: Kezdeti hozzárendelés meghatározása É-Ny-i sarok módszerrel.

1. lépés: Útkeresés címkézéssel

Találtunk utat, az út a címkéken visszafelé haladva a következő:

Az út élei alatti sorokban a szabad kapacitást és az élek megszokott jelöléseit is megadtunk.

Az út mentén értéke nyilvánvalóan csak 1 lehet. A szokásos módon a -el jelölt cellákon csökkentjük, a -el jelölteken pedig növeljük a folyamot. A csökkentés azt jelenti, hogy ott a létező hozzárendelést megszüntetjük, a növelés pedig új hozzárendelést jelent. A továbbiakban nem írjuk le külön az utat és nem is jelöljük be a táblázatba a megszokott és szimbólumokat, hanem az út (címkék segítségével való) meghatározása során azonnal elvégezzük a régi hozzárendelés megszüntetését ill. az új hozzárendelés felvételét. Itt is igaz, hogy az út egy törtvonal és végpontjain felváltva történik hozzárendelés felvétel és megszüntetés, felvétellel kezdve és befejezve is. A hozzárendelés javítását a következő táblázat mutatja:

Vége az algoritmusnak, mert az összes személyt hozzárendeltük a munkákhoz. A hozzárendelés a táblázatból kiolvasható.

2. példa:

Oldjuk meg az alábbi „házasság” feladatot!

0. lépés: Kezdeti hozzárendelés meghatározása.

Most nem az Észak-Nyugati sarok módszerrel végezzük az induló hozzárendelést, hanem a kevés *-ot tartalmazó sorokban és oszlopokban kezdjük az induló hozzárendelés meghatározását. Először a 3. személy hozzárendelését végeztük el, mivel az csak egy munkához rendelhető, másodszor az 5. személy hozzárendelése következik, mert már az előző hozzárendelést figyelembevéve szintén csak egy munkához rendelhető, utána a 6. személy következett, mert ő a többi személyhez képest kevesebb munkához rendelhető, ezekután a 2., majd a 4. személy következett.

1. lépés: Útkeresés címkézéssel

Vége az algoritmusnak, mert nem találtunk utat, így nem tudjuk tovább javítani a hozzárendelést. Arra az eldöntendő kérdésre, hogy az összes személy hozzárendelhető-e a munkákhoz, a válasz nem, mivel 1 személyt semmiképpen sem lehet hozzárendelni. Arra a kérdésre, hogy maximálisan hány személy rendelhető a munkákhoz szintén megkaptuk a választ, 1 híján az összeset, tehát 5 személyt. Az algoritmus azt is megmutatja, hogy a lehető legtöbb személy hozzárendelését milyen módon biztosíthatjuk. Ez a fenti táblából kiolvasható. Elképzelhető természetesen más hozzárendelés is, azonban 5-nél több személy semmiképpen nem rendelhető a munkákhoz. Mivel az összes személyt nem lehet hozzárendelni, így a „házasság” feladatra vonatkozó KŐNIG tétel értelmében meghatározhatók a személyek és munkák P és R halmazai. A P és R halmazba a megcímkézett személyek ill. munkák tartoznak, azaz

A P-beli személyek és az R-beli munkák száma pedig

Tehát , ahogy ezt a KŐNIG tétel állította. Valóban nem lehet az összes személyt hozzárendelni a munkákhoz, hiszen már a P-beli 3 személy mindegyikét sem tudjuk hozzárendelni, mert csupán 2 olyan munka van, amelyekhez a P-beliek hozzárendelhetők.

Végezetül a lefedést is elvégezhetjük, mégpedig a nem P-beli (címkézetlen) sorokat és az R-beli (címkézett) oszlopokat fedjük le. Látható, hogy a fedetlen helyeken nincs *, így minden * le lett fedve. A kétszer fedett helyeken nincs hozzárendelés, vagyis hozzárendelés csak egyszer fedett helyen lehet.

12.6. Feladatok

  1. Tegyük fel, hogy 5 feladatunk (F) van, ezeket 6 vállalat (V) között kell szétosztanunk. Egy-egy vállalat a feladatok közül csak bizonyosakat tud elvégezni és ezek közül is csak egyet vállal. Döntsük el, lehetséges-e a feladatok szétosztása; ha nem lehetséges, akkor osszunk szét a feladatokból annyit amennyit csak tudunk. A vállalatok az alábbi feladatokat tudják elvállalni: ; ; ; ; ; .

  2. Oldja meg az alábbi kvalifikációs táblázattal adott „házasság” feladatot!

    a) Az induló hozzárendelést Észak-Nyugati sarok módszerrel végezze!

    b) Az induló hozzárendelést a minimális * elv alapján végezze!

  3. Adott az alábbi táblázat.

    a) Válassza ki a lehető legtöbb *-ot úgy, hogy minden sorban és oszlopban legfeljebb egy *-ot választhat!

    b) Fedje le az összes *-ot a lehető legkevesebb fedővonallal!

  4. Adott az alábbi számtáblázat.

    a) Fedje le a táblázat összes 5-nél kisebb elemeit minimális számú vonallal!

    b) Fedje le a táblázat összes 5-nél nagyobb elemeit minimális számú vonallal!

    c) Válassza ki a lehető legtöbb 4-nél kisebb számot úgy, hogy minden sorban és oszlopban legfeljebb egy szám választható!

13. fejezet - „Futószalag” feladat

13.1. A feladat megfogalmazása

Jelölje a személyeket, pedig egy futószalagon lévő munkahelyeket (munkákat). Legyen adva az alábbi táblázat, amelynek (egész) eleme azt jelenti, hogy az munkás a munkát mennyi idő alatt tudja elvégezni. A személyek és a munkák számának azonosnak kell lenni!

A „futószalag” feladat az alábbi sémával jellemezhető:

Mielőtt a feladatot megfogalmaznánk definiáljuk a futószalag ütemidejét. A futószalag addig áll, amíg a futószalag munkahelyein munkavégzés folyik, amikor minden munka befejeződött, akkor a futószalag továbblép. Ezt az állásidőt nevezzük a futószalag továbbítási ütemének vagy röviden a futószalag ütemidejének. A futószalag ütemidejét tehát a futószalagon lévő munkák közül a leghosszabb műveleti idejű határozza meg.

A „futószalag” feladat megfogalmazása:

Rendeljük a személyeket a futószalag munkahelyeihez kölcsönösen egyértelmű módon úgy, hogy a futószalag ütemideje a lehető legkisebb legyen.

A hozzárendelést a szokásos módon olyan döntési változóval jelöljük, amelynek értéke , ha az személy hozzá van rendelve a munkához és , ha nincs.

Matematikai megfogalmazás:

Jelölje a kölcsönösen egyértelmű hozzárendelést.

Meghatározandó a kölcsönösen egyértelmű hozzárendelés úgy, hogy a

mennyiség minimális legyen.

Az olyan optimalizálási feladatokat, amelyekben a célfüggvény valamilyen maximális érték és ennek a maximális értéknek kell a minimumát keresni szűk-keresztmetszet feladatoknak nevezzük.

13.2. Algoritmus a „futószalag” feladat megoldására

Kézenfekvő az alábbi egyszerű algoritmus, amelynek lényege, hogy a „futószalag” feladatot „házasság” feladatok sorozatával oldjuk meg.

1. lépés: Kezdeti hozzárendelés készítése ().

Ezt végezhetjük például a legkisebb időértékeken keresztül.

2. lépés: A hozzárendeléshez tartozó ütemidő meghatározása.

Jelöljük -al a futószalag ütemidejét, amely

tehát a hozzárendelésben szereplő idők maximuma.

3. lépés: Új hozzárendelés készítése.

Próbáljunk meg olyan új hozzárendelést készíteni, amelynél a futószalag ütemideje az előzőnél kisebb. Ez tulajdonképpen egy olyan „házasság” feladat, amelyben ott lehetséges a hozzárendelés, ahol . A „házasság” feladat megoldhatósága szerint két esetet vizsgálunk:

  1. Ha nem tudtuk az összes személyt hozzárendelni a munkákhoz, akkor az előző hozzárendelés a legjobb. Vége az algoritmusnak.

  2. Ha minden személyt hozzá tudtunk rendelni a munkákhoz, akkor egy olyan új hozzárendelést kaptunk, amelyhez tartozó ütemidő biztosan jobb (kisebb), mint az előző. A 2. és a 3. lépéseket addig ismételjük, amíg az (1) esetet nem kapjuk.

Nyilvánvaló, hogy az eljárás véges lépésben végetér.

13.3. Példamegoldás

Oldjuk meg az alábbi időtáblázattal adott „futószalag” feladatot:

1. Kezdeti Hozzárendelés és a hozzá tartozó ütemidő () meghatározása:

Az induló hozzárendelést úgy határozzuk meg, hogy személyenként haladva mindig a sor legkisebb adatának cellájára programozzuk a hozzárendelést.

2. A „házasság” feladat kvalifikációs táblázata és a „házasság” feladat megoldása:

Kezdeti hozzárendelés majd útkeresés címkézéssel:

Találtunk utat, a hozzárendelés javítása és útkeresés címkézéssel:

    Találtunk utat, a hozzárendelés javítása:

A „házasság” feladatot megoldottunk, az összes személy hozzá lett rendelve a munkákhoz. Ehhez a hozárendeléshez tartozó ütemidő () meghatározása:

3. A „házasság” feladat kvalifikációs táblázata és a feladat megoldása:

Ez a „házasság” feladat nem oldható meg, nem tudjuk az összes személyt hozzárendelni, hiszen az személy senkihez sem rendelhető. Tehát ütemidőnél kisebb időhöz tartozó hozzárendelés nincs, így az ütemidőhöz tartozó hozzárendelés az optimális, amely a következő:

Az ütemidő időegység.

13.4. Feladatok

  1. Oldjuk meg az alábbi időtáblázattal adott „futószalag” feladatot!

  2. Egy tervezőiroda egy cégtől öt feladatot (F) kap. Az iroda vezetője kiválasztja azt az öt tervezőt (T), akik elkezdhetik az egyébként független munkák elvégzését. A kiválasztott tervezők felkészültségének és a munkában mutatott intenzitásának figyelembevételével a feladatok megoldásához szükséges idő napokban kifejezve az alábbi táblázattal van megadva. Hogyan érdemes az irodavezetőnek szétosztani a feladatokat a tervezők között, ha az a célja, hogy az öt munkából álló megbízást minél hamarabb teljesítse?

  3. Adott hat gép (G), amely hat alkatrésztípus (A) mindegyikét képes gyártani. Az alábbi táblázat azt mutatja, hogy az egyes gépeken egy-egy alkatrésztípusból egy sorozatot mennyi idő alatt lehet megmunkálni. Minden alkatrésztípusból egy sorozatot kell legyártani. Hogyan kell a gyártást megszervezni (melyik gép melyik alkatrésztípust gyártsa), ha azt akarjuk, hogy a gyártás minél rövidebb ideig tartson feltéve, hogy

    a) minden gépen egyszerre kezdődik a gyártás,

    b) az alkatrésztípusok megmunkálását egymás után kezdjük? (Vigyázat, mert ez utóbbi nem „futószalag” feladat!)

  4. Adott az alábbi számtáblázat. Válasszunk ki öt számot úgy, hogy minden sorból és oszlopból csak egy számot választhatunk és a kiválasztott számok közül a legnagyobb a lehető legkisebb legyen!

  5. A gépeken az alkatrésztípusokból egy óra alatt az alábbi táblázat által adott termékmennyiség (darab) készíthető el. Mindegyik alkatrésztípusból egy 120 darabot tartalmazó alkatrészsorozatot kell legyártani. Hogyan osszuk el a munkát, ha a gépek és az alkatrészek között kölcsönösen egyértelmű megfeleltetést akarunk létrehozni és azt akarjuk, hogy a négy alkatrészsorozat egymástól függetlenül, egyszerre kezdhető legyártásához szükséges átfutási idő minimális legyen?

  6. Egy város pontján egy-egy azonos típusú teherautó áll rendelkezésünkre. A város pontján egy-egy ugyanilyen típusú autóra jelentkezik egy-egy igénylő. Milyen utasítást adjunk ki, ha a négy autót a lehető leghamarabb szeretnénk az igénylőkhöz eljuttatni feltéve, hogy egyidőben indítjuk mind a négy autót? Az alábbi táblázat a megfelelő pontok közötti távolságokat mutatja és feltételezzük, hogy az idő arányos a távolsággal.

  7. Három olajkút (K) termékét eladhatjuk nyersanyagként (N) vagy részben finomított nehézolajként (F) vagy pedig finomított benzinként (B). Az iparnak mindhárom termékre szüksége van. Az egyes olajkutak termékeit csak egyfajta módon érdemes értékesíteni. Az alábbi táblázat mutatja, hogy az egyes kutakból az egyes termékek milyen fajlagos költséggel állíthatók elő. Készítsen optimális gyártási tervet, ha az a célunk, hogy a legkedvezőtlenebb fajlagos előállítási költség a lehető legkisebb legyen!

  8. Egy vállalat hat feladatát (F) hat másik vállalat (V) az alábbi táblázat szerint megadott határidővel tudja elvégezni (az időt napokban adtuk meg). Mely vállalatokat kell megbízni az egyes feladatok elvégzésével (egy vállalat csak egy feladatot vállal el), hogy a feladatok minél hamarabb készüljenek el?

14. fejezet - Szállítási feladat

14.1. A szállítási feladat megfogalmazása

Legyenek adottak a termelők (vagy termelőhelyek), amelyek rendre kínálattal rendelkeznek és az fogyasztók (vagy fogyasztóhelyek), amelyek kereslete (igénye) rendre . Legyenek továbbá adottak a szállítás egységköltségek, amelyek a termelőtől az fogyasztóhoz történő egységnyi mennyiségú árú szállításának költségét jelentik. A megadott adatok legyenek nemnegatív egészek. A szállítási feladat az alábbi sémával jellemezhető:

Tegyük fel, hogy az összkínálat egyenlő az összkereslettel, azaz

Ezt az összefüggést a kereslet-kínálat egyensúlyának is szokás nevezni.

Az alábbiakban megfogalmazzuk a szállítási feladatot (ezt nevezzük primál feladatnak), majd ezután a szállítási feladat duál feladatát ismertetjük.

A szállítási feladat (primál feladat):

Határozzuk meg azt a szállítást, amely a keresletet és a kínálatot kielégíti és a szállítási összköltség minimális feltéve, hogy a szállítási költség arányos a szállítási mennyiséggel.

A feladat tehát feltételezi a linearitást. Talán jobban érthető a feladat, ha a kínálatok és a keresletek rakományban vannak kifejezve és a szállítási egységköltség egy rakomány elszállításának költségét jelenti.

Jelölje a termelőtől az fogyasztóhoz szállítandó mennyiséget. A kínálat kielégítése azt jelenti, hogy minden termelőtől a kínálatának megfelelő mennyiséget kell elszállítani, azaz bármelyik termelőtől az összes fogyasztóhoz szállított mennyiség összege egyenlő legyen a termelő kínálatával. A kereslet kielégítése pedig azt jelenti, hogy minden fogyasztóhoz az igényének megfelelő mennyiségű árut kell szállítani, azaz bármelyik fogyasztóhoz az összes termelőtől szállított mennyiség összege egyenlő legyen az fogyasztó keresletével. A kínálat és a kereslet kielégítése maradéktalanul teljesíthető a kereslet-kínálat egyensúlya miatt. A szállítási összköltséget pedig a linearitás miatt a szállított mennyiségek és a szállítási egységköltségek szorzatának az összege adja.

A szállítási feladat matematikai megfogalmazása:

Meghatározandók az egész számok úgy, hogy

feltételek teljesülése mellett a

mennyiség minimális legyen.

A szállítási feladat duál feladata:

Az eredeti feladatot a termelőknek kell megoldaniuk, vagyis az árukat a fogyasztókhoz elszállítani. Tételezzük fel, hogy van egy vállalkozó, aki a termelőtől áron felvásárolja az áru egységét, majd elszállítja az fogyasztóhoz és ott áron eladja (visszaadja) a termelőnek. Nyilván az , felvásárlási, ill. eladási egységáraknak olyannak kell lenniük, hogy a termelőknek megérje a vállalkozóval való szállítás. A termelőnek az fogyasztóhoz való szállításnál akkor éri meg igénybe venni a vállalkozó szolgáltatását, ha így nem kerül többe a szállítás, mintha maga végezné a termelő, azaz minden lehetséges szállítási viszonylatban fenn kell állnia a összefüggésnek.

Ha tehát biztosítva van a fenti feltétellel, hogy a vállalkozó kapja meg az összes szállítást, akkor a vállalkozó a fenti összefüggéseket kielégítő árrendszert úgy fogja megválasztani, hogy a szállítással elért haszna a legnagyobb legyen, amit a bevételeinek és a kiadásainak a különbsége ad meg. Ezek után a szállítási feladat duál feladatának matematikai megfogalmazása a következő:

Meghatározandók az és egész számok úgy, hogy

feltételek teljesülése mellett a

mennyiség maximális legyen.

14.2. A feladatpár matematikai vizsgálata

Először a szállítási feladat primál és duál feladatának célfüggvényértékei közötti kapcsolatot, majd az optimalitási kritériumot és végül a feladatpár megoldhatóságára vonatkozó dualitási tételt közöljük bizonyításaikkal együtt.

A SZÁLLÍTÁSI FELADATPÁR ALAPLEMMÁJA:

Ha az lehetséges szállítás (azaz kielégíti a primál feladat feltételeit) és lehetséges árrendszer (azaz kielégíti a duál feladat feltételeit), akkor

Bizonyítás.

Az egyébként egyszerű bizonyítás során először a duál feltételeket, majd sorra a primál feltételek használjuk fel:

Az első egyenlőtlenségnél felhasználtuk az nemnegativitását. A továbbiakban pedig az összeadandókat átrendeztük és kiemelést végeztünk, majd a többi primál feltételt használtuk fel.

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha az lehetséges szállítás és az lehetséges árrendszer olyan, hogy a hozzájuk tartozó primál és duál célfüggvényértékek megegyeznek, akkor ez a szállítás és ez az árrendszer egyben optimális megoldás is.

Bizonyítás.

Jelölje és azt a primál és duál lehetséges megoldást, amelyekre

Legyen tetszőleges, lehetséges szállítás. A lemma alapján

figyelembevéve a *-gal jelölt változókhoz tartozó célfüggvényértékek megegyezését, kapjuk, hogy

Ez utóbbi egyenlőtlenség éppen azt fejezi ki, hogy az primál lehetséges megoldás optimális megoldás. Hasonlóan igazolható, hogy az duál lehetséges megoldások szintén optimális megoldások. Ennek igazolását az olvasóra bízzuk.

A soron következő második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (Optimalitási kritérium):

A két feladat célfüggvényértéke akkor és csak akkor egyezik meg (azaz lemmában egyenlőség akkor és csak akkor áll fenn), ha minden indexpárra

Bizonyítás.

Ez a lemma bizonyításából egyszerűen kiolvasható, ugyanis a két oldal akkor és csak akkor lehet egyenlő, ha a bizonyításban szereplő egyenlőtlenség egyenlőséggel teljesül, azaz

amelyből átrendezéssel kapjuk, hogy

Mivel a fenti összeg minden tagjában mindkét tényező a primál és a duál feltételek miatt nemnegatív, ezért az összeg mindegyik tagja nemnegatív. Nemnegatív számok összege pedig akkor és csak akkor lehet zérus, ha mindegyik tagja zérus, azaz minden (i, j) indexpárra

A SZÁLLÍTÁSI FELADATPÁR DUALITÁSI TÉTELE:

Mind a primál, mind a duál feladatnak létezik optimális megoldása és a primál feladat célfüggvényértékének minimuma megegyezik a duál feladat célfüggvényértékének maximumával, azaz

Bizonyítás.

A tétel bizonyítása konstruktív bizonyítás, amely azt jelenti, hogy az optimális megoldásoknak nemcsak a létezését igazolja, hanem a bizonyítás menete egyben algoritmust is szolgáltat az optimális megoldások meghatározására. A bizonyításból kiolvasható algoritmus „magyar módszer” néven ismeretes. Az elnevezés H. W. KUHN-tól származik, aki ezzel kívánt emléket állítani két kiváló magyar matematikusnak. Az algoritmus „magyar” eredetére a későbbiekben még visszatérünk.

Legyenek adottak az lehetséges duál változók, amelyek kielégítik a feltételeket, azaz minden (i, j) indexpárra. A későbbiekben egyszerűsíti a jelöléseinket, ha bevezetjük az mennyiségeket. Ez az egyrészt a duál változók értékétől függő mennyiség, másrészt pedig a szállítási egységköltség módosított értéke, szokás ezért redukált szállítási egységköltségnek vagy röviden redukált költségnek is nevezni. Az optimalitási kritériumot, így az

összefüggéssel fogalmazhatjuk meg. Ez azt jelenti, hogy optimális esetben csak ott engedélyezett a szállítás, ahol . Kíséreljük meg az összes árut elszállítani a termelőktől a fogyasztókhoz úgy, hogy az optimalitási kritérium teljesüljön. Az csak akkor teljesedik, ha csak olyan cellákon engedélyezzük a szállítást, amelyekben . Tulajdonképpen egy általános Kőnig feladatot kell megoldanunk. Az ottani jelöléseknek megfelelően * ott van, ahol szabad a szállítás (), az cellákon pedig tiltás van.

Az általános Kőnig feladatot a vonatkozó algoritmus használatával megoldjuk és a KŐNIG tétel értelmében két esetet vizsgálunk.

1.eset:

Ha az általános Kőnig feladat megoldható, vagyis az összes árut el tudjuk szállítani, akkor ez a szállítás optimális is egyben, hisz az optimalitás követelménye teljesül. Vége az algoritmusnak.

2. eset:

Ha az általános Kőnig feladat nem oldható meg, akkor viszont a KŐNIG tétel értelmében megkapjuk a termelők P és a fogyasztók R halmazát, amelyekre mint tudjuk fennáll, hogy

Ha a P és az R halmazok segítségével elvégezzük a szokásos lefedést, akkor a KŐNIG tételből adódóan az alábbi táblázatban látható összefüggések is érvényesek:

A következő lépésben új és duál változókat határozunk meg, amelyek

  1. teljesítik a duál feltételeket és

  2. a duál célfüggvénynek az új értéke nagyobb az előzőnél.

Az új duál változók meghatározásához először határozzuk meg a fedetlen cellákban lévő redukált költségek minimumát, jelöljük ezt a számot -al:

Mivel az szám pozitív számok minimuma, így . Ennek az számnak és a P, R halmazoknak a segítségével az új és duál változókat az alábbiak szerint határozzuk meg:

Ezek az új duálváltozók az megfelelő választása miatt kielégítik a duál feltételeket. Másképpen fogalmazva az új duál változókkal számolt új redukált költségek is nemnegatívok, azaz

minden (i, j) indexre.

Vizsgáljuk meg, hogy ez valóban teljesedik-e. A P, R halmazokkal particionált tábla négy blokkjára blokkonként külön megvizsgáljuk:

  1. Ha és , akkor .

  2. Ha és , akkor .

  3. Ha és , akkor , az pozitivitása miatt.

  4. Ha és , akkor , az definíciója miatt.

A fentiekből kiolvasható, hogy az új redukált költségek számítása a lefedés segítségével nagyon egyszerűen elvégezhető, nevezetesen

  • fedetlen helyen értékével csökkenteni kell,

  • kétszer fedett helyen értékével növelni kell,

  • egyszer fedett helyen változatlanul kell hagyni.

Miután beláttuk, hogy az új duál változók valóban megengedettek, meghatározhatjuk a hozzájuk tartozó duál célfüggvény értékét:

Mivel és a KŐNIG tétel értelmében a kifejezésben az szorzója pozitív, ezért a duál célfüggvény új értéke valóban nagyobb, mint az előző célfüggvényérték. Az új duálváltozókkal megismételjük a fenti lépéseket, azaz megpróbáljuk megoldani az új általános Kőnig feladatot, ott megengedve a szállítást, ahol az új redukált költségek értéke zérus.

Mivel mindegyik , valamint az is egész szám, ezért a duál célfüggvény értéke egész számmal növekszik. A lemma alapján tudjuk, hogy a duál célfüggvény korlátos felülről, mindezekből következik, hogy az eljárás véges sok lépésben végetér.

A szállítási feladat először HITCHOCK F.L. munkájában [7] található, ezért szokás HITCHOCK feladatnak is nevezni. A szállítási feladat lineáris programozási módszerrel is megoldható. A folyamok segítségével történő megoldási módszert, a dualitási tétel konstruktív bizonyítását FORD L. R. Jr. és FULKERSON D.R. [5] adták meg.

14.3. Algoritmus a szállítási feladat megoldására. A „magyar módszer”

Az algoritmus a fenti tétel konstruktív bizonyításából kiolvasható. Két dolgot kell csupán megbeszélnünk, egyik az algoritmus indításával, másik az általános Kőnig feladattal kapcsolatos. Az algoritmus indításához lehetséges duál változókat kell meghatározni. A kezdeti lehetséges duál változókat sokféleképpen meghatározhatjuk. Arra kell csupán ügyelnünk, hogy az és duál változók olyanok legyenek, hogy a belőlük számított redukált költség legyen. Jó lenne olyan redukált költségekből kiindulni, amelyek egyrészt egyszerűen számolhatók, másrészt sok zérus van közöttük. Ez utóbbi azért fontos, mert akkor már az induló Kőnig feladatban sok szabad hely lesz. Alakítsuk át -t az alábbi formára:

Ha a értékeket olyanra választjuk, hogy azokat a -ből levonva nemnegatív eredményt kapunk és a értékeket pedig olyanra választjuk, hogy azokat a -ből levonva szintén nemnegatív eredményt kapunk, akkor az redukált költség nemnegatív marad. Elvileg nagyon sok ilyen , választás lehetséges. A legjobb ilyen választás az, amikor a redukált költségeket úgy kapjuk meg, hogy a költségmátrix minden sorából a sor legkisebb elemét vonjuk ki és az eredménymátrix minden oszlopából pedig az oszlop legkisebb elemét vonjuk ki. A redukált költségek ilyen módon való meghatározásánál a sorokon végrehajtott műveletet sorredukciónak, az oszlopokon végrehajtott műveletet pedig oszlopredukciónak nevezzük. Ezzel a sor- és oszlopredukcióval olyan megengedett induló redukált költségmátrixot kapunk, amely azzal a jó tulajdonsággal bír, hogy minden sorában és oszlopában van legalább egy zérus.

Természetesen elfogadható más induló redukált költségmátrix is. Például végezhetünk csak sorredukciót vagy csak oszlopredukciót vagy először oszlopredukciót, majd utána sorredukciót vagy az is elképzelhető, hogy nem redukáljuk a költségmátrixot. Javasoljuk az olvasónak, hogy a „magyar módszer” begyakorlásánál egy feladatot többféle indulással is végezzen el.

Az általános Kőnig feladatban ott szabad szállítani, ahol a redukált költség zérus. Az általános Kőnig feladat megoldási algoritmusa az előzőekből már ismert, így az nem jelent különösebb problémát. Induló szállítást kell meghatározni majd a szállítást javítani útkeresésekkel. Ha nem sikerült elszállítani az összes árut a termelőktől, akkor a kiadódó P, R halmazok alapján elvégezzük a lefedéseket és ezek segítségével egy számot határozunk meg, amely a fedetlen helyeken lévő redukált költségek minimuma. Ezután, mint ahogy ezt a bizonyításnál láttuk ezzel az számmal az alábbiak szerint módosítjuk a redukált költségeket:

  • az redukált költségeket a fedetlen helyen értékkel csökkentjük,

  • az redukált költségeket a kétszer fedett helyen értékkel növeljük,

  • az redukált költségeket az egyszer fedett helyen változatlanul hagyjuk.

Megjegyezzük, hogy az algoritmus során valójában a duál változókat nem használjuk, nem érdemes ugyanis kiszámítani őket, mivel csak az redukált költségekre van szükségünk. A duál változók egyébként burkoltan benne vannak a redukált költségekben.

Az új redukált költségekkel újra megoldunk egy általános Kőnig feladatot. Ennek megoldása szintén egy induló szállítás meghatározásával kezdődik. A Kőnig feladatnál elmondottakból tudjuk, hogy szállítás csak egyszer fedett helyeken lehet és az előzőekből pedig azt tudjuk, hogy az egyszer fedett helyeken nem változott a redukált költség, így az előző általános Kőnig feladatban kapott szállítás egyben az új Kőnig feladat induló szállítása lehet. Természetesen minden egyes általános Kőnig feladat induló szállítását az Észak-Nyugati sarok módszerrel is meghatározhatjuk, de az előbb említett lehetőség lehetővé teszi ennek mellőzését.

Ne feledkezzünk meg azonban arról, hogy a fent ismertetett „magyar módszer” csak standard szállítási feladat megoldására szolgál, azaz csak akkor alkalmazható, ha az összkínálat és az összkereslet egyenlő egymással. Ezért a megoldás 0. lépésében ellenőrizni kell a kereslet-kínálat egyensúlyát. Amennyiben nem standard szállítási feladattal van dolgunk, akkor először standard szállítási feladattá kell alakítani, ennek megvalósítására egy külön szakaszban visszatérünk.

A következő folyamatábrán a szállítási feladat „magyar módszerrel” történő megoldásának menetét vázoljuk fel:

14.4. Nem standard szállítási feladat kezelése

Az előzőekben ismertetett szállítási feladatra az ún. standard alakúra dolgozták ki a „magyar módszert”. A gyakorlatban sok esetben a szállítási feladat különböző variánsaival találkozunk. Ezeket is a „magyar módszerrel” fogjuk megoldani, de a módszer alkalmazásához a feladatot standard alakra kell hozni. Három különbőző esetet vizsgálunk, természetesen ezek egyidejűleg is előfordulhatnak egy feladat kapcsán.

  1. Egyedi tiltások kezelése.

    Ha valamely viszonylatban valamilyen oknál fogva a szállítás nem lehetséges (útjavítás, szerződés hiánya, stb.), akkor úgy járunk el, hogy a szállítási egységköltséget nagyon nagyra választjuk. Kézi számolásnál szokásos az M jelölés.

  2. Nem teljesül a kereslet-kínálat egyensúlya.

    Két esetet különböztetünk meg, attól függően, hogy a kínálat vagy a kereslet a nagyobb. Mindkét esetben standard feladatra kell alakítanunk a feladatot, amelyben már a kereslet-kínálat egyensúlya fennáll.

    • Az összkereslet meghaladja az összkínálatot.

      Ekkor egy ún. fiktív vagy virtuális termelőt iktatunk be szállítási egységköltségekkel és kínálattal. Könnyen ellenőrizhető, hogy így standard feladatot kaptunk és ennek optimális megoldása megegyezik az eredeti feladat optimális megoldásával.

      Az eredeti feladat optimális megoldásában biztosan lesznek olyan fogyasztók, amelyeknek az igénye nem lesz kielégítve. Ha olyan nem standard szállítási feladatunk van, amelyben például az fogyasztó igényét valamilyen ok (gazdasági érdek, egészségügyi okok, stb.) miatt feltétlenül ki kell elégíteni, akkor le kell tiltani a fiktív viszonylatot, ezzel biztosítjuk, hogy az fogyasztó igénye valóságos termelők által legyen kielégítve. Az előzőek alapján ezt úgy valósítjuk meg, hogy a zérus szállítási egységköltség helyett a -et használjuk.

    • Az összkínálat meghaladja az összkeresletet.

      Ekkor egy ún. fiktív vagy virtuális fogyasztót iktatunk be szállítási egységköltségekkel és kereslettel. Nyilvánvalóan az optimális esetben lesznek olyan termelők, amelyektől nem szállítjuk el a kínálatuknak megfelelő mennyiségű árut. Ha olyan a nem standard szállítási feladat, hogy például a termelőnél ne maradjon árú raktáron, akkor hasonlóan az előzőhöz a zérus szállítási egységköltség helyett a -et kell választani.

  3. Maximum feladat kezelése.

    Ha a szállítási feladat célfüggvényét maximalizálni kell (pl. a szállítási költség legkisebb felső korlátját akarjuk meghatározni), akkor a célfüggvényt standard alakra, azaz minimalizálandó formára kell hozni. Legyen k egy tetszőleges szám. A „költségtáblázat”-hoz tartozó célfüggvény ekkor az alábbiak szerint írható:

    A kereslet-kínálat egyensúlya miatt , azaz a fenti célfüggvény első tagja konstans, így az új „költségtáblázat”-hoz tartozó célfüggvény minimalizálása ekvivalens az eredeti költségekkel megfogalmazott szállítási feladat célfüggvényének maximalizálásával. Hogy a megszokott nemnegatív számokkal dolgozhassunk, azaz nemnegatív legyen, úgy k értékét a legnagyobb szállítási egységköltségnek (vagy annál nagyobbnak) kell választani. Összefoglalva tehát, olyan „költségtáblázat”-ot készítünk, amelyet úgy kapunk, hogy a legnagyobb szállítási egységköltségből kivonjuk a szállítási egységköltségeket.

Megjegyzés:

Ha egy nem standard feladatban maximalizálni kell és a kereslet-kínálat sem teljesül, akkor célszerű először a minimalizálásra visszavezetni a feladatot, majd ezután bevezetni a fiktív termelőt vagy a fiktív fogyasztót. Megjegyezzük azt is, hogy a fenti levezetésben szereplő mennyiség akkor is konstans lesz, mégpedig a és az mennyiségek kisebbikével lesz egyenlő.

Mint említettük, ha van letiltás, akkor azt egy nagy értékű szállítási költséggel valósítjuk meg, a minimalizálás miatt ide biztosan nem adódik szállítás. A nagy szám helyett egy M szimbólumot használunk a költségtáblázatban. Az algoritmus során a költségtáblázaton végrehajtandó módosításoknál ezt a kölségadatot sohasem változtatjuk, mindig M marad. Ha egy táblázatban sok letiltás szerepel, akkor elképzelhető az is, hogy a kereslet-kínálati szállítás egyáltalán nem valósítható meg. Erről egy általános Kőnig feladat megoldásával lehet meggyőződni.

14.5. Példamegoldás

1. Példa:

Oldjuk meg az alábbi szállítási feladatot „magyar módszerrel”!

0. lépés: A kereslet és a kínálat egyensúlyban van, tehát a „magyar módszer” alkalmazható.

1. lépés: A kiinduló redukált költségtáblázat meghatározása sor- és oszlopredukcióval.

2. lépés: Az általános Kőnig feladat megkonstruálása, a kiinduló szállítás meghatározása, majd útkeresés cimkézéssel.

A pozitív redukált költség helyeken a letiltások (-) beírása után az induló szállítást az Észak-Nyugati sarok módszerrel határozzuk meg, majd a folyamnövelést címkézéssel végezzük.

Az általános Kőnig feladat nem oldható meg, azaz az összes árut nem lehet elszállítani. A Kőnig feladat megoldási lépéséből áttérünk az redukált költségtáblázat módosításának lépésére.

3. lépés: Lefedés és a költségredukció végrehajtása.

A baloldali táblázat a régi -t, a jobboldali pedig az új redukált költségtáblázatot mutatja. A Kőnig feladat utolsó címkézése alapján elvégezzük a lefedést. A címkézett oszlopokat és a címkézetlen sorokat fedjük le a redukált költségtáblázatban. Hogy egy helyen legyen a lefedés és a redukált költségek módosítása, ezért írtuk le mégegyszer a régi táblázatot.

Az számítása: .

Az új -t úgy számítjuk ki, hogy a fedetlen elemeket csökkentjük értékkel, a kétszer fedetteket növeljük értékkel, az egyszer fedett elemeket változatlanul hagyjuk. Innentől kezdve a 2. és a 3. lépések ismétlődnek addig, amíg valamelyik Kőnig feladat megoldható nem lesz.

4. lépés: Az új általános Kőnig feladat megoldása.

A letiltásokat az új redukált költségtáblázat alapján elvégezzük és egy induló szállítást határozunk meg. Ezt végezhetjük a jól ismert Észak-Nyugati sarok módszerrel, de az előző általános Kőnig feladat szállítása is használható. A példamegoldás során mi az utóbbit követjük, vagyis bemásoljuk az előző szállítást. A bemásolásnál legfeljebb zérus szállítást nem tudunk bemásolni. Ezután a szállítási táblázatban azo(ko)n a hely(ek)en üres cella fog lenni, ahol az számításánál a minimum eléretett. Ezekre a helyekre a táblázat szegélyei alapján beírjuk a szállítást. Ha pozitív szállítást tudtunk beírni, akkor a szállítást javítottuk. Ezt a fajta folyamnövelést triviális folyamnövelésnek vagy egyszerűbben triviális javításnak szoktuk nevezni, mivel minden nehézség nélkül elvégezhető. A példában a -tól az -hez 2-t szállíthatunk triviális módon.

Találtunk utat, az út mentén a szállítást növelhetjük. Az útkeresés az termelőtől indult ki és megérkeztünk a fogyasztóhoz. Az utat mint ismeretes a címkéken visszafelé haladva határozhatjuk meg, amely a következő:

Mint ahogy az általános Kőnig feladat tárgyalásánál láttuk, az utat nem írjuk le, hanem amikor az utat meghatározzuk a címkéken visszafelé haladva, egyszerre elvégezzük az út éleinek bejelölését, váltakozva a és a szimbólumok berajzolásával. Az út éleinek szabad kapacitását az út élei alatt tüntettük fel. A szállításon mennyiséggel javíthatunk. A ismeretében egyszerűen elvégezhető a szállítás javítása, szimbólumnál csökkentünk, szimbólumnál növelünk. Az alábbi táblázat a fent leírt javítást mutatja és újra kezdjük a címkézést, mivel még van elszállítandó mennyiség.

5. lépés: Lefedés és a költségredukció végrehajtása.

A könnyebb követhetőség kedvéért mégegyszer leírtuk a régi táblázatot. A későbbiekben az eredeti helyen végezzük el a régi táblázat lefedését.

6. lépés: Az új általános Kőnig feladat megoldása.

Az általános Kőnig feladatot megoldottuk, azaz sikerült elszállítani az összes árut a fogyasztókhoz. Ezzel a „magyar módszer” algoritmusa végetért. Az alábbiakban a primál feladat és a duál feladat optimális megoldását közöljük.

A primál feladat optimális megoldása:

Az optimális szállítást az alábbi táblázat tartalmazza. A zérusok kiírása helyett a jobb áttekinthetőség miatt (-) jeleket is használhatunk. Ez itt nem letiltást jelent, hanem optimális esetben ezekre a helyekre nem érdemes szállítani.

A minimális szállítási költség számítása:

A duál feladat optimális megoldása:

A teljesség kedvéért közöljük a szállítási feladat duáljának optimális megoldását. Ez egyfajta ellenőrzési lehetőség lehet, mivel a két célfüggvény optimális értéke megegyezik. Az eljárás során a duál változókat magába foglaló redukált költségtáblázattal dolgoztunk. Az definíciós összefüggés alapján könnyen vissza tudjuk számítani az és a duál változók optimális értékeit. Célszerű a fenti képlet helyett a képlet használata. A baloldal ismert, hisz az eredeti költségtáblázatot és a legutolsó redukált költségtáblázatot kell kivonni egymásból. A jobboldalból pedig látható, hogy a duálváltozók egyértelműen nem határozhatók meg, csak egy konstans erejéig. Válasszuk például az -t. Az alábbi táblázat árnyékolt részének celláin végighaladva először a , majd az duál változókat határozhatjuk meg az egyenlet cellánkénti megoldása utján. Természetesen más duál változót is megválaszthatunk önkényesen és az egyenleteket más cellákra is felírhatjuk.

A duál feladat célfüggvényének maximális értéke:

Látható, hogy a két feladat célfüggvényének optimális értéke megegyezik. Ez egyfajta ellenőrzést is szolgáltathat a megoldás helyességére.

A szállítási feladat dualitási tételében beláttuk, hogy a duál célfüggvény minden lépésben határozottan növekszik. Megmutatjuk, hogy lépésenként mekkora volt a növekmény. Először meg kell határoznunk az induló duál változókhoz tartozó célfüggvényértéket. Az induló duálváltozók pedig egyszerűen adódnak a sor- és oszlopredukcióból, hiszen . Tehát a és . A duál célfüggvény pedig

Észrevehetjük, hogy a kínálati mennyiségeket rendre össze kell szorozni a sorokat redukáló mennyiségekkel, majd a keresleti mennyiségeket is rendre össze kell szorozni az oszlopokat redukáló mennyiségekkel és ezeket a szorzatokat össze kell adni. Az induló duál célfüggvényérték tehát 124.

A 2. lépésben a Kőnig feladat nem volt megoldható, így a kiadódó halmazok: és . Ekkor . A célfüggvénynövekményt pedig az alábbi összefüggés adja:

Az új, javított célfüggvényérték: 132.

A 4. lépésben sem volt megoldható a Kőnig feladat, ekkor és . Ekkor . A célfüggvénynövekmény: 6. Az új, javított célfüggvényérték: 138. Több javítás nem volt, ez az optimális (maximális) duál célfüggvényérték.

2. példa:

Három raktárban (R) 10, 12 ill. 12 tonnányi bizonyos fajta anyagunk van. Az anyagokat öt felhasználó műhelybe (M) kell szállítani, amelyeknek rendre 4, 5, 7, 9, 7 tonna anyagra van szüksége. Az anyagok tonnánkénti szállítási költségét az alábbi táblázat tartalmazza. Feladatunk olyan szállítási program kidolgozása, hogy a műhelyek 32 tonna igényét kielégítsük és a szállítás költsége minél kisebb legyen. Feltesszük, hogy a szállítási költség arányos a szállított mennyiséggel. Az raktár nem szállíthat az műhelynek. Az raktárt ki kell üríteni.

Megoldás:

0. lépés: Átalakítás standard alakra:

A feladat nem standard szállítási feladat, mert az összkereslet (32) kisebb, mint az összkínálat (34). Be kell iktatni egy () műhelyt zérus szállítási egységköltségekkel és 2 kereslettel. Mivel az előírás szerint az raktárban nem maradhat áru, ezért innen csak valóságos műhelyekhez szállíthatunk, tehát le kell tiltani az viszonylatot. Ezt egy nagy költség használatával valósítjuk meg és M szimbólummal jelöljük a költséget. Hasonlóan tiltjuk le az viszonylatot is. A standard szállítási feladat ekkor a következő. Indulhat a megoldás a „magyar módszerrel”.

1. lépés: Sor- és Oszlop redukció:

Sorredukció:

Oszlopredukció:

2. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel

Nem találtunk utat.

3. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Most már nem írjuk le mégegyszer a táblázatot, hanem a helyén végezzük el a lefedést. Az új redukált költségtáblázat a következő:

4. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Nem találtunk utat.

5. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

6. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Nem találtunk utat.

7. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

8. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Vége az algoritmusnak, mert az összes árú el lett szállítva. A keresett szállítási programot a fenti táblázat mutatja. Ebből kiolvasható, hogy az raktárban marad 2 tonnányi elszállítatlan áru.

A minimális szállítási költség: 126.

3. példa:

Három termelőnél (T) összesen 18 mennyiségű áru van azonos eloszlásban. El kell szállítani ezeket az árukat a fogyasztókhoz, amelyeknek az igénye rendre 4, 7, 3, 6 mennyiség. Ismertek a termelők és a fogyasztók közötti távolságok valamilyen távolságegységben. Tudjuk azt, hogy a szállítási költség arányos a távolsággal, az arányossági tényező értéke 20. Mennyi a szállítási költség alsó és felső korlátja? Az fogyasztó teljes igényét ki kell elégíteni. Az fogyasztó nem igényel árut a termelőtől.

Megoldás:

A feltett kérdésre azonnal megadhatjuk a választ. A szállítási költség alsó korlátja 0 (nem lehet negatív a költség), a felső korlát pedig (9-nél nagyobb költséggel nem szállíthatunk). Ennél jobb felső korlát is adható . Itt az egyes termelőktől történő szállítás legnagyobb költségével számoltunk. Hasonlóan adható meg a jobb alsó korlát is, amely . Nyílvánvaló, hogy a legjobb korlátokat szeretnénk megismerni. A legnagyobb alsó korlát és a legkisebb felső korlát érdekli a szállíttatót, ami esetünkben a minimális ill. a maximális költségnek felel meg. Ehhez két feladatot kell megoldani, egyik a szállítási költséget minimalizáló, másik pedig maximalizáló szállítási feladat.

Ne feledkezzünk meg arról, hogy távolságadataink vannak, ebből költségtáblázatot úgy készítünk, hogy minden táblázatbeli adatot beszorozzuk az arányossági tényezővel. Erre azonban nincs szükség, elegendő az algoritmus lépéseit a távolságadatokkal elvégezni és a végén szorozzuk be a távolságokkal számított célfüggvényértéket 20-al.

(A) Minimum feladat:

0. lépés: Átalakítás standard alakra:

A feladat nem standard szállítási feladat, mert az összkínálat (18) kisebb, mint az összkereslet (20). Be kell iktatni egy () termelőt zérus szállítási egységköltségekkel és 2 kínálattal. Mivel az előírás szerint az fogyasztó teljes igényét ki kell elégíteni, ezért ide csak valóságos fogyasztóktól szállíthatunk, tehát le kell tiltani az viszonylatot. Hasonlóan tiltjuk le az viszonylatot is. A standard szállítási feladat ekkor a következő. Indulhat a megoldás a „magyar módszerrel”.

1. lépés: Sor- és Oszlop redukció:

Sorredukció:

Oszlopredukcióra most nincs szükség.

2. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel

Nem találtunk utat.

3. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Most már nem írjuk le mégegyszer a táblázatot, hanem a helyén végezzük el a lefedést. Az új redukált költségtáblázat a következő:

4. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

5. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

6. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

7. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

8. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Nem találtunk utat.

9. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

10. lépés: Általános Kőnig feladat megoldása:

A szabaddá vált viszonylatban triviális módon javíthatjuk a szállítást. Ezt mutatja a következő táblázat:

Vége az algoritmusnak, mert az összes árú el lett szállítva. A minimális költségű szállítás a fenti táblázat szerint valósítható meg. Ebből kiolvasható, hogy az fogyasztó igényét nem elégítettük ki.

A minimális szállítási költség: .

(B) Maximum feladat:

0. lépés: Átalakítás standard alakra:

A feladat nem standard szállítási feladat, egyrészt mert nem minimumot kell keresni, másrészt az összkínálat (18) kisebb, mint az összkereslet (20). Először minimumfeladattá alakítjuk a problémát úgy, hogy a táblázat minden elemét kivonjuk a táblázat legnagyobb eleméből (9). Ezután iktatjuk be a be a fiktív termelőt (). Ezt és a letiltásokat ugyanúgy végezzük mint a minimumfeladatnál. A standard szállítási feladat ekkor a következő. Indulhat a megoldás a „magyar módszerrel”.

1. lépés: Sor- és Oszlop redukció:

Sorredukció:

Oszlopredukcióra most nincs szükség.

2. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel

Nem találtunk utat.

3. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Most már nem írjuk le mégegyszer a táblázatot, hanem a helyén végezzük el a lefedést. Az új redukált költségtáblázat a következő:

4. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

5. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

6. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

7. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

8. lépés: Általános Kőnig feladat megoldása:

A szabaddá vált viszonylatban triviális módon javíthatjuk a szállítást. Ezt mutatja a következő táblázat:

Vége az algoritmusnak, mert az összes árú el lett szállítva. A maximális költségű szállítás a fenti táblázat szerint valósítható meg. Ebből kiolvasható, hogy az fogyasztó igényét nem elégítettük ki.

A maximális szállítási költség: .

Tehát a szállítási költség a intervallumban mozoghat.

4. példa:

Egy üzem három műhelyében (M) termel bizonyos terméket, amelyekből három megrendelő (F, fogyasztó) rendre 40, 20, 10 darab terméket igényel. A műhelyek termelési kapacitása rendre 20, 40, 30 darab termék. Az egyes műhelyek fajlagos termelési költsége rendre 100, 120, 110 Ft/db. A műhelyek és a megrendelők közötti fajlagos szállítási költségeket (Ft/db) az alábbi táblázat mutatja. Az megrendelő csak az vagy az műhely által gyártott terméket kívánja megvásárolni. Határozza meg a műhelyek optimális termelési tervét és az optimális szállítási tervet úgy, hogy a megrendelést minél kisebb összköltséggel (termelési + szállítási) biztosítsuk! Mennyi az üzem összes termelési ill. összes szállítási költsége?

Megoldás:

Ha a műhelyek teljes kapacitással termelnének, akkor a kínálatuk 90 lenne, míg a fogyasztók igénye csak 70. A műhelyek nem mindegyikének érdemes tehát teljes kapacitáson termelnie. A feladatot úgy oldjuk meg, hogy mindegyik műhely a „kapacitásán” termel, a bevezetett fiktív fogyasztó fogja majd biztosítani, hogy mely műhelyek mennyit termeljenek a valóságban. Az, hogy melyiknek mennyit érdemes termelni az a megrendelésen kívül a fajlagos termelési és szállítási költségektől függ. A célfüggvény tehát itt a két fajlagos költség összege lesz, amelyet egyszerűen beláthatunk. Ha például az -tól az -hez szállítandó mennyiség, akkor ez azt jelenti, hogy ezt a mennyiséget egyrészt le kell gyártani, másrészt el kell szállítani. A termelés költsége , a szállítás költsége pedig , a költségek összege . Hasonlóan a táblázat többi eleménél is a két fajlagos költséget össze kell adni. Az elmondottak alapján elkészíthetjük az eredeti feladat standard alakú szállítási feladatát, figyelembe véve a letiltási előírást is. Tehát be kell vezetni egy fiktív fogyasztót mennyiségű kereslettel. Mivel nincs különös előírás a műhelyekre olyan vonatkozásban, hogy valamelyiknek teljes kapacitással kell termelni, ezért a fikfív fogyasztóhoz tartozó költségek zérusok.

Innentől kezdve a „magyar módszer” szokásos lépései szerint haladunk a megoldásban. A megoldás során a gyorsítás végett a lefedendő táblázatot nem közöljük kétszer, hanem a helyén fedjük le. Ez zavarhatja az olvasót, hisz amikor még csak számolja az táblát az már le van fedve. Először tehát a sor- és oszlopredukciót végezzük el.

A redukált táblázat segítségével kijelöljük a szabad és a tiltott szállítási helyeket, majd Észak-Nyugati sarok módszerrel egy induló szállítást határozunk meg, amit címkézéssel próbálunk javítani.

Nem sikerült javítani, a címkézés alapján elvégezzük a lefedést és meghatározzuk az új redukált költségtáblázatot.

Az új redukált költségtáblázat alapján újra kijelöljük a szabad és a tiltott szállítási helyeket, majd az előző szállítás bemásolása után a szállításon címkézéssel próbálunk javítani.

Most sem sikerült javítani, a címkézés alapján az utolsó redukált költségtáblázatot lefedjük és egy újabb redukált költségtáblázatot állítunk elő.

Ehhez a redukált költségtáblázathoz tartozó szabad szállítási helyeken már sikerül elszállítani az összes terméket.

Az algoritmus befejeződött, az optimális megoldás az alábbiakban adható meg.

Mivel az műhely 20 terméket a fiktív megrendelőhöz szállít, ez azt jelenti, hogy az műhelynek nem kell teljes kapacitáson dolgoznia, neki 40-20=20 darab terméket kell termelnie, amelyeket az megrendelőhöz fog elszállítani. A másik két műhely nem szállít fiktív megrendelőnek, így azok a kapacitásuknak megfelelő mennyiségű (20 ill. 30) terméket gyártanak. Az műhely a termelését (20) az -hez, míg az műhely termeléséből (30) 20-at az -hez, 10-et az -hoz szállít.

Az üzem összes költsége: Ft.

Az üzem összes termelési költsége: Ft.

Az üzem összes szállítási költsége: Ft.

14.6. Feladatok

  1. Oldja meg az alábbi sémával adott szállítási feladatokat és duálisukat:

    a)

    b)

    c)

    d)

  2. Adott az alábbi baloldali sémával egy szállítási feladat és ennek egy megengedett megoldása.

    a) Igazolja, hogy a megengedett megoldás optimális!

    b) Írja fel a duál feladat optimális megoldását!

    c) Tegyük fel, hogy a értéke 11-ről 16-ra változik. Optimális-e az adott megengedett megoldás? Ha nem optimális, akkor határozza meg az új feladat optimális megoldását!

  3. Három raktárban (R) 100, 120 ill. 120 tonnányi bizonyos fajta anyagunk van. Az anyagokat öt felhasználó üzembe (Ü) kell szállítani, amelyeknek rendre 40, 50, 70, 90, 90 tonna anyagra van szüksége. Az anyagok tonnánkénti szállítási költségét az alábbi táblázat tartalmazza. Feladatunk olyan szállítási program kidolgozása, hogy a 340 tonna anyag kiszállítása a legkisebb költséggel történjen feltéve, hogy a szállítási költség arányos a szállított mennyiséggel.

  4. Egy vállalatnak az A, B és C városokban van üzemegysége. Az üzemegységben azonos termékeket termelnek, melyek legnagyobb felvevőpiaca az X, Y, U, V városokban van. A megfelelő távolságokat (10 km-ben) az alábbi táblázat mutatja. Az üzemek termelése rendre 20, 13, 16 ezer darab; a piac igénye pedig rendre 10, 15, 12, 7 ezer darab. Hogyan kell a legkisebb szállítási összköltséggel lebonyolítani az eladást, ha feltételezzük, hogy a szállítási egységköltség arányos

    a) a távolsággal,

    b) a távolság négyzetével?

  5. Négy feldolgozó vállalat (V) egyheti alapanyagigénye rendre 70, 25, 50, 10 tonna. A vállalatok ellátását az irányító szerv három raktárból (R) rendeli el, melyek rendre 80, 25, 40 tonna alapanyagot tárolnak. A vállalatok és a raktárak viszonylatainak fajlagos szállítási költségeit az alábbi táblázat mutatja.

    a) Határozza meg a feldolgozó vállalatok legkisebb költséggel történő alapanyagellátását!

    b) Tegyük fel, hogy a és vállalat olcsóbban termel, mint a és vállalat, emiatt kívánatos a és vállalat teljes kapacitásának a kihasználása.

  6. Egy lignitmezőn három külszíni (K) és két mélyművelésű (M) bánya termékének hasznosítására három elektromos központ (E) települt. A bányák és az elektromos központok távolságait km-ben az alábbi táblázat mutatja. A bányák termelési kapacitása rendre 500, 300, 800, 600, 200 t/nap; az elektromos központok fogyasztása egyformán 800 t/nap. A szén szállítását gépkocsival végzik. A szállítási tarifa 0-4, 5-9, 10-14, 15-30 km távolságokra rendre 10, 18, 24, 28 Ft/t. Adja meg az elektromos központok optimális ellátási tervét!

  7. Négy olajfinomító (F) három várost (V) lát el. Az olaj tonnánkénti vasúti szállítási költsége forintban az alábbi táblázattal adott. Az olajüzemek kapacitása rendre 22, 35, 25, 41 t/nap. A városok napi olajfogyasztása rendre 30, 40, 53 t. Az első város olajigénye 10%-kal növekedett, amelyet maradéktalanul ki kell elégíteni; az olajüzemek kapacitása változatlan. Tervezze meg a városok olajellátását minimális szállítási költség mellett?

  8. Öt olajlelőhelyről (O) négy finomítót (F) látnak el nyersanyaggal. Az olajlelőhelyek és a finomítók távolságai km-ben az alábbi táblázattal adottak. A lelőhelyek napi termelése rendre 6000, 1000, 500, 3000, 2700 t. A finomítók napi kapacitása rendre 1000, 200, 4000, 6000 t. A szállítás vasúton történik, kivéve az viszonylatban, ahol a közúti szállítás olcsóbb, így ezen viszonylatban a lehető legtöbbet közúton szállítunk. Tervezze meg a finomítók nyersanyagellátását úgy, hogy a vasúti szállítások tonnakilométere minimális legyen!

  9. Három mészégető telepről (M) négy cementgyár (C) igényét kell kielégíteni. A mészégető telepek havi kibocsátóképessége rendre 500, 800, 1500 t. A mészégető telepek és a cementgyárak távolsága km-ben vannak megadva az alábbi táblázat szerint. A cementgyárak mészigénye egyformán 600 t/hó. Milyen ellátási terv lesz optimális, ha az és mészégető telep nem rendelkezik raktári kapacitással és a vasúttársaság az ill. az útvonalakon pályafelújítás miatt szünetelteti a forgalmat?

  10. Egy építőipari vállalat három betonkeverő bázist (B) létesít hat építkezés (E) betonnal történő ellátására. A szállítást gépkocsikkal végzik. Az építkezések napi betonigénye az ütemtervek alapján ismert. Az egyes bázisok termelőképessége és az egyes építkezések betonigénye -ben kifejezve az alábbi:

    A betonkeverő bázisok és az építkezések távolságai km-ben az alábbiak:

    Készítse el a hét utolsó napjának ellátási tervét minimális tonnakilométer (ill. ) figyelembevételével.

15. fejezet - Trans-shipment feladat

15.1. A feladat megfogalmazása

Tekintsünk egy hálózatot, több forrással és több nyelővel. A hálózat minden élén a kapacitások mellett értelmezzünk egy szállítási egységköltséget, jelölje ezeket A hálózatban az élek kapacitása és egységköltsége mellett adottak a forrásokból kifolyó folyamok és a nyelőkbe befolyó folyamok mennyiségei. Jelölje ezeket az adott mennyiségeket ill. . Tegyük fel, hogy a forrásokból kifolyó mennyiségek összege megegyezik a nyelőkbe befolyó mennyiségek összegével, azaz

A hálózat olyan pontját, amely sem nem forrás, sem nem nyelő, közbülső pontnak nevezzük. Ezeket a pontokat átrakodó pontoknak is szokás nevezni, innen a feladat elnevezése, például ezekben a pontokban egyik hajóról a másik hajóra történik a beérkező áru átrakodása és innen a továbbszállítása. A trans-shipment feladatot sokféleképpen elképzelhetjük. Egy olyan szállítási feladatként is, amelyben a termelőkön és a fogyasztókon kívül ún. átrakodópontok is vannak, tehát nem közvetlenül történik a szállítás a termelő és a fogyasztó között. Az ilyen módon megfogalmazott feladatot általános szállítási feladatnak is nevezik. A szállítási feladatban termelő-termelő és fogyasztó-fogyasztó között nincs kapcsolat. A trans-shipment feladatban ilyen kapcsolatok is lehetnek.

A trans-shipment feladat megfogalmazása:

Határozzuk meg a hálózatban a minimális költségű folyamot úgy, hogy teljesüljenek az alábbiak:

  • az éleken a folyam nem lehet nagyobb az él kapacitásánál,

  • a forráspontokból az adott mennyiség áramlik ki,

  • a nyelőpontokba az adott mennyiség áramlik be,

  • a közbülső pontokban a beáramló és a kiáramló mennyiség azonos legyen.

A trans-shipment feladat matematikai megfogalmazása:

Vezessük be a folyamproblémánál megismert jelölést egy pontból kifolyó ill. befolyó folyamok összegére:

Meghatározandók az folyamkomponensek úgy, hogy

15.2. A feladat matematikai vizsgálata és megoldási algoritmusa

A trans-shipment feladatot egy standard szállítási feladatra lehet transzformálni az alábbiak szerint. A szállítási feladat termelői legyenek a trans-shipment feladat élei, a kínálati mennyiségek pedig legyenek az élek kapacitásai. A szállítási feladat fogyasztói legyenek a trans-shipment feladat pontjai, a keresleti mennyiségeket pedig az alábbi módon határozzuk meg. Jelölje az i pontból kiinduló élek kapacitásainak összegét, azaz

Ennek segítségével az alábbi módon határozzuk meg a keresleti mennyiségeket:

A szállítási feladat termelői és fogyasztói közötti szállítási egységköltségek pedig a következők: az „termelő” sorában az i oszlopban , a oszlopban a többi helyen pedig . Tehát soronként csak két helyen engedünk meg szállítást. Az alábbi táblázat a megkonstruált szállítási feladat sémáját mutatja, a könnyebb áttekinthetőség kedvéért a költség helyett a (-) letiltást alkalmaztuk:

A megkontruált szállítási feladat standard feladat, tehát az összkínálat megegyezik az összkereslettel. Ennek igazolását az olvasóra bízzuk.

Ezután megoldjuk a szállítási feladatot, pl. „magyar módszerrel”. Jelölje a megoldást abban a cellában, ahol a költség , a zérus költségű cellában pedig , a kínálati egyensúly miatt. Ezt mutatja az alábbi séma:

Most megvizsgáljuk, hogy a szállítási feladat feltételei hogyan teljesítik a trans-shipment feladat feltételeit.

A szállítási feladatban is előírás a nemnegativitás.

A szállítási feladat kínálati feltételei biztosítják az korlátozottsági feltételt.

A szállítási feladat keresleti feltételei pedig az alábbiak miatt biztosítják a forráspontokra, közbülső pontokra és a nyelőpontokra vonatkozó előírásokat. Az i-edik oszlopra az alábbi keresleti egyenlőség áll fenn:

ezt részletezve:

a definíciójából pedig következik a két oldal egyenlősége.

Végül a célfüggvények ekvivalenciáját az alábbiak szerint ellenőrizhetjük:

A fentiekből kiolvasható, hogy a trans-shipment feladat megoldó algoritmusa minden olyan algoritmus, amellyel szállítási feladat oldható meg. Mi a „magyar módszert” ismertettük a szállítási feladat megoldására, így a megoldó algoritmusunk a „magyar módszer”.

Megjegyzés:

A transzformálás akkor is alkalmazható, ha egy forrással és egy nyelővel rendelkező minimális költségű folyamfeladatunk van. A minimális költségű folyamfeladat ismertetésénél olyan algoritmust mutattunk be, amely sorozatos minimális útkeresésekből állt. Ezzel a transzformációval egy új megoldó algoritmust kaptunk a minimális költségű folyamfeladatra.

15.3. Példamegoldás

Oldjuk meg az alábbi ábrán látható trans-shipment feladatot! Az élekre írt adatok közül az első az él kapacitását, a második (zárójelben lévő) az élen az egységköltséget jelenti. A pontok melletti adatoknál az betű a forrást, az betű a nyelőt jelöli, a számadatok pedig a forrásokból kifolyó folyamok ill. a nyelőkbe befolyó folyamok mennyiségét jelenti.

Megoldás:

Legelőször készítsük el a szállítási feladat sémáját. A szállítási feladat termelői az élek, fogyasztói pedig a pontok. A kínálati mennyiségek az élek kapacitásai. A keresleti mennyiségek számítása pedig az alábbi egyszerű módon történik. Az i pont kereslete: össze kell adni a bal szegélyen lévő azon élek kapacitását, amely él kezdőpontja i, majd nyelőpont esetén ehhez hozzá kell adni a nyelőpontra előírt mennyiséget ill. forráspont esetén ebből ki kell vonni a forráspontra előírt mennyiséget. A szállítási egységköltségek beírása is egyszerű: az él i kezdőpontjának cellájába zérust, a j végpontjának cellájába értéket írunk, a többi cellát letiltjuk. A pontokat a következőkben -vel jelöljük. A szállítási feladat sémája tehát a következő:

Az éleket betüvel jelöljük a szállítási feladat megoldása során.

A szállítási feladatot „magyar módszerrel” oldjuk meg. Könnyen látható, hogy sorredukcióra és oszlopredukcióra nincs szükség, így a redukált költségtáblázat az eredeti költségtáblázat, amely az alábbi:

Elkezdjük az általános Kőnig feladat megoldását, az induló megoldást É-Ny-i sarok módszerrel végezzük és címkézéssel próbálunk javítani a szállításon.

Nem sikerült a javítás, következik a redukált költségtáblázat lefedése (), majd az új redukált költségtáblázat meghatározása, amelyet az alábbi táblázat mutat:

A szabaddá vált cellán 1 egységgel, a szintén szabaddá vált cellán pedig 4 egységgel javíthatunk a szállításon, majd címkézéssel próbálunk javítani a szállításon.

Sikerült utat találnunk a címkézéssel, így javítható a szállítás, ezt mutatja a következő táblázat. Újra címkézéssel próbálunk javítani a szállításon:

Nem sikerült a javítás, következik a redukált költségtáblázat lefedése (), majd az új redukált költségtáblázat meghatározása, amelyet az alábbi táblázat mutat:

A szabaddá vált cellán 1 egységgel javíthatunk a szállításon, majd címkézéssel próbálunk javítani a szállításon.

Nem sikerült a javítás, következik a redukált költségtáblázat lefedése (), majd az új redukált költségtáblázat meghatározása, amelyet az alábbi táblázat mutat:

Most nincs triviális javítási lehetőség, címkézéssel próbálunk javítani a szállításon.

Sikerült utat találnunk a címkézéssel, így javítható a szállítás, ezt mutatja a következő táblázat.

Mivel az összes áru el lett szállítva, így az algoritmust befejezzük. A szállítási feladat megoldását a fenti táblázat, a trans-shipment feladat megoldását pedig az alábbi táblázat mutatja. A szürkén jelzett cellákon olvasható le a trans-shipment feladat optimális folyama.

A megoldást hálózaton az alábbi ábra mutatja:

A minimális költség : 26.

15.4. Feladatok

  1. Adott az alábbi „honnan-hova” táblázattal egy hálózat, kapacitás és költség adatokkal. Továbbá legyenek a 3, 5 pontok források rendre 5, 2 kifolyó mennyiséggel, a 2, 6 pontok nyelők rendre 4, 3 befolyó mennyiséggel. Határozza meg a minimális költségű folyamot!

  2. Adott az alábbi ábrával egy trans-shipment feladat. Oldja meg a feladatot "magyar módszerrel”! Az élekre írt adatok közül az első az él kapacitását, a második (zárójelben lévő) az élen az egységköltséget jelenti. A pontok melletti adatoknál az betű a forrást, az betű a nyelőt jelöli, a számadatok pedig a forrásokból kifolyó folyamok ill. a nyelőkbe befolyó folyamok mennyiségét jelenti.

16. fejezet - Hozzárendelési feladat

16.1. A hozzárendelési feladat megfogalmazása

Jelölje a személyeket, a munkahelyeket (munkákat). Legyen adva az alábbi táblázat, amelynek , (egész) eleme azt jelenti, hogy az munkás a munkát mennyi idő alatt tudja elvégezni. A személyek és a munkák számának azonosnak kell lenni!

A hozzárendelési feladat (primál feladat):

Rendeljük a személyeket a munkahelyekre (munkákhoz) úgy, hogy egy személy egy munkahelyen dolgozzon, egy munkahelyre egy személy kerüljön és a munkavégzés összideje a lehető legkisebb legyen.

Az olyan hozzárendelést, amelynél előírjuk, hogy egy személy egy munkahelyen dolgozzon és egy munkahelyen egy személy dolgozzon, kölcsönösen egyértelmű hozzárendelésnek nevezzük.

A hozzárendelést egy döntési változóval jelöljük. Legyen , ha az személy hozzá van rendelve a munkához és , ha az személy nincs hozzárendelve a munkához. Az a feltétel, hogy az személy egy munkahelyen dolgozzon úgy fogalmazható meg, hogy az döntési változók i-edik sorbeli összege 1. Az a feltétel pedig, hogy a munkát egy személy végezze úgy fogalmazható meg, hogy az döntési változók j-edik oszlopbeli összege 1. A munkavégzés összidejét azon időértékek összege adja, amelyekre , ez pedig ekvivalens a összeggel.

A hozzárendelési feladat matematikai megfogalmazása:

Meghatározandó úgy, hogy

feltételek teljesülése mellett a

mennyiség minimális legyen.

Könnyen felismerhető, hogy a hozzárendelési feladat a szállítási feladat azon speciális esete, amikor minden és minden .

A hozzárendelési feladat duál feladata:

A hozzárendelési feladat duál feladata a szállítási feladat duál feladatából könnyen származtatható és az alábbi alakban írható:

Meghatározandók az és egész számok úgy, hogy

feltételek teljesülése mellett a

mennyiség maximális legyen.

A hozzárendelési feladatra is ugyanazon elméleti összefüggések levezethetők, mint amiket a szállítási feladatra láttunk. A megoldást is a „magyar módszerrel” végezzük.

16.2. A „magyar módszer” eredetéről

A történeti hűséghez hozzátartozik, hogy a „magyar módszert” H. W. KUHN 1955-ben [10] a hozzárendelési feladat megoldására fejlesztette ki. Mivel a szállítási feladat a hozzárendelési feladat általánosításaként kezelhető, így a szállítási feladat megoldására is alkalmas. A jegyzetbeli tárgyalásban a „magyar módszert” szállítási feladatra ismertettük és a szállítási feladat speciális esetére, a hozzárendelési feladatra csupán alkalmazzuk.

Mivel a módszernek magyar vonatkozása van, érdemes a "magyar módszer" eredetéről a felfedezőnek az 1991-ben megjelent, a Matematikai programozás történetéről c. könyvben [6] írt visszaemlékezéséből idézni.

”... A történet 1953 nyarán kezdődik, amikor ...”. A szószerinti idézés helyett röviden összefoglaljuk a cikkben foglaltakat.

Ebben az időben H. W. KUHN a Bryn Mawr College-ban dolgozott és a nyári szünetben több kíváló kombinatorikust és algebristát hívtak meg a Kaliforniai Egyetemre, többek között KUHN-t is. A nyár folyamán C. B. TOMPKINS egy -es hozzárendelési feladatot próbált megoldani az akkori időszak egyik legjobb számítógépének (SWAC) segítségével az összes permutáció leszámlálásával. Egyetlen próbálkozása sem járt sikerrel.

A cikk ezen részében KUHN a hozzáredelési feladatot lineáris programozási feladatként írja fel, a célfüggvényben szereplő együtthatókat -vel jelölve és maximum problémaként megfogalmazva.

Ebben az időszakban KŐNIG DÉNES klasszikus művét [9] olvasta KUHN és rájött, hogy egy gráf két darab egyenként pontból álló részre particionálása és a két rész közötti párosítás problémája pontosan megegyezik egy olyan -es hozzárendelési feladattal, ahol az mátrix minden eleme vagy vagy . De még ennél is fontosabb volt KUHN számára, hogy KŐNIG DÉNES megadott egy olyan kombinatorikus algoritmust, amellyel meghatározhatók voltak a párosítási problémának és kombinatorikus duáljának az optimális megoldásai. KUHN a cikkben e helyen a már klasszikusnak számító KŐNIG-EGERVÁRY tételt ([9], 240. oldal, D Tétel) fogalmazza meg. KUHN megjegyzi: Ezek után már csak a következő probléma megoldása maradt hátra: hogyan lehet az általános hozzárendelési feladatot 0-1 típusúra visszavezetni?

Figyelmesebben olvasva KŐNIG DÉNES könyvét [9] KUHN felfigyelt a 238. oldalon található 2. lábjegyzetre, amely EGERVÁRY JENŐ magyar nyelvű cikkére [1] mutatott rá.. KUHN érezte, hogy a probléma megoldásának kulcsát éppen itt találhatja meg.

Amikor ősszel visszatért Kaliforniából a munkahelyére, a könyvtárból kikölcsönözte EGERVÁRY cikkének egy másolatát valamint egy nagy magyar szótár és nyelvtan könyvet. Ahogy írja: Két hétig magyarul tanult és közben lefordította Egerváry cikkét. KUHN megérzése bevált, mivel EGERVÁRY cikke valóban tartalmazott egy módszert, amelynek alapján az általános hozzárendelési feladat visszavezethető véges sok 0-1 típusú hozzárendelési feladatra. Felhasználva EGERVÁRY redukciós eljárását és KŐNIG párosítási algoritmusát 1953 őszén számos -es hozzárendelési feladat megoldását számolta ki kézzel. Mindegyik feladatot meg tudta oldani két órán belül és ez meggyőzte KUHN-t, hogy az általa javasolt kombinált algoritmus "jó". KUHN egy érdekes megjegyzést tesz: Valószínüleg ez egyike volt azon legutolsó eseteknek, amikor papirral és tollal le lehetett győzni a világ legnagyobb és leggyorsabb elektronikus számítógépét.

Végezetül KUHN megjegyzi: Hogy teljesen nyilvánvaló legyen, miszerint az általa javasolt algoritmust két magyar matematikus, KŐNIG DÉNES és EGERVÁRY JENŐ munkája inspirálta, ezért ezt az eljárást "magyar módszer"-nek nevezte el és ezen a néven is publikálta [10], [2].

Eddig a "magyar módszer" története.

16.3. Algoritmus a hozzárendelési feladat megoldására. A „magyar módszer”

A szállítási feladatnál leírtak szerint kell megoldani a hozzárendelési feladatot is. Az optimalitási kritérium itt azt jelenti, hogy hozzárendelés csak az cellákon lehetséges. Tehát egyetlen különbség van, nevezetesen amíg a szállítási feladatot általános Kőnig feladatok sorozatával oldjuk meg, addig a hozzárendelési feladatot egyszerű Kőnig feladatok vagy másnéven „házasság” feladatok sorozatával oldjuk meg.

16.4. Nem standard hozzárendelési feladat kezelése

A gyakorlati problémák nagyon sokszor nem standard alakú hozzárendelési feladatként fogalmazhatók meg, hanem annak különböző variánsaként. Ezek kezelése hasonló módon történik a szállítási feladatnál látottakhoz. A lényeg tehát itt is a standard feladatra való átalakítás.

  1. Egyedi tiltások kezelése.

    Ha valamely viszonylatban valamilyen oknál fogva nem lehetséges hozzárendelés, akkor ott a időt nagyon nagyra (M) választjuk.

  2. Nem egyenlő az egymáshoz rendelendők száma.

    Két esetet különböztetünk meg, attól függően, hogy a személyek vagy a munkák száma a nagyobb.

    • A munkák száma meghaladja a személyek számát.

      Ekkor annyi ún. fiktív vagy virtuális személyt iktatunk be, hogy a személyek száma megegyezzen a munkák számával. A beiktatott személyek soraiba zérus időértékeket írunk. Az eredeti feladat optimális megoldásában lesznek olyan munkák, amelyek elvégezetlenül maradnak. Ha a hozzárendelési feladat olyan, hogy például a munka feltétlenül el legyen végezve, akkor a fiktív személyek sorainak k-adik oszlopába zérus helyett nagyon nagy számot (M) írunk.

    • A személyek száma meghaladja a munkák számát.

      Ekkor annyi ún. fiktív vagy virtuális munkát iktatunk be, hogy a munkák száma megegyezzen a személyek számával. A beiktatott munkák oszlopaiba zérus időértékeket írunk. Az eredeti feladat optimális megoldásában lesznek olyan személyek, amelyek nem lesznek hozzárendelve munkához. Ha a hozzárendelési feladat olyan, hogy például az személy mindenképpen foglalkoztatva legyen, akkor a fiktív munkák oszlopainak k-adik sorába zérus helyett nagyon nagy számot (M) írunk.

  3. Maximum feladat kezelése.

    A hozzárendelési feladatoknál sűrün előfordul, hogy a célfüggvényt maximalizálni kell. Például az összidő legkisebb felső korlátját akarjuk meghatározni, vagy a értékek a személyek által előállított értéket jelentik, stb. Ekkor egy új táblázatot állítunk elő úgy, hogy a legnagyobb táblázatbeli elemből kivonjuk a táblázat elemeit és ezen táblázattal oldjuk meg a hozzárendelési feladatot.

Javasoljuk, hogy először a minimumra való visszavezetést végezzük el, ha több standard előírás nem teljesedik.

16.5. Példamegoldás

1. példa:

Oldjuk meg az alábbi hozzárendelési feladatot „magyar módszerrel”!

0. lépés: Ellenőrzés

Ellenőrizzük, hogy a sorok és oszlopok száma megegyezik-e, mert a „magyar módszer” erre a standard alakra lett kidolgozva.

1. lépés: A redukált időtáblázat meghatározása.

Sor- és oszlopredukcióval előállítjuk az redukált időtáblázatot.

2. lépés: A „házasság” feladat megkonstruálása és megoldása.

A kezdeti hozzárendelést az Észak-Nyugati sarok módszerrel végezzük. Itt nem érdemes külön az és a hozzárendelési (0 vagy 1 értékekből álló) táblázatot is tárolni, a hozzárendelés az táblázatban is megadható a „házasság” feladatnál ismertetett bekarikázással. Tehát ne feledjük, hogy csak cellákon lehetséges hozzárendelést végezni. A kezdeti hozzárendelés után címkézéssel megpróbáljuk javítani a hozzárendelést.

Találtunk utat, az út mentén a hozzárendelést eggyel javíthatjuk. Az útkeresés az és személyektől indult ki és vagy a vagy a munkákhoz szerettünk volna eljutnunk. Sikerült eljutnunk mindkettő munkához. Mivel minket csak egy út érdekel, ezért tetszőlegesen választottuk meg az út végpontját, legyen ez a munka. A címkéken visszafelé haladva a következő út adódott:

Az út mentén az típusú élen új hozzárendelést kapunk, a típusú élen pedig a régi hozzárendelés megszűnik, ezt jelöltük a és a szimbólumokkal. Mint ahogy a „házasság” feladat tárgyalásánál láttuk, az utat nem írjuk le, hanem amikor a címkéken visszafelé haladva felkutatjuk utat, egyszerre elvégezzük az új hozzárendelés berajzolását és a régi hozzárendelés törlését. Ezt mutatja az alábbi táblázat.

A régi hozzárendelés megszüntetését szaggatott körrel, az új hozzárendelést pedig vastagított körrel jelöltük. Ezt a táblázatot csupán azért közöltük, hogy az út mentén való módosítást könnyebben tudjuk nyomon követni. Természetesen az út megtalálása után azonnal a javított táblázatot írjuk fel, amelyen el is kezdjük az újabb útkeresést. Ezt mutatja a következő táblázat.

Nem találtunk utat, így az időtáblázatot fogjuk módosítani a lefedés segítségével. A táblázatba be is rajzoltuk a lefedést.

3. lépés: A redukált időtáblázat módosítása.

Mivel egyetlen táblázatot használunk, így a redukált időtáblázat által meghatározott „házasság” feladatot is azonnal elkezdjük megoldani. Tehát ellentétben a szállítási feladat megoldásával, itt elegendő egyetlen táblázat használata is. Ehhez a redukált időtáblázathoz az induló hozzárendelést vagy Észak-Nyugati sarok módszerrel vagy egyszerűen az előző hozzárendelés bemásolásával végezzük el. A példában az utóbbi szerint jártunk el.

4. lépés: A redukált időtáblázat meghatározása és a „házasság” feladat megoldása.

Találtunk utat, az út mentén a hozzárendelést javítjuk, ezt mutatja a következő táblázat.

Vége az algoritmusnak, mert sikerült az összes személyt a munkákhoz rendelni. A primál és a duál feladat optimális megoldása az alábbi:

A primál feladat optimális megoldása:

Az optimális hozzárendelést a fenti legutolsó táblázat tartalmazza bekarikázásokkal jelölve. Az optimális hozzárendelés tehát:

.

A minimális összidő számítása:

A duál feladat optimális megoldása:

A szállítási feladatnál látottakhoz hasonlóan határozzuk meg a hozzárendelési feladat duál változóinak optimális értékeit. Ha azt akarjuk, hogy a duál változók között ne legyen negatív, akkor adjunk mindegyikhez 3-at, ezt mutatja a jobboldali táblázatrész.

A duál feladat célfüggvényének maximális értéke:

2. Példa:

Az alábbi táblázat mutatja, hogy az egyes személyek (I) az egyes gépeken (G) dolgozva egy óra alatt hány darab terméket tudnak előállítani. Határozza meg a személyek gépekhez való hozzárendelését úgy, hogy a gépeken legfeljebb egy személy dolgozhat és a lehető legtöbb termék legyen előállítva egy óra alatt. Továbbá előírjuk, hogy az , , hozzárendelés nem lehetséges. Azt is megköveteljük, hogy a harmadik személy mindenképpen dolgozzon.

Megoldás:

A példa egy nem standard alakú hozzárendelési feladat, amelyben az egymáshoz hozzárendelendők száma nem azonos, a célfüggvény maximumát kell keresni és egyedi letiltások is vannak. Először a minimum feladatra történő visszavezetést végezzük el, azáltal, hogy a táblázat legnagyobb (esetleg annál nagyobb) eleméből kivonjuk a táblázat összes elemét. Másodszor egy fiktív gépet iktatunk be zérus adatokkal. Harmadszor pedig az egyedi tiltásokat egy M szimbólum használatával kezelhetjük. A fentieket elvégezve, az alábbi sémával adott hozzárendelési feladatot kell megoldani „magyar módszerrel”.

Mint ismeretes a „magyar módszer” első lépéseként sorredukciót majd oszlopredukciót szoktunk alkalmazni. A feladatban a sorredukció csak a 3. sor adatait változtatja meg, ezáltal a 3. sor elemei a többihez képest kisebbek lesznek és az oszlopredukció során általában ebben a sorban keletkeznek a zérusok. A zérusok jobb eloszlása miatt érdemes először az oszlopredukciót elvégezni. Az oszlopredukció elvégzése után következhet a sorredukció, amely jelen példában elmarad.

Ezután a kezdeti hozzárendelést készítjük el az Észak-Nyugati sarok módszerrel, majd a „magyar módszer” szokásos lépései (címkézés, lefedés, módosítás) következnek:

A lefedés segítségével az új táblázat elkészítése és az előző hozzárendelés bemásolása következik. A hozzárendelés triviális módon javítható az hozzárendeléssel.

A címkézés során találtunk utat, amely mentén tovább javítható a hozzárendelés. Az alábbi táblázat az új hozzárendelést tartalmazza.

Vége az algoritmusnak, mert az összes személyt hozzárendeltük a „gépek”-hez.

Az eredeti feladat optimális hozzárendelése is a fenti táblázatból olvasható ki. A megoldás szerint az személy lett a fiktív géphez rendelve, ami azt jelenti, hogy az optimális megoldásban az személyt nem érdemes foglalkoztatni, a többi személy pedig az alábbi módon lett a gépekhez rendelve:

Az egy óra alatt előállított termékek maximális száma: .

Megjegyezzük, hogy amennyiben a duál feladaton keresztül esetleges ellenőrzést szeretnénk végezni, úgy azt a standard alakú feladaton kell elvégeznünk.

3. Példa:

Adott az alábbi mátrix. Válasszunk ki a mátrix elemei közül ötöt úgy, hogy minden sorban és oszlopban legfeljebb egyet választhatunk és a kiválasztott elemek összege minél kisebb legyen! Továbbá vegyük figyelembe a kiválasztásnál, hogy a harmadik oszlopban mindenképpen válasszunk számot, az elemet pedig ne válasszuk.

Megoldás:

A példa egy nem standard alakú hozzárendelési feladat, amelyben az egymáshoz hozzárendelendők száma nem azonos és letiltások is vannak. Egy fiktív sort kell beiktatnunk zérus adatokkal. Az egyedi tiltásokat egy M szimbólum használatával kezelhetjük. A fentieket elvégezve, az alábbi sémával adott hozzárendelési feladatot kell megoldani „magyar módszerrel”:

Első lépésként elvégezzük a sorredukciót, majd az oszlopredukciót és utána Észak-Nyugati sarok módszerrel készítünk egy induló hozzárendelést. A következő lépésben pedig címkézéssel megpróbáljuk javítani a hozzárendelést. Ezt mutatja a következő táblázat.

Nem tudtunk javítani a hozzárendelésen, a címkézés alapján elvégezzük a lefedést és meghatározzuk értékét (). Elvégezzük a tábla adatainak módosítását és az új táblázaton újra címkézünk.

Most sem sikerült javítani a hozzárendelésen, a címkézés alapján elvégezzük a lefedést és meghatározzuk értékét (). Elvégezzük a tábla adatainak módosítását és az új táblázaton újra címkézünk. Ezt mutatja a következő táblázat:

A fenti táblán két címkézést is végeztünk a helytakarékosság miatt. Az első címkézésnél találtunk utat és javítottunk a hozzárendelésen. A szaggatott kör a régi hozzárendelés megszüntetését, a vastag kör pedig az új hozzárendelést mutatja. A második címkézés már a normál és a vastag körrel jelölt hozzárendelés javítását szolgálja. Nem sikerült javítani, így újabb lefedés, majd módosítás következik. Ezt mutatja a következő táblázat. El is kezdjük a címkézést és sikerült utat találni, a hozzárendelés javítható, amit végre is hajtottunk a táblázatban.

A fenti táblázatból kiolvasható a feladat optimális megoldása, amely szerint az és az mátrixelemeket kell kiválasztani. A kiválasztott öt elem összege = 36.

Megjegyezzük, hogy az egy táblázaton való többszöri címkézés helytakarékosság miatt hasznos lehet, de az eligazodás viszont nehézkesebb. Ezért ezt a lehetőséget a gyakorlottabb példamegoldóknak javasoljuk.

16.6. Feladatok

  1. Legyenek raktárhelyek (vagy raktárak) és pedig gépek helyei (vagy gépek). Adott az alábbi táblázattal az egyes gépek és raktárak között a szállítási útszakasz hossza. Homogén raktárakat kell kialakítani, azaz az egyes raktárakban csak egy-egy gép által megmunkált alkatrészt akarjuk tárolni. Adjuk meg a gépek és a raktárak közötti kölcsönösen egyértelmű hozzárendelést úgy, hogy az alkatrészek szállítási utvonalainak összhosszúsága minimális legyen!

  2. Az gépeken az alkatrésztípusokból egy óra alatt az alábbi táblázat által adott termékmennyiség (darab) készíthető el. Mindegyik alkatrésztípusból egy 120 darabot tartalmazó alkatrészsorozatot kell legyártani. Hogyan osszuk el a munkát, ha a gépek és az alkatrészek között kölcsönösen egyértelmű megfeleltetést akarunk létrehozni és azt akarjuk, hogy a négy alkatrészsorozat legyártásához szükséges gépidők összege minimális legyen?

  3. Egy város pontján egy-egy azonos típusú teherautó áll rendelkezésünkre. A város pontján egy-egy ugyanilyen típusú autóra jelentkezik egy-egy igénylő. Milyen utasítást adjunk ki, ha a négy autót a lehető legkisebb költséggel szeretnénk az igénylőkhöz eljuttatni. Az alábbi táblázat a megfelelő pontok közötti távolságokat mutatja és feltételezzük, hogy a költség arányos a távolsággal.

  4. Adott az alábbi számtáblázat. Válasszunk ki öt számot úgy, hogy minden sorból és oszlopból csak egy számot választhatunk és a kiválasztott számok

    a) összege minimális legyen,

    b) összege maximális legyen!

  5. Adott az alábbi számtáblázat. Válasszunk ki öt számot úgy, hogy minden sorból és oszlopból legfeljebb egy számot választhatunk és a kiválasztott számok

    a) összege minimális legyen,

    b) összege maximális legyen!

  6. Négy gép (G) négy alkatrész (A) mindegyikét képes gyártani. Ismertek az alábbi és táblázatok. Az azt jelenti, hogy a gépen egy alkatrész-sorozatot hány óra alatt lehet legyártani. A idő/költség dimenziójú, ha egy alkatrész-sorozatot a gépen munkálunk meg, akkor a megmunkálás egy órája költséggel jár. Minden alkatrészből egy-egy sorozatot (tételt) kell legyártani. Hogyan kell a gyártást megszervezni (melyik gép, melyik alkatrészt gyártsa), ha azt akarjuk, hogy a gyártási összköltség minimális legyen?

  7. Az munkások az munkák elvégzésére alkalmazhatók. Az munkás kétszer olyan gyorsan végzi az munkát, mint a -t és háromszor olyan gyorsan, mint a -t. A munkás a munkát háromszor olyan gyorsan végzi, mint -t és ötször olyan gyorsan, mint -t. A munkás az -t és -t egyformán végzi, a -t ezeknél ötször gyorsabban. Hogyan osszuk szét a munkákat a munkások között, hogy azok a leggyorsabban el legyenek végezve feltéve, hogy a munkákat egymás után végeztetjük?

  8. Az alábbi táblázat azt mutatja, hogy az egyes személyek (I) az egyes munkákat (J) milyen hasznossággal tudják elvégezni. Milyen kölcsönösen egyértelmű hozzárendeléssel érhetjük el, hogy az összhasznosság a lehető legnagyobb legyen?

  9. Ismert az alábbi táblázat szerint, hogy az egyes szakemberek (S) az egyes feladatokat (F) mennyi idő alatt tudják elvégezni. Hogyan kell a szakembereket a feladatokhoz rendelni (egy szakembert egy feladathoz és fordítva), ha azt akarjuk, hogy az összidőszükséglet minimális legyen figyelembe véve azt, hogy az szakembert az feladathoz nem lehet hozzárendelni és az feladatot okvetlenül el kell végezni?

17. fejezet - Vegyes feladatok

  1. Az alábbi táblázat 16 eleme közül válasszon ki négyet úgy, hogy a kiválasztott számok összege a lehető legnagyobb legyen! Minden sorban és minden oszlopban csak egyet választhat és a bal alsó elemet nem választhatja! Mekkora ez az összeg?

  2. Egy építőipari vállalat három betonkeverő bázist (B) létesít négy építkezés (E) betonnal való ellátására. A betonkeverők naponta rendre 6, 5, 2 teherautónyi betont tudnak előállítani. Az építkezéseknek rendre 3, 4, 4 teherautónyi betonra van szükségük. Az egyes betonkeverő helyek és az egyes építkezések közötti távolságokat az alábbi táblázat mutatja. A szállítási költség arányos a távolsággal, az arányossági tényező 7. A B1 és B3 betonkeverőknek teljes kapacitással kell dolgozniuk. Az építkezések betonellátásához szükséges szállítás összköltségnek mi a minimális értéke és ez milyen szállítással valósítható meg?

  3. Adott az alábbi táblázattal egy hálózat. Határozza meg az 5 pontot a 3 ponttól elválasztó minimális kapacitású vágást! Adja meg a vágásbeli éleket, a vágás kapacitását, valamint írja fel a feladat párjának optimális megoldását is!

  4. Egy építőipari vállalat három betonkeverő bázist (B) létesít három építkezés (E) betonnal való ellátására. Az építkezéseknek 50-50 teherautónyi betonra van szükségük. A betonkeverők naponta 60-60 teherautónyi betont tudnak előállítani. Az egyes betonkeverő helyek és az egyes építkezések közötti távolságokat az alábbi táblázat mutatja. A szállítási költség arányos a távolsággal, az arányossági tényező 2. A B2 nem szállíthat az E2-nek és a B1-nek teljes kapacitással kell dolgozni. Az építkezések betonellátásához szükséges szállítás összköltségnek mi a legkisebb felső korlátja (más szóval mi a legnagyobb szállítási költség)?

  5. Egy edző a következő olimpián a 4x100 m-es vegyesváltó csapatát akarja összeállítani úgy, hogy a lehető legjobb időeredményt érje el a 4 fős csapat. Az előzetes felmérések alapján a váltóba való bekerülésre kiválasztott öt úszó úszásnemenkénti eredményét mp-ben az alábbi táblázat mutatja. Az U2 úszó nem jó startoló, így őt nem indítja az első számban. Az U5 úszó pedig rossz hajrázó, így őt nem indítja az utolsó számban. Mi lesz a legjobb csapat, kit nem indít az edző és mennyi lesz a várható időeredmény?

  6. Adott az alábbi táblázattal egy hálózat. Határozza meg az 5 pontot a 3 ponttól elválasztó minimális kapacitású vágást! Adja meg a vágásbeli éleket, a vágás kapacitását, valamint írja fel a feladat párjának optimális megoldását is!

  7. Egy fuvarozó vállalat három telephellyel (T) rendelkezik, a telephelyeken rendre 28, 52, 40 szállítóeszköz van. A vállalat három helyről (H) kap megbízatást, ahová szállítóeszközeivel el kell mennie. A megrendelőhelyek rendre 40, 32, 48 szállítóeszközt igényelnek. Az alábbi táblázat mutatja a telephelyek és a megrendelőhelyek közötti távolságot valamilyen távolságegységben. Vegye figyelembe, hogy a T1 telephelyről nem lehet eljutni a H2 megrendelőhelyre! A megrendelőhelyekre történő kivonulás költségének mi a legkisebb felső korlátja (maximuma), feltételezve, hogy a kiszállási költség a távolsággal arányos, az arányossági tényező értéke 1? Milyen kivonulási terv tartozik ehhez a költséghez?

  8. Az alábbi táblázat 16 eleme közül válasszon ki négyet úgy, hogy a kiválasztott számok összege a lehető legkisebb legyen! Minden sorban és minden oszlopban csak egyet választhat és a bal alsó elemet nem választhatja! Mekkora ez az összeg?

  9. Egy fuvarozó vállalatnak négy telephelye (T) van, mindegyikben 10 szállítóeszköz van. A vállalat három helyről (H) kap megbízatást, ahová szállítóeszközeivel el kell mennie. A megrendelőhelyek mindegyike 12 szállítóeszközt igényel. Az alábbi táblázat mutatja a telephelyek és a megrendelőhelyek közötti távolságot valamilyen távolságegységben. Hogyan ossza szét a vállalat a szállítóeszközeit, ha a legkisebb költséggel kíván a megrendelőhelyekre kivonulni, feltételezve, hogy a távolsággal arányos a költség? Mely telephelyeken marad szállítóeszköz és mennyi? Mennyi a kiszállási költség, ha az arányossági tényező értéke 2?

  10. Adott az alábbi táblázattal egy hálózat. Határozza meg az 5 pontot a 3 ponttól elválasztó minimális kapacitású vágást! Adja meg a vágásbeli éleket, a vágás kapacitását, valamint írja fel a feladat párjának optimális megoldását is!

  11. Adott az alábbi táblázattal egy hálózat. Határozza meg az 5 pontból a 3 pontba irányuló 4 egységnyi folyamot, amelynek költsége minimális!

  12. Adott egy mátrix. Válasszon ki 3 elemet úgy, hogy minden sorban és oszlopban legfeljebb egyet választhat és a kiválasztott 3 szám összege minimális legyen! Az elemet nem választhatja!

  13. Egyetemünk Gazdaságtudományi Karán öt bizottságba (B) kell hallgatókat (H) delegálni. Egy bizottságba csak egy hallgatót és egy hallgatót csak egy bizottságba. Hat hallgató van a jelöltek között, akik rangsorolva vannak az egyes bizottságokba való bekerülés szerint. A rangsorolást az alábbi táblázat mutatja.

    a) Megoldható-e a delegálás az első és a második helyen rangsorolt hallgatókkal?

    b) Melyik hallgatókat melyik bizottságba delegáljuk, ha azt akarjuk, hogy a rangszámok összege minél kisebb legyen? Melyik hallgatót nem delegáljuk?

  14. Adott egy mátrix. Válasszon ki 3 elemet úgy, hogy minden sorban és oszlopban legfeljebb egyet választhat és a kiválasztott 3 szám összege maximális legyen! Az elemet nem választhatja! A harmadik oszlopban feltétlenül válasszon elemet!

  15. Adott az alábbi táblázattal egy hálózat és azon egy megengedett folyam. Határozza meg az 5-ből a 2-be irányuló maximális folyam értékét és a folyam-mátrixot! Adja meg a feladat duáljának optimális megoldását! A megoldásnál használja fel, hogy ismert egy megengedett folyam!

  16. Adott az alábbi táblázattal egy hálózat. Határozza meg a 4 pontot a 2 ponttól elválasztó minimális kapacitású vágást! Adja meg a vágásbeli éleket, a vágás kapacitását, valamint írja fel a feladat párjának optimális megoldását is!

  17. Egy város 3 térségét (T) 3 kenyérgyár (K) látja el kenyérrel. A gyárak fajlagos termelési költségei 50, 60, 70 Ft/t; mindegyik azonos termelési kapacitással 30 t/nap rendelkezik. Minden térségnek egyformán 25 t/nap az igénye. A fajlagos szállítási költségeket (Ft/t) az alábbi táblázat mutatja. Határozza meg az optimális termelési és szállítási tervet, ha azt akarjuk, hogy az összköltség (termelési + szállítási) minimális legyen és a K2 nem szállíthat a T2-nek! Számítsa ki a szállítási és a termelési költséget is!

  18. A G1, G2, G3, G4, G5 gépeken az A1, A2, A3, A4 alkatrésztípusokból egy óra alatt az alábbi táblázat által adott termékmennyiség (darab) készíthető el. Mindegyik alkatrésztípusból egy 120 darabot tartalmazó alkatrészsorozatot kell legyártani. Melyik gépen melyik alkatrészsorozatot gyártsuk (egy gépen egy alkatrészsorozatot és egy alkatrészsorozatot egy gépen), ha azt akarjuk, hogy a négy alkatrészsorozat legyártásához szükséges gépidők összege minimális legyen? Mennyi a minimális gyártási összidő? Melyik gépet nem érdemes igénybe venni?

  19. Az alábbi táblázat minden oszlopából válasszon ki egy számot, de egy sorból legfeljebb egyet úgy, hogy a kiválasztott számok összege a lehető legnagyobb legyen! Mekkora ez az összeg?

  20. Öt munkát (M) kell szétosztani négy szakértő (S) között. Az alábbi táblázat mutatja, hogy az egyes munkákat a szakértők milyen teljesítménnyel tudják elvégezni. A szétosztásnál figyelembe veendők:

    - egy szakértő csak egy munkát végezhet és egy munkát csak egy szakértő kaphat,

    - az M3 munkát az S2 szakértő nem végezheti,

    - az M2 munkát feltétlenül ezek a szakértők végezzék,

    - a szétosztásnak megfelelő teljesítmények összege minél nagyobb legyen.

    Mennyi a maximális összteljesítmény és melyik munkát végeztessük más szakértővel?

  21. Egy fuvarozó vállalatnak három helyen van telephelye (T), amelyekben rendre 12, 12, 12 szállítóeszköz van. A vállalat négy helyről (H) kap megbízatást, ahová szállítóeszközeivel el kell mennie. A megrendelőhelyek mindegyike tíz szállítóeszközt igényel. Az alábbi táblázat mutatja a telephelyek és a megrendelőhelyek közötti távolságot valamilyen távolságegységben. Mi a kiszállási költség legrosszabb értéke feltételezve, hogy a távolsággal arányos a költség és a harmadik megrendelést feltétlenül teljesíteni kell? A vállalat a szállítóeszközeinek milyen kiosztása mellett valósulna meg ez a legrosszabb költség? Az arányossági tényező értéke 29?

  22. Az alábbi táblázat minden oszlopából válasszon ki egy számot, de egy sorból legfeljebb egyet úgy, hogy a kiválasztott számok összege a lehető legnagyobb legyen! Mekkora ez az összeg?

  23. Egy telephelyről hat különböző helyre egy-egy teherautónyi mennyiségű gyorsan romló árut kell szállítani. A szállításra hat teherautót jelöltek ki. Az egyes helyekre (H) szállítandó áru rakodásához szükséges időt a baloldali táblázat, míg a szállításhoz szükséges időt a jobboldali táblázat mutatja teherautó-típusonként (T). Melyik teherautót melyik helyre irányítsuk, ha azt akarjuk, hogy minél gyorsabban célba érjenek az áruk, feltételezve, hogy egyszerre kezdődik a rakodás minden teherautónál és amikor egy teherautón végeznek a rakodással azonnal indul a teherautó.

  24. A CHEM Kft. egy bizonyos kémiai terméket négy különböző helyen lévő üzemében (U) termel, az üzemek termelése 5-5 teherautónyi mennyiség. A termékeket három gyár (G) vásárolja meg további feldolgozásra, a gyárak igénye 6-6 teherautónyi mennyiség. A többlettermelést az üzemek maguk dolgozzák fel, kivéve a harmadik üzemet, amelyben karbantartás miatt a feldolgozó részleg nem üzemel, így ott tárolási lehetőség sincs. Az alábbi táblázat az üzemek és a gyárak közötti távolságokat mutatja. Hogyan elégítené ki a feldolgozó gyárak igényeit, ha azt akarjuk, hogy a szállítási összköltség minimális legyen, feltéve, hogy egységnyi távolság esetén egy teherautónyi fuvar költsége 1 pénzegység, kivéve az U1-G2 és az U4-G2 viszonylatokat, ahol 1,5 pénzegység? Mennyi a szállítási költség? Mely üzemek milyen mennyiségben végeznek továbbfeldolgozást?

  25. Adott az alábbi táblázattal egy digráf. Határozza meg a 2 pontból a 3 pontba vezető azon utat, amely a legkevesebb élet tartalmazza!

  26. Adott az alábbi táblázattal egy úthálózat egy-egy szakaszának hossza. A 5 pontból a 4 pontba akarunk 5 teherautónyi árut szállítani. Melyik úton érdemes lebonyolítani a szállítást és mennyi a szállítás összköltsége, ha a szállítási költség arányos a távolsággal, az arányossági tényező értéke 2?

  27. Az alábbi táblázat mutatja, hogy az egyes munkások (M) az egyes gépeken (G) dolgozva egy óra alatt hány terméket tudnak előállítani. Határozza meg a kölcsönösen egyértelmű munkás-gép hozzárendelést úgy, hogy a lehető legtöbb termék legyen előállítva egy óra alatt és adja meg az előállított termékek számát! (A táblázatbeli "-" jel azt jelenti, hogy az illető munkás nem dolgozhat az illető gépen)

  28. Európa hat fővárosát tekintve, bizonyos városok között van csak közvetlen légi összeköttetés, amelyet az alábbi táblázat tartalmaz. Mely városokat érintve, milyen járatokat kell igénybe venni, ha a legkevesebb átszállással akarunk légi úton eljutni a 4 jelű városból a 2 jelű városba?

  29. Négy raktárból (R1, R2, R3, R4) rendre 4, 2, 3, 3 mennyiségű árut kell elszállítani négy feldolgozó helyre (F1, F2, F3, F4), amelyeknek rendre 5, 3, 2, 2 mennyiségű árura van szüksége. Adja meg, az egyes raktárakból melyik feldolgozóhelyre mennyi árut szállítsanak úgy, hogy a legrövidebb idő alatt befejeződjön a szállítás, feltéve, hogy minden útvonalon egyidőben kezdődik! Az egyes viszonylatokban a szállítási időket az alábbi táblázat tartalmazza:

  30. Adott az alábbi táblázattal egy hálózat. Határozza meg a 3 pontból a 2 pontba vezető legrövidebb utat és az út hosszát!

  31. Az alábbi táblázat mutatja, hogy az egyes munkások (M) az egyes gépeken (G) dolgozva egy óra alatt hány terméket tudnak előállítani. Határozza meg a kölcsönösen egyértelmű munkás-gép hozzárendelést úgy, hogy a lehető legtöbb termék legyen előállítva egy óra alatt és adja meg az előállított termékek számát! (A táblázatbeli "-" jel azt jelenti, hogy az illető munkás nem dolgozhat az illető gépen)

  32. Adott az alábbi táblázattal egy hálózat. Határozza meg a 2 pontot a 4 ponttól elválasztó minimális kapacitású vágást! Adja meg a vágásbeli éleket, a vágás kapacitását, valamint írja fel a feladat párjának optimális megoldását is!

  33. Egy üzemben négy alkatrészből álló terméket gyártanak. Az egyes alkatrészeket (A1, A2, A3, A4) négy gépen (G1, G2, G3, G4) lehet előállítani. Ismert, hogy az egyes alkatrészek megmunkálása az egyes gépeken mennyi időt igényel. Melyik alkatrészt melyik gépen gyártsák (egy gépen egy fajta alkatrészt, ill. egy alkatrészt egy gépen készítenek), hogy egy termék előállításához szükséges gépidők összege minimális legyen? Mennyi ez a minimális idő?

  34. Hét munkásnak (M) hét alkatrészt (A) kell elkészítenie. Az egyes munkások a következő alkatrészek elkészítéséhez értenek: ; ; ; ; ; ; . Döntse el, hogy minden munkás megbízható-e egy olyan alkatrész elkészítésével, amelyikhez ért, feltéve, hogy egy alkatrészt csak egy munkás készíthet el! Ha ez a megbízás nem lehetséges, akkor ezt indokolja meg és adjon meg egy legtöbb munkást foglalkoztató hozzárendelést is!

  35. Egy megye három körzetét (K) három húsüzem (H) látja el tőkehússal. Az üzemek napi termelési kapacitása rendre 20, 30, 40 tonna, míg a körzetek napi igénye rendre 40, 20, 10 tonna tőkehús. Ismertek a fajlagos szállítási költségek az egyes viszonylatokban, amely értékeket az alábbi táblázat tartalmazza. Határozza meg az optimális termelési és szállítási tervet, ha az egyes körzetek ellátását minimális szállítási összköltséggel akarjuk megoldani! Melyik húsüzem kapacitása nincs kihasználva?

  36. Adott az alábbi táblázattal egy úthálózat és az egyes utakon történő szállítás költsége. Milyen útvonalon lehet a legkisebb költséggel szállítani az 1 pontból a 3 pontba és mennyi a szállítási költség?

  37. Egy tevékenység sorozat esetében az egyes tevékenységek a kezdő és a befejező eseményük sorszámával, valamint a tevékenységi idejükkel az alábbi táblázattal adottak. Határozza meg a kritikus utat, az átfutási időt, valamint a (3,4) tevékenység legkorábbi kezdési és befejezési idejét, legkésőbbi kezdési és befejezési idejét!

  38. Egy üzemben négyféle gépet (G1, G2, G3, G4) négy műhelyben (M1, M2, M3, M4) gyártanak. Az M1-ben a G1-et, M2-ben a G2-t, M3-ban a G3-t, M4-ben a G4-et. A legyártott gépek raktározása az R1, R2, R3, R4 raktárakban történik. Homogén raktárakat kell kialakítani, azaz az egyes raktárakban csak egyféle gépet lehet tárolni. Adottak az egyes műhelyek és raktárak közötti távolságok. Hol történjen az egyes gépfajták tárolása, hogy a raktárba való szállítási útvonal összhosszúsága a legkisebb legyen? Mennyi a keresett összhosszúság?

  39. Az alábbiakban adott az mátrix és a , vektorok. Határozza meg azt az mátrixot, amelynek sorösszegei rendre a vektor elemei, oszlopösszegei pedig rendre a vektor elemei. Továbbá olyan legyen az mátrix, hogy az mátrix elemeinek az mátrix ugyanolyan pozicióban lévő elemeivel vett súlyozott számtani átlaga

    a) minimális legyen,

    b) maximális legyen!

  40. Az alábbiakban adott az mátrix. Határozza meg azt az mátrixot, amelynek elemei vagy , valamint minden sorában és oszlopában pontosan egy darab értéke 5. Továbbá olyan legyen az mátrix, hogy az mátrix és az mátrix ugyanolyan pozicióban lévő elemei szorzatának

    a) összege minimális legyen,

    b) összege maximális legyen,

    c) maximális értéke minimális legyen!

  41. Tekintsük az alábbi öt sorból és öt vonalból álló sakktáblarészletet, amelynek mezőiben számok vannak. Adott öt világos és négy sötét bástya. Tegyük a sötét bástyákat a tábla mezőire.

    1. Helyezzük el a fennmaradó mezőkre a világos bástyákat úgy, hogy egymást ne támadják és a felhasznált mezőkön lévő számok összege minél kisebb legyen! (Két bástya akkor támadja egymást, ha egy sorban vagy egy vonalban vannak.)

    2. Hány százalékkal csökken a minimum érték, ha a világos bástyákból csak három van, de azok a sötét bástyákat sem támadhatják.

  42. Tekintsük az alábbi öt sorból és hét vonalból álló sakktáblarészletet, amelynek mezőiben számok vannak. Helyezzünk el öt darab gyalogot a mezőkre úgy, hogy minden vonalban és minden sorban legfeljebb egy gyalog lehet és a felhasznált mezőkön lévő számok összege minimális legyen! Vegye figyelembe a gyalogelhelyezésnél, hogy a vonalra mindenképpen kerüljön gyalog és az mezőkön nem tehet gyalog! Végezze el a gyalogelhelyezést úgy is, hogy a felhasznált mezőkön lévő számok összege maximális!

Irodalomjegyzék

[1] Egerváry Jenő. Mátrixok kombinatorikus tulajdonságairól. Matematikai és Fizikai Lapok. 38. 1931. 16–28.

[2] Egerváry Jenő. On Combinatorial Properties of Matrices, translated by H. W. Kuhn. Logistics Papers (Issue 11), Paper 4, George Washington University. 4/11. 1955. 1–11.

[3] Euler L.. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae. 8. 1736. 128–140.

[4] Ford L. R., Jr.. Network Flow Theory. The RAND Corporation, Paper-923, July 14. 1956.

[5] Ford L. R., Jr.-Fulkerson D. R.. Flow in Networks. Princeton University Press, Princeton, N. J.. 1962.

[6] History of Mathematical Programming, A Collection of Personal Reminiscences. Stichting Mathematisch Centrum. 1991. 77–81.

[7] Hitchock F. L.. Distribution of a Product from Several Sources to Numerous Localities. J. Math. Phys.. 20. 1941.

[8] Klafszky Emil. Hálózati folyamok. Bolyai János Matematikai Társulat kiadványa, Budapest. 1969.

[9] Kőnig Dénes. Theorie der endlichen und unendlichen Graphen: kombinatorische Topologie der Strechenkomplexe. Akademische Verlagsgesellschaft, Leipzig. 1936.

[10] Kuhn H. W.. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly. 2. 1955. 83–97.

[11] Minty G. J.. A Comment on the Sortest Route Problem. Operations Research. 5. 1957.