Ízelítő a könyvből

Tartalomjegyzék

 Előszó 8

1 Lineáris programozás 9

1.1. Az optimális hozzárendelés problémája 9

1.2. A lineáris programozás alapfeladata13

1.3. A megoldhatóság vizsgálata 16

1.3.1. Fourier–Motzkin elimináció  16

1.3.2. Farkas-lemma 18

1.4. Dualitás21

1.4.1. A célfüggvény korlátossága21

1.4.2. A lineáris programozás dualitástétele 24

1.4.3. A lineáris programozás bonyolultsága 25

1.5. Egészértékű programozás26

1.5.1. Az egészértékű programozás alapfeladata. 27

1.5.2. Az egészértékű programozás bonyolultsága27

1.5.3. Korlátozás és szétválasztás29

1.6. Totális unimodularitás. 32

1.7. Szimplex módszer 47

1.8. Ajánlott irodalom 65

2 Matroidok 66

2.1. Matroidok alaptulajdonságai 66

2.2. Duális matroid, minorok73

2.3. Mátrixok és matroidok77

2.4. Matroidok összege 81

2.5. Matroidok metszete 84

2.6. Matroidmetszet-algoritmus . 86

2.7. A matroidpárosítási probléma 88

2.8. Mátrixok és matroidok II.89

2.9. Matroidelméleti tulajdonságok jellemzése92

2.10. Ajánlott irodalom 93

3 Közelítő algoritmusok 94

3.1. Közelítés kis additív hibával 95

3.2. Közelítés kis multiplikatív hibával96

3.3. Az euklidészi utazó ügynök probléma . 102

3.4. Ajánlott irodalom 106

4 Ütemezési algoritmusok 107

4.1. Alapfogalmak, problématípusok. 107

4.2. Egygépes ütemezések. 108

4.3. Ütemezés párhuzamos gépeken 109

4.4. Két megoldott eset 113

4.5. Ládapakolás 117

4.6. Ajánlott irodalom 117

4.7. Függelék . 118

5 Megbízható hálózatok tervezése 122

5.1. Hálózatok megbízhatósága . 122

5.2. Gráfok összefüggősége122

5.3. Az összefüggőség kiszámítása 124

5.4. Többszörösen összefüggő részgráfok126

5.5. Diszjunkt fenyők és feszítőfák 132

5.5.1. Többszörösen összefüggő irányítások 135

5.6. Ajánlott irodalom 137

 Előszó

 A huszadik század közepén sokan gondolták, hogy a véges sok eset átvizsgálásával megoldható matematikai problémák a számítógépek elterjedésével érdektelenné válnak. A tapasztalat azóta megcáfolta ezt a vélekedést: a gyakorlati élet számos olyan feladatot vet fel, amelyekben az összes eset kipróbálása még számítógéppel is reménytelenül sokáig tartana. Ha például néhány várost olyan sorrendben kell végiglátogatni, hogy az útiköltség a legkedvezőbb legyen, akkor az összes lehetséges sorrend átvizsgálása a ma elképzelhet ő legmodernebb szuperszámítógéppel már 30 város esetén is tovább tartana, mint a Naprendszer várható élettartama.

Éppen ezért a huszadik század második felétől gyors fejlődésnek indult az olyan módszerek kutatása, amelyek az egyszerű próbálgatásnál jóval hatékonyabban oldják meg a gyakorlati életből származó feladatokat. A matematikának több, egymást részben átfedő ága foglalkozik ilyen kérdésekkel: az operációkutatás, a számítástudomány és a kombinatorikus optimalizálás.

Könyvünkben ezeknek a tudományterületeknek az anyagából válogatunk. Az első négy fejezetben általánosabb, átfogó módszereket mutatunk be, a hátralévő négy fejezetben pedig konkrét esettanulmányokban alkalmazzuk a kombinatorikus optimalizálás módszereit.

A könyv eredetileg a BME-n a műszaki informatikus hallgatók számára tartott Rendszeroptimalizálás című, valamint az alkalmazott matematikus hallgatók számára tartott Kombinatorikus optimalizálás című tárgyakhoz készült. Azt reméljük azonban, hogy a tudományegyetemek matematikusképzésében meghirdetett, hasonló témájú tárgyak hallgatói is haszonnal forgathatják. A könyv megértéséhez szükséges előismeretek nem lépik túl az alapképzésében oktatott matematikai alapműveltség szintjét (lineáris algebra, gráfelmélet és algoritmuselmélet elemei).

A könyv megírásához felhasználtuk Jordán Tibor és Recski András egy korábbi egyetemi jegyzetét, valamint két kollégánk, Csákány Rita és Radics Norbert meg nem jelent kéziratainak részleteit. Nagyon hálásak vagyunk továbbá Frank Andrásnak, akinek Operációkutatás című egyetemi jegyzetét az 1. fejezet megírásánál felhasználtuk, és akinek egyéb egyetemi előadásai a könyv többmás fejezetére is hatással voltak. Köszönetet mondunk még Helle Zitának, Salamon Gábornak, Szegő Lászlónak és Wiener Gábornak, akik a könyv egyes fejezeteihez számos értékes észrevételt tettek. Végül köszönjük a Pro Renovanda Cultura Hungariae alapítvány ’Tudomány az oktatásban’ szakalapítványának a könyv megírásához nyújtott támogatását.