Metody operačního výzkumu cvičení

Metody operačního výzkumu cvičení

Opakování vektorové algebry – domácí úkol 1) Pojem vektorového prostoru – praktická aplikace - je tvořen všemi vektory dané dimenze - operace s vektory (součin, sčítání, násobení vektoru skalární hodnotou) 2) Vektor – význam, aplikace 3) Lineární kombinace vektorů – záměna vektorů - a = (2, 3) ca = 5 0,4 - lineární konvexní kombinace - součet = 1 a musí b = (5, 6) cb = -1 0,6 být mezi 0 a 1 c = (5, 9) -všechny lineární konvexní 4 kombinace 2 vektorů 4) Báze vektorového prostoru 3 - množina vektorů - vektory jsou lineárně nezávislé 2

5

Soustavy lineárních rovnic Květák a kedlubny Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a kedlubny. Pro květák však lze využít nejvýše 8 arů. Předpokládá, že se mu podaří dosáhnout z jednoho aru květáku tržby ve výši 5 000 Kč a z jednoho aru kedluben 2 000 Kč. Požaduje celkovou výši tržeb alespoň ve výši 50 000 Kč. Výměry jednotlivých plodin musí být takové, aby minimalizovali celkové náklady, přitom na jeden ar květáku budou náklady asi 2 000 Kč a na jeden ar kedluben 1 000 Kč. 1) Sestavte vhodný model – definujte proměnné, omezující podmínky a účelovou - kriteriální funkci - proměnné: x1 ... květák (ar) x2 ... kedlubna (ar) - omezující podmínky: x1 ≤ 8 x1 + x2 ≤ 35 5x1 + 2x2 ≥ 50 - kriteriální funkce: z = 2x1 + x2 -> min 2) Upravte model do rovnicového tvaru d1 ... doplňková proměnná x1 + d1 = 8 x1 + x2 + d2 = 35 5x1 + 2x2 - d3 = 50 3) Frobeniova věta

-1-

Christy


4) Určete bázické řešení a bázické vektory x1 x2 d1 d2 d3 1 0 1 0 0 1 1 0 1 0 5 2 0 0 -1

⎛1 0 1 0 0 8 ⎞ ⎜ ⎟ ⎜ 1 1 0 1 0 35 ⎟ ⎜ 5 2 0 0 − 1 50 ⎟ ⎝ ⎠

b 8 35 50

⎞ ⎟ 0 8⎟ 1 0 0 1 10 ⎟ ⎟ 2 ⎟ 1 1 0 0 − 25 ⎟ 2 ⎠

⎛ ⎜ ⎜ 1 ⎜− 1 ⎜ 2 ⎜ 5 ⎜ ⎝ 2

~

úplná jednotková submatice

0 1 0

5 1 x1 + x 2 − d 3 = 25 2 2

x1 d1 d2 x2

x2 1 3 − 2 5 2

d1 0

d2 1

d3 0

0

0

1

1

0

0

b 0 1 2 1 − 2

x1 = 0 8

d1 = 8 x2 = 25 d2 = 10

10

d3 = 0

25

- hodnoty nebázických proměnných vždy pokládáme = 0 - hodnoty bázických proměnných dáváme rovno b 5) Určete parametrické řešení a možnou hodnotu některé proměnné x1 = 5 d1 = 3 d3 = 0 x2 = 12/5 d2 = 35/2 6) Vypočítejte sousední řešení pomocí Jordanovy eliminační metody (5 nad 3) = 10 bázických proměnných d1 1 0 1 0 0 8 d2 1 1 0 1 0 35 d3 -5 -2 0 0 1 -50 7) Vypočítejte sousední řešení pomocí matice transformace B-1

Důležité pojmy vektorový prostor, vektor, skalár, lineární kombinace vektorů, lineární závislost a nezávislost vektorů, báze vektorového prostoru, Jordanova eliminační metoda, řídící řádek, řídící prvek – pivot, matice transformace, kanonický tvar soustavy, bázické řešení, parametrické řešení, hodnoty proměnných Jordanova eliminační metoda skalární součin násobení maticí, inverzní matici -2-

Christy


MOV 03 – cvičení 2 Konstrukce a vlastnosti lineárního modelu, grafické řešení Květák a kedlubny Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a kedlubny. Pro květák však lze využít nejvýše 8 arů. Předpokládá, že se mu podaří dosáhnout z jednoho aru květáku tržby ve výši 5 000 Kč a z jednoho aru kedluben 2 000 Kč. Požaduje celkovou výši tržeb alespoň ve výši 50 000 Kč. Výměry jednotlivých plodin musí být takové, aby minimalizovali celkové náklady, přitom na jeden ar květáku budou náklady asi 2 000 Kč a na jeden ar kedluben 1 000 Kč. 1) Sestavte vhodný model – definujte proměnné, omezující podmínky a účelovou - kriteriální funkci x1 ... květák (ar) x2 ... kedlubna (ar) x1 ≤ 8 x1 + x2 ≤ 35 5x1 + 2x2 ≥ 50 x1,2 ≥ 0 2) Vyřešte jej graficky v prostoru řešení nebo prostoru požadavků. prostor řešení: dvourozměrný zobrazujeme množinu přípustných řešení prostor požadavků: třírozměrný požadavkový vektor - požadavky (vlastnosti) proměnné řeší se skládáním vektorů v tomto případě: požadavkové vektory - 3 složky -> 3 podmínky 2 složky -> 2 proměnné graf: tím, že namalujeme I. kvadrant vyřešíme podmínky nezápornosti dosazuji za x1 a x2, abych dostala dvojici bodů kriteriální funkce z = 2x1 + x2 -> min gradient vektor -> parciální derivace - 2 nad 1 3) Ilustrujte na grafickém znázornění tohoto modelu vlastnosti lineární úlohy. slovní vysvětlení řešení: květák 8 arů kedlubny 5 arů tržby jsou právě požadované, protože řešení leží na ?omezující podmínce

Krmná dávka pro skot Předpokládejte, že krmná dávka bude složena ze dvou základních složek tak, aby při splnění požadovaného obsahu živin byla co nejlevnější. Potřebné údaje jsou v následujících tabulkách (jednotky pro obsah ŠJ jsou kg/kg a pro obsah SNL g/kg).

-3-

Christy


Živiny v krmivu Krmný ječmen Zelená píce Seno víceletých Seno jednoletých Kukuřičná siláž Senáž víceletých Kukuřičné úsušky

Obsah ŠJ 0,705 0,113 0,363 0,35 0,134 0,197 0,499

Obsah SNL 74 20 73 68 12 44 32

Cena 2,9 0,37 0,85 0,8 0,45 0,67 2,73

ŠJ 5,4 1,3 2,8 4,1

SNL 842 270 470 650

Živiny v KD Dojnice 500 kg, 10 l Telata 80 kg Jalovice 300 kg Skot ve výkrmu 400 kg

1) Sestavte vhodný model – definujte proměnné, omezující podmínky a účelovou funkci x1 ... krmný ječmen kg x2 ... zelená píce kg x3 ... seno víceletých kg x4 ... seno jednoletých kg x5 ... kukuřičná siláž kg x6 ... senáž víceletých kg x7 ... kukuřičné úsušky kg 2 omezující podmínky 0,705x1+0,113x2 + 0,636x3 + 0,35x4 + 0,134x5 + 0,197x6 + 0,499x7 = 2,8 74x1 + 20x2 + 73x3 + 68x4 + 12x5 + 44x6 + 32x7 = 470 kriteriální funkce 2,9x1 + 0,37x2 + 0,85x3 + 0,8x4 + 0,45x5 + 0,67x6 + 2,73x7 -> MIN x1 ... x7 ≥ 0 2) Vyřešte jej graficky v prostoru řešení nebo prostoru požadavků. 7 požadavkových vektorů o 2 složkách bude se řešit v prostoru požadavků (7 rozměrný prostor) skládáme vektory tak, abychom dostali vektor pravých stran musíme zjistit kolik které krmivo obsahuje živin za 1 Kč Živiny v krmivu Krmný ječmen Zelená píce Seno víceletých Seno jednoletých Kukuřičná siláž Senáž víceletých Kukuřičné úsušky Živiny v KD Dojnice 500 kg, 10 l Telata 80 kg Jalovice 300 kg Skot ve výkrmu 400 kg

Obsah ŠJ 0,705 0,113 0,363 0,35 0,134 0,197 0,499

Obsah SNL 74 20 73 68 12 44 32

ŠJ 5,4 1,3 2,8 4,1

SNL 842 270 470 650

Cena 2,9 0,37 0,85 0,8 0,45 0,67 2,73

0,243103 0,305405 0,427059 0,4375 0,297778 0,29403 0,182784

25,51724 54,05405 85,88235 85 26,66667 65,67164 11,72161

->

0,56

94

-4-

Christy


100 90 80 70 60

Řada1

50

Řada2

40 30 20 10 0 0

0,1

0,2

0,3

0,4

0,5

0,6

3) Ilustrujte na grafickém znázornění tohoto modelu vlastnosti lineární úlohy. Důležité pojmy lineární optimalizační model, omezující podmínky, účelová – kriteriální funkce, prostor řešení, množina přípustných řešení,množina optimálních řešení, konvexní polyedr, polyedrický kužel, prostor požadavků, aktivita, lineární kombinace vektorů

MOV 04 – cvičení 3 Simplexový algoritmus Květák a kedlubny Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a kedlubny. Pro květák však lze využít nejvýše 8 arů. Předpokládá, že se mu podaří dosáhnout z jednoho aru květáku tržby ve výši 5 000 Kč a z jednoho aru kedluben 2 000 Kč. Požaduje celkovou výši tržeb alespoň ve výši 50 000 Kč. Výměry jednotlivých plodin musí být takové, aby minimalizovali celkové náklady, přitom na jeden ar květáku budou náklady asi 2 000 Kč a na jeden ar kedluben 1 000 Kč. 1) Sestavte vhodný model – definujte proměnné, omezující podmínky a účelovou - kriteriální funkci (viz cvičení 2) x1 ... květák (ar) x2 ... kedlubna (ar) x1 ≤ 8 x1 + x2 ≤ 35 5x1 + 2x2 ≥ 50 z = 2x1 + x2 -> min x1,2 ≥ 0 2) Upravte omezující podmínky do rovnicového kanonického tvaru. x1 + d1 = 8 x1 + x2 + d2 = 35 5x1 + 2x2 - d3 + p3 = 50 z = 2x1 + x2 + 0d1 + 0d2 + 0d3 + 10p3 -> min - v účelové funkci má doplňková proměnná vždy hodnotu 0, 10p3 je vymyšlené a má být o řád vyšší (v případě min) -5-

Christy


x1 ⎛1 ⎜ ⎜1 ⎜5 ⎝

x2 d1 d2 d3 p3 b 0 1 0 0 0 8⎞ ⎟ 1 0 1 0 0 35 ⎟ 2 0 0 − 1 1 50 ⎟⎠

d1, d2, p3 ... bázické proměnné

3) Vypište výchozí řešení omezujících podmínek a určete hodnotu kriteriální funkce. x1 = 0 x2 = 0 d1 = 8 d2 = 35 d3 = 0 p3 = 50 z = 500 4) Vypište alespoň jedno parametrické řešení omezujících podmínek a určete jak se změní hodnota kriteriální funkce. x1 = 2 - x1 zvolím a dosazuji do matice x2 = 0 d1 = 6 d2 = 33 d3 = 0 p3 = 40 z = 404 5) Jsou splněny předpoklady simplexového algoritmu? předpoklady: - kanonický tvar soustavy - na pravé straně nezáporné hodnoty 0x1 + 0x1 + 10x5 = 50 - 2 = 48 2 1 0 1 0 0 1 1 10 5 2 48 19

0 1 0 0 0

0 0 10 0 0 0 8 d1 1 0 0 35 d2 0 − 1 1 50 p3 - zj-cj když budou v posledním řádku samá záporná čísla a 0 − 10 0 500 nuly nelze už řešení zlepšit - účelový sloupec - x1 protože 48 zlepší hodnotu kriteriální funkce o 48 jednotek - test přípustnosti: 8/1, 35/1, 50/5 - klíčový řádek (je nejnižší číslo) - klíčový prvek - průsečík účelového sloupce s klíčovým řádkem 2 x1 1 0 1 0 0 0 8

0 d 2 0 1 − 1 1 0 0 27 - test optimality, test přípustnosti až do opt. řešení 10 p3 0 2 − 5 0 − 1 1 10 zj-cj 0 19 -48 0 -10 0 116 - toto řešení také není optimální kvůli 19 - klíčový řádek p3 19, klíčový sloupec 10/2, klíčový prvek 2 2 x1 1 0 1 0 0 0 8 0 d2 0 0 3/2 1 1/2 -1/2 22 1 x2 0 0 -5/2 0 -1/2 1/2 5 zj-cj 0 0 -1/2 0 -1/2 -9,5 21 - toto řešení je optimální květák pěstuji na 8 ar, kedlubny na 5 ar, 22 je nevyužitá orná půda

-6-

Christy


6) Vyřešte tento model pomocí simplexové metody s penalizací pomocných proměnných. 7) Na kolika arech má být pěstován květák a kedlubny má v následujícím období, aby bylo dosaženo minimálních nákladů? Důležité pojmy simplexový algoritmus, test optimality, test přípustnosti, bázické a nebázické proměnné, strukturní, doplňkové a pomocné proměnné, kanonický tvar soustavy lineárních rovnic, bázické řešení, přípustné a nepřípustné řešení, optimální řešení

MOV 04 – cvičení 4 Rozbor a analýza výsledků lineárního modelu Květák a kedlubny Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a kedlubny. Pro květák však lze využít nejvýše 8 arů. Předpokládá, že se mu podaří dosáhnout z jednoho aru květáku tržby ve výši 5 000 Kč a z jednoho aru kedluben 2 000 Kč. Požaduje celkovou výši tržeb alespoň ve výši 50 000 Kč. Výměry jednotlivých plodin musí být takové, aby minimalizovali celkové náklady, přitom na jeden ar květáku budou náklady asi 2 000 Kč a na jeden ar kedluben 1 000 Kč. 8) Sestavte a vyřešte vhodný model (viz cvičení 2 a 3) d1 d2 p3

2 x1 1 1 5

1 x2 0 1 2

0 d1 1 0 0

0 d2 0 1 0

2 x1 0 d2 1 x2 zj - cj

1 0 0 0

0 0 1 0

1 3/2 -5/2 -1/2

0 1 0 0

0 0 10

0 d3 0 0 1

10 p3 0 0 1

b 8 35 50

0 0 8 1/2 -1/2 22 -1/2 1/2 5 -1/2 -19/2 21

9) Analyzujte optimální řešení - na kolika arech má být pěstován květák a kedlubny v následujícím období, aby bylo dosaženo minimálních nákladů? 10) Popište informace v simplexové tabulce. Najděte a popište matice B a B-1. - cena výrobního programu by byla 21000 Kč 0 0 ⎞ ⎛1 0 0⎞ ⎛ 1 ⎟ ⎟ ⎜ ⎜ −1 B = ⎜ 3 / 2 1 − 1/ 2 ⎟ B = ⎜1 1 1⎟ ⎜5 0 2⎟ ⎜ − 5 / 2 0 1/ 2 ⎟ ⎠ ⎠ ⎝ ⎝

11) Existuje alternativní řešení? - ne - kdyby bylo na výsledném řádku víc nul než optimálních řešení, tak by existovalo

-7-

Christy


12) Navrhněte vhodné suboptimální řešení. d1 = 1 - zvolili jsme si x1 = 7 d2 = 20,5 x2 = 7,5 zj - cj = 21,5 13) Jak bude vypadat optimální řešení, uvolníme-li omezení pro výměru květáku? ⎛ 35 ⎞ ⎜ ⎟ −1 B ⋅ b = ⎜ 62,5 ⎟ (b = 35, 35, 50) ⎜ − 62,5 ⎟ ⎝ ⎠ (b = 8 + μ1, 35, 50) 8 + μ1 ≥ 0 3/2(8 + μ1) + 35 - 25 ≥ 0 -5/2(8 + μ1) + 25 ≥ 0 μ1 є <-8; 2> b1 є <0; 10>

-5/2(8 + μ1) + 25 ≥ 0 -20 - 2,5 μ1 + 25 ≥ 0 2,5 μ1 ≤ 5 μ1 ≤ 2

14) Jak bude vypadat řešení, jestliže očekáváme změnu nákladů kedluben? 0 0 10

d1 d2 p3

2 x1 0 d2 1+α2 x2 zj - cj

2 1+α2 0 x1 x2 d1 1 0 1 1 1 0 5 2 0 1 0 0 0

0 0 1 0

1 3/2 -5/2 -1/2

0 d2 0 1 0 0 1 0 0

0 d3 0 0 1

10 p3 0 0 1

b 8 35 50

0 0 8 1/2 -1/2 22 -1/2 1/2 5 -1/2 -19/2 21

2.1 + (1 + α2) . -5/2 ≤ 0 -1/2 . (1 + α2) ≤ 0 α2 є <-0,2; ∞> c2 є <0,8; ∞>

Důležité pojmy optimální řešení, alternativní řešení, suboptimální řešení, vektor bázického řešení, vektor obecného řešení, interval stability hodnot proměnných, interval stability změn pravých stran, interval stability změn koeficientů účelové funkce, interval stability hodnot proměnných, analýza stability, parametrizace

-8-

Christy


MOV 04 – cvičení 5 Duální simplexový algoritmus Výroba Mozzarelly Carlo Pontini z Piacenze je výrobce sýrů Mozzarella. Každý den ráno se rozhoduje kolik z připravené sýrové hmoty má zpracovat na trvanlivou Mozzarellu zapečetěnou ve vosku. Sýrová hmota zraje v nádobách o kapacitě 30 kg. Může vyrábět ve tří formách. 1. Mozzarella „Spaghetti“ Na jeden kus spotřebuje 0,5 kg sýrové hmoty. Denně prodá vždy alespoň 200 ks. 2. Mozzarella „Boccia“ Na jeden kus spotřebuje 1 kg sýrové hmoty. Denně prodá vždy alespoň 50 ks. 3. Mozzarella „Rullo“ Na jeden kus spotřebuje 2,5 kg sýrové hmoty. Denně prodá vždy alespoň 20 ks. Z technologických důvodů může hmotu obsaženou v jedné nádobě použít: 1. Z jedné třetiny na výrobu Mozzarella „Spaghetti“, další třetinu na Mozzarella „Boccia“ a zbytek na Mozzarella „Rullo“. Při tomto technologickém postupu jsou náklady na zpracování jedné nádoby 25 EUR. 2. Třetinu na Mozzarella „Spaghetti“ a současně zbytek na výrobu Mozzarella „Boccia“ Při tomto technologickém postupu jsou náklady na zpracování jedné nádoby 20 EUR. 3. Polovinu na Mozzarella „Boccia“ a současně zbytek na výrobu Mozzarella „Rullo“ Při tomto technologickém postupu jsou náklady na zpracování jedné nádoby 15 EUR. Kolik nádob se sýrovou hmotou má použít na denní produkci, jestliže chce minimalizovat své náklady. Úkoly: 15) Sestavte vhodný primární model – definujte proměnné, omezující podmínky a účelovou kriteriální funkci k s P1 P2 P3 x1 ... postup 1 (počet nádob) š 20 20 0 x2 ... postup 2 (počet nádob) b 10 20 15 x3 ... postup 3 (počet nádob) r

4

6

20x1 + 20x2 ≥ 200 10x1 + 20x2 + 15x3 ≥ 50 4x1 + 6x3 ≥ 20 z - 25x1 + 20x2 + 15x3 -> MIN x1,2,3 ≥ 0

-9-

Christy


0 0 0 20 0 0 20 0 25

d1 d2 d3 zj-cj x2 d2 d3 zj-cj x2 d2 x1 zj-cj

25 x1 -20 -10 -4 -25 1 10 -4 -5 0 0 1 0

20 x2 -20 -20 0 -20 1 0 0 0 1 0 0 0

15 0 0 0 x3 d1 d2 d3 0 -1 0 0 -15 0 -1 0 -6 0 0 1 -15 0 0 0 0 -1/20 0 0 -15 -1 1 0 -6 0 0 1 -15 -1 0 0 -1,5 -1/20 0 1/4 -30 -1 1 2,5 1,5 0 0 -0,3 -7,5 -1 0 -1,25

b -200 -50 -20 0 10 150 -20 200 5 100 5 225

největší nejzápornější

výsledný řádek/vybraný řádek

16) Sestavte duální model 17) Přesvědčete se o splnění podmínek pro duální simplexový algoritmus 18) Vyřešte pomocí duálního simplexového algoritmu 19) Interpretujte výsledné řešení Důležité pojmy Dualita, duálně sdružené modely, primární a duální přípustnost řešení, duální simplexová metoda, test optimality, test přípustnosti

MOV 04 – cvičení 6 Kvadratické programování Květák a kedlubny Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a kedlubny. Pro květák však lze využít nejvýše 8 arů. Je zde však problém s náklady. Zemědělec ví, že se náklady na produkci těchto dvou komodit skládají ze dvou částí: z nákladů fixních, a to ve výši 100 Kč na jeden ar, které musí vynaložit, ať už na té půdě pěstuje jednu z těchto plodin nebo ne. K tomu se ještě přidává variabilní složka nákladů, které progresivně rostou vzhledem k obdělávané výměře. U květáku rostou přibližně podle funkce N1 = 0,25 x12-3x1, u kedluben zhruba podle funkce N2 = x22-4x2, kde x1,2 jsou výměry plodin. Úkoly: 20) Sestavte vhodný model – definujte proměnné, omezující podmínky a účelovou - kriteriální funkci x1 ... květák (ar) x2 ... kedlubny (ar) x1 + x2 ≤ 35 x1 ≤ 8 - 10 -

Christy


35.100 + 0,25x12 - 3x1 + x22 - 4x2 -> MIN X1,2,3 ≥ 0 21) Sestavte Lagrangeovu funkci L(x,u) = f(x) + uT.q(x) f(x) - kriteriální funkce u - lagrangeovy multiplikátory q(x) - omezující podmínky L(x1,x2,u1,u2) = 35.100 + 0,25x12 - 3x1 + x22 - 4x2 + u1.(x1 + x2 - 35) + u2 (x1 - 8) 22) Určete Kuhn-Tuckerovy podmínky. 1) x1,2 > 0 u1,2 > 0 ∂L 2) = x1 + x 2 − 35 ≤ 0 ∂u1 ∂L = x1 − 8 ≤ 0 ∂u 2 ∂L 3) = 0,5 x1 − 3 + u1 + u 2 ≥ 0 ∂x1 ∂L = 2 x 2 − 4 + u1 ≥ 0 ∂x 2 4) u1(x1 + x2 - 35) = 0 u2(x1 - 8) = 0 5) x1(0,5x1 - 3 + u1 + u2) = 0 x2(2x2 - 4 + u1) = 0

x1 + x2 + y1 = 35 x1 + y2 = 8 0,5x1 + u1 + u2 - v1 = 3 2x2 + u1 - v2 = 4 u1.y1 = 0 u2.y2 = 0 x1.v1 = 0 x2.v2 = 0

23) Určete Wolfeho podmínky 24) Jaké je omezení vstupu proměnných do báze? 25) Vyřešte model pomocí Wolfeho algoritmu 26) Interpretujte výsledné řešení Důležité pojmy Konvexní kvadratický model, Lagrangeova funkce, sedlový bod, Kuhn-Tuckerovy podmínky, Wolfeho podmínky, Wolfeho algoritmus, řízení vstupu proměnných do báze.

MOV 04 – cvičení 8 II. Optimalizace jednostupňového dopravního systému Seníky Ze tří velkokapacitních seníků je třeba zásobovat 4 objektů živočišné výroby. Vzdálenosti mezi seníky a objekty živočišné výroby jsou zadány v následující tabulce (tři trasy není možné pro zásobování využívat). Jsou známy i kapacity seníků a předpokládané požadavky živočišné výroby. Najděte optimální způsob zásobování senem a proveďte rozbor výsledků. - 11 -

Christy


Kapacity seníků Svojšovice 2513 t Nevelice 1620 t Líbeznice 980 t

Požadavky objektů ŽV Novín 620 t Litovel 490 t Čejč 810 t Kůty 270 t

Tabulka vzdáleností 1 16 1 21 2 27 3

2 12 20 30

3 11 18

4 11 15 24

Liblice Řepín Nová ves Okoř 5

6 10 7 6

12

380 t 410 t 420 t 750 t 7 40 19 15

8 62 28 24

1) Jestliže není možné některé trasy použít, jak se to projeví v modelu? - dáme tam vysoké číslo jako penalizaci a tím optimalizační model tuto trasu vyřadí 2) Sestavte matematický model pro řešení tohoto problému. - 7 omezujících podmínek xij ... (t) x11 + x12 + x13 + x14 ≤ 2513 u1 x21 + x22 + x23 + x24 ≤ 1620 u2 x31 + x32 + x33 + x34 ≤ 980 u3 x11 + x21 + x31 ≥ 620 v1 x12 + x22 + x32 ≥ 490 v2 x13 + x23 + x33 ≥ 810 v3 x14 + x24 + x34 ≥ 270 v4 z = 16x11 + 12x12 + ... +1000x33 + ... + 24x34 -> MIN xij ≥ 0 3) Sestavte příslušný duální model. u1 + v1 ≤ 16 - u max bude vždy menší nebo rovno, u min to bude naopak u2 + v2 ≤ 20 . . u3 + v4 ≤ 24 z = 2513u1 + 1620u2 + ... + 270v4 ->MAX u1,2,3 ≤ 0 - protože u podmínek je také menší nebo rovno v1,2,3,4 ≥ 0 - protože u podmínek je také větší nebo rovno 4) Najděte výchozí řešení modelu. - model není vyvážený proto vytvoříme fiktivního odběratele, kterému přiřadíme zbývající množství Metoda severozápadního rohu O1 S1 S2 S3 bj

O2 16

620

O3

490 21

-

30 -

620

15 -

0 1620

100 -

490

0 323

18 -

27

11 270

20

24 -

810

ai

Ofikt

11 810

-

-

O4

12

270 - 12 -

0 980 2923

2513 1620 980

Christy


- bázické proměnné - x11, x12, x13, x14, x15, x25, x35 - omezujících podmínek je 8 (všechny sloupečky i řádky) - bázických proměnných je jiný počet než omezujících podmínek -> degenerativní řešení Vogelova aproximační metoda O1 O2 O3 O4 16 12 11 S1 620 490 810 270 21 20 18 S2 27 30 100 S3 bj 620 490 810 270 diference 5 8 7

Ofikt 11

ai 0

323 15

0 1620

24

0 980 2923

4

2513 1620

11 15 24

980

0

- diference - rozdíl mezi nejmenší a druhou nejmenší hodnotou - vybereme nejmenší diferenci - diference musíme přepočítávat - když jsme udělali řádek s 24 tak to musíme přepočítat (tady to náhodou vyšlo stejně) - oba způsoby řešení nemusí vyjít stejně - opět je to jen náhoda Důležité pojmy Dopravní model, vyváženost, degenerace, dualita, výchozí řešení, test optimality, test přípustnosti, uzavřené okruhy, lineární závislost tras

MOV 04 – cvičení 9 Optimalizace jednostupňového dopravního systému a analýza výsledků řešení Seníky Ze tří velkokapacitních seníků je třeba zásobovat 11 objektů živočišné výroby. Vzdálenosti mezi seníky a objekty živočišné výroby jsou zadány v následující tabulce (tři trasy není možné pro zásobování využívat). Jsou známy i kapacity seníků a předpokládané požadavky živočišné výroby. Najděte optimální způsob zásobování senem a proveďte rozbor výsledků. Kapacity seníků Svojšovice 2513 t Nevelice 1620 t Líbeznice 980 t Tabulka vzdáleností 1 16 1 21 2 27 3

Požadavky objektů ŽV Novín 620 t Litovel 490 t Čejč 810 t Kůty 270 t 2 12 20 30

3 11 18

4 11 15 24

Liblice Řepín Nová ves Okoř 5

12

6 10 7 6

380 t 410 t 420 t 750 t 7 40 19 15

8 62 28 24

1) Sestavte matematický model pro řešení tohoto problému a vyřešte jej (viz cvičení 7). - 13 -

Christy


Indexová metoda O1

O2 16

S1

12 89

620 -5

O3

Ofikt

11 4

490

11 -

+ 100 20 82

21 -8

O4

2513

0

1620

0

980

0

15 18

15 270

0 1350

12 27 -18

100 30 100 -9 24 + 0 810 170 12 15 810 270 2923 490 12 100 15 0

S3 16 bj vj

ui

0 1403

S2 16 -11

ai

620 16

Test optima 1. bude se týkat obsazených polí xij > 0 c'ij

cij

xij ui+vj

Qij

- někde zvolím 0 - je jedno kde c11 = 16 u1 + v1 = 16 u1 = 0 0 + v1 = 16 v1 = 16 2. bude se týkat neobsazených polí xij = 0 c’ij = ui + vj - cij c’ij < 0 => řešení je optimální c’ij = 0 => existuje alternativní řešení c’ij > 0 => řešení není optimální a je třeba pokračovat změnou báze k optimálnímu t = min (xij-) = min (1403; 810) = 810 O1

O2 16

S1

620 -5

O3 12

490 21 -8

O4

Ofikt

11 4 810

11 +

593

15 18 -

20 -7

S2

15 + 270

16 -11

12 27 -18

11 30 -89 100 -9

24

bj vj

12 620 16

490 12

11 810 11

2513

0

1620

0

980

0

0 980

16

ui

0 1350

S3

ai 0

15 270 15

2923 0

t = 270

- 14 -

Christy


O1

O2 16

S1

12

620 -5

11

490 21 -8

O4

O3

11 270 -4 15

810 20 -7

Ofikt

18

S2 12 27 -18

11 11 30 -89 100 -13

S3 16 bj vj

12 620 16

11 810 11

490 12

11

270 270 11

2513

0

1620

0

980

0

0

24 +

ui

0 323 + 1620

16 -11

ai

0 980 2923 0

2) Kolik tunokilometrů bude vynaloženo na zásobování senem? Jak bude zásobování probíhat? 3) Existuje alternativní řešení? 4) Proveďte analýzu perspektivity tras. Perspektivita c‘ij - určuje zhoršení účelové funkce při přepravě jedné jednotky po suboptimální trase (zhoršení či zlepšení - při MIN zhoršení) xij > 0 , c‘ij = 0 xij = 0 , c’ij = ui + vj - cij - když je tam vysoké číslo tak je trasa málo perspektivní ÚF = 620·16 + 490·12 + 810·11 = 24710 - hodnota účelové funkce - když pojedeme po trase s -4 tak se o tolik zhorší 5) Proveďte analýzu propustnosti tras. Propustnost Qij - maximální množství, které je možné po trase dopravit aniž by došlo ke změně stability báze xij > 0 , Qij = xij xij = 0 , Qij = t O1

O2 16 +

S1

620 3

12 490

21 -

S2 24 -3

O3

ε

O4 11 -

810 20 1

11 270

18

4

15 +

19 19 30 -81 100 -5

27 -10

24

S3 24 bj vj

20 620 16

490 12

19 810 11

Ofikt -8 0

19 270 11

-8 -8 0 1620 -8 -8 0 980 -8 2600 -8

ai

ui

2190

0

1620

8

980

8

m+n-1

m ... počet dodavatelů (řádků) n ... počet odběratelů (sloupců) 3 + 5 - 1 = 7 máme jen 6 proto je tam degenerace

- 15 -

Christy


O1

O2 16

S1

O3 12

620

O4 11

490

11

810

Ofikt -4 0

270

ai

ui

2190

0

1620

4

980

4

-4 -1

21 -4

20 -3

18

20 -7

16 27 -14

30

15

ε

S2

0 1620

15 -85 100 -9

24

S3

0 980

20 bj vj

16 620 16

15 - 11 = 4

15 810 11

490 12

15 270 11

2600 -4

- sloupeček s epsilon a číslo v tom sloupci dole

Důležité pojmy Dopravní model, vyváženost, degenerace, perspektivita, propustnost, substituce tras

MOV 04 – cvičení 11 Model vícekriteriální optimalizace Květák a kedlubny Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a kedlubny. Předpokládá, že se mu podaří dosáhnout z jednoho aru květáku tržby ve výši 5 000 Kč a z jednoho aru kedluben 2 000 Kč. Požaduje celkovou výši tržeb alespoň ve výši 50 000 Kč. Výměry jednotlivých plodin musí být takové, aby minimalizovali celkové náklady, přitom na jeden ar květáku budou náklady asi 4 000 Kč a na jeden ar kedluben 1 000 Kč a zároveň maximalizovali výměru květáku.

Řešení 1. Sestavte vhodný model x1 + x2 ≤ 35 5x1 + 2x2 ≥ 50 z1 = 4x1 + x2 -> MIN z2 = x1 -> MAX x1,2 ≥ 0 2. Určete dílčí (parciální) optimální řešení a určete ideální a bazální variantu. obr x1 par. z1 0 par. z2 35 Nmax = 55 13,75

x2 25 0 0

z1 25 140 55

z2 0 35 13,75

I = (25; 35) - nejlepší varianta ze sloupců z B = (140; 0) - bazální řešení - nejhorší varianty 3. Nalezněte řešení s využitím nákladů jako omezující podmínky s požadavkem nepřekročení hranice 55 tis. Kč resp. 35 tis. Kč. - 16 -

Christy


4x1 + x2 ≤ 55 4. Použijte metodu cílového váženého programování s požadavkem Min n1 + p2 z1 = 50 z2 = 20 4x1 + x2 + d1- - d1+ = 50 - mínus pro nedosažení, plus pro překročení + x1 - d2 - d2 = 20 zc = d1- + d1+ + d2- + d2+ -> MIN x1 par. z1 0 par. z2 35 Nmax = 55 13,75 20 20

x2 25 0 0 20 0

zc = d1+ + d2- -> MIN

z1 25 140 55 100 80

z2 0 35 13,75 20 20

Zc 0 20

5. Nalezněte řešení pomocí součtové agregace kritérií s váhami 1:1 a 1:10. z1 = 4x1 + x2 -> MIN - „náklady“ z2 = x1 -> MAX - „tržby“ zA = -3x1 - x2 -> MAX - „zisk“ = 3x1 + x2 -> MIN - přebere to MIN, MAX podle funkce od které se odečítá 6. Sestavte kriteriální tabulku. Varianty – řešení Květák Kedlubny

Náklady

Kritéria Výměra květáku

Důležité pojmy Vícekriteriální rozhodování, vícekriteriální optimalizace, protichůdnost kritérií, dílčí – parciální optimální řešení, agregace účelových funkcí, převod kritérií na omezení, minimalizace odchylek od optimálních hodnot kritérií, cílové programování

MOV 04 – cvičení 10 Vícekriteriální analýza variant Nejvhodnější nabídka Máme zvolit jednu ze čtyř nabídek služeb pro naší firmu. Jednotlivé nabídky se liší cenou, dobou realizace a dodatečnými službami. Model je možno zformulovat následujícím způsobem:

Nabídka 1 Nabídka 2 Nabídka 3 Nabídka 4

cena (Kč) 75000 100000 65000 80000

doba realizace (měsíce) 2 3 5 4

dodatečné služby (porovnání nabídek) špatné = 4 nejlepší = 1 dobré = 3 lepší = 2

- 17 -

Christy


1) Určete bazální a ideální variantu. H = (65 000; 2; nejlepší) D = (100 000; 5; špatné) 2) Jak by dopadl výběr nabídek pro následující aspirační úrovně? - nejhorší přípustná hodnota daného kritéria a) (80000, 4, 4) - vybrali bychom 4 nebo 1 b) (75000, 4, 4) - vyhovuje nabídka 1 c) (75000, 4, 2) - nevíme kterou vybrat 3) Kterou nabídku vyberete metodou pořadí? (návod – ohodnoťte pořadí jednotlivých nabídek podle jednotlivých kritérií) N1 N2 N3 N4

K1 2 4 1 3

K2 1 2 4 3

K3 4 1 3 2

∑ 7 7 8 8

K1 K2 K3

K1 1 1 0

K2 0 1 0

K3 1 1 1 ∑

∑ 2 3 1 6

- vybrali bychom tu s nejmenším součtem 4) Pomocí párového porovnávání určete váhy kritérií. vi 1/3 1/2 1/6 1

5) Jsou-li váhy kritérií postupně 0,6 – 0,2 – 0,2 , můžete metodu pořadí rozšířit o důležitost – preferenci kritérií. N1 N2 N3 N4 vj

K1 2 4 1 3 0,6

K2 1 2 4 3 0,2

K3 4 1 3 2 0,2

∑ 2,2 3 2 2,8

6) Porovnejte bodovací metodu pro určení preference alternativ a funkci užitku. N1 N2 N3 N4

4 1 3 2

1 10 3 7

- budujeme od 1 do 10 s tím, že 10 je nejlepší 7) Vyřešte problém metodou váženého součtu. N1 N2 N3 N4 vj

obr 2 rij =

K1 2 4 1 3 0,6

K2 1 2 4 3 0,2

K3 4 1 3 2 0,2 H D

K1 75 100 65 80 0,6 65 100

K2 2 3 5 4 0,2 2 5

K3 1 10 3 7 0,2 10 1

5/7 0 1 4/7 3/5

1 2/3 0 1/3 1/5

0 1 2/9 2/3 1/5

Ui 0,63 0,33 0,64 0,54

y ij − D j H j − Dj

Důležité pojmy Vícekriteriální rozhodování, vícekriteriální analýza variant, protichůdnost kritérií, kompromisní řešení, dominance alternativ, ordinální a kardinální uspořádání, uspořádání alternativ, aspirační úrovně, grafické znázornění - 18 -

Christy


- 19 -

Christy

Metody operačního výzkumu cvičení

Recommend Documents