Krekó Béla: Lineáris programozás

ELŐSZÓ A jelen könyv átdolgozott és bővített változata az 1962-ben megjelent "Lineáris programozás" című kötetnek, amely azóta teljesen elfogyott. Az átdolgozás az időközben szerzett oktatási tapasztalatok alapján történt, a bővítést pedig az a szándék tette indokolttá, hogy az új kiadás tükrözze az optimumszámítás területén elért fejlődést mind elméleti, mind gyakorlati szempontból. Az elmondottaknak megfelelően, az új könyvben szerepel már - többek között - az általánosított szállítási probléma megoldása, a felső korláttal kapcsolatos számítási technika, továbbá az ún. dekompozíciós módszer is, amely bizonyára jelentős szerpeet fog játszani a tervezés elméletében és gyakorlatában. Az eddiginél nagyobb teret kaptak azok a megoldási módszerek, amelyek nem a közismert szimplex-módszeren alapulnak. Jelentősen bővült a gyakorlati alkalmazásokkal foglalkozó rész is. Vissza TARTALOM Előszó 9 A lineáris programozás technikája Bevezetés 13 A közgazdasági tudományok és a matematika kapcsolata 13 A programozási módszerekről 15 Példák a lineáris programozásra 16 Mi tehát a lineáris programozás? 21 Történeti megjegyzések 24 A szállítási probléma 26 A probléma megfogalmazása 26 A költségmatrix átalakítása 28 Az induló program 31 A program javítása 36 A potenciálok módszere 40 Alternatív lehetőségek az optimalizálásban 45 Névleges állomások beiktatása 46 Szállítási feladat kapacitáskorlátokkal 50 Még egyszer az induló programról 60 Az általános szimplex-módszer 65 A normál-feladat 65 Az induló program 66 A program javítása 68 Van-e mindig megoldás? 78 A degeneráció 79 Alternatív optimumok 82 A módosított normál-feladat 85 Az általános eset 92 A dualitás 101 Speciális problémák 111 Egy szállítási feladat módosítása 111 Alulról és felülről korlátozott változók 114 Számolás előjelkorlátozás nélkül 125 Egy ellenőrzési lehetőség 127 Variánsszámítás az általános szimplex-módszerrel 130 A parametrikus programozás 135 A konvex programozásról 143 A lineáris programozás matematikai alapjai Halmazelméleti alapfogalmak 153 Halmazok 153 Műveletek halmazokkal 154 Az alaphalmaz 155 Matrixaritmetika 157 Alapfogalmak 157 Nagyságrendi relációk és műveleti szabályok 164 Számolás blokkokra bontott matrixokkal 177 A lineáris térről 180 Az n elemű vektorok tere 180 A lineáris függetlenség 185 Dimenzió és bázis 192 Matrixok rangja 195 Az euklideszi tér 197 Konvex halmazok 204 Az elemi bázistranszformáció és alkalmazásai 210 Az elemi bázistranszformáció és alkalmazásai 210 az elemi bázistranszformáció 217 a kompatiblitás 219 A matrixok rangjának meghatározása 221 Matrixok faktorizációja 225 Lineáris egyenletrendszerek megoldása és matrixok inverziója 225 A lineáris egyenletrendszerek 232 A matrixok inverze 235 Az inverz numerikus meghatározása 240 A bázistranszformációról általában 246 Az ortogonális vetület 251 Lineáris egyenlőtlenségrendszerek 251 Alapfogalmak 254 A normál-rendszer 261 AZ L halmaz szerkezete 277 A szomszédos csúcspontok meghatározása 283 A lineáris programozás és a szimplex-módszer 283 A probléma megfogalmazása 286 A normál-feladat 291 a normál-feladat megoldása degeneráció nélkül 295 A degeneráció 297 A módosított normál-feladat 302 Az általános eset 305 A dualitás 313 A Farkas-féle tétel 316 A duális szimplex-módszer 320 A módosított szimplex-módszer 328 Néhány speciális probléma 328 számolás alulról és felülről korlátozott változókkal 332 Variánsok számítása 334 A parametrikus programozás 338 Az egészsámú lineáris programozás 346 A szállítási probléma 346 A feladat megfogalmazása 349 Alapvető fogalmak és tételek 355 A disztribúciós módszer 359 A degeneráció problémája 363 A klasszikus feladat kapacitáskorlátokkal 367 Az általánosítótt szállítási probléma 368 A lineáris programozási feladatok felbontása 384 az alapfeladat 384 A dekompozíciós módszer 388 Egy numerikus példa 393 A módszer kiegészítése 398 A probléma általános tárgyalása 403 A lineáris pprogramozás egyéb módszerei 405 A megoldó együtthatók módszere 405 A teljes előállítás módszere 413 A gradiens-módszer 419 A lineáris programozás és a játékelmélet 425 A játékelmélet alapfogalmai 425 Néhány alapvető tétel 427 Neumann tétele 431 Egy Numerikus példa 434 A lineáris programozás mint a játékelmélet speciális esete 437 Néhány megjegyzés a játékelmélethez 442 Gyakorlati alkalmazások Az alkalmazás feltételei 445 A közgazdasági-matematikai modellekről 445 Programozási modellek 447 Numerikus példák 453 Egy összetett szállítási probléma 453 Minimális üresfutás 457 Termelési programok összekapcsolása szállítási programokkal 461 Egy termelési probléma 466 Egy speciális gépterhelési feladat 470 A gépterhelési probléma általánosítása 477 Alternatív technológiai lehetőségek 481 Egy mezőgazdasági alkalmazás 484 Optimális létszám-probléma 487 Egy áruellátási probléma 488 Minimális vágási veszteség 493 Néhány probléma általános tárgyalása 497 Az üzemi termelési modellekről általában 497 Kantorovics termelésprogramozási modelljei 499 A magyar papíripar termelési modellje 501 Ágazati kapcsolatok elemzése 506 Optimumszámítás népgazdasági szinten 511 Függelék A magyar módszer 519 A hozzárendelési probléma 519 A szállítási probléma 531 A Kőnig - Egerváry-féle tétel 536 A független pontok és a fedővonalak megkeresése 539 Az iteráció matematikai indokolása 540 Irodalomjegyzék 545 Tárgymutató 555