Badania Operacyjne w Logistyce
Wykład 3
Zadania pokrewne zadaniu transportowemu
Jacek Rogowski
Instytut Matematyki
Politechnika A
ódzka
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n).
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n). Znane sÄ…:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n). Znane sÄ…:
ai  podaż i-tego dostawcy dla i = 1, 2, . . . , m,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n). Znane sÄ…:
ai  podaż i-tego dostawcy dla i = 1, 2, . . . , m,
bj  popyt j-tego dostawcy dla j = 1, 2, . . . , n,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n). Znane sÄ…:
ai  podaż i-tego dostawcy dla i = 1, 2, . . . , m,
bj  popyt j-tego dostawcy dla j = 1, 2, . . . , n,
tij  czas przewozu na trasie (i, j) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n). Znane sÄ…:
ai  podaż i-tego dostawcy dla i = 1, 2, . . . , m,
bj  popyt j-tego dostawcy dla j = 1, 2, . . . , n,
tij  czas przewozu na trasie (i, j) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
m n

Założenie: ai = bj.
i=1 j=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców Di, (i = 1, 2, . . . , m), do n odbiorców: Oj,
(j = 1, 2, . . . , n). Znane sÄ…:
ai  podaż i-tego dostawcy dla i = 1, 2, . . . , m,
bj  popyt j-tego dostawcy dla j = 1, 2, . . . , n,
tij  czas przewozu na trasie (i, j) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
m n

Założenie: ai = bj.
i=1 j=1
Problem: Należy znalez
ć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych. Dla każdego ukÅ‚adu tras bazowych É " &! oznaczmy
T (É) = max{tij : (i, j) " É}.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych. Dla każdego ukÅ‚adu tras bazowych É " &! oznaczmy
T (É) = max{tij : (i, j) " É}.
Funkcja celu:
T (É) min, É " &!
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych. Dla każdego ukÅ‚adu tras bazowych É " &! oznaczmy
T (É) = max{tij : (i, j) " É}.
Funkcja celu:
T (É) min, É " &!
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych. Dla każdego ukÅ‚adu tras bazowych É " &! oznaczmy
T (É) = max{tij : (i, j) " É}.
Funkcja celu:
T (É) min, É " &!
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
m

xij = bj, j = 1, 2, . . . , n.
i=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych. Dla każdego ukÅ‚adu tras bazowych É " &! oznaczmy
T (É) = max{tij : (i, j) " É}.
Funkcja celu:
T (É) min, É " &!
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
m

xij = bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Oznaczmy przez &! zbiór wszystkich dopuszczalnych układów tras
bazowych. Dla każdego ukÅ‚adu tras bazowych É " &! oznaczmy
T (É) = max{tij : (i, j) " É}.
Funkcja celu:
T (É) min, É " &!
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
m

xij = bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiÄ…zania ZTzKC:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiÄ…zania ZTzKC:
Liczby należące do zbioru
{tij : i = 1, 2, . . . , m, j = 1, 2, . . . , n}
ustawiamy w ciÄ…g rosnÄ…cy:
T1 < T2 < . . . < Tr .
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiÄ…zania ZTzKC:
Liczby należące do zbioru
{tij : i = 1, 2, . . . , m, j = 1, 2, . . . , n}
ustawiamy w ciÄ…g rosnÄ…cy:
T1 < T2 < . . . < Tr .
Znajdujemy najmniejszy wskaz
nik k taki, że zbiór &!k tras
(i, j), dla których tij Tk, zawiera przynajmniej jeden
dopuszczalny układ tras bazowych.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiÄ…zania ZTzKC:
Liczby należące do zbioru
{tij : i = 1, 2, . . . , m, j = 1, 2, . . . , n}
ustawiamy w ciÄ…g rosnÄ…cy:
T1 < T2 < . . . < Tr .
Znajdujemy najmniejszy wskaz
nik k taki, że zbiór &!k tras
(i, j), dla których tij Tk, zawiera przynajmniej jeden
dopuszczalny układ tras bazowych.
Wybieramy dowolny układ tras bazowych ze zbioru &!k i
przyjmujemy go za rozwiÄ…zanie ZTzKC.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiÄ…zania ZTzKC:
Liczby należące do zbioru
{tij : i = 1, 2, . . . , m, j = 1, 2, . . . , n}
ustawiamy w ciÄ…g rosnÄ…cy:
T1 < T2 < . . . < Tr .
Znajdujemy najmniejszy wskaz
nik k taki, że zbiór &!k tras
(i, j), dla których tij Tk, zawiera przynajmniej jeden
dopuszczalny układ tras bazowych.
Wybieramy dowolny układ tras bazowych ze zbioru &!k i
przyjmujemy go za rozwiązanie ZTzKC. Wówczas
Tk = Tmin := min{T (É) : É " &!}.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [cij]
jednostkowych kosztów transportu na wszystkich trasach (i, j).
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [cij]
jednostkowych kosztów transportu na wszystkich trasach (i, j).
Oznaczmy
&!min = {É " &! : T (É) = Tmin}.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [cij]
jednostkowych kosztów transportu na wszystkich trasach (i, j).
Oznaczmy
&!min = {É " &! : T (É) = Tmin}.
SpoÅ›ród wszystkich ukÅ‚adów tras bazowych É " &!min należy
wybrać tę trasę, dla której łączny koszt przewozu towaru od
dostawców do odbiorców jest najmniejszy.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [cij]
jednostkowych kosztów transportu na wszystkich trasach (i, j).
Oznaczmy
&!min = {É " &! : T (É) = Tmin}.
SpoÅ›ród wszystkich ukÅ‚adów tras bazowych É " &!min należy
wybrać tę trasę, dla której łączny koszt przewozu towaru od
dostawców do odbiorców jest najmniejszy.
Tak postawione zadanie nazywamy zadaniem transportowym z
priorytetem czasu.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m n

cijxij min, {xij} " &!min
i=1 j=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m n

cijxij min, {xij} " &!min
i=1 j=1
Ograniczenia:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m n

cijxij min, {xij} " &!min
i=1 j=1
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m n

cijxij min, {xij} " &!min
i=1 j=1
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
m

xij = bj, j = 1, 2, . . . , n.
i=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m n

cijxij min, {xij} " &!min
i=1 j=1
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
m

xij = bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m n

cijxij min, {xij} " &!min
i=1 j=1
Ograniczenia:
n

xij = ai, i = 1, 2, . . . , m,
j=1
m

xij = bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
RozwiÄ…zujemy ZTzKC i wyznaczamy Tmin,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Wybieramy liczbę M większą od każdej jednostkowej ceny
przewozu cij, i = 1, . . . , m, j = 1, . . . , n.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Wybieramy liczbę M większą od każdej jednostkowej ceny
przewozu cij, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i, j), dla której tij > Tmin, zastępujemy w
macierzy kosztów jednostkowych liczbę cij przez liczbę M
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Wybieramy liczbę M większą od każdej jednostkowej ceny
przewozu cij, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i, j), dla której tij > Tmin, zastępujemy w
macierzy kosztów jednostkowych liczbę cij przez liczbę M
otrzymując nową macierz kosztów jednostkowych C .
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Wybieramy liczbę M większą od każdej jednostkowej ceny
przewozu cij, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i, j), dla której tij > Tmin, zastępujemy w
macierzy kosztów jednostkowych liczbę cij przez liczbę M
otrzymując nową macierz kosztów jednostkowych C .
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C .
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Wybieramy liczbę M większą od każdej jednostkowej ceny
przewozu cij, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i, j), dla której tij > Tmin, zastępujemy w
macierzy kosztów jednostkowych liczbę cij przez liczbę M
otrzymując nową macierz kosztów jednostkowych C .
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C . Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i, j), dla których
tij Tmin
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiÄ…zania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy Tmin, czyli najkrótszy
czas w jakim może być zrealizowany przewóz towaru od
dostawców do odbiorców zaspokajający ich oczekiwania.
Wybieramy liczbę M większą od każdej jednostkowej ceny
przewozu cij, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i, j), dla której tij > Tmin, zastępujemy w
macierzy kosztów jednostkowych liczbę cij przez liczbę M
otrzymując nową macierz kosztów jednostkowych C .
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C . Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i, j), dla których
tij Tmin i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób. Dla każdej pary (i, j), i, j = 1, . . . , n, znane są
koszty cij wykonania i-tego zadania przez j-tÄ… osobÄ™.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób. Dla każdej pary (i, j), i, j = 1, . . . , n, znane są
koszty cij wykonania i-tego zadania przez j-tÄ… osobÄ™.
Należy znalez
ć taki jednoznaczny przydział zadań poszczególnym
osobom, dla którego łaczne koszty wykonania wszystkich zadań
były najmniejsze.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób. Dla każdej pary (i, j), i, j = 1, . . . , n, znane są
koszty cij wykonania i-tego zadania przez j-tÄ… osobÄ™.
Należy znalez
ć taki jednoznaczny przydział zadań poszczególnym
osobom, dla którego łaczne koszty wykonania wszystkich zadań
były najmniejsze.
Uwagi:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób. Dla każdej pary (i, j), i, j = 1, . . . , n, znane są
koszty cij wykonania i-tego zadania przez j-tÄ… osobÄ™.
Należy znalez
ć taki jednoznaczny przydział zadań poszczególnym
osobom, dla którego łaczne koszty wykonania wszystkich zadań
były najmniejsze.
Uwagi:
Niezdolność i-tej osoby do wykonania j-tego zadania
uwzględniamy przyjmując wysokie koszty cij.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób. Dla każdej pary (i, j), i, j = 1, . . . , n, znane są
koszty cij wykonania i-tego zadania przez j-tÄ… osobÄ™.
Należy znalez
ć taki jednoznaczny przydział zadań poszczególnym
osobom, dla którego łaczne koszty wykonania wszystkich zadań
były najmniejsze.
Uwagi:
Niezdolność i-tej osoby do wykonania j-tego zadania
uwzględniamy przyjmując wysokie koszty cij.
Niekiedy zakłada się, że cij jest zyskiem z wykonania i-tego
zadania przez j-tÄ… osobÄ™.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Problem optymalnego przydziału zadań (POPZ)
Rozważamy n zadań, z których każde może zostać przydzielone
każdej z n osób. Dla każdej pary (i, j), i, j = 1, . . . , n, znane są
koszty cij wykonania i-tego zadania przez j-tÄ… osobÄ™.
Należy znalez
ć taki jednoznaczny przydział zadań poszczególnym
osobom, dla którego łaczne koszty wykonania wszystkich zadań
były najmniejsze.
Uwagi:
Niezdolność i-tej osoby do wykonania j-tego zadania
uwzględniamy przyjmując wysokie koszty cij.
Niekiedy zakłada się, że cij jest zyskiem z wykonania i-tego
zadania przez j-tą osobę. W takim przypadku przydział zadań
powinien być taki, aby łączny zysk z wykonania wszystkich
zadań był największy.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Ograniczenia:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Ograniczenia:
n

xij = 1, i = 1, 2, . . . , n,
j=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Ograniczenia:
n

xij = 1, i = 1, 2, . . . , n,
j=1
n

xij = 1, j = 1, 2, . . . , n.
i=1
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Ograniczenia:
n

xij = 1, i = 1, 2, . . . , n,
j=1
n

xij = 1, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Ograniczenia:
n

xij = 1, i = 1, 2, . . . , n,
j=1
n

xij = 1, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij " {0, 1}, i = 1, 2, . . . , n, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Formalizacja POPZ
Funkcja celu:
n n

cijxij min,
i=1 j=1
Ograniczenia:
n

xij = 1, i = 1, 2, . . . , n,
j=1
n

xij = 1, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij " {0, 1}, i = 1, 2, . . . , n, j = 1, 2, . . . , n.
xij = 1 Ð!Ò! i-te zadanie przydzielono j-tej osobie.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
4 Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C zawierajÄ…ce zera.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
4 Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C zawierajÄ…ce zera.
5 Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C następująco:
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
4 Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C zawierajÄ…ce zera.
5 Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C następująco:

w macierzy C znajdujemy najmniejszy nieskreślony element c,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
4 Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C zawierajÄ…ce zera.
5 Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C następująco:

w macierzy C znajdujemy najmniejszy nieskreślony element c,
odejmujemy c od elementów nieskreślonych,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
4 Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C zawierajÄ…ce zera.
5 Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C następująco:

w macierzy C znajdujemy najmniejszy nieskreślony element c,
odejmujemy c od elementów nieskreślonych,
dodajemy c do elementów skreślonych podwójnie,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
1 W każdym wierszu macierzy C = [cij] od każdego wyrazu
odejmujemy najmniejszy wyraz tego wiersza.
2 W tych kolumnach otrzymanej macierzy, które nie zawierają
zera, od każdego wyrazu odejmujemy najmniejszy wyraz tej
kolumny.

3 W każdej linii otrzymanej macierzy C znajduje się co
najmniej jedno zero.
4 Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C zawierajÄ…ce zera.
5 Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C następująco:

w macierzy C znajdujemy najmniejszy nieskreślony element c,
odejmujemy c od elementów nieskreślonych,
dodajemy c do elementów skreślonych podwójnie,
wracamy do kroku 4.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
dla każdego z wybranych pól (i, j) przyjmujemy xij = 1,
Å»
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
dla każdego z wybranych pól (i, j) przyjmujemy xij = 1,
Å»
wszystkie pozostałe pola wypełniamy zerami.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
dla każdego z wybranych pól (i, j) przyjmujemy xij = 1,
Å»
wszystkie pozostałe pola wypełniamy zerami.
Uwaga: Jeżeli w POPZ liczba zadań jest różna od liczby osób,
należy wyrównać te liczby
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
dla każdego z wybranych pól (i, j) przyjmujemy xij = 1,
Å»
wszystkie pozostałe pola wypełniamy zerami.
Uwaga: Jeżeli w POPZ liczba zadań jest różna od liczby osób,
należy wyrównać te liczby poprzez wprowadzenie fikcyjnych osób
lub zadań.
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
dla każdego z wybranych pól (i, j) przyjmujemy xij = 1,
Å»
wszystkie pozostałe pola wypełniamy zerami.
Uwaga: Jeżeli w POPZ liczba zadań jest różna od liczby osób,
należy wyrównać te liczby poprzez wprowadzenie fikcyjnych osób
lub zadań. Dla fikcyjnych osób/zadań przyjmujemy cij = M 0
(w przypadku zadania typu min)
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT
Algorytm węgierski rozwiązywania POPZ
6 Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C jest równa n,
Å»
konstruujemy optymalne rozwiązanie X = [Żij] następująco:
x

dla każdej pary (i, j): jeżeli cij = 0, to przyjmujemy xij = 0,
Å»
Å»
z pozostałych (niewypełnionych zerami) pól macierzy X
wybieramy n pól w taki sposób, aby w każdym wierszu i każdej
Å»
kolumnie macierzy X znalazło się dokładnie jedno takie pole,
dla każdego z wybranych pól (i, j) przyjmujemy xij = 1,
Å»
wszystkie pozostałe pola wypełniamy zerami.
Uwaga: Jeżeli w POPZ liczba zadań jest różna od liczby osób,
należy wyrównać te liczby poprzez wprowadzenie fikcyjnych osób
lub zadań. Dla fikcyjnych osób/zadań przyjmujemy cij = M 0
(w przypadku zadania typu min) albo cij = 0 (w przypadku
zadania typu max).
Jacek Rogowski BOwL Wykład 3: Zadanie pokrewne ZT