2. část: Základy matematického programování, dopravní úloha. Ing. Michal Dorda, Ph.D

2. část: Základy matematického programování, dopravní úloha.

Ing. Michal Dorda, Ph.D.

1

Úvodní pojmy • Metody na podporu rozhodování lze obecně dělit na: – Exaktní metody – metody zaručující nalezení optimální řešení, např. Littlův algortimus, Hakimiho algoritmus atd. – Heuristické metody – metody, které nezaručují nalezení optimálního řešení, např. Metoda nejbližšího dosud nenavštíveného vrcholu atd.


2

Úvodní pojmy • Přípustné řešení je každé řešení, které splňuje omezující podmínky úlohy. • Optimální řešení je přípustné řešení, pro které nabývá hodnota optimalizačního kritéria extrému (maxima či minima). • Optimalizační kritérium je hledisko, pomocí kterého posuzujeme kvalitu jednotlivých přípustných řešení. Je-li optimalizační kritérium formulováno jako funkční vztah, hovoříme o účelové funkci. Ing. Michal Dorda, Ph.D.

3

Matematické modelování • Předmětem matematického modelování je sestava a řešení matematických modelů reálných problémů. • Matematické modelování patří mezi exaktní metody. • Matematické modely lze členit podle mnoha kritérií. • Podle toho, zda matematický model obsahuje náhodné proměnné, dělíme: – Deterministické modely (proměnné modelu nemají charakter náhodných proměnných). – Stochastické modely (proměnné modelu mají charakter náhodných proměnných).


4

Matematické modelování • Podle toho, je-li do modelu včleněn čas, dělíme modely na: – Statické (neobsahující čas, umožňují rozhodnout se v konkrétní situaci, nikoliv výhledově). – Dynamické (obsahující čas, umožňují rozhodovat výhledově).


5

Matematické programování • Je třeba provést nějaké rozhodnutí (např. jak naplánovat přepravy určitého materiálu ze skladů k zákazníkům tak, abychom minimalizovali celkové náklady na přepravu). • Účelem matematického programování je sestava a řešení rozhodovacích úloh, hledáme optimální řešení vzhledem k definovanému optimalizačnímu kritériu. Ing. Michal Dorda, Ph.D.

6

Matematické programování • Modely matematického programování dělíme na: – Lineární (podmínky úlohy jsou vyjádřeny lineárními rovnicemi nebo nerovnicemi). – Nelineární (podmínky úlohy jsou vyjádřeny nelineárními rovnicemi či nerovnicemi; o nelineární model se jedná i tehdy, je-li část podmínek nelineární a zbytek lineární).


7

Lineární programování • Budeme se zabývat jednoduchými lineárními matematickými modely a to statickými a deterministickými. • Požadavky na matematický model: – Model musí co nejpřesněji vystihovat modelovanou situaci. – Model musí být co nejjednodušší.


8

Lineární programování • K aplikacím lineárního programování např. patří již uvedené stanovení objemů přeprav mezi zdroji a zákazníky při minimalizaci celkových nákladů za přepravu, stanovení výrobního plánu náhradních dílů do dopravních prostředků při maximalizaci zisku, stanovení střižného plánu plechů při minimalizaci získaného odpadu atd. Ing. Michal Dorda, Ph.D.

9

Lineární programování • Každý matematický model je tvořen: – Soustavou omezujících podmínek (vymezují množinu přípustných řešení). – Účelovou funkcí, která umožňuje posuzovat kvalitu jednotlivých přípustných řešení z pohledu optimalizačního kritéria (např. minimalizace nákladů apod.).


10

Lineární programování • Omezující podmínky úlohy dělíme na: – Strukturální podmínky (zajišťují splnění podmínek plynoucích ze zadání konkrétního problému). – Obligatorní podmínky (specifikují definiční obory proměnných vystupujících v modelu).


11

Lineární programování • Do matematického modelu vstupují dvě skupiny veličin: – Veličiny konstantní, jejichž hodnoty se v průběhu výpočtu nemění. – Veličiny, jejichž hodnoty se v průběhu výpočtu mění – proměnné.

• Pomocí proměnných modelujeme jednotlivá rozhodnutí, z hodnot proměnných musí být po ukončení výpočtu jasné, jaká rozhodnutí máme udělat. Ing. Michal Dorda, Ph.D.

12

Lineární programování • V lineárním programování rozlišujeme podle oboru hodnot proměnných dva typy úloh: – Úlohy spojitého lineárního modelování. – Úlohy celočíselného lineárního modelování.

• V lineárním programování rozeznáváme tři základní typy oborů hodnot proměnných: – Obor nezáporných reálných čísel. – Obor nezáporných celých čísel. – Obor hodnot 0 a 1. Ing. Michal Dorda, Ph.D.

13

Lineární programování • Budeme-li např. rozhodovat o tom, kolik vyrobit šroubků M12, přičemž výrobní jednotkou bude tuna, budou definičním oborem příslušné proměnné nezáporná reálná čísla. • Budeme-li rozhodovat o tom, kolik vyrobit automobilů, potom budou definičním oborem proměnné celá nezáporná čísla. • Budeme-li rozhodovat o tom, které úseky zařadit do minimální Hamiltonovy kružnice, potom bude definiční obor proměnných {0,1}. Ing. Michal Dorda, Ph.D.

14

Lineární programování • V lineárním programování je dovoleno sčítat a odečítat proměnné a násobit proměnné reálnou konstantou. • V lineárním programování je dovoleno používat relační znaménka =, ≤ a ≥.


15

Dopravní úloha • Definice dopravní úlohy: Máme m zdrojů o kapacitách ai , kde i  1,2,..., m a n spotřebitelů s požadavky b j , kde j  1,2,..., n , mezi kterými se přepravuje homogenní typ zásilek. Dále je dána matice sazeb Cij – jednotkové náklady na přepravu z i–tého zdroje k j–tému spotřebiteli. Úkolem dopravní úlohy je potom určit jednotlivé objemy přeprav z i–tého zdroje k j–tému spotřebiteli tak, aby se minimalizovaly celkové náklady na přepravu. Ing. Michal Dorda, Ph.D.

16

Dopravní úloha • Rozeznáváme 3 typy dopravní úlohy: m n – Dopravní úloha vybilancovaná -

 a  b i 1

i

j 1

j

.

– Dopravní úloha nevybilancovaná s přebytkem m n kapacit zdrojů -  ai   b j . i 1

j 1

– Dopravní úloha nevybilancovaná s nedostatkem m n kapacit zdrojů -  ai   b j . i 1

j 1


17

Vlastnosti vybilancované dopravní úlohy 1. Množina přípustných řešení vybilancované dopravní úlohy je konvexní. • Obecně platí, že množina přípustných oblastí může být tvořena: – Prázdnou množinou. – Konvexním polyedrem (bod je považován za konvexní polyedr). – Neohraničenou konvexní oblastí. Ing. Michal Dorda, Ph.D.

18

Vlastnosti vybilancované dopravní úlohy Oblast přípustných řešení Oblast přípustných řešení

Konvexní polyedr

Neohraničená konvexní oblast


19

Vlastnosti vybilancované dopravní úlohy 2. Vybilancovaná dopravní úloha má vždy přípustné řešení.


20

Vlastnosti vybilancované dopravní úlohy Důkaz m n • Pro vybilancovanou úlohu platí  xij   xij  A . i 1 j 1 ai  b j • Zvolme xij  pro všechna i,j. Musíme A ověřit, zda je toto řešení přípustným. ai  b j  0 , čili • Jelikož ai , b j , A  0, potom platí xij  A obligatorní podmínky jsou splněny.


21

Vlastnosti vybilancované dopravní úlohy m

n

n

 xij  

ai  b j



ai   b j j 1

 ai pro • Dále platí A A j 1 j 1 všechna i, jsou tedy splněny podmínky pro zdroje. m

m

m

ai  b j

b j   ai

• Platí  xij   A  A  b j pro všechna j, i 1 i 1 jsou tedy splněny podmínky pro zákazníky. j 1


22

Vlastnosti vybilancované dopravní úlohy • Jelikož jsou splněny všechny omezující ai  b j podmínky úlohu, zvolené řešení xij  pro A všechna i,j je řešením přípustným.


23

Vlastnosti vybilancované dopravní úlohy 3. Vybilancovaná dopravní úloha má vždy optimální řešení. 4. Jsou-li všechny kapacity zdrojů a požadavky spotřebitelů celá nezáporná čísla, každé základní řešení se skládá pouze z celých čísel.


24

Vlastnosti vybilancované dopravní úlohy

Oblast přípustných řešení

Základní řešení


25

Vlastnosti vybilancované dopravní úlohy 5. Účelová funkce nabývá minima v krajním bodě konvexního polyedru, který je množinou přípustných řešení dané úlohy. Jestliže účelová funkce nabývá minima ve více než jednom krajním bodu, dosahuje stejných hodnot ve všech bodech, které jsou konvexními kombinacemi bodů, v nichž účelová funkce nabývá minima (leží tedy na spojnici těchto bodů). Ing. Michal Dorda, Ph.D.

26

Matematický model vybilancované dopravní úlohy a1

c11, x11

Z1

c12 , x12

a2

Z2

S2

b1

b2

cm 2 , xm 2

cm1 , xm1 Zm

c21, x21

c22 , x22 c2 n , x2 n

am

S1

m

n

 a  b i 1

i

j 1

j

c1n , x1n cmn , xmn

Sn

bn

Proměnná xij – objem přepravy mezi i-tým zdrojem a j-tým spotřebitelem. Ing. Michal Dorda, Ph.D.

27

Matematický model vybilancované dopravní úlohy • Účelová funkce: min f x   c11x11  c1 x12  ...  c1n x1n  c21x21  c22 x22  ...  c2 n x2 n  ...   cm1 xm1  cm 2 xm 2  ...  cmn xmn

• Obligatorní podmínky: x11, x12 ,..., x1n , x21, x22 ,..., x2n ,...xm1 , xm2 ,...xmn  0


28

Matematický model vybilancované dopravní úlohy • Strukturální podmínky: Kapacita každého zdroje bude zcela vyčerpána. x11  x12  ...  x1n  a1

Požadavek každého spotřebitele bude zcela splněn.

x21  x22  ...  x2 n  a2

x11  x21  ...  xm1  b1

................................... xm1  xm 2  ...  xmn  am

x12  x22  ...  xm 2  b2


................................... x1n  x2 n  ...  xmn  bn 29

Matematický model vybilancované dopravní úlohy • Matematický model ve zkrácené podobě: m

n

min f x    cij xij i 1 j 1

za podmínek: n

x j 1

ij

 ai pro i  1,2,..., m

m

x i 1

ij

 b j pro j  1,2,..., n

Vyčerpání kapacit zdrojů. Uspokojení požadavků. xij  0 pro i  1,2,..., m a i  1,2,..., n Ing. Michal Dorda, Ph.D.

30

Matematický model nevybilancované DÚ s přebytkem kapacit zdrojů a1

c11, x11

Z1

c12 , x12

a2

Z2

c22 , x22

b1

S2

b2

Sn

bn

n

 a  b i 1

cm 2 , xm 2

cm1 , xm1 Zm

c21, x21

m

c2 n , x2 n

am

S1

i

j 1

j

c1n , x1n cmn , xmn


31

Matematický model nevybilancované DÚ s přebytkem kapacit zdrojů • Účelová funkce: min f x   c11x11  c1 x12  ...  c1n x1n  c21x21  c22 x22  ...  c2 n x2 n  ...   cm1 xm1  cm 2 xm 2  ...  cmn xmn


 Účelová funkce a obligatorní podmínky mají stejný tvar jako u vybilancované dopravní úlohy! Ing. Michal Dorda, Ph.D.

32

Matematický model nevybilancované DÚ s přebytkem kapacit zdrojů • Strukturální podmínky: Kapacita každého zdroje bude vyčerpána jenom částečně nebo zcela.

Požadavek každého spotřebitele bude zcela splněn.

x11  x12  ...  x1n  a1 x21  x22  ...  x2 n  a2 ................................... xm1  xm 2  ...  xmn  am Ing. Michal Dorda, Ph.D.

x11  x21  ...  xm1  b1 x12  x22  ...  xm 2  b2 ................................... x1n  x2 n  ...  xmn  bn 33

Matematický model nevybilancované DÚ s přebytkem kapacit zdrojů • Matematický model ve zkrácené podobě: m

n

min f x    cij xij i 1 j 1

za podmínek: n

x j 1

ij

 ai pro i  1,2,..., m

Částečné nebo úplné vyčerpání kapacit zdrojů.

m

x i 1

ij

 b j pro j  1,2,..., n

Uspokojení požadavků.

xij  0 pro i  1,2,..., m a i  1,2,..., n Ing. Michal Dorda, Ph.D.

34

Matematický model nevybilancované DÚ s nedostatkem kapacit zdrojů a1

c11, x11

Z1

c12 , x12

a2

Z2

c22 , x22

b1

S2

b2

Sn

bn

n

 a  b i 1

cm 2 , xm 2

cm1 , xm1 Zm

c21, x21

m

c2 n , x2 n

am

S1

i

j 1

j

c1n , x1n cmn , xmn


35

Matematický model nevybilancované DÚ s nedostatkem kapacit zdrojů • Účelová funkce: min f x   c11x11  c1 x12  ...  c1n x1n  c21x21  c22 x22  ...  c2 n x2 n  ...   cm1 xm1  cm 2 xm 2  ...  cmn xmn


Účelová funkce a obligatorní podmínky mají opět stejný tvar jako u vybilancované dopravní úlohy! Ing. Michal Dorda, Ph.D.

36

Matematický model nevybilancované DÚ s nedostatkem kapacit zdrojů • Strukturální podmínky: Kapacita každého zdroje bude zcela vyčerpána. x11  x12  ...  x1n  a1

Požadavek každého bude uspokojen pouze částečně nebo úplně.

x21  x22  ...  x2 n  a2

x11  x21  ...  xm1  b1

................................... xm1  xm 2  ...  xmn  am

x12  x22  ...  xm 2  b2


................................... x1n  x2 n  ...  xmn  bn 37

Matematický model nevybilancované DÚ s nedostatkem kapacit zdrojů • Matematický model ve zkrácené podobě: m

n

min f x    cij xij i 1 j 1

za podmínek: n

x j 1

ij

 ai pro i  1,2,..., m

Vyčerpání kapacit zdrojů.

m

x i 1

ij

 b j pro j  1,2,..., n

Částečné nebo úplné uspokojení požadavků.

xij  0 pro i  1,2,..., m a i  1,2,..., n Ing. Michal Dorda, Ph.D.

38

Analytické řešení dopravní úlohy • K řešení úloh lineárního programování se používá Simplexová metoda. • Z výpočetního hlediska není tato metoda pro řešení dopravní úlohy vhodná, proto byl vyvinut G.B. Dantzigem speciální algoritmus pro řešení dopravní úlohy.


39

Analytické řešení dopravní úlohy • Pro potřeby výpočtu musíme znát: – Počet zdrojů a jejich kapacity ai , kde i  1,2,..., m . – Počet spotřebitelů s požadavky b j , kde j  1,2,..., n . – Matici sazeb (jednotkových nákladů) C, jednotlivé prvky cij této matice odpovídají nákladům na přepravu jedné jednotky mezi i-tým zdrojem a j-tým spotřebitelem.

• Proměnná xij bude nezáporná. Ing. Michal Dorda, Ph.D.

40

Analytické řešení dopravní úlohy • Vlastní algoritmus se skládá z následujících kroků: 1) Kontrola vybilancovanosti úlohy, postup na krok 2). 2) Nalezení výchozího řešení, postup na krok 3). 3) Kontrola nedegenerace úlohy, postup na krok 4). 4) Test optimality, není-li řešení optimální, postup na krok 5), v opačném případě algoritmus končí. Vyhledané řešení je řešením optimálním. 5) Transformace řešení a návrat ke kroku 3). Ing. Michal Dorda, Ph.D.

41

Analytické řešení dopravní úlohy – krok 1) • Algoritmus je vytvořen pro řešení vybilancované dopravní úlohy. • Máme-li nevybilancovanou dopravní úlohu s přebytkem kapacit zdrojů, potom přidáme fiktivního spotřebitele S s požadavkem f m n b f   ai   b j . i 1

j 1

• V případě nevybilancované dopravní úlohy s nedostatkem kapacit zdrojů přidáme fiktivní n m zdroj Zf s kapacitou a f   b j   ai . j 1


i 1

42

Analytické řešení dopravní úlohy – krok 2) • Výchozí řešení lze určit některou ze tří metod: – Metodou severozápadního rohu. – Indexovou metodou. – Vogelovou aproximační metodou.


43

Analytické řešení dopravní úlohy – krok 2) • Metoda severozápadního rohu: Jako první obsazujeme maximálním objemem přepravy pole odpovídající prvnímu zdroji a prvnímu zákazníkovi. V případě vyčerpání kapacity příslušného zdroje se přesouváme na další řádek, v opačném případě o jedno pole doprava. Pole obsazujeme tedy postupně od levého horního rohu (tedy severozápadu).


44

Analytické řešení dopravní úlohy – krok 2) • Indexová metoda: Postupně obsazujeme pole s nejnižší sazbou , přičemž postupujeme od sazeb nižších k sazbám vyšším. Vyskytuje-li se v tabulce více stejných sazeb, potom vybíráme libovolnou z nich. Nulové sazby (tedy ty, které odpovídají fiktivním přepravám) obsazujeme jako poslední v pořadí.


45

Analytické řešení dopravní úlohy – krok 2) • Vogelova aproximační metoda: 1) V každé řadě vypočítáme diferenci, nelze-li diference spočítat, postup na krok 4), v opačném případě jdeme na krok 2). 2) Vyhledáme řadu s maximální diferencí, v této řadě vyhledáme pole s nejnižší sazbou a to obsadíme maximálním možným objemem přepravy. Je-li více řad s maximální diferencí, potom vybíráme tu řadu, ve které je nejnižší sazba ze všech těchto řad a na toto pole umístíme maximální možný objem přepravy. Postup na krok 3). Ing. Michal Dorda, Ph.D.

46

Analytické řešení dopravní úlohy – krok 2) • Vogelova aproximační metoda: 3) Řadu, jejíž kapacitu nebo požadavek jsme vyčerpali, pomyslně vyškrtneme a při dalším postupu vedoucím k vyhledání výchozího řešení s ní dočasně nepracujeme, návrat na krok 1). 4) Obsadíme pole odpovídající zbylým hodnotám, vyhledané řešení je výchozím řešením.


47

Analytické řešení dopravní úlohy – krok 2) • Použitím některé z uvedených 3 metod získáme výchozí řešení, které je základní. • Řešení je základní tehdy, pokud graf, který vznikne spojením obsazených polí vodorovnými a svislými čarami, neobsahuje kružnici.


48

Analytické řešení dopravní úlohy – krok 3) • Získané řešení je nedegenerované, pokud je přepravami obsazeno (m + n – 1) polí. Případnou degeneraci odstraníme tak, že chybějící počet polí obsadíme nulovými objemy přepravy, přičemž je třeba opět respektovat, aby řešení bylo základní, tedy nuly lze umisťovat pouze na pole tak, aby v grafu nevznikla kružnice. Ing. Michal Dorda, Ph.D.

49

Analytické řešení dopravní úlohy – krok 4) • Test optimality řešení se skládá ze 3 kroků: 1) Výpočet potenciálů ui a vj podle vztahu ui + vj = cij. Potenciály počítáme pouze s využitím sazeb na obsazených polích – počítáme (m + n) potenciálů a máme pouze (m + n – 1) rovnic. Jeden potenciál položíme roven nule (doporučuje se za nulový potenciál volit ten, který odpovídá řadě s největším počtem obsazených polí). Ostatní potenciály dopočítáme podle výše uvedeného vztahu. Ing. Michal Dorda, Ph.D.

50

Analytické řešení dopravní úlohy – krok 4) 2) Výpočet nepřímých sazeb cij podle vztahu cij  ui  v j . Tyto nepřímé sazby vypočítáme pro všechna pole, postupujeme-li správně, potom musí na obsazených polích platit cij  cij . 3) Platí-li na všech polích nerovnost cij  cij , potom je aktuální řešení optimálním. Pokud toto neplatí pro všechna pole, potom je nutno přistoupit k transformaci řešení – krok 5).


51

Analytické řešení dopravní úlohy – krok 5) • Před transformací vypočteme hodnotu účelové funkce aktuálního řešení, tato hodnota se po provedení transformace řešení nesmí zvýšit. Samotnou transformaci provedeme následujícím postupem: – V tabulce vyhledáme nejvyšší kladný rozdíl cij  cij (kandidát s nejvyšší možnou úsporou) a na toto pole umístíme dosud neznámý objem přepravy t. – V řešící tabulce vyhledáme uzavřený obvod, přičemž se můžeme pohybovat pouze vodorovně nebo svisle a měnit směr lze pouze na polích obsazených přepravami. – V místech lomení obvodu střídavě odečítáme a přičítáme objem přepravy t. – Hodnota t je rovna nejmenšímu objemu přepravy na polích, na kterých se hodnota t odečítá. Ing. Michal Dorda, Ph.D.

52

Dantzigova ε perturbační metoda • V případě velké degenerovanosti úlohy lze k odstranění degenerace úlohy použít tuto metodu. • Metoda spočívá v úpravě vstupů úlohy: – ai  ai   pro i  1,2,..., m (všechny kapacity zdrojů zvýšíme o ε. – bj  b j pro j  1,2,..., n 1; bn  bn  m (všechny požadavky zůstanou stejné kromě požadavku posledního spotřebitele, který navýšíme o mε. Ing. Michal Dorda, Ph.D.

53

Dantzigova ε perturbační metoda • Číslo ε se nazývá perturbační konstanta a určí se podle vztahu: 10 k   , 2m

kde k představuje řád nejnižší kapacity zdroje, resp. nejnižšího požadavku spotřebitele. • Před hledáním výchozího řešení upravíme vstupy úlohy, vyhledáme výchozí řešení a poté hodnoty podle běžných zásad zaokrouhlíme na celá čísla. Takto získáme nedegenerované řešení. Ing. Michal Dorda, Ph.D.

54

2. část: Základy matematického programování, dopravní úloha. Ing. Michal Dorda, Ph.D

Recommend Documents