Az algoritmus a módszer Lagrange szorzók
Home | Rólunk | visszacsatolás
Lagrange multiplikátor módszerrel.
Lagrange multiplikátor módszer egyike a technikák, amelyek lehetővé teszik számunkra, hogy megoldja nemlineáris programozási feladat.
Nemlineáris programozási egyik ága a matematikai programozás, tanulási módszerek megoldására optimalizálási problémák nemlineáris célfüggvény és megvalósítható régió által meghatározott nemlineáris korlátok. A közgazdaságtanban ez megfelel annak a ténynek, hogy az eredmények (hatékonyság) növelheti vagy csökkentheti aránytalan változás erőforrás-felhasználás mérlegek (vagy ezzel egyenértékű termelési skála) feszültség. köszönhető, hogy a szétválás a termelési költség vállalatok a változók és feltételes állandó; telítődése miatt áruk iránti kereslet, amikor minden következő egység eladni nehezebb, mint az előző, és így tovább. d.
A bonyolult probléma a nemlineáris programozási feladat találni az optimális egyedi célfüggvény
ha a körülmények
ahol x vektor ismeretlen változók;
g (x) - a funkció korlátozása (folyamatosan differenciálható);
b - a vektor konstansok korlátai.
Megoldás a nemlineáris programozási feladat (globális maximum vagy minimum) is tartozhat akár a határ vagy a belső a megvalósítható készlet.
Ezzel szemben a lineáris programozási feladat, a probléma a nemlineáris programozás optimális nem feltétlenül fekszik a terület határát által meghatározott korlátozásokat. Más szóval, a kihívás az, hogy válasszon, mint a nem-negatív változók korlátozás alá formájában egyenlőtlenségrendszer, amellyel a maximális (vagy minimális) a funkciót. Ebben az esetben a nyomtatványt nem határoz meg célfüggvény vagy egyenlőtlenség. Lehet különböző esetekben: az objektív függvény nemlineáris és lineáris korlátokat; az objektív függvény lineáris és korlátozott (legalább egy közülük) nem lineáris; és az objektív függvény és a nemlineáris korlátok.
Nemlineáris programozási feladat található a természettudományok, műszaki, közgazdaságtan, matematika, a területén az üzleti kapcsolatok a tudomány a kormány.
Nemlineáris programozás, például együtt jár a fő gazdasági feladat. Tehát a probléma az elosztása szűkös erőforrások vagy a hatékonyság maximalizálása, vagy ha a fogyasztó tanulmány, a fogyasztás a jelenléte a megszorítások, amelyek kifejezik a feltételeket a források hiánya. Az ilyen általános kijelentés a matematikai megfogalmazása a probléma nem lehet, de az adott alkalmazás mennyiségi véve az összes funkció közvetlenül meghatározható. Például egy gyártó üzem gyárt műanyag termékeket. A termelés hatékonysága becsült nyereség és cash korlátok értelmezni munkaerő, termelési létesítmények, berendezések teljesítményét, stb
A módszer a „költség - hatékonyság” beleillik a rendszer nemlineáris programozás. Ezt a módszert dolgoztak ki, amelyet a döntéshozatalban a kormány. A teljes funkció a hatékonyság vagyon. Ez két problémát vet fel a nemlineáris programozás: az első -, hogy maximalizálja a hatását korlátozott költségek, a második - a költségek minimalizálása, feltéve, hogy a hatás egy bizonyos minimális szintet. Általában ezt a feladatot jól modellezhető nemlineáris programozás.
Nemlineáris probléma összetett, gyakran egyszerűsített az a tény, hogy ők vezetnek lineáris. Erre a célra, hagyományosan feltételezzük, hogy egy adott részét a célfüggvény nő vagy csökken arányosan a független változók. Ezt a megközelítést nevezik a szakaszonként lineáris közelítés, vonatkozik, azonban csak bizonyos típusú nemlineáris problémák.
Nemlineáris problémák bizonyos körülmények között oldják meg a Lagrange-függvény: találni neki egy nyereg pont, és így megtalálni a megoldást. Közül számítási algoritmusok N. N. Egy nagy helyet foglalja el gradiens-módszereket. Univerzális ugyanazt a módszert nemlineáris problémák vannak, és úgy tűnik, nem lehet, mert nagyon változatos. Különösen nehéz megoldani multiextremal problémákat.
Az egyik módszer, amely lehetővé teszi, hogy csökkentsék a probléma nemlineáris programozási megoldásához az egyenletrendszert a módszer Lagrange szorzók.
Segítségével a Lagrange multiplikátor módszer, a szükséges feltételek jönnek létre az érdemi azonosítását lehetővé tevő optimális pont optimalizálási problémák megszorítások formájában ra-egyenletek. Tehát a probléma a megszorítások az ekvivalens-vegyértéke problémáját korlátozatlan optimalizálás, melyben néhány ismeretlen paramétereket, úgynevezett La Grange szorzók.
Lagrange szorzók módszer abban áll, a csökkentés a feltételes szélsőérték problémák feltétel nélküli szélsőérték kisegítő funkciót - T N .. Lagrange-függvény.
szorzók # 955; 1. # 955; 2. # 955; m nevezett. Lagrange szorzók.
Ha az érték a x1. x2. xn. # 955; 1. # 955; 2. # 955; m oldatai meghatározó egyenletek stacionárius pont a Lagrange-függvény, nevezetesen, a differenciálható függvények oldatai az egyenletrendszert
majd ha megfelelő X1 általános feltételezések. x2. xn szállít extrém f értékét.
Tekintsük a probléma minimalizálása n-változós függvény korlátozható formájában egyenlőség:
A módszer szerint a Lagrange szorzók, a feladat átalakul a következő korlátozatlan optimalizálási probléma:
minimalizálva L (x, # 955;) = f (x) - # 955; * H (x) (3)
ahol az L (x; # 955;) nevezzük a Lagrange,
# 955; - ismeretlen konstans, amely az úgynevezett Lagrange szorzó. a jel # 955; nincs követelményeket támasztanak.
Tegyük fel, hogy egy adott érték # 955 = # 955; 0 abszolút minimális függvény L (x, # 955;) függvényt x érünk el az x = x0 és x0 kielégíti az egyenletet H1 (X0) = 0. Ezután, amint az jól látható, x0 minimalizálja, (1) a (2), mivel minden x értéke kielégíti (2), H1 (x) = 0, és L (x, # 955;) = min f (x).
Persze, ki kell választani egy értéket # 955 = # 955; 0 úgy, hogy az abszolút minimális pontjának koordinátája x0 kielégítik (2) egyenlet. Ez úgy valósítható meg, figyelembe véve # 955; mint egy változó, meg az abszolút minimum, a funkció (3) függvényében # 955;, majd válassza # 955;, amelyben a egyenlőséget (2). Mi illusztrálására példaként.
Minimize f (x) = x1 2 + x2 2 = 0
Megfelelő korlátozatlan optimalizálás van írva a következő:
Határozat. Egyenlővé a két komponenst L gradiens nullára, megkapjuk
Annak érdekében, hogy ellenőrizze, hogy stacionárius pont x ° megfelel egy minimális, kiszámítja Hesse mátrix elemeit a függvény L (x, u), tekinthető az X függvényében,
ami kiderül, hogy pozitív definit.
Ez azt jelenti, hogy az L (x, u) - konvex függvény x. Következésképpen, a koordináták x1 = 0 # 955;, x2 = 0 # 955; / 2 határozzuk globális minimum pontot. Az optimális érték # 955; Azt találtuk, szubsztituálásával értékei x1 és x2 0 0 uravnenie2x1 + x2 = 2, a 2 # 955 + # 955; / 2 = 2, vagy # 955; 0 = 4/5. Így, a relatív minimális érhető el, ha X1 = 0 4/5 0 és x2 = 2/5 és az egyenlő min f (x) = 4/5.
A probléma megoldásának a példában néztük L (x; # 955;) függvényében két változó x1 és x2, és ezen kívül, azt feltételezzük, hogy a paraméter értékét # 955; úgy választjuk meg, hogy megfelel a restrikciós-chenie. Ha az oldat a rendszer
explicit függvények # 955; nem lehet beszerezni, akkor az értékek az x és # 955; Ezek megtalálhatók megoldása az alábbi álló rendszer n + 1 egyenletek n + 1 ismeretlenek:
Annak érdekében, hogy megtalálja az összes lehetséges megoldást a rendszer, akkor a numerikus keresési módszerek (mint például a Newton-módszer). Az egyes oldatok () kiszámításához szükséges az elemek a hesseni mátrix funkciók L, minősül az X függvényében, és megtudja, hogy ez egy pozitív definit mátrix (helyi minimum) vagy negatív határozott (helyi maximum).
Lagrange szorzók módszere lehet terjeszteni az esetre, ha a feladat kevés korlátozások formájában egyenletek. Vegyünk egy általános probléma, amely előírja,
alatti megszorítások hk = 0, k = 1, 2 K.
Lagrange-függvény a következő alakú:
itt # 955; 1. # 955; 2. # 955; k olyan tényező Lagrange, azaz ismeretlen paramétereket, amelyek értéke kell meghatározni. Egyenlővé parciális deriváltak x L nullára, kapjuk az alábbi, n egyenletek n ismeretlennel:
Ha megoldást találni a fenti formában vektor függvények # 955; nehéz, lehetőség van bővíteni a rendszert a benne foglalt korlátozások formájában egyenlőségek
Megoldás kiterjesztett rendszer, amely n + k egyenletek N + K ismeretlen funkció egy fix pont L. hitelesítési eljárás valósul akkor a minimális vagy a maximális, amelynek alapja a kiszámítására az elemek a hesseni funkció L, minősül az X függvényében, csak ahogy ez történt a probléma esetén egy korlátozást. Bizonyos problémák, a kiterjesztett rendszer n + k egyenletek n + K ismeretlenek nem lehet megoldásokat, és Lagrange multiplikátor módszer nem alkalmazható. Meg kell jegyezni azonban, hogy az ilyen problémák a gyakorlatban ritkák.
Úgy véljük, a speciális esete az általános nemlineáris programozási feladat, feltételezve, hogy a rendszer csak korlátok az egyenletnek nincs nemnegativitását feltételek és a változók, valamint - a függvény folytonos együtt parciális deriváltak
Ezt a problémát nevezik a problémát egy feltételes szélsőérték vagy klasszikus optimalizálási probléma.
Megoldást találni erre a problémára, újonnan bevezetett változó nevű Lagrange szorzók. töltsük fel a Lagrange-
a részleges származékok a rendszer, és figyelembe véve az n + m egyenletek
n + m ismeretlenek minden egyenletek megoldása (7) meghatároz egy pont, amely kerülhet sor szélsőérték a függvény. Következésképpen megoldani egy egyenletrendszert (7), így az összes pontot, amelynél a függvény (6) extrém értékeket.
Az algoritmus a módszer Lagrange szorzók
1.Sostavlyaem Lagrange-függvény.
2.Nahodim részleges származékok a Lagrange-függvény vonatkozásában változók xJ, # 955; i és egyenlővé őket nullára.
3.Reshaem egyenletrendszert (7), megtaláljuk a pontot, ahol a célfüggvény a probléma lehet szélsőséges.
4. között a pontokat, hogy gyanús szélsőérték megtalálni azokat, ahol a szélsőérték eléréséig, kiszámolja a függvény értékei (6) ezeken a pontokon.
Háttér: A terv szerint a produkciós cég kell termelni 180 termék. Ezek a termékek lehet két technológiai szempontból. A gyártási eljárás 1 x1 gyártási költségek 4x1 + x1 2 RUB. és a gyártmányokhoz 2 x2 módon teszik 8x2 + x2 2 rubelt. Határozza meg, hogy hány példány minden módszert kell tenni, hogy a termelési költség minimális volt.
A célfüggvény erre a problémára adott
®min körülmények X1 + X2 = 180, x2 ≥0.
1.Sostavlyaem Lagrange
.
2. Számítsuk ki az parciális deriváltak x1. x2, # 955; és azokat azonosítani nullával:
3. megoldására kapott egyenletrendszert kapjuk, hogy x1 = 91, x2 = 89
4.Sdelav szubsztitúciót a célfüggvény x2 = 180-x1. kapjunk függvényében egy változó, nevezetesen f1 = 4x1 + x1 2 + 8 (180-x1) + (180-x1) 2
Számítsuk vagy 4x1 -364 = 0,
A: A termékek száma által gyártott az első módszer egyenlő x1 = 91, x2 = a második módszer 89 ahol a célfüggvény érték egyenlő 17278 dörzsölje.