Optimalizálás (matematika)

Az optimalizálás ( matematikában , számítástechnikában és operációkutatásban ) az a feladat , hogy egy véges dimenziós vektortér valamely tartományában egy célfüggvény szélsőértékét (minimumát vagy maximumát) találjuk meg, amelyet lineáris és/vagy nem változó halmaz korlátoz. lineáris egyenlőségek és/vagy egyenlőtlenségek .

Az optimalizálási probléma megoldásának elméletét és módszereit a matematikai programozás tanulmányozza .

A matematikai programozás  a matematikának egy olyan ága, amely elméletet, numerikus módszereket fejleszt többdimenziós problémák korlátokkal történő megoldására. [egy]

Az optimalizálási probléma kijelentése

A tervezési folyamat során a feladat általában az objektumparaméterek bizonyos értelemben legjobb struktúrájának vagy értékeinek meghatározása . Az ilyen problémát optimalizálási feladatnak nevezzük. Ha az optimalizálás egy adott objektumstruktúra optimális paraméterértékeinek kiszámításához kapcsolódik , akkor ezt paraméteres optimalizálásnak nevezzük . Az optimális szerkezet kiválasztásának problémája a szerkezeti optimalizálás .

A szabványos matematikai optimalizálási feladat így van megfogalmazva. Az X halmazokat alkotó χ elemek között keressünk egy χ * elemet , amely megadja az adott f(χ) függvény minimális f(χ * ) értékét. Az optimalizálási probléma helyes felvetéséhez be kell állítani:

1. A megengedett halmaz  a halmaz ;
2. Objektív függvény  - leképezés ;
3. Keresési feltétel (max vagy min).

Ezután a probléma megoldása a következők egyikét jelenti:

1. Mutasd meg .
2. Mutassuk meg, hogy a célfüggvény nem korlátos alább.
3. Keresse meg .
4. Ha , akkor keresse meg .

Ha a minimalizálandó függvény nem konvex , akkor gyakran a lokális minimumok és maximumok megtalálására korlátozódnak: olyan pontok , amelyek a szomszédságukban mindenhol minimum és maximum értékét jelentik.

Ha a halmaz megengedhető , akkor az ilyen problémát feltétel nélküli optimalizálási feladatnak , ellenkező esetben feltételes optimalizálási feladatnak nevezzük .

Optimalizációs módszerek osztályozása

Az optimalizálási problémák általános jelölése osztályaik széles skáláját határozza meg. A módszer megválasztása (megoldásának hatékonysága) a probléma osztályától függ. A problémák osztályozását a következők határozzák meg: a célfüggvény és a megengedett terület (egyenlőtlenségi és egyenlőtlenségi rendszerrel vagy bonyolultabb algoritmussal). [2]

Az optimalizálási módszereket optimalizálási feladatok szerint osztályozzuk:

• Lokális módszerek: konvergálnak a célfüggvény valamilyen lokális szélsőségéhez. Unimodális célfüggvény esetén ez az extrémum egyedi, és a globális maximum/minimum lesz.
• Globális módszerek: multiextremális célfüggvények kezelése. A globális keresésben a fő feladat a célfüggvény globális viselkedésében mutatkozó trendek azonosítása.

A jelenleg létező keresési módszerek három nagy csoportra oszthatók:

1. meghatározó;
2. véletlenszerű (sztochasztikus);
3. kombinált.

A megvalósítható halmaz dimenziójának kritériuma szerint az optimalizálási módszereket egydimenziós optimalizálási módszerekre és többdimenziós optimalizálási módszerekre osztják .

A célfüggvény és a megengedett halmaz alakja szerint az optimalizálási problémák és megoldásukra szolgáló módszerek a következő osztályokba sorolhatók:

• Azokat az optimalizálási problémákat, ahol a célfüggvény és a kényszerek lineáris függvények, úgynevezett lineáris programozási módszerekkel oldjuk meg .
• Ellenkező esetben egy nemlineáris programozási problémával foglalkozunk, és a megfelelő módszereket alkalmazzuk. Két konkrét feladat különböztethető meg tőlük:
  • ha és konvex függvények, akkor az ilyen problémát konvex programozási feladatnak  nevezzük ;
  • ha , akkor egész (diszkrét) programozási feladattal van dolgunk .

A simaságra és a parciális származékok célfüggvényben való jelenlétére vonatkozó követelmények szerint ezek is feloszthatók:

• közvetlen módszerek, amelyek csak a célfüggvény számítását igénylik a közelítési pontokban;
• elsőrendű módszerek : megkövetelik egy függvény első parciális deriváltjainak kiszámítását;
• másodrendű módszerek: megkövetelik a másodlagos parciális deriváltak, azaz a célfüggvény Hess -féle kiszámítását.

Ezenkívül az optimalizálási módszereket a következő csoportokra osztják:

• analitikai módszerek (például a Lagrange-szorzók módszere és a Karush - Kuhn - Tucker feltételei );
• numerikus módszerek ;
• grafikus módszerek .

Az X halmaz természetétől függően a matematikai programozási problémákat a következőképpen osztályozzuk:

• diszkrét programozási problémák (vagy kombinatorikus optimalizálás ) - ha X véges vagy megszámlálható ;
• egész szám programozási problémák  - ha X az egész számok halmazának részhalmaza ;
• nemlineáris programozási problémák, ha a megszorítások vagy a célfüggvények nemlineáris függvényeket tartalmaznak , és X egy véges dimenziós vektortér részhalmaza .
• Ha minden kényszer és a célfüggvény csak lineáris függvényeket tartalmaz, akkor ez lineáris programozási probléma.

Ezenkívül a matematikai programozás ágai a parametrikus programozás , a dinamikus programozás és a sztochasztikus programozás .

A matematikai programozást az optimalizálási problémák megoldására használják az operációkutatásban .

Az extrémum megtalálásának módját teljes mértékben meghatározza a probléma osztálya. De mielőtt matematikai modellt kapna, a modellezés 4 szakaszát kell végrehajtania:

• Az optimalizáló rendszer határainak meghatározása
  • Elvetjük az optimalizálási objektumnak azokat a külvilággal való kapcsolatait, amelyek nem tudják nagyban befolyásolni az optimalizálás eredményét, pontosabban azokat, amelyek nélkül a megoldás egyszerűsödik.
• A szabályozott változók kiválasztása
  • Egyes változók (nem kezelt változók) értékét „lefagyasztjuk”. A többiek az elfogadható döntések (vezérelt változók) területéről vehetnek fel tetszőleges értéket.
• A vezérelt változókra vonatkozó korlátozások meghatározása
  • … (egyenlőségek és/vagy egyenlőtlenségek)
• A numerikus optimalizálási feltétel kiválasztása (pl. teljesítménymutató )
  • Hozzon létre egy célfüggvényt

Történelem

A lineáris programozási problémák voltak az első olyan részletesen tanulmányozott problémák, amelyek a függvények szélsőértékének megtalálását eredményezték olyan kényszerek jelenlétében , mint az egyenlőtlenségek . 1820- ban Fourier , majd 1947 -ben George Dantzig javasolta a szomszédos csúcsok irányított számbavételének módszerét a célfüggvény növelésének irányába  - a szimplex módszert , amely a lineáris programozási problémák megoldásának fő módszere lett.

A "programozás" kifejezés jelenléte a tudományág nevében azzal magyarázható, hogy a lineáris optimalizálási problémák első tanulmányai és első alkalmazásai a közgazdaságtan területére vonatkoztak, mivel az angol "programozás" szó tervezést , rajzot jelent. terveket vagy programokat. Teljesen természetes, hogy a terminológia azt a szoros kapcsolatot tükrözi, amely a probléma matematikai megfogalmazása és közgazdasági értelmezése (az optimális gazdasági program tanulmányozása) között fennáll. A " lineáris programozás " kifejezést J. Danzig javasolta 1949 -ben a lineáris függvények lineáris megszorítások melletti optimalizálásával kapcsolatos elméleti és algoritmikus problémák tanulmányozására.

Ezért a „matematikai programozás” elnevezés abból adódik, hogy a problémák megoldásának célja az optimális cselekvési program kiválasztása.

Az extrém problémák egy osztályának azonosítását, amelyet egy lineáris függvény határoz meg egy lineáris kényszerekkel meghatározott halmazon, az 1930-as éveknek kell tulajdonítani. Az elsők között, akik általános formában tanulmányozták a lineáris programozási problémákat: John von Neumann  matematikus és fizikus, aki bebizonyította a mátrixjátékok fő tételét és tanulmányozta a nevét viselő gazdasági modellt , valamint L. V. Kantorovich  , egy szovjet akadémikus, Nobel Díjnyertes (1975), aki számos lineáris programozási problémát megfogalmazott, és 1939-ben megoldási módszert javasolt ( a faktorok feloldásának módszere ), amely kissé eltér a szimplex módszertől.

1931- ben Egervari B. magyar matematikus egy matematikai megfogalmazást fontolgatott és megoldott egy lineáris programozási feladatot, amit „választási feladatnak” neveztek, a megoldási módszert „ magyar módszernek ” nevezték.

L. V. Kantorovich és M. K. Gavurin 1949 - ben dolgozta ki a potenciál módszerét , amelyet a közlekedési problémák megoldására használnak . L. V. Kantorovich, V. S. Nyemcsinov , V. V. Novozsilov , A. L. Lurie , A. Brudno , A. G. Aganbegyan , D. B. Yudin , E. G. Golshtein és mások további munkáiban matematikusok és közgazdászok továbbfejlesztették a matematikai és programozási módszereinek és a nemlineáris alkalmazásának elméletét. különböző gazdasági problémák tanulmányozására.

Külföldi tudósok számos munkája foglalkozik a lineáris programozás módszereivel. 1941-ben F. L. Hitchcock állította a közlekedési kihívást . A lineáris programozási problémák megoldásának alapvető módszerét, a szimplex módszert  1949-ben publikálta J. Dantzig. A lineáris és nemlineáris programozás módszereit továbbfejlesztették G. Kuhn , A. Tucker , Gass (Saul I. Gass), Charnes (A. Charnes), Beale (EM Beale) és mások munkáiban.

A lineáris programozás fejlesztésével egyidejűleg nagy figyelmet fordítottak a nemlineáris programozási problémákra , amelyekben vagy a célfüggvény , vagy a megszorítások, vagy mindkettő nemlineáris. 1951- ben jelent meg G. Kuhn és A. Tucker munkája , amelyben megadták a szükséges és elégséges optimalitási feltételeket a nemlineáris programozási problémák megoldásához. Ez a munka képezte a későbbi kutatás alapját ezen a területen.

1955 óta számos másodfokú programozással foglalkozó mű jelent meg (Beal, Barankin és R. Dorfman , Frank (M. Frank) és F. Wolf , G. Markowitz stb. művei). Dennis (JB Dennis), Rosen (JB Rosen) és Zontendijk (G. Zontendijk) munkái gradiens módszereket dolgoztak ki nemlineáris programozási problémák megoldására.

Jelenleg a matematikai programozási módszerek hatékony alkalmazására és számítógépes problémák megoldására algebrai modellező nyelveket fejlesztettek ki , amelyek képviselői az AMPL és a LINGO .

Lásd még

• Többcélú optimalizálás
• Matematikai elemzés
• Skaláris rangsor

Jegyzetek

1. ↑ Forrás: Altai Regionális Egyetemes Tudományos Könyvtár. V. Ya. Shishkova (AKUNB) Archiválva : 2022. március 5. a Wayback Machine -nél . Optimalizálási módszerek: Proc. juttatás. Brazovskaya N.V.; Altáj Állami Műszaki Egyetem I. I. Polzunova, [Távolsági központ. képzés].-Barnaul: Publishing House of AltSTU, 2000, 120 p. - UDC / LBC 22.183.4 B871
2. ↑ Az optimális megtalálása: A számítógép kibővíti a lehetőségeket . - M . : Nauka, 1989. - S.  14 . — ISBN 5-02-006737-7 .

Irodalom

• Abakarov A. Sh., Sushkov Yu. A. Egy globális optimalizálási algoritmus statisztikai vizsgálata . - A FORA eljárásai, 2004.
• Akulich I. L. Matematikai programozás példákban és feladatokban: Proc. diákgazdasági juttatás. szakember. egyetemek. - M . : Felsőiskola, 1986.
• Gill F., Murray W., Wright M. Gyakorlati optimalizálás. Per. angolról. - M .: Mir, 1985.
• Girsanov IV. Előadások az extrém problémák matematikai elméletéről. - M .; Izhevsk : Kutatóközpont "Szabályos és kaotikus dinamika", 2003. - 118 p. — ISBN 5-93972-272-5 .
• Zhiglyavsky A. A., Zhilinkas A. G. Methods for searching for a global extremum. - M .: Nauka, Fizmatlit , 1991.
• Karmanov VG Matematikai programozás. - Phys.-Math. Irodalom, 2004.
• Korn G., Korn T. Matematikai kézikönyv tudósok és mérnökök számára. - M . : Nauka, 1970. - S. 575-576.
• Korshunov Yu. M., Korshunov Yu. M. A kibernetika matematikai alapjai. — M .: Energoatomizdat , 1972.
• Lotov A. V. , Pospelova I. I. Előadásjegyzetek a többszempontú optimalizálás elméletéről és módszereiről. Archiválva : 2022. január 21. a Wayback Machinetelepülés M., 2005. 127 p.
• Maksimov Yu. A., Filippovskaya EA Algoritmusok nemlineáris programozási problémák megoldására. — M. : MEPhI, 1982.
• Maksimov Yu. A. Lineáris és diszkrét programozási algoritmusok. — M. : MEPhI, 1980.
• Plotnikov A.D. Matematikai programozás = expressz kurzus. - 2006. - S. 171. - ISBN 985-475-186-4 .
• Rastrigin L. A. A keresés statisztikai módszerei. - M. , 1968.
• Sergeev Ya. D., Kvasov D. E. A globális optimalizálás átlós módszerei Archivált 2017. október 26-án a Wayback Machine -nél . — M.: FIZMATLIT, 2008. 341s.
• Hemdy A. Taha. Bevezetés az operációkutatásba = Operations Research: An Introduction. - 8. kiadás - M .: Williams , 2007. - S. 912. - ISBN 0-13-032374-8 .
• Kini RL, Raifa H. Döntéshozatal több kritérium alapján: preferenciák és helyettesítések. - M . : Rádió és kommunikáció, 1981. - 560 p.
• Zukhovitsky S. I. , Avdeeva L. I. Lineáris és konvex programozás. - 2. kiadás, átdolgozva. és további .. - M . : "Nauka" Kiadó, 1967.
• Minaev Yu. N. Gazdasági és matematikai optimalizálási modellek stabilitása. - M . : Statisztika, 1980.
• Moiseev NN Numerikus módszerek az optimális rendszerek elméletében . - M. : Nauka, 1971. - 424 p.
• Moiseev NN Az optimális rendszerek elméletének elemei . — M .: Nauka, 1975. — 528 p.
• Moiseev NN , Ivanilov Yu. P. , Stolyarova EM Optimalizálási módszerek . - M. : Nauka, 1978. - 352 p.

• Degtyarev Yu. I. Optimalizálási módszerek. - M . : Szovjet rádió, 1980. - 272 p.
• Rekleitis G., Reyvindran A., Ragsdel K. Optimization in engineering. - M . : Mir, 1986. - 400 p.
• Romanovsky IV Algoritmusok extrém problémák megoldására. — M .: Nauka, 1977. — 352 p. - 16.000 példány.
• Umnov A.E. , Umnov E.A. Paraméteres problémák a matematikai programozásban archiválva : 2021. július 9. a Wayback Machine -nél (pdf)
• Khokhlyuk VI Párhuzamos egész optimalizálási algoritmusok. Archivált : 2021. január 18. a Wayback Machine Course előadásainál. Novoszibirszk , 2007.
• Khokhlyuk V. I. Diszkrét optimalizálási módszerek. Archiválva : 2021. január 18. a Wayback Machine -nél NSU, ​​2013. 154. o.

Linkek

• Polyak B.P. A matematikai programozás története a Szovjetunióban: a jelenség elemzése  // A 14. Bajkál iskolai szeminárium „Optimalizálási módszerek és alkalmazásaik” anyaga. - 2008. - T. 1 . - S. 2-20 .

Szótárak és enciklopédiák	Nagy dán Nagy orosz Britannica (online)
Bibliográfiai katalógusokban	BNF : 11932649z GND : 4043664-0 J9U : 987007538691105171 LCCN : sh85107312 NKC : ph122672