Klasické metódy neobmedzenej optimalizácie. Metódy nepodmienenej a podmienenej optimalizácie Podstata metód operačného výskumu

5. Viacrozmerná optimalizácia

Lineárne programovanie

Optimalizácia je cieľavedomá činnosť zameraná na dosiahnutie najlepších výsledkov za vhodných podmienok.

Kvantitatívne hodnotenie kvality, ktorá sa optimalizuje, sa nazýva kritérium optimálnosti alebo cieľová funkcia .Môže byť napísaný v tvare:

(5.1)

kde x 1, x 2, …, x n– niektoré parametre objektu optimalizácie.

Existujú dva typy optimalizačných problémov – nepodmienené a podmienené.

Bezpodmienečná úloha optimalizácia spočíva v nájdení maxima alebo minima reálnej funkcie (5.1).nreálne premenné a určenie zodpovedajúcich hodnôt argumentov.

Problémy podmienenej optimalizácie , alebo problémy s obmedzeniami, sú tie, pri ktorých formulácii sú na hodnoty argumentov kladené obmedzenia vo forme rovnosti alebo nerovností.

Riešenie optimalizačných úloh, v ktorých je kritériom optimality lineárna funkcia nezávislých premenných (t. j. obsahuje tieto premenné do prvého stupňa) s lineárnymi obmedzeniami na ne je predmetom lineárne programovanie.

Slovo „programovanie“ tu odráža konečný cieľ štúdia – určenie optimálneho plánu alebo optimálneho programu, podľa ktorého sa spomedzi mnohých možné možnosti v rámci skúmaného procesu sa na základe určitého kritéria vyberie najlepšia, optimálna možnosť.

Príklad taká úloha je problém optimálnej distribúcie surovín medzi rôznymi odvetviami pri maximálnych výrobných nákladoch.

Nechajte vyrobiť dva druhy výrobkov z dvoch druhov surovín.

Označme: x 1 , x 2 – počet jednotiek výrobkov prvého a druhého typu; c 1, c 2 – jednotková cena výrobkov prvého a druhého druhu, resp. Potom budú celkové náklady na všetky produkty:

(5.2)

V dôsledku výroby je žiaduce, aby celkové náklady na výrobu boli maximalizované.R (x 1, x 2 ) je objektívna funkcia v tomto probléme.

b 1, b 2 – množstvo dostupných surovín prvého a druhého druhu;a ij– počet jednotiek i - druh suroviny potrebnej na výrobu jednotkyj- druh výrobku.

Vzhľadom na to, že spotreba daného zdroja nemôže prekročiť jeho celkové množstvo, zapíšeme obmedzujúce podmienky pre zdroje:

(5.3)

Čo sa týka premenných x 1, x 2 môžeme tiež povedať, že sú nezáporné a nekonečné:

(5.4)

Medzi mnohými riešeniami systému nerovností (5.3) a (5.4) je potrebné nájsť také riešenie ( x 1, x 2 ), pre ktoré je funkciaRdosiahne svoju najväčšiu hodnotu.

V podobnej podobe sú formulované takzvané dopravné problémy (úlohy optimálne zorganizovať dodávku tovaru, surovín či produktov z rôznych skladov do viacerých destinácií s minimálnymi nákladmi na dopravu) a množstvo ďalších.

Grafická metóda riešenia úloh lineárneho programovania.

Nech sa vyžaduje nájsť x 1 a x 2 , uspokojujúce systém nerovností:

(5.5)

a podmienky nezápornosť:

(5.6)

Pre ktorých funkcia

(5. 7 )

dosiahne svoje maximum.

Riešenie.

Zostrojme v sústave pravouhlých súradníc x 1 x 2 oblasť realizovateľných riešení problému (obr. 11). Aby sme to dosiahli, nahradíme každú z nerovností (5.5) rovnosťou vhodné jeho hraničná čiara:

(i = 1, 2, … , r)

Ryža. jedenásť

Táto priamka rozdeľuje celú rovinu na dve polroviny. Pre súradnice x 1, x 2 akýkoľvek bod A v jednej polrovine platí nasledujúca nerovnosť:

a pre súradnice ľubovoľného bodu INďalšia polrovina – opačná nerovnosť:

Súradnice ktoréhokoľvek bodu na hraničnej čiare spĺňajú rovnicu:

Na určenie, na ktorej strane hraničnej čiary sa nachádza polrovina zodpovedajúca danej nerovnosti, stačí „otestovať“ jeden bod (najjednoduchší spôsob je bod O(0;0)). Ak je pri dosadzovaní svojich súradníc do ľavej strany nerovnosti splnená, potom sa polrovina otočí smerom k testovanému bodu; ak nerovnosť splnená nie je, príslušná polrovina sa otočí opačným smerom. . Smer polroviny je na výkrese znázornený šrafovaním. Nerovnosti:

zodpovedajú polrovinám umiestneným napravo od osi y a nad osou x.

Na obrázku zostrojíme hraničné priamky a polroviny zodpovedajúce všetkým nerovniciam.

Spoločná časť (priesečník) všetkých týchto polrovín bude predstavovať oblasť realizovateľných riešení tohto problému.

Pri konštrukcii oblasti realizovateľných riešení môže v závislosti od konkrétneho typu systému obmedzení (nerovností) na premenné nastať jeden z nasledujúcich štyroch prípadov:

Ryža. 12. Oblasť realizovateľných riešení je prázdna, čo zodpovedá nejednotnosti systému nerovností; žiadne riešenie

Ryža. 13. Oblasť realizovateľných riešení predstavuje jeden bod A, ktorý zodpovedá jedinému riešeniu sústavy

Ryža. 14. Oblasť realizovateľných riešení je obmedzená a je znázornená ako konvexný mnohouholník. Existuje nekonečné množstvo realizovateľných riešení

Ryža. 15. Oblasť realizovateľných riešení je neobmedzená, vo forme konvexnej polygonálnej oblasti. Existuje nekonečné množstvo realizovateľných riešení

Grafické znázornenie účelovej funkcie

pri pevnej hodnoteRdefinuje priamku a pri zmeneR- rodina rovnobežných čiar s parametromR. Pre všetky body ležiace na jednej z čiar je funkcia R nadobúda jednu konkrétnu hodnotu, preto sa nazývajú naznačené priamky úrovňové čiary pre funkciu R.

Vektor gradientu:

kolmýk čiaram úrovne, ukazuje smer nárastuR.

Problém hľadania optimálneho riešenia sústavy nerovníc (5.5), pre ktorú je účelová funkciaR(5.7) dosiahne maximum, geometricky zredukuje na určenie v oblasti prípustných riešení bod, cez ktorý bude prechádzať nivelačná čiara zodpovedajúca najväčšej hodnote parametra.R

Ryža. 16

Ak je oblasťou realizovateľných riešení konvexný mnohouholník, potom extrémom funkcieR sa dosiahne aspoň v jednom z vrcholov tohto mnohouholníka.

Ak extrémna hodnotaRsa dosiahne v dvoch vrcholoch, potom sa rovnaká extrémna hodnota dosiahne v ktoromkoľvek bode segmentu spájajúceho tieto dva vrcholy. V tomto prípade sa hovorí, že úloha má alternatívne optimum .

V prípade neohraničenej oblasti extrém funkcieRbuď neexistuje, alebo je dosiahnutá v jednom z vrcholov oblasti, alebo má alternatívne optimum.

Príklad.

Predpokladajme, že potrebujeme nájsť hodnoty x 1 a x 2 , ktorý spĺňa systém nerovností:

a podmienky nezápornosť:

Pre ktorého funkcia je:

dosiahne svoje maximum.

Riešenie.

Nahradme každú z nerovností rovnosťou a zostrojme hraničné čiary:

Ryža. 17

Určme polroviny zodpovedajúce týmto nerovnostiam „testovaním“ bodu (0;0). Vziať do úvahy nezápornosť x 1 a x 2 získame oblasť realizovateľných riešení tohto problému vo forme konvexného mnohouholníka OAVDE.

V oblasti realizovateľných riešení nájdeme optimálne riešenie zostrojením gradientového vektora

zobrazujúcismer nárastuR.

Optimálne riešenie zodpovedá bodu IN, ktorého súradnice možno určiť buď graficky alebo riešením sústavy dvoch rovníc zodpovedajúcich hraničným priamkam AB a VD:

odpoveď: x 1 = 2; x2 = 6; Rmax = 22.

Úlohy. Nájdite polohu krajného bodu a krajnú hodnotu účelovej funkcie

za daných obmedzení.

Tabuľka 9
Možnosť č.	Extrémne	Obmedzenia
	M sekera	; ; ; ;
	Max	; ; ; ;
		; ;
		; ; ; ;
		; ; ; ;
		; ;

Úloha 1. Nájsť

Problém 1 sa týka riešenia sústavy rovníc:

a študujte hodnotu druhého diferenciálu:

v bodoch riešenia rovníc (8.3).

Ak je kvadratická forma (8.4) v určitom bode záporne definitná, potom dosiahne svoju maximálnu hodnotu a ak je pozitívne definitná, potom dosiahne svoju minimálnu hodnotu.

Príklad:

Systém rovníc má riešenia:

Bod (– 1/3,0) je maximálny bod a bod (1/3,2) je minimálny bod.

Úloha 2. Nájsť

za podmienok:

Problém 2 je riešený metódou Lagrangeovho multiplikátora. Ak to chcete urobiť, nájdite riešenie systému (t + p) rovnice:

Príklad. Nájdite strany obdĺžnika s maximálnou plochou vpísanom do kruhu: . Oblasť A obdĺžnika možno zapísať ako: A = 4h, Potom

Úloha 3. Nájsť:

za podmienok:

Táto úloha pokrýva širokú škálu úloh definovaných funkciami f A  .

Ak sú lineárne, potom je problémom problém lineárneho programovania.

Úloha3 A.

za podmienok

Rieši sa simplexovou metódou, ktorá pomocou aparátu lineárnej algebry vykonáva cielené vyhľadávanie vrcholov mnohostenu definovaného (8.13).

Simplexná metóda (pozostáva z dvoch fáz):

Etapa 1. Nájdenie referenčného roztoku x (0).

Referenčným roztokom je jeden z bodov mnohostenu (8.13).

Fáza 2. Nájdenie optimálneho riešenia.

Optimálne riešenie sa nájde postupným vyčíslením vrcholov mnohostenu (8.13), v ktorom hodnota účelovej funkcie z v každom kroku neklesá, teda:

Špeciálnym prípadom problému lineárneho programovania je takzvaný transportný problém.

Problém s dopravou. Nech sú na miestach sklady, v ktorých sa podľa toho skladuje tovar v množstvách. Na miestach sú spotrebitelia, ktorí potrebujú dodávať tento tovar v zodpovedajúcich množstvách. Označme c ij náklady na prepravu jednotky nákladu medzi bodmi

Študujeme fungovanie prepravy tovaru spotrebiteľmi v množstve dostatočnom na uspokojenie potrieb spotrebiteľov. Označme množstvom prepravovaného tovaru z miesta A i ukázať b j .

Na uspokojenie požiadaviek spotrebiteľov je potrebné, aby hodnoty X ij splnil podmienky:

Zároveň zo skladu a; Nemôžete vyvážať viac potravín, ako je tam k dispozícii. To znamená, že požadované množstvá musia spĺňať systém nerovností:

Existuje nespočetné množstvo spôsobov, ako splniť podmienky (8.14), (8.15), teda vytvoriť dopravný plán, ktorý spĺňa požiadavky spotrebiteľov. Aby operačný výskumník vybral určité riešenie, teda zadal určité X ij, musí byť sformulované nejaké pravidlo výberu, určené pomocou kritéria, ktoré odráža našu subjektívnu predstavu o cieli.

Problém kritéria je riešený nezávisle od štúdie prevádzky - kritérium musí stanoviť operátor. V tomto probléme bude jedným z možných kritérií cena dopravy. Definuje sa takto:

Potom je problém dopravy formulovaný ako problém lineárneho programovania: určte veličiny vyhovujúce obmedzeniam (8.14), (8.15) a poskytujúce minimálnu hodnotu funkcii (8.16). Obmedzenie (8.15) je podmienka rovnováhy; podmienku (8.14) možno nazvať cieľom operácie, pretože zmyslom operácie je uspokojovanie potrieb spotrebiteľov.

Tieto dve podmienky v podstate tvoria model fungovania. Realizácia operácie bude závisieť od kritéria, podľa ktorého sa cieľ operácie dosiahne. Kritérium sa môže objaviť v rôznych rolách. Môže pôsobiť ako spôsob formalizácie cieľa aj ako princíp výberu akcií spomedzi tých, ktoré sú prípustné, teda takých, ktoré spĺňajú obmedzenia.

Jednou zo známych metód riešenia transportného problému je metóda potenciálov.

V prvej fáze riešenia problému sa vypracuje prvotný dopravný plán, ktorý vyhovuje

obmedzenia (8.14), (8.15). Ak (t. j. celkové potreby sa nezhodujú s celkovými zásobami výrobkov na skladoch), potom sa do úvahy zavedie fiktívne miesto spotreby alebo fiktívny sklad s nákladmi na dopravu rovnými nule. Pre novú úlohu sa celkový počet tovaru v skladoch zhoduje s jeho celkovým dopytom. Potom sa nejakým spôsobom (napríklad najmenší prvok alebo severozápadný roh) nájde pôvodný plán. V ďalšom kroku postupu výsledného plánu je zostrojený systém špeciálnych charakteristík - potenciálov. Nevyhnutnou a postačujúcou podmienkou optimálneho plánu je jeho potenciál. Postup na spresnenie plánu sa vykonáva, kým sa nestane potenciálnym (optimálnym).

Problém 3b. Vo všeobecnom prípade sa problém (8.10 – 8.11) nazýva problém nelineárneho programovania. Pozrime sa na to v akceptovanejšej forme:

za podmienok

Na vyriešenie tohto problému sa používajú takzvané relaxačné metódy. Proces vytvárania postupnosti bodov sa nazýva relaxácia, ak:

Spôsoby zostupu (všeobecná schéma). Všetky metódy zostupu na riešenie úlohy neobmedzenej optimalizácie (8.17) sa líšia buď výberom smeru zostupu alebo spôsobom pohybu pozdĺž smeru zostupu. Spôsoby zostupu pozostávajú z nasledujúceho postupu konštrukcie { X k }.

Ako počiatočná aproximácia sa vyberie ľubovoľný bod X 0 . Postupné aproximácie sú konštruované podľa nasledujúcej schémy:

Bod X k je zvolený smer zostupu - s k ;

Nájdite aproximáciu (k + 1) – e pomocou vzorca:

kde množstvo je zvolené ako akékoľvek číslo, ktoré spĺňa nerovnosť

kde číslo je ľubovoľné číslo kedy

Vo väčšine zostupových metód sa hodnota  k volí rovná jednotke. Na určenie  k je teda potrebné vyriešiť problém jednorozmernej minimalizácie.

Gradientná metóda zostupu. Keďže antigradient udáva smer najrýchlejšieho poklesu funkcie f(X), potom je prirodzené prejsť od bodu X k v tomto smere. Metóda zostupu, ktorá sa nazýva gradientová metóda zostupu. Ak, potom sa relaxačný proces nazýva metóda najstrmšieho zostupu.

Metóda konjugovaných smerov. V lineárnej algebre je táto metóda známa ako metóda konjugovaného gradientu na riešenie systémov lineárnych algebraických rovníc. AX=b, a teda ako metóda na minimalizáciu kvadratickej funkcie

Schéma metódy:

Ak = 0, potom sa tento okruh zmení na okruh metódy najstrmšieho zostupu. Vhodný výber hodnoty t k zaručuje konvergenciu metódy konjugovaného smeru rýchlosťou rovnakého rádu ako pri metódach gradientového zostupu a zabezpečuje, že počet iterácií v kvadratickom zostupe je konečný (napríklad).

Súradnicový zostup. Pri každej iterácii, ako smer zostupu - s k je zvolený smer pozdĺž jednej zo súradnicových osí. Metóda má mieru konvergencie procesu minimalizácie rádovo 0 (1/m). Navyše výrazne závisí od rozmeru priestoru.

Schéma metódy:

kde je súradnicový vektor

Ak v bode X k sú tam informácie o správaní sa gradientu funkcie f(X), Napríklad:

potom ako smer zostupu s k môžete vziať súradnicový vektor e j . V tomto prípade je rýchlosť konvergencie metódy n-krát menšia ako pri gradientovom klesaní.

Zapnuté počiatočná fáza minimalizačný proces, môžete použiť metódu cyklického súradnicového zostupu, keď sa zostup najskôr uskutoční v smere e 1 , potom pozdĺž e 2 atď až e P , potom sa celý cyklus znova opakuje. Sľubnejší ako predchádzajúci je zostup podľa súradníc, v ktorom sú smery zostupu vybrané náhodne. Pri tomto prístupe k výberu smeru existujú a priori odhady, ktoré zaručujú funkciu f(X) s pravdepodobnosť inklinujúca k jednote pri , proces konverguje rýchlosťou rádovo 0 (1/m).

Schéma metódy:

V každom kroku procesu sa náhodne vyberie číslo z n čísel (1, 2, ..., n) j(k) a ako s k je zvolený jednotkový súradnicový vektor e j ( k ) , po ktorom nasleduje zostup:

Metóda náhodného zostupu.s k, s rovnomerným rozložením na tejto guli a potom podľa prvku vypočítaného v k-tom kroku procesu X Komu definované:

Rýchlosť konvergencie pri metóde náhodného zostupu je n-krát nižšia ako pri metóde gradientového zostupu, ale n-krát vyššia ako pri metóde náhodného zostupu súradníc. Uvažované metódy zostupu sú použiteľné aj na funkcie, ktoré nie sú nevyhnutne konvexné a zaručujú ich konvergenciu pri veľmi malých obmedzeniach (ako je absencia lokálnych miním).

Relaxačné metódy matematického programovania. Vráťme sa k problému 36 ((8.17) – (8.18)):

za podmienok

Pri optimalizačných problémoch s obmedzeniami výber smeru zostupu zahŕňa potrebu neustáleho overovania novej hodnoty X k +1 by mala byť rovnaká ako predchádzajúca X k uspokojiť systém obmedzení X.

Metóda podmieneného gradientu. Pri tejto metóde je myšlienka výberu smeru zostupu nasledovná: v bode X Komu linearizovať funkciu f(X), zostrojenie lineárnej funkcie a následná minimalizácia f(X) na súprave X, nájsť bod r k . Potom predpokladajú a potom zostupujú týmto smerom, takže

Na nájdenie smeru – s k je teda potrebné vyriešiť problém minimalizácie lineárnej funkcie na množine X. Ak X je zase daný lineárnymi obmedzeniami, potom sa stáva problémom lineárneho programovania.

Metóda možných smerov. Myšlienka metódy: medzi všetkými možnými smermi v bode X Komu vyberte ten, pozdĺž ktorého funkcia f(X) klesá najrýchlejšie a potom klesá týmto smerom.

Smer - s v bode X X sa nazýva možné, ak existuje číslo také, že pre všetkých. Na nájdenie možného smeru je potrebné vyriešiť problém lineárneho programovania alebo najjednoduchší problém kvadratického programovania:

Za podmienok:

Nech je riešením tohto problému. Podmienka (8.25) zaručuje, že smer je možný. Podmienka (8.26) zabezpečuje maximálnu hodnotu (teda medzi všetkými možnými smermi – s, smer – poskytuje najrýchlejší pokles funkcie f(X). Podmienka (8.27) eliminuje neohraničenosť riešenia úlohy. Metóda možných smerov je odolná voči možným výpočtovým chybám. Mieru jeho konvergencie je však vo všeobecnom prípade ťažké odhadnúť a tento problém zostáva nevyriešený.

Metóda náhodného vyhľadávania. Implementácia vyššie uvedených metód minimalizácie je vo všeobecnosti veľmi náročná na prácu, s výnimkou najjednoduchších prípadov, keď má množina obmedzení jednoduchú geometrickú štruktúru (napríklad ide o viacrozmerný hranol). Vo všeobecnosti môže byť metóda náhodného vyhľadávania, keď je smer zostupu zvolený náhodne, veľmi sľubná. V tomto prípade výrazne stratíme v rýchlosti konvergencie, ale jednoduchosť výberu smeru môže tieto straty kompenzovať z hľadiska celkových nákladov práce na riešenie problému minimalizácie.

Schéma metódy:

Na n-rozmernej jednotkovej gule so stredom v počiatku sa vyberie náhodný bod r k, ktorá sa riadi rovnomerným rozložením na tejto guli a potom je smer zostupu s k z podmienok,

Ako počiatočná aproximácia sa zvolí . Na základe bodu vypočítaného pri každej iterácii X k vo výstavbe ( k+ 1) bod X k +1 :

Akékoľvek číslo z =, ktoré spĺňa nerovnosť, sa vyberie ako kvalita:

Konvergencia tejto metódy je preukázaná pri veľmi voľných obmedzeniach funkcie f (konvexnosť) a mnohé obmedzenia X (konvexnosť a uzavretie).

Problém 1. Nájsť

kde x = (x 1 .. x p) e E p

Tento problém sa týka riešenia sústavy rovníc

a študujte hodnotu druhého diferenciálu

v bodoch (a-|, (*2, a n) riešenia rovníc (7.3).

Ak je kvadratická forma (7.4) v určitom bode záporne definitná, potom dosiahne svoju maximálnu hodnotu a ak je pozitívne definitná, potom dosiahne svoju minimálnu hodnotu.

Príklad:

Systém rovníc má riešenia:

Bod (-1; 3.0) je maximálny bod a bod (1; 3.2) je minimálny bod.

Úloha 2. Nájdite

za podmienok:

Tento problém 2 je riešený metódou Lagrangeovho multiplikátora, pre ktorú sa nájde riešenie systému (t + p) rovnice:

Príklad 2 Nájdite strany obdĺžnika s maximálnou plochou vpísanou do kruhu Oblasť L obdĺžnika

možno napísať ako: A= 4xy teda

kde

Úloha 3. Nájdite za podmienok:

Tento problém pokrýva široký rozsah nastavení určených funkciami f a St Ak sú lineárne, potom je problémom problém lineárneho programovania.

Úloha pre.

za podmienok

Rieši sa simplexovou metódou, ktorá pomocou aparátu lineárnej algebry cielene vyhľadáva vrcholy mnohostenu definovaného (7.13).

Simplexná metóda pozostáva z dvoch etáp.

Etapa 1. Nájdenie referenčného roztoku x^ 0). Referenčným roztokom je jeden z bodov mnohostenu (7.13).

Fáza 2. Nájdenie optimálneho riešenia. Zisťuje sa postupným vyčíslením vrcholov mnohostenu (7.13), v ktorom hodnota účelovej funkcie z v každom kroku neklesá, to znamená:

Špeciálnym prípadom problému lineárneho programovania je takzvaný transportný problém.

Problém s dopravou. Nech v bodoch a-1, a 2, .... a l sú sklady, v ktorých sa skladuje tovar v množstvách x 1, x 2, ..., x l, resp. V bodoch b-|, b 2,..., b t sú spotrebitelia, ktorí potrebujú dodať tento tovar v množstvách y- r 2, r t resp. Označme Cjj náklady na prepravu jednotky nákladu medzi bodmi a-| a podľa.

Skúmame fungovanie prepravy tovaru spotrebiteľmi v množstve dostatočnom na uspokojenie potrieb klientely. Označme podľa Hu množstvo tovaru prepraveného z bodu a do bodu o.

Na uspokojenie potrieb spotrebiteľov je potrebné, aby hodnoty x, y spĺňali podmienky:

Zároveň nie je možné vyviezť zo skladu viac produktov, ako je tam k dispozícii. To znamená, že požadované množstvá musia spĺňať systém nerovností:

Splniť podmienky (7,14), (7,15), t.j. Existuje nespočetné množstvo spôsobov, ako vytvoriť dopravný plán, ktorý spĺňa potreby spotrebiteľov. Aby operačný výskumník vybral určité optimálne riešenie, t.j. priradiť isté xjj, musí byť formulované nejaké pravidlo výberu, určené pomocou kritéria, ktoré odráža našu subjektívnu predstavu o cieli.

Problém kritéria je riešený nezávisle od štúdie prevádzky - kritérium musí stanoviť operátor. V uvažovanom probléme budú jedným z možných kritérií náklady na dopravu. To predstavuje

Potom je problém dopravy formulovaný ako problém lineárneho programovania: určte hodnoty x,y > O, ktoré spĺňajú obmedzenia (7.14), (7.15) a poskytnite minimálnu hodnotu funkcii (7.16). Obmedzenie (7.15) je stav rovnováhy; podmienku (7.14) možno nazvať cieľom operácie, pretože zmyslom operácie je uspokojovanie potrieb spotrebiteľov.

Zadanie dvoch podmienok v podstate predstavuje model operácie. Realizácia operácie bude závisieť od kritéria, podľa ktorého sa cieľ operácie dosiahne. Kritérium sa môže objaviť v rôznych rolách. Môže pôsobiť jednak ako spôsob formalizácie cieľa, jednak ako princíp výberu akcií spomedzi tých, ktoré sú prípustné, t. splnenie obmedzení.

Jednou zo známych metód riešenia dopravného problému je potenciálna metóda, ktorej schéma je nasledovná.

V prvej fáze riešenia problému sa vypracuje počiatočný dopravný plán, ktorý spĺňa obmedzenia (7.14), (7.15). Ak

(t.j. celkové potreby sa nezhodujú s celkovými zásobami výrobkov v skladoch), potom sa do úvahy zavedie fiktívne miesto spotreby alebo fiktívny sklad

s nákladmi na dopravu rovnými nule. Pre novú úlohu sa celkový počet tovaru v skladoch zhoduje s jeho celkovým dopytom. Potom sa nejakou metódou (napríklad najmenší prvok alebo severozápadný roh) nájde pôvodný plán. V ďalšom kroku postupy výsledného plánu budujú systém špeciálnych charakteristík - potenciálov. Nevyhnutnou a postačujúcou podmienkou optimálneho plánu je jeho potenciál. Postup upresňovania plánu sa opakuje, kým sa plán nestane potenciálnym (optimálnym).

Úloha 36. Vo všeobecnom prípade sa problém (7.10-7.11) nazýva problém nelineárneho programovania. Zvážme to vo forme

za podmienok

Na vyriešenie tohto problému sa používajú takzvané relaxačné metódy. Proces vytvárania postupnosti bodov sa nazýva relaxácia, ak:

Spôsoby zostupu (všeobecná schéma). Všetky spôsoby zostupu pri riešení úlohy neobmedzenej optimalizácie (7.17) sa líšia buď výberom smeru zostupu alebo spôsobom pohybu pozdĺž smeru zostupu. Spôsoby zostupu pozostávajú z nasledujúceho postupu konštrukcie (x k).

Ako počiatočná aproximácia je zvolený ľubovoľný bod Xq. Postupné aproximácie sú konštruované podľa nasledujúcej schémy:

bod x k je zvolený smer zostupu - S k;
Nájsť (Komu+ 1) aproximácia podľa vzorca

kde ako množstvo tis vyberte ľubovoľné číslo, ktoré spĺňa nerovnosť

kde je číslo X k -ľubovoľné číslo také, že 0 X k min f(x k - $ Sk).

Vo väčšine metód zostupu je hodnota X k je zvolený rovný jednej. Na určenie (3^ je teda potrebné vyriešiť problém jednorozmernej minimalizácie.

Gradientná metóda zostupu. Keďže antigradient je G(x k) udáva smer najrýchlejšieho poklesu funkcie f(x), potom je prirodzené prejsť od bodu x podľa týmto smerom. Spôsob zostupu, pri ktorom S k = f" (x k) nazývaná metóda gradientového zostupu. Ak X k= 1, potom sa relaxačný proces nazýva metóda najstrmšieho zostupu.

Metóda konjugovaných smerov. IN V lineárnej algebre je táto metóda známa ako metóda konjugovaného gradientu na riešenie systémov lineárnych algebraických rovníc. OH= b, a teda ako metóda na minimalizáciu kvadratickej funkcie f(x) =((Dx - b)) 2.

Schéma metódy:

Ak f k = 0, potom sa tento okruh zmení na okruh metódou najstrmšieho zostupu. Vhodný výber hodnoty tk zaručuje konvergenciu metódy konjugovaného smeru rýchlosťou rovnakého rádu ako pri metódach gradientového zostupu a zabezpečuje, že počet iterácií v kvadratickom zostupe je konečný (napr.

Súradnicový zostup. Pri každej iterácii ako smer zostupu S k je zvolený smer pozdĺž jednej zo súradnicových osí. Metóda má mieru konvergencie procesu minimalizácie rádovo 0 (1 //77) a výrazne závisí od rozmeru priestoru.

Schéma metódy:

Kde súradnicový vektor,

Ak v bode x k sú tam informácie o správaní sa gradientu funkcie f(x), Napríklad,

potom ako smer zostupu S k môžeme vziať súradnicový vektor ey. V tomto prípade je miera konvergencie metódy P krát menej ako pri gradientovom klesaní.

V počiatočnom štádiu procesu minimalizácie môžete použiť metódu cyklického zostupu súradnice po súradnici, keď sa najprv zostup uskutoční v smere e-|, potom v smere b2 atď. až do e p, po ktorom sa celý cyklus opakuje. Sľubnejší ako ten opísaný je zostup po súradnici, pri ktorom sú smery zostupu vybrané náhodne. Pri tomto prístupe k výberu smeru existujú a priori odhady, ktoré zaručujú funkciu f(x) s pravdepodobnosťou smerujúcou k jednote, keď proces konverguje rýchlosťou rádovo 0 (1 1t).

Schéma metódy:

V každom kroku procesu Pčísla (1, 2, ..., P) je náhodne vybrané číslo j(k) a ako s k je vybraný jednotkový súradnicový vektor vsch, po ktorom nasleduje zostup:

Metóda náhodného zostupu. Na n-rozmernej jednotkovej gule so stredom v počiatku sa vyberie náhodný bod S k , dodržiavať rovnomerné rozloženie na tejto sfére a potom podľa výpočtu na / krok procesný prvok x k určený x k+] :

Miera konvergencie metódy náhodného zostupu v P krát menej ako metóda gradientového zostupu, ale P krát väčšia ako pri metóde náhodného zostupu súradníc. Uvažované metódy zostupu sú použiteľné aj na funkcie, ktoré nie sú nevyhnutne konvexné a zaručujú ich konvergenciu pri veľmi malých obmedzeniach (ako je absencia lokálnych miním).

Relaxačné metódy matematického programovania. Vráťme sa k problému 36 ((7.17) - (7.18)):

za podmienok

Pri optimalizačných problémoch s obmedzeniami výber smeru zostupu zahŕňa potrebu neustáleho overovania novej hodnoty x k +" by mala byť rovnaká ako predchádzajúca x k, spĺňať systém obmedzení X.

Metóda podmieneného gradientu. IN Pri tejto metóde je myšlienka výberu smeru zostupu nasledovná: v bode x k linearizovať funkciu

f(x), zostrojenie lineárnej funkcie f(x) = f(x k) + (y"(x k), x-x k), a potom minimalizovanie f(x) na súprave X, nájsť bod pri k. Potom veria S k = y k - x k a potom zostup týmto smerom Xk+ 1= x k - $ k (x k -y k), takže g X.

Teda nájsť smer S k mal by sa vyriešiť problém minimalizácie lineárnej funkcie na množine X. Ak je X, naopak, špecifikované lineárnymi obmedzeniami, stáva sa to problém lineárneho programovania.

Metóda možných smerov. Myšlienka metódy: spomedzi všetkých možných smerov v bode xk vyberte ten, v ktorom je funkcia f(x) klesá najrýchlejšie a potom klesá týmto smerom.

Smer s v bode X e X sa nazýva možný_ak existuje také číslo (3 > O, že X- (3 s e X pre všetkých (3 g. Na nájdenie možného smeru je potrebné vyriešiť úlohu lineárneho programovania alebo najjednoduchšiu úlohu kvadratického programovania: hej?=>min za podmienok

Nechaj d k A s k- riešenie tohto problému. Podmienka (7.25) zaručuje, že smer s k možné. Podmienka (7.26) zabezpečuje maximálnu hodnotu (/"( x k), s), tie. medzi všetkými možnými smermi s, smer s k poskytuje funkciu najrýchlejšieho znižovania f(x). Podmienka (7.27) eliminuje neohraničenosť riešenia úlohy. Metóda možných smerov je odolná voči možným výpočtovým chybám. Mieru jeho konvergencie je však vo všeobecnom prípade ťažké odhadnúť a tento problém zostáva nevyriešený.

Metóda náhodného vyhľadávania. Implementácia vyššie popísaných minimalizačných metód je vo všeobecnosti veľmi náročná na prácu, s výnimkou najjednoduchších prípadov, keď má množina obmedzení jednoduchú geometrickú štruktúru (napríklad ide o viacrozmerný hranol). Vo všeobecnosti môže byť metóda náhodného vyhľadávania, keď je smer zostupu zvolený náhodne, veľmi sľubná. V tomto prípade dôjde k výraznej strate rýchlosti konvergencie, ale jednoduchosť výberu smeru môže kompenzovať tieto straty z hľadiska celkových nákladov práce na riešenie problému minimalizácie.

Schéma metódy:

na n-rozmernej jednotkovej gule so stredom v počiatku sa vyberie náhodný bod gu podlieha rovnomernému rozloženiu na tejto sfére a potom smer zostupu - s^ z podmienok

Ako počiatočnú aproximáciu volíme xc e X. Na základe bodu vypočítaného pri každej iterácii X? vo výstavbe (k + 1) bod x^+ y:

Akékoľvek číslo od uspokojujúca nerovnosť

Konvergencia tejto metódy je dokázaná pri veľmi nerigidných obmedzeniach funkcie / (konvexita) a súboru obmedzení X(konvexnosť a uzavretie).

Medzi optimalizačné metódy nultého rádu V CAD sa používajú metódy Rosenbrock, konfigurácia, deformovateľný mnohosten a náhodné vyhľadávanie. Metódy využívajúce deriváty zahŕňajú najstrmší zostup, konjugovaný gradient a metódy s premenlivou metrikou.

Rosenbrockova metóda je vylepšená verzia súradnicového zostupu.

Súradnicová metóda zostupu sa vyznačuje výberom smerov hľadania striedavo pozdĺž všetkých súradnicových osí, krok je vypočítaný na základe jednorozmernej optimalizácie, kritériom pre ukončenie hľadania je , kde je zadaná presnosť určenia lokálneho extrému, je rozmer priestor kontrolovaných parametrov. Trajektória zostupu súradníc pre príklad dvojrozmerného priestoru riadených parametrov je znázornená na obr. 1, kde sú body na trajektórii vyhľadávania a sú kontrolované parametre. Cieľová funkcia je reprezentovaná jej riadkami rovnakých úrovní a zodpovedajúca hodnota je napísaná vedľa každého riadku. Je zrejmé, že existuje minimálny bod.

Ryža. 1. Trajektória zostupu súradníc

Pri použití metódy súradnicového zostupu je vysoká pravdepodobnosť, že hľadanie uviazne na dne rokliny ďaleko od extrémneho bodu. Na obr. 2 ukazuje, že po zasiahnutí bodu nachádzajúceho sa na dne rokliny sú možné ďalšie kroky len v smeroch alebo , ale vedú k zhoršeniu účelovej funkcie. Preto sa vyhľadávanie zastaví v bode .

Poznámka 1

Roklina je časť priestoru riadených parametrov, v ktorej sú v niektorých smeroch pozorované slabé zmeny v deriváciách účelovej funkcie a v niektorých iných smeroch výrazné zmeny so zmenou znamienka. Znamienko derivácie sa mení v bodoch patriacich dnu rokliny.

Ryža. 3. Trajektória zostupu súradníc s výhodnou orientáciou súradnicových osí

Rosenbrockova metóda spočíva v otáčaní súradnicových osí tak, aby sa jedna z nich ukázala ako kvázi rovnobežná s dnom rokliny. Toto otáčanie sa vykonáva na základe údajov získaných po sérii krokov zostupu súradníc. Polohu nových osí je možné získať lineárnou transformáciou predchádzajúcich osí: os sa zhoduje v smere s vektorom; zostávajúce osi sú zvolené z podmienky ortogonality k sebe a k sebe navzájom.

Ďalšou úspešnou modifikáciou súradnicového zostupu je metóda konfigurácie(Hook-Jeeves). V súlade s touto metódou sa najskôr vykonajú obvyklé série krokov súradnicového zostupu, potom sa vykoná ďalší krok v smere vektora, ako je znázornené na obr. 4, kde sa vykoná ďalší krok v smere vektora, ktorý vedie k bodu .

Ryža. 4. Ilustrácia spôsobu konfigurácie

Hľadajte extrém metóda deformovateľného mnohostenu(Nelder-Mead) je založený na konštrukcii mnohostenu s vrcholmi v každom kroku vyhľadávania, kde je rozmer priestoru kontrolovaných parametrov. Na začiatku vyhľadávania sa tieto vrcholy vyberú náhodne, v ďalších krokoch už výber podlieha pravidlám metódy.

Tieto pravidlá sú vysvetlené na obr. 5 na príklade úlohy dvojrozmernej optimalizácie. Vyberú sa vrcholy pôvodného trojuholníka: , , . Nový vrchol sa nachádza na lúči nakreslenom z najhoršieho vrcholu (z vrcholu s najvyššia hodnota objektívna funkcia) cez ťažisko mnohostenu a odporúča sa zvoliť vzdialenosť od rovnej . Nový vrchol nahradí najhorší vrchol. Ak sa ukáže, že má najlepšia hodnota objektívna funkcia medzi vrcholmi mnohostenu, potom sa vzdialenosť zväčší. Na obrázku je presne táto situácia, ktorá nastáva a zvýšenie dáva pointu. V novom mnohostene s vrcholmi , , je najhorší vertex , podobne sa dostane vertex , potom vertex , atď. Ak nový vrchol dopadne horšie, potom treba zachovať najlepší vrchol v mnohostene a dĺžky všetkých hrán zmenšiť napríklad na polovicu (stiahnutím mnohostenu na najlepší vrchol). Vyhľadávanie sa zastaví, keď je splnená podmienka zmenšenia veľkosti mnohostenu na určitú hranicu.

optimálny krok sa vyberie pomocou jednorozmernej optimalizácie.

Pri použití metódy najstrmšieho zostupu, podobne ako pri väčšine iných metód, je účinnosť vyhľadávania v situáciách žľabu výrazne znížená. Trajektória hľadania nadobúda cikcakovitý tvar s pomalým pohybom pozdĺž dna rokliny smerom ku extrému. Na zvýšenie účinnosti gradientových metód sa používa niekoľko techník.

Jedna z techník používaných v metóda konjugovaného gradientu(nazývaná aj metóda Fletcher-Reeves), je založená na koncepte konjugácie vektorov. Vektory a sa nazývajú -konjugované, ak , kde je kladná definitná štvorcová matica rovnakého rádu ako veľkosť vektorov a (špeciálnym prípadom konjugácie je ortogonalita vektorov, kedy je matica identity rádu ), je riadok vektor, je stĺpcový vektor.

Zvláštnosť konjugovaných smerov pre , kde je Hessova matica, v problémoch s kvadratickou objektívnou funkciou je nasledovná: jednorozmerná minimalizácia sekvenčne pozdĺž konjugovaných smerov umožňuje nájsť extrémny bod maximálne v krokoch.

Poznámka 2

Hessova matica je matica druhých parciálnych derivácií cieľovej funkcie vzhľadom na riadené parametre.

Dôvodom použitia -konjugovaného vyhľadávania je to, že pre funkcie () všeobecný pohľad Môže sa použiť kvadratická aproximácia, čo v praxi vedie k tomu, že vyhľadávanie sa vykonáva vo viac ako krokoch.

Hľadanie extrému sa vykonáva podľa vzorca

kde je koeficient. Okrem toho sa berie do úvahy stav konjugácie

Keďže krok je vypočítaný na základe podmienky jednorozmernej optimalizácie, potom v prvom rade platí nasledujúci vzťah:

Algoritmus vyhľadávania sa redukuje na použitie vzorca (3), kým nie je splnená podmienka na dokončenie výpočtov

Na určenie koeficientu vyriešte sústavu rovníc (2)-(7) dosadením do (4) hodnôt z (3) a z (2):

alebo

kde

a berúc do úvahy (6) a (7)

Výraz (10) je sústava lineárnych algebraických rovníc. Jeho koreň je ďalším priblížením k riešeniu

Ak proces konverguje, potom sa riešenie dosiahne v malom počte iterácií, ktorých koncom je splnenie podmienky
Kde

Preto

Dá sa ukázať, že smeruje k , - do kedy , kde je rozmer priestoru kontrolovaných parametrov. Po vykonaní krokov musíte začať znova od .

Za optimálnu sa považuje najprijateľnejšia možnosť rozhodovania, ktorá sa robí na manažérskej úrovni v súvislosti s akoukoľvek otázkou, a proces jej hľadania sa považuje za optimalizáciu.

Vzájomná závislosť a zložitosť organizačných, sociálno-ekonomických, technických a iných aspektov riadenia výroby v súčasnosti spočíva v prijímaní manažérskych rozhodnutí, ktoré ovplyvňujú veľké množstvo rôzne druhy faktorov, ktoré sú navzájom úzko prepojené, v dôsledku čoho nie je možné analyzovať každý zvlášť pomocou tradičných analytických metód.

Väčšina faktorov je v rozhodovacom procese rozhodujúca a nie je možné ich (vo svojej podstate) kvantifikovať. Sú aj také, ktoré sú prakticky nezmenené. V tejto súvislosti bolo potrebné vyvinúť špeciálne metódy, ktoré by mohli zabezpečiť výber dôležitých manažérske rozhodnutia v rámci zložitých organizačných, ekonomických, technických problémov (odborné posudky, operačný výskum a optimalizačné metódy a pod.).

Metódy zamerané na operačný výskum sa využívajú pri hľadaní optimálnych riešení v takých oblastiach riadenia, ako je organizovanie výrobných a dopravných procesov, plánovanie veľkovýroby, materiálové a technické zásobovanie.

Metódy na optimalizáciu riešení zahŕňajú výskum porovnávaním numerických odhadov množstva faktorov, ktorých analýza tradičné metódy nemožné realizovať. Optimálne riešenie je najlepšie spomedzi možných variantov ekonomického systému a najprijateľnejšie vo vzťahu k jednotlivým prvkom systému je suboptimálne.

Podstata metód operačného výskumu

Ako už bolo spomenuté, tvoria metódy na optimalizáciu manažérskych rozhodnutí. Ich základom sú matematické (deterministické), pravdepodobnostné modely reprezentujúce skúmaný proces, typ činnosti alebo systému. Tento druh modely poskytujú kvantitatívny popis príslušného problému. Slúžia ako základ pre prijímanie dôležitých manažérskych rozhodnutí v procese hľadania optimálnej možnosti.

Zoznam problémov, ktoré zohrávajú významnú úlohu pre priamych výrobných manažérov a ktoré sa riešia počas používania uvažovaných metód:

stupeň platnosti zvolených možností rozhodnutia;
o koľko sú lepšie ako alternatívy;
stupeň zohľadnenia určujúcich faktorov;
aké je kritérium pre optimálnosť vybraných riešení.

Tieto metódy optimalizácie rozhodovania (manažérske) sú zamerané na nájdenie optimálnych riešení pre čo najviac firiem, spoločností alebo ich divízií. Sú založené na doterajších úspechoch v štatistických, matematických a ekonomických disciplínach (teória hier, radenie, grafika, optimálne programovanie, matematická štatistika).

Odborné metódy posudzovania

Tieto metódy na optimalizáciu manažérskych rozhodnutí sa používajú vtedy, keď problém čiastočne alebo úplne nepodlieha formalizácii a jeho riešenie nie je možné nájsť pomocou matematických metód.

Odbornosť je štúdium zložitých špeciálnych problémov v štádiu vývoja špecifického manažérskeho rozhodnutia príslušnými osobami, ktoré majú špeciálnu vedomostnú základňu a pôsobivé skúsenosti s cieľom získať závery, odporúčania, názory a hodnotenia. V procese expertného výskumu využívajú najnovšie úspechy a vedu a techniku v rámci špecializácie odborníka.

Uvažované metódy na optimalizáciu množstva manažérskych rozhodnutí (odborných posudkov) sú účinné pri riešení nasledujúcich úloh riadenia v oblasti výroby:

Štúdium zložitých procesov, javov, situácií, systémov, ktoré sa vyznačujú neformálnymi, kvalitatívnymi charakteristikami.
Zoradenie a určenie, podľa daného kritéria, významných faktorov, ktoré sú rozhodujúce pre fungovanie a rozvoj výrobného systému.
Uvažované optimalizačné metódy sú obzvlášť účinné pri predpovedaní trendov vo vývoji výrobného systému, ako aj jeho interakcie s vonkajším prostredím.
Zvýšenie spoľahlivosti odborného hodnotenia najmä cieľových funkcií, ktoré majú kvantitatívny a kvalitatívny charakter, spriemerovaním názorov kvalifikovaných odborníkov.

A to sú len niektoré metódy na optimalizáciu množstva manažérskych rozhodnutí (odborné posúdenie).

Klasifikácia posudzovaných metód

Metódy riešenia optimalizačných problémov na základe počtu parametrov možno rozdeliť na:

Metódy jednorozmernej optimalizácie.
Metódy viacrozmernej optimalizácie.

Nazývajú sa aj „metódy numerickej optimalizácie“. Presnejšie povedané, ide o algoritmy na jeho vyhľadávanie.

V rámci používania derivátov ide o tieto metódy:

metódy priamej optimalizácie (nultého rádu);
gradientové metódy (1. rád);
metódy 2. rádu atď.

Väčšina metód viacrozmernej optimalizácie má blízko k problému druhej skupiny metód (jednorozmerná optimalizácia).

Metódy jednorozmernej optimalizácie

Akékoľvek numerické optimalizačné metódy sú založené na približnom alebo presnom výpočte takých charakteristík, ako sú hodnoty cieľovej funkcie a funkcie, ktoré definujú prípustnú množinu a ich deriváty. Pre každú jednotlivú úlohu teda možno otázku týkajúcu sa výberu charakteristík pre výpočet vyriešiť v závislosti od existujúcich vlastností uvažovanej funkcie, dostupných možností a obmedzení pri ukladaní a spracovaní informácií.

Existujú nasledujúce metódy riešenia optimalizačných problémov (jednorozmerné):

Fibonacciho metóda;
dichotómie;
Zlatý pomer;
zdvojnásobenie kroku.

Fibonacciho metóda

Najprv musíte nastaviť súradnice bodu x na intervale ako číslo, ktoré sa rovná pomeru rozdielu (x - a) k rozdielu (b - a). Preto má a súradnicu 0 vzhľadom na interval a b má súradnicu 1 a stred je ½.

Ak predpokladáme, že F0 a F1 sa navzájom rovnajú a získame hodnotu 1, F2 sa bude rovnať 2, F3 - 3, ..., potom Fn = Fn-1 + Fn-2. Takže Fn sú Fibonacciho čísla a Fibonacciho vyhľadávanie je optimálnou stratégiou pre takzvané sekvenčné hľadanie maxima, pretože s nimi dosť úzko súvisí.

V rámci optimálnej stratégie je zvykom voliť xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. Pre ktorýkoľvek z dvoch intervalov (alebo), z ktorých každý môže pôsobiť ako zúžený interval neistoty, bude mať bod (zdedený) vzhľadom na nový interval buď súradnice , alebo . Ďalej sa berie bod ako xn - 2, ktorý má jednu z prezentovaných súradníc vzhľadom na nový interval. Ak použijete F(xn - 2), funkčnú hodnotu, ktorá je zdedená z predchádzajúceho intervalu, bude možné znížiť interval neistoty a zdediť jednu funkčnú hodnotu.

V poslednom kroku bude možné prejsť na interval neistoty, ako napríklad , pričom stredný bod sa zdedí z predchádzajúceho kroku. Ako x1 je nastavený bod, ktorý má relatívnu súradnicu ½+ε a konečný interval neistoty bude alebo [½, 1] vzhľadom na .

V 1. kroku sa dĺžka tohto intervalu skrátila na Fn-1: Fn (z jednej). Pri dokončovacích krokoch je zmenšenie dĺžok zodpovedajúcich intervalov reprezentované číslami Fn-2: Fn-1, Fn-3: Fn-2, ..., F2: F3, F1: F2 (1 + 2ε ). Takže dĺžka takého intervalu ako finálna verzia bude mať hodnotu (1 + 2ε) : Fn.

Ak zanedbáme ε, potom asymptoticky 1: Fn sa bude rovnať rn s n→∞ a r = (√5 - 1) : 2, čo sa približne rovná 0,6180.

Stojí za zmienku, že asymptoticky pre významné n každý nasledujúci krok Fibonacciho vyhľadávania výrazne zužuje uvažovaný interval o vyššie uvedený koeficient. Tento výsledok je potrebné porovnať s 0,5 (koeficient zúženia intervalu neistoty v rámci bisekčnej metódy na nájdenie nuly funkcie).

Metóda dichotómie

Ak si predstavíte určitú účelovú funkciu, musíte najskôr nájsť jej extrém na intervale (a; b). Na tento účel je úsečka rozdelená na štyri ekvivalentné časti, potom je potrebné určiť hodnotu príslušnej funkcie v 5 bodoch. Ďalej sa z nich vyberie minimum. Extrém funkcie musí ležať v intervale (a"; b"), ktorý susedí s minimálnym bodom. Hranice vyhľadávania sa zúžia 2-krát. A ak sa minimum nachádza v bode a alebo b, potom sa zužuje o všetky štyri krát. Nový interval je tiež rozdelený na štyri rovnaké segmenty. Vzhľadom na to, že hodnoty tejto funkcie v troch bodoch boli určené v predchádzajúcej fáze, je potom potrebné vypočítať cieľovú funkciu v dvoch bodoch.

Metóda zlatého pomeru

Pre významné hodnoty n sú súradnice bodov ako xn a xn-1 blízke 1 - r, rovné 0,3820 a r ≈ 0,6180. Posun z týchto hodnôt je veľmi blízko požadovanej optimálnej stratégii.

Ak predpokladáme, že F(0,3820) > F(0,6180), potom je interval načrtnutý. Avšak vzhľadom na skutočnosť, že 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, potom F je už v tomto bode známa. V dôsledku toho je v každej fáze, počnúc od 2., potrebný iba jeden výpočet účelovej funkcie a každý krok skracuje dĺžku uvažovaného intervalu faktorom 0,6180.

Na rozdiel od Fibonacciho vyhľadávania, v túto metódu nie je potrebné opraviť číslo n pred začatím vyhľadávania.

„Zlatý rez“ úseku (a; b) je úsek, pri ktorom je pomer jeho dĺžky r k väčšej časti (a; c) zhodný s pomerom väčšej časti r k menšej, tj. (a; c) až (c; b). Nie je ťažké uhádnuť, že r je určené vyššie uvedeným vzorcom. V dôsledku toho pre významné n ide do tohto Fibonacciho metóda.

Metóda zdvojenia krokov

Podstatou je hľadať smer poklesu účelovej funkcie, nasťahovať sa v tomto smere v prípade úspešného hľadania s postupne sa zvyšujúcim krokom.

Najprv určíme počiatočnú súradnicu M0 funkcie F(M), minimálnu hodnotu kroku h0 a smer hľadania. Potom definujeme funkciu v bode M0. Ďalej urobíme krok a zistíme hodnotu tejto funkcie v tomto bode.

Ak je funkcia menšia ako hodnota, ktorá bola v predchádzajúcom kroku, ďalší krok by sa mal vykonať v rovnakom smere, pričom sa najskôr dvakrát zvýši. Ak je jeho hodnota väčšia ako predchádzajúca, budete musieť zmeniť smer vyhľadávania a potom sa začať pohybovať vo zvolenom smere s krokmi h0. Prezentovaný algoritmus je možné upraviť.

Metódy viacrozmernej optimalizácie

Vyššie uvedená metóda nultého rádu neberie do úvahy derivácie minimalizovanej funkcie, preto môže byť ich použitie efektívne, ak sa vyskytnú nejaké ťažkosti pri výpočte derivácií.

Skupina metód 1. rádu sa nazýva aj gradientové metódy, pretože na stanovenie smeru hľadania sa používa gradient danej funkcie - vektor, ktorého zložky sú parciálne derivácie minimalizovanej funkcie vzhľadom na zodpovedajúce optimalizované parametre. .

V skupine metód 2. rádu sú použité 2 deriváty (ich použitie je značne obmedzené pre ťažkosti pri ich výpočte).

Zoznam neobmedzených optimalizačných metód

Pri použití viacrozmerného vyhľadávania bez použitia derivátov sú neobmedzené metódy optimalizácie nasledovné:

Hook a Jeeves (vykonávajú 2 typy vyhľadávania - na základe vzoru a prieskumné);
minimalizácia správnym simplexom (hľadanie minimálneho bodu zodpovedajúcej funkcie porovnaním jej hodnôt vo vrcholoch simplexu pri každej jednotlivej iterácii);
cyklický súradnicový zostup (použitie súradnicových vektorov ako referenčných bodov);
Rosenbrock (založený na použití jednorozmernej minimalizácie);
minimalizácia pomocou deformovaného simplexu (úprava minimalizačnej metódy pomocou bežného simplexu: pridanie postupu kompresie a naťahovania).

V situácii použitia derivácií v procese viacrozmerného hľadania sa rozlišuje metóda najstrmšieho zostupu (najzákladnejší postup minimalizácie diferencovateľnej funkcie s viacerými premennými).

Existujú aj iné metódy, ktoré využívajú konjugované smery (Davidon-Fletcher-Powell metóda). Jeho podstatou je znázornenie smerov vyhľadávania ako Dj*grad(f(y)).

Klasifikácia matematických optimalizačných metód

Konvenčne, na základe dimenzie funkcií (cieľ), sú to:

s 1 premennou;
viacrozmerný.

V závislosti od funkcie (lineárnej alebo nelineárnej) existuje veľké množstvo matematických metód zameraných na nájdenie extrému na vyriešenie problému.

Na základe kritéria použitia derivátov sa metódy matematickej optimalizácie delia na:

metódy na výpočet 1 derivácie účelovej funkcie;
viacrozmerný (1. derivácia-vektorová veličina-gradient).

Na základe efektívnosti výpočtu existujú:

metódy rýchleho výpočtu extrému;
zjednodušený výpočet.

Toto je podmienená klasifikácia posudzovaných metód.

Optimalizácia obchodných procesov

Tu je možné použiť rôzne metódy v závislosti od riešených problémov. Na optimalizáciu obchodných procesov je obvyklé rozlišovať nasledujúce metódy:

výnimky (zníženie úrovní existujúceho procesu, odstránenie príčin rušenia a vstupnej kontroly, redukcia prepravných ciest);
zjednodušenie (uľahčené spracovanie objednávok, znížená zložitosť štruktúry produktu, rozloženie práce);
štandardizácia (použitie špeciálne programy metódy, technológie atď.);
akcelerácia (paralelné inžinierstvo, stimulácia, prevádzkový návrh prototypov, automatizácia);
zmena (zmeny surovín, technológie, pracovných metód, personálneho obsadenia, pracovných systémov, objemu zákaziek, postupov spracovania);
zabezpečenie interakcie (vo vzťahu k organizačným útvarom, personálu, systému práce);
výber a zaradenie (vo vzťahu k potrebným procesom, komponentom).

Daňová optimalizácia: metódy

Ruská legislatíva poskytuje daňovníkovi veľmi bohaté možnosti zníženia daní, preto je zvykom takéto metódy zamerané na ich minimalizáciu rozlišovať na všeobecné (klasické) a špeciálne.

Všeobecné metódy daňovej optimalizácie sú nasledovné:

vypracovanie účtovných zásad spoločnosti s max možná aplikácia poskytnuté Ruská legislatíva možnosti (postup pri odpise IPP, výber spôsobu výpočtu tržieb z predaja tovaru a pod.);
optimalizácia prostredníctvom zmluvy (uzatvorenie preferenčných obchodov, jasné a kompetentné používanie formulácií atď.);
uplatňovanie rôznych druhov výhod a daňových výnimiek.

Druhú skupinu metód môžu využívať aj všetky spoločnosti, no stále majú pomerne úzky rozsah použitia. Špeciálne metódy daňovej optimalizácie sú nasledovné:

nahradenie vzťahov (operácia, ktorá zahŕňa zaťažujúce zdanenie, je nahradená inou, ktorá umožňuje dosiahnuť podobný cieľ, ale zároveň využiť zvýhodnené daňové zaobchádzanie).
rozdelenie vzťahov (nahradenie len časti obchodnej transakcie);
odklad platenia dane (posunutie momentu vzniku zdaniteľného predmetu na iné kalendárne obdobie);
priame zníženie predmetu zdanenia (zbavenie sa mnohých zdaniteľných obchodov alebo majetku bez negatívneho dopadu na hl ekonomická aktivita spoločnosti).