Badania Operacyjne w Logistyce
Wykład 3
Zadania pokrewne zadaniu transportowemu
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Badania Operacyjne w Logistyce
Wykład 3
Zadania pokrewne zadaniu transportowemu
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n).
Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n). Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n). Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n). Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n). Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n). Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Pewien jednorodny towar powinien zostać szybko dostarczony od
m dostawców D
i
, (i = 1, 2, . . . , m), do n odbiorców: O
j
,
(j = 1, 2, . . . , n). Znane są:
a
i
– podaż i -tego dostawcy dla i = 1, 2, . . . , m,
b
j
– popyt j -tego dostawcy dla j = 1, 2, . . . , n,
t
ij
– czas przewozu na trasie (i , j ) dla i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Założenie:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
Problem: Należy znaleźć taki plan przewozu towaru, aby popyt
odbiorców został zaspokojony i czas przewiezienia towaru na
najdłuższej trasie był najkrótszy.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
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{t
ij
: (i , j ) ∈ ω}.
Funkcja celu:
T (ω) → min,
ω ∈ Ω
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
ZTzKC nie jest ZPL.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiązania ZTzKC:
Liczby należące do zbioru
{t
ij
: i = 1, 2, . . . , m,
j = 1, 2, . . . , n}
ustawiamy w ciąg rosnący:
T
1
< T
2
< . . . < T
r
.
Znajdujemy najmniejszy wskaźnik k taki, że zbiór Ω
k
tras
(i , j ), dla których t
ij
¬ T
k
, 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
T
k
= T
min
:= min{T (ω) : ω ∈ Ω}.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiązania ZTzKC:
Liczby należące do zbioru
{t
ij
: i = 1, 2, . . . , m,
j = 1, 2, . . . , n}
ustawiamy w ciąg rosnący:
T
1
< T
2
< . . . < T
r
.
Znajdujemy najmniejszy wskaźnik k taki, że zbiór Ω
k
tras
(i , j ), dla których t
ij
¬ T
k
, 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
T
k
= T
min
:= min{T (ω) : ω ∈ Ω}.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiązania ZTzKC:
Liczby należące do zbioru
{t
ij
: i = 1, 2, . . . , m,
j = 1, 2, . . . , n}
ustawiamy w ciąg rosnący:
T
1
< T
2
< . . . < T
r
.
Znajdujemy najmniejszy wskaźnik k taki, że zbiór Ω
k
tras
(i , j ), dla których t
ij
¬ T
k
, 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
T
k
= T
min
:= min{T (ω) : ω ∈ Ω}.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiązania ZTzKC:
Liczby należące do zbioru
{t
ij
: i = 1, 2, . . . , m,
j = 1, 2, . . . , n}
ustawiamy w ciąg rosnący:
T
1
< T
2
< . . . < T
r
.
Znajdujemy najmniejszy wskaźnik k taki, że zbiór Ω
k
tras
(i , j ), dla których t
ij
¬ T
k
, 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
T
k
= T
min
:= min{T (ω) : ω ∈ Ω}.
Jacek Rogowski
Zadanie transportowe z kryterium czasu (ZTzKC)
Schemat rozwiązania ZTzKC:
Liczby należące do zbioru
{t
ij
: i = 1, 2, . . . , m,
j = 1, 2, . . . , n}
ustawiamy w ciąg rosnący:
T
1
< T
2
< . . . < T
r
.
Znajdujemy najmniejszy wskaźnik k taki, że zbiór Ω
k
tras
(i , j ), dla których t
ij
¬ T
k
, 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
T
k
= T
min
:= min{T (ω) : ω ∈ Ω}.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [c
ij
]
jednostkowych kosztów transportu na wszystkich trasach (i , j ).
Oznaczmy
Ω
min
= {ω ∈ Ω : T (ω) = T
min
}.
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
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [c
ij
]
jednostkowych kosztów transportu na wszystkich trasach (i , j ).
Oznaczmy
Ω
min
= {ω ∈ Ω : T (ω) = T
min
}.
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
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [c
ij
]
jednostkowych kosztów transportu na wszystkich trasach (i , j ).
Oznaczmy
Ω
min
= {ω ∈ Ω : T (ω) = T
min
}.
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
Zadanie transportowe z priorytetem czasu (ZTzPC)
Załóżmy, że dane jest ZTzKC, w którym dodatkowo znana jest
macierz
C = [c
ij
]
jednostkowych kosztów transportu na wszystkich trasach (i , j ).
Oznaczmy
Ω
min
= {ω ∈ Ω : T (ω) = T
min
}.
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
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z priorytetem czasu (ZTzPC)
Formalizacja ZTzPC
Funkcja celu:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
{x
ij
} ∈ Ω
min
Ograniczenia:
n
X
j =1
x
ij
= a
i
,
i = 1, 2, . . . , m,
m
X
i =1
x
ij
= b
j
,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
0,
i = 1, 2, . . . , m,
j = 1, 2, . . . , n.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
,
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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
.
Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
Zadanie transportowe z prirytetem czasu (ZTzPC)
Schemat rozwiązania ZTzPC:
Rozwiązujemy ZTzKC i wyznaczamy T
min
, 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 c
ij
, i = 1, . . . , m, j = 1, . . . , n.
Dla każdej trasy (i , j ), dla której t
ij
> T
min
, zastępujemy w
macierzy kosztów jednostkowych liczbę c
ij
przez liczbę M
otrzymując nową macierz kosztów jednostkowych C
0
.
Rozwiązujemy ZT z macierzą kosztów jednostkowych
transportu C
0
. Rozwiązanie optymalne tego ZT będzie
składało się tylko z tych tras bazowych (i , j ), dla których
t
ij
¬ T
min
i wśród takich rozwiązań dopuszczalnych będzie
realizowane po najmniejszym koszcie całkowitym.
Jacek Rogowski
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
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 c
ij
wykonania i -tego zadania przez j -tą osobę.
Należy znaleźć 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 c
ij
.
Niekiedy zakłada się, że c
ij
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
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Formalizacja POPZ
Funkcja celu:
n
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
Ograniczenia:
n
X
j =1
x
ij
= 1,
i = 1, 2, . . . , n,
n
X
i =1
x
ij
= 1,
j = 1, 2, . . . , n.
Warunki brzegowe:
x
ij
∈ {0, 1},
i = 1, 2, . . . , n,
j = 1, 2, . . . , n.
x
ij
= 1 ⇐⇒ i -te zadanie przydzielono j -tej osobie.
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
1
W każdym wierszu macierzy C = [c
ij
] 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
0
znajduje się co
najmniej jedno zero.
4
Używając możliwie najmniejszej liczby prostych należy skreślić
wszystkie linie macierzy C
0
zawierające zera.
5
Jeżeli liczba użytych prostych skreślających jest mniejsza od n,
to modyfikujemy macierz C
0
następująco:
w macierzy C
0
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
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min)
albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski
Algorytm węgierski rozwiązywania POPZ
6
Jeżeli minimalna liczba prostych użytych do skreślenia
wszystkich zawierających zera linii macierzy C
0
jest równa n,
konstruujemy optymalne rozwiązanie ¯
X = [¯
x
ij
] następująco:
dla każdej pary (i , j ): jeżeli c
0
ij
6= 0, to przyjmujemy ¯
x
ij
= 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 ¯
x
ij
= 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 c
ij
= M 0
(w przypadku zadania typu min) albo c
ij
= 0 (w przypadku
zadania typu max).
Jacek Rogowski