WikiZero - Optymalizacja (matematyka)

otwórz projekt wikipedii.

Ten termin ma inne znaczenie, patrz Optymalizacja .

Optymalizacja - w matematyka , informatyka i badania operacyjne zadanie znalezienie ekstremum (minimum lub maksimum) funkcja docelowa w jakiejś skończonej domenie wymiarowej przestrzeń wektorowa ograniczony zestaw liniowy i / lub nieliniowe równości i / lub nierówności .

Teoria i metody rozwiązywania problemu optymalizacji polegają na studiowaniu programowania matematycznego .

Programowanie matematyczne to dziedzina matematyki, która rozwija teorię, metody numeryczne do rozwiązywania wielowymiarowych problemów z ograniczeniami. W przeciwieństwie do klasycznej matematyki, programowanie matematyczne dotyczy matematycznych metod rozwiązywania problemów ze znalezieniem najlepszych opcji ze wszystkich możliwych. [1]

W toku projekt zazwyczaj jest to zadanie określenia najlepszego, w pewnym sensie struktury lub wartości parametry przedmioty. Takie zadanie nazywa się optymalizacją. Jeśli optymalizacja jest związana z obliczeniami optymalne wartości parametry danej struktury obiektu, nazywane są optymalizacją parametryczną . Zadaniem wyboru optymalnej struktury jest optymalizacja strukturalna .

W ten sposób sformułowano standardowy problem optymalizacji matematycznej. Wśród elementów χ tworzących zbiór Χ znajdź element χ *, który dostarcza minimalną wartość f (χ *) danej funkcji f (χ). Aby poprawnie ustawić problem optymalizacji, musisz określić:

1. Dopuszczalny zestaw to zbiór X = {x → | gi (x →) ≤ 0, i = 1, ..., m} ⊂ Rn {displaystyle matembb {X} = {{vec {x}} | g_ {i} ({vec {x }}) qq 0, i = 1, kropki, m} zestaw matbb {R} ^ {n}} ;
2. Funkcja docelowa to mapowanie f: X → R {displaystyle f: Mathbb {X} Mathbb {R}} ;
3. Kryteria wyszukiwania (max lub min).

Następnie rozwiąż problem f (x) → min x → ∈ X {dispystyle f (x) o min _ {{vec {x}} Mathrm {X}}} oznacza jeden z:

1. Pokaż, że X = ∅ {displaystyle Mathbb {X} = nic} .
2. Pokaż, że funkcja celu f (x →) {displaystyle f ({vec {x}})} nie ogranicza się do dna.
3. Znajdź x → ∗ ∈ X: f (x → ∗) = min x → ∈ X f (x →) {displaystyle {vec {x}} ^ {*} Mathbb {X}: f ( {vec {x}} ^ {*}) = min _ {{vec {x}} Mathbb {X}} f ({vec {x}})} .
4. Jeśli ∄ x → ∗ {displaystyleexists {vec {x}} ^ {*}} następnie znajdź inf x → ∈ X f (x →) {displaystyle inf _ {{vec {x}} Mathbb {X}} f ({vec {x}})} .

Jeśli zminimalizowana funkcja nie jest wypukły , często ogranicza się do znalezienia lokalnych minimów i maksimów: punkty x 0 {displaystyle x_ {0}} takie, że wszędzie w pewnym sąsiedztwie ich f (x) ≥ f (x 0) {displaystyle f (x) ge f (x_ {0})} dla minimum i f (x) ≤ f (x 0) {displaystyle f (x) q f ​​(x_ {0})} na maksimum.

Jeśli dopuszczalny zestaw X = R n {displaystyle Mathbb {X} = Mathbb {R} ^ {n}} wtedy takie zadanie nazywa się bezwarunkowym problemem optymalizacji , w przeciwnym razie nazywane jest zadaniem optymalizacji warunkowej .

Ogólna rejestracja zadań optymalizacyjnych określa szeroką gamę ich klas. Wybór metody zależy od klasy zadania (skuteczność jego rozwiązania). Klasyfikacja zadań jest określona przez: funkcję celu i dopuszczalny region (zdefiniowany przez system nierówności i równości lub przez bardziej złożony algorytm). [2]

Metody optymalizacji są klasyfikowane zgodnie z zadaniami optymalizacji:

• Metody lokalne: zbiegają się do pewnego lokalnego ekstremum funkcji celu. W przypadku unimodalnej funkcji celu, to ekstremum jest unikalne i będzie globalnym maksimum / minimum.
• Metody globalne: radzenie sobie z wielofunkcyjnymi funkcjami celu. W globalnym wyszukiwaniu głównym zadaniem jest identyfikacja trendów w globalnym zachowaniu funkcji celu.

Aktualne metody wyszukiwania można podzielić na trzy duże grupy:

1. deterministyczny;
2. losowy (stochastyczny);
3. połączone.

Kryterium wymiaru dopuszczalnego zestawu dzieli się na metody optymalizacji jednowymiarowej i metody optymalizacji wielowymiarowej .

Poprzez formę funkcji celu i dopuszczalnego zestawu problemy optymalizacji i metody ich rozwiązania można podzielić na następujące klasy:

Zgodnie z wymogami płynności i obecności pochodnych cząstkowych w funkcji celu, można je również podzielić na:

• metody bezpośrednie wymagające jedynie obliczeń funkcji celu w punktach aproksymacji;
• metody pierwszego rzędu : wymaga obliczenia pierwszych pochodnych cząstkowych funkcji;
• metody drugiego rzędu: wymagają obliczenia drugich pochodnych cząstkowych, tj. hessian funkcja celu.

Ponadto metody optymalizacji są podzielone na następujące grupy:

W zależności od charakteru zestawu X zadania programowania matematycznego są klasyfikowane jako:

Ponadto sekcje programowania matematycznego są programowanie parametryczne , programowanie dynamiczne i programowanie stochastyczne .

Programowanie matematyczne jest wykorzystywane w rozwiązywaniu problemów optymalizacyjnych. badania operacyjne .

Sposób znalezienia ekstremum jest całkowicie zdeterminowany przez klasę problemu. Zanim jednak uzyskasz model matematyczny, musisz wykonać 4 etapy modelowania:

• Definiowanie granic systemu optymalizacji
  • Odrzucamy te połączenia obiektu optymalizacji ze światem zewnętrznym, które nie mogą znacząco wpłynąć na wynik optymalizacji, a dokładniej te, bez których rozwiązanie jest uproszczone.
• Wybór zmiennych kontrolowanych
  • „Zamrażamy” wartości niektórych zmiennych (zmiennych niezarządzanych). Inni muszą zaakceptować dowolne wartości z zakresu możliwych rozwiązań (zmienne kontrolowane)
• Definicja ograniczeń dla zmiennych kontrolowanych
  • ... (równość i / lub nierówność)
• Wybieranie numerycznego kryterium optymalizacji (na przykład, wskaźnik wydajności )
  • Utwórz funkcję celu

Zadania programowanie liniowe były pierwszymi dokładnie zbadanymi zadaniami wyszukiwania ekstremum funkcje, jeśli są dostępne ograniczenia jak nierówności . W 1820 Fourier a potem w 1947 George Danzig zaproponował metodę kierunkowego poszukiwania sąsiednich wierzchołków w kierunku zwiększania funkcja docelowa - metoda simplex , który stał się głównym w rozwiązywaniu problemów programowania liniowego.

Obecność terminu „programowanie” w tytule dyscypliny tłumaczy się tym, że pierwsze badania i pierwsze zastosowania liniowe zadania optymalizacyjne były w dziedzinie ekonomii, ponieważ w języku angielskim słowo „programowanie” oznacza planowanie , tworzenie planów lub programów. Jest całkiem naturalne, że terminologia odzwierciedla ścisły związek między matematycznym sformułowaniem problemu a jego interpretacją ekonomiczną (badanie optymalnego programu gospodarczego). Termin „ programowanie liniowe „Zaproponował J. Danzig w 1949 do badania problemów teoretycznych i algorytmicznych związanych z optymalizacją funkcji liniowych w warunkach ograniczeń liniowych.

Dlatego nazwa „programowanie matematyczne” wiąże się z faktem, że celem rozwiązywania problemów jest wybór optymalnego programu działań.

Wybór klasy ekstremalnych problemów zdefiniowanych przez funkcjonalność liniowa na zbiorze określonym liniowymi ograniczeniami należy przypisać lata 30-te. Jednym z pierwszych do zbadania problemów programowania liniowego w ogólnej formie był: John von Neumann - matematyk i fizyk, który udowodnił główne twierdzenie o grach macierzowych i studiował ekonomię model nosząc jego imię i L.V. Kantorovich - Radziecki akademik, laureat Nagroda Nobla (1975), który sformułował szereg problemów programowania liniowego i zaproponował w 1939 r. Metodę ich rozwiązywania ( metoda mnożnika rozstrzygającego ), nieco różni się od metody simpleks.

W 1931 Węgierski matematyk B. Egervari rozważyli sformułowanie matematyczne i rozwiązali problem programowania liniowego zwany „problemem wyboru”, metodę rozwiązania nazwano „ Metoda węgierska „

L. V. Kantorovich wraz z M. K. Gavurin opracowany w 1949 roku potencjalna metoda który jest stosowany podczas rozwiązywania zadania transportowe . W kolejnych pracach L. V. Kantorovicha, V.S Nemchinova , V.V. Novozhilova , A. Lurie , A. Brudno , A. G. Aganbegyan , D. B. Yudina , E. G. Holstein a inni matematycy i ekonomiści byli dalej rozwijani jako matematyczna teoria liniowości i programowanie nieliniowe oraz zastosowanie jej metod do badania różnych problemów gospodarczych.

Techniki programowania liniowego są poświęcone wielu pracom zagranicznych naukowców. W 1941 F.L. Hitchcock zestaw zadanie transportowe . Główną metodą rozwiązywania problemów z programowaniem liniowym jest metoda simplex - został opublikowany w 1949 r. przez J. Danziga. Dalszy rozwój metod programowania liniowego i nieliniowego otrzymanych w pracach G. Kuna , A. Tucker , Gassa (Saul. I. Gass), Charnes (A. Charnes), Beat (EM Beale) i in.

Równolegle z rozwojem programowania liniowego wiele uwagi poświęcono zadaniom programowanie nieliniowe w którym też funkcja celu lub ograniczenia, lub oba są nieliniowe. W 1951 roku praca została opublikowana G. Kuna i A. Tucker , który zawiera niezbędne i wystarczające warunki optymalności do rozwiązywania problemów programowania nieliniowego. Praca ta posłużyła jako podstawa do dalszych badań w tej dziedzinie.

Od 1955 r. Opublikowano wiele artykułów na ten temat programowanie kwadratowe (praca Billa, Barankina i R. Dorfman , Franca (M. Frank) i F. Wolfe [en] , G. Markowitz i inne). W pracach Dennisa (JB Dennis) opracowali Rosen (JB Rosen) i Zontendijk (G. Zontendijk) metody gradientowe rozwiązywanie problemów programowania nieliniowego.

Obecnie dla efektywnego stosowania metod programowania matematycznego i rozwiązywania problemów na komputerach opracowano języki modelowania algebraicznego których przedstawiciele są AMPL i Lingo .

• Abakarov A. Sh., Sushkov Yu. A. Badanie statystyczne pojedynczego globalnego algorytmu optymalizacji . - Postępowanie FORA, 2004.
• Akulich I. L. Programowanie matematyczne w przykładach i problemach: Proc. podręcznik dla studentów gospodarki. specjalne uniwersytety. - M .: Higher School, 1986.
• Gill F., Murray W., Wright M. Praktyczna optymalizacja. Per. z angielskiego - M .: Mir, 1985.
• Girsanov I.V. Wykłady na temat matematycznej teorii problemów ekstremalnych. - M. Iżewsk : SRC Regular and Chaotic Dynamics, 2003. - 118 pkt. - ISBN 5-93972-272-5 .
• Zhiglyavsky A. A., Zhilinkas A. G. Metody poszukiwania ekstremum globalnego. - M .: Science, Fizmatlit, 1991.
• Karmanov V. G. Programowanie matematyczne. - Wydawnictwo fizyczne. literatura, 2004.
• Korn G., Korn T. Podręcznik matematyki dla naukowców i inżynierów. - M .: Science, 1970. - str. 575-576.
• Korshunov Yu M., Korshunov Yu M. Matematyczne podstawy cybernetyki. - M .: Energoatomizdat, 1972.
• Maksimov Yu. A., Fillipovskaya E. A. Algorytmy do rozwiązywania problemów programowania nieliniowego. - M .: MEPI, 1982.
• Maksimov Yu A. Algorytmy programowania liniowego i dyskretnego. - M .: MEPI, 1980.
• A. Plotnikov Programowanie matematyczne = kurs ekspresowy. - 2006. - str. 171. - ISBN 985-475-186-4 .
• Rastrigin L. А. Statystyczne metody wyszukiwania. - M., 1968.
• Diagonalne globalne metody optymalizacji (zasób elektroniczny) / Sergeev Ya.D., Kvasov D.E. - M .: FIZMATLIT, 2008. 341s.
• Hemdi A. Taha. Wprowadzenie do badań operacyjnych = Badania operacyjne: wprowadzenie. - 8 wyd. - M .: Williams , 2007. - str. 912. - ISBN 0-13-032374-8 .
• Kini R. L., Raifa H. Podejmowanie decyzji w wielu kryteriach: Preferencje i substytucje. - M .: Radio i komunikacja, 1981. - 560 str.
• S. Zukhovitsky , L. Avdeeva. Programowanie liniowe i wypukłe. - 2nd ed., Pererab. i dodatkowe .. - M .: Publishing "Science", 1967.
• Minaev Yu. N. Stabilność ekonomicznych i matematycznych modeli optymalizacji. - M .: Statistics, 1980.
• Moiseev N. N. Metody numeryczne w teorii systemów optymalnych. - M: Science, 1971. - 424 str.
• Moiseev N. N. Elementy teorii systemów optymalnych. - M: Science, 1975. - 528 p.
• Moiseev N. N. , Ivanilov Yu P., Stolyarova E.M. Metody optymalizacji. - M: Science, 1978. - 352 p.
• Degtyarev Yu I. Metody optymalizacji. - M: Radio radzieckie, 1980. - 272 p.
• Reclaith G., Raivindran A., Ragsdel K. Optymalizacja w inżynierii. - M .: Mir, 1986. - 400 p.
• Romanovsky IV Algorytmy rozwiązywania ekstremalnych problemów. - M: Science, 1977. - 352 p. - 16 000 kopii