Problémy s konvexným programovaním. Konvexné programovanie

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

Najobecnejší problém s nelineárnym programovaním je možné formulovať takto:

je potrebné určiť hodnoty n premenných x 1, x 2, ..., x n, ktoré vyhovujú m rovniciam alebo nerovniciam 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. Všeobecne sa predpokladá, že všetky alebo aspoň niektoré z premenných 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, ktorý sa netýka tohto, sa považuje za nelineárny problém.

V príslušných častiach matematiky boli vyvinuté všeobecné (klasické) metódy určovania maxím a minimov funkcií rôznych typov. Takýto všeobecný prístup k riešeniu problémov však prakticky nachádza obmedzené použitie na získanie numerických výsledkov, pretože vedie k potrebe riešenia nelineárnych systémov 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ú hlavne metódy, ktoré môžu slúžiť ako algoritmus, to znamená ako výpočtový postup pre numerické riešenie špeciálnych problémov so špecifickými ekonomickými aplikáciami. Uveď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é iba v prípadoch, keď má cieľová funkcia určité vlastnosti. Konkrétne môže byť napríklad cieľová funkcia vyjadrená ako

kde funkciám f j (x j) musia byť naopak uložené určité obmedzenia. Toto je takzvaná oddeliteľná funkcia. V inom prípade možno objektívnu funkciu zapísať ako súčet lineárnych a kvadratických funkcií:

Nelineárne problémy tohto typu sa nazývajú kvadratické programovacie problémy. Aby bolo možné nájsť optimálne riešenie, je potrebné uložiť ďalšie obmedzenia v hodnotách 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 sa na funkcie g i a f klásť veľmi prísne požiadavky. Optimálne riešenie nelineárneho problému možno dosiahnuť 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. . Ďalej bude uvedená dôsledná definícia konvexných a konkávnych funkcií. Tu je potrebné len poukázať na to, že konvexná vlastnosť funkcií f zaisťuje existenciu iba jedného minima a konkávna vlastnosť f zaisťuje iba jedno maximum f vo vnútri oblasti definovanej obmedzeniami. Z toho sú založené algoritmy na určenie optimálnej hodnoty cieľovej funkcie. Ak absentuje konvexnosť alebo konkávnosť, riešenie problému matematického programovania naráža na prítomnosť miestnych minim alebo maxim, na ktoré sa vo všeobecnosti dajú použiť klasické metódy.

Zváženie tejto triedy problémov sa zvyčajne začína prezentáciou metóda neurčitých Lagrangeových multiplikátorov. Za to dáme toto / (x, ..., X ") a g (x b ..., X ")- spojité funkcie spolu s ich parciálnymi deriváciami, nateraz odstraňujeme podmienky pre nezápornosť premenných a formulujeme nasledujúci problém pre podmienené extrémy:

Pri hľadaní jeho riešenia uvádzame Lagrangeove multiplikátory y b / = 1, t a zostaviť tzv Lagrangeova funkcia:

nájsť a vyrovnať na nulu jej 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 v ..., X ") v bode má extrém, potom existuje vektor Y (0> = (y, 0, ..., y °) že bod (Ag (0), F (0)) je riešením systému (2.23). Riešením systému (2.23) preto získame body, v ktorých funkcia (2.20) môže mať extrém. Nájdené body sa ďalej skúmajú rovnakým spôsobom ako pri riešení problému nepodmieneného extrému.

Lagrangeova multiplikátorová metóda teda zahrnuje nasledujúce kroky.

• 1. Vytvorte Lagrangeovu funkciu.
• 2. Nájdite čiastočné deriváty vzhľadom na Xj a y, z Lagrangeovej funkcie a vyrovnajte ich na nulu.
• 3. Systém riešenia problémov (2.23), nájdite body, v ktorých môže mať objektívna funkcia extrémnosť.
• 4. Medzi bodovými kandidátmi na extrém nájdite tie, pri ktorých je extrém dosiahnutý, a vypočítajte hodnoty funkcie f (x, ..., X ") v týchto bodoch.

Popísaná metóda je použiteľná na problémy s konvexným programovaním, t.j. na tie, v ktorých je objektívna funkcia konvexná (alebo konkávna) a oblasť uskutočniteľných riešení určená obmedzeniami je tiež konvexná.

Definícia 1. Funkcia f (x,..., x n), dané na konvexnej množine X, sa nazýva konvexný, ak pre akékoľvek body X, X 2 z Hee pre ľubovoľné číslo X, 0 X 1 nerovnosť

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

Definícia 3. Sada uskutočniteľných riešení problému s konvexným programovaním spĺňa podmienku pravidelnosti, ak existuje aspoň jeden bod Xj, patriace do regiónu uskutočniteľných riešení, pre ktoré g ^ XJ) =b h i = 1, t.

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

Definícia 4. Lagrangeovou funkciou problému s konvexným programovaním je funkcia

kde y je Lagrangeov multiplikátor.

Definícia 5. Bod (X (0), T (0)) = (x, °, ..., X (',r, 0,..., y " ) zavolal sedlový bod Lagrangeovej funkcie, Ak

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

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

kde DA) je nelineárna diferencovateľná funkcia vyhovujúca podmienkam

kde je gradient funkcie /

v bode A “(0).

Dôkazy.

Rozšírte objektívnu funkciu v Taylorovom rade v susedstve bodu X (())

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 akákoľvek hodnota súradnice vektora x | 0)> 0, potom derivát

, pretože inak súradnica x až môcť,

s pevnými hodnotami zvyšných premenných pokračujte v minimalizácii objektívnej 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 malo byť pokiaľ

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

Veta je dokázaná.

Definujme si teraz nevyhnutné a dostatočné podmienky pre existenciu bodu sedla Lagrangeovej funkcie.

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

Dôkazy.

1) Nevyhnutnosť. Nech (X (0), Y "(0)) je bod sedla, 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). Je tak dokázaná nevyhnutnosť.

• 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) vyplýva, že pri zohľadnení podmienok (2.27) a (2.28) je uvedené

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

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

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

Ak sú v probléme s konvexným programovaním (2.20) - (2.21) objektívna funkcia a obmedzenia neustále diferencovateľné, potom je možné Kuhnovu-Tuckerovu vetu doplniť analytickými výrazmi definujúcimi potrebné 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 problému s programovaním. Toto sú výrazy (2.27) a (2.28). Sú spokojní s problémom kvadratického programovania. Pre jeho finálnu formuláciu uvádzame niekoľko definícií a jednu vetu.

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

Definícia 7. Kvadratická forma F sa nazýva pozitívny / negatívny 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ý semidefinit, ak F (X ")>О / YES ") X, a navyše existuje taká množina premenných - zložiek vektora X ",čo F (X ") = 0.

Veta 5. Kvadratická forma je konvexná / konkávna funkcia, ak je pozitívna / negatívna semidefinitná.

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

s obmedzeniami

kde je kladný / záporný semidefinitný kvadratický tvar, tzv kvadratický problém programovania(RFQ).

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

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

Pre 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, použitá na zistenie minimálnej hodnoty umelej objektívnej funkcie F = ^ Pj, kde p sú umelé premenné. Metóda ako-

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. Formou výrazov (2.27), (2.28) zapíšeme potrebné a dostatočné podmienky pre existenciu sedlového bodu Lagrangeovej funkcie.
• 3. Použitím metódy umelého základu sa stanoví absencia sedlového bodu pre Lagrangeovu funkciu alebo sa nájdu jeho súradnice.
• 4. Zapíšte si optimálne riešenie pôvodného problému a nájdite hodnotu objektívnej funkcie.

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

Rozhodnutie. Nasledujúca funkcia by mala byť minimalizovaná:

za podmienok:

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

Vypočítajme čiastkové derivácie tejto funkcie vzhľadom na X, x 2, r a vyrovnať ich na nulu:

Prenesenie v prvej a druhej rovnici o na pravú stranu a rovnicou na ľavú stranu dostaneme zjavné skratky:

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

Použitím druhých parciálnych derivácií je ľahké ukázať, že nájdený bod je podmienené minimum funkcie /

Problémy podobné tým, o ktorých sa diskutuje vyššie, v mnohých spočíva v hospodárskej praxi. Pravda, skutočné problémy zvyčajne obsahujú veľké množstvo premenných a obmedzení, čo znemožňuje ich riešenie bez použitia počítača. Účinnosť používania štandardizovaného softvéru je však určená vedomosťami výskumníka o povahe transformácií uskutočňovaných počítačom. To mu pomáha správne sa orientovať v rôznych metódach, výpočtových postupoch a softvérových systémoch navrhovaných na riešenie problémov s optimalizáciou.

Na upevnenie témy zvážte ešte jednu číselný príklad(Č. ​​2). Nájdite maximálnu hodnotu funkcie

za podmienok:

Rozhodnutie. 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,čo je negatívne definované. Obmedzenia obsahujú iba lineárne obmedzenia. V dôsledku toho možno použiť Kuhn-Tuckerovu vetu a schému riešenia CSP.

1. Zostavme Lagrangeovu funkciu:

2. Zapíšme si potrebné a dostatočné podmienky pre existenciu sedlového bodu funkcie Ľ

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

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

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

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

Tu zjavné základné uskutočniteľné riešenie vyzerá takto:

Objektívna funkcia F vyjadrovať prostredníctvom nepodstatných premenných:

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

Prednáška 11.Konvexné programovanie

Definícia 1. Z konvexným programovaním je nelineárny problém programovania, pri ktorom sú všetky funkcie konvexné.

Problém s konvexným programovaním je teda problémom podmienenej minimalizácie, keď objektívna funkcia je konvexná a uskutočniteľnou doménou je konvexná množina tvorená systémom konvexných nerovností. Preto sú vyhlásenia získané skôr v časti 6 platné pre problém s konvexným programovaním. V tejto časti konkretizujeme tieto všeobecné výsledky a prinášame ich do formy, ktorá je pohodlnejšia na štúdium a riešenie nasledujúceho problému s konvexným programovaním:

(1)

, (2)

. (3)

Budeme potrebovať nejaké pomocné konštrukcie vo vesmíre
vektory
... Vektor z prvého
bodová zložka bude označený ... Takže
.

Pre úlohu (1) - (3) definujeme množinu

Kde
.

Lemma . Pre problém s konvexným programovaním (1) - (3) veľa konvexne.

Dôkazy. Vyberte ľubovoľné vektory
zástupu a číslo
... Potom existujú body a z ako a. Tieto nerovnosti vynásobíme a
a prípadne ich pridať. Pretože všetky funkcie sú konvexné, dostaneme

Zo získaných nerovností vyplýva, že množina je konvexná .

Veta 1. (Kuhn-Tuckerova veta vo forme bodu sedla Lagrangeovej funkcie problému s konvexným programovaním ) Predpokladajme, že v probléme s konvexným programovaním (1) - (3) systém (2) vyhovuje podmienke Slater vzhľadom na bolo riešením problému (1) - (3), je nevyhnutné a dostatočné, aby existoval nezáporný vektor také, že
Je bodom sedla Lagrangeovej funkcie.

Dôkazy. Pretože dostatočnosť tejto podmienky už bola preukázaná pre svojvoľný problém s nelineárnym programovaním (pozri vetu 2.6 v úvode), zostáva iba dokázať nevyhnutnosť.

Nevyhnutnosť. Nechaj sa - riešenie problému (1) - (3). Dali sme
... Je to zrejmé
, as
,
a
.

Uistite sa, že to
... Predpokladajme opak. To znamená, že tu je bod
také, že
... Teda - taký prijateľný bod, ktorého hodnota objektívnej funkcie je menšia ako minimum Skutočnosť, že sme, je v rozpore - riešenie problému s konvexným programovaním.

Takže
... Podľa lemmy množina konvexný. Následne sú splnené všetky požiadavky vety 8.2. Preto existuje nenulová hodnota

vektor
otočný bod do zástupu :

Ďalej overíme, či sú všetky súradnice vektora nie sú pozitívne. Predpokladajme opak. Nech je súradnica
... Opravme vektor všetky komponenty okrem -Och. Potom, s prihliadnutím na to, že výrobok
môže nadobúdať ľubovoľne veľké hodnoty (pretože súradnice sú neohraničené zhora) ), dostaneme rozpor s nerovnosťou (4).

Je ľahké to vidieť pre kohokoľvek
vektory
obsiahnuté v mnohých ... Potom od (4) máme:

Ukážme to
... Nech to tak nie je. Potom
... Teda
... Podľa Slaterovho stavu existuje vektor
také, že
... preto
... Výsledný rozpor to znamená
.

Označujeme
... Ukážme, že skonštruovaný vektor je požadovaný vektor Lagrangeových multiplikátorov. Je to zrejmé
a od (5) získame

Preto, na
by mal

. (7)

Na druhej strane však od
(pokiaľ
) a
, dostaneme nerovnosť

... Z toho a (7) vyplýva, že v danom bode
je splnená podmienka doplnkovej nečinnosti:

. (8)

Z (6) a (8) máme

alebo, ktorý je rovnaký,

Ďalej dovoľte
... Potom
... Z toho a (8) dostaneme nerovnosť

Nerovnosti (9), (10) a znamenajú to
Je bodom sedla Lagrangeovej funkcie konvexného problému

programovacie logo. Čo sa vyžadovalo.

Pred oboznámením sa s ďalšou verziou Kuhn-Tuckerovej vety uvádzame nasledujúcu vetu, ktorá je podmieneným minimálnym kritériom z hľadiska podporných vektorových kužeľov.

Veta 2. Nechaj sa - konvexné a diferencovateľné na
funkcia, nastav
konvexný. Potom pre bod
bolo podmienené minimum funkcie na pľaci
, je to nevyhnutné a postačujúce na zaradenie

. (11)

Dôkaz vyplýva priamo z vety 6.5 a definície kužeľa
podporné vektory v bode do zástupu
.

Veta 3. (Kuhn-Tuckerova veta v diferenciálnej forme pre problém s konvexným programovaním ) Nech je problém s konvexným programovaním uvedený v tvare (1), (2), kde sú všetky funkcie
sú nepretržite diferencovateľné, systém (2) vyhovuje podmienke Slater. Potom, aby vektor
bolo riešením problému (1), (2), je nevyhnutné a dostatočné, aby existoval nezáporný vektor také, že podmienky

, (12)

.

Dôkazy. Ukážme, že podmienky (12) a (13) sú ekvivalentné inklúzii (11). Nechajte bod
je taký, že
... Potom
a
.

Poďme teraz
... Potom z viet 2 a 10.5 vyplýva, že nevyhnutnou a dostatočnou podmienkou pre extrém je existencia takýchto faktorov
,
pre ktoré
... Dali sme
pre všetkých
a získame z posledných podmienok rovnosti (12) a (13). Čo sa vyžadovalo.

Na záver tejto časti uvádzame formulácie dvoch Kuhn-Tuckerových viet pre problém

konvexné programovanie s lineárnymi obmedzeniami.

Veta 4. Nech sústava obmedzení (2) v konvexnom probléme s programovaním (1) - (3) má tvar

, b je vektor dimenzie
... Potom, aby bol nezáporný vektor bolo riešením problému, je nevyhnutné a postačujúce

existoval nezáporný vektor také, že
Je bodom sedla Lagrangeovej funkcie daného problému.

Upozorňujeme, že v tomto prípade má Lagrangeova funkcia tvar.

Veta 5. Nechajte v konvexnom probléme s programovaním (1), (2) objektívnu funkciu je neustále diferencovateľný, systém obmedzení (2) má formu
, kde A je matica dimenzie
, b je vektor dimenzie
. Potom, aby vektor
bolo riešením problému, je nevyhnutné a dostatočné, aby existoval nezáporný vektor také, že podmienky
,
.

Upozorňujeme, že vo vetách 4 a 5 nie je splnenie podmienky Slater požadované, preto nejde o zvláštne prípady viet 1 a 3 a vyžaduje si nezávislý dôkaz.

Funkcia definovaná na konvexnej množine sa nazýva konvexná, ak nerovnosť platí pre akékoľvek body a pre všetky. Lineárna kombinácia s nezápornými koeficientmi funkcií konvexných na konvexnej množine je konvexná funkcia na danej množine. Nech sú funkcie definované na konvexnej množine konvexné.

Zdieľajte svoju prácu na sociálnych sieťach

Ak vám táto práca nevyhovovala, v dolnej časti stránky je zoznam podobných prác. Môžete tiež použiť tlačidlo vyhľadávania

Prednáška číslo 12

KONVEXOVÉ PROGRAMOVANIE

Široká trieda problémov matematického programovania je spojená s minimalizáciou konvexných funkcií viacerých premenných definovaných na konvexnej množine. Takéto problémy sa nazývajú problémy s konvexným programovaním (CVP).

Problém matematického programovania

(12.1)

sa nazýva problém s konvexným programovaním, ak sú všetky funkcie konvexné.

Poďme sa venovať prvkom konvexnej analýzy - oblasti matematiky, v ktorej sa študujú vlastnosti konvexných množín a konvexných funkcií a ktorá hrá zásadnú rolu v teórii a metódach riešenia extrémnych problémov.

Prvky konvexnej analýzy

Uveďme niekoľko definícií a zvážme konkrétne príklady konvexných množín. V nasledujúcom sa budeme zaoberať funkciami definovanými na množinách konečného trojrozmerného euklidovského priestoru E n.

Definícia 12.1. Veľa pohľadov

(12.2)

sa nazýva segment spájajúci body a a označuje.

Je zrejmé, že v tomto bode X sa zhoduje s jedným z koncov segmentu (), pre - s druhým () a pre - s niektorým vnútorným bodom segmentu.

Definícia 12.2. Súprava sa volá konvexný ak k nim spolu s ľubovoľnými dvoma bodmi patrí segment, ktorý ich spája.

Konvexnosť množiny znamená, že z príslušnosti k množine vyplýva, že patrí všetkým.

Je zrejmé, že segment, polpriamka, priama čiara, kruh, trojuholník, polrovina a celá rovina sú konvexné.

Celý priestor zjavne tvorí konvexnú množinu. Je vhodné predpokladať, že prázdna množina a množina pozostávajúca z jedného bodu sú konvexné.

Veta 12.1. Farkasova veta.Nech je uvedená rozmerová matica a vektor. Nerovnosť platí pre všetky vtedy a len vtedy, ak existuje taký vektor.

DÔKAZ. Primeranosť. Nechajte vzťahy a buďte spokojní. Potom pre akýkoľvek vektor bude

Nevyhnutnosť. Nech to platí pre všetkých. Zvážte kužeľ. Ak, potom je veta dokázaná. Poďme to predstierať. Sada podľa definície 12.2 je konvexná a uzavretá; preto podľa vety o odlúčení existuje vektor taký, že

(12.3)

pre všetkých.

Pretože pre všetkých, od (12.3) dostaneme to pre všetkých. Prostriedky. Na druhej strane. To je, a keďže to tak je pre všetkých, potom

. (12.4)

Ale teda z (12.3) to vyplýva

. (12.5)

Ak vezmeme z (12.4) a (12.5), dostaneme rozpor s podmienkami vety.

Komentovať. Dajme geometrickú interpretáciu Farkasovej vety. Nechaj sa

a. Kužeľ je súbor všetkých vektorov, ktoré s každým z vektorov zvierajú neakútne uhly. Na obrázku 12.1 je kužeľ zatienený zvislými čiarami a kužeľ vodorovnými čiarami. Geometrický význam vety je nasledovný. Aby pre akýkoľvek vektor nebol uhol medzi a ostrý, je potrebné a postačujúce, aby patril ku kužeľu.

Obr. 12.1

Definícia 12.3. Volá sa funkcia definovaná na konvexnej množine konvexný ak za nejaké body a nerovnosť

(12.6)

Funkcia sa volá striktne konvexné ak pre každú nerovnosť (12.6) platí ako prísna. Funkcia sa volá silne konvexné ak je také číslo, (silná konvexná konštanta) také, že nerovnosť

(12.7)

Akákoľvek silne konvexná funkcia je striktne konvexná, a ešte viac konvexná funkcia, ale nie naopak.

Príkladom konvexnej funkcie je kvadratická funkcia s pozitívnou určitou maticou.

Veta 12.2. Lineárna kombinácia s nezápornými koeficientmi funkcií konvexných na konvexnej množine je konvexná funkcia na danej množine.

DÔKAZ. Nech sú funkcie definované na konvexnej množine konvexné. Ukážme si túto funkciu

, (12.8)

kde je vypuklé.

Pre ľubovoľné body a od a ľubovoľný počet máme

V tomto reťazci vzťahov platí prvá nerovnosť, pretože funkcie sú konvexné. Tento výsledok ukazuje, že funkcia definovaná vzorcom (12.8) je na množine konvexná.

Veta 12.3. Ak je na konvexnej množine konvexná, potom pre všetky body a akékoľvek čísla také, že Jensenova nerovnosť

. (12.9)

DÔKAZ (indukciou). Nerovnosť (12,9) je totiž zrejmá. Skutočne, ak, potom a, t.j. (12.9) je splnená ako rovnosť. Predpokladajme, že (12.9) platí pre, t.j. pre konvexnú kombináciu bodov. Ukážme, že potom platí aj pre konvexnú kombináciu bodov množiny, teda

Navyše, ak, potom je v (12.9) zrejmá rovnosť. Ak. Z konvexnosti a indukčnej hypotézy potom vyplýva, že

Hovorí sa, že súprava vyhovujepodmienka pravidelnostiak pre každého existuje bod taký, že, t.j.

(12.10)

Je ľahké ukázať, že podmienka (12.10) je ekvivalentná inej volanej podmienkepodmienka pravidelnosti Slater.

Veta 12.4. Ak súprava vyhovuje podmienke pravidelnosti(12.10), potom súprava pravidelne Slater, a síce, že existuje bod, v ktorom sú prísne všetky obmedzenia

. (12.11)

DÔKAZ. Nech je splnená podmienka pravidelnosti (12.10). Vyberte bod, ktorý je konvexnou kombináciou bodov, a preto patrí. Potom pre všetky, ktoré budeme mať

tie. ... V tomto reťazci vzťahov platí prvá nerovnosť z dôvodu Jensenovej nerovnosti a druhá - pretože najmenej jeden člen súčtu, konkrétne, striktne menej. Tieto nerovnosti ukazujú, že u uvažovaného platí podmienka pravidelnosti Slater.

Bez dôkazu uvádzame nasledujúcu dôležitú vlastnosť konvexných funkcií.

Konvexná funkcia definovaná na konvexnej množine je spojitá v každom vnútornom bode tejto množiny a má deriváciu v každom vnútornom bode v ľubovoľnom smere.

Dôležitú vlastnosť konvexných diferencovateľných funkcií, ktorú budeme často používať, stanovuje nasledujúca veta.

Veta 12.5. Funkcia diferencovateľná na konvexnej množine je konvexná vtedy a len vtedy, ak existuje a patrí do nerovnosti

. (12.12)

DÔKAZ. Nevyhnutnosť ... Nech je to konvexné. Potom pre akékoľvek u, () a všetky také, ktoré nerovnosť

alebo

odkiaľ

Pri prechode na limit v poslednej nerovnosti pre dostaneme

Primeranosť ... Teraz nech je podmienka (12.12) splnená pre akékoľvek dva body množiny. Potom, pokiaľ ide o príslušnosť, nerovnosti

Vynásobením prvej nerovnosti, druhej a pridaním výsledných nerovností máme

alebo vzhľadom na to, že máme

to je konvexná funkcia na množine.

Zvážte niekoľko extrémnych vlastností konvexných funkcií na konvexnej množine, ktoré zohrávajú zásadnú úlohu pri riešení problému hľadania bodu konvexnej množiny, v ktorom konvexná funkcia definovaná na dosahuje svoju minimálnu hodnotu :.

Veta 12.6. Akýkoľvek bod lokálneho minima funkcie na konvexnej množine je bodom globálneho minima

DÔKAZ. Dovolme byť bodom miestneho minima funkcie na. Potom podľa definície miestneho minimálneho bodu existuje susedstvo s týmto bodom, ktoré predstavuje nerovnosť

. (12.13)

Predpokladajme, že nejde o bod globálneho minima funkcie, to znamená, že existuje bod taký. Zvážte body formulára.

tie. ... To je však v rozpore s podmienkou, ktorá predstavuje bod miestneho minima, pretože pri dostatočne malom mieste je bod v susedstve, kde sa koná (12.13).

Preto je bod globálneho minima na.

Veta 12.7. Množina minimálnych bodov konvexnej funkcie na konvexnej množine je konvexná množina.

DÔKAZ. Nech je množina minimálnych bodov konvexnej funkcie na konvexnej množine, t.j.

Vyberme akékoľvek dva body a. Pretože a je konvexná množina, potom pre každú bude

a keďže funkcia je konvexná, máme

Tj. Okrem toho, keďže je zapnutá minimálna hodnota funkcie, potom. A teda t.j. ... Preto je konvexná množina.

Veta 12.8. Striktne konvexná funkcia na konvexnej množine dosiahne svoje minimum vo viac ako jednom bode.

DÔKAZ. Dovoliť byť striktne konvexnou funkciou na konvexnej množine, t.j. za každú prísnu nerovnosť

Nech =.

Predpokladajme, že existuje taký bod

Akýkoľvek bod potom patrí do množiny a kvôli prísnej konvexnosti funkcie bude

tie. ... To je v rozpore s podmienkou, ktorá je minimálnym bodom. Preto je pointa jedinečná.

Skúšobné papiere

1. Vysvetlite problém s konvexným programovaním.

2. Uveďte definíciu konvexnej množiny.

3. Zadajte formuláciu Farkasovej vety.

4. Podajte geometrickú interpretáciu Farkasovej vety.

5. Zadajte definície konvexnej, striktne konvexnej a silne konvexnej funkcie na konvexnej množine.

6. Uveďte príklady konvexných funkcií.

7. Vytvorte podmienku, aby bola súprava pravidelná.

8. Formulujte podmienky pre pravidelnosť súpravy Slater.

9. Poskytnite nevyhnutnú a dostatočnú podmienku pre konvexnosť funkcie, diferencovateľnýna konvexnej súprave .

10. Vymenujte hlavné extremálne vlastnosti konvexných funkcií na konvexnej množine.

STRANA 131

Nech systém nerovností formulára

(4.3) a funkcia

Z = f (x 1, x 2, ..., x n), (4,4)

navyše všetky funkcie sú konvexné na nejakej konvexnej množine M a funkcia Z je buď konvexná na množine M, alebo konkávne.

Úlohou konvexného programovania je nájsť riešenie systému obmedzení (4.3), pri ktorom cieľová funkcia Z dosiahne svoju minimálnu hodnotu alebo konkávna funkcia Z dosiahne svoju maximálnu hodnotu. (Podmienky pre nezápornosť premenných možno považovať za zahrnuté v systéme (4.3)).

Z hľadiska vlastnosti 3 0 je akýkoľvek problém lineárneho programovania špeciálnym prípadom problému s konvexným programovaním. Všeobecne sú konvexné problémy s programovaním nelineárne problémy s programovaním. Rozdelenie problémov s konvexným programovaním na špeciálnu triedu je vysvetlené extrémnymi vlastnosťami konvexných funkcií: akékoľvek lokálne minimum konvexnej funkcie (lokálne maximum konkávnej funkcie) je súčasne globálne; navyše s ohľadom na vlastnosť 2 0, konvexná (konkávna) funkcia definovaná v uzavretej ohraničenej množine dosahuje v tejto množine globálne maximum a globálne minimum. Z toho teda vyplýva ak je objektívna funkcia Z striktne konvexná (striktne konkávna) a ak doména riešenia systému obmedzení nie je prázdna a ohraničená, potom má problém s konvexným programovaním vždy jedinečné riešenie.

Volá sa funkcia F (X) = F (x 1, x 2, ..., x n) oddeliteľné, ak ju možno reprezentovať ako súčet funkcií, z ktorých každá závisí iba od jednej premennej, t.j. Ak

(je možné, že F i (x i) = 0 pre niektoré i).

Nech je v konvexnom probléme s programovaním uvedená sústava obmedzení (4.3) a objektívna funkcia (4.4) a objektívna funkcia Z a všetky obmedzenia sú oddeliteľné. Potom problém vyzerá takto:

Nájdite minimum konvexnej (maximálnej - konkávnej) funkcie

s obmedzeniami

Myšlienka metódy kusovej lineárnej aproximácie je, že všetky f i a všetky sú nahradené prerušovanými čiarami pozostávajúcimi z úsečiek. V takom prípade sa pôvodný problém s konvexným programovaním nahradí novým, približným problémom, ktorý je problémom lineárneho programovania. Tento problém sa zvyčajne rieši simplexnou metódou a jeho riešenie je približným riešením pôvodného problému s konvexnými programami.

Obrázok 12. Riešenie úlohy konvexného programovania po častiach lineárnou aproximáciou

Pri zostrojení aproximačného problému uvažujme po častiach lineárnu aproximáciu funkcie jednej premennej h (x) danej na intervale. Tento segment rozdelíme na r častí bodmi x 0

Rovnica segmentu lomenej čiary medzi bodmi (x k; h k) a (x k + 1; h k + 1) má tvar (rovnica priamky pozdĺž dvoch bodov). Ak je každý zo vzťahov v tejto rovnosti označený ako, potom dostaneme:

Upozorňujeme, že pre každú z nich existuje jedinečná hodnota vyhovujúca podmienkam (4.7). Označením môžeme prepísať (4.7) vo forme:

[Rovnice (4.8) sa nazývajú parametrické rovnice segmentu.

Ak h (x) = 0, potom sa druhá z týchto rovníc zmení na identitu 0 = 0 a prvá bude mať tvar (4.1) - rovnica segmentu ležiaceho na osi úsečky].

Pre každú rovnicu prerušovanej čiary teda možno napísať tvar:

a iba dve hodnoty sú vždy nenulové (ak x je vnútorný bod k-tého segmentu oddielu) alebo jedna (ak x je totožný s koncom segmentu).

Keď sa vrátime k problému konvexného programovania s oddeliteľnými funkciami, všimneme si, že predovšetkým (v závislosti od systému obmedzení) je potrebné určiť variačný interval každej premennej x j. Potom je každý z tohto intervalu rozdelený na časti bodmi x jk a pomocou vzorcov (4.9) je vykonaná po častiach lineárna aproximácia pre funkcie f j a je zostrojená. Potom môžeme zapísať približnú úlohu pre pôvodnú úlohu (4.6):

Nájdite maximum funkcie

podlieha obmedzeniam (4.10)

Pretože aproximačný problém (4.10) je problémom lineárneho programovania, ktorý sa zvyčajne rieši simplexnou metódou, podmienky pre nezápornosť premenných sa zapisujú osobitne od ostatných obmedzení.

Rozdiel získanej úlohy (4.10) od obvyklej úlohy lineárneho programovania je v tom, že pre každé x j existujú najviac dve susediace nenulové hodnoty, a preto nemožno brať ako hlavné premenné dve s rovnakým j a susediacim k. Upozorňujeme tiež, že samozrejme nie je potrebné uskutočňovať po častiach lineárnu aproximáciu za podmienok nezápornosti premenných členov fj (xj) a (ak existujú).

Táto kapitola preskúmala iba niekoľko optimalizačných techník, ktoré používajú manažéri na efektívne rozhodovanie v podnikoch. Popísané techniky však umožňujú pochopiť základný princíp používania matematického aparátu v ekonómii, ktorý umožňuje výber z rôznych alternatívnych možností, ktoré sú optimálne pre daný prípad alebo situáciu.