Články o celočíselném programování metodou větvení a vázané metody. Problém obchodního cestujícího - metoda větve a vazby. Obecný plán řešení problému obchodního cestujícího
Jak jsme již uvedli, optimalizační problém je úkolem najít takové hodnoty faktorů X 1 = X 1* , X 2 = X 2* , …, Xk = Xk * , pro kterou funkce odezvy ( na) dosahuje extrémní hodnoty na= ext (optimální).
Známý různé metodyřešení optimalizačního problému. Jednou z nejpoužívanějších je gradientní metoda, nazývaná také Box-Wilsonova metoda a metoda strmého výstupu.
Uvažujme o podstatě gradientní metody na příkladu dvoufaktorové odezvové funkce y =F(X 1 , X 2 ). Na Obr. Ve faktorovém prostoru jsou zobrazeny křivky 4.3 stejné hodnoty funkce odezvy (křivky hladiny). Bod se souřadnicemi X 1 *, X 2 * odpovídá krajní hodnotě funkce odezvy na ext.
Pokud jako počáteční vybereme libovolný bod ve faktorovém prostoru ( X 1 0 , X 2 0), pak nejkratší cesta k vrcholu funkce odezvy z tohoto bodu je cesta podél křivky, jejíž tečna se v každém bodě shoduje s normálou k křivce hladiny, tzn. je to cesta ve směru gradientu funkce odezvy.
Gradient spojité jednohodnotové funkce y =F(X 1 , X 2) je vektor určený ve směru gradientem se souřadnicemi:
Kde já,j– jednotkové vektory ve směru souřadnicových os X 1 a X 2. Parciální derivace charakterizují směr vektoru.
Protože neznáme typ závislosti y =F(X 1 , X 2), nemůžeme najít parciální derivace a určit skutečný směr gradientu.
Podle gradientové metody je v některé části faktorového prostoru vybrán počáteční bod (počáteční úrovně). X 1 0 , X 20. S ohledem na tyto počáteční úrovně je konstruován symetrický dvouúrovňový experimentální design. Navíc je variační interval zvolen tak malý, že lineární model je adekvátní. Je známo, že jakoukoli křivku na dostatečně malé ploše lze aproximovat lineárním modelem.
Po sestrojení symetrického dvouúrovňového plánu je řešena interpolační úloha, tzn. ve výstavbě lineární model:
a kontroluje se jeho přiměřenost.
Pokud se pro zvolený variační interval ukáže lineární model jako adekvátní, pak lze určit směr gradientu:
Směr gradientu funkce odezvy je tedy určen hodnotami regresních koeficientů. To znamená, že se budeme pohybovat ve směru gradientu, pokud z bodu se souřadnicemi ( ) pojďme k bodu se souřadnicemi:
Kde m – kladné číslo, které určuje velikost kroku ve směru gradientu.
Protože X 10 = 0 a X 2 0 = 0, tedy 
.
Definováním směru přechodu () a výběrem velikosti kroku m, provádíme zkušenosti na základní linieX 1 0 , X 2 0 .
Poté uděláme krok ve směru spádu, tzn. Experiment provádíme v bodě se souřadnicemi . Pokud se hodnota funkce odezvy zvýšila oproti její hodnotě na počáteční úrovni, uděláme další krok ve směru gradientu, tzn. Experiment provádíme v bodě se souřadnicemi:
Pokračujeme v pohybu po gradientu, dokud se funkce odezvy nezačne snižovat. Na Obr. 4.3 pohyb podél gradientu odpovídá přímce vycházející z bodu ( X 1 0 , X 20). Postupně se odchyluje od skutečného směru gradientu, znázorněného přerušovanou čarou, kvůli nelinearitě funkce odezvy.
Jakmile se v dalším experimentu hodnota funkce odezvy sníží, pohyb po gradientu se zastaví, experiment se maximální hodnota funkce odezvy pro novou počáteční úroveň, sestavte nový symetrický dvouúrovňový plán a znovu vyřešte problém interpolace.
Sestavením nového lineárního modelu 
, vykonat regresní analýza. Pokud zároveň kontrola významnosti faktorů ukáže, že alespoň jeden koeficient
faktor, což znamená, že ještě nebylo dosaženo krajní oblasti funkce odezvy (optimum region). Je určen nový směr gradientu a začíná pohyb směrem k optimální oblasti.
Objasňování směru gradientu a pohyb po gradientu pokračuje, dokud v procesu řešení další interpolační úlohy kontrola významnosti faktorů neukáže, že všechny faktory jsou nevýznamné, tzn. Všechno . To znamená, že bylo dosaženo optimální oblasti. V tomto okamžiku je řešení optimalizační úlohy zastaveno a experiment s maximální hodnotou funkce odezvy je brán jako optimum.
V obecný pohled posloupnost akcí potřebných k vyřešení optimalizačního problému pomocí gradientové metody lze prezentovat ve formě vývojového diagramu (obr. 4.4).
1) počáteční úrovně faktorů ( Xj 0) měl by se volit co nejblíže optimálnímu bodu, pokud existují nějaké apriorní informace o jeho poloze;
2) variační intervaly (Δ Xj) musí být zvolen tak, aby byl lineární model pravděpodobně adekvátní. Hranice pod Δ Xj v tomto případě se jedná o minimální hodnotu variačního intervalu, při které zůstává funkce odezvy významná;
3) hodnota kroku ( T) při pohybu po spádu se volí tak, aby největší z produktů nepřesahoval rozdíl mezi horním a nižší úrovně faktory v normalizované podobě
.
Proto, . V nižší hodnotě T rozdíl mezi funkcí odezvy na počáteční úrovni a v bodě se souřadnicemi se může ukázat jako nevýznamný. Na vyšší hodnotu kroku hrozí přestřelení optima funkce odezvy.
Metoda gradientní sestup.
Směr nejstrmějšího klesání odpovídá směru největšího poklesu funkce. Je známo, že směr největšího nárůstu funkce dvou proměnných u = f(x, y) je charakterizován svým gradientem:
kde e1, e2 jsou jednotkové vektory (orts) ve směru souřadnicových os. V důsledku toho bude směr opačný ke gradientu indikovat směr největšího poklesu funkce. Jsou volány metody založené na výběru optimalizační cesty pomocí gradientu spád.
Myšlenka metody gradientního sestupu je následující. Výběr nějakého výchozího bodu
Vypočítáme v něm gradient uvažované funkce. Uděláme krok opačným směrem, než je gradient:
Proces pokračuje, dokud není získána minimální hodnota účelové funkce. Přesně řečeno, konec hledání nastane, když pohyb od získaného bodu jakýmkoli krokem vede ke zvýšení hodnoty účelové funkce. Pokud je uvnitř uvažované oblasti dosaženo minima funkce, pak je v tomto bodě gradient nulový, což může také sloužit jako signál o konci optimalizačního procesu.
Metoda gradientního sestupu má stejnou nevýhodu jako metoda souřadnicového sestupu: v přítomnosti roklí na povrchu je konvergence metody velmi pomalá.
V popsané metodě je nutné vypočítat gradient účelové funkce f(x) v každém optimalizačním kroku:
Vzorce pro parciální deriváty lze získat v výslovně pouze v případě, kdy Objektivní funkce dáno analyticky. V opačném případě se tyto derivace vypočítají pomocí numerické derivace:
Při použití sestupu gradientu v optimalizačních problémech většina výpočtu obvykle připadá na výpočet gradientu účelové funkce v každém bodě trajektorie sestupu. Proto je vhodné počet takových bodů snížit, aniž by došlo k ohrožení samotného řešení. Toho je dosaženo v některých metodách, které jsou modifikacemi sestupu gradientu. Jednou z nich je metoda nejstrmějšího sestupu. Podle této metody se po určení v počátečním bodě směru opačného ke gradientu účelové funkce vyřeší jednorozměrný optimalizační problém minimalizací funkce v tomto směru. Konkrétně je funkce minimalizována:
Chcete-li minimalizovat 
Můžete použít jednu z metod jednorozměrné optimalizace. Můžete se jednoduše pohybovat v opačném směru než je gradient, a to ne o jeden krok, ale o několik kroků, dokud cílová funkce nepřestane klesat. V nově nalezeném bodě se opět určí směr sestupu (pomocí gradientu) a hledá se nový bod minima účelové funkce atd. Při této metodě dochází k sestupu v mnohem větších krocích a gradient funkce se počítá v menším počtu bodů. Rozdíl je v tom, že zde je směr jednorozměrné optimalizace určen gradientem účelové funkce, zatímco souřadnicový sestup se provádí v každém kroku podél jednoho ze souřadnicových směrů.
Nejstrmější metoda sestupu pro případ funkce dvou proměnných z = f(x,y).
Za prvé, je snadné ukázat, že gradient funkce je v daném bodě kolmý k tečně k linii hladiny. V důsledku toho u gradientových metod dochází k sestupu podél normály k rovině. Za druhé, v bodě, ve kterém je dosaženo minima účelové funkce ve směru, se derivace funkce v tomto směru stane nulovou. Ale derivace funkce je nulová ve směru tečně k linii úrovně. Z toho vyplývá, že gradient účelové funkce v novém bodě je kolmý na směr jednorozměrné optimalizace na předchozí krok sestup ve dvou po sobě následujících krocích se provádí ve vzájemně kolmých směrech.
Vektor gradientu je směrován ve směru nejrychlejšího nárůstu funkce v daném bodě. Vektor opačný k gradientu -grad(/(x)) se nazývá antigradient a směřuje ve směru nejrychlejšího poklesu funkce. V minimálním bodě je gradient funkce nulový. Metody prvního řádu, nazývané také gradientové metody, jsou založeny na vlastnostech gradientů. Pokud nejsou žádné další informace, pak z počátečního bodu x (0 > je lepší přejít do bodu x (1) ležícího ve směru antigradientu - nejrychlejší pokles funkce. Volba antigradientu -grad(/( x (^)) v bodě jako směr sestupu x(k získáme iterační proces formuláře
V souřadnicové formě je tento proces napsán takto:
Jako kritérium pro zastavení iteračního procesu můžete použít buď podmínku (10.2) nebo splnění podmínky malého gradientu
Možné je i kombinované kritérium spočívající v současném splnění stanovených podmínek.
Gradientní metody se od sebe liší způsobem volby velikosti kroku A V metodě s konstantním krokem určitý konstantní krok. Docela malý krok a^ zajišťuje snížení funkce, tzn. naplnění nerovnosti
To však může vést k nutnosti provést dostatečné velký počet iterací k dosažení minimálního bodu. Na druhou stranu taky velký krok může způsobit zvýšení funkce nebo vést ke kolísání kolem minimálního bodu. Požadované dodatečné informace pro výběr velikosti kroku, takže metody s konstantním krokem se v praxi používají jen zřídka.
Gradientní metody s proměnnými kroky jsou spolehlivější a ekonomičtější (z hlediska počtu iterací), kdy se velikost kroku nějakým způsobem mění v závislosti na získané aproximaci. Jako příklad takové metody zvažte metodu nejstrmějšího sestupu. V této metodě se při každé iteraci volí velikost kroku i* z podmínky minima funkce f(x) ve směru sestupu, tzn.
Tato podmínka znamená, že k pohybu podél antigradientu dochází tak dlouho, dokud hodnota funkce /(x) klesá. Proto je při každé iteraci nutné řešit problém jednorozměrné minimalizace vzhledem k φ funkce φ(τ) =/(x(/r) - - agrad^x^))). Algoritmus metody nejstrmějšího klesání je následující.
- 1. Stanovme souřadnice počátečního bodu x^° a přesnost přibližného řešení r k = 0.
- 2. V bodě x (/r) vypočítáme hodnotu gradientu grad(/(x (^)).
- 3. Určete velikost kroku a^ jednorozměrnou minimalizací funkce cp(i) vzhledem k i.
- 4. Určeme novou aproximaci k bodu minima x (* +1 > pomocí vzorce (10.4).
- 5. Zkontrolujeme podmínky pro zastavení iteračního procesu. Pokud jsou splněny, výpočty se zastaví. Jinak předpokládáme k k+ 1 a přejděte ke kroku 2.
Při metodě nejstrmějšího klesání se směr pohybu z bodu x (*) dotýká čáry hladiny v bodě x (* +1). Sestupová dráha je klikatá a sousední klikaté spojnice jsou navzájem ortogonální. Opravdu, krok a^ se vybírá minimalizací o A funkce ( A). Předpoklad
minimum funkce - = 0. Po výpočtu derivace
komplexní funkce, získáme podmínku pro ortogonalitu vektorů sestupných směrů v sousedních bodech:
Problém minimalizace funkce φ(π) lze redukovat na problém výpočtu kořene funkce jedné proměnné g(a) =
Gradientové metody konvergují k minimu rychlostí geometrické progrese pro hladké konvexní funkce. Takové funkce mají největší a nejmenší vlastní čísla matice druhých derivací (Hessovy matice)
se od sebe málo liší, tzn. matice H(x) je dobře podmíněná. V praxi však mají minimalizované funkce často špatně podmíněné matice druhých derivací. Hodnoty takových funkcí se v některých směrech mění mnohem rychleji než v jiných. Rychlost konvergence gradientních metod také významně závisí na přesnosti gradientových výpočtů. Ztráta přesnosti, ke které obvykle dochází v blízkosti minimálních bodů, může obecně narušit konvergenci procesu gradientního klesání. Proto se gradientní metody často používají v kombinaci s jinými, více efektivní metody na počáteční fázeřešení problému. V tomto případě je bod x (0) daleko od minimálního bodu a kroky ve směru antigradientu umožňují dosáhnout výrazného poklesu funkce.
Úlohu vyřešíme pomocí kalkulačky. Vezměme si jako libovolnou cestu:Xo = (1,2);(2,3);(3,4);(4,5);(5,1)
Potom F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
K určení spodní hranice množiny použijeme redukční operace nebo zmenšení matice řádek po řádku, pro které je nutné v každém řádku matice D najít minimální prvek.
d i = min(j) d ij
| já j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 90 | 80 | 40 | 100 | 40 |
| 2 | 60 | M | 40 | 50 | 70 | 40 |
| 3 | 50 | 30 | M | 60 | 20 | 20 |
| 4 | 10 | 70 | 20 | M | 50 | 10 |
| 5 | 20 | 40 | 50 | 20 | M | 20 |
Potom odečteme d i od prvků příslušného řádku. V tomto ohledu bude v nově získané matici v každém řádku alespoň jedna nula.
| já j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
Provádíme stejnou redukční operaci podél sloupců, pro které najdeme minimální prvek v každém sloupci:
dj = min(i) d ij
| já j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
| d j | 0 | 10 | 0 | 0 | 0 |
Po odečtení minimálních prvků získáme zcela redukovanou matici, kde hodnoty d i a d j nazýváme odlévací konstanty.
| já j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 40 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 0 | M | 40 | 0 |
| 4 | 0 | 50 | 10 | M | 40 |
| 5 | 0 | 10 | 30 | 0 | M |
Součet redukčních konstant určuje dolní mez H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Prvky matice d ij odpovídají vzdálenosti bodu i k bodu j.
Protože v matici je n měst, pak D je matice nxn s nezápornými prvky d ij >=0
Každá platná trasa představuje cyklus, ve kterém cestující obchodník navštíví město pouze jednou a vrátí se do původního města.
Délka trasy je určena výrazem:
F(M k) = ∑d ij
Navíc je každý řádek a sloupec v trase zahrnut pouze jednou s prvkem d ij .
Krok 1.
Určení hrany větvení
| já j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | 0(40) | 60 | 40 |
| 2 | 20 | M | 0(20) | 10 | 30 | 10 |
| 3 | 30 | 0(10) | M | 40 | 0(30) | 0 |
| 4 | 0(10) | 50 | 10 | M | 40 | 10 |
| 5 | 0(0) | 10 | 30 | 0(0) | M | 0 |
| d j | 0 | 10 | 10 | 0 | 30 | 0 |
d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Největší součet redukčních konstant je (40 + 0) = 40 pro hranu (1,4), proto je množina rozdělena na dvě podmnožiny (1,4) a (1*,4*).
H(l*,4*) = 140 + 40 = 180
Hranu (1,4) odstraníme nahrazením prvku d 14 = 0 M, načež provedeme další redukci matice vzdáleností pro výslednou podmnožinu (1*,4*), ve výsledku získáme redukovaná matice.
| já j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | M | 60 | 40 |
| 2 | 20 | M | 0 | 10 | 30 | 0 |
| 3 | 30 | 0 | M | 40 | 0 | 0 |
| 4 | 0 | 50 | 10 | M | 40 | 0 |
| 5 | 0 | 10 | 30 | 0 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 0 | 40 |
Zahrnutí hrany (1,4) se provádí vyloučením všech prvků 1. řádku a 4. sloupce, ve kterých je prvek d 41 nahrazen M, aby se eliminoval vznik nehamiltonovského cyklu.
Výsledkem je další redukovaná matice (4 x 4), která podléhá operaci redukce.
∑d i + ∑d j = 10
| já j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | 0 | 0 |
| 4 | M | 50 | 10 | 40 | 10 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 10 |
Dolní mez podmnožiny (1,4) se rovná:
H(1,4) = 140 + 10 = 150 ≤ 180
Protože spodní hranice této podmnožiny (1,4) je menší než podmnožina (1*,4*), zahrneme do trasy hranu (1,4) s novou hranicí H = 150
Krok 2.
Určení hrany větvení a rozdělit celou množinu cest vzhledem k této hraně na dvě podmnožiny (i,j) a (i*,j*).
Za tímto účelem u všech buněk matice s nulovými prvky nahradíme nuly po jedné M (nekonečno) a určíme pro ně součet výsledných redukčních konstant, jsou uvedeny v závorkách.
| já j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0(20) | 30 | 20 |
| 3 | 30 | 0(10) | M | 0(30) | 0 |
| 4 | M | 40 | 0(30) | 30 | 30 |
| 5 | 0(30) | 10 | 30 | M | 10 |
| d j | 20 | 10 | 0 | 30 | 0 |
d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Největší součet redukčních konstant je (0 + 30) = 30 pro hranu (3,5), proto je množina rozdělena na dvě podmnožiny (3,5) a (3*,5*).
Dolní mez pro hamiltonovské cykly této podmnožiny je:
H(3*,5*) = 150 + 30 = 180
Hranu (3.5) odstraníme nahrazením prvku d 35 = 0 M, načež provedeme další zmenšení matice vzdáleností pro výslednou podmnožinu (3*,5*), ve výsledku získáme redukovanou matici .
| já j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | M | 0 |
| 4 | M | 40 | 0 | 30 | 0 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 30 | 30 |
Zahrnutí hrany (3.5) se provádí vyloučením všech prvků 3. řádku a 5. sloupce, ve kterých je prvek d 53 nahrazen M, aby se eliminoval vznik nehamiltonovského cyklu.
Výsledkem je další redukovaná matice (3 x 3), která podléhá operaci redukce.
Součet redukčních konstant redukované matice:
∑d i + ∑d j = 10
Po operaci redukce bude redukovaná matice vypadat takto:
| já j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 40 | 0 | 0 |
| 5 | 0 | 10 | M | 0 |
| d j | 0 | 10 | 0 | 10 |
Dolní mez podmnožiny (3.5) se rovná:
H(3,5) = 150 + 10 = 160 ≤ 180
Protože spodní hranice této podmnožiny (3,5) je menší než podmnožina (3*,5*), zahrneme do trasy hranu (3,5) s novou hranicí H = 160
Krok č. 3.
Určení hrany větvení a rozdělit celou množinu cest vzhledem k této hraně na dvě podmnožiny (i,j) a (i*,j*).
Za tímto účelem u všech buněk matice s nulovými prvky nahradíme nuly po jedné M (nekonečno) a určíme pro ně součet výsledných redukčních konstant, jsou uvedeny v závorkách.
| já j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0(20) | 20 |
| 4 | M | 30 | 0(30) | 30 |
| 5 | 0(20) | 0(30) | M | 0 |
| d j | 20 | 30 | 0 | 0 |
d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Největší součet redukčních konstant je (0 + 30) = 30 pro hranu (5,2), proto je množina rozdělena na dvě podmnožiny (5,2) a (5*,2*).
Dolní mez pro hamiltonovské cykly této podmnožiny je:
H(5*,2*) = 160 + 30 = 190
Hranu (5,2) odstraníme nahrazením prvku d52 = 0 M, načež provedeme další zmenšení matice vzdáleností pro výslednou podmnožinu (5*,2*), ve výsledku získáme redukovanou matice.
| já j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 30 | 0 | 0 |
| 5 | 0 | M | M | 0 |
| d j | 0 | 30 | 0 | 30 |
Zahrnutí hrany (5.2) se provádí vyloučením všech prvků 5. řádku a 2. sloupce, ve kterých je prvek d 25 nahrazen M, aby se eliminoval vznik nehamiltonovského cyklu.
Výsledkem je další redukovaná matice (2 x 2), která podléhá operaci redukce.
Součet redukčních konstant redukované matice:
∑d i + ∑d j = 20
Po operaci redukce bude redukovaná matice vypadat takto:
| já j | 1 | 3 | d i |
| 2 | 20 | 0 | 0 |
| 4 | M | 0 | 0 |
| d j | 20 | 0 | 20 |
Dolní mez podmnožiny (5,2) se rovná:
H(5,2) = 160 + 20 = 180 ≤ 190
Protože spodní hranice této podmnožiny (5,2) je menší než podmnožina (5*,2*), zahrneme do trasy hranu (5,2) s novou hranicí H = 180
V souladu s touto maticí zařazujeme do hamiltonovské cesty hrany (2,1) a (4,3).
Výsledkem je, že podél větveného stromu hamiltonovského cyklu tvoří hrany:
(1,4), (4,3), (3,5), (5,2), (2,1),
Délka trasy je F(Mk) = 180
Níže je uveden stav problému a textová část řešení. Celé řešení je ve formátu doc v archivu si můžete stáhnout. Některé znaky se na stránce nemusí objevit, ale wordový dokument vše je zobrazeno. Další příklady práce na EMMM si můžete prohlédnout
FORMULACE PROBLÉMU
Nakladatelství musí do týdne (počet dní m = 5) dokončit psaní na stroji za pomoci pracovníků n kategorií (vysoká, průměrná, podprůměrná, nízká). Je třeba stanovit optimální počet zaměstnanců podle kategorií, který zajistí dokončení práce s minimálním vynaložením mzdového fondu za daných omezení. Počáteční údaje jsou uvedeny v tabulkách 1 a 2.
stůl 1
tabulka 2
Úlohu je třeba vyřešit pomocí celočíselné metody lineární programování v Mathcadu 2000/2001.
SESTAVENÍ MATEMATICKÉHO MODELU
ŘEŠENÍÚKOLY
Pro výpočet optimálního počtu zaměstnanců, který zajistí minimální výdaje mzdového fondu, a matematický model celočíselné lineární programování, protože počet zaměstnanců nemůže být zlomková hodnota.
Řešení celočíselného programovacího problému se provádí ve dvou fázích.
V první fázi je proveden problém lineárního programování bez zohlednění celého čísla.
Ve druhé fázi se vyrábí proces krok za krokem nahrazení neceločíselných proměnných nejbližšími horními nebo dolními celočíselnými hodnotami.
Nejprve je problém vyřešen bez zohlednění celočíselné podmínky.
Účelová funkce je určena vzorcem:
Kde Q- všeobecný platový fond za výkon práce;
X 1 , X 2 , …, x n- počet zaměstnanců podle kategorií;
n - počet kategorií pracovníků;
C 1 , C 2 ,…, c n- během dne tarifní sazba jeden zaměstnanec podle kategorie;
m- počet pracovních dnů v týdnu, m = 5.
Cílovou funkci lze zapsat ve vektorové podobě:
Při řešení problémů je třeba splnit následující: následující omezení. Horní limit
X ≤ d (1)
udává maximální počet zaměstnanců podle kategorie, kde d je vektor, který určuje počet zaměstnanců podle kategorie.
V omezení
bere se v úvahu, že celkový počet zaměstnanců by neměl překročit k max.
V omezení zdola
R× x≥P(3)
odráží se, že všichni pracovníci společně musí dokončit dané množství práce R.
Jako poslední omezení je napsána podmínka nezápornosti vektoru proměnných
X≥0 (4)
Matematický model pro řešení problému bez zohlednění celočíselné podmínky obsahuje následující výrazy:
X ≤ d
R× x≥P,
X ≥ 0 .
Model celočíselného programování musí obsahovat také výrazy (5). dodatečná omezení, s jehož pomocí neceločíselné proměnné X jsou nahrazeny celočíselnými hodnotami. Konkrétní modelové výrazy s celočíselnými proměnnými jsou diskutovány v další podkapitole.
ŘEŠENÍ PROBLÉMU OPTIMALIZACE VMATHCAD
Zdrojová data pro příklad jsou uvedena v tabulce. 1 a 2.
K vyřešení problému použijte balíček Mathcad s funkcí Minimize. Tato funkce určuje vektor řešení problému:
X:= Minimalizovat ( Q, X),
Kde Q— vyjádření objektivní funkce, která určuje fond minimální mzdy, X- vektor proměnných.
Nejprve je problém vyřešen bez zohlednění celočíselné podmínky. Toto řešení je uvedeno v příloze 1. První řádek obsahuje nulové počáteční hodnoty vektoru X a objektivní funkce Q(X) . Za slovem Dan a před funkcí Minimize jsou uvedena omezení. V důsledku toho bylo získáno neceločíselné optimální číslo podle kategorie:
X =
s platovým fondem Q= 135 cu. E.
Z toto rozhodnutí nachází se celočíselné řešení metoda větvení a vazby.
Výsledný roztok nejprve analyzuje zlomkovou hodnotu x 4 =
= 1,143. Můžete pro něj nastavit dvě celočíselné hodnoty: x 4 = 1 a x 4 = 2. Začíná konstrukce rozhodovacího stromu (Příloha 2). Počáteční nulový uzel je v rozhodovacím stromě vyčleněn. Poté je spojen prvním uzlem x4 a z tohoto uzlu jsou vykresleny dvě větve odpovídající omezením: x4 = 1 a x4 = 2.
Pro větev s omezením x 4 = 1 je vyřešen problém lineárního programování uvedený v Příloze 1 s přihlédnutím k tomuto omezení.
Výsledkem bylo řešení tohoto problému. Proměnná x 1 se stala celým číslem, ale proměnná x 2 se stala zlomkem x 2 = 0,9.
Pro pokračování větvení se vytvoří uzel x 3 a větev x 3 = 1. Úloha lineárního programování se opět provede se všemi třemi omezeními: x 4 = 1, x 2 = 1, x 3 = 1. S těmito omezeními se úloha má řešení x T =
= (1,938 1 1 1).
Pro pokračování větvení se vytvoří uzel x 1 a větev x 1 = 2. Úloha lineárního programování se provede znovu se všemi třemi omezeními: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2. S těmito omezeními má problém řešení x T = = (2 1 1 1).
Proces konstrukce stromu řešení a provádění úlohy lineárního programování se opakuje, dokud nejsou vytvořeny všechny větve.
Příloha 2 poskytuje úplný strom možných celočíselných řešení, z něhož vyplývá, že úloha má 4 efektivní řešení.
Nejlepší je vybrán z efektivních a je akceptován jako optimální celočíselné řešení celého problému s minimální hodnotou Q(X) . V našem případě máme dvě optimální celočíselná řešení
Q(X) = 140,
x T = (2 1 1 1),
x T = (1122).
V důsledku toho musí vydavatelská organizace najmout dva vysoce kvalifikované pracovníky pro psaní textu, jednoho pracovníka střední kategorie, jeden pracovník podprůměrné kategorie a jeden pracovník nízké kategorie. Je možná i jiná rovnocenná možnost přilákání pracovníků: jeden pracovník vysoké kategorie, jeden pracovník střední kategorie, dva pracovníci podprůměrné kategorie a dva pracovníci nízké kategorie. V obou variantách budou náklady minimální a budou činit 140 den. Jednotky
Stáhněte si řešení problému:
Název souboru: 2.rar
Velikost souboru: 24,99 Kb
Pokud stahování souboru nezačne po 10 sekundách, klikněte na
