Matematika és informatika - PDF ingyenes letöltés
1 Prof. Dr. Winfried Hochstättler lineáris optimalizálási kurzus LESEPROBE matematika és informatika
2 A mű szerzői jogi védelem alatt áll. Az ezzel megállapított jogok, különösen a sokszorosítás és terjesztés, valamint a fordítás és az újranyomás joga fenntartva van, még ha csak részben is. A FernUniversität írásbeli engedélye nélkül a munka egyetlen része sem reprodukálható semmilyen formában (nyomtatás, fénymásolás, mikrofilm vagy bármilyen más eljárás), feldolgozás, sokszorosítás vagy terjesztés elektronikus rendszerek segítségével.
3 Tartalom-jegyzék Bevezetés Jelölési index vii xi xiv 1 Lineáris optimalizálás - A probléma meghatározása és modellezése Első példák A diétás probléma A kapzsiság nem mindig jó keverési probléma Az általános lineáris optimalizálási probléma technikái egyenértékű transzformációkhoz A diéta problémájának megoldása a tésztától a burgonyáig A grafikus módszer Javasolt megoldások a gyakorlatokhoz Csomagolás és kombinációi K n konvex kúpjának affin alterületei K n domború kúpjai konvex halmazai K n összegzés Javasolt megoldások a gyakorlatokhoz Kettősség Az étrendprobléma másik nézete Farkas lemma iii
4 iv Tartalomjegyzék 3.3 A lineáris programozás kettősségi tétele Lineáris programok dualizálása A kiegészítő csúszás tétele Javasolt megoldások a gyakorlatokhoz Polyhedron Kétosztályú társadalom? Oldalsó felületek Fazetták Sarok és élek Például a permutahedron Az oldalrács kúpja és a Farkas Lemma sűrű változata A Weyl-tétel A kúpok polarizációs trükkje és a Minkowski-tétel Gyakorlatok A szimplex módszer A politop 1 csontváza A szimplex algoritmus geometriai elképzelése A Gauss-Jordan algoritmus ismétlése A szimplex algoritmus táblázatos formája Pivot kiválasztás, degeneráció, végesség A numerikus megjegyzések A kétfázisú módszer A Big M módszer A felülvizsgált szimplex algoritmus D-optimalizálás és érzékenység A játék neve Javasolt megoldások a gyakorlatokra
5 Tartalom v 6 A szimplex algoritmus bonyolultságáról Szigorúan polinomiális algoritmusok és töredékes hátizsák Személyzeti telepítés megtervezése Klee-Minty kockák A szimplex algoritmus átlagos futási ideje Dantzig-Wolfe dekompozíció Függelék: A Landau szimbólumok Javasolt megoldások a feladatokhoz Az ellipszoid módszer problémái Az algipszis módszer problémái Az algoritmus csökkentése Lineáris programok elfogadhatósági tesztje és optimalizálása A kettősség bináris keresésének kiaknázása Az Ellipszoid módszer geometriai elképzelése Az Ellipszoid módszer a lineáris programozásban Hogyan oldja meg a problémát pontos aritmetikával? Matematikai Sputnik megoldási javaslatok optimalizálása és elkülönítése a gyakorlatokhoz Belső pont módszerek A Karmarkar módszer Az egység szimplex projektív transzformációja A Karmarkar módszer geometriai ötlete a helyesség és a futásidejű elemzéshez A Karmarkar normál forma Útkövető algoritmus Geometriai ötletek Néhány előkészítés A ferdeséges szimmetrikus önduális modell A központi út és az optimális partíció Az optimális partíció megtalálása Pontos megoldás keresése Általános belső pont-módszer Outlook
6 vi Tartalomjegyzék 8.4 Javasolt megoldások a feladatokhoz Irodalomjegyzék 319
7 6. fejezet A szimplex algoritmus bonyolultságáról A szimplex algoritmus felfedezése óta hatékony gyakorlatnak bizonyult a gyakorlatban. Elméleti szempontból erre nincs igazán kielégítő magyarázat. Ebben a fejezetben megismerjük a komplexitás első, egyszerűbb fogalmát, és ebből a szempontból vesszük figyelembe a szimplex algoritmust. 6.1 Szigorúan polinomiális algoritmusok és töredékes hátizsák Ha fel akarjuk mérni egy algoritmus minőségét, akkor egy jó eljárást is lehetővé teszünk, hogy nagyobb feladatok esetén hosszabb ideig számoljunk. De először meg kell határoznunk a feladat méretét. Legalább hozzávetőlegesen meg kell adnunk egy algoritmus definícióját is. Egy probléma (vagy egy problémaosztály) algoritmusa alapján megértünk egy jól definiált szabály vagy parancs sorozatát, amelyek az egyes bemenetekből, a probléma egy példányából, meghatározott számú kimenetet generálnak véges számú elemi lépésben. Tehát követeljük: i) Az algoritmusnak véges hosszúságú szövegben leírhatónak kell lennie. ii) A lépések sorrendje minden számításban egyedi. iii) Minden elemi lépést mechanikusan és hatékonyan lehet végrehajtani. 189
18 200 6. fejezet. A Simplex algoritmus komplexitása Ha a harmadik tanácsadótól kezdve keresünk, akkor az 1. és a 3. tanácsadó, az 1. ügyfél pedig a T-ben van. Tehát növeljük az 1. és a 3. tanácsadó változóit, és csökkentjük az 1. kliensét. Mivel c 12 = 2, csak 1-gyel növekedhetünk anélkül, hogy elveszítenénk az elfogadhatóságot. Most az 1. tanácsadót a 2. ügyfélhez, a 3. tanácsadót pedig az 1. ügyfélhez rendeljük. A következő lépésben a 4. tanácsadó kettős változóját kettőre növeljük, és hozzárendeljük a harmadik ügyfélhez. Ezután az 5. tanácsadó kettős változóját 1-re állítjuk. A 2. ügyfél azonban már meg van adva. Tehát újra elkészítjük a T fánkat. Ez tartalmazza az 1., 3. és 5. tanácsadót, valamint a 2. és 1. tanácsadót. Mivel c 13 = 3, csak ismét növekedünk. Az új él a 4. és a 3. tanácsadót is tartalmazza a fában. Mivel c 14 = c 34 = 4, megint csak a kettős változót változtatjuk meg 1-vel.
20 202 6. fejezet. A szimplex algoritmus összetettségét csak n egyenlőtlenség és n előjel korlátozás adja. A bemeneti változó I (w) = n 2. H n-nek 2 n csúcsa van, nevezetesen az n összes vektora. Ha a szimplex algoritmust ennek a sokszögnek a megfelelő torzításával tudjuk megtenni, akkor Dantzig-szabály folytatásakor a Az így torzított hiperkocka bejárása azt mutatja, hogy a módszer exponenciális futási idővel rendelkezik a változók számát tekintve. Ez nem lehet polinom a bemeneti adatok méretében. A következő lineáris programok (LP n) n N esetében azt csinálnak, amit akarunk, amint ezt most megmutatjuk. (LP n) max 2 n 1 xn 2 xxn 1 + xn x 1 5 4x 1 + xx 1 + 4x 2 + xnxn 1 xxn 1 + xn 5 n. X 0 Először is be akarjuk bizonyítani, hogy ez valójában torz hiperkocka. Megfigyeljük: Tétel. Legyen x megengedett (LP n) esetén. Ekkor minden i = 1. n: i) Ha x i = 0, akkor az i-edik egyenlőtlenség szigorú. ii) Ha az i-edik egyenlőtlenség nem szigorú, akkor x i> 0. Bizonyítás. i) Az állítás nyilvánvalóan helytálló i = 1 esetén. Ha i> 1, az (i 1) -edik egyenlőtlenség 2 i 1 x i 2 x x i 2 + x i 1 5 i 1.
23 6.3. Klee-Minty kockák 205 perc 5 év yn 1 ynnyn y 1 + 4y 2 + 8y nyn 2 n 1 y 2 + 4y n 1 yn 2 n 2 yn 2 yn 2 nyn 1 + 4y n 2 yn 1 y 1. yn 0 alatt. Az yn = 1, yi = 0 hozzárendelés i = 0. esetén n 1 megengedett az 5 n objektív függvényértékkel rendelkező kettős optimalizálási probléma esetén. Mivel az adott megoldás elsődleges optimalizálási problémája ugyanazt az objektív függvényértéket feltételezi, a kettősség tétel szerint mindkettőnek optimális megoldásnak kell lennie. Másrészt, ha x az optimális megoldás az elsődleges problémára, akkor az objektív függvény és az utolsó korlátozás miatt 2 n 1 xn 2 xxn 1 + xn = 5 n 2 nxn 1 xxn 1 + xn 5 n 2 n 1 xn 2 xxn 1 0 Mivel minden változó nem negatív, ebből következően x1 =. = x n 1 = 0 és így xn = 5 n, így a megoldás egyedisége is. Ezen előkészületek után megmutatjuk: Mondat. A Dantzig-féle forgatókönyvű szimplex algoritmushoz 2 n 1 elfordulási lépés szükséges (LP n). Bizonyíték. Az állítás nyilvánvalóan megegyezik azzal a ténnyel, hogy ebben az eljárásban 2 n táblát vezetünk át. Ezt a n teljes indukciójával mutatjuk be. Pontosabban:
25 6.3. Klee-Minty kockák 207 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tábla 2 n 1 Az egyetlen pozitív csökkentett költségű oszlop az n-edik változó oszlopa, és megkapjuk a következő táblát: 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tábla 2 n Ez az LP n 1 kiterjesztett első táblájának is látszik, azzal a különbséggel, hogy az (n 1) -edik és az (n 1) -edik változó oszlopai cserélődnek. Ez azonban nem változtatja meg a forgatókönyvet, amelynek meg kell értenie ezt a csereügyletet, mivel a csökkentett költségek nulla nélküli bejegyzései páronként eltérőek, ezért a legnagyobb bejegyzéssel rendelkező oszlop mindig egyedi. Tehát ismét 2 n 1 ismétlést kell végrehajtanunk, hogy a Tableau 2 n-nél landoljunk. 2c n A 0 0 I n b 2c n 1 4c n Tábla 2 n Ez az optimális, de csak 2 n 1 lépés után érte el. Így bebizonyítottuk: Tétel. A Dantzig pivot-szabályát használó szimplex algoritmus nem szigorúan polinomiális algoritmus, ezért sem polinom algoritmus. Bizonyíték. A bemeneti adat mérete I (LP n) = O (n 2) vagy LP n = O (n 3), mivel a legnagyobb előforduló 5 n szám legfeljebb 3n bit használatával kódolható.