Přiřazovací úloha

Literatura

Kosková: Distribuční úlohy I

Typ úlohy

• Jednostupňová dopravní úloha

• Počet dodavatelů = počtu spotřebitelů (m)

• Čtvercová matice sazeb

• Kapacity všech dodavatelů se rovnají 1

• Požadavky všech spotřebitelů se rovnají 1

• Počet obsazených polí musí být roven m (porovnej s m+n-1 u jednostupňové DÚ)

Matematický model

Účelová funkce

Podmínky

Přiřazení se buď uskuteční x=1 nebo neuskuteční x=0

m

i

m

jijij zxc

1 1min

m

jjij

m

jiij

mjbx

miax

1

1

,...,2,11

,...,2,11

1,0ijx

Maďarská metoda

1. Primární redukce matice sazeb

2. Výběr nezávislých nul

3. Kontrola správnosti výběru ( krycí čáry)

4. Sekundární redukce matice sazeb

5. Opakujeme kroky 2, 3 a 4 dokud není nalezeno m nezávislých nul

Příklad - Kombajny

Pět kombajnů pracuje na 5 polích (A,B,C,D,E).

Během dne, když sklizeň dokončí, se mají přesunout na jiných 5 polí (F,G,H,I,J), kde se dosud sekat nezačalo.

Vzájemné vzdálenosti polí jsou v tabulce.

Navrhněte, přesuny tak, aby celkový ujetý počet kilometrů byl co nejnižší.

Pole, kde se ještě nezačalo

Skli-zená pole

F G H I J

A 10 20 15 12 10

B 8 10 15 11 6

C 15 18 12 8 10

D 10 12 4 15 20

E 15 11 14 10 15

Příklad - kombajny

Primární redukce

Cíl: V každém řádku a v každém sloupci alespoň jedna nula.

1. V každém řádku od všech sazeb odečteme nejnižší sazbu.

2. Ve sloupcích, kde není žádná nula, odečítáme nejnižší sazbu od všech sazeb ve sloupci.

Pole, kde se ještě nezačalo odečítám

Skli-zená pole

F G H I J

A 0 10 5 2 0 10

B 2 4 9 5 0 6

C 7 10 4 0 2 8

D 6 8 0 11 16 4

E 5 1 4 0 5 10

Primární redukce - řádková

V sloupci G není nula

Pole, kde se ještě nezačalo

Skli-zená pole

F G H I J

A 0 9 5 2 0

B 2 3 9 5 0

C 7 9 4 0 2

D 6 7 0 11 16

E 5 0 4 0 5

Primární redukce - sloupcová

Odečítám 1 ve sloupci G

Pole, kde se ještě nezačalo

Skli-zená pole

F G H I J

A 0 9 5 2 0

B 2 3 9 5 0

C 7 9 4 0 2

D 6 7 0 11 16

E 5 0 4 0 5

Výběr nezávislých nul

Silně nezávislá nulaSama v řádku i ve sloupci

Slabě nezávislá nulaSama v řádku, resp. sloupci

Pole, kde se ještě nezačalo

Skli-zená pole

F G H I J

A 0 9 5 2 0

B 2 3 9 5 0

C 7 9 4 0 2

D 6 7 0 9 16

E 5 0 4 0 5

Výběr nezávislých nul

• V každém řádku a sloupci musí být jedna vybraná nula

Konec řešení Pole, kde se ještě nezačalo

Skli-zená pole

F G H I J

A 10 20 15 12 10

B 8 10 15 11 6

C 15 18 12 8 10

D 10 12 4 15 20

E 15 11 14 10 15

• Podařilo se vybrat m nezávislých nul . Výpočet končí.

• Počet ujetých kilometrů:10+11+4+8+6=39

Příklad 2

F G H I J

A 10 20 15 12 14

B 10 10 15 12 15

C 12 18 12 10 10

D 10 12 14 15 20

E 15 11 12 10 15

Příklad 2- řádková redukce

F G H I J

A 0 10 5 2 4

B 0 0 5 2 5

C 2 8 2 0 0

D 0 2 4 5 10

E 5 1 2 0 5

Příklad 2 - sloupcová redukce

F G H I J

A 0 10 3 2 4

B 0 0 3 2 5

C 2 8 0 0 0

D 0 2 2 5 10

E 5 1 0 0 5

Příklad 2 - výběr nezávislých nul

F G H I J

A 0 10 3 2 4

B 0 0 3 2 5

C 2 8 0 0 0

D 0 2 2 5 10

E 5 1 0 0 5

• Neexistuje žádná silně nezávislá nula• Nutno vybrat další tři nuly• Nepodařilo se

Příklad 2 - krycí čáryF G H I J

A 0 10 3 2 4

B 0 0 3 2 5

C 2 8 0 0 0

D 0 2 2 5 10

E 5 1 0 0 5

• Začínáme čárou kolmou na řadu, kde není nezávislá nula (tyto řady jsou žluté) vedenou přes nulový prvek

• Cílem je pokrýt všechny nuly. • Počet čar se musí rovnat počtu vybraných nul, tj. 4.

Příklad 2 – sekundární redukceF G H I J

A 0 10 3 2 4

B 0 0 3 2 5

C 2 8 0 0 0

D 0 2 2 5 10

E 5 1 0 0 5

• Najdeme minimum z hodnot nepokrytých prvků, to je rovno 22

• Od nepokrytých prvků tuto hodnotu jednou odčítáme

• Ke dvakrát pokrytým tuto hodnotu přičítáme

Příklad 2 - sekundární redukceF G H I J

A 0 10 1 0 2

B 0 0 1 0 3

C 4 10 0 0 0

D 0 2 0 3 8

E 7 3 0 0 5

Příklad 2 - výběr nezávislých nul

F G H I J

A 0 10 1 0 2

B 0 0 1 0 3

C 4 10 0 0 0

D 0 2 0 3 8

E 7 3 0 0 5

• Pokud by se nepodařilo vybrat 5 nezávislých nul, musíme opakovat krycí čáry a sekundární redukci

Příklad 2 – konec řešení

F G H I J

A 0 10 1 0 2

B 0 0 1 0 3

C 4 10 0 0 0

D 0 2 0 3 8

E 7 3 0 0 5

• Minimální náklady

Zmin=10+10+12+12+10=54