Metody operačního výzkumu přednášky

Metody operačního výzkumu přednášky

PEF - KOSA - Předměty - MOV04 MOV05syl - všechno k předmětu pef.czu.cz/kosa sekce Předměty u zkoušky - zajímá jí postup, numerické chyby nevadí 12 evidenčních testů - na základní věci 12 bodů za dobrovolné domácí úkoly (pokud bude málo bodů z testů)

Modely operačního výzkumu

•Optimalizační modely •Distribuční a dopravní modely •Plánování a řízení projektů •Teorie rozvrhování •Modely strukturální analýzy •Simulační a stochastické modely •Teorie rozhodování a teorie her Optimalizační modely Cílem je najít řešení splňující omezující podmínky a optimalizující hodnotu kritéria. Distribuční a dopravní modely Řešení problémů spojených s dopravou, distribucí nebo přiřazováním. Plánování a řízení projektů Umožňují časovou, nákladovou a zdrojovou analýzu projektů - procesů, ve kterých probíhá více operací, které jsou na sobě závislé Teorie rozvrhování Časové a prostorové uspořádání průmyslových operací z mnoha různých hledisek. Modely strukturální analýzy Bilancují vztahy mezi produkcí jednotlivých hospodářských odvětví a vyhledávají rovnovážný stav systému. Simulační modely Napodobují jednotlivé kroky chování zkoumaného systému. Stochastické modely Popisují výsledky systémů se stochastickým chováním, nikoliv jejich jednotlivé kroky. Teorie rozhodování a teorie her Modelování konfliktních situací. Vznikly z potřeby modelovat chování hráčů hazardních her. OBECNÉ OPTIMALIZAČNÍ MODELY Obsah

•Historická poznámka •Úloha na volný extrém •Úloha na vázaný extrém •Optimalizační úloha •Klasifikace optimalizačních úloh •Možnosti řešení optimalizačních úloh pef-info.wz.cz

-1-

Christy


Historická poznámka

•Nalezení extrému funkce pomocí metod matematické analýzy - derivace atd. •Praktické aplikace - omezení definičního oboru funkce Úloha na volný extrém min {f(x) ⏐ x ∈ Df } kde Df je definiční obor funkce f(x). minimální hodnota funkce na celém definičním oboru př. půjdu si koupit rohlíky chci min 2, jeden stojí 1,50 x≥2 cena min 1,5x minimum v -∞ - to není možné, proto omezení definičního oboru - úloha na vázaný extrém

y

1,5

2

Úloha na vázaný extrém min {f(x) ⏐ x ∈ M } úloha nalezení extrému funkce podél křivky. Optimalizační úloha min {f(x) ⏐ qi(x) ≤ 0 , i = 1, ..., m , xT=(x1, x2, ..., xn)T ∈ Rn }, f(x) a qi (x) jsou reálné funkce více proměnných a x je prvek vektorového prostoru Rn.

Optimalizační úloha Základní prvky optimalizačního modelu proměnné - procesy omezující podmínky kriteriální - účelová funkce Základní pojmy přípustné a nepřípustné řešení optimální řešení Klasifikace optimalizačních úloh Z hlediska počtu kritérií jednokriteriální optimalizační model, vícekriteriální optimalizační model. Z hlediska typu kritéria minimalizační model f(x) → MIN maximalizační model f(x) → MAX cílový model dosažení cíle f(x) = h Podle typu použitých funkcí lineární optimalizační model nelineární optimalizační model konvexní model - kvadratický konvexní model nekonvexní model. Možnosti řešení optimalizačních úloh Nalezení vektoru x splňujícího omezující podmínky qi(x) ≤ 0 , i = 1, ..., m Nalezení minimální hodnoty účelové funkce f(x). Grafický přístup Analytické metody Numerické metody

pef-info.wz.cz

-2-

Christy


Nalezení přípustného řešení Problém - nekonvexnost množiny přípustných řešení. Když už jedno přípustné řešení najdeme, jak najít to optimální.

Nalezení extrému účelové funkce Problém - nekonvexnost účelové funkce - lokální a globální extrémy. Kterým směrem postupovat k optimálnímu řešení? hledáme-li minimum - nekonvexnost hledáme-li maximum - nekonkávnost

Analytické metody

•Lagrangeova funkce

L(x,u) = f(x) + uT.q(x)

•Sedlový bod

L(xopt, u) ≤ L(xopt, uopt) ≤ L(x, uopt)

•Kuhn-Tuckerovy podmínky - vlastnosti sedlového bodu •Wolfeho algoritmus pro řešení kvadratických optimalizačních úloh Numerické metody

•Gradientní metody

xk+1 = xk + λk.sk sk...směr, λk....doba, xk....bod ze kterého vyjdeme, xk+1....bod kde skončíme

•Penalizační a bariérové metodyn

min {f(x) + pk(x) ⏐ x ∈ R }

•Heuristické metody

•metoda TOP TWENTY

pef-info.wz.cz

-3-

Christy


LINEÁRNÍ OPTIMALIZAČNÍ MODEL Obsah přednášky

•Cíl modelu •Definice modelu •Grafické zobrazení modelu •Základní pojmy •Základní věty Cíl lineárního optimalizačního modelu

•Optimální rozsahy procesů •Splnění omezení •Maximalizace či minimalizace hodnoty kritéria Příklad Z desek 5x7 je potřeba nařezat obdélníky 2x3 a čtverce 1x1. Možné řezné plány: A B C Potřeba přířezů Obdélníky 0 5 4 100 Čtverce 35 5 11 200 Kolik minimálně rozřezat desek?

Definice modelu Všechny prvky modelu jsou vyjádřeny pomocí lineárních funkcí

z (x) = cT x → MIN ≤ Ax = b ≥ x≥0

-> kritérium -> optimalizační podmínky c... cena proměnné, kriteriální koeficient

•proměnné - procesy (jednotky) •omezující podmínky - zformulujeme pomocí lineárních rovnic a nerovnic •kritérium - také podle lineární funkce •lineární funkce a lineární rovnice a nerovnice Příklad x1 - počet rozřezaných desek podle plánu A x2 - to samé podle plánu B x3 - to samé podle plánu C 1.x1 + 1.x2 + 1.x3 → MIN 0.x1 + 5.x2 + 4.x3 ≥ 100 35.x1 + 5.x2 + 11.x3 ≥ 200 x1,2,3 ≥ 0 x1 0 35 1

pef-info.wz.cz

x2 5 5 1

x3 4 11 1 x1, x2, x3

>= >= MIN >=

100 200 0

-4-

Christy


Grafické zobrazení modelu Prostor řešení - prostor proměnných Zobrazují se jednotlivé omezující podmínky Kriteriální funkce - směr růstu Konvexní polyedr

Polyedrický kužel

Konvexní polyedr

Δf(x)

Polyedrický kužel

Δf(x)

Příklad

Prostor řešení neuvažujeme řezný plán A

3 2 2

obdélníky

Xopt

čtverce

1

kritérium

1 5 0 0

10

pef-info.wz.cz

20

30

40

50

-5-

Christy


Grafické zobrazení modelu Prostor požadavků - prostor vektorů koeficientů jednotlivých proměnných transformovaných na jednotkovou cenu Složením vektorů musí být vektor pravých stran n

∑a x j

j =1

j

=b

Optimální řezný plán

Prostor požadavků 40

x1

35 x2 30 x3 25 b 20 15 10

Dvě možnosti

5 0 0

10

20

30

40

Základní pojmy

•Přípustné řešení - množina přípustných řešení - všechna řešení, která splňují omezující podmínky včetně podmínky nezápornosti

•Bázické řešení (vrchol) - řešení, ve kterém požadavkové vektory nenulové proměnné jsou lineárně nezávislé - odpovídají vrcholům přípustných řešení

•Optimální řešení - nejlepší přípustné řešení •Alternativní řešení - další optimální řešení •Suboptimální řešení - pod optimálním - blíží se optimálnímu, ale hodnota kritéria je horší Řešitelnost modelu

•Řešení neexistuje

- neexistuje řešení omezujících podmínek - kriteriální funkce je neomezená v požadovaném směru

•Existuje právě jedno řešení - jediné a bázické

•Existuje nekonečně mnoho řešení

- dvě a více bázická optimální (alternativní) řešení

pef-info.wz.cz

-6-

Christy


Základní věty

•Má-li úloha LP přípustné řešení, má i přípustné bázické řešení. •Má-li úloha LP optimální řešení, má i optimální bázické řešení. •Řešení úlohy LP leží vždy na hranici množiny přípustných řešení. •Má-li úloha LP více než jedno optimální řešení řešení, je optimálním řešením i jejich konvexní kombinace. SIMPLEXOVÝ ALGORITMUS Obsah přednášky

•Definice lineárního optimalizačního modelu •Soustava omezujících podmínek •Simplexový algoritmus •Řešení modelu Lineární optimalizační model Řešitelnost modelu

•Řešení neexistuje

- neexistuje řešení omezujících podmínek - kriteriální funkce je neomezená v požadovaném směru

•Existuje právě jedno řešení - jediné a bázické

•Existuje nekonečně mnoho řešení

- dvě a více bázická optimální (alternativní) řešení

Soustava omezujících podmínek

•Numericky umíme řešit pouze soustavy lineárních rovnic, nikoliv nerovnic •Jordanova eliminační metoda – bázické řešení ≤ Ax = b ≥

převedeme na

~ A~ x = b

Kapacitní podmínky

•Ax ≤ b •Ax + Ed = b, d ≥ 0 Ax

doplňkové proměnné

Ed

b

Požadavkové podmínky

•Ax ≥ b •Ax - Ed + Ep = b, d ≥ 0 Ax

pef-info.wz.cz

-Ed

doplňkové proměnné Ep

b

-7-

Christy


Podmínky v rovnicovém tvaru

•určení, bilanční a pod. •Ax = b •Ax + Ep = b, p ≥ 0 Ax

pomocné proměnné

Ep

b

Postup řešení modelu SIMPLEXOVÝ ALGORITMUS - Nalezení řešení soustavy omezujících podmínek - Jordanova eliminační metoda - Nalezení optimálního řešení Jordanova eliminační metoda Povolené eliminační úpravy

•Násobení řídící rovnice převrácenou hodnotou řídícího prvku. •Přičtení vhodného násobku řídící rovnice k upravované rovnici. Bázické řešení

•Kanonický tvar soustavy rovnic - matice soustavy obsahuje jednotkovou submatici •Proměnné s jednotkovými vektory - bázické •Jestliže A = (AN, E), x = (xN, xB) = (0, b), pak B

A.x = AN.xN + E.xB = b B

xN

xB E

AN

b

Test optimality

•Existuje lepší řešení? •Cena ekvivalentní lineární kombinace zj - cj = Σiαij.ci - cj

•zj - cj ≥ 0 •zj - cj ≤ 0

skutečná cena nižší než bázická

cj ... cena testované proměnné αij ... sloupec testované proměnné v matici

skutečná cena vyšší než bázická

•Celková změna ceny - xj.(zj - cj) •Nutně musí být xj nezáporné (nebo nekladné) - odvození

x p = ( x Np , x Bp )T = ( 0 , β )T z( x p ) = c T x p = c TN x Np + c TB x Bp = c TN 0 + c TB x Bp = c TB x Bp = c TB β x p +1 = ( x Np +1 , x Bp +1 )T = ( 0 , xk ,0 , β − αk xk )T z (x p +1 ) = c T x p +1 = c TN x Np +1 + c TB x Bp +1 = c TN (0, x k ,0) T + c TB (β − α k x k ) = c k x k + c TB (β − α k x k ) z (x p +1 ) − z (x p ) = c k x k + c TB (β − α k x k ) − c TB β = (c k − c TB α k ) x k = −(c TB α k − c k ) x k = −( z k − c k ) x k pef-info.wz.cz

-8-

Christy


Test přípustnosti řípustnosti

•Splnění omezujících omezujících podmínek •Nezápornost řešení pro vybrané xj ≥ 0 xi = bi - αij.xj ≥ 0

•αij > 0 ... xj ≤ bj /αij •αij ≤ 0 ... platí vždy

- odvození

⎛ 0 ⎞ ⎟ ⎜ ⎜ xk ⎟ x=⎜ 0 ⎟ ⎟ ⎜ ⎜ β − αx ⎟ k ⎠ ⎝

xi = β i − α ik xk ≥ 0 , ∀i ∈ B. pokud α ik ≥ 0 pak xk ≤

βi α ik

Simplexový algoritmus

•Podmínky algoritmu: =, b≥0, kanonická báze •Simplexová tabulka •Test optimality •Test přípustnosti •Nové bázické řešení - JEM Simplexová tabulka

A

B

b


p1 p2

10 10

p1 x1

10 1

x2 x1

1 1

pef-info.wz.cz

x1 1 0 35 349 0 1 0 0 1 0

x2 x3 d1 d2 1 1 0 0 5 4 -1 0 5 11 0 -1 99 149 -10 -10 4 -1 0 5 0,142857 0,314286 0 -0,02857 -10 -0,02857 49,14286 39,31429 1 0,8 -0,2 0 0 0,2 0,028571 -0,02857 0 0 -0,17143 -0,02857

-9-

p1 p2 b 10 10 1 0 100 0 1 200 5,714286 0 0 3000 1 0 100 20 0 0,028571 5,714286 40 0 -9,97143 1005,714 0,2 0 20 25 -0,02857 0,028571 2,857143 14,28571 -9,82857 -9,97143 22,85714

Christy



x2 x1

1 1

x2 x3

1 1

x1 1 0 1 0 -4 5

x2 1 1 0 0 1 0

x3 1 0,8 0,2 0 0 1

d1 0 -0,2 0,028571 -0,17143 -0,31429 0,142857

d2 0 0 -0,02857 -0,02857 0,114286 -0,14286

b 20 2,857143 22,85714 8,571429 14,28571

Optimální řešení: 2,857 desek podle prvního řezného plánu - alternativa 0 desek 20 desek podle druhého řezného plánu - alternativa 8,57 desek 0 desek podle třetího řezného plánu - alternativa 14,28 desek

Optimalizace portfolia domácnosti Domácnost chce uložit své volné finanční prostředky do některého z následujících aktiv: - akcie - termínovaný vklad - podílový list podílového fondu nebo je nechat doma v hotovosti K dispozici má 1000000 Kč. Portfolio nesmí překročit stanovenou míru rizika, musí být dostatečně likvidní a domácnost musí mít požadovanou úroveň zkušeností s jednotlivými typy produktů. Cílem je dosáhnout maximálního výnosu celého portfolia. Podkladové údaje jsou v tabulce: Na 1000 Kč Riziko Likvidita Zkušenost Zisk pef-info.wz.cz

Akcie 10 10 0,1 1,12

Termínovaný vklad 0,5 180 8 1,007

Podílový list

„Slamník“

Omezení

Jednotka

1 2 0,1 1,05

0,1 0 10 1,00

max. 1000 max. 5000 min. 30000 MAX

body dny body tis. Kč

- 10 -

Christy


x1 .. Akcie x2 .. TV x3 .. PF x4 … slamník

Kč Kč Kč Kč

1,12 1,01 1,05 0 0

d1 d2

0

d3

-10 p4 zj - cj 0 d1 0 d2 0

d3

1

x4 zj - cj 0 d1

0

d2

1,007

x2

1

x4 zj - cj 0 d1 1,05

x3

1,007

x2

1

x4 zj - cj 0 d1 0

d4

1,007

x2

1

x4 zj - cj 0 d1

1

0

0

0

0

-10

x1 1

x2 1

x3 1

x4 1

d1 1

d2 0

d3 0

d4 0

p4 0

10 10 0,1

0,5 180 8

1 2 0,1

0,1 0 10

0 0 0

1 0 0

0 1 0

0 0 -1

0 0 1

-2,12 0,99

-81 0,2

-2,05 0,99

-101 0

0 1

0 0

0 0

10 0,1

0 -0,1

10 0,42 1 10 180 2 0,01 0,8 0,01

0 0 1

0 0 0

1 0 0

0 1 0

0,01 -0,01 0 0 -0,1 0,1

700 5000 3000

-0,09

-7,2

-1,04

0

0

0

0

-0,1

3000

0,98 9,98 0,06 -0,03

0 0 1 0

0,99 0,99 0,01 0

0 0 0 1

1 0 0 0

0 1 0 0

-0 0,1 -0,1 996994,4 1009331 -0 0,01 -0,01 688,3333 692,2561 0,01 0 0 27,77778 2500 -0 -0,1 0,1 2977,778 2680000

0

0,001

5000

--

30000 -300000 997000

3000

0

1 0 0 0

-0,99 0 0,09 -0,09 996310,6 11062015 1,01 -0 0,01 -0,01 692,2561 68833 -0,01 0,01 -0 0 20,08604 ---0 -0 -0,1 0,1 2977,009 --1,044

-98,8 998 0,06 99,7

0 0 1 0

0

0

0

-8,96 99,4 0,01 9,94

0 0 0 1

1 0 0 0

-0

0 1 0 0

0 -1 0 0

990111,1 44555000 68833,33 -295000 27,77778 5000 9861,111 -355000

0

0

10

-0,02

0

10

9889,083

0 0 0 1

1 0 0 0

-10 100 0 10

0 0 1 0

0 1 0 0

0 -1 0 0

990000 70000 5000 10000

0,278 100 -99 10 999,9

5 5 -4 180 42

8,95 10 -9 2 99,9

0 1 0 0 0

0 0 1 0 0

10 10 -10 0 100

0 0 0 1 0

0 0 0 0 1

10 0 0 0 -1

10000 10000 990000 5000 70000

B 1

1

0

0

0,1 0 10

0 0 0

0 1 0

0 0 -1

B-1 0 1

10 -10

0 0

0 0

d3

1

x4 zj - cj

pef-info.wz.cz

-7,7 -718,354

20

3724,104

2977

-0,09 10,09 3724,104

-10 0,02 100 -0,23 0 0,01 10 -0,03

-9 99,9 2 10

d4

x3 = 700 996303

3005,75

-99 -4 1000 42 10 180 100 5

0

3750

0

99,82 1,007 8,906

0

27,77778

0 0 0 1

10,47 1,007

-303000 3000

4985000 1666,667

999,9 43,01 -1,04

0 1 0 0

10,1

1000000 10000

-8,93 10 -0,06 -0,05

0 0 1 0

-0,1

10,1

b 1000000 1000

0

0

1

0

0

100

0

-1

- 11 -

Christy


ANALÝZA VÝSLEDKŮ LINEÁRNÍHO OPTIMALIZAČNÍHO MODELU Obsah

•Formulace modelu •Výpočet modelu •Optimální řešení •Alternativní řešení •Suboptimální řešení •Analýza citlivosti vzhledem k změnám cen •Analýza citlivosti vzhledem k změnám pravých stran •Změny formulace modelu - rozsahu modelu Formulace (definice) modelu

•Proměnné - procesy (jednotky) •Omezující podmínky - soustava lineárních rovnic a nerovnic •Kritérium - účelová funkce (lineární) Optimální řezný plán Z desek 5x7 je potřeba nařezat obdélníky 2x3 a čtverce 1x1. Možné řezné plány: A B C Potřeba přířezů Obdélníky 0 5 4 100 Čtverce 35 5 11 200 Kolik minimálně rozřezat desek? x1 0 35 1

x2 5 5 1

x3 4 11 1 x1, x2, x3

>= >= MIN >=

100 200 0

Simplexový algoritmus

•Podmínky algoritmu: =, b≥0, kanonická báze •Simplexová tabulka •Test optimality - proměnná zařazovaná do báze - vybere proměnou, jejíž cena je výhodnější než cena bázických

proměnných

•Test přípustnosti - proměnná vyřazovaná z báze - který proces bude novým výhodným procesem nahrazen •JEM (Jordanova eliminační metoda) - nové bázické řešení Jordanova eliminační metoda - máme pouze dva způsoby jak to provést - řídící řádek vydělíme řídícím prvkem - jediná povolené operace s řídícím řádkem - ke každému jinému řádku přičteme řídící řádek - počítáme špatně - když vyjde záporná hodnota na pravé straně - když zmizí kanonický tvar

•kanonická – jednotková báze •změna báze – nahrazení jednoho bázického vektoru druhým – Steinitzova věta o výměně •matice bázických vektorů B •matice přechodu od báze k bázi B-1

pef-info.wz.cz

- 12 -

Christy


Simplexový algoritmus - najít optimální řešení za daných omezujících podmínek

•Algoritmus končí nalezením optimálního řešení,

•pokud není v bázi pomocná proměnná, je to optimální přípustné řešení modelu, •pokud pomocná proměnná v bázi zůstala a je nenulová, neexistuje přípustné řešení problému,

•nebo zjištěním, že účelová funkce je neomezená

•pokud nelze najít proměnnou pro vyřazení z báze.

Analýza výsledků řešení Do modelu můžeme přidat další podmínku, rovnici účelové funkce x1 + x2 + x3 = z a po úpravě z - x1 - x2 - x3 = 0 z 0 0 1

x1 x2 0 5 35 5 -1 -1 x1, x2, x3

x3 4 11 1 >=

>= >= = 0

100 200 0

Analýza simplexové tabulky Vliv proměnné x3 na optimální řešení

x2 x1 z

Matice

x1 0,00 1,00 0,00

Inverzní matice báze B-1 x2 1,00 0,00 0,00

x3 d1 d2 p1 p2 b 0,80 -0,20 0,00 0,20 0,00 20,00 0,20 0,03 -0,03 -0,03 0,03 2,86 0,00 -0,17 -0,03 -9,83 -9,97 22,86

Hodnoty zj - cj

Hodnoty bázických proměnných

Hodnota kritéria

~ ~ ~ B −1 ⋅ A = B −1 ( A, E ) = ( B −1 ⋅ A, B −1 ⋅ E ) = ( B −1 ⋅ A, B −1 ) Řešení modelu

•Optimální řešení

- bázické řešení s optimální hodnotou kritéria ve výsledné simplexové tabulce

•Alternativní řešení

- každé další bázické i nebázické optimální řešení, lze odvodit z výsledné simplexové tabulky

•Suboptimální řešení

- bázické i nebázické řešení problému s dostatečně dobrou hodnotou kritéria, odvozuje se z výsledné simplexové tabulky

Další řešení modelu

•Interval přípustných hodnot nebázické proměnné xj

0, min αβiji α ij > 0

•Test přípustnosti •Nové řešení bázické nebo nebázické

pef-info.wz.cz

- 13 -

Christy



x2 x1

1,00 1,00

x1 1,00 0,00 1,00 0,00

x2 1,00 1,00 0,00 0,00

Optimální řezný plán x1 x2 1,00 1,00 x2 1,00 0,00 1,00 x1 1,00 1,00 0,00 0,00 0,00 x2 1,00 -4,00 1,00 x3 1,00 5,00 0,00 0,00 0,00

x3 d1 d2 b 1,00 0,00 0,00 0,80 -0,20 0,00 20,00 0,20 0,03 -0,03 2,86 0,00 -0,17 -0,03 22,86

x3 1,00 0,80 0,20 0,00 0,00 1,00 0,00

d1 0,00 -0,20 0,03 -0,17 -0,31 0,14 -0,17

d2 0,00 0,00 -0,03 -0,03 0,11 -0,14 -0,03

první řezný plán druhý řezný plán třetí řezný plán

Optimální řešení 2,86 desek 20 desek 0 desek

první řezný plán druhý řezný plán třetí řezný plán

Optimální řešení 2,86 desek 20 desek 0 desek

b 20,00 2,86 22,86 8,57 14,29 22,86

Alternativa 0 desek 8,57 desek 14,29 desek


x2 x1

1,00 1,00

x1 1,00 0,00 1,00 0,00

x2 1,00 1,00 0,00 0,00

x3 d1 d2 b 1,00 0,00 0,00 0,80 -0,20 0,00 20,00 0,20 0,03 -0,03 2,86 0,00 -0,17 -0,03 22,86

Suboptimální řešení první řezný plán 2,86 - 0,03 d1 20 + 0,2 d1 druhý řezný plán překročení obdélníků z intervalu 〈0, 95.3〉

Analýza citlivosti vzhledem k změnám vstupních dat

•Analýza citlivosti vzhledem k změnám cen •Analýza citlivosti vzhledem k změnám hodnot pravých stran •Analýza citlivosti vzhledem k změnám koeficientů v omezujících podmínkách Analýza citlivosti vzhledem k změnám cen

•Změnu sledované ceny cj vyjádříme jako cj + λ

•Přepočítáme kriteriální řádek a získáme hodnoty s parametrem λ •Test optimality - soustava lineárních nerovnic s parametrem λ •Interval stability - nemění se báze řešení ani hodnoty proměnných, mění se hodnota kritéria Optimální řezný plán

x2 x1

1,00 1,00

x1 1,00 0,00 1,00 0,00

x2 1,00 1,00 0,00 0,00

x3 d1 d2 b 1,00 0,00 0,00 0,80 -0,20 0,00 20,00 0,20 0,03 -0,03 2,86 0,00 -0,17 -0,03 22,86

Analýza citlivosti vzhledem k změnám hodnot pravých stran

•Změnu sledované pravé strany bi vyjádříme jako bi + μ

•Přepočítáme vektor pravých stran a získáme hodnoty s parametrem μ •Test přípustnosti - soustava lineárních nerovnic s parametrem μ •Interval stability - nemění se báze řešení, mění se hodnoty proměnných a hodnota kritéria pef-info.wz.cz

- 14 -

Christy


Přepočet pravých stran

•Řešení soustavy lineárních rovnic pomocí JEM - Ax = b - báze B - x = B-1Ax = B-1b

•Parametrizovaný vektor pravých stran -1

- b + µ bude přepočítán B (b + µ)

Optimální řezný plán p1 p2

10 10

p1 x1

10 1

x2 x1

1 1

x1 x2 x3 d1 1,00 1,00 1,00 0,00 5,00 4,00 -1,00 0,00 35,00 5,00 11,00 0,00 349,00 99,00 149,00 -10,00 0,00 5,00 4,00 -1,00 1,00 0,14 0,31 0,00 0,00 49,14 39,31 -10,00 0,00 1,00 0,80 -0,20 1,00 0,00 0,20 0,03 0,00 0,00 0,00 -0,17

d2 0,00 0,00 -1,00 -10,00 0,00 -0,03 -0,03 0,00 -0,03 -0,03

b 100,00 200,00 3000,00 100,00 5,71 1005,71 20,00 2,86 22,86

Analýza citlivosti vzhledem k změnám koeficientů v omezujících podmínkách

•Změna koeficientu bázické proměnné - tvoří nový vektor s ostatními bázickými vektory opět bázi? - Nejlépe přidat nový vektor, novou proměnnou

•Změna koeficientu nebázické proměnné -1

- Přepočítat vektor pomocí B , test optimality a případně další výpočet

Změny formulace modelu - rozsahu modelu

•Přidání podmínky •Vynechání podmínky •Přidání proměnné •Vynechání proměnné (bázická, nebázická) TEORIE DUALITY Obsah

•Dualita •Dualita lineárních modelů •Tvorba duálního modelu •Vztahy dvojice duálně sdružených modelů •Duální simplexová metoda Dualita

•Vztah mezi dvěma objekty •Umožňuje na základě vlastností jednoho odvodit vlastnosti druhého •Maximalizační optimalizační model a minimalizační optimalizační model

pef-info.wz.cz

- 15 -

Christy


Dualita lineárních modelů

A

b

cT

AT

c

bT Dualita lineárních modelů

•Matice koeficientů A v primárním modelu a matice AT v duálním •Vektor pravých stran b v primárním modelu a vektor cen b v duálním •Vektor cen c v primárním modelu a vektor pravých stran c v duálním •Typ omezení a typ proměnných !!!!!!!!!!!!!! Tvorba duálního modelu - pravidla pro tvorbu

MAX

MIN

AT c b y y≥0 y libovolné y≤0 ATy ≥ c ATy = c ATy ≤ c bTy→Min

A b c x Ax ≤ b Ax = b Ax ≥ b x≥0 x libovolné x≤0 T c x→Max

Optimální řezný plán Z desek 5x7 je potřeba nařezat obdélníky 2x3 a čtverce 1x1. Možné řezné plány: A B C Potřeba přířezů 0 5 4 100 Obdélníky Čtverce 35 5 11 200 Kolik minimálně rozřezat MODEL x1 y1 0 y2 35 1

pef-info.wz.cz

desek? x2 5 5 1

x3 4 11 1 x1, x2, x3

>= >= MIN >=

100 200 0

- 16 -

Christy


Optimální řezný plán Primární model 1.x1 + 1.x2 + 1.x3 → MIN 0.x1 + 5.x2 + 4.x3 ≥ 100 35.x1 + 5.x2 + 11.x3 ≥ 200 x1,2,3 ≥ 0

Duální model 100.y1 + 200.y2 → MAX 0.y1 + 35.y2 ≤ 1 5.y1 + 5.y2 ≤ 1 4.y1 + 11.y2 ≤ 1 y1,2 ≥ 0

Vztahy dvojice duálně sdružených modelů

•Nechť primární úloha je minimalizační a xp je její přípustné řešení, nechť současně yp je přípustné řešení příslušné

duální úlohy, pak platí cTxp ≥ bTyp.

•Minimum kriteriální funkce je omezeno zdola maximem sdružené kriteriální funkce a naopak. Takže existuje konečné optimální řešení. - Hodnota účelové funkce min. úlohy je vyšší nebo rovna než hodnota funkce max. úlohy Vztahy dvojice duálně sdružených modelů

•Primární úloha má optimální řešení xo právě tehdy, když má duální úloha optimální řešení yo . •Navíc platí cTxo = bTyo. •Nechť má primární úloha přípustné řešení x a duální úloha přípustné řešení y, pro která platí cTx = bTy, pak jsou tato řešení optimálními řešeními obou úloh.

Vztahy dvojice duálně sdružených modelů Věta o dualitě Pro dvojici duálně sdružených úloh platí buď:

•obě úlohy mají přípustná řešení, pak mají i optimální řešení nebo •jedna z úloh přípustné řešení nemá, pak druhá nemá optimální řešení (buď také nemá přípustné řešení nebo má neomezenou účeovou funkci)

Vztahy dvojice duálně sdružených modelů Kritérium optimality Nechť má primární úloha přípustné řešení x a duální úloha přípustné řešení y. Tato řešení jsou optimálními řešeními obou úloh právě tehdy, když pro ně platí yT(Ax - b) = 0 xT(ATy - c) = 0

•Je-li proměnná bázická, odpovídající podmínka musí být splněna jako rovnice, je-li nebázická, podmínka musí platit. Vztahy dvojice duálně sdružených modelů

Primární a duální přípustnost řešení lineární optimalizační úlohy

•Primárně přípustné řešení splňuje všechny omezující podmínky a podmínky nezápornosti (test přípustnosti). •Duálně přípustné řešení splňuje všechny omezující podmínky a podmínky optimality (test optimality).

pef-info.wz.cz

- 17 -

Christy


Optimální řezný plán Primární model

Duální model

1.x1 + 1.x2 + 1.x3 → MIN -0.x1 – 5.x2 – 4.x3 ≤ -100 -35.x1 – 5.x2 – 11.x3 ≤ -200 x1,2,3 ≥ 0

100.y1 + 200.y2 → MAX 0.y1 + 35.y2 ≤ 1 5.y1 + 5. y2 ≤ 1 4.y1 + 11.y2 ≤ 1 y1,2 ≥ 0

duálně přípustné bázické řešení x = (0, 0, 0), d = (-100, -200) test optimality z-c = (-1, -1, -1, 0, 0)

primárně přípustné bázické řešení y = (0, 0), d = (1, 1, 1) test optimality z-c = (-100, -200, 0, 0, 0)

Vztahy dvojice duálně sdružených modelů Grafická interpretace

•Dualita prostoru řešení a prostoru požadavků lineární úlohy •Prostor řešení primární úlohy splývá s prostorem řešení duální úlohy a naopak. Grafická interpretace 34

Prostor požadavků primární úlohy

•Dualita prostoru řešení a prostoru požadavků Prostor řešení duální úlohy

x1 29

x2 x3 b

0,3

d1 d2 24

0,25 0,2

1. omez

19

2. omez

0,15

3. omez

14

Gradient

0,1 0,05

9

0 0

4

-1

1

3

0,05

0,1

0,15

0,2

0,25

0,3

5

-1

pef-info.wz.cz

- 18 -

Christy


Existence řešení sdružených modelů Primární úloha Duální úloha přípustné řešení nepřípustné řešení přípustné řešení nepřípustné řešení

přípustné řešení nepřípustné řešení nepřípustné řešení přípustné řešení

optimální řešení

Duální simplexová metoda

•Primární SA

- primárně přípustné řešení → primárně i duálně přípustné řešení = optimální řešení - hodnota kritéria se zlepšuje

•Duální SA

- duálně přípustné řešení → duálně i primárně přípustné řešení = optimální řešení - hodnota kritéria se zhoršuje

Duální simplexová metoda

•Podmínky - duálně přípustné a primárně nepřípustné řešení omezujících podmínek v rovnicovém tvaru •Test přípustnosti - volba proměnné vystupující z báze xr = min xi xi < 0

•Test optimality - volba proměnné vstupující do báze

z s − cs

α rs

= min α rj <0

zj − cj

α rj


d1 d2

0 0

d1 x1

0 1

x2 x1

1 1

x1 1 0 -35 -1 0 1 0 0 1 0

x2 1 -5 -5 -1 -5 0,14 -0,86 1 0 0

x3 1 -4 -11 -1 -4 0,31 -0,69 0,8 0,2 0,00

d1 0 1 0 0 1 0 0 -0,2 0,03 -0,17

d2 0 0 1 0 0 -0,03 -0,03 0 -0,03 -0,03

b -100 -200 0 -100 5,71 5,71 20 2,86 22,86

Primární simplexová metoda

•Podmínky - primárně přípustné a duálně nepřípustné řešení omezujících podmínek v rovnicovém tvaru zj − cj •Test optimality - volba proměnné vstupující do báze pro maximalizaci z s − cs = zmin −c <0 j

j

•Test přípustnosti - volba proměnné vystupující z báze br = min bi α rs

pef-info.wz.cz

- 19 -

α is > 0

α is

Christy


OBECNÉ OPTIMALIZAČNÍ MODELY Obsah

•Historická poznámka •Úloha na volný extrém •Úloha na vázaný extrém •Optimalizační úloha •Klasifikace optimalizačních úloh •Možnosti řešení optimalizačních úloh Historická poznámka

•Nalezení extrému funkce pomocí metod matematické analýzy - derivace atd. •Praktické aplikace - omezení definičního oboru funkce Úloha na volný extrém min {f(x) ⏐ x ∈ Df } kde Df je definiční obor funkce f(x). minimální hodnota funkce na celém definičním oboru Úloha na vázaný extrém min {f(x) ⏐ x ∈ M } úloha nalezení extrému funkce podél křivky. Optimalizační úloha min {f(x) ⏐ qi(x) ≤ 0 , i = 1, ..., m , xT=(x1, x2, ..., xn)T ∈ Rn }, f(x) a qi (x) jsou reálné funkce více proměnných a x je prvek vektorového prostoru Rn. Klasifikace optimalizačních úloh Z hlediska počtu kritérií jednokriteriální optimalizační model, vícekriteriální optimalizační model. Z hlediska typu kritéria minimalizační model f(x) → MIN maximalizační model f(x) → MAX cílový model dosažení cíle f(x) = h Podle typu použitých funkcí lineární optimalizační model nelineární optimalizační model konvexní model - kvadratický konvexní model nekonvexní model. Možnosti řešení optimalizačních úloh Nalezení vektoru x splňujícího omezující podmínky qi(x) ≤ 0 , i = 1, ..., m Nalezení minimální hodnoty účelové funkce f(x). Grafický přístup Analytické metody Numerické metody - lineární modely - jsou tam jen lineární funkce - nelineární modely - alespoň jedna nelineární funkce - konvexní model - model jehož množina řešení je konvexní, konvexní kriteriální funkce u MIN, konkávní MAX

pef-info.wz.cz

- 20 -

Christy


Nalezení přípustného řešení

Nalezení extrému účelové funkce

Analytické metody

•Lagrangeova funkce

L(x,u) = f(x) + uT.q(x)

•Sedlový bod

L(xopt, u) ≤ L(xopt, uopt) ≤ L(x, uopt)

•Kuhn-Tuckerovy podmínky - vlastnosti sedlového bodu •Wolfeho algoritmus pro řešení kvadratických optimalizačních úloh Kuhn-Tuckerovy podmínky

•Kuhn-Tuckerovy podmínky - vlastnosti sedlového bodu

•Konvexní optimalizační úloha má řešení xopt právě tehdy, když existuje vektor uopt a platí x opt ≥ 0 ∧ u opt ≥ 0

∂L(x opt , u opt ) ≤ 0 , i = 1,...,m ∂ui uiopt .

∂L(x opt , u opt ) = 0 , i = 1,...,m ∂ui

∂L(x opt ,u opt ) ≥ 0 , j = 1,...,n ∂x j x opt j .

∂L(x opt ,u opt ) = 0 , j = 1,...,n ∂x j

Kvadratická úloha min {xTCx + pTx⏐Ax ≤ b, xj ≥ 0, j=1, ..., n, x ∈ Rn }

•C je matice koeficientů kvadratických členů účelové funkce, •p je vektor koeficientů lineárních členů v účelové funkci, •A je matice koeficientů soustavy omezujících podmínek a •b je vektor pravých stran těchto podmínek

pef-info.wz.cz

- 21 -

Christy


Wolfeho podmínky

•Úprava Kuhn-Tuckerových podmínek pro kvadratickou optimalizační úlohu –lineární podmínky

Ax + y = b -Cx - ATu + v = p x ≥ 0, u ≥ 0, v ≥ 0, y ≥ 0

–nelineární kvadratické podmínky uoptT yopt + xoptTvopt = 0

Pomocná optimalizační úloha lineární omezující podmínky Ax + y = b, Cx + ATu - v + w = -p podmínky nezápornosti x ≥ 0, u ≥ 0, v ≥ 0, y ≥ 0, w ≥ 0 účelová funkce w1 + w2 + ... + wn → min. dodatečná nelineární podmínka uoptT yopt + xoptTvopt = 0 Řešení pomocné optimalizační úlohy

•Simplexový algoritmus pro lineární část •Rozšíření testu optimality – vstup proměnných do báze •Výpočet se liší podle hodnot ve vektorech p a b Wolfeho algoritmus

•1. krok – Kuhn-Tuckerovy podmínky •2. krok – Wolfeho podmínky •3. krok – Pomocná lineární optimalizační úloha •4. krok – Optimální řešení původní kvadratické úlohy

–Vektor xopt získaný jako řešení Wolfeho podmínek je optimálním řešením původní kvadratické optimalizační úlohy. Hodnotu kriteriální funkce vypočítáme dosazením, tedy zopt = f(xopt) = xTCx + pTx. Numerické metody

•Gradientní metody

xk+1 = xk + λk.sk

•Penalizační a bariérové metody

min {f(x) + pk(x) ⏐ x ∈ Rn }

•Heuristické metody

DISTRIBUČNÍ A DOPRAVNÍ SYSTÉMY Obsah

•Dopravní problémy •Zobecněné distribuční problémy •Přiřazovací problémy •Jednostupňová dopravní úloha •Model a jeho řešitelnost •Metody nalezení výchozího řešení

pef-info.wz.cz

- 22 -

Christy


Dopravní problémy

•Skutečná přeprava zboží, materiálu, lidí … •To, co odvážíme nebo přivážíme se jednoduše sčítá

D

- Odkud - dodavatelé - Jak (čím) - indexy - Přes co - mezisklady - stupně - Kam – spotřebitelé -Co (kolik) - podle kapacit a požadavků

M S

Jednostupňová dvouindexová úloha

•Přeprava zboží, materiálu, lidí …z míst zdrojů k místům spotřeby jediným způsobem •To, co odvážíme nebo přivážíme se jednoduše sčítá D

- Odkud - dodavatelé - Kam – spotřebitelé - Co (kolik)

S

•Dopravní (dvouindexová) tabulka

Přeprava od dodavatelů Přeprava ke spotřebite lům

Dvoustupňová dvouindexová úloha

•Přeprava zboží, materiálu, lidí …z míst zdrojů přes mezisklady k místům spotřeby jediným způsobem •To, co odvážíme nebo přivážíme se sčítá - Odkud - dodavatelé - Přes co - mezisklady - Kam – spotřebitelé - Co (kolik)

D

M S

•Dvoustupňová (dvouindexová) dopravní tabulka

pef-info.wz.cz

- 23 -

Christy


Přeprava od dodavatelů Přeprava k meziskladům

Přeprava ke spotřebitelům Přepravaa od meziskldů

Jednostupňová tříindexová úloha

•Přeprava zboží, materiálu, lidí …z míst zdrojů k místům spotřeby různými způsoby •To, co odvážíme nebo přivážíme se jednoduše sčítá D - Odkud - dodavatelé - Jak nebo čím - Kam – spotřebitelé - Co (kolik)

S

•Jednostupňová tříindexová dopravní tabulka

Přeprava od dodavatelů Přeprava ke spotřebite

Způsob přepravy

lům

Zobecněné distribuční problémy

•Rozdělení práce, materiálu apod. •Dochází ke změně jednotek – sčítání rozdělovaného množství s různými koeficienty pef-info.wz.cz

- 24 -

Christy


•Složitější problémy - obecný lineární model Rozdělení práce strojů na obdělání polí (koeficienty sčítání – výkon strojů) Přiřazovací problémy

•Kapacity i požadavky jsou jednotkové – přiřazení buď je nebo není •Většinou stejný počet zdrojů a spotřebitelů

Rozdělení pracovníků po jednom na jednotlivé práce, jejich výkon, schopnosti jsou různé Jednostupňová dopravní úloha

•Dodavatelé – D1, … , Dm - kapacity ai •Spotřebitelé – S1, … , Sn - požadavky bj •Trasa (i,j) – jediné spojení Di a Sj •Ohodnocení tras – dopravní náklady - cij •Přepravované množství xij - hledáme i - index dodavatel, j - index spotřebitele •Minimalizace ceny přepravy

- kapacity - kolik který dodavatel může dodat služeb atd. Rozvoz hnojiv

•Dva sklady – kapacity 150, 200 •Podniky – 80, 60, 150 •Matice vzdáleností 16 18

11 20

23 17

•Z kterého skladu mají být podniky zásobovány? - tunokilometry - dopravní náročnost je vyjádřená množstvím tun na kilometr (tuny krát kilometry) Jednostupňová dopravní úloha

•Nelze překročit ani kapacity ani požadavky •Podmínky dodavatelů - nedodá víc než má

S D

Σj xij ≤ ai , i=1,…,m

•Podmínky spotřebitelů - nepřijme víc než chce Σi xij ≤ bj , j=1,…,n

•Nezápornost •Kritérium

S D

xij ≥ 0

Σi Σj cij.xij → MIN

D

Jednostupňová dopravní úloha Předpoklad - rovnost kapacit a požadavků vyváženost dopravního systému

S S S

Σj xij = ai , i=1,…,m Σi xij = bj , j=1,…,n xij ≥ 0 Σi Σj cij.xij → MIN Matematický model x11 + x12 + x13 = 150 x21 + x22 + x23 = 200 x11 + x21 = 80 x12 + x22 = 60 x13 + x23 = 150 pef-info.wz.cz

- 25 -

Christy


xij ≥ 0 16x11+11x12+23x13+18x21+20x22+17x23 → MIN Maticové schéma modelu

x11 x12 .......... x21 x22 .............................. xm1 ........... xmn

a1 a2 ...

b1 b2 ... Řešitelnost dopravního modelu

•Frobeniova věta - požadavek vyváženosti •Omezující podmínky jsou vždy řešitelné •Bázické řešení - počet bázických proměnných •Lineární závislost tras Vyváženost systému

•celková kapacita dodavatelů se rovná celkovému pozadavku spotřebitelů •Σj ai = Σj bj •fiktivní dodavatel - am+1 = Σj bj - Σj ai (chybí dodávky) •fiktivní spotřebitel - bn+1 = Σj ai - Σj bj (chybí spotřeba) Jednostupňová dopravní tabulka

•Řádky - dodavatelé •Sloupce spotřebitelé •Pole - trasa S1 S2

P1 16 18 80

P2 11 20 60

P3 23 17 150

150 200

•Systém nutno vyvážit Výchozí řešení Základní princip - volba jednotlivých tras a vyčerpání dodávky či uspokojení požadavku Obecně v každém kroku je vyčerpán dodavatel nebo naplněn požadavek

•Volba trasy •Maximální přepravované množství je dáno zbývající kapacitou dodavatele nebo zbývajícím požadavkem spotřebitele •Úprava kapacit nebo dodavatelů Výchozí řešení Metody, jak postupně vybírat trasy

pef-info.wz.cz

- 26 -

Christy


•Metoda severozápadního rohu •Indexová metoda •Vogelova aproximační metoda •Habrova frekvenční metoda Nejjednodušší metody

•Metoda severozápadního rohu

–Vždy se volí volná trasa na severozápadě tabulky

•Indexová metoda (nejmenší ceny)

–Vždy se volí volná trasa s nejnižší sazbou Vogelova aproximační metoda

•Volba tras s největší diferencí a nejlepší sazbou •Minimalizace ztráty z použití nevhodného spoje - trasy •Vogelovy diference - rozdíl mezi nejlepší a druhou nejlepší sazbou •Čím vyšší diference, tím větší ztráta hrozí Rozvoz hnojiv

•Vyváženost systému •Výchozí řešení - VAM S1

P1 80

P2 60

18

S2 Diference

16

80 2

11 20

60 9

P3 10 140 150 6

PF

Diference

23 17

60 60 0

0

150

11, 5, 7

0

200

17, 1

DOPRAVNÍ ÚLOHA Postup řešení a analýza výsledků Obsah

•Jednostupňová dopravní úloha •Model a jeho řešitelnost •Duální model •Test optimality •Test přípustnosti •Algoritmus řešení •Analýza výsledků Jednostupňová dopravní úloha

•Dodavatelé – D1, … , Dm - kapacity ai •Spotřebitelé – S1, … , Sn - požadavky bj •Trasa (i,j) – jediné spojení Di a Sj •Ohodnocení tras – dopravní náklady - cij •Přepravované množství xij •Minimalizace ceny přepravy pef-info.wz.cz

- 27 -

Christy


Rozvoz hnojiv

•Dva sklady – kapacity 150, 200 •Podniky – 80, 60, 150 •Matice vzdáleností 16 18

11 20

23 17

•Z kterého skladu mají být podniky zásobovány? Jednostupňová dopravní úloha Předpoklad - rovnost kapacit a požadavků vyváženost dopravního systému Σj xij = ai , i=1,…,m Σi xij = bj , j=1,…,n xij ≥ 0 Σi Σj cij.xij → MIN Matematický model x11 + x12 + x13 = 150 x21 + x22 + x23 = 200 x11 + x21 = 80 x12 + x22 = 60 x13 + x23 = 150 xij ≥ 0 16x11+11x12+23x13+18x21+20x22+17x23 → MIN Rozvoz hnojiv

•Vyváženost systému •Výchozí řešení - VAM S1

P1 80

P2 60

18

S2 Diference

16

80 2

11 20

60 9

P3 10 140 150 6

PF 23 17

60 60 0

Diference 0

150

11, 5, 7

0

200

17, 1

Maticové schéma modelu x11 x12 .......... x21 x22 .............................. xm1 ........... xmn a1 a2 ...

u1 u2 ... v1 v2 ...

b1 b2 ...

c11 c12 .......... c21 c22 .............................. cm1 ........... cmn Duální model ui + vj ≤ cij , i = 1, ..., m, j = 1, ...,n Σiai.ui + Σj bj.vj → MAX

pef-info.wz.cz

- 28 -

Christy


Kritérium optimality

•Využití výsledků teorie duality v dopravních modelech Nechť má dopravní úloha přípustné řešení x a k ní duální úloha přípustné řešení u,v. Tato řešení jsou optimálními řešeními obou úloh právě tehdy, když pro ně platí ui (Σj xij - ai) = 0 vj (Σi xij - bj) = 0 xij (ui + vj - cij ) = 0 Kritérium optimality

•Využití v algoritmu takto Nechť má dopravní úloha přípustné řešení x a nechť platí ui (Σj xij - ai) = 0 vj (Σi xij - bj) = 0 xij (ui + vj - cij ) = 0 Toto řešení je optimální řešení dopravní úlohy právě tehdy, když u,v jsou přípustným řešením duální úlohy. Test optimality řešení

•Lze najít lepší řešení - vztah mezi sazbami •Metoda MODI

a) ui + vj = cij pro (i,j)∈ B B je množina bázických tras, bázických proměnných xij b) zij - cij = ui + vj - cij pro všechny trasy (i,j)

•Cena ekvivalentní kombinace přeprav

zrs = crk – cik + cij - ... + cls trasa (r,s) je nepoužitá trasa, zrs vychází z možné úpravy řešení Degenerace řešení

•Degenerované řešení •Nedegenerované řešení •Odstranění degenerace •Metoda MODI a degenerace řešení

- počet duálních proměnných m+n - počet bázických proměnných - řešení soustavy m+n – 1 rovnic pro m+n proměnných ui + vj = cij pro (i,j)∈ B

Rozvoz hnojiv

•Test optimality

P1 80

S1 -8

S2

18

16

•první krok •druhý krok

P2 60

16

11

-15

20

11

P3 10 140

PF 23 17

23

6

60

0

0

0

-6

6

u1 + v1 = 16 ....... 0 + v1 = 16 ........ atd. ověření, že platí ui + vj ≤ cij pro všechna i, j

Nové řešení - test přípustnosti

•Změna přepravního plánu - vybranou trasou se poveze více - úprava ostatních tras

- od každého dodavatele v sumě stejně - každému spotřebiteli v sumě stejně - v každém řádku a sloupci dopravní tabulky musí být suma změn rovna nule Σj Δxij = 0 , i=1,…,m Σi Δxij = 0 , j=1,…,n

pef-info.wz.cz

- 29 -

Christy


Nové řešení - test přípustnosti

•Změna přepravního plánu vybranou trasou se poveze více - úprava ostatních tras –v dopravní tabulce musí být v každém řádku a každém sloupci dvě trasy pro vyrovnání změny –nebo žádná Spotřebitel Dodavatel

Rozvoz hnojiv

•Nalezení nového řešení P1 80

S1 S2

-8

M = 10 P2 60

16 18

-15

P3 10

11 20

16

23 6 17

140

11

PF M 60

23

0

0

0

-6

6

Rozvoz hnojiv

•Test optimality •Optimální řešení P1 80

S1 S2

-2

P2 60

16 18

-9

P3 11

-6

20

16

23 17

150

11

PF 10 50

17

0

0

0

0

0

Algoritmus řešení

•Podmínky algoritmu - vyváženost •Výchozí bázické řešení •Test optimality - metoda MODI •Test přípustnosti - Dantzigovy okruhy •Přechod na nové bázické řešení Analýza výsledků

•Optimální řešení - odkud, kam, kolik a zač? •Alternativní řešení •Suboptimální řešení

–Perspektivita tras - suboptimální řešení - analýza hodnot zij - cij –Propustnost tras - substituce tras - možnosti nebázických přeprav - uzavřené okruhy

Rozvoz hnojiv

•Analýza optimálního řešení •Zásobování –S1 - P1, P2, nevyužitý –S2 - P3, nevyužitý

•Dopravní náklady 80.16 + 60.11 + 150.17 = 4490 P1 80

S1 S2

-2

18

16 pef-info.wz.cz

P2 60

16 -9

P3 11 20

11

-6

23

150

17

17

PF 10 50

0

0

0

0

0 - 30 -

Christy


Rozvoz hnojiv

•Analýza propustnosti tras S1 - P3: propustnost 10, substituuje trasu S1-PF S2 - P1 propustnost 50, substituuje trasu S2-PF S2 - P2 propustnost 50, substituuje trasu S2-PF –vysoká propustnost - 50 a více –nízká propustnost - méně než 50 S1

P1 80

S2

50

16 18

P2 60 50

16

11 20

P3 10 150

11

23 17

PF 10 50

17

0

0

0

0

0

Rozvoz hnojiv

•Analýza perspektivity řešení

–hodnoty 0, 2, 6, 9 –vysoce perspektivní trasa .......... –perspektivní trasa ............ –neperspektivní trasa ............. P1

P2

P3

PF

S1

0

16 0

11 -6

23 0

0

0

S2

-2

18 -9

20 0

17 0

0

0

16

11

17

0

Rozvoz hnojiv Analýza perspektivity a propustnosti tras 10

160 140

8

120

S1-persp

100

6

S2-persp

80 4

60

2

40 20

S1-prop S2-prop

0

0 P1

P2

P3

PF

DÚ: Do příštího pátku, zadání si vymyslet VÍCEKRITERIÁLNÍ OPTIMALIZAČNÍ MODELY Obsah

•Vícekriteriální optimalizační modely •Základní pojmy •Grafické zobrazení •Cíl řešení modelů •Metody řešení

pef-info.wz.cz

- 31 -

Christy


Vícekriteriální optimalizační model

•Množina přípustných řešení je nekonečná •Alespoň dvě účelové funkce •Vícekriteriální lineární optimalizační model z1 (x) = c1T x → MAX zk (x) = ckT x → MIN Ax ≤ b x≥0 Vícekriteriální řezný plán Z desek 5x7 je potřeba nařezat obdélníky Možné řezné plány: A Obdélníky 0 Čtverce 35

2x3 a čtverce 1x1. B C Potřeba přířezů 5 4 100 5 11 200

K dispozici je 70 desek. Kolik minimálně rozřezat desek, tak aby byl maximalizován počet obdélníků?

Celkem desek Obdélníků Čtverců Min desek Max obdélníků

A 1 0 35 1 0

B 1 5 5 1 5

C 1 4 11 1 4 x1, x2, x3

< > > MIN MAX >=

70 100 200

0

Základní pojmy

•Ideální a bazální varianta

- bazální řešení - má nejhorší hodnoty o kterých jsme ochotni uvažovat

•Dominance řešení

- jedno řešení dominuje druhé řešení

•Paretovské řešení •Kompromisní řešení •Kompenzace kritérií Grafické zobrazení problému I

pef-info.wz.cz

- 32 -

Christy


Grafické zobrazení problému II

f2

- a1 a a2 jsou nedominovaná a dominují a3 a a4

a1

H

- a3 a a4 jsou vzájemně nedominovaná

a2

- a1 a a2 jsou paretovskými řešeními

a3 D

- D - bazální řešení - H - ideální řešení - kompromisní řešení - blízké ideálnímu - vybráno bude řešení podle toho, které kritérium je pro nás důležitější

a4

Cíl řešení modelů

f1

•Nalezení kompromisního řešení •Nalezení všech nedominovaných řešení •Většina metod umožňuje kompenzaci hodnot kritérií Typy informací

•Intrakriteriální preference - preference mezi kritérii

- vždy kardinální - hodnoty kriteriálních funkcí

•Interkriteriální preference

- váhy - důležitost jednotlivých kritérií žádná informace nominální informace - aspiračních úrovně ordinální informace - kvalitativní - uspořádání nutno převést na kardinální informaci - vyjádření pořadím kardinální informace - kvantitativní - víme co je důležitější a kolikrát

Metody řešení problému

•Hledání kompromisního řešení

- Dílčí (parciální) optimalizace - Agregace kriteriálních funkcí pomocí vhodně zvoleného operátoru - Převod kritéria na vlastní omezení modelu - Cílové programování - Vícekriteriální simplexový algoritmus

Dílčí optimalizace

•Řešíme tolik úloh, kolik je kritérií

- Úloha U(j) má původní omezující podmínky a jednu kriteriální funkci, j=1,..., k

U(j) : z j (x) = cTj x → MAX Ax ≤ b x≥0 Dílčí optimalizace

•Získáme vlastně kriteriální matici pro vícekriteriální analýzu variant - Na diagonále ideální řešení, lze určit i bazální řešení

•Využití spíše pro orientaci v problému

pef-info.wz.cz

- 33 -

Christy


1

x x2 … xk

Dílčí řešení

Kriteriální funkce z2(x) … z12 … z22 … … … zk2 …

z1(x) z11 z21 … zk1

zk(x) z1k z2k … zkk

Vícekriteriální řezný plán Celkem desek Obdélníků Čtverců Min desek Max obdélníků

A 1 0 35 1 0

B 1 5 5 1 5

C 1 4 11 1 4 x1, x2, x3

< > > MIN MAX >=

70 100 200

0

Vícekriteriální řezný plán Min desek Max obdélníků

A 2,857143 0

B 20 70

C 0 0

Min desek Max obdélníků 22,85714 100 70 350

Ideální řešení Bazální řešení

22,85714 70

350 100

Agregace kriteriálních funkcí

•Agregované kritérium nemá obvykle ekonomickou interpretaci •Typy agregace •Součinová či podílová •Součtová či rozdílová •Konvexní lineární kombinace kritérií

•Min kritéria nutno převést na max kritéria

min f(x) = max (-f(x)) nebo min f(x) = max 1/f(x)


•Konvexní lineární kombinace kritérií

- řešíme následující jednokriteriální úlohu s původními omezujícími podmínkami k

Z (x) = ∑ v jcTj x = v TCx → MAX j =1

Ax ≤ b x≥0

Vícekriteriální řezný plán Celkem desek Obdélníků Čtverců Min desek Max obdélník ů Agregované kritérium

pef-info.wz.cz

A 1 0 35 -1 0 -5

B 1 5 5 -1 5 0

C 1 4 11 -1 4 -1 x1, x2, x3

< > > MAX MAX MAX >=

- 34 -

70 100 200 5 1 0

Christy



A 2,857143 0

B 20 70

C 0 0


Ideální řešení Bazální řešení Agregace 5:1

0

40

22,85714 70

350 100

40

200

0

Převod kritérií na omezení modelu

•Kteroukoli omezující podmínku lze formulovat jako kriteriální funkci a naopak •Zvolíme nejdůležitější kritérium •Stanovíme požadované - aspirační úrovně ostatních kritérií •Řešíme jednokriteriální úlohu s původními podmínkami a podmínkami zaručujícími požadované hodnoty upravených kritérií

•Lze použít i iterační postup a kritéria upravovat postupně Grafické zobrazení kritérií a omezení a2 z2

a1

z1


•Zvolíme kritérium z1(x) •

Stanovíme požadované - aspirační úrovně ostatních kritérií zj’ (mezi ideálním a bazálním řešením) –pro max zj(x) ≥ zj’ a pro min zj(x) ≤ zj’

•Řešíme jednokriteriální úlohu (pro max kritéria) z1 (x) = c1T x → MAX Ax ≤ b z j ( x) ≥ z′j j = 2,..., k x≥0 Grafické zobrazení nového modelu a 2

a

a’1

1

z2 z2(x) = z’2

z1

pef-info.wz.cz

- 35 -

Christy


Vícekriteriální řezný plán A 1 0 35 1 0


B 1 5 5 1 5

C 1 4 11 1 4 x1, x2, x3

< > > < MAX >=

70 100 200 30 0


A 2,857143 0

B 20 70

C 0 0

Ideální řešení Bazální řešení 0 40 Agregace 5:1 De sek méně než 30 1,666667 28,33333

Min desek Max obdélníků 22,85714 100 70 350 22,85714 70

350 100

40 30

200 141, 6667

0 0

Cílové programování

•Dosažení požadovaných hodnot kritérií •Minimalizace odchylek od cílových hodnot jednotlivých kritérií •Proměnné překročení •Proměnné nedosažení •Maximalizační kritérium může cílovou hodnotu překročit •Minimalizační kritérium může cílové hodnoty nedosáhnout Cílová podmínka

•Dosažení požadované hodnoty kritéria pokud nelze, pak je hodnota kritéria - buď překročena T ci x = yi0 - nebo nedosažena T

ci x + d i− − d i+ = yi0 x ≥ 0; d i− ≥ 0, d i+ ≥ 0 d i− d i+ = 0, Cílové programování k

Z(d) = ∑ (vi− d i− + v i+ d i+ ) → min i =1

za podmínek ci x + d − d i+ = yi0 , i = 1,2,..., k, Ax ≤ b x ≥ 0; d i− ≥ 0, d i+ ≥ 0 d i−d i+ = 0, T

− i

di- a di+ jsou proměnné nedosažení a překročení vi- a vi+ jsou jejich váhy

pef-info.wz.cz

- 36 -

Christy



Cílové programování Celkem desek Obdélníků Čtverců Min desek Max obdélníků Min odchylek

B 1 5 5 1 5

C 1 4 11 1 4

d1+

d1-

d2+

d2-

< > > -1 = 1 -1 = 1 1 1 MIN x1, x2, x3, d+, d- >=

1 1

70 100 200 30 250 0


A 2,857143 0

B 20 70

C 0 0

Ideální řešení Bazální řešení 0 40 Agregace 5:1 De sek méně než 30 1,666667 28,33333 0 50 Cíl 30/250


350 100

40 30 50

200 141, 6667 250

0 0 0

VÍCEKRITERIÁLNÍ ANALÝZA VARIANT Obsah

•Typy modelů vícekriteriálního rozhodování •Základní pojmy •Typy informací •Cíl modelů •Užitek, funkce užitku •Grafické zobrazení •Metody vícekriteriální analýzy variant Typy modelů

•Vícekriteriální optimalizační model

–Množina přípustných řešení je nekonečná

•Model vícekriteriální analýzy variant

–Množina přípustných řešení je konečná Vícekriteriální optimalizační model

•Množina přípustných řešení je nekonečná •Alespoň dvě účelové funkce •Vícekriteriální lineární optimalizační model y1 (x) = c1T x → MAX yk (x) = ckT x → MIN Ax ≤ b x≥0 pef-info.wz.cz

- 37 -

Christy


Model vícekriteriální analýzy variant

•Množina přípustných řešení je konečná •Každá varianta je hodnocena podle několika kritérií a1 a2 ap

f1

⎛ y 11 ⎜ ⎜ y 21 ⎜… ⎜ ⎜ y p1 ⎝

f 2 … fk y 12 … y 1k ⎞ ⎟ y 22 … y 2k ⎟ … … …⎟ ⎟ y p2 … y pk ⎟⎠

Základní pojmy

•Ideální a bazální varianta •Dominance řešení •Paretovské řešení •Kompromisní řešení Ideální a bazální varianta

•Ideální řešení (varianta) je hypotetické nebo reálné řešení, reprezentované ve všech kritériích současně nejlepšími možnými hodnotami. - varianta H s ohodnocením (h1, ..., hk) •Bazální řešení (varianta) je hypotetické nebo reálné řešení, reprezentované nejhorším ohodnocením podle všech kritérií. - varianta D s ohodnocením (d1, ..., dk). Dominance řešení V této definici předpokládáme všechna kritéria maximalizační.

•Varianta ai dominuje variantu aj , jestliže pro její ohodnocení platí (yi1, yi2 ,…, yik) ≥ (yj1, yj2,…, yjk) a existuje alespoň jedno kritérium fl , že yil > yjl .

•Řešení je nedominované (efektivní) řešení problému, pokud neexistuje žádné jiné řešení, které by jej dominovalo. Paretovské řešení

•Varianta (řešení), která není dominovaná žádnou jinou variantou, je nedominovaná varianta, často se též nazývá efektivní nebo paretovská. (Wilfredo Paretto) Kompromisní řešení

•Kompromisní varianta (řešení) má od ideální varianty (řešení) nejmenší vzdálenost podle vhodné metriky (měřenou vhodným způsobem).

•Kompromisem může být i zanedbání některých kritérií. Cíl řešení modelů

•Nalezení jediné kompromisní varianty, kompromisního řešení (Nalezení určitého počtu kompromisních variant) •Rozdělení řešení na efektivní a neefektivní •Uspořádání všech řešení od nejlepšího k nejhoršímu •Problémy umožňující kompenzaci a problémy nepovolující kompenzaci Užitek, funkce užitku

•Každé ohodnocení varianty je možno vyjádřit ve formě užitku, který tato varianta přináší pef-info.wz.cz

- 38 -

Christy


•Dílčí hodnoty užitku lze sloučit do celkového užitku varianty a podle toho varianty vybírat Funkce užitku

•Funkce užitku převádí ohodnocení řešení do intervalu 〈0, 1〉 •Podle jejího tvaru lze charakterizovat rozhodovatele Přístupný riziku

1

Neutrální k riziku

0

Odmítající riziko

Grafické zobrazení problému I

f2 a1

H a2

a3 D

a4

f1 Grafické zobrazení problému II

S

a1 a2

a1 S

a2

Modely vícekriteriální analýzy variant

•Množina přípustných řešení je konečná •Každá varianta je hodnocena podle několika kritérií - kriteriální matice a1 a2 ap

f1 f 2 ⎛ y 11 y 12 ⎜ ⎜ y 21 y 22 ⎜… … ⎜ ⎜ y p1 y p2 ⎝

pef-info.wz.cz

… fk … y 1k ⎞ ⎟ … y 2k ⎟ … …⎟ ⎟ … y pk ⎟⎠

- 39 -

Christy


Koupě motorové kosy Cena 9600,10900,12950,min

722 S 726 D 735 S

Výkon 0,7 kW/min 0,8 kW/min 1,1 kW/min max

Hmotnost 5,8 6,2 6,2 min

Názor ne nevím ano

Typy informací

•Inter a intra kriteriální preference

- Preference jednotlivých kritérií - Hodnocení variant podle každého kritéria žádná informace nominální informace - aspiračních úrovně ordinální informace - kvalitativní - uspořádání kardinální informace - kvantitativní

Metody kvantifikace informace

•Metoda pořadí

- nejlepší varianta, nejdůležitější kritérium bude první v pořadí

•Bodovací metoda

- nejlepší varianta, nejdůležitější kritérium dostane nejvíce bodů

•Párové porovnávání

- porovnává se důležitost kritérií či ohodnocení variant podle jednotlivých kritérií

Koupě motorové kosy Cena Výkon Hmotnost Názor

Cena 1 1 0 0

Výkon 0 1 0 1

Hmotnost 1 1 1 0

Názor 1 0 1 1

Součet 3 3 2 2 10

Váhy 0,3 0,3 0,2 0,2


Žádná Informace o atributech

Nominální Ordinální Kardinální

Informace o alternativách Ordinální Kardinální Bodovací metoda, metoda pořadí Metoda aspiračních úrovní metoda ORESTE Metoda váženého součtu, Saatyho metoda metoda TOPSIS

Metody řešení

•Bodovací metoda nebo metoda pořadí •Metoda aspiračních úrovní •Metoda váženého součtu Bodovací metoda nebo metoda pořadí

•Jednotlivé varianty budou ohodnoceny pořadovými čísly mezi 1 a počtem variant •Jednotlivé varianty budou ohodnoceny podle jednotlivých kritérií vždy ve stejné bodové stupnici, např. 1 až 10 pef-info.wz.cz

- 40 -

Christy


•Pořadí nebo body se sečtou •Oba postupy mohou být rozšířeny o váhy kritérií Koupě motorové kosy Cena Výkon Hmotnost 722 S 9600,- 0,7 kW/min 5,8 10900,- 0,8 kW/min 6,2 726 D 12950,- 1,1 kW/min 6,2 735 S min max min Metoda pořadí 1 722 S 2 726 D 3 735 S

3 2 1


1 2,5 2,5

Součet 8 8,5 7,5

3 2 1

Metoda aspiračních úrovní

•Konjunktivní metoda

- připustíme pouze varianty, které splňují všechny aspirační úrovně

•Disjunktivní metoda

- připustíme všechny varianty, které splňují alespoň jeden požadavek

•Iterační postup

- zpřísňování nebo uvolňování aspiračních úrovní

Koupě motorové kosy Cena Výkon Hmotnost 722 S 9600,- 0,7 kW/min 5,8 726 D 10900,- 0,8 kW/min 6,2 735 S 12950,- 1,1 kW/min 6,2 min max min Aspirační úrovně 10000,722 S 726 D 735 S 10000,-


0,7 kW/min

6

nevím

0,7 kW/min

6

ne

722 S 726 D 735 S

Metoda váženého součtu •Převedeme minimalizační kritéria na maximalizační podle vztahu

y ij = max (y ij ) − y ij i −1,..., s

•Určíme ideální variantu H s ohodnocením (h1, ..., hk) a bazální variantu D s ohodnocením (d1, ..., dk). •Vytvoříme standardizovanou kriteriální matici R, jejíž prvky získáme pomocí vzorce y ij − d j = r ij k hj − dj •Pro jednotlivé varianty vypočteme užitek u(a ) = ∑ v r i

•Varianty seřadíme sestupně podle hodnot u(ai).

pef-info.wz.cz

j =1

j ij

- 41 -

Christy


Koupě motorové kosy 722 S 726 D 735 S

D H 722 S 726 D 735 S

Cena 9600 10900 12950 min

Výkon 0,7 0,8 1,1 max

Hmotnost 5,8 6,2 6,2 min

Názor 1 2 3 max

3350 2050 0 0 3350 1 0,61194 0 0,3

0,7 0,8 1,1 0,7 1,1 0 0,25 1 0,3

0,4 0 0 0 0,4 1 0 0 0,2

1 2 3 1 3 0 0,5 1 0,2

Součet 0,5 0,358582 0,5

VÍCEKRITERIÁLNÍ OPTIMALIZAČNÍ MODELY Obsah

•Vícekriteriální optimalizační modely •Základní pojmy •Grafické zobrazení •Cíl řešení modelů •Metody řešení Vícekriteriální optimalizační model

•Množina přípustných řešení je nekonečná •Alespoň dvě účelové funkce •Vícekriteriální lineární optimalizační model z1 (x) = c1T x → MAX zk (x) = ckT x → MIN Ax ≤ b x≥0 Vícekriteriální řezný plán Z desek 5x7 je potřeba nařezat obdélníky Možné řezné plány: A Obdélníky 0 Čtverce 35

2x3 a čtverce 1x1. B C Potřeba přířezů 5 4 100 5 11 200

K dispozici je 70 desek. Kolik minimálně rozřezat desek, tak aby byl maximalizován počet obdélníků?

Celkem desek Obdélníků Čtverců Min desek Max obdélníků pef-info.wz.cz

A 1 0 35 1 0

B 1 5 5 1 5

C 1 4 11 1 4 x1, x2, x3

< > > MIN MAX >= - 42 -

70 100 200

0 Christy


Základní pojmy

•Ideální a bazální varianta •Dominance řešení •Paretovské řešení •Kompromisní řešení •Kompenzace kritérií Grafické zobrazení problému I

Grafické zobrazení problému II

f2 a1

H a2

a3 D

a4

f1 Cíl řešení modelů

•Nalezení kompromisního řešení •Nalezení všech nedominovaných řešení •Většina metod umožňuje kompenzaci hodnot kritérií Typy informací

•Intrakriteriální preference

- vždy kardinální - hodnoty kriteriálních funkcí

•Interkriteriální preference

- váhy - důležitost jednotlivých kritérií žádná informace nominální informace - aspiračních úrovně ordinální informace - kvalitativní - uspořádání nutno převést na kardinální informaci kardinální informace - kvantitativní


•Hledání kompromisního řešení

- Dílčí (parciální) optimalizace - Agregace kriteriálních funkcí pomocí vhodně zvoleného operátoru

pef-info.wz.cz

- 43 -

Christy


- Převod kritéria na vlastní omezení modelu - Cílové programování - Vícekriteriální simplexový algoritmus Dílčí optimalizace

•Řešíme tolik úloh, kolik je kritérií

- Úloha U(j) má původní omezující podmínky a jednu kriteriální funkci, j=1,..., k

U(j) : z j (x) = cTj x → MAX Ax ≤ b x≥0 Dílčí optimalizace

•Získáme vlastně kriteriální matici pro vícekriteriální analýzu variant - Na diagonále ideální řešení, lze určit i bazální řešení

Dílčí řešení

•Využití spíše pro orientaci v problému Kriteriální funkce z2(x) … z12 … z22 … … … zk2 …

z1(x) z11 z21 … zk1

x1 x2 … xk

zk(x) z1k z2k … zkk

Vícekriteriální řezný plán Celkem desek Obdélníků Čtverců Min desek Max obdélníků

A 1 0 35 1 0

B 1 5 5 1 5

C 1 4 11 1 4 x1, x2, x3

< > > MIN MAX >=

70 100 200

0


A 2,857143 0

B 20 70

C 0 0


Ideální řešení Bazální řešení

22,85714 70

350 100


•Agregované kritérium nemá obvykle ekonomickou interpretaci •Typy agregace •Součinová či podílová •Součtová či rozdílová •Konvexní lineární kombinace kritérií

•Min kritéria nutno převést na max kritéria

min f(x) = max (-f(x)) nebo min f(x) = max 1/f(x)


•Konvexní lineární kombinace kritérií

- řešíme následující jednokriteriální úlohu s původními omezujícími podmínkami

pef-info.wz.cz

- 44 -

Christy


k

Z (x) = ∑ v jcTj x = v TCx → MAX j =1

Ax ≤ b x≥0

Vícekriteriální řezný plán A 1 0 35 -1 0 -5

Celkem desek Obdélníků Čtverců Min desek Max obdélník ů Agregované kritérium

B 1 5 5 -1 5 0

C 1 4 11 -1 4 -1 x1, x2, x3

< > > MAX MAX MAX >=

70 100 200 5 1 0


A 2,857143 0

B 20 70

C 0 0


Ideální řešení Bazální řešení Agregace 5:1

0

40

22,85714 70

350 100

40

200

0


•Kteroukoli omezující podmínku lze formulovat jako kriteriální funkci a naopak •Zvolíme nejdůležitější kritérium •Stanovíme požadované - aspirační úrovně ostatních kritérií •Řešíme jednokriteriální úlohu s původními podmínkami a podmínkami zaručujícími požadované hodnoty upravených kritérií

•Lze použít i iterační postup a kritéria upravovat postupně Grafické zobrazení kritérií a omezení

a2 a1

z2

z1


•Zvolíme kritérium z1(x) •

Stanovíme požadované - aspirační úrovně ostatních kritérií zj’ (mezi ideálním a bazálním řešením) - pro max zj(x) ≥ zj’ a pro min zj(x) ≤ zj’

•Řešíme jednokriteriální úlohu (pro max kritéria) pef-info.wz.cz

- 45 -

Christy


z1 (x) = c1T x → MAX Ax ≤ b z j ( x) ≥ z′j j = 2,..., k x≥0 Grafické zobrazení nového modelu

a2 a1

z2

a’1

z2(x) = z’2

z1



B 1 5 5 1 5

C 1 4 11 1 4 x1, x2, x3

< > > < MAX >=

70 100 200 30 0


A 2,857143 0

B 20 70

C 0 0

Ideální řešení Bazální řešení 0 40 Agregace 5:1 De sek méně než 30 1,666667 28,33333


350 100

40 30

200 141, 6667

0 0

Cílové programování

•Dosažení požadovaných hodnot kritérií •Minimalizace odchylek od cílových hodnot jednotlivých kritérií •Proměnné překročení •Proměnné nedosažení •Maximalizační kritérium může cílovou hodnotu překročit •Minimalizační kritérium může cílové hodnoty nedosáhnout T

ci x = yi0

Cílová podmínka

•Dosažení požadované hodnoty kritéria pokud nelze, pak je hodnota kritéria - buď překročena - nebo nedosažena pef-info.wz.cz

T

ci x + d i− − d i+ = yi0 x ≥ 0; d i− ≥ 0, d i+ ≥ 0 d i− d i+ = 0, - 46 -

Christy


Cílové programování k

Z(d) = ∑ (vi− d i− + v i+ d i+ ) → min i =1

za podmínek ci x + d − d i+ = yi0 , i = 1,2,..., k, Ax ≤ b x ≥ 0; d i− ≥ 0, d i+ ≥ 0 d i−d i+ = 0, T

− i

di- a di+ jsou proměnné nedosažení a překročení vi- a vi+ jsou jejich váhy Vícekriteriální řezný plán Cílové programování Celkem desek Obdélníků Čtverců Min desek Max obdélníků Min odchylek

A 1 0 35 1 0


A 2,857143 0

B 1 5 5 1 5

C 1 4 11 1 4

d1+

1

C 0 0

Ideální řešení Bazální řešení 0 40 Agregace 5:1 De sek méně než 30 1,666667 28,33333 0 50 Cíl 30/250

d2+

d2-

< > > -1 = 1 -1 = 1 1 1 MIN x1, x2, x3, d+, d- >=

1

B 20 70

d1-

70 100 200 30 250 0


350 100

40 30 50

200 141, 6667 250

0 0 0

TEORIE ROZHODOVÁNÍ Obsah

•Formulace rozhodovacího modelu •Rozhodování za jistoty, rizika a nejistoty •Možnosti řešení rozhodovacího modelu •Kritéria řešení rozhodovacího modelu •Rozhodovací a pravděpodobnostní stromy Teorie her

•Nalezení optimální strategie v hazardních hrách •Model konfliktní situace •John von Neumann, Oscar Morgenstern - 1928 •Ekonomické chování - volba alternativy rozhodnutí Rozhodovací modely

•Volba nejlepšího rozhodnutí ovlivňovaného budoucím stavem světa pef-info.wz.cz

- 47 -

Christy


•Většinou neopakovatelné situace •Alternativy rozhodnutí •Stavy okolností •Rozhodovací tabulka - výplaty pro kombinace alternativa/stav okolností •Rozhodovací kritérium •Jistota, riziko a nejistota Rozhodovací tabulka

Stavy okolností s2 ..... sn s1 a1 v11 v12 ..... v1n a2 v21 v22 ..... v2n Alternativy ..... ..... ..... ..... ..... am vm1 vm2 ..... vmn Riziko p1 p2 ..... pn Volba strategie firmy

Pověst firmy Kontrola kvality ANO Kontrola kvality NE Pravděpodobnosti

velký 1 1,1

Zájem střední 0,95 0,8

malý 0,7 0,6

0,4

0,2

0,4

vyšší cena nižší cena

Jistota, riziko a nejistota

•rozhodování s jistotou

pravděpodobnost realizace jistého stavu okolností je rovna 1 a pravděpodobnosti ostatních stavů okolností jsou rovny nule

•rozhodování s rizikem

pravděpodobnosti realizace stavů okolností jsou odhadovány či známy

•rozhodování za nejistoty

pravděpodobnosti realizace stavů okolností jsou neznámé

Možnosti řešení rozhodovacích modelů

•Volba dominantní alternativy •Volba nejvýhodnější alternativy •Volba alternativy podle nejvyššího užitku Volba dominantní alternativy (max)

•Dominance podle výplat: aI dominuje aK

min vIj ≥ max vKj

j =1,..., n

j =1,..., n

•Dominance podle stavů okolností : aI dominuje aK

vIj ≥ vKj

•Dominance podle pravděpodobností : aI dominuje aK

P (v I ≥ x ) ≥ P ( v K ≥ x )

pef-info.wz.cz

- 48 -

∀j , j = 1,..., n

Christy


Dominance podle výplat 1,2 1 0,8

min vIj ≥ max vKj

0,6

j =1,..., n

j =1,..., n

0,4 0,2 0

min

max

ANO

0,7

1

NE

0,6

1,1

Dominance podle stavů okolností Kontrola kvality ANO

1,2 1

Kontrola kvality NE

0,8

vIj ≥ vKj

0,6

∀j , j = 1,..., n

0,4 0,2 0 velký

střední

malý

Dominance podle pravděpodobností 1,2

1 0,8

P (v I ≥ x ) ≥ P ( v K ≥ x )

0,6

0,4

ANO NE

0,2

0 0

0,2

0,4

0,6

0,8

1

1,2

Volba nejvýhodnější alternativy

•Rozhodování za jistoty •Rozhodování za nejistoty

- maximaxové pravidlo - Waldovo - maximinové pravidlo - Savageovo pravidlo minimální ztráty - Laplaceovo pravidlo nedostatečné evidence - Hurwitzovo pravidlo

•Rozhodování za rizika

- pravidlo EMV - očekávané hodnoty výplaty - pravidlo EOL - očekávané možné ztráty - pravděpodobnost dosažení aspirační úrovně

pef-info.wz.cz

- 49 -

Christy


Volba strategie za jistoty

Pověst firmy Kontrola kvality ANO Kontrola kvality NE Pravděpodobnosti

velký 1 1,1


malý 0,7 0,6

0,4

0,2

0,4

a I : v IJ = max v iJ


i =1,..., m

Volba strategie za nejistoty¨


velký 1 1,1

Kontrola kvality ANO Kontrola kvality NE


0,1 0

0 0,15

malý 0,7 0,6

MAXIMIN 0,7 0,6

0 0,1

SAVAGE 0,1 0,15

aI : vIJ = max min vij

MAXIMAX 1 1,1

LAPLACE 0,883 0,8333333

⎛1 n ⎞ a I : v I = max ⎜⎜ n ∑ v ij ⎟⎟ i =1,..., m ⎝ j=1 ⎠

i = 1,...,m j = 1,...,n

aI : vIJ = max max vij i = 1,...,m j = 1,...,n

a I : z IJ = min max ( max v ij − v ij ) i =1,... m j =1,..., n

i =1,..., m

Volba strategie za nejistoty Kontrola kvality ANO Kontrola kvality NE

max 1 1,1

min 0,7 0,6 t

HURWICZ 0,7 0,6 0

0,79 0,75 0,3

0,88 0,9 0,6

1 1,1 1

1,2

1

0,8

Kontrola kvality ANO

0,6

0,4

aI : vI = max (t.hi + (1 − t).di ) i = 1,...,m

d i = min vij j = 1,...,n hi = max vij

Kontrola kvality NE

0,2

j = 1,...,n

0 0

0,2

0,4

pef-info.wz.cz

0,6

0,8

1

1,2

- 50 -

Christy


Volba strategie za rizika

velký 1 1,1


malý 0,7 0,6

Pravděpodobnosti

0,4

0,2

0,4


0,1 0

0 0,15

0 0,1


a I : EMVI = max EMVi = max i =1,..., m

i =1,..., m

a I : EOLI = min EOL i = min i =1,..., m

i =1,..., m

EMV 0,87 0,84

EOL 0,04 0,07

n

∑p v j

ij

j=1

n

∑ p j ( max v ij − vij ) = min

i =1,..., m

i =1,..., m

j=1

n

∑p z j=1

j ij

Rozhodovací strom Zájem velký Zájem střední M Kontrola ANO

Zájem malý

R Zájem velký

Kontrola NE

Zájem střední M Zájem malý

Pravděpodobnostní strom Kontrola kvality výrobků ne: 0,95

Vada

0,9

ano: 0,05 ne: 0,02

0,7

Reklamace ano: 0,03 0,5

pef-info.wz.cz

- 51 -

Christy


Pravděpodobnostní strom

Kontrola kvality výrobků Výrobek

Kontrola kvality ANO Pravděpodobnosti

bezvadný

chybný s reklamací

0,9 0,95

0,5 0,03

chybný bez reklamace 0,7 0,02

1,2 1 0,8 0,6 0,4 0,2 0 0

0,2

0,4

0,6

0,8

1

TEORIE HER Obsah přednášky

•Hra •Třídění her •Modely teorie her. •Maticová hra •Čisté strategie •Smíšené strategie •Hra s přírodou Teorie her

•Nalezení optimální strategie v hazardních hrách •Model konfliktní situace •John von Neumann, Oscar Morgenstern - 1928 •Ekonomické chování - volba alternativy rozhodnutí Hra

•Model konfliktní situace •Konflikt zájmů •Kooperativní a nekooperativní •Antagonistická - neantagonistická •Probíhá v čase pef-info.wz.cz

- 52 -

Christy


•Opakuje se - neopakuje se •Hra - partie - strategie - tah Hráči

•Počet hráčů •Inteligentní a neinteligentní hráči •Vytvářejí či nevytvářejí koalice Strategie

•Chování hráče ve hře •Hra - partie - strategie - tah •Konečný či nekonečný počet strategií Výplata

•Výsledek hráče při určitých strategiích všech hráčů •Výplatní funkce •Maximalizace zisku •Hry s konstantním (nulovým) a nekonstantním součtem Řešení hry

•Nalézt takovou strategii každého hráče, která mu přinese nejlepší možný výsledek, tj. při které on i ostatní hráči dosáhnou svých nejlepších možných výsledků •Platba hry je výsledek jednotlivých hráčů Model hry

•Model v rozvinutém tvaru

- strom hry (rozhodovací strom - jednotlivé tahy)

•Model v normálním tvaru

- výplatní matice (rozhodovací tabulka)

Maticová hra

•Dva inteligentní hráči •Konečné množiny strategií každého hráče •Konstantní, resp. nulový součet •Výplaty pro každou dvojici strategií •Výplatní matice Výplatní matice

Strategie druhého hráče S1

S2

Strategie R1

a11

a12

a1n

prvního

R2

a21

a22

a2n

hráče

... Rm

pef-info.wz.cz

...

Sn

... am1

am2

amn

- 53 -

Christy


Čistá a smíšená strategie

•Čistá strategie - jednoznačně určená strategie hráče •Smíšená strategie - pro každou strategii je dána pravděpodobnost jejího použití - četnost použití při opakování hry - při

mnoha partiích

Řešení v oboru čistých strategií Pohled protihráče

•První hráč

a kh = max min a ij = v

•Druhý hráč

a kh = min max a ij = v

i =1,..., m j =1,..., n

j =1,..., n i =1,..., m

Pohled hráče Sedlový bod hry

•Dvojice strategií (Rk, Sh) určuje sedlový bod hry, jestliže v = v Dolní cena hry se rovná horní ceně hry

pro každé i=1, ... ,m a j=1, ...,n a ih ≤ a kh ≤ a kj Jestliže jeden z hráčů udělá chybu, získá méně.

•Pro sedlový bod platí

Řešení v oboru čistých strategií Věta

•Maticová hra má řešení v oboru čistých strategií právě tehdy, když má sedlový bod. Hra dvou inteligentních hráčů Konkurence firem

Firma A

Firma B Kontrola kvality ANO NE 0,8 0,5 0,4 0,7

Kontrola kvality ANO Kontrola kvality NE max

0,7 minimax

min 0,5 0,4

maxmin

0,8

Řešení v oboru smíšených strategií

•smíšená strategie prvního hráče r = (r1, r2, ... , rm)T, kde Σ ri = 1

•smíšená strategie druhého hráče s = (s1, s2, ... , sn)T , kde Σ sj = 1 •musí platit

m

n

r T A s = ∑∑ ri a ijs j = v i =1 j =1


•první hráčT chce platbu alespoň w (maximin) r aj ≥ w pro každé j=1,...,n Σ ri = 1 r≥0 w → max

pef-info.wz.cz

- 54 -

Christy


•druhý hráč chce platbu nejvýše w (minimax) ais ≤ w pro každé i=1,...,m Σ sj = 1 r≥0 w → min


•první hráčT

r aj ≥ w pro každé j=1,...,n Σ ri = 1 r≥0 w → max

•upravímeT (transformace xi = ri/w)

x aj ≥ 1 pro každé j=1,...,n Σ xi = 1/w x≥0 1/w = Σ xi → min


•duálně sdružené úlohy •první hráčT

x aj ≥ 1 pro každé j=1,...,n x≥0 Σ xi → min

•druhý hráč

ajy ≤ 1 pro každé i=1,...,m y≥0 Σ yj → max


•Transformace je možná pouze pro kladné výplaty, pak je cena hry w kladná - nutná úprava matice přičtením hodnoty

α = min min a ij + 1 i =1,...,m j=1,...,n

•Výsledek pomocných modelů nutno transformovat zpět !!!!!!!!! Hra dvou inteligentních hráčů Základní věta teorie maticových her Každá maticová hra je řešitelná - existují optimální strategie hráčů a cena hry Strategie zaručující nejlepší možný výsledek hráčů, když hráči neudělají chybu Hra dvou inteligentních hráčů

•První hráč 0,5r1 + 0,7r2 ≥ w 0,8r1 + 0,4r2 ≥ w r1 + r2 = 1 r1 , r2 ≥ 0 w → max

pef-info.wz.cz

0,5x1 + 0,7x2 ≥ 1 0,8x1 + 0,4x2 ≥ 1 (x1 + x2 = 1/w) x1 , x2 ≥ 0 x1 + x2 → min

- 55 -

Christy


•Druhý hráč

0,5s1 + 0,8s2 ≤ w 0,7s1 + 0,4s2 ≤ w s1 + s2 = 1 s1 , s2 ≥ 0 w → min

0,5y1 + 0,8y2 ≤ 1 0,7y1 + 0,4y2 ≤ 1 (y1 + y2 = 1/w) y1 , y2 ≥ 0 y1 + y2 → max

•Řešení X2 X1 Z

X1 0 1 0

X2 1 0 0

D1 -2,222 1,111 -1,111

D2 1,389 -1,944 -0,556

0,833 0,833 1,667

1 = 0,6 1,667 0,833 0,833 x1 = = 0,5 x 2 = = 0,5 1,667 1,667 1,111 0,556 y1 = = 0,667 y 2 = = 0,333 1,667 1,667

w=

Hra s neinteligentním hráčem

•Neinteligentní hráč - příroda •Modely teorie rozhodování •Stejné postupy řešení Pověst firmy

Kontrola kvality ANO Kontrola kvality NE Pravděpodobnosti

pef-info.wz.cz

velký 1 1,1


malý 0,7 0,6

0,4

0,2

0,4


- 56 -

Christy

Metody operačního výzkumu přednášky

Recommend Documents