Matematika a informatika - PDF na stiahnutie zadarmo
1 Prof. Dr. Kurz Winfrieda Hochstättlera v lineárnej optimalizácii matematiky a informatiky LESEPROBE
2 Dielo je chránené autorskými právami. Takto ustanovené práva, najmä právo na rozmnožovanie a distribúciu, ako aj preklad a opätovnú tlač, sú vyhradené, aj keď len čiastočne. Žiadna časť diela nesmie byť reprodukovaná v akejkoľvek podobe (tlač, fotokópia, mikrofilm alebo iný proces) alebo spracovávaná, duplikovaná alebo distribuovaná pomocou elektronických systémov bez písomného súhlasu FernUniversität.
3 Obsah Úvod Notácia Register vii xi xiv 1 Lineárna optimalizácia - Definícia a modelovanie problému Prvé príklady Problém so stravou Chamtivosť nie je vždy dobrá Problém so zmiešaním Všeobecné problémy s lineárnou optimalizáciou Techniky ekvivalentných transformácií Riešenie problému so stravou Z cestovín na zemiaky Grafická metóda Navrhované riešenia cvičení Zbalenie a kombinácie Afinné podpriestory K n Konvexné kužele v K n Konvexné množiny v K n Zhrnutie Navrhované riešenia cvičení Cvičenie Dualita Iný pohľad na problém stravovania Farkas lemma iii
4 iv Obsah 3.3 Veta o dualite lineárneho programovania Dualizácia lineárnych programov Veta o komplementárnom sklze Navrhované riešenia cvičení Polyhedron Dvojtriedna spoločnosť? Bočné povrchy Fasety Rohy a hrany Napríklad permutáter Bočný mriežkový kužeľ a hustá verzia Farkasovej lemy Weylova veta Polarizačný trik pre kužele a Minkowského veta Cvičenia Metóda simplexu 1-kostra polytopu Geometrická myšlienka simplexného algoritmu Opakovanie Gauss-Jordanovho algoritmu Tabuľková forma simplexného algoritmu Pivot výber, degenerácia, konečnosť Komentáre k numerike Dvojfázová metóda Metóda Big M Revidovaný simplexný algoritmus Postoptimalizácia a analýza krokov citlivosti Duálne simplexné hranice Názov hry Navrhované riešenia cvičení
5 Obsah v 6 O zložitosti simplexného algoritmu Prísne polynomické algoritmy a zlomkový batoh Plánovanie nasadenia personálu Klee-Minty Cubes Priemerná doba chodu simplexného algoritmu Dantzig-Wolfeho rozklad Dodatok: Symboly Landau Navrhované riešenia cvičení Elipsoidná metóda Zníženie algoritmických problémov Dĺžka kódovania Lineárne programy Test prípustnosti a optimalizácia Využitie dualitného binárneho vyhľadávania Geometrická idea elipsoidnej metódy Elipsoidná metóda v lineárnom programovaní Ako riešite problém presnou aritmetikou? Optimalizácia a separácia Matematické návrhy riešenia Sputniku pre cvičenia Vnútorné bodové metódy Karmarkarova metóda Projektívna transformácia jednotky simplex Geometrická myšlienka Karmarkarovej metódy Pre analýzu správnosti a doby behu Karmarkarova normálna forma Algoritmus sledovania trasy Geometrické nápady Niektoré prípravy Šikmo-symetrický sebap duálny model Centrálna cesta a optimálny oddiel Nájdenie optimálneho oddielu Nájdenie presného riešenia Všeobecná perspektíva metódy vnútorného bodu
6 vi Obsah 8.4 Navrhované riešenia cvičení Bibliografia 319
7 Kapitola 6 O zložitosti simplexného algoritmu Simplexový algoritmus sa od svojho objavenia v praxi etabloval ako efektívna metóda. Z teoretického hľadiska na to neexistuje skutočne uspokojivé vysvetlenie. V tejto kapitole spoznáme prvý, jednoduchší koncept zložitosti a z tejto perspektívy zvážime simplexný algoritmus. 6.1 Prísne polynomické algoritmy a zlomkový batoh Ak chceme posúdiť kvalitu algoritmu, umožníme pri väčších úlohách tiež dobrý postup na dlhšie počítanie. Najprv však musíme definovať veľkosť úlohy. Mali by sme tiež poskytnúť aspoň približnú definíciu algoritmu. Algoritmom pre problém (alebo pre triedu problému) rozumieme postupnosť presne definovaných pravidiel alebo príkazov, ktoré generujú konkrétny výstup z každého konkrétneho vstupu, príkladu problému, v konečnom počte elementárnych krokov. Takže požadujeme: i) Algoritmus musí byť možné popísať textom konečnej dĺžky. ii) Postupnosť krokov je v každom výpočte jedinečná. iii) Každý elementárny krok možno vykonať mechanicky a efektívne. 189
18 200 Kapitola 6. Zložitosť algoritmu Simplex Ak hľadáme od tretieho poradcu, máme poradcu 1 a 3 a klienta 1 v T. Takže zvýšime premenné poradcu 1 a 3 a zmenšíme ich klienta 1. Pretože c 12 = 2, môžeme zvýšiť iba o 1 bez straty prípustnosti. Poradcu 1 teraz priradíme zákazníkovi 2 a konzultanta 3 zákazníkovi 1. V ďalšom kroku zvýšime duálnu premennú konzultanta 4 na dve a priradíme ju k tretiemu zákazníkovi. Potom sme nastavili duálnu premennú konzultanta 5 na 1. Zákazník 2 je však už dodaný. Takže znova zostavíme náš strom T. Ten obsahuje poradcov 1, 3 a 5 a zákazníkov 2 a 1. Pretože c 13 = 3, opäť iba pribúdame. Nová hranica obsahuje tiež poradcu 4 a zákazníka 3 v strome. Pretože c 14 = c 34 = 4, opäť zmeníme iba duálne premenné o 1.
20 202 Kapitola 6. Zložitosť simplexného algoritmu je daná iba obmedzeniami n nerovností a znakmi n. Vstupná premenná je I (w) = n 2. H n má 2 n vrcholov, menovite všetky vektory v n. Ak teraz môžeme urobiť simplexný algoritmus vhodným skreslením tohto mnohostenu, pri postupe podľa Dantzigovho pravidla budú všetky vrcholy Takto skreslená hyperkocka prechádzať potom ukazuje, že metóda má v počte premenných exponenciálny čas behu. Vo veľkosti vstupných údajov to nemôže byť polynóm. Nasledujúca trieda lineárnych programov (LP n) pre n N robí to, čo chceme, ako si teraz ukážeme. (LP n) max 2 n 1 xn 2 xxn 1 + xn pod x 1 5 4x 1 + xx 1 + 4x 2 + xnxn 1 xxn 1 + xn 5 n. X 0 V prvom rade chceme dokázať, že je to skutočne tak je skreslená hyperkocka. Pozorujeme: Propozícia. Nech x je prípustné pre (LP n). Potom pre všetky i = 1. n: i) Ak x i = 0, potom je i-tá nerovnosť prísna. ii) Ak i-tá nerovnosť nie je prísna, potom x i> 0. Dôkaz. i) Tvrdenie je zjavne správne pre i = 1. Ak i> 1, potom (i 1) -tá nerovnosť poskytne 2 i 1 x i 2 x x i 2 + x i 1 5 i 1.
23 6.3. Klee-Minty kocky 205 min 5 rokov yn 1 ynnyn pod 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. Priradenie yn = 1, yi = 0 pre i = 0. n 1 je prípustné pre úlohu duálnej optimalizácie s hodnotou objektívnej funkcie 5 n. Pretože problém primárnej optimalizácie s daným riešením predpokladá rovnakú hodnotu objektívnej funkcie, musia byť obe optimálnymi riešeniami podľa vety duality. Na druhej strane, ak je x optimálnym riešením primárneho problému, potom kvôli objektívnej funkcii a poslednému obmedzeniu máme 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 Pretože všetky premenné nie sú záporné, vyplýva z toho, že x1 =. = x n 1 = 0 a teda xn = 5 n, teda aj jedinečnosť riešenia. Po týchto prípravách ukážeme: Vetu. Simplexný algoritmus s Dantzigovým pivotným pravidlom vyžaduje 2 n 1 otočných krokov pre (LP n). Dôkaz. Tvrdenie je zjavne ekvivalentné skutočnosti, že v tomto postupe prechádzame 2 n obrazovkami. Ukážeme to pomocou úplnej indukcie na n. Presnejšie, ukážeme:
25 6.3. Klee-Minty Cubes 207 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tableau 2 n 1 Jediným stĺpcom s kladne zníženými nákladmi je stĺpec n-tej premennej a dostaneme ďalšie tablo: 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tabuľka 2 n Toto tiež vyzerá ako rozšírené prvé tablo pre LP n 1, až na to, že stĺpce (n 1) -tej premennej a (n 1) -tej premennej sklzu sú zamenené. To však nemení otočný výber, ktorý musí tomuto swapu porozumieť, pretože nenulové položky v znížených nákladoch sa líšia v pároch, a preto je stĺpec s najväčšou položkou vždy jedinečný. Takže musíme znova urobiť 2 n 1 iterácie, aby sme pristáli na Tableau 2 n. 2c n A 0 0 I n b 2c n 1 4c n Tabuľka 2 n Toto je optimálne, ale dosiahlo sa to až po 2 n 1 krokoch. Dokázali sme teda: Vetu. Simplexný algoritmus využívajúci Dantzigovo otočné pravidlo nie je striktne polynomiálnym algoritmom, a teda ani polynomiálnym algoritmom. Dôkaz. Veľkosť vstupných dát je I (LP n) = O (n 2) alebo LP n = O (n 3), pretože najväčšie číslo 5 n možno kódovať pomocou maximálne 3 n bitov.