"Dynamické programování při řešení výrobních úkolů." Výukový program: Dynamické programování v ekonomických úkolech

2.1. Úkolu distribuce investic

"Podmínka úkolu. Výrobní asociace zahrnuje tři podniky PI, Ti2, SH. Řízení sdružení se rozhodlo investovat 5 podmíněných měnových jednotek v jejich podnicích (den. Den). Marketingový výzkum předpovídá částku očekávaných zisků každého podniky v závislosti na objemu investovaných prostředků. Tyto údaje jsou uvedeny v tabulce níže. Je za to, že se očekává, že nulové investice nebudou nulové.

Je nutné nalézt takové rozdělení investic mezi podniky, které by zajistilo maximální maximální očekávaný zisk.

Rozhodnutí. V tomto úkolu je řízený systém zvažovanou asociací výroby, vícestupňovým procesem - proces přidělování prostředků do podniků. Všimněte si, že struktura vícestupňového procesu v tomto problému se stanoví ne v průběhu času, ale postupem pro rozložení investic na plánování. Ekonomický účinek představuje celkovou částku očekávaného zisku a zároveň je úkol vyřešen na hledání maxima.

Pro vyřešení úkolu budujeme první svého ekonomického a matematického modelu v souladu s odstavci. 1-5 sekundy. 1.7 CH. jeden.

Počet kroků. / V Toto úkolu by mělo být přijato 3 odpovídající počtu podniků zahrnutých do výrobní asociace: v prvním kroku je plánován zdůraznit finanční prostředky společnosti P, ve druhém kroku - společnost Ya2, ve třetím kroku - podniku Sh.

Jako fázová proměnná X, která určuje stav systému během procesu distribuce investic, přijmeme celkovou částku prostředků přidělených podnikům po každém procesu procesu. Právě je to právě, proměnná X představuje výši prostředků přidělených podnikům po prvním kroku procesu (tj. Pouze podniku P), X2 - výše finančních prostředků přidělených po druhém kroku (podniky P a D2), X3- Výměna finančních prostředků přidělených po procesu třetího kroku (všechny podniky P, YA2 a YAZ). Vzhledem k tomu, že v počátečním okamžiku je celkové množství přidělených prostředků 0, pak je počáteční stav systému charakterizován hodnotou Xq \u003d 0. Podle podmínce problému je celková částka investičních nástrojů 5 SL. doupě. Jednotky., tj. Kód kabelu je vyžadován.. Například v důsledku pozornosti problému bylo možné zvolit jako proměnnou x rozlišení nepřidělených prostředků.

Jako kontrolní proměnná a převzít množství prostředků přidělených podnikům na každém z krocích procesu. Je to proměnná, která představuje výši finančních prostředků přidělených podniku (v 1. kroku procesu), a2 - výše finančních prostředků přidělených na podniku P2 (ve 2. kroku) od objemu prostředků přidělených podle Enterprise 773 (ve 3. kroku). Předpokládáme, že prostředky pro podniky jsou přiděleny částky, ale celočíselným počtem podmínek. doupě. Jednotky; V souladu s tím všechny ovládací prvky trvá pouze celé číslo 0, 1, 2, ....

Funkce procesu XI \u003d / і (xі-і, U), určující zákon změny stavu systému, se zdá být vzorec tohoto problému

Xі \u003d xі-і +

a má následující jednoduchý význam: celková výše fondů XI přidělených podnikům s rostoucím výsledkem po současném kroku s číslem g se rovná celkové výši prostředků přidělených podnikům po předchozím kroku s číslem і - 1 ( nebo to stejné, do aktuálního kroku) plus objem finančních prostředků přidělených do podnikání v aktuálním kroku.

Funkce ZI, která určuje soukromý ekonomický efekt v kroku s počtem procesu, závisí pouze na objemu investovaných prostředků v podniku, tj. Zi \u003d ZI (m), a je určen tabulkou těchto úkolů na sloupec, který tuto společnost odpovídá. Například Z (2) \u003d 4 (z sloupce odpovídajícího podniku PI), Z2 (3) \u003d 6, 23 (4) \u003d 9.

O těchto akcích předepsaných PP. 1-5 sekundy. 1.7 CH. 1 provedeno, což znamená dokončení matematické formalizace úkolu, tj. Výstavba vhodné ekonomiky matematický model. Všimněte si, že po stanovené formalizaci jsou prováděny hlavní předpoklady metody DP: Absence následného sledování vyplývá z explicitních vzorců pro výpočet XI a ZI a doplňku cílové funkce

Z \u003d ZI (UI) + Z2 (AND2) + 23 (M3)

vzhledem k velmi formulaci problému.

Můžete tedy přímo pokračovat do výpočtů v souladu s metodou DP. Tyto výpočty, jak je uvedeno výše v sekci. 1.6 CH. 1, prováděný ve třech fázích: předběžná fáze, stadium podmíněného optimalizace a konečným krokem optimalizace. V předběžné fázi a ve fázi podmíněné optimalizace jsou výsledky výpočtu zaznamenány v pomocné a základní tabulce struktury, která je uvedena v sekci. 1.7 CH. 1. V rámci nesporného optimalizace je vybudován optimální řešení problému pomocí informací obsažených v hlavních tabulkách.

Předběžná fáze. Tato fáze řešení problému se provádí v přirozeném pořadí pro і \u003d 1, 2.3 a není přímo v souvislosti s výpočtem funkcí Bellman BI (XI). Vyplní se pouze první řetězec pomocného stolu a čtyři levé sloupce hlavní tabulky.

Pomocný stůl je naplněn počátečním stavu Xq \u003d 0 a má formulář

Plnění hlavní tabulky se provádí následujícím způsobem. Pro danou jednoduchou přípustnou hodnotu XQ \u003d 0 vyberte všechny možné hodnoty řídicích hodnot (to může trvat všechny celočíselné hodnoty od 0 do 5 inclusive) a zadejte je do druhého sloupce tabulky. Podle vzorce XI - Xq + (další obecný vzorec XG \u003d XI + U na і \u003d 1) provádíme výpočet odpovídajících hodnot proměnné XX a zadejte je do třetího sloupce . Chcete-li vyplnit čtvrtý sloupec, hodnoty očekávaného zisku ZX pocházejí ze sloupce úlohy zdrojové datové tabulky, která splňuje podniku PI. Pro SH - 1 na této tabulce ZJ \u003d 2, pro a \u003d 2, podle tabulky ZI - 4 atd., Pro SH \u003d 0, podle stavu problému Zi \u003d 0. Získáme následující hlavní tabulku:

Na tom je vyplnění levé strany hlavní tabulky dokončena a tabulka má pouze jeden malý fragment. Přejděte k dalšímu kroku.

i \u003d 2.

Ve druhém kroku, v prvním řádku pomocného stolu, provedeme všechny hodnoty proměnné x, vypočtené v předchozím kroku a zobrazí se ve třetím sloupci předchozí hlavní tabulky. Dostaneme následující pomocný stůl:

Chcete-li zaplnit hlavní tabulku v tomto kroku, budeme analogicky s předchozím krokem, postupně vyberte všechny přípustné hodnoty X, zadané do dceřiné tabulky a provádět odpovídající výpočty. Každá hodnota X bude odpovídat jeho malému fragmentu hlavního stolu; Přilehlé malá písmena horizontální čáry jsou odděleny.

Pro hodnotu X \u003d 0 vyberte všechny možné hodnoty ovládacího prvku U2 (může trvat všechny celočíselné hodnoty z přibližně 5 inclusive) a zadejte je do druhého sloupce tabulky. Podle

formula X2 \u003d X + U2 (následující z obecného vzorce XI \u003d XI-L +

při r \u003d 2) provádíme výpočet odpovídajících hodnot proměnné x2 a zadejte je do třetího sloupce. Chcete-li vyplnit čtvrtý sloupec, hodnoty očekávaného zisku Z2 odešlete ze sloupce zdrojové datové tabulky úlohy odpovídající podniku P ^. "Pro и2 \u003d 1 pro tuto tabulku, Z2 \u003d 1, pro U2 - 2, podle tabulky Z2 \u003d 2 atd. Vyplnění prvního fragmentu linky hlavního stolu odpovídající X \u003d 0; Tento fragment má následující formulář:

Pro další přípustnou hodnotu XI \u003d 1 stavíme následující malá fragment. Současně ovládání And2 může mít všechny hodnoty celého čísla od 0 do 4 inclusive (protože po výběru nástrojů Enterprise P v množství X \u003d 1

Podobně jsou tvořeny fragmenty linky tabulky a pro x \u003d 2,3,4,5. Je zřejmé, že se zvýšením hodnoty x je sada přípustných řídicích hodnot U2 zúžena a pro x \u003d 5 je pouze jedna hodnota pouze jedna hodnota a 2 \u003d 0. V důsledku toho získáme následující hlavní tabulka:

Vytvořený stůl je rozdělen do 6 malých písmen, tolik, kolik různých hodnot může přijímat variabilní XI. Přejděte na další (poslední) krok. .

Ve třetím kroku, v prvním řádku pomocného stolu, provedeme všechny hodnoty proměnné x2 vypočtené v předchozím kroku a zobrazí se ve třetím sloupci předchozí hlavní tabulky. Tyto hodnoty opakovaně opakují

Dynamické programování je matematický přístroj určený pro efektivní řešení Nějaká třída problémů matematického programování. Tato třída se vyznačuje možností přirozeného (a někdy umělého) rozdělení celého provozu do řady vzájemně provázaných fází. Termín "dynamický" v názvu metody se objevil, zřejmě, protože se předpokládá, že jsou včas odděleny. Kroky však mohou být prvky operace, v žádném případě navzájem spojeny. Metoda řešení takových vícestupňových úkolů je však aplikován stejným a jeho název se obecně přijímá, i když v některých zdrojích se nazývá vícestupňové programování.

Dynamické modelovací modely mohou být aplikovány například při vývoji pravidel rezerv vytváření okamžiku doplňování zásob a výši řádu doplňování; Při vývoji principů kalendářního plánování výroby a vyrovnání zaměstnanosti v podmínkách kolísajícího poptávky po výrobcích; v distribuci nedostatečných kapitálových investic mezi možnými novými směry jejich použití; Při vypracování plánů kalendáře pro aktuální a generální opravu složitého vybavení a jeho výměny; Při vývoji dlouhodobých pravidel pro nahrazení provozu dlouhodobého majetku atd.

Nejjednodušší způsob, jak vyřešit problém, je úplné vyhledávání všech možností. Když je počet možností malý, tato metoda je poměrně přijatelná. V praxi je však úkol s malým počtem možností velmi vzácný, takže plná busta je obvykle nepřijatelná z důvodu nadměrných nákladů na výpočetní prostředky. V takových případech se proto dynamické programování přichází na záchranu.

Dynamický programování často pomáhá vyřešit úkol, perknown algoritmus, pro který by vyžadoval spoustu času. Tato metoda používá myšlenku krok za krokem optimalizace. V této myšlence je základní jemnost: Každý krok není optimalizován sám, ale s "světlem pro budoucnost", na důsledcích přijatého "kroku" řešení. Mělo by zajistit maximální výhry, které nejsou v určitém kroku, ale na celé souhrnné kroky obsažené v provozu.

Dynamická metoda programování lze použít pouze pro konkrétní třídu úkolů. Tyto úkoly by měly tyto požadavky splňovat:

· Optimalizační úkol je interpretován jako proces správy n-krok;

· Cílová funkce se rovná množství cílové funkce každý krok;

· Výběr řízení krok k-m Záleží pouze na stavu systému do tohoto kroku, neovlivňuje předchozí kroky (žádná zpětná vazba);

· Stát s K. Po kroku K-tého řízení závisí pouze v předchozím stavu s k-1 a managementu x K. (nedostatek prostředí);

· Na každém kroku, managementu X K. Závisí na konečném počtu řídicích proměnných a stavu s K. - Z konečného počtu parametrů.

Řešení všech úkolů dynamického programování je "Princip optimality" Bellmanu, který vypadá takto:

bez ohledu na stav Systém S v důsledku libovolného počtu kroků, v blízkém kroku je třeba zvolit řízení tak, že je v kombinaci s optimálním ovládáním ve všech následujících krocích vedlo k optimálnímu výboru na všech zbývajících krocích, včetně tohoto.

Tento princip byl poprvé formulován R. Bellmanem v roce 1953. Bellman byl jasně formulován podmínkami, za kterých je princip věrný. Základním požadavkem je proces řízení musí být bez zpětné vazby, tj. Vedení v tomto kroku by nemělo mít vliv na předchozí kroky.

Obecná formulace klasického úkolu investic.

Zvažte celkovou formulaci dynamického úkolu distribuce investic.

Pro rozvoj, kapitálové investice do výši S jsou zdůrazňovány pro rozvoj. Na investičních předmětů je pro každá z nich očekávaná zisková fi (x), získaná z přílohy určité výše finančních prostředků. Je nutné distribuovat kapitálové investice mezi objekty N (podniky, projekty) takovým způsobem, aby bylo dosaženo nejvyšší možné výši příjmů.

Kompilovat matematický model, pokračujeme z předpokladů:

· Zisk z každého podniku (projekt) nezávisí na investicích v jiných podnicích;

· Zisk z každého podniku (projekt) je vyjádřen v některých konvenčních jednotkách;

· Celkový zisk se rovná výši zisku přijatých z každého podniku (projekt).

Toto nastavení je zjednodušený model procesu distribuce reálného investování a v "čisté" formuláře nedochází, protože nebere v úvahu některé faktory, a to:

· Přítomnost "neformálních" kritérií, tj Ti, kteří nemohou být změřeny kvantitativně (například soudržnost projektu s celkovou strategií podnikání, jeho sociální nebo environmentální charakter, atd.), a proto projekty mohou mít jinou prioritu;

· Úroveň rizik projektů;

· Další faktory.

Vzhledem k potřebě zaznamenat úroveň rizika při tvorbě investičního portfolia se objevilo stochastické dynamické programování, které se zabývají pravděpodobnostními hodnotami. To bylo aplikováno v různých oblastech, mezi nimiž jeden z nejrozšířenějších studií je řízení rizikových finančních investic.

Dynamické programování (DP) je metoda optimalizace přizpůsobená operacím, ve kterém může být rozhodovací proces rozdělen do kroků (kroků). Tyto operace se nazývají vícestupňový. Začátek vývoje DP odkazuje na 50. let XX století. Je spojen s názvem R. Bellman.

Pokud mohou být lineární programovací modely použity v ekonomice pro výrobu rozsáhlých plánovaných řešení v obtížných situacích, modely DP se používají při řešení úkolů výrazně menšího měřítku, například při vývoji pravidel správy rezerv, která stanoví okamžik Doplnění zásob a výši řádu doplňování; Při vývoji principů kalendářního plánování výroby a vyrovnání zaměstnanosti v podmínkách kolísajícího poptávky po výrobcích; Při distribuci vzácných kapitálových investic mezi možnými novými směry jejich použití; Při vypracování plánů kalendáře pro aktuální a generální opravu složitého vybavení a jeho výměny; Při vývoji dlouhodobých pravidel pro nahrazení hlavních fondů odcházejících z provozu atd. \\ T

Ve skutečnosti fungují velké ekonomické systémy, mikroekonomická řešení jsou vyžadovány týdně. DP modely jsou cenné v tom, že umožňují založené na standardním přístupu s využitím minimálního lidského zásahu, aby taková rozhodnutí. A pokud každý odebraný takový roztok je zbytečně, pak v souhrnu, tato řešení mohou mít velký dopad na zisky.

Spravovaný proces je považován za například ekonomický proces rozdělení finančních prostředků mezi podniky, využívání zdrojů po dobu několika let, nahrazujícím vybavení, doplňování rezerv, atd.

V důsledku řídicího systému (řídicí objekt) je přeložen z počátečního stavu (tak) do konečného stavu (SN). Předpokládejme, že správa lze rozdělit na n-kroky, tj. Řešení je akceptováno postupně v každém kroku a ovládání, které překládá systém S z počátečního stavu do finále, je proces řízení n-kroku.

V každém kroku se aplikuje určité řídicí roztok X K, zatímco sada X- (X1, X2, ..., XN) se nazývá řízení. Dynamická metoda programování je založena na nedostatku následky a stavu aditivity cílové funkce.

Stav nedostatku pozornosti. Stav s k, který přepnutý na systém po dobu jedné doby, závisí pouze na stavu S K -1 a Control X K a nezávisí na tom, jak systém přišel do stavu S k.1:

S. k. (S. k.1, X. k.)

Je také zohledněno, že volba řízení na kroku K-OM závisí pouze ve stavu systému do tohoto kroku:

x. k. (S. k. -1 )

Na každém kroku řízení x k závisí na konečném počtu řídicích proměnných. Stav systému v každém kroku závisí na konečném počtu parametrů.

Princip optimality.Bez ohledu na stav systému v důsledku libovolného počtu kroků, v blízkém kroku je třeba zvolit řízení tak, že je v kombinaci s optimálním ovládáním na všech následujících krocích na optimální výhru na všech zbývajících krocích, včetně tohoto . Základním požadavkem, ve kterém zásada věrného je proces řízení musí být bez zpětné vazby, tj. Vedení v tomto kroku by nemělo mít vliv na předchozí kroky.

Řešení v každém kroku se tedy ukazuje, že je to nejlepší z hlediska řízení jako celku.

Opakované vztahy Bellman.

Nalezení optimálního řešení řízeného procesu lze provést na základě recidivujících poměrů Bellman. Nech být f. k. (S k -1, x k) - indikátor účinnosti kroků k-th se všemi druhy řízení. Přidělte zpětný a přímý vzor Bellmanu.

Stůl6 . Hodnoty ziskových podniků

Objem přidělených zdrojů	Zisk z projektů

V této tabulce 6. jsou uvedeny hodnoty zisků (f; (q)), které byly získány řešením výroby a ekonomického úkolu každého investovaného podnikání. Tyto hodnoty se liší v závislosti na objemech investic.

Tabulka 7. Údaje o dodatečném příjmu podniků

Přidělené prostředky

V této tabulce 7. Údaje o dodatečném příjmu, které podnik investora obdrží z každé investice investovaných, v závislosti na objemu investic investovaných.

Tabulka 8. Byly vypočteny ukazatele účinnosti (ZI (Q)) investovaných podniků, které byly získány s použitím přímého schématu Belleman.

Tabulka 8. Mapy účinnosti

Přidělené prostředky	Další příjmy z projektů

Zvažte zjištění každé z ukazatelů výkonnosti:

Pro indikátory účinnosti jednoho podniku ZI (0) \u003d PI (0) \u003d 0

Z1 (200'000) \u003d P1 (200 "000) \u003d 7068135.2

Z1 (400 "000) \u003d P1 (400" 000) \u003d 2567391.9

Z1 (600 "000) \u003d p1 (600" 000) \u003d 2216151,6

Z1 (800 "000) \u003d P1 (800" 000) \u003d 1222330,8

Z1 (L "OOO" OOO) \u003d p1 (l "000" 000) \u003d 122233.09 pro ukazatele účinnosti dvou podniků.

Z 2 (0) \u003d P 2 (0) \u003d 0

Z 2 (200 "000) \u003d max (0 + 70 68135.2; 94 07519,6 + 0 )=9407519,6

Z 2 (400 "000) \u003d max (0 + 25 67391,9; 94 07519,6 + 70 68135,2 ; 80 92519,9 + 0}=16475654,8

Z 2 (600 "000) \u003d max (0 + 22 16151,6; 94 07519,6 +25 67391,9; 80 92519,9 +70 68135,2 ; 80 92353,6 + 0)=15160655,1

Z 2 (800 "000) \u003d max (0 + 12 2233.08; 94 07519,6 + 22,16151,6; 80 92519,9 + 25,67391,9; 80 92353,6 + 70 68135,2 : 80 92353,6 + 0}=15160488,8

Z 2 (l "000" 000) \u003d max (0 + 12 22330,9; 94 07519,6 + 12,22330,8; 80 92519,9 + 22 16151,6; 80 92353,6 + 25 67391,9; 80 92353,6 + 70 68135,2 ; 67 38741,6 + 0}=15160488,8

Pro účinnost tří podniků.

Z 3 (0) \u003d P 3 (0) \u003d 0

Z 3 (200 "000) \u003d max (0 + 94 07519.6; 507 43194,2 + 0 )=50743194,2

Z 3 (400 "000) \u003d max (0 + 8092519.9; 507 43194,2 + 94 07519,6 ; 272 10300,4 + 0}=60150713,8

Z 3 (600 "000) \u003d max (0 + 8092353.6; 507 43194,2 + 8092519,9 ; 272 10300,4+94 07519,6; 272 10300,4 + 0}=58835714,1

Z 3 (800 "000) \u003d max (0 + 8092353.6: 507 43194,2 + 8092353,6 ; 272 10300,4 +9407519,6; 272 10300,4 + 8092519,9; 272 10300,5 + 0}= 58835547,8

Z 3 (l "000" 000) \u003d max (0 + 6738741.6; 507 43194,2 + 8092353,6 ; 272 10300,4 + 8092353,6; 272 10300,4 + 8092519,9; 272 10300,5 + 94 07519,6; 27210300,4+0}=58835547,8

Pro účinnost čtyř podniků.

Z 4 (0) \u003d P 4 (0) \u003d 0

Z 4 (200 "000) \u003d Max ( 0 + 507 43194,2 ; 118 73132,7 + 0}= 507 43194,2

Z 4 (400 "000) \u003d max (0 + 27210300.4; 118 73132,7 + 507 43194,2 ; 84 75336,3+0}=62616326,9

Z4 (600 "000) \u003d max (0 + 27210300.4; 118 73132.7 + 27210300.4; 84 75336,3 + 507 43194,2 ; 84 75336,3 + 0}= 59218530,5

Z4 (800 "000) \u003d max (0 + 27 210 300.5; 11 873 132,7 + 27,10 300,4; 8 475 336,3 + 27 210 300.4; 8 475 336,3 + 50 743 194,2 ; 71 37734,9 + 0}=59218530,5

Z4 (l "000" 000) \u003d max (0 + 27210300.4; 118 73132,7 + 27210300,5; 84 75336,3+ 27210300.4; 84 75336,3 + 27210300.4; 71 37734,9 + 507 43194,2 ; 62 83185,8+0}=57880929,1

Pro účinnost pěti podniků.

Z 5 (0) \u003d p5 (0) \u003d 0

Z 5 (200 "000) \u003d Max ( 0 + 11873132,7 ; 103 07000,5 + 0}= 11873132,7

Z 5 (400 "000) \u003d max (0 + 8475336.3; 103 07000,5 + 11873132 ,7; 77 36093,1+ 0}=22180133,2

Z 5 (600 "000) \u003d max (0 + 8 475 336,3; 10 307 000,5 + 8 475 336.3; 7 736 093,1+11 873 132,7 ; 7 736 093,2 + 0}=19609225,8

Z 5 (800 "000) \u003d max (0 + 7137734,9; 10 307000,5 + 8 475336,3; 77 36093,1 + 8475336.3; 77 36093,2 + 11873132,7 ; 72 41299,8 + 0}= 19609225,9

Z 5 (l "000000) \u003d max (0 + 6283185,8; 103 07000,5 + 7137734,9; 77 36093,1 + 8475336,3; 7736093,2+ 8475336.3; 72 41299,8+11873132,7 ; 71 67372,4+, 0}=19714432,5

Po obdržení posledního ukazatele výkonnosti můžete získat řešení problému:

Z 5 (1 "000" 000) \u003d 103 07000,5 + 59218530,5 \u003d 69525531,00 Q 1 \u003d 20 000 000p.

Z4 (800 "000) \u003d 118 73132,7 + 58835714.1 \u003d 70708846,80 Q \u003d 20 000 000p.

Z 3 (600 "000) \u003d 507 43194,2 + 16475654,8 \u003d 67218849,00 Q 3 \u003d 20 000 000 p.

Z 2 (400 "000) \u003d 94 07519,6 + 7068135.2 \u003d 164756548 Q 4 \u003d 20 000 000p.

Z1 (200000) \u003d p! (200 "000) \u003d 70 68135,2 q 5 \u003d 20 000 000 ° C.

Pro získání maximálního zisku, přidělené prostředky investora (hotovost ve výši 100 000 000 rublů) by měly být distribuovány následovně - každý vyšetřovaný podnik by měl být přidělen na 20 000 000 rublů. Zároveň bude maximální indikátor kombinovaného výkonu 7078.846.80 rublů.

Dynamické programování (DP) je matematický přístroj, který je určen ke zvýšení účinnosti výpočtů při řešení určité třídy problémů matematických programování rozkladem (rozkladu) na relativně malých a proto méně složitých podtaskásel. Charakteristika pro dynamické programování je přístup k řešení úkolu v etapách, z nichž každá je spojena jedna řízená proměnná. Sada opakovacích postupů výpočetní techniky různé stádiaPoskytuje získání přípustného optimálního řešení problému obecně, pokud je dosaženo poslední fáze.

Základní princip založený na teorii DP je zásada optimality. V podstatě určuje postup pro postupné rozhodnutí o rozkladu úkolu (to je přijatelnějším způsobem než okamžité řešení problému v původní formulaci) s pomocí postupů výpočetní techniky.

Hlavní ustanovení dynamického programování spolu s neobvyklým matematickým zápisem často vytvářejí potíže ve studiu této části matematického programování. Zejména to odkazuje na ty, kteří nejprve splní předmět. Zkušenosti však ukazují, že systematické odvolání na úkoly a metody DP, což vyžaduje určitou vytrvalost, nakonec vede k úplnému porozumění na začátku nejasných ustanovení. Když se to stane, dynamické programování se začíná zdát překvapivě jednoduchou a štíhlou teorii.

Použijte metodu dynamického programování pro distribuci investic mezi čtyřmi událostmi. Celková výše finančních prostředků investujících do vývoje není více než deset milionů hřiven. Na základě technických a ekonomických výpočtů bylo zjištěno, že v důsledku rekonstrukce v závislosti na výši strávených prostředků, které činnosti budou mít výkon uvedenou v tabulce 2.5. Je nutné určit optimální rozložení finančních prostředků mezi opatřeními, která zajišťuje maximální zvýšení produktivity podnikání. Kritérium se tedy používá v této optimalizačním úkolu - celkový výkon činností.

Tabulka 2.5 - Data pro řešení problému

Počet událostí	Fondy investované do vývoje

Výkonnost v důsledku vývoje (TN)

Přímý a zjevně, příliš zjednodušený způsob, jak vyřešit formulovaný úkol, je použít postup úplného hašení. Úkolem má 4 x 5 \u003d 20 možných řešení a některé z nich nejsou přípustné, protože je implikováno do prostředků přes 10 milionů UAH. V procesu úplné hrubé síly se počítají celkové náklady spojené s každou z 20 možných řešení. Pokud náklady na náklady nepřekročí výši pokročilých fondů, měly by být vypočteny odpovídající celkové příjmy. Nejlepší řešení bude optimální poskytnutí maximálně celkového příjmu.

Všimli jsme si následující nedostatky postupu úplného busta.

1. Každá kombinace projektů určuje některé řešení problému jako celku, odkud vyplývá, že busta všech možných kombinací v úkolech průměrného a velkého rozměru mohou být spojeny s nadměrně velkým objemem výpočtu.
2. Neexistuje žádné informace o řešeních, které nejsou přípustné, což snižuje účinnost výpočtového výpočtového systému.
3. Informace získané v důsledku analýzy některých kombinací projektů se nepoužívá k identifikaci a eliminování neopravních kombinací.

Použití metod DP umožňuje eliminovat všechny uvedené chyby.

Nechť x 1, x 2, x 3, x 4 - investice do vývoje prvního, druhého, třetího, čtvrtého, 0 x I 10000000, i \u003d. Označte f1 (x), f 2 (x), f3 (x), f 4 (x) - funkce změny výkonu prvního, druhého, třetího, čtvrtého akcí při investování do jejich vývoje x mln. UAH. Tyto funkce odpovídají řetězci 1, 2, 3, 4 v tabulce 2.5.

Definujeme funkci maximální funkce

F (x 1, x 2, x 3, x 4) \u003d f1 (x) + f 2 (x) + f3 (x) + f4 (x).

Zároveň investice X1, X2, X3, X4 omezené

x 1 + x 2 + x 3 + x 4 \u003d a,

Základem dynamické metody programování používané k vyřešení úkolu je založena na principu optimality.

Podle tohoto principu, výběrem některých počátečních distribucí zdrojů provádíme vícestupňovou optimalizaci a v blízkém kroku, zvolíme takové rozložení zdrojů tak, že je kombinován s optimálním rozložením všech následujících kroků k maximálnímu vítězství na všech zbývajících krocích, včetně tohoto.

Zvýrazňujeme 3 kroky v našem úkolu:

- milion UAH. Investovat do prvního, druhého události současně;
- milion UAH. Investovat do první, druhé, třetí události společně;

MLN UAH. investováno do čtyř akcí současně;

Označte: F 1,2 (a), f 1,2,3 (a), f 1,2,3,4 (a) - optimální rozložení prostředků pro první, druhé, třetí kroky.

Algoritmus dynamické metody programování se skládá ze dvou stupňů. V první fázi se podmíněná optimalizace provádí v tom, že pro každou ze tří kroků, podmíněné optimální výhra F 1,2 (a), F 1,2,3 (a), F 1,2,3,4 (a) ). Ve druhé fázi se provádí bezpodmínečná optimalizace. Využití výsledků první etapy jsou hodnoty investic nalezeny ve vývoji opatření X 1, X 2, X 3, X 4 Zajištění maximálního výkonu skupiny činností.

První etapa obsahuje následující kroky:

1) Výpočet maximálního kritéria optimalizace pro různé hodnoty kapitálových investic X \u003d 0, 2500000, 5000000, 7500000, 10000000, které se používají pouze pro opatření 1 a 2. Výpočet se provádí podle vzorce (2.4).

Výsledky výpočtu jsou uvedeny v tabulce 2.6.

Tabulka 2.6 - Výsledky výpočtů v první fázi

Například za účelem stanovení F 1.2 (5000000) je nutné vypočítat

f1 (500 000) + F 2 (0) \u003d 700 + 5000 \u003d 5700;

f1 (2500000) + F 2 (2500000) \u003d 600 + 6000 \u003d 6600;

f 1 (0) + F 2 (5000000) \u003d 500 + 7000 \u003d 7500.

Zbývající f l, 2 (x) se získá jako největší hodnota každé diagonální v tabulce (tyto hodnoty jsou podtrženy v tabulce):

F 2 (0) \u003d 5500; F 2 (2500000) \u003d max (5600, 6500) \u003d 6500;

F 2 (500 000 000) \u003d max (5700, 6600, 7500) \u003d 7500;

F 2 (7500000) \u003d max (5800, 6700, 7600, 9000) \u003d 9000;

F 2 (10000000) \u003d max (5900, 6800, 7700, 9100, 1500) \u003d 9100;

2) Výpočet maximálního kritéria optimalizace pro různé hodnoty kapitálových investic X \u003d 0, 2500000, 5000000, 7500000, 10000000, které se používají pouze pro aktivity 1.2 a 3.

Výpočet je založen na vzorci (2.5).

Výsledky výpočtu jsou uvedeny v tabulce 2.7, což je podobné tabulce 2.6, pouze namísto f1 (x), hodnoty f2 (a), a f 2 (A - X) jsou nahrazeny F3 (A A - X).

Tabulka 2.7 - Výsledky výpočtů ve druhé fázi

Hodnoty f 1,2,3 (a) budou následující:

F 1,2,3 (0) \u003d 8600; F 1,2,3 (2500000) \u003d 9600; F 1,2,3 (5000000) \u003d 10600;

F 1,2,3 (7500000) \u003d 12100; F 1,2,3 (10000000) \u003d 12200.

3) Výpočet maximálního kritéria optimalizace pro různé hodnoty kapitálových investic X \u003d 0, 2500000, 5000000, 7500000, 10000000, které se používají pro aktivity 1.2, 3, 4.

Výpočet je založen na vzorci (2.6).

Výsledky výpočtů budou uvedeny v tabulce 2.8.

Tabulka 2.8 - Výsledky výpočtů ve třetí etapě

Hodnoty f 1,2,3,4 (a) bude následující:

F 1,2,3,4 (0) \u003d 9300; F 1,2,3,4 (2500000) \u003d 10300; F 1,2,3,4 (5000000) \u003d 11300;

F 1,2,3,4 (7500000) \u003d 12800; F 1,2,3,4 (10000000) \u003d 12900.

V tomto, první fázi řešení úkolu dynamického programování končí.

Pojďme pokračovat do druhé fáze řešení problému dynamického programování - bezpodmínečná optimalizace. V této fázi se používají tabulky 2,6, 2,7, 2.8. Definujeme optimální investice do vývoje podniků pro A \u003d 0, 2500000, 5000000, 7500000, 10 000 000.000. Chcete-li to provést následující výpočty:

1) Nechte částku investic přidělené na rozvoj podniků, je A \u003d 10 000 000 UAH.

Definujeme množství kapitálových investic na vývoj čtvrté akce. Chcete-li to provést, použijte tabulku 2.8. Vyberte si diagonála, která odpovídá A \u003d 10000000 je hodnoty 12900, 12900, 11500, 10550, 9600. Z těchto čísel vezmeme maximum F 1,2,3,4 (10000000) \u003d 12900 tun. Všimli jsme si sloupec, ve kterém tato hodnota stojí za to. Dále definujeme v označeném sloupci investice do čtvrté události X 4 \u003d 2500000.

Vývoj prvního, druhého a třetího akcí zůstává

A \u003d 10000000 - X 4 \u003d 2500000 UAH.

2) Definujeme množství kapitálových investic přidělených na vývoj třetího akce.

Chcete-li to provést, použijte tabulku 2.7. Vyberte diagonál v této tabulce odpovídající A \u003d 7500000 je hodnoty 12100, 10700, 9800, 8900. Všimli jsme si sloupec, ve kterém maximum (podtržený) výkon f 1,2,3 (7500000) \u003d 12100 tun. Určete X 3 \u003d 0 UAH. V označeném sloupci.

Třetí událost nebudeme financovat.

3) Definujeme množství investic na vývoj druhé akce. Chcete-li to provést, použijte tabulku 2.6. Vybíráme diagonáli na něm odpovídajícím A \u003d 75000000 - je to 5800, 6700, 7600, 9000. Z těchto čísel vezměte maximálně F 1.2 (75000000) \u003d 9000 t. Všimli jsme si sloupec, ve kterém tato hodnota stojí za to. Dále určujeme v označeném sloupci objem investic do druhé události x 2 \u003d 7500000.

Pro kapitálové investice, a \u003d 10000000 UAH. Optimální je investice do vývoje čtvrté akce 2500 000 UAH, druhý - 7 500 000 UAH, rozvoj první a třetí události, fondy nejsou přiděleny. Současně bude celkový výkon čtyř podniků 12900 tun.

Opakování výpočtů druhého stupně roztoku pro A \u003d 3, 2, 1, 0 definujeme optimální investice do rozvoje činností. Výsledky budou následující:

F 1,2,3,4 (7500000) \u003d 12800; x 1 \u003d 0; x 2 \u003d 7500000; x 3 \u003d 0; x 4 \u003d 0

F 1,2,3,4 (5000000) \u003d 11300; x 1 \u003d 0; X 2 \u003d 5000000; x 3 \u003d 0; x 4 \u003d 0

F 1,2,3,4 (2500000) \u003d 10300; x 1 \u003d 0; x 2 \u003d 250000; x 3 \u003d 0; x 4 \u003d 0

F 1,2,3,4 (0) \u003d 9300; x 1 \u003d 0; x 2 \u003d 0; x 3 \u003d 0; x 4 \u003d 0

Dynamické programování je matematický přístroj, který je navržen tak, aby účinně řešit určitou třídu matematických programovacích úkolů. Tato třída se vyznačuje možností přirozeného (a někdy umělého) rozdělení celého provozu do řady vzájemně provázaných fází. Termín "dynamický" v názvu metody se objevil, zřejmě, protože se předpokládá, že jsou včas odděleny. Kroky však mohou být prvky operace, v žádném případě navzájem spojeny. Metoda řešení takových vícestupňových úkolů je však aplikován stejným a jeho název se obecně přijímá, i když v některých zdrojích se nazývá vícestupňové programování.

Chcete-li určit podstatu dynamického programování, zvažte úlohu:

Představte si určitý provoz na řadě po sobě jdoucích "kroků" nebo fázích, například průmyslových činností v průběhu řady obchodních let. Nechte počet kroků rovných m. Vítězství (provozní efektivita) Z pro celou operaci se skládá z výhradníků v jednotlivých krocích:

kde Zi vyhrát na I-M.

Pokud má takovou vlastnost, nazývá se aditivní kritérium.

Provoz o je spravovaný proces, to znamená, že můžeme zvolit některé parametry, které ovlivňují jeho pohyb a výsledek a v každém kroku je řešení vybráno, ze kterého výherně závisí na tomto kroku a zisk pro operaci jako celek . Tato řešení se nazývají kroková.

Kombinace všech krok za kroknějších kontrol je provoz operace jako celku. Označte svým písmenem X a krokové ovládání písmen X1, X2, ..., XM: X \u003d X (X1, X2, ..., XM). Je nutné najít takové ovládací prvky X, ve kterém je výhra nakreslena na maximum:

Tato kontrola x *, ve kterém je dosaženo tohoto maxima, se nazývá optimální kontrola. Skládá se ze sady optimálních stepicích: x * \u003d x * (x1 *, x2 *, ..., xm *).

Maximální zisk, který je dosažen s kontrolou, označujeme následujícím způsobem:
,

kde x-set přípustné (možné) ovládací prvky.

Nejjednodušší způsob, jak vyřešit problém je plný všech možností. Když je počet možností malý, tato metoda je poměrně přijatelná. V praxi je však úkol s malým počtem možností velmi vzácný, takže plná busta je obvykle nepřijatelná z důvodu nadměrných nákladů na výpočetní prostředky. V takových případech se proto dynamické programování přichází na záchranu.

Metoda dynamického programování lze použít pouze pro specifickou třídu úkolů. Tyto úkoly by měly tyto požadavky splňovat:

Úkolem optimalizace je interpretován jako proces správy n-krok.
Cílová funkce se rovná součtu cílových funkcí každého kroku.
Výběr ovládacích prvků v kroku K-M závisí na stavu systému do tohoto kroku, neovlivňuje předchozí kroky (žádná zpětná vazba).
Stav SK po kroku K-th závisí pouze na předchozím stavu XK SK-1 (ne po následném následování).
V každém kroku se XK řízení závisí na konečném počtu řídicích proměnných a stát SK je z konečného počtu parametrů.

Řešení všech úkolů dynamického programování leží "Optimality Princip" BellmanCo vypadá takto:

Bez ohledu na stav Systém S v důsledku libovolného počtu kroků, v blízkém kroku je třeba zvolit řízení tak, že je v kombinaci s optimálním ovládáním ve všech následujících krocích vedlo k optimálnímu výboru na všech zbývajících krocích, včetně tohoto.

Tento princip byl poprvé formulován R. Bellmanem v roce 1953. Bellman byl jasně formulován podmínkami, za kterých se zásada věrných. Hlavním požadavkem je proces řízení musí být bez zpětné vazby, tj. Vedení v tomto kroku by nemělo mít vliv na předchozí kroky.

Princip optimality tvrdí, že pro jakýkoli proces bez zpětné vazby, optimální správa toho je, že je optimální pro jakoukoli podproces ve vztahu k počátečnímu stavu této podprocesy. Proto je řešení v každém kroku je nejlepší z hlediska řízení jako celku.

"Dynamické programování při řešení výrobních úkolů." Výukový program: Dynamické programování v ekonomických úkolech

2.1. Úkolu distribuce investic

Poslední

Je nutné vědět