Gradiens módszerek - studopediya
Általában, amelyet grádiens módszerek megérteni eljárások, amelyekben a mozgásának iránya a pont optimális funkció egybeesik az irányt a gradiens a függvény. Gradiens módszerek közelítő módszerek nemlineáris programozási feladat. Általánosságban elmondható, hogy optimális megoldást biztosítanak keresztül végtelen folyamat egymást követő közelítések. Ugyanakkor bizonyos esetekben a folyamat végén, miután egy véges számú iteráció.
Gradiens módszer alkalmazható bármely nemlineáris programozási feladat, ami csak helyi, hanem globális szélsőérték. Ezért azok hatékonyabb megoldásában konvex programozási feladat, ahol minden helyi szélsőérték egyszerre globális.
Az általános megfogalmazása a probléma megfelel a (5.1) és (5.2). Azonban, Az általánosság elvesztése nélkül, ez átalakítható formában
Matematikai stratégia gradiens módszer a következő. Kiválasztása egy tetszőleges kivitelezhető pontján. Áthelyezéséhez iterációk eredő pontra egy meghatározott irányban. elegendően kis fény egyértelműen régióváltások. Ez a következő pont az iteratív folyamat határozza meg a képlet:
A különbség gradiens módszerek áll egy eljárás annak meghatározására, az irányt és a paraméter.
1. Ha - belső pontját a domain a megvalósítható megoldásokat, majd
a gradiens a függvény a ponton. Stratégia, által kifejezett kapcsolatban (5,57) határozza meg, mozgását változtatható pitch, mint a pitch érték függ a gradiens értéke. Mivel a gradiens csökken közel optimális értéket, akkor bizonyos területeken lesz kis lépések, amelyek kiterjesztik a keresési idő. Ebből hátrány kiküszöbölhető gradiens stratégiát egy pitch érték állandó. Ebben az esetben, a gradiens vektor helyébe a gradiens vektor irányban:
2. nem tartozik a megvalósítható régióban. Ez lehet a helyzet, ha a pont abba az irányba halad, a legnagyobb növekedést a függvény i -k megsértették korlát (5,54). A büntetés a megsértése i-edik faktor határértékek Ri és vspomogatelnuyu célfüggvény.
Ha a cél, hogy jobban megismerje a jövedelem a vállalkozás, ez nem más, mint a jövedelem a vállalati mínusz szankciókat.
A legegyszerűbb esetben Rí jelentése a következő:
Száma R nagynak kell lennie ahhoz, hogy egy pontot, hogy beköltözik a megengedett területen. A mozgási irányának egy pont ebben az esetben adja a vektor
A hátránya ennek a stratégiának az, hogy a pontossága a számítás függ a választott R. Ha nem a választás a száma R iteratív folyamat fogja jellemezni kerüli az a pont a határ közelében.
Ezt a hátrányt el lehet kerülni, ha azt feltételezzük, hogy a bírság legyen minél kisebb, kevésbé zavar léphet fel, azaz, célszerű azt feltételezni, hogy
1) beállítása az állandó minden ismétléseket. Minél kisebb a szám. A pontosabb számítást. Ennek megfelelően a keresési idő növekedésével, az optimális;
2) kiválasztott paraméter minden egyes lépésében a feltételek min # 955; ' # 955; „> ahol # 955; „- az érték, amelynél a fénysugár + # 955; (K) s (k) keresztezi a TCC; # 955; „- egy érvényes érték # 955;. ahol f (+ # 955; (k) S (k)) érik el maximális a gerenda. Ez a stratégia lehetővé teszi, hogy a DHS és optimalizálja az iterációk számát. Azonban, amikor a nemlineáris és nemlineáris korlátok célfüggvény számítási # 955; ' # 955; „is meglehetősen időigényes.
Annak illusztrálására, hogy gradiens módszer döntünk a következő stratégiát: # 955; - A számos rendszeres; értéke a bírság arányos a korlátozás megsértését; iránya egybeesik a pont irányába a gradiens. Ez az úgynevezett gradiens módszer Arrow-Hurwitz. Ha a jel korlátok (5,55) nem, a koordinátáit az új pont szerint kell kiszámítani, (5,56) (5,60) a következő képlet:
Figyelembe véve a nem-negatív körülmények között (5,55), a kifejezés (5,62) a következő lenne:
A kifejezések (5,62) és a (5,63) büntetési függvény szerint számítjuk képlet (5,61).
5.3 példa van szükség, hogy maximalizálja a funkciót
enged # 955; = 0,1; R1 (0) = 2; x1 (0) = 3; x2 (0) = 1,5, vagyis, úgy döntünk, a kiindulási pont, nyilvánvalóan nem tartozik a megvalósítható régióban.
Egyenletek (5,62) a következők:
Egyenletek (5,61) a következők:
Második iteráció: A lényeg az, már bent a régióváltások, azonban egy tényező. bár kisebb. hanem a különböző, a 0 és a határ továbbra is „push” mozgó pontra belül megengedhető terület (ez a pont még mindig a „veszélyes távolság” a határ):
Hasonlóképpen, ez a folyamat megy tovább és tovább. Számának növelésével iterációk a pont, amikor a feltétele domborulata az objektív függvény elkötelezett a feladat.
Az ajánlott olvasás
1. AV Kuznyecov, II hideg. Matematikai programozás. - Minszk: "High School". 984-221.
4. Zaichenko YP Operációkutatás: Proc. juttatás egyetemi hallgatók számára. - 2nd ed. Felülvizsgált. és ext. - Kiev: Vishcha iskola. A fő kiadó, 1979. 392 p.
5. IA Akulich. Matematikai programozási példák és problémák. - M., "High School", 1986.- 319 p.
9. S. Gass. Lineáris programozás. - M., "Nauka", 1961.-303 a.
10. Sakovich VA Operations Research (determinisztikus módszerek és modellek): A használati útmutató. - Mn. Ön. wk. 1984-256s.
11. Taha H. Bevezetés Operációkutatás: két könyv. Kn.1,2 Pere. az angol. - Mir 1985.