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).
937540456.047.png 937540456.058.png 937540456.069.png 937540456.080.png 937540456.001.png
 
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.
937540456.002.png 937540456.003.png 937540456.004.png 937540456.005.png 937540456.006.png 937540456.007.png 937540456.008.png 937540456.009.png 937540456.010.png 937540456.011.png 937540456.012.png 937540456.013.png 937540456.014.png 937540456.015.png
 
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).
937540456.016.png 937540456.017.png 937540456.018.png 937540456.019.png 937540456.020.png 937540456.021.png 937540456.022.png 937540456.023.png 937540456.024.png 937540456.025.png 937540456.026.png 937540456.027.png 937540456.028.png 937540456.029.png 937540456.030.png 937540456.031.png 937540456.032.png 937540456.033.png 937540456.034.png 937540456.035.png 937540456.036.png
 
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
937540456.037.png 937540456.038.png 937540456.039.png 937540456.040.png 937540456.041.png 937540456.042.png 937540456.043.png 937540456.044.png 937540456.045.png 937540456.046.png 937540456.048.png 937540456.049.png 937540456.050.png 937540456.051.png 937540456.052.png 937540456.053.png 937540456.054.png 937540456.055.png 937540456.056.png 937540456.057.png 937540456.059.png 937540456.060.png 937540456.061.png 937540456.062.png 937540456.063.png 937540456.064.png 937540456.065.png 937540456.066.png 937540456.067.png 937540456.068.png 937540456.070.png 937540456.071.png 937540456.072.png 937540456.073.png 937540456.074.png 937540456.075.png 937540456.076.png 937540456.077.png 937540456.078.png 937540456.079.png 937540456.081.png 937540456.082.png 937540456.083.png 937540456.084.png 937540456.085.png 937540456.086.png 937540456.087.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin