Matematică și Informatică - PDF Descărcare gratuită
1 prof. Dr. Curs Winfried Hochstättler de optimizare liniară LESEPROBE matematică și informatică
2 Opera este protejată de drepturile de autor. Drepturile stabilite prin aceasta, în special dreptul de reproducere și distribuție, precum și traducerea și reimprimarea, sunt rezervate, chiar dacă doar parțial. Nicio parte a lucrării nu poate fi reprodusă sub nicio formă (tipărit, fotocopiat, microfilm sau orice alt proces) sau procesată, duplicată sau distribuită folosind sisteme electronice fără permisiunea scrisă a FernUniversität.
3 Cuprins Introducere Notare Index vii xi xiv 1 Optimizare liniară - Definirea și modelarea problemelor Primele exemple O problemă de dietă Lăcomia nu este întotdeauna bună O problemă de amestecare Problema generală de optimizare liniară Tehnici pentru transformări echivalente Rezolvarea problemei dietei de la paste la cartofi Metoda grafică Soluții sugerate pentru înfășurarea exercițiilor și combinații Subspații afine de K n Conuri convexe în K n Seturi convexe în K n Rezumat Soluții sugerate pentru exerciții Dualitate O altă viziune a problemei dietei Farkas lemma iii
4 iv Cuprins 3.3 Teorema dualității programării liniare Dualizarea programelor liniare Teorema alunecării complementare Soluții sugerate pentru exerciții Poliedru Societate din două clase? Suprafețe laterale Fațete Colțuri și margini De exemplu, permutaedrul Conul de rețea lateral și versiunea densă a Lemei Farkas Teorema Weyl Trucul de polarizare pentru conuri și teorema Minkowski Exerciții Metoda simplex 1-scheletul unui politop Ideea geometrică a algoritmului simplex Repetarea algoritmului Gauss-Jordan Forma tabloului algoritmului simplex Selecția pivotului, degenerarea, finitudinea Comentarii la numerică Metoda în două faze Metoda Big M Algoritmul simplex revizuit Analiza post-optimizare și sensibilitate Analiza pasului Simplex dual Numele jocului Soluții sugerate la exerciții
5 Cuprins v 6 Despre complexitatea algoritmului simplex Algoritmi strict polinomiali și un rucsac fracționat Planificarea desfășurării personalului Cuburi Klee-Minty Durata medie de funcționare a algoritmului simplex Descompunerea Dantzig-Wolfe Anexă: Simbolurile Landau Soluții sugerate pentru exerciții Metoda elipsoidelor Reduceri ale problemelor algoritmice Programe liniare Test de admisibilitate și optimizare Exploatarea dualității Căutare binară Ideea geometrică a metodei elipsoidelor Metoda elipsoidelor în programarea liniară Cum rezolvați problema cu aritmetica exactă? Optimizarea și separarea unei propuneri matematice de soluții Sputnik pentru exerciții Metode punct interne Metoda Karmarkar Transformarea proiectivă a unității simplex Ideea geometrică a metodei Karmarkar Pentru corectitudine și analiza timpului de rulare Forma normală Karmarkar Un algoritm de urmărire a căilor Idei geometrice Câteva pregătiri Modelul auto-dual asimetric Calea centrală și partiția optimă Găsirea partiției optime Găsirea unei soluții exacte O metodă generică pentru puncte interioare Outlook
6 vi Cuprins 8.4 Soluții sugerate pentru exerciții Bibliografie 319
7 Capitolul 6 Despre complexitatea algoritmului simplex Algoritmul simplex sa stabilit ca metodă eficientă în practică de la descoperirea sa. Din punct de vedere teoretic, nu există o explicație cu adevărat satisfăcătoare pentru acest lucru. În acest capitol vom cunoaște un prim concept mai simplu de complexitate și vom lua în considerare algoritmul simplex din acest punct de vedere. 6.1 Algoritmi strict polinomiali și un rucsac fracționat Dacă dorim să evaluăm calitatea unui algoritm, vom permite, de asemenea, o procedură bună pentru a calcula mai mult pe sarcini mai mari. Dar mai întâi trebuie să definim dimensiunea unei sarcini. De asemenea, ar trebui să oferim cel puțin o definiție aproximativă a unui algoritm. Printr-un algoritm pentru o problemă (sau pentru o clasă de problemă) înțelegem o secvență de reguli sau comenzi bine definite care generează o ieșire specifică din fiecare intrare specifică, o instanță a problemei, într-un număr finit de pași elementari. Deci, cerem: i) Un algoritm trebuie să poată fi descris într-un text de lungime finită. ii) Secvența pașilor este unică în fiecare calcul. iii) Fiecare etapă elementară poate fi realizată mecanic și eficient. 189
18 200 Capitolul 6. Complexitatea algoritmului Simplex Dacă căutăm pornind de la cel de-al treilea consilier, avem consilierul 1 și 3 și clientul 1 în T. Deci creștem variabilele consilierului 1 și 3 și le reducem pe cele ale clientului 1. Din c 12 = 2, putem crește doar cu 1 fără a pierde admisibilitatea. În pasul următor mărim variabila duală a consultantului 4 la doi și îl atribuim celui de-al treilea client. Apoi stabilim variabila duală a consultantului 5 la 1. Cu toate acestea, clientul 2 este deja furnizat. Așadar, ne construim din nou arborele T. Acesta conține consultanții 1, 3 și 5 și clienții 2 și 1. Deoarece c 13 = 3, creștem din nou doar cu. Noul margine include și consilierul 4 și clientul 3 în arbore. Deoarece c 14 = c 34 = 4, schimbăm din nou doar variabilele duale cu 1.
20 202 Capitolul 6. Complexitatea algoritmului simplex este dată doar de n inegalități și n restricții de semn. Variabila de intrare este I (w) = n. Pentru a parcurge hipercubul distorsionat în acest fel, se arată că metoda are timp de funcționare exponențial în numărul de variabile. Acest lucru nu poate fi polinomial în dimensiunea datelor de intrare. Următoarea clasă de programe liniare (LP n) pentru n N face ceea ce dorim, așa cum vom arăta acum. (LP n) max 2 n 1 xn 2 xxn 1 + xn sub x 1 5 4x 1 + xx 1 + 4x 2 + xnxn 1 xxn 1 + xn 5 n. X 0 În primul rând, vrem să dovedim că acesta este de fapt este un hipercub distorsionat. Observăm: Propunere. Fie x admisibil pentru (LP n). Atunci pentru toate i = 1. n: i) Dacă x i = 0, atunci inegalitatea a i-a este strictă. ii) Dacă inegalitatea i-a nu este strictă, atunci x i> 0. Dovadă. i) Afirmația este evident corectă pentru i = 1. Dacă i> 1, atunci (i 1) -a inegalitate produce 2 i 1 x i 2 x x i 2 + x i 1 5 i 1.
23 6.3. Cuburi Klee-Minty 205 min 5y yn 1 ynnyn sub 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 1st yn 0. Atribuirea yn = 1, yi = 0 pentru i = 0. n 1 este permisă pentru problema de optimizare duală cu valoarea funcției obiective 5 n. Deoarece problema de optimizare primară presupune aceeași valoare a funcției obiective cu soluția dată, ambele trebuie să fie soluții optime conform principiului dualității. Pe de altă parte, dacă x este o soluție optimă a problemei primare, atunci datorită funcției obiective și a ultimei restricții avem 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 Deoarece toate variabilele sunt non-negative, rezultă că x1 =. = x n 1 = 0 și astfel xn = 5 n, deci și unicitatea soluției. După aceste pregătiri arătăm: Frază. Algoritmul simplex cu regula pivotului Dantzig necesită 2 n 1 pași pivot pentru (LP n). Dovadă. Afirmația este în mod evident echivalentă cu faptul că trecem prin 2 n tablouri în această procedură. Arătăm acest lucru prin inducție completă pe n. Mai precis, arătăm:
25 6.3. Cuburi Klee-Minty 207 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tablou 2 n 1 Singura coloană cu costuri reduse pozitive este coloana variabilei a n-a și obținem următorul tablou: 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tablou 2 n Aceasta arată, de asemenea, ca un prim tablou extins pentru LP n 1, cu excepția faptului că coloanele variabilei (n 1) a și a variabilei de alunecare (n 1) sunt schimbate. Cu toate acestea, acest lucru nu schimbă selecția pivot, care trebuie să înțeleagă acest swap, deoarece intrările diferite de zero în costurile reduse sunt diferite în perechi și, prin urmare, coloana cu cea mai mare intrare este întotdeauna unică. Prin urmare, trebuie să facem din nou 2 iterații pentru a ateriza la Tabloul 2 n. 2c n A 0 0 I n b 2c n 1 4c n Tablou 2 n Acest lucru este optim, dar a fost atins doar după 2 n 1 pași. Am demonstrat astfel: Teorema. Algoritmul simplex care utilizează regula pivotului lui Dantzig nu este un algoritm strict polinomial și, prin urmare, nici un algoritm polinomial. Dovadă. Dimensiunea datelor de intrare este I (LP n) = O (n 2) sau LP n = O (n 3), deoarece cel mai mare număr care apare 5 n poate fi codat folosind maximum 3n biți.