Badania Operacyjne w Logistyce

Wykład 3

Zadania pokrewne zadaniu transportowemu

Jacek Rogowski

Instytut Matematyki

Politechnika Łó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 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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

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{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

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{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

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{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

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{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

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{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

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{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

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{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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

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 = [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

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 = [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

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 = [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

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 = [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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

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 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

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 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

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 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

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 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

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 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

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 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

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 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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

BOwL Wykład 3: Zadanie pokrewne ZT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

BOwL Wykład 3: Zadanie pokrewne ZT