Konvexné programovanie

Ak v úlohe matematického programovania potrebujete nájsť extrém funkcie, napríklad:

na množine realizovateľných riešení daných obmedzeniami

1) účelová funkcia je diferencovateľná a konkávna, t.j. je splnená podmienka:

Pre akékoľvek

2) a ľavé strany všetkých obmedzení - diferencovateľné a konvexné funkcie, t.j. pre nich sú splnené tieto podmienky:

Pre akékoľvek

Potom sa problém (4.7) - (4.8) nazýva problém konvexné programovanie.

Akákoľvek lineárna funkcia súčasne spĺňa podmienky konvexnosti aj konkávnosti; tie. možno ju považovať za konvexnú aj konkávnu. To nám umožňuje považovať lineárne problémy za špeciálny prípad problémov konvexného programovania.

Ak pre problémy matematického programovania vo všeobecnom prípade stále neexistuje koherentná teória existencie a stability riešenia, potom pre problémy konvexného programovania takáto teória existuje.

Uveďme tri definície:

1). Lagrangeova funkcia konvexného programovacieho problému (4.7) - (4.8) je funkcia:

,

, (4.9)

2). Hovorí sa, že konvexný problém programovania (4.7) - (4.8) vyhovuje stav pravidelnosti ak existuje aspoň jeden vnútorný bod množiny realizovateľných riešení definovaných striktnými nerovnosťami získanými z (4.8) (t.j. ).

3). Bod sa volá sedlo bod funkcie ak pre všetkých hotový:

Ak je cieľová funkcia (odstrániť)

V teórii nelineárneho programovania má ústredné miesto Kuhn-Tuckerova veta, ktorá zovšeobecňuje klasickú metódu Lagrangeových multiplikátorov na prípad, keď obmedzenia nelineárneho problému spolu s obmedzeniami vo forme rovnosti obsahujú aj obmedzenia. vo forme nerovností.

Kuhn-Tuckerova veta. Ak konvexný problém programovania (4.7) - (4.8) spĺňa podmienku pravidelnosti, potom je bod optimálnym riešením tohto problému vtedy a len vtedy, ak existuje bod s nezápornými súradnicami, ktorý je sedlovým bodom Lagrangeovej funkcie tohto problému. .

Podmienky Karush - Kuna - Tucker v diferenciálnej forme:

Ak je Lagrangeova funkcia konvexná vzhľadom na, konkávna vzhľadom na všetky a plynule diferencovateľná vzhľadom na všetky a potom na to, aby bol pár sedlovým bodom Lagrangeovej funkcie, je potrebné a postačujúce, aby boli splnené nasledujúce podmienky:

,

,

,

Príklad Kuhn-Tuckerova veta zdôvodňuje redukciu problému konvexného programovania na problém nájdenia sedlového bodu Lagrangeovej funkcie. Aby takáto redukcia mala praktický význam, je potrebné, aby výsledný problém bol o niečo jednoduchší ako ten pôvodný. Nestáva sa to vždy, preto bolo vyvinutých množstvo priamych metód na nájdenie riešenia nelineárneho problému (4.5), (4.6). Poďme sa na niektoré z nich pozrieť.

Zváženie tejto triedy problémov zvyčajne začína prezentáciou metóda neurčitých Lagrangeových multiplikátorov. Na tento účel vložíme / (x, ..., NS") a g (x b ..., NS")- spojité funkcie spolu s ich parciálnymi deriváciami, zatiaľ odstránime podmienky nezápornosti premenných a pre podmienený extrém sformulujeme nasledujúcu úlohu:

Aby sme našli jeho riešenie, predstavíme Lagrangeove multiplikátory y b / = 1, T a skladať tzv Lagrangeova funkcia:

nájdite a vyrovnajte jeho parciálne derivácie vzhľadom na všetky premenné

po prijatí systému n + t rovnice pre neznáme x b x n,

Uy -, U -

Ak je funkcia f (x h ..., NS") v bode má extrém, potom existuje vektor Y (0> = (y, 0, ..., y °), že bod (Ag (0), F (0)) je riešením sústavy (2.23). Riešením sústavy (2.23) teda dostaneme body, v ktorých funkcia (2.20) môže mať extrém. Ďalej sa nájdené body skúmajú rovnakým spôsobom ako pri riešení úlohy pre bezpodmienečný extrém.

Metóda Lagrangeovho multiplikátora teda zahŕňa nasledujúce kroky.

• 1. Vytvorte Lagrangeovu funkciu.
• 2. Nájdite parciálne derivácie vzhľadom na Xj a y, z Lagrangeovej funkcie a prirovnať ich k nule.
• 3. Systém riešenia (2.23), nájdite body, v ktorých môže mať účelová funkcia extrém.
• 4. Medzi bodmi-kandidátmi na extrém nájdite tie, pri ktorých je extrém dosiahnutý, a vypočítajte hodnoty funkcie f (x, ..., NS") v týchto bodoch.

Opísaná metóda je použiteľná na problémy konvexného programovania, t.j. k tým, v ktorých je účelová funkcia konvexná (alebo konkávna) a oblasť realizovateľných riešení určená obmedzeniami je tiež konvexná.

Definícia 1. Funkcia f (x,..., x n), daný na konvexnej súprave X, sa nazýva konvexné ak pre niektoré body X, X 2 od Hee pre ľubovoľné číslo X, 0 X 1 nerovnosť

Definícia 2. Funkcia/(*, NS„) Definované na konvexnej množine X, sa nazýva konkávne, ak pre akékoľvek body NS NS, X 2 od Hee pre ľubovoľné číslo X, 0 X

Definícia 3. Množina realizovateľných riešení konvexného programovacieho problému spĺňa podmienku pravidelnosti, ak existuje aspoň jeden bod Xj, patriace do regiónu realizovateľných riešení, pre ktoré g ^ XJ) =b h i = 1, T.

Veta 1. Akýkoľvek lokálny extrém konvexného programovacieho problému je globálny.

Definícia 4. Lagrangeova funkcia konvexného programovacieho problému je funkcia

kde y je Lagrangeov multiplikátor.

Definícia 5. Bod (X (0), T (0)) = (x, °, ..., NS (',y, 0,..., y" ) volal sedlový bod funkcie Lagrange, ak

Uvádzame dve krátke vety pomocného charakteru.

Veta 2. Optimálny plán X (0)úlohy NP- toto je

kde DA) je nelineárna diferencovateľná funkcia spĺňajúca podmienky

kde je gradient funkcie /

v bode A "(0).

Dôkaz.

Rozšírte cieľovú funkciu v Taylorovom rade v okolí bodu NS (())

kde OH- vektor malých prírastkov X (0);

I - označenie normy (dĺžky) vektora.

Z výrazu (2.26) vyplýva, že ak je nejaká hodnota súradnice vektora x | 0)> 0, potom derivácia

, keďže inak súradnica x do môcť,

s pevnými hodnotami zostávajúcich premenných pokračujte v minimalizácii cieľovej funkcie, znižovaní hodnoty x [0), ak je derivácia väčšia ako nula, alebo zvyšovaní xf ak je derivát menší

škrabanec. Ak x | 0) = 0, potom by tam malo byť pokiaľ

inak by bolo možné znížiť hodnotu f (X m), zvýšenie 4 0) o hodnotu Dx * bez zmeny hodnôt ostatných premenných. Preto pre akékoľvek Komu platí rovnosť:

Veta je dokázaná.

Definujme teraz potrebné a postačujúce podmienky pre existenciu sedlového bodu Lagrangeovej funkcie.

Veta 3. Aby bod (A 10 *, I 0)) s nezápornými súradnicami bol sedlovým bodom diferencovateľnej funkcie L (X, Y), musia byť splnené tieto podmienky:

Dôkaz.

1) Potreba. Nech (X (0), Y "(0)) je sedlový bod, t.j.:

Vzorec (2.29) je ekvivalentný výrazu

Na základe (2.29) a (2.30) sú splnené podmienky (2.27) a (2.28). Nevyhnutnosť je teda preukázaná.

• 2) Primeranosť. Predpokladáme, že podmienky (2.27) a (2.28) sú splnené. Rozbaľte funkciu L (X, Y) v Taylorovom rade v blízkosti bodu

Z expanzie (2.31) a zohľadnenia podmienok (2.27) a (2.28) vyplýva, že

Posledné dva výrazy sú ekvivalentné vzorcu (2.29). Veta je dokázaná.

Po vyššie uvedených vetách sformulujeme dnes už prakticky zrejmú Kuhnovu - Tuckerovu vetu.

Veta 4 (Kuhn - Tucker). Pre konvexný problém programovania (2.20) - (2.21), ktorého množina realizovateľných riešení má vlastnosť pravidelnosti, bod X (0) =(xj 0 *, ..., x ’0)), x, - 0>> 0, / = 1, NS je optimálny návrh vtedy a len vtedy, ak existuje vektor T = (y 1 (0), ..., yi 0)), Y / 0)> 0, / = 1, T,že bod (T (0), H 0>) je sedlový bod Lagrangeovej funkcie.

Ak v úlohe konvexného programovania (2.20) - (2.21) sú účelová funkcia a obmedzenia spojito diferencovateľné, potom možno Kuhnovu - Tuckerovu vetu doplniť o analytické výrazy definujúce nevyhnutné a postačujúce podmienky pre bod (X (0), Y i (l), ) bol sedlový bod Lagrangeovej funkcie, t.j. bolo riešením konvexného programovacieho problému. Ide o výrazy (2.27) a (2.28). Sú spokojní s problémom kvadratického programovania. Pre jeho konečnú formuláciu uvádzame niekoľko definícií a jednu vetu.

Definícia 6. Kvadratický tvar vzhľadom na premenné X [, ..., NS"číselná funkcia týchto premenných sa nazýva, ktorá má tvar:

Definícia 7. Kvadratická forma F sa nazýva kladný / záporný určitý ak F (X)> 0/ F (X) 0 pre všetky hodnoty premenných, ktoré tvoria vektor X.

Definícia 8. Kvadratická forma F sa nazýva kladný / záporný semidefinitný ak F (X ")>О / YES ") X a navyše existuje taká množina premenných - zložky vektora X ",čo F (X") = 0.

Veta 5. Kvadratická forma je konvexná / konkávna funkcia, ak je kladná / záporná semidefinitná.

Definícia 9. Úloha minimalizovať / maximalizovať hodnotu funkcie

s obmedzeniami

kde je kladná / záporná semidefinitívna kvadratická forma, tzv problém kvadratického programovania(RFQ).

Pre túto úlohu má Lagrangeova funkcia tvar:

Ak má Lagrangeova funkcia sedlový bod, sú v nej splnené podmienky (2.27), (2.28). Teraz, keď uvádzame ďalšie premenné, ktoré menia nerovnosti na rovnosti (táto technika sa používa aj pri riešení úloh LP), zapíšeme tieto podmienky vo forme:

Na nájdenie riešenia ZKP je potrebné určiť nezáporné riešenie sústavy lineárnych algebraických rovníc (2.32). Takéto riešenie sa dá nájsť metóda na umelom základe, aplikovaný na nájdenie minimálnej hodnoty umelej objektívnej funkcie F = ^ Pj, kde p sú umelé premenné. Metóda od-

Je známe, že v konečnom počte krokov nájde optimálny plán alebo zistí neriešiteľnosť problému.

Proces hľadania riešenia RFQ teda zahŕňa nasledujúce kroky.

• 1. Vytvorte Lagrangeovu funkciu.
• 2. Nevyhnutné a postačujúce podmienky pre existenciu sedlového bodu Lagrangeovej funkcie sú zapísané vo forme výrazov (2.27), (2.28).
• 3. Pomocou metódy umelej bázy zistite absenciu sedlového bodu pre Lagrangeovu funkciu alebo nájdite jej súradnice.
• 4. Napíšte optimálne riešenie pôvodného problému a nájdite hodnotu účelovej funkcie.

Zvážte elementárne číselný príklad(№ 1) z knihy I. L. Akulicha „Matematické programovanie v príkladoch a problémoch“. Podľa plánu výroby musí podnik vyrobiť 180 produktov. Môžu byť vyrobené pomocou dvoch technológií. Vo výrobe NS výrobkov 1. spôsobom, náklady boli xf+ 4x, rub., A pri výrobe x 2 produkty 2. spôsobom sú si rovné x + 8 x 2 ruble. Určte, koľko položiek by sa mala vyrobiť každá metóda, aby sa minimalizovali náklady na objednávku.

Riešenie. Nasledujúce funkcie by sa mali minimalizovať:

za podmienok:

Funkcia Lagrange v tomto prípade bude vyzerať takto:

Vypočítajme parciálne derivácie tejto funkcie vzhľadom na X, x 2, y a prirovnať ich k nule:

Prenášanie v prvej a druhej rovnici pri na pravú stranu a prirovnanie ľavých strán dostaneme po zrejmých skratkách:

Riešením tejto rovnice spolu s treťou rovnicou systému zistíme, že Toto je bod - uchádzač o extrém.

Pomocou druhej parciálnej derivácie je ľahké ukázať, že nájdený bod je podmienené minimum funkcie /

Problémy podobné tým, o ktorých sme hovorili vyššie, sú v hospodárskej praxi prezentované mnohými spôsobmi. Je pravda, že skutočné problémy spravidla obsahujú veľké množstvo premenných a obmedzení, čo znemožňuje ich riešenie bez použitia počítača. Efektívnosť používania štandardizovaného softvéru je však určená znalosťami výskumníka o povahe transformácií vykonávaných počítačom. To mu pomáha správne sa orientovať v súbore metód, výpočtových postupov a softvérových systémov navrhnutých na riešenie optimalizačných problémov.

Ak chcete tému upevniť, zvážte ešte jednu číselný príklad(č. 2). Nájdite maximálnu hodnotu funkcie

za podmienok:

Riešenie. Funkcia / je konkávna, pretože je súčtom lineárnej funkcie f = 2x 2 + 4x b ktoré možno považovať za konkávne a kvadratické / 2 = -x -2x1, ktorý je negatívne definovaný. Obmedzenia obsahujú iba lineárne obmedzenia. V dôsledku toho je možné použiť Kuhnovu - Tuckerovu vetu a schému riešenia CSP.

1. Zostavme Lagrangeovu funkciu:

2. Zapíšme si potrebné a postačujúce podmienky pre existenciu sedlového bodu funkcie L.

3. Zaviesť do sústavy lineárnych nerovností ďalšie nezáporné premenné v b V2, w, w 2, premeniť nerovnosti na rovnosť. Dostaneme sústavu rovníc:

V tomto prípade sú samozrejme splnené nasledujúce podmienky:

Na určenie súradníc sedlového bodu Lagrangeovej funkcie je potrebné nájsť základné riešenie sústavy rovníc (2.33). Na tento účel použijeme metódu umelého základu. Minimalizácia umelej objektívnej funkcie

kde Zi, Zi- umelé premenné za podmienok:

Zjavné základné možné riešenie tu vyzerá takto:

Objektívna funkcia F vyjadriť prostredníctvom nezákladných premenných:

Na záver úvahy si všimneme, že zaniká pre Xj (0) = 1, = 1 a ostatné premenné s nulovými hodnotami. T (0) = (1, 1) je teda optimálny plán pôvodného problému,

Funkcia sa volá konvexné

Funkcia sa volá konkávne na konvexnej množine ak pre nejaké body a pre ľubovoľné číslo platí nasledujúca nerovnosť:

Niekedy sa konvexná funkcia nazýva konvexná smerom nadol, na rozdiel od konkávnej funkcie, ktorá sa niekedy nazýva konvexná smerom nahor. Význam týchto názvov je zrejmý z geometrického obrazu typickej konvexnej (obr. 3.3) a konkávnej (obr. 3.4) funkcie.

Ryža. 3.3. Konvexná funkcia

Ryža. 3.4. Konkávna funkcia

Zdôrazňujeme, že definície konvexných a konkávnych funkcií majú zmysel len pre konvexnú množinu X, keďže len v tomto prípade ide o bod nevyhnutne patrí NS.

Konvexný problém programovania je špeciálny prípad všeobecného problému matematického programovania (3.7), (3.8), keď účelová funkcia a obmedzujúce funkcie sú konkávne na konvexnej množine R.

Keďže problém maximalizácie funkcie je ekvivalentný problému minimalizácie tejto funkcie so znamienkom mínus, obmedzenie je ekvivalentné nerovnosti a konvexnosť vyplýva z konkávnosti a naopak. Odtiaľ

problém konvexného programovania sa tiež nazýva problém minimalizácie konvexnej funkcie pod obmedzeniami:

, ,

kde sú konvexné funkcie; R Je konvexná sada. Je to len iná forma problému.

Treba poznamenať, že ak je problém konvexného programovania formulovaný ako maximálny problém, potom je účelová funkcia nevyhnutne konkávna a ak je formulovaná ako minimálny problém, potom je konvexná. Ak sú obmedzenia zapísané vo forme, potom obmedzujúce funkcie sú konkávne, ak sú obmedzenia zapísané vo forme, tak obmedzujúce funkcie sú konvexné. Toto spojenie je spôsobené prítomnosťou určitých vlastností problému konvexného programovania, ktoré môžu chýbať, ak je takéto spojenie narušené. Dve hlavné takéto vlastnosti sú uvedené v nasledujúcej leme.

Lema 1

Súbor realizovateľných plánov pre problémy s konvexným programovaním

je konvexná. Akékoľvek lokálne maximum konkávnej funkcie je zapnuté NS je globálny.

Ak boli obmedzujúce funkcie konvexné, tak pre definovanú množinu NS(3.14) už nebude nasledovať konvexnosť. V tomto prípade je možné dokázať konvexnosť súpravy:

Ak by bola účelová funkcia konvexná, potom by sa tvrdenie lemy o jej maximách stalo nesprávnym, ale podobné tvrdenie by sa dalo dokázať aj pre minimá.

Funkcia sa volá prísne konvexné na konvexnej množine ak pre nejaké body , a ľubovoľné číslo, ktoré nerovnosť platí.

Funkcia sa volá prísne konkávne na konvexnej množine ak pre nejaké body a pre ľubovoľné číslo platí nasledujúca nerovnosť:

Lema 2

Súčet konvexných (konkávnych) funkcií je konvexný (konkávny). Súčin konvexnej (konkávnej) funkcie a kladného čísla je konvexný (konkávny). Súčet konvexných (konkávnych) a prísne konvexných (prísne konkávnych) funkcií je prísne konvexný (prísne konkávny).

Veta 1

Ak je funkcia striktne konkávna (striktne konvexná) na konvexnej množine NS, potom môže mať len jeden maximálny (minimálny) bod.

Dôkaz

Predpokladajme opak, t.j. že sú tam dva body ,, čo sú maximálne body striktne konkávnej funkcie na NS... Označenie, máme ... Potom pre všetky platí:

tie. došlo k rozporu. Dôkaz je podobný pre minimum striktne konvexnej funkcie.

Lineárna funkcia je jediným príkladom konvexnej aj konkávnej funkcie, takže nie je striktne konvexná (prísne konkávna). Kvadratická funkcia nemusí byť konvexné (konkávne), ale môže byť prísne konvexné (prísne konkávne); toto všetko určuje matica D... Maticové prvky D predstavujú druhé parciálne derivácie kvadratickej funkcie, t.j.

.

Maticu druhých parciálnych derivácií označme ako.

Lema 3

Aby kvadratická funkcia bola konvexná (konkávna) v celom priestore, je potrebné a postačujúce, aby matrica D bola pozitívne (negatívne) definovaná. Ak D pozitívne (negatívne) definované, t.j.

potom je prísne konvexný (prísne konkávny).

Problém maximalizácie (minimalizácie) kvadratickej funkcie pri lineárnych obmedzeniach, kde D Je negatívna (pozitívna) určitá matica a D T= D sa volá problém kvadratického programovania .

Z lemy vyplýva, že problém lineárneho programovania uvažovaný v časti 2, podobne ako problém kvadratického programovania, je špeciálnym prípadom problému konvexného programovania.

Existujú funkcie, ktoré sú v jednej skupine premenných konvexné a v inej konkávne. Takéto funkcie predstavujú jednu z hlavných tried funkcií, pre ktoré určite existuje sedlový bod.

Veta 2

(O existencii sedlového bodu pre konkávno-konvexnú funkciu). Nechať byť X a Y sú konvexné uzavreté ohraničené podmnožiny konečno-rozmerných euklidovských priestorov a funkcia je spojitá a, konkávna a konvexná, má sedlový bod.

Zvážte Lagrangeovu funkciu pre konvexný problém programovania:

(3.15)

definované na priamom produkte, kde. Táto funkcia je vďaka svojej konkávnosti konkávna a lineárna, a teda konvexná.

Na základe vety 1 však nemožno tvrdiť, že má sedlový bod, pretože množina R nie je nevyhnutne uzavreté a obmedzené, ale Y samozrejme neobmedzene. Napriek tomu sa dá očakávať, že za určitých podmienok bude sedlový bod stále existovať.

Najznámejšia veta súvisiaca s touto problematikou je Kuhn-Tuckerova veta, ktorá vytvára spojenie medzi existenciou riešenia konvexného programovacieho problému a sedlovým bodom pre Lagrangeovu funkciu, keď Slaterove podmienky : konvexný problém programovania spĺňa podmienku Slater, ak existuje bod, v ktorom je podmienka splnená: .

Kuhn-Tuckerova veta

Ak konvexný problém programovania spĺňa Slaterovu podmienku, tak nevyhnutnou a postačujúcou podmienkou pre optimálnosť návrhu je existencia takej, že dvojica je sedlovým bodom Lagrangeovej funkcie (3.15) zapnutá.

Že Slaterova podmienka je nevyhnutná, ukazuje nasledujúci príklad.

Príklad 1

Je daný konvexný problém programovania:

Tu je zrejmé, že X = 0 má riešenie problému, ale Lagrangeovu funkciu neexistuje žiadny sedlový bod, pretože vonkajšia plocha v probléme minimax nie je dosiahnutá:

Rozdelenie obmedzení v konvexnom programovacom probléme do a , ako už bolo spomenuté, je podmienené. Preto zvyčajne pod R sa rozumie súbor jednoduchej formy, tým je buď celý priestor E n, alebo nezáporný ortant alebo rovnobežnosten. Zložitosť problému konvexného programovania je určená systémom obmedzení:

.

Keďže sedlový bod Lagrangeovej funkcie sa hľadá na súčine zostáv, kde Y je tiež množina jednoduchej formy (nezáporný orthant), zmyslom Kuhnovej-Tuckerovej vety je zredukovať problém nájdenia extrému funkcie s komplexnými obmedzeniami na premenné na problém nájdenia extrému novej funkcie. s jednoduchými obmedzeniami.

Ak je súbor R sa zhoduje s E n, potom podmienky pre extrém, ako je známe, majú tvar:

Navyše, tieto podmienky sú nielen nevyhnutné na to, aby funkcia dosiahla maximum, ale aj postačujúce. Toto je dôležitá vlastnosť konkávnych funkcií a pre problém konvexného programovania je konkávna.

Veta 3

Aby kontinuálne diferencovateľná konkávna funkcia mala maximum v bode na E n, je potrebné a postačujúce, aby gradient funkcie v bode bol rovný nule, t.j. ...

Pripomeňme, že gradient funkcie je:

.

Teda nájsť sedlový bod Lagrangeovej funkcie na produkte a následne nájsť riešenie konvexného programovacieho problému pre R= E n je potrebné riešiť sústavu rovníc (3.16). Ale v tomto systéme n rovnice a neznáme n+ m, keďže okrem toho n-rozmerný vektor je nám neznámy a m-rozmerný vektor Lagrangeových multiplikátorov. Pre sedlový bod Lagrangeovej funkcie však platí veľmi dôležitá vlastnosť:

. (3.17)

Z rovnice (3.17) vyplýva, že buď, alebo, alebo oboje súčasne. Táto vlastnosť je podobná druhej vete o dualite (časť 2.5) lineárneho programovania. Obmedzenia, ktoré sú v určitom bode splnené ako rovnosť, sa nazývajú aktívny .

Teda len tie Lagrangeove multiplikátory môžu byť nenulové, ktoré zodpovedajú obmedzeniam aktívnym v danom bode. Berúc do úvahy túto vlastnosť, na nájdenie riešenia konvexného programovacieho problému zvážte nasledujúcu metódu.

Veľké množstvo praktických ekonomických situácií, ktorých štúdium je predmetom matematického programovania, sa buď vôbec nedá redukovať na lineárne úlohy, alebo (aj keď sa takáto linearizácia v určitom štádiu vykonáva) je stále snaha o podrobnejšiu úvahu. vedie k nelinearite.

Najvšeobecnejší problém nelineárneho programovania možno formulovať takto:

je potrebné určiť hodnoty n premenných x 1, x 2, ..., x n, ktoré spĺňajú m rovníc alebo nerovníc tvaru

i = 1, 2, ..., m.

a previesť cieľovú funkciu na maximum (alebo minimum)

f (X) = f (x 1, x 2, ..., x n).(2.2)

Predpokladajme, že f a g i sú nelineárne dané funkcie, b i sú známe konštanty. Vo všeobecnosti sa predpokladá, že všetky alebo aspoň niektoré premenné musia byť nezáporné.

V konkrétnom prípade lineárneho programovania sa predpokladá, že funkcie f a g i sú lineárne, t.j.

Akýkoľvek iný problém matematického programovania okrem tohto sa považuje za nelineárny problém.

V príslušných oddieloch matematiky boli vyvinuté všeobecné (klasické) metódy na určovanie maxím a miním funkcií rôzneho typu. Takýto všeobecný prístup k riešeniu úloh však prakticky nachádza obmedzené uplatnenie pri získavaní numerických výsledkov, keďže vedie k potrebe riešiť nelineárne sústavy rovníc s mnohými neznámymi a nie je vhodný na hľadanie hraničných extrémov. Preto sa v matematickom programovaní študujú najmä metódy, ktoré môžu slúžiť ako algoritmus, teda ako výpočtový postup na numerické riešenie špeciálnych problémov so špecifickými ekonomickými aplikáciami. Naznačme niektoré z týchto problémov.

Najdôkladnejšie študované problémy s lineárnymi obmedzeniami a nelineárnou cieľovou funkciou. Avšak aj pre tieto problémy boli výpočtové metódy vyvinuté len v prípadoch, keď cieľová funkcia má určité vlastnosti. Najmä napríklad funkcia cieľa môže byť reprezentovaná ako

kde funkcie f j (x j) musia mať zase určité obmedzenia. Ide o takzvanú oddeliteľnú funkciu. V inom prípade možno účelovú funkciu zapísať ako súčet lineárnych a kvadratických funkcií:

Nelineárne problémy tohto typu sa nazývajú problémy kvadratického programovania. Aby bolo možné nájsť optimálne riešenie, je potrebné uložiť niektoré ďalšie obmedzenia na hodnoty d ij.

Problémy s nelineárnymi obmedzeniami sú ťažšie ako lineárne. Aby sa dosiahlo optimálne riešenie týchto problémov, musia byť kladené veľmi prísne požiadavky na funkcie g i a f. Optimálne riešenie nelineárneho problému možno získať najmä vtedy, ak obmedzenia gi dané nelineárnymi nerovnosťami definujú konvexnú množinu v priestore premenných (pozri kapitolu 1, oddiel 3) a cieľovou funkciou je nelineárna hladká konvexná alebo konkávna funkcia. . V nasledujúcom texte bude uvedená presná definícia konvexných a konkávnych funkcií. Tu je však potrebné len upozorniť, že vlastnosť konvexnosti funkcií f zabezpečuje existenciu len jedného minima a vlastnosť konkávnosti funkcie f iba jedno maximum funkcie f vo vnútri oblasti definovanej obmedzeniami. Na tom sú založené algoritmy na určenie optimálnej hodnoty cieľovej funkcie. Pri absencii konvexnosti alebo konkávnosti riešenie problému matematického programovania naráža na prítomnosť lokálnych miním alebo maxím, na hľadanie ktorých sú vo všeobecnom prípade použiteľné klasické metódy.

(dokument)

Projekt kurzu – Štýly programovania. Praktická časť - hra na 100 zápasov (kurz)

Laboratórna práca č.4. Viacrozmerné vyhľadávanie. Nelineárne programovanie. Neobmedzené metódy minimalizácie (laboratórium)

Veselov S.L. Programovanie ústrední Samsung a Panasonic (dokument)

Prezentácia - Lineárne programovanie (abstrakt)

Tichomirova L.S. Metódy minimalizácie boolovských funkcií (dokument)

Kirsanová O.V., Semjonová G.A. Matematické programovanie (typický výpočet) (dokument)

Kozyrev D.V. 1C: Konfigurácia a programovanie Enterprise 7.7. Účtovníctvo komponentov. Dištančný kurz (dokument)

Laboratórna práca č.1. Neobmedzená jednorozmerná optimalizácia (laboratórium)

A. P. Moschevikin "Teória rozhodovania" Prezentácie z prednášok (dokument)

n1.doc

1. 
   Konvexné programovanie. Kuhn-Tuckerova veta. Kuhn-Tucker podmienky

V teórii konvexného programovania je hlavným problémom minimalizácia konvexnej funkcie

Za podmienok

(1.3)

Kde sú funkcie
sa predpokladá, že sú konvexné.

Ak
a sú konkávne funkcie, potom máme problém s maximalizáciou
s obmedzeniami
a

Zostavme Lagrangeovu funkciu pre tento problém:

Bod sa nazýva sedlový bod funkcie (1.4), ak je bod minimálnym bodom funkcie
a bod je maximálny bod funkcie. Inými slovami, na bod do sedla pre všetkých
a vzťah platí

(1.5)

Veta 1 (Kuhn-Tuckerova veta). Nech je tam aspoň jeden bod
, pre ktoré
... Potom nevyhnutná a postačujúca podmienka pre optimálnosť vektora
patriace do oblasti realizovateľných riešení úlohy (1.1) - (1.5) je existencia takéhoto vektora
že pre všetkých a
nerovnosti (1,5)

Prijímame túto vetu bez dôkazu.

Kuhn-Tuckerova veta sa nazýva aj veta o sedlovom bode.

Ak
a
sú diferencovateľné funkcie, potom sú nerovnosti v (1.5) ekvivalentné nasledujúcim miestnym Kuhn-Tuckerovým podmienkam:

Tieto výrazy znamenajú, že hodnoty derivátov sa berú v bode
.

1.2. Kvadratické programovanie. Barankin-Dorfmanova metóda.

Špeciálnym prípadom problému konvexného programovania je problém kvadratického programovania. Hlavným problémom kvadratického programovania je problém minimalizácie funkcie Z, ktorá je súčtom lineárnej a kvadratickej funkcie:

Pri lineárnych obmedzeniach

Matica D sa považuje za symetrickú a nezáporne definitívnu. V tomto prípade bude funkcia (2.1) konvexná.

Zostavme pre úlohu (2.1) - (2.3) lokálne Kuhn-Tuckerove podmienky (1.6) - (1.7), ktoré sú nevyhnutnými a postačujúcimi podmienkami pre optimálnosť riešenia úlohy (2.1) - (2.3).

Lagrangeova funkcia je v tomto prípade:

Poďme nájsť parciálne derivácie tejto funkcie:

Označujeme

Berúc do úvahy tento zápis, vzťahy (2.4) a (2.5), Kuhn-Tuckerove podmienky (1.6) - (1.7) majú nasledujúci tvar

Rovnice (2.6) a (2.7) tvoria sústavu N = n + m lineárnych rovníc s 2N = 2 (n + m) neznámych:.

Takže v súlade s Kuhnovou-Tuckerovou vetou riešenie
problému (2.1) - (2.3) kvadratického programovania je optimálny vtedy a len vtedy, ak spolu s riešením
existujú riešenia
a
také, že ide o riešenie sústavy (2.6) - (2.8) za podmienky, že platí rovnosť (2.9).

Podmienka (2.9) pre problém (2.1) - (2.3) je ekvivalentná splneniu podmienky

Existuje niekoľko metód na riešenie problému kvadratického programovania. Zoberme si jednu z nich - metódu Barankin-Dorfman.

Touto metódou sa najprv redukuje systém rovníc (2.6) - (2.7) do tvaru:

Kde (základné premenné) a
(voľné premenné) sú rôzne prvky nejakej permutácie premenných a všetky sú nezáporné čísla (i = 1,2,…, N).

Potom sa zo systému (2.11) nájde počiatočné riešenie podpory

Systémy (2.6) - (2.8) a zložky vektora usporiadané v poradí.

Ak pre riešenie podmienka (2.10) je splnená, potom je vyriešený problém (2.1) - (2.3) a jeho optimálne riešenie
sa zistí zo zodpovedajúcich komponentov vektora.

Ak pre podmienku (2.10) nie je splnená, potom pre prechod na iné referenčné riešenie sa zostaví nasledujúca tabuľka (tabuľka 2.1). Telo tejto tabuľky obsahuje riadky pre všetky premenné v poradí. Pre základné premenné sú prvky riadkov prevzaté zo systému (2.11) a pre voľné premenné zo vzťahov

Parametre dodatočnej časti tabuľky 2.1 sú nasledovné:

A) sa nachádzajú zo vzorca kde - vektor zložený z prvkov s-tého stĺpca hlavnej časti tabuľky;

B) pre tie s pre ktoré
, zostávajúce parametre sa vypočítajú:

(prvky príslušných stĺpcov poskytujúce minimum označené hviezdičkou),
.

Stĺpec, ktorý zodpovedá najmenšiemu záporu , je priradený ako permisívny stĺpec, riadok s hviezdičkou tohto stĺpca je permisívny riadok a tento prvok sám je permisívnym prvkom a pomocou nich sa vykoná simplexná transformácia tabuľky 2.1.

kde:

Výsledkom je nové podporné riešenie systému (2.6) - (2.8). Tento proces pokračuje, kým nie je splnená podmienka (2.10). Padám
, a
, potom sa ako počiatočné zvolí iné riešenie.

1.3 Príklad riešenia úlohy metódou Barankin-Dorfman
Minimalizovať funkciu

S obmedzeniami:

;
.

Riešenie

Nájdite počiatočné podporné riešenie pre systém (2.12). V tomto prípade sa hodnota účelovej funkcie rovná.

Potom podmienka (2.10) nie je splnená, a preto riešenie nie je optimálne.

Zostavme si tabuľku 2.2, aby sme prešli na nové podporné riešenie systému (2.12) - (2.13). Hlavnú časť tejto tabuľky vyplníme pomocou systému (2.12).

A) pre dodatočnú časť tabuľky nájdeme:

B) za pozitívne a vypočítajte ostatné parametre:

Štvrtý stĺpec s najmenším záporom , priradíme rozlišovací stĺpec, riadok s prvkom 3 tohto stĺpca - rozlišovaciu čiaru a samotný prvok 3 - rozlišovací prvok a s ich pomocou vykonáme simplexnú transformáciu tabuľky 2.2.

Výsledkom je tabuľka 2.3, ktorá obsahuje nové riešenie podpory.

Pre toto riešenie

Doplnkovú časť tabuľky 2.3 preto vyplníme rovnakým spôsobom ako v predchádzajúcom prípade, aby sme prešli na nové referenčné riešenie sústavy (2.12) - (2.13).

Ak tabuľku 2.3 podrobíme simplexnej transformácii s rozlišovacím prvkom na 13,30, dostaneme ďalšiu tabuľku s referenčným riešením, pre ktoré
.

Tak sa našlo optimálne riešenie
, pri ktorej je účelová funkcia Z daného problému minimalizovaná. V čom

1.4 Samostatná úloha: riešenie úlohy metódou Barankin-Dorfman

;

Riešenie

Zo vzťahov (2.6) - (2.7) dostaneme nasledujúcu sústavu rovníc:

Po jednoduchých transformáciách uvádzame tento systém do podoby:

(2.14)

Odkiaľ, berúc do úvahy nezápornosť

Nájdite počiatočné základné riešenie
systém (2.14). V tomto prípade je hodnota účelovej funkcie
.

Pretože potom podmienka (2.10) nie je splnená, a preto riešenie nie je optimálne.

Zostavme si tabuľku 2.4, aby sme prešli na nové základné riešenie sústavy (2.14) - (2.15).
Tabuľka 2.4

, a, potom musí byť výber počiatočného riešenia podpory vykonaný nanovo.

	1	-	-	-
	0	-1	0	0
	0	0	-1	0
	4	1	-2	0
	0	0	0	-1
	2	4 *	-6	-2
	4	2	0	-1
	32
		12	-10	-4
		4
		1/2		Tabuľka 2.5	0	0	-1
	0	-1	0	0
	3	-1/2	3 *	0
	110,25
		-2,5	9	-2
			-3