algorytm węgierski.pdf
(
126 KB
)
Pobierz
Badania operacyjne I
ZAGADNIENIE PRZYDZIAýU (ZP)
(Assignment Problem)
Bliskim "krewniakiem" ZT (w sensie podobieıstwa modelu
decyzyjnego) jest zagadnienie przydziaþu (ZP). Oglnie przez ZP rozumiemy
nastħpujĢcĢ sytuacjħ decyzyjnĢ.
Dane jest
n celw
i
n Ļrodkw
do ich realizacji. Z kaŇdym
skojarzeniem i-tego celu oraz j-tego Ļrodka zwiĢzana jest pewna korzyĻę
i
c
.
KaŇdy cel musi byę zrealizowany, a kaŇdy ze Ļrodkw moŇe byę uŇyty tylko
jeden raz
.
Oznaczmy zmiennĢ decyzyjnĢ ZP przez
i
x
. Zmienna taka moŇe przybieraę
dwie wartoĻci:
x
=
gdy i-ty cel
jest
realizowany za pomocĢ j-tego Ļrodka albo
ij
x
=
gdy i-ty cel
nie jest
realizowany za pomocĢ j-tego Ļrodka.
ij
NaleŇy znaleŅę takie skojarzenia wszystkich celw z Ļrodkami, aby þĢczna
korzyĻę z takich skojarzeı byþa najlepsza.
Model decyzyjny ZP jest nastħpujĢcy:
n
n
(1)
max (min) x =
c x
Ã
Ã
i
=
j
=
ij ij
(þĢczna korzyĻę)
n
x
=
i
=
n
Ã
j
=
ij
(2)
(bilanse dla celw)
n
=
x
=
j
=
n
Ã
i
ij
(3)
(bilanse dla Ļrodkw)
{
}
x
ij
¬
i
=
n j
=
n
(4)
Model decyzyjny ZP (1)-(4)
nie jest zadaniem PL
z uwagi na binarne
(nieliniowe) warunki (4).
Badania operacyjne I
Model decyzyjny ZP (1)-(4) moŇna uoglnię poprzez rozwaŇanie
kojarzenia m celw z n Ļrodkami, gdzie m niekoniecznie musi rwnaę siħ n.
W modelu (1)-(4) zmieniĢ siħ wwczas relacje w bilansach (2) i (3).
<n , tj. w przypadku
nadwyŇki Ļrodkw nad celami
(nie kaŇdy
Ļrodek bħdzie wykorzystany), zastosujemy model (1)-(2),(3Ó),(4).
Przy m
max
(min)
x
=
m
i
n
j
c
ij
x
à Ã
(1)
=
=
ij
(þĢczna korzyĻę)
n
j
x
=
i
=
m
Ã
=
(2)
(bilanse dla celw)
ij
m
i
x
j
=
n
Ã
=
(3Ó)
ij
(bilanse dla Ļrodkw)
{ }
x
ij
¬
i
=
m
j
=
n
(4)
>n , tj. w przypadku
nadwyŇki celw nad Ļrodkami
(nie kaŇdy
cel bħdzie zrealizowany), zastosujemy model (1),(2Ó),(3)-(4).
Przy m
max
(min)
x
=
m
i
n
j
c
ij
x
à Ã
(1)
=
=
ij
(þĢczna korzyĻę)
n
j
x
i
=
m
Ã
=
(2Ó)
(bilanse dla celw)
ij
m
i
x
=
j
=
n
Ã
=
(3)
ij
(bilanse dla Ļrodkw)
{ }
x
ij
¬
i
=
m
j
=
n
(4)
Badania operacyjne I
ROZWIġZYWANIE ZP
Wykorzystanie KAT
(áuciĢŇliweÑ)
ZastĢpmy warunek (4) w ZP (1)-(4) warunkiem (4Ó) postaci:
x
ij
i
=
3
n
j
=
3
n
(4Ó)
Wwczas model ZP staje siħ analogiczny do modelu ZT. Wyrazy wolne
ograniczeı takiego ZT sĢ liczbami caþkowitymi (jedynki).
ZP (1)-(4) moŇemy rozwiĢzaę za pomocĢ KAT wykorzystujĢc twierdzenie 2
dla ZT (wykþad 4 s. 3) Î áprzy wyrazach wolnych w ZT w postaci liczb
caþkowitych jego rozwiĢzanie optymalne dane jest rwnieŇ w liczbach
caþkowitychÑ. Wynika stĢd, Ňe KAT zastosowany do rozwiĢzania ZP musi
daę rozwiĢzanie optymalne z wartoĻciami
0
lub
1
.
Jednak uŇywajĢc KAT musimy liczyę siħ z wystĢpieniem ágþħbokiejÑ
degeneracji rozwiĢzania bazowego (przy n Ļrodkach i n celach stopieı
degeneracji rozwiĢzania bazowego ZT wyniesie n+n-1-n =
n-1
). OkolicznoĻę
ta stanowi podstawowe utrudnienie zwiĢzane z wykorzystaniem KAT w
rozwiĢzywaniu ZP.
METODA WĦGIERSKA
(Hungarian Method)
Obecnie powszechnie stosowanĢ metodĢ rozwiĢzywania ZP jest metoda
nazywana wħgierskĢ (Hungarian Method) nie majĢca nic wsplnego z KAT.
W odniesieniu do teorii PL jest ona najbliŇsza dualizmowi w PL, choę
powstaþa na dþugo przed rozwiniħciem teorii PL.
Metodħ zawdziħczamy wħgierskiemu matematykowi
E.EgervaryÓemu
,
ktry opublikowaþ pierwotnĢ wersjħ omawianego dalej postħpowania juŇ w
1931 roku.
1953, 1955 Î H. Kuhn, tþumaczenie z wħgierskiego i publikacja z uŇyciem
nazwy áThe Hungarian methodÑ.
1957 Î J. Munkres rozwinĢþ metodħ wħgierskĢ na oglny przypadek ZT.
Badania operacyjne I
Postħpowanie
w metodzie wħgierskiej
(na przykþadzie)
Tabela podaje koszty wykonania usþug (A, B, C, D i E) przez technikw (T1,
T2, T3, T4 i T5). NaleŇy przydzielię kaŇdego z technikw do wykonania
jednej z usþug tak, aby þĢczny koszt wykonania wszystkich usþug byþ
minimalny. Cele to usþugi, Ļrodki to technicy.
i
c
T1 T2 T3 T4 T5
A
1
2
1
2
2
B
4
1
2
1
5
C
5
3
4
3
1
D
2
4
3
3
3
E
3
5
5
6
4
Model tego zagadnienia ZP jest nastħpujĢcy:
à Ã
K
=
c
x
n
ij
ij
i
=
j
=
Ã
x
=
i
=
ij
j
=
Ã
x
=
j
=
ij
i
=
{ }
x
¬
i
=
ij
j
=
UWAGA !!!
JeŇeli problem ZP dotyczy
maksymalizacji
(poszukiwanie
wartoĻci najwiħkszej funkcji celu
U
), to naleŇy wszystkie parametry
i
c
funkcji celu
pomnoŇyę przez (-1).
Badania operacyjne I
Etap wstħpny (redukcja macierzy
C
)
[ ]
=C
.
Od kaŇdego elementu wiersza
odejmujemy minimalny element w tym wierszu.
c
1.
Redukcja wierszy macierzy
ij
C
T1 T2 T3 T4 T5
minimum wiersza
A
1
2
1
2
2
1
B
4
1
2
1
5
1
C
5
3
4
3
1
1
D
2
4
3
3
3
2
E
3
5
5
6
4
3
[ ]
=C
.
Od kaŇdego elementu kolumny
odejmujemy minimalny element w tej
kolumnie.
CÓ
T1 T2 T3 T4 T5
c
2.
Redukcja kolumn macierzy
ij
A
0
1
0
1
1
B
3
0
1
0
4
C
4
2
3
2
0
D
0
2
1
1
1
E
0
2
2
3
1
0
0
0
0
0
minimum kolumny
[ ]
=C
CÓÓ
T1 T2 T3 T4 T5
A
c
Macierz zredukowana
ij
0
1
0
1
1
B
3
0
1
0
4
C
4
2
3
2
0
D
0
2
1
1
1
E
0
2
2
3
1
Plik z chomika:
Gumiho
Inne pliki z tego folderu:
algorytm węgierski.pdf
(126 KB)
Marszałkiewicz,Witaszczyk gr1.pdf
(787 KB)
Marszałkiewicz,Witaszczyk, gr1.docx
(68 KB)
Marszałkiewicz,Witaszczyk.pdf
(542 KB)
opty.zip
(44 KB)
Inne foldery tego chomika:
Avatary
Biznespaln
Galeria
Logistyka zaopatrzenia
Private
Zgłoś jeśli
naruszono regulamin