Operační výzkum. Přiřazovací problém

Operační výzkum Přiřazovací problém.

Operační program Vzdělávání pro konkurenceschopnost Název projektu: Inovace magisterského studijního programu Fakulty ekonomiky a managementu Registrační číslo projektu: CZ.1.07/2.2.00/28.0326

Přiřazovací problém


Přiřazovací problém = úloha optimálního přiřazení - např. strojů na pracovišti, - pracovišť k pracovníkům, - zákazníků k poskytovatelům služeb, - ... Jeden činitel 1. druhu je vždy přiřazen právě jednomu činiteli 2. druhu. Nejprve se tedy seznámíme s problematikou řešení minimalizačních úloh, následně se budeme věnovat i řešení maximalizačních úloh.

Michal Šmerek

Přiřazovací problém.


Př. (motivační): Podnik má k dispozici 3 jeřáby, které má přepravit na 3 pracoviště (každý jeřáb právě na jedno pracoviště). Vzdálenosti v km mezi stanovišti jeřábu Ji , i = 1, 2, 3, a pracovišti Pj , j = 1, 2, 3, jsou uvedeny v tabulce: cij P1 P2 P3 J1 4 3 1 J2 1 2 6 J3 4 5 3 Nalezněte optimální řešení, tj. takový plán přepravy, při kterém bude celkový počet ujetých kilometrů minimální.

Michal Šmerek



Řešení: 1. Matematický model Je třeba stanovit, který z jeřábů má být přepraven na které pracoviště tak, aby v součtu přepravní vzdálenost všech jeřábů byla minimální. Zavedeme bivalentní proměnnou xij , i = 1, 2, 3, j = 1, 2, 3, přičemž xij = 1, jestliže i-tý jeřáb je přiřazen na j-té pracoviště, xij = 0, jestliže i-tý jeřáb není přiřazen na j-té pracoviště. Řešením tedy budeme rozumět čtvercovou matici třetího (obecně n-tého) řádu 1 0 x11 x12 x13 X = @ x21 x22 x23 A . x31 x32 x33

Michal Šmerek



Každý jeřáb má být přiřazen právě na jedno pracoviště, proto v každém řádku matice X musí být právě jedna jednička a n − 1 nul. Každému pracovišti má být přiřazen právě jeden jeřáb, takže každý sloupec matice X musí obsahovat právě jednu jedničku a n − 1 nul. V souladu s tím můžeme psát omezující podmínky ve tvaru: J1 : x11 + x12 + x13 = 1, J2 : x21 + x22 + x23 = 1, J3 : x31 + x32 + x33 = 1,

(1)

P1 : x11 + x21 + x31 = 1, P2 : x12 + x22 + x32 = 1, P3 : x13 + x23 + x33 = 1.

(2)

resp.

Michal Šmerek



Podmínky (1), resp. (2) lze úsporněji zapsat ekvivalentním způsobem následovně: 3 X xij = 1, i = 1, 2, 3,

(3)

j=1

resp. 3 X

xij = 1,

j = 1, 2, 3.

(4)

i=1

Účelová funkce zde vyjadřuje součet přepravních vzdáleností. Má tvar: z = c11 x11 + c12 x12 + c13 x13 + c21 x21 + · · · + c33 x33 → min. Zkráceně: z=

3 X 3 X

cij xij → min.

i=1 j=1

Michal Šmerek


(5)


Obecně jde o to, přiřadit n činitelů n jiným činitelům tak, aby součet příslušných sazeb byl minimální (resp. maximální). OBECNÝ MATEMATICKÝ MODEL: z=

n P n P

cij xij → min.

i=1 j=1 n P j=1 n P

xij = 1,

9 > i = 1, 2, . . . , n > =

xij = 1,

> > j = 1, 2, . . . , n ;

i=1

1 xij =

celkem 2n omezení (rovnic),

. . . přiřazení

% &

n2 proměnných. 0

. . . nepřiřazení

n proměnných nabývá hodnoty 1, n2 − n proměnných je rovno 0. Základních proměnných je v úloze 2n − 1. Tedy, stupeň degenerace, je roven n − 1). Pro řešení se využívá algoritmus nazývaný maďarská metoda.

Michal Šmerek



Postup při užití maďarské metody Předpokládáme, že řešená úloha je minimalizační. 1

Provedeme redukci sazeb (cij ) matice: i) od každého řádku matice odečteme nejmenší sazbu v tomto řádku, ii) od každého sloupce matice odečteme nejmenší sazbu v tomto sloupci.

2

V redukované matici sazeb vyhledáme tzv. nezávislé nuly, tj. nuly, z nichž se každá nachází v jiném řádku a jiném sloupci. Budeme je označovat pomocí horního indexu, tj. 01 . V dané matici je třeba najít maximální počet nezávislých nul, proto postupujeme následovně: i) Za nezávislou nulu zvolíme tu, která se nachází na svém řádku či sloupci samostatně. ii) Vynecháme řádky a sloupce, na jejichž průsečíku se označené nuly nachází a ve vzniklé submatici pokračujeme bodem 2.i) iii) Pokud každý řádek či sloupec obsahuje víc než jednu neoznačenou nulu, vybereme řádek či sloupec s nejmenším počtem nul a ve vybraném řádku či sloupci libovolnou nulu zvolíme za nezávislou. Pokračujeme bodem 2.ii)

3

Podaří-li se vám vybrat n nezávislých nul, obsadíme místa matice, kde se nezávislé nuly nacházejí, hodnotou 1, ostatní pole hodnotou 0. Získali jsme optimální řešení přiřazovacího problému. Hodnota účelové funkce je rovna součtu původních sazeb příslušných místům obsazených jedničkami.

Michal Šmerek



Postup při užití maďarské metody 4

Je-li počet nezávislých nul menší než n, zjistíme pomocí tzv. Königovy věty, zda jsme vybrali maximální možný počet nezávislých nul. KÖNIGOVA VĚTA: Maximální počet nezávislých nul v matici je roven minimálnímu počtu krycích čar, jimiž je možné pokrýt všechny nulové sazby dané matice. Za tím účelem je potřeba všechny nulové sazby matice pokrýt minimálním počtem krycích čar. KONSTRUKCE KRYCÍCH ČAR: i) Řádky a sloupce, ve kterých neleží nezávislé nuly, označíme *. Nulovými sazbami takto označených řádků (resp. sloupců) vedeme svislé (resp. vodorovné) čáry. ii) Vynecháme řádky a sloupce označené * a řádky a sloupce pokryté čarami. Ve vzniklé submatici pokračujeme krokem 4.i). iii) Zůstanou-li nepokryté pouze řádky a sloupce s nezávislými nulami, vedeme minimální počet krycích čar i přes tyto nuly.

5

Je-li počet nalezených nezávislých nul roven počtu krycích čar, jimiž jsme pokryli všechny nulové sazby (tj. vybrali jsme maximální počet nezávislých nul), přistoupíme k další redukci sazeb matice: i) z nepokrytých polí vybereme minimální sazbu, ii) hodnotu této sazby odečteme od všech prvků nepokrytých krycími čarami, a přičteme k prvkům, kde se krycí čáry kříží, iii) sazby v polích pokrytých jedinou krycí čarou ponecháme nezměněny.

6

Celý postup opakujeme od 2. bodu (opět hledáme nezávislé nuly). Michal Šmerek



Př: Nalezněte všechna optimální řešení motivačního přiřazovacího problému s jeřáby. Řešení: Začneme redukcí matice sazeb dle bodu 1. algoritmu maďarské metody. Nejprve od sazeb každého řádku odečteme nejmenší sazbu v daném řádku. Protože ještě ve druhém sloupci není nulová sazba, odečteme od sazeb tohoto sloupce jedničku (nejmenší sazba tohoto sloupce). 0 1 1 1 0 0 4 3 1 −1 3 2 0 3 1 0 @ 1 2 6 A −1 −→ @ 0 1 5 A −→ @ 0 0 5 A 4 5 3 −3 1 2 0 1 1 0 −1 V poslední matici již je v každém řádku alespoň jedna nula a v každém sloupci je alespoň jedna nula. Dle bodu 2. nalezneme nezávislé nuly (označíme 1 ). V prvním řádku je jediná nula, proto ji můžeme označit, podobně ve druhém sloupci je jediná nula, i tu označíme za nezávislou. Samozřejmě dbáme na pravidlo, že nelze označit za nezávislé dvě nuly v jednom řádku ani v jednom sloupci. 0 1 0 ∗ 1 0 ∗ 1 0 1 3 1 01 3 1 01 3 1 01 2 0 0 1 1 1 @0 0 5 A→ @ 0 0 5 A→ @ 0 0 5 A →@ 0 0 6 A ∗ 1 1 ∗ 1 1 0 0 0 1 1 0 0 0 1 Michal Šmerek



1 0 3 1 01 @ 0 01 5 A → @ ∗ 1 1 0 0

∗ 3 0 1

1 01 1

1 0 01 5 A→ @ ∗ 0

∗ 3 0 1

1 01 1

1 0 01 2 5 A →@ 0 0 0 1

0 0 0

1 0 6 A 0

Označíme * řádky a sloupce, v nichž nejsou nezávislé nuly a vyznačíme krycí čáry, tj. postupujeme dle bodu 4.i). Počet krycích čar (jimiž jsme pokryli všechny nulové sazby) je roven počtu nalezených nezávislých nul. Tím jsme si ověřili, že jsme skutečně vybrali maximální počet nezávislých nul. Nejmenší z nepokrytých sazeb má hodnotu 1. Provedeme redukci matice sazeb podle bodu 5. V této znovu redukované matici opět hledáme nezávislé nuly. Tentokrát jsme již našli tři (tolik, kolik je řád matice) nezávislé nuly. A dokonce jsme objevili tři trojice nezávislých nul (odlišeny indexem). 1 0 1 0 2 03 012 2 0 0 @ 0 0 6 A −→ @ 023 01 6 A 0 0 0 01 02 03 Úloha má proto tři optimální řešení.

Michal Šmerek



Úloha má proto tři 0 0 0 Xopt,1 = @ 0 1 1 0 0 0 0 Xopt,2 = @ 1 0 0 1 0 0 1 Xopt,3 = @ 1 0 0 0

optimální 1 1 0 A, 0 1 1 0 A, 0 1 0 0 A, 1

řešení: z(Xopt,1 ) = 1 + 2 + 4 = 7,

z(Xopt,2 ) = 1 + 1 + 5 = 7,

z(Xopt,3 ) = 1 + 3 + 3 = 7.

Michal Šmerek



Poznámka: Celý postup budeme zapisovat stručněji. příkladu by vypadalo například takto: 0 1 1 0 0 ∗ 3 4 3 1 −1 3 2 0 @ 1 2 6 A −1 −→ @ 0 1 5 A −→ @ 0 ∗ 1 4 5 3 −3 1 2 0 −1 0 1 2 03 012 23 1 0 6 A −→ @ 0 01 02 03

Michal Šmerek

Řešení předchozího

1 01 1


1 01 5 A −→ 0 1


Přiřazovací problém maximalizačního typu Dosud jsme se věnovali přiřazovacím úlohám minimalizačního typu. Nejsou však vyjímkou přiřazovací problémy maximalizačního typu. Převádíme je na minimalizační přiřazovací problém, který má stejnou množinu všech optimálních řešení jako původní maximalizační úloha. Tento převod na úlohu minimalizační provádíme tak, že všechny prvky matice vynásobíme číslem (−1). Dále postupujeme maďarskou metodou.

Michal Šmerek



Př: Uvažujme firmu, v níž čtyři pracovníci Pi , i = 1, 2, 3, 4, mohou vyrábět čtyři druhy výrobků Vj , j = 1, 2, 3, 4 (podle toho, na kterou ze čtyř výrobních linek jsou pracovníci přiřazeni). Počet cij výrobků Vj , které je pracovník Pi schopen za 1 hodinu vyrobit je uveden v tabulce. Určete, které výrobky bude vyrábět který pracovník, aby celkový počet výrobků vyrobených za 1 hodinu byl maximální. cij P1 P2 P3 P4

V1 5 6 20 10

Michal Šmerek

V2 17 15 10 15

V3 23 17 10 20

V4 10 15 15 15



Řešení: 0 5 B 6 B @ 20 10

17 15 10 15

0

23 17 10 20

1 0 10 B 15 C C · (−1) → B A @ 15 15

18 B 11 →B @ 0 10

6 2 10 5 −2

0 0 10 0

0

1 01 5 02

012 3 10 0

18 B 14 →B @ 012 10

0 1 18 13 B 11 2 C C→B 1 @ 0 5 A ∗ 10 5 −2

−5 −6 −20 −10

4 01 8 3

−17 −15 −10 −15

01 0 10 0

−23 −17 −10 −20 ∗ 11 0 3 3

1 C C → A

1 8 02 C C 0 A 1 0

Michal Šmerek


3

1 −(−23) −10 −(−17) −15 C C → −15 A −(−20) −(−20) −15


Úloha má dvě optimální řešení:

0 B 0 =B @ 1 0

0 1 0 0

1 0 0 0

1 0 0 C C, 0 A 1

z(Xopt,1 ) = 23 + 15 + 20 + 15 = 73 ks/hod.,

0

0 0 0 1

1 0 0 0

1 0 1 C C, 0 A 0

z(Xopt,2 ) = 23 + 15 + 20 + 15 = 73 ks/hod.

0

Xopt,1

Xopt,2

0 B 0 =B @ 1 0

Michal Šmerek


Operační výzkum. Přiřazovací problém

Recommend Documents