Řízení dotazů metodou dynamického programování. Dynamické programování, základní principy. Fáze I. Podmíněná optimalizace

Na počáteční fázeřešení dopravní problém musí být získán počáteční referenční plán. Jak to udělat, je podrobně popsáno v článku. Jak vyřešit dopravní problém. Po obdržení referenční plán je nutné zkontrolovat, zda nedošlo k degeneraci.

Pravidlo: počet základních (vyplněných) buněk v původním plánu by měl být VŽDY roven m + n - 1, kde m je počet dodavatelů, n je počet spotřebitelů přepravního úkolu.

Co dělat, když je počet vyplněných buněk v referenčním plánu menší, než je nutné?

V určité fázi získávání počátečního plánu může nastat situace, kdy jsou současně uspokojeny potřeby prodejny a vyprázdněn sklad. V tomto případě dochází ke „ztrátě“ základní buňky. To vede k tomu, že systém pro určování potenciálů nemá jednoznačné řešení.

Abychom tuto situaci obešli, přidáme k základním buňkám chybějící počet buněk s nulovými hodnotami. Do buňky vložíme nulovou hodnotu, stojící poblíž se základní buňkou, což způsobilo „ztrátu“ základní hodnoty.

Degenerace referenčního řešení dopravního problému - příklad 1:

Vytvořte si počáteční plán pro následující situaci:

Počet dodavatelů (skladů) = 3, počet spotřebitelů (prodejen) = 4

60 + 30 + 40 = 40 + 50 + 10 + 30 - poptávka se rovná nabídce - problém je uzavřen.

Severní metoda západním rohu dostaneme základní plán.

Začneme levou horní buňkou.

Potřeby prvního obchodu byly plně uspokojeny, ale ve skladu ještě zbývá nějaký náklad. Doplňme to dále.

Zbývající náklad z prvního skladu 60 - 40 = 20 se přepraví do druhého skladu. Ve stejné době byl první sklad prázdný, ale potřeby prodejny nebyly plně uspokojeny.

Přesuňme se do druhého skladu. Všech 30 jednotek nákladu překládáme do druhé prodejny, jejíž potřeby se shodují se zásobováním skladu 50 - 20 = 30.

Na daná distribuce sklad se vyprázdní a potřeby druhé prodejny jsou plně uspokojeny. Dochází ke ztrátě základní buňky!

V v tomto případě je nutné přidat buňku s nulová hodnota, nacházející se vedle právě naplněného, ​​který způsobil ztrátu.

Pokračujme.

Ze třetího skladu odešleme 10 jednotek nákladu do skladu 4, abychom plně uspokojili jeho potřeby. Ve 3. skladu zbývá 40 - 10 = 30 jednotek nákladu, které převezeme do poslední prodejny.

Základní plán byl vypracován.

Počet základních buněk je 6 = 3 + 4 - 1. Podmínka nedegenerace je splněna!

Degenerace referenčního řešení dopravního problému - příklad 2:

Tři obchodní sklad dodávat produkty do čtyř obchodů. Dostupnost produktů na skladech a potřeby prodejen jsou uvedeny v následující tabulce. Pojďme sestavit počáteční plán pro problém s dopravou:

Uzavřený úkol:

12 + 10 + 14 = 36

4 + 18 + 8 + 6 = 36

Výchozí plán získáme metodou severního úhlu.

Začneme vyplněním buňky (1;1).

Zásoby prvního skladu byly rozděleny mezi první a druhou prodejnu, přičemž zásoby skladu byly vyčerpány a potřeby druhé prodejny nebyly uspokojeny. Přesuňme se do druhého skladu.

Všech 10 jednotek nákladu posíláme do druhého obchodu, jehož potřeby jsou momentálně se rovnají 18 - 8 = 10. Všimněte si, že na tento krok Zároveň dochází k naplňování potřeb druhé prodejny a dochází inventář druhého skladu. Došlo ke ztrátě jedné základní hodnoty.

Je v pořádku, pokud tento bod při získávání referenčního plánu přehlédnete. Hlavní věcí je nezapomenout zkontrolovat stav nedegenerace před kontrolou optimálnosti plánu. Po analýze již získaného rozložení zatížení není těžké najít okamžik, kdy se základní buňka „ztratila“.

Abychom kompenzovali ztrátu, musíme zadat nulovou buňku vedle vyplněné. Můžeme jej umístit doprava, doleva nebo pod hodnotu 10.

Dokončíme vyplňování tabulky:

Výchozí plán jsme získali metodou severozápadního rohu. Počet základních buněk je 4 + 3 - 1 = 6.

Můžete začít řešit problém pomocí metody potenciálu!

Předpokládejme to kanonický problém LP nemá příliš speciální formu a například pravé strany rovnic systému omezení mohou být záporné.
Tento případ nastává při řešení dietní problémy. Kanonická forma problému vypadá takto:

F=20 X 1 + 20X 2 + 10X 3 → min.

Zapišme úlohu do simplexní tabulky (tabulka 1).

Tabulka 1

Základní řešení odpovídající základu (x 4, x 5, x 6) a rovné (0; 0; 0; -33; 23; -12) není platné z důvodu negativity X 4 < 0, x 5 < 0, x 6 < 0.

Pojďme formulovat pravidlo pro nalezení platného referenčního plánu.
Pokud jsou ve sloupci volných členů záporné prvky, vyberte největší v modulu a v jeho řádku - jakýkoli záporný. Vezmete-li tento prvek jako povolující prvek, přepočítejte tabulku jako dříve pravidla 2-5.
Pokud se ve výsledné tabulce všechny prvky sloupce volných členů stanou kladnými nebo 0, pak toto základní řešení lze brát jako počáteční referenční plán. . Pokud ve sloupci volných výrazů nejsou všechny prvky nezáporné, použijte toto pravidlo znovu.
Udělejme tento krok pro problém s dietou. Jako rozlišovací řádek tabulky. 1 musíte vybrat první. A jako rozlišovací prvek zvolíme například prvek -4.

Tabulka 2

základní				uvolnit

Všimněte si, že do základu byla zahrnuta proměnná x 1 místo x 4, všechny výpočty byly provedeny podle pravidla 2-5. V pravém sloupci stále zbývá záporný prvek, použijme znovu pravidlo. Variabilní řetězec X 6 je rozlišovací a jako rozlišovací prvek si vezměme například 3 / 2, zde je nějaká volba.

Tabulka 2

základní				uvolnit

Výsledná základní linie X* = (X 1 , X 2 , X 3, X 4 , X 5 , X 6) = (7, 0, 5/2, 0, 1/2, 0) je přípustné a navíc se ukazuje jako optimální, protože v řetězci indexu nejsou žádné záporné prvky. Optimální hodnota objektivní funkce rovná se F* = 165. Opravdu,
F = 20X 1 + 20X 2 + 10X 3 = 20 7 + 0 + 10 = 140 + 25 = 165.

V tomto problému nebylo nutné vylepšovat nalezený výchozí referenční plán, protože ukázalo se to jako optimální. Jinak jsme se museli vrátit do fáze III.

Řešení plánové úlohy simplexovou metodou

Úkol. Společnost má tři druhy surovin a hodlá vyrábět čtyři druhy výrobků. Koeficienty v tabulce 3.12 udávají náklady na odpovídající druh suroviny na jednotku určitého typu výrobku, dále zisk z prodeje jednotky výrobku a celkové zásoby zdrojů. Úkol: najít optimální plán výroba produktů, které zajistí maximální zisk.

Tabulka 3

Pojďme skládat matematický model. Nechat X 1 , X 2 , X 3 , X 4 - počet výrobků typu I, II, III, IV v plánu. Potom se množství použitých surovin a jejich zásoby vyjádří v nerovnostech:

F=3 x 1 + 5x 2 + 4x 3 + 5x 4 → max.

Objektivní funkce vyjadřuje celkový celkový zisk získaný z prodeje všech plánovaných výrobků a každá z nerovností vyjadřuje náklady na určitý druh výrobku. Je jasné, že náklady by neměly překročit zásoby surovin.

Snižme problém na kanonická forma a do speciálního formuláře zavedením dalších proměnných x 5, x 6, x 7 do každé z nerovností.
Je zřejmé, že pokud je první zdroj potřebný pro výrobu plánovaných produktů 5 X 1 + 0,4X 2 + 2X 3 + 0,5X 4 pak X 5 jednoduše označuje přebytek prvního zdroje jako rozdíl mezi dostupnou nabídkou a zásobou požadovanou pro výrobu. Rovněž X 6 a X 7. Dodatečné změny v problému LP tedy indikují přebytky surovin, času a dalších zdrojů zbývajících při výrobě daného optimálního plánu.

Zapišme problém do tabulky 4, poté, co jsme nejprve napsali jeho kanonickou formu:

Fáze I . Jedná se o problém speciálního typu, základ tvoří proměnné (x5, x6, x7), pravé strany rovnic jsou nezáporné, plán X= (0, 0, 0, 0, 400, 300, 100) - reference. Odpovídá simplexní tabulce.

Tabulka 4

základní					uvolnit

Etapa II . Zkontrolujeme optimalitu plánu. Vzhledem k tomu, že v indexu F -line jsou negativní prvky, plán není optimální, přecházíme do fáze III.

Stupeň III . Zlepšení referenčního plánu. Jako rozlišovací sloupec zvolíme čtvrtý sloupec, ale mohli bychom zvolit i druhý, protože v obou (-5). Když jsme se rozhodli pro čtvrtý, zvolíme 1 jako rozlišovací prvek, protože právě na něm je dosaženo minimálních poměrů . S vyřešením prvku 1 transformujeme tabulku podle pravidel 2-5 (tabulka 5).

Tabulka 5

Výsledný plán je opět neoptimální, protože v F-řetězci je záporný prvek -5. tento sloupec je povolený.

Jako rozlišovací prvek volíme 5, protože .

Znovu přepočítáme tabulku. Všimněte si, že je vhodné začít přepočítávání od řádku indexu, protože pokud jsou všechny jeho prvky nezáporné, pak je plán optimální a k jeho vypsání stačí přepočítat sloupec volných členů, není třeba počítat „vnitřek“ tabulky (tabulka 6).

Tabulka 6

základní					uvolnit

Plán je optimální, protože v řádku indexu nejsou žádné negativní prvky, zapište to.

Etapa IV . Základní proměnné (x5, x2, x4) nabývají hodnot ze sloupce volných podmínek a volné proměnné jsou rovny 0. Optimální plán X* = (0, 40, 0, 100, 334, 0, 0) a F* = 700. Opravdu, F = 3X 1 + 4X 3 + 5X 2 + 5X 4 = 5 · 40 + 5 · 100 = 700. To znamená získat maximální zisk 700 rublů. podnik musí vyrábět výrobky typu II v množství 40 kusů, typu IV v množství 100 kusů, výrobky typu I a III jsou nerentabilní na výrobu. V tomto případě budou suroviny druhého a třetího typu zcela spotřebovány a surovin prvního typu zůstane 334 jednotek ( X 5 = 334, X 6 = 0, X 7 = 0).