A Bolyai János Matematikai Társulat kiadványa
Klafszky Emil: HÁLÓZATI FOLYAMOK
Budapest 1969
Az operációkutatás matematikai módszerei című tanfolyam anyaga
Szerkesztő: Prékopa András
Kiadó: MTESZ Bolyai János Matematikai Társulat
Felelős kiadó: Császár Ákos
Készült 220 példányban
69/6847. MTESZ HNy. Bp./Sné.
Előszó
Ez a jegyzet a Bolyai János Matematikai Társulat "Az operációkutatás
matematikai módszerei" c. két éves tanfolyama hálózati folyamatok
tárgyának anyagát tartalmazza.
A jegyzet célja, hogy az utóbbi időben rendkívül gyorsan fejlődő
folyamhálózati módszerekről egy bevezetést nyújtson A tárgyalásra
kerülő anyagot kilenc főbb fejezetre, mint önálló modellekre bontottam.
Ezen fejezeteken belül az első paragrafus a fejezet /modell/ alapvető
tételét, a következő a megoldó algoritmust tartalmazza. A további
paragrafusok az alapmodellre épülő alkalmazásokat tartalmazzák.
Ettől a felépítéstől kicsit eltér a VIII. fejezet. Az eltérést az
indokolja, hogy a tervütemezési modelleket /CPM/ time, CPM/cost, PERT/
egy önálló fejezetben kívántam összefogni, amely, - az olyan olvasó
számára, akit speciálisan csak az érdekel, - a jegyzet nagy részének
átolvasása nélkül is olvasható.
Az egyes fejezetek egymáshoz való kapcsolatát az alábbi séma mutatja. A folytonos vonal jelöli a jegyzetbeli kapcsolatot, míg a szaggatott és pontozott vonal egy más, lehetséges kapcsolatot mutat, melynek pontosabb megmutatása - az olvasóra bízva - a feladatok közt szerepel.
A lineáris programozásban járatos olvasó észreveszi, hogy az egyes modellek speciális lineáris programozási modellként is felfoghatók és így a dualitási tétel /integritás nélkül/, a lineáris programozás dualitási tételéből azonnal adódik. Erre a kapcsolatra a jegyzetben, - hogy tisztán folyamhálózati eszközöknél maradjunk, - nem térünk ki.
 |
Az anyag tárgyalása előtt a "Bevezetés"-ben megkíséreltem az alapvető fogalmakat heurisztikusan bevezetni. Lehet, hogy ez az olvasónál, - épp ellenkezőleg, - nehézséget okoz, akkor a bevezetés kihagyásával, esetleg későbbi visszatéréssel, olvassa a jegyzetet.
A fejezetek végén lévő feladatok egyrészt az algoritmus begyakorlását, másrészt az alapmodell alkalmazását
és más fejezetekhez való kapcsolatát mutatják.
Köszönetet mondok Majtay Antalnak a kézirat gondos áttanulmányozásáért és értékes megjegyzéseiért.
1969. augusztus
A szerző
T A R T A L O M
BEVEZETÉS
1. Példa: Egy egyszerű raktár modell 5
2. Példa: Egy egyszerű terhelési feladat 12
Irodalom 16
I. DIGRÁF. CIMKÉZÉSI TECHNIKA
1. Vágás és út dualitás tétele 17
2. Címkézési technika 20
3. Legrövidebb út probléma 23
Irodalom 38
Feladatok 38
II. HÁLÓZATI FOLYAMOK
4. Maximális folyam - minimális vágás tétel 41
5. Algoritmus a maximális folyam meghatározására 46
6. Integritási tétel 51
7. Gráfelméleti alkalmazás: Egerváry-Kőnig és Menger tételek 55
Irodalom 58
Feladatok 59
III. "HÁZASSÁG" PROBLÉMA
8. Kőnig-Hall tétel 62
9. Algoritmus a "házasság" probléma megoldására 66
10. Futószalag modell 71
11. Diltworth lánclebontás 72
12. Egyszerű halmazreprezentációs alkalmazás 75
Irodalom 78
Feladatok 79
IV. KERESLET-KINÁLAT PROBLÉMA
13. Gale tétel 80
14. Algoritmus a kereslet-kínálat modell megoldására 83
15. "Baseball játék" probléma 89
16. Tételek a kereslet-kínálat modell megvalósíthatóságáról 93
17. Szimmetrikus kereslet-kínálat modell 94
18. Multiplicitásos halmazreprezentáció 101
19. Digráfok részgráf problémája 107
20. Matrixok 0 és 1 komponensekkel 112
Irodalom 124
Feladatok 125
V. KORLÁTOZOTT FOLYAMOK. CIRKULÁCIÓ
21. Maximális folyam - minimális vágás tétel korlátozott folyamnál 129
22. Algoritmus a maximális korlátozott folyam meghatározására 135
23. Folyamcirkuláció. Cirkulációs tétel 138
24. Algoritmus a cirkulációs folyam meghatározására 144
25. A cirkulációs tétel alkalmazása halmazreprezentációs feladatra 146
26. A cirkuláció egy gráfelméleti alkalmazása: Unicursal gráf 150
Irodalom 152
Feladatok 153
VI. HOZZÁRENDELÉSI PROBLÉMA
27. Egerváry-Kuhn dualitás tétel 155
28. Algoritmus a hozzárendelési feladat megoldására 159
29. Arányos ár modell 163
Irodalom 167
Feladatok 167
VII. SZÁLLITÁSI PROBLÉMA
30. Ford-Fulkerson dualitás tétel 170
31. Algoritmus a szállítási probléma megoldására 176
32. Egy egyszerű készletgazdálkodási modell 183
33. Trans-shipment probléma 184
Irodalom 188
Feladatok 188
VIII. TERVÜTEMEZÉSI MODELLEK
34. Időtervezési feladat (CPM/time) és dualitás tétele 191
35. Algoritmus az optimális időütem terv meghatározására 198
36. Költségtervezési feladat (CPM/cost) és dualitás tétele 201
37. Algoritmus a költségtervezési feladat megoldására 208
38. Sztohasztikus időtervezési feladat (PERT) 217
Irodalom 222
Feladatok 222
IX: ÁLTALÁNOS KÖLTSÉGES FOLYAM PROBLÉMA
39. Általános minimális költségű folyam probléma 224
40. Algoritmus a paraméteres feladat megoldására 231
41. Maximális dinamikus folyam 247
42. Költséges korlátozott folyam probléma 254
43. Költséges cirkulációs folyam probléma 255
Irodalom 257
Feladatok 257
IRODALOM JEGYZÉK 259
4. oldalig
BEVEZETÉS
5. oldal
6.-7. oldalak
8.-9. oldalak
10.-11. oldalak
12.-13. oldalak
14.-15. oldalak
16. oldal
I. DIGRÁF. CIMKÉZÉSI TECHNIKA
17. oldal
18.-19. oldalak
20.-21. oldalak
22.-23. oldalak
24.-25. oldalak
26.-27. oldalak
28.-29. oldalak
30.-31. oldalak
32.-33. oldalak
34.-35. oldalak
36.-37. oldalak
38.-39. oldalak
40. oldal
II. HÁLÓZATI FOLYAMOK
41. oldal
42.-43. oldalak
44.-45. oldalak
46.-48. oldalak
48.-49. oldalak
50.-51. oldalak
52.-53. oldalak
54.-55. oldalak
56.-57. oldalak
58.-59. oldalak
60.-61. oldalak
III. "HÁZASSÁG" PROBLÉMA
62.-63. oldalak
64.-65. oldalak
66.-67. oldalak
68.-69. oldalak
70.-71. oldalak
72.-73. oldalak
74.-75. oldalak
76.-77. oldalak
78.-79. oldalak
IV. KERESLET-KINÁLAT PROBLÉMA
80.-81. oldalak
82.-83. oldalak
84.-85. oldalak
86.-87. oldalak
88.-89. oldalak
90.-128. oldalak
V. KORLÁTOZOTT FOLYAMOK. CIRKULÁCIÓ
129.-154. oldalak
VI. HOZZÁRENDELÉSI PROBLÉMA
155.-169. oldalak
VII. SZÁLLITÁSI PROBLÉMA
170.-190. oldalak
VIII. TERVÜTEMEZÉSI MODELLEK
191.-223. oldalak
IX: ÁLTALÁNOS KÖLTSÉGES FOLYAM PROBLÉMA
224.-258. oldalak
IRODALOM JEGYZÉK
259. oldal
260-261. oldalak
262-263. oldalak
-----------------------------------------------
A jelen honlap technikai szerkesztője:
Hujter Mihály
http://www.math.bme.hu/~hujter
-----------------------------------------------
Név és tárgymutató
(szerkesztés alatt, Hujter M.)
aciklikus => ciklusmentes
altér duálisa : 154
assignment probléma : 156
beszerzési-eladási politika : 5
bevétel : 24
bipartit digráf : 55
blokkoló élhalmaz : 38
Bolyai : címlap
Chan : 16
ciklusmentes hálózat : 12
cimkézési technika : 5
CPM : Előszó
Császár Ákos => felelős kiadó
csúcs => digráf
D'Esopo : 38
digráf : 17
dinamikus programozás : 33
dualitás : 19
duál feladat : 24
Egerváry : 55, 58, 155, 157
egészértékű folyam : 59
elválasztás : 19
él => digráf
Eötvös : 58
ferde szimmetricitás : 51
folyam : 5
folytonossági meggondolások : 53
forrás : 51, 59
forrásból generált ... : 59
Ford : 25, 38, 58, 170
Fulkerson : 58, 170
független elempár : 65
független élek : 55
generált vágás : 59
Hall : 62
Harris : 58
hálózati folyamok : címlap
hátizsák : 12
házasság : 62
hozzárendelés probléma : 156
hurokél => él
időmátrix : 26
integer => egészértékű
ív => digráf
Jewell : 16
kvalifikációs mátrix : 62
korlátozottság (folyamé) : 51
legrövidebb út : 23
Kőnig : 58, 62
Kőnig-Hall tétel : 159
Kuhn : 155, 157
magyar módszer : 159
Majtay : Előszó
maximális folyam : 59
mátrix vonalai : 65
minimális vágás : 59
Menger : 58
Minty : 38
MTESZ : címlap
nyelő : 51, 59
nyelőből generált ... : 59
páros gráf => bipartit digráf
PERT : Előszó
pollack : 38
pont => digráf
potenciál : 5
potenciál differencia függvény : 154
Prékopa András => sorozatszerkesztő
raktármodell : 5,16
Robacher : 58
Ross : 58
sorozatszerkesztő : belső címlap
struktúra mátrix : 18
súlykapacitás : 12
szabad cirkuláció : 154
szállító : 24
szállítási feladat : 170
szimmetricitás => ferde szimmetricitás
telítetlen út telítése : 53
teljes digráf : 19
terhelési feladat : 12
termelő : 24
többszörös él => él
utazási időmátrix : 26
vágás : 19
-----------------------------------------------------------
A technikai szerkesztő megjegyzései
1. A jelen honlap Klafszky Emil szerző, Prékopa András sorozatszerkesztő és a kiadó, a Bolyai Társulat engedélyének birtokában készül. Nekik és a felelős kiadónak, Császár Ákosnak köszönjük, hogy a digitalizálást engedélyezték. Hálásak vagyunk továbbá Csizmadia Ákosnak és Mályusz Leventének a jegyzet egy-egy példánya beszerzéséért.
2. Esetleges észrevételeiket a hujter.misi@gmail.com
címre küldjék.