Badania Operacyjne w Logistyce
Wykład 2
Zadania sprowadzalne do zadania transportowego
Jacek Rogowski
Instytut Matematyki
Politechnika A
ódzka
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie. Przyjmijmy,
że zablokowaną trasą jest trasa (p, q).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie. Przyjmijmy,
że zablokowaną trasą jest trasa (p, q).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zmienić wyraz cpq
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie. Przyjmijmy,
że zablokowaną trasą jest trasa (p, q).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zmienić wyraz cpq zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów cij, gdzie (i, j) = (p, q).

Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie. Przyjmijmy,
że zablokowaną trasą jest trasa (p, q).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zmienić wyraz cpq zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów cij, gdzie (i, j) = (p, q).

Tak zmodyfikowane ZT może nie posiadać rozwiązania
optymalnego, w którym nie występuje trasa (p, q)
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie. Przyjmijmy,
że zablokowaną trasą jest trasa (p, q).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zmienić wyraz cpq zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów cij, gdzie (i, j) = (p, q).

Tak zmodyfikowane ZT może nie posiadać rozwiązania
optymalnego, w którym nie występuje trasa (p, q) niezależnie od
tego, jak duża liczba zastąpi wartość cpq.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z zablokowanÄ… trasÄ…
W dalszym ciągu będziemy zakładać, że dane jest
zbilansowane ZT z macierzą kosztów C.
Załóżmy, że jedna z tras jest zablokowana, tzn. nie jest możliwe
przewiezienie jakiejkolwiek ilości towaru na tej trasie. Przyjmijmy,
że zablokowaną trasą jest trasa (p, q).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zmienić wyraz cpq zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów cij, gdzie (i, j) = (p, q).

Tak zmodyfikowane ZT może nie posiadać rozwiązania
optymalnego, w którym nie występuje trasa (p, q) niezależnie od
tego, jak duża liczba zastąpi wartość cpq.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q)
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zastąpić p-ty wiersz przez dwa wiersze
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zastąpić p-ty wiersz przez dwa wiersze numerując je np. p oraz p .
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zastąpić p-ty wiersz przez dwa wiersze numerując je np. p oraz p .
Dostawcę Dp (którego podaż wynosi ap) zastępujemy dwoma

fikcyjnymi dostawcami: Dp oraz Dp
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zastąpić p-ty wiersz przez dwa wiersze numerując je np. p oraz p .
Dostawcę Dp (którego podaż wynosi ap) zastępujemy dwoma

fikcyjnymi dostawcami: Dp oraz Dp umieszczonymi w wierszach p
oraz p odpowiednio.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zastąpić p-ty wiersz przez dwa wiersze numerując je np. p oraz p .
Dostawcę Dp (którego podaż wynosi ap) zastępujemy dwoma

fikcyjnymi dostawcami: Dp oraz Dp umieszczonymi w wierszach p

oraz p odpowiednio. Dostawcy Dp przypisujemy podaż d
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewiez
ć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d min(ap, bq).
Aby uwzględnić powyższy warunek w zadaniu, należy w macierzy C
zastąpić p-ty wiersz przez dwa wiersze numerując je np. p oraz p .
Dostawcę Dp (którego podaż wynosi ap) zastępujemy dwoma

fikcyjnymi dostawcami: Dp oraz Dp umieszczonymi w wierszach p

oraz p odpowiednio. Dostawcy Dp przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu

cp j = cpj
na trasach od tego dostawcy.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu

cp j =
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu

cpj dla j = q,


cp j =
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu

cpj dla j = q,


cp j =
M dla j = q,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu

cpj dla j = q,


cp j =
M dla j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu

cpj dla j = q,


cp j =
M dla j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
Dp cp1 . . . cpq . . . cpn ap
z macierzy kosztów jednostkowych
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą

Dostawcy Dp przypisujemy podaż ap - d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu

cpj dla j = q,


cp j =
M dla j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
Dp cp1 . . . cpq . . . cpn ap
z macierzy kosztów jednostkowych zastępujemy wierszami:

Dp cp1 . . . cpq . . . cpn d
.

Dp cp1 . . . M . . . cpn ap - d
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy Dp można analogiczną procedurę
przeprowadzić dla odbiorcy Oq.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy Dp można analogiczną procedurę
przeprowadzić dla odbiorcy Oq.
W przypadku, gdy min(ap, bq) d < max(ap, bq) dokonujemy
 rozdwojenia
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy Dp można analogiczną procedurę
przeprowadzić dla odbiorcy Oq.
W przypadku, gdy min(ap, bq) d < max(ap, bq) dokonujemy
 rozdwojenia
dostawcy, jeżeli d < ap,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy Dp można analogiczną procedurę
przeprowadzić dla odbiorcy Oq.
W przypadku, gdy min(ap, bq) d < max(ap, bq) dokonujemy
 rozdwojenia
dostawcy, jeżeli d < ap,
odbiorcy, jeżeli d < bq.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy Dp można analogiczną procedurę
przeprowadzić dla odbiorcy Oq.
W przypadku, gdy min(ap, bq) d < max(ap, bq) dokonujemy
 rozdwojenia
dostawcy, jeżeli d < ap,
odbiorcy, jeżeli d < bq.
Jeżeli d max(ap, bq), ograniczenie przewozu na trasie (p, q) nie
ma wpływu na rozwiązanie ZT.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy Dp można analogiczną procedurę
przeprowadzić dla odbiorcy Oq.
W przypadku, gdy min(ap, bq) d < max(ap, bq) dokonujemy
 rozdwojenia
dostawcy, jeżeli d < ap,
odbiorcy, jeżeli d < bq.
Jeżeli d max(ap, bq), ograniczenie przewozu na trasie (p, q) nie
ma wpływu na rozwiązanie ZT.
Jeżeli w ZT występuje więcej niż jedna częściowo zablokowana
trasa, opisaną procedurę stosujemy do każdej z nich.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n). Producent Pi ma zdolność
produkcyjną ai jednostek towaru, zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n). Producent Pi ma zdolność
produkcyjną ai jednostek towaru, zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru. Dla każdej trasy (i, j) od
producenta Pi do odbiorcy Oj znany jest koszt cij transportu
jednostki towaru na tej trasie,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n). Producent Pi ma zdolność
produkcyjną ai jednostek towaru, zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru. Dla każdej trasy (i, j) od
producenta Pi do odbiorcy Oj znany jest koszt cij transportu
jednostki towaru na tej trasie, zaś dla każdego producenta Pi
znany jest koszt ki wytworzenia przez niego jednostki towaru.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n). Producent Pi ma zdolność
produkcyjną ai jednostek towaru, zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru. Dla każdej trasy (i, j) od
producenta Pi do odbiorcy Oj znany jest koszt cij transportu
jednostki towaru na tej trasie, zaś dla każdego producenta Pi
znany jest koszt ki wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewiez
ć od producentów do odbiorców tak, aby popyt
odbiorców został zaspokojony, a łączne koszty produkcji i
transportu były najniższe z możliwych.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n). Producent Pi ma zdolność
produkcyjną ai jednostek towaru, zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru. Dla każdej trasy (i, j) od
producenta Pi do odbiorcy Oj znany jest koszt cij transportu
jednostki towaru na tej trasie, zaś dla każdego producenta Pi
znany jest koszt ki wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewiez
ć od producentów do odbiorców tak, aby popyt
odbiorców został zaspokojony, a łączne koszty produkcji i
transportu były najniższe z możliwych.
Założenie:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
Pi, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: Oj, (j = 1, 2, . . . , n). Producent Pi ma zdolność
produkcyjną ai jednostek towaru, zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru. Dla każdej trasy (i, j) od
producenta Pi do odbiorcy Oj znany jest koszt cij transportu
jednostki towaru na tej trasie, zaś dla każdego producenta Pi
znany jest koszt ki wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewiez
ć od producentów do odbiorców tak, aby popyt
odbiorców został zaspokojony, a łączne koszty produkcji i
transportu były najniższe z możliwych.
Założenie:
m n

ai > bj. (1)
i=1 j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Z założenia (1) wynika, że rozważane zadanie nie jest ZT.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Z założenia (1) wynika, że rozważane zadanie nie jest ZT.
Schemat sprowadzania ZT-P do zbilansowanego ZT
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Z założenia (1) wynika, że rozważane zadanie nie jest ZT.
Schemat sprowadzania ZT-P do zbilansowanego ZT
Wprowadzamy fikcyjnego odbiorcę On+1, któremu
przypisujemy popyt
m n

bn+1 = ai - bj.
i=1 j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Z założenia (1) wynika, że rozważane zadanie nie jest ZT.
Schemat sprowadzania ZT-P do zbilansowanego ZT
Wprowadzamy fikcyjnego odbiorcę On+1, któremu
przypisujemy popyt
m n

bn+1 = ai - bj.
i=1 j=1
Konstruujemy macierz [kij] " Mm×(n+1) Å‚Ä…cznych kosztów
produkcji i transportu
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie transportowo-produkcyjne (ZT-P)
Z założenia (1) wynika, że rozważane zadanie nie jest ZT.
Schemat sprowadzania ZT-P do zbilansowanego ZT
Wprowadzamy fikcyjnego odbiorcę On+1, któremu
przypisujemy popyt
m n

bn+1 = ai - bj.
i=1 j=1
Konstruujemy macierz [kij] " Mm×(n+1) Å‚Ä…cznych kosztów
produkcji i transportu przyjmujÄ…c

hi + cij dla i = 1, . . . , m, j = 1, . . . , n,
kij =
0 dla i = 1, . . . , m, j = n + 1.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt oraz m
punktów, w których możliwe jest zlokalizowanie jego produkcji.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt oraz m
punktów, w których możliwe jest zlokalizowanie jego produkcji.
Popyt w j-tym punkcie zapotrzebowania wynosi bj,
(j = 1, 2, . . . , n),
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt oraz m
punktów, w których możliwe jest zlokalizowanie jego produkcji.
Popyt w j-tym punkcie zapotrzebowania wynosi bj,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i-tej
lokalizacji są równe ai, (i = 1, 2, . . . , m).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt oraz m
punktów, w których możliwe jest zlokalizowanie jego produkcji.
Popyt w j-tym punkcie zapotrzebowania wynosi bj,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i-tej
lokalizacji są równe ai, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji hi, (i = 1, 2, . . . , m)
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt oraz m
punktów, w których możliwe jest zlokalizowanie jego produkcji.
Popyt w j-tym punkcie zapotrzebowania wynosi bj,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i-tej
lokalizacji są równe ai, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji hi, (i = 1, 2, . . . , m) oraz znane sÄ…
przewidywane jednostkowe koszty transportu cij na każdej trasie
(i, j).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Dane jest n punktów zapotrzebowania na pewien produkt oraz m
punktów, w których możliwe jest zlokalizowanie jego produkcji.
Popyt w j-tym punkcie zapotrzebowania wynosi bj,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i-tej
lokalizacji są równe ai, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji hi, (i = 1, 2, . . . , m) oraz znane sÄ…
przewidywane jednostkowe koszty transportu cij na każdej trasie
(i, j).
Należy ustalić, w których punktach należy uruchomić produkcję, ile
produktu wytwarzać w każdym z uruchomionych punktów
produkcji i jak zaplanować transport wytworzonego produktu, aby
zaspokoić zapotrzebowanie odbiorców ponosząc jednocześnie
najmniejsze Å‚Ä…czne koszty produkcji i transportu.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m n

ai > bj.
i=1 j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m n

ai > bj.
i=1 j=1
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m n

ai > bj.
i=1 j=1
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
n

ai < bj dla pewnego i " {1, 2, . . . , m}.
j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m n

ai > bj.
i=1 j=1
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
n

ai < bj dla pewnego i " {1, 2, . . . , m}.
j=1
n

Gdyby dla każdego i zachodziła nierówność ai bj
j=1
produkcja w jednej lokalizacji zaspokoiłaby całkowity popyt.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m n

ai > bj.
i=1 j=1
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
n

ai < bj dla pewnego i " {1, 2, . . . , m}.
j=1
n

Gdyby dla każdego i zachodziła nierówność ai bj
j=1
produkcja w jednej lokalizacji zaspokoiłaby całkowity popyt.
ZLP sprowadza się do ZT w identyczny sposób, jak ZT-P.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m n

ai > bj.
i=1 j=1
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
n

ai < bj dla pewnego i " {1, 2, . . . , m}.
j=1
n

Gdyby dla każdego i zachodziła nierówność ai bj
j=1
produkcja w jednej lokalizacji zaspokoiłaby całkowity popyt.
ZLP sprowadza się do ZT w identyczny sposób, jak ZT-P. Ilości
produktu przewożone do fikcyjnego odbiorcy oznaczają, o ile należy
zmniejszyć moce produkcyjne poszczególnych lokalizacji.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
ai  podaż i-tego dostawcy, i = 1, 2, . . . , m,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
ai  podaż i-tego dostawcy, i = 1, 2, . . . , m,
bj  popyt j-tego odbiorcy, j = 1, 2, . . . , n,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
ai  podaż i-tego dostawcy, i = 1, 2, . . . , m,
bj  popyt j-tego odbiorcy, j = 1, 2, . . . , n,
ki  cena zakupu jednostki towaru u i-tego dostawcy,
i = 1, 2, . . . , m,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
ai  podaż i-tego dostawcy, i = 1, 2, . . . , m,
bj  popyt j-tego odbiorcy, j = 1, 2, . . . , n,
ki  cena zakupu jednostki towaru u i-tego dostawcy,
i = 1, 2, . . . , m,
pj  cena sprzedaży jednostki towaru j-temu odbiorcy,
j = 1, 2, . . . , n,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
ai  podaż i-tego dostawcy, i = 1, 2, . . . , m,
bj  popyt j-tego odbiorcy, j = 1, 2, . . . , n,
ki  cena zakupu jednostki towaru u i-tego dostawcy,
i = 1, 2, . . . , m,
pj  cena sprzedaży jednostki towaru j-temu odbiorcy,
j = 1, 2, . . . , n,
cij  jednostkowy koszt transportu na trasie (i, j),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane sÄ…:
ai  podaż i-tego dostawcy, i = 1, 2, . . . , m,
bj  popyt j-tego odbiorcy, j = 1, 2, . . . , n,
ki  cena zakupu jednostki towaru u i-tego dostawcy,
i = 1, 2, . . . , m,
pj  cena sprzedaży jednostki towaru j-temu odbiorcy,
j = 1, 2, . . . , n,
cij  jednostkowy koszt transportu na trasie (i, j),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znalez
ć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
xij  ilość jednostek towaru przewożona na trasie (i, j),
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
xij  ilość jednostek towaru przewożona na trasie (i, j),
dij  dochód z przewiezienia jednostki towaru na trasie (i, j).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
xij  ilość jednostek towaru przewożona na trasie (i, j),
dij  dochód z przewiezienia jednostki towaru na trasie (i, j).
Dochód jednostkowy z trasy (i, j) obliczamy ze wzoru:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
xij  ilość jednostek towaru przewożona na trasie (i, j),
dij  dochód z przewiezienia jednostki towaru na trasie (i, j).
Dochód jednostkowy z trasy (i, j) obliczamy ze wzoru:
dij = pj - ki - cij,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
xij  ilość jednostek towaru przewożona na trasie (i, j),
dij  dochód z przewiezienia jednostki towaru na trasie (i, j).
Dochód jednostkowy z trasy (i, j) obliczamy ze wzoru:
dij = pj - ki - cij,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że dij < 0 dla pewnej trasy (i, j).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Ograniczenia:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Ograniczenia:
n

xij ai, i = 1, 2, . . . , m,
j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Ograniczenia:
n

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

xij bj, j = 1, 2, . . . , n.
i=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Ograniczenia:
n

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

xij bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Ograniczenia:
n

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

xij bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Funkcja celu:
m n

dijxij max
i=1 j=1
Ograniczenia:
n

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

xij bj, j = 1, 2, . . . , n.
i=1
Warunki brzegowe:
xij 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Zadanie pośrednika jest ZPL.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
n

am+1 = bj.
j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
n

am+1 = bj.
j=1
Wprowadzamy fikcyjnego odbiorcę, któremu przypisujemy
podaż
m

bn+1 = ai.
i=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
n

am+1 = bj.
j=1
Wprowadzamy fikcyjnego odbiorcę, któremu przypisujemy
podaż
m

bn+1 = ai.
i=1
Przyjmujemy jednostkowe dochody równe 0 dla tras (i, n + 1)
oraz (m + 1, j), i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
RozwiÄ…zanie poczÄ…tkowe wyznaczamy stosujÄ…c dowolnÄ…
metodÄ™,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
RozwiÄ…zanie poczÄ…tkowe wyznaczamy stosujÄ…c dowolnÄ…
metodę, metodę kąta północno-zachodniego
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
RozwiÄ…zanie poczÄ…tkowe wyznaczamy stosujÄ…c dowolnÄ…
metodę, metodę kąta północno-zachodniego lub metodę
maksymalnego elementu dla macierzy dochodów
jednostkowych.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
RozwiÄ…zanie poczÄ…tkowe wyznaczamy stosujÄ…c dowolnÄ…
metodę, metodę kąta północno-zachodniego lub metodę
maksymalnego elementu dla macierzy dochodów
jednostkowych.
Korzystając z metody potencjałów sprawdzamy, czy aktualnie
otrzymane rozwiÄ…zanie dopuszczalne jest optymalne.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
RozwiÄ…zanie poczÄ…tkowe wyznaczamy stosujÄ…c dowolnÄ…
metodę, metodę kąta północno-zachodniego lub metodę
maksymalnego elementu dla macierzy dochodów
jednostkowych.
Korzystając z metody potencjałów sprawdzamy, czy aktualnie
otrzymane rozwiÄ…zanie dopuszczalne jest optymalne. Jako
kryterium optymalności rozwiązania dopuszczalnego
przyjmujemy zachodzenie nierówności:
"ij 0
dla wszystkich niebazowych tras (i, j).
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Zagadnienie pośrednika (ZP)
Algorytm transportowy modyfikujemy następująco:
RozwiÄ…zanie poczÄ…tkowe wyznaczamy stosujÄ…c dowolnÄ…
metodę, metodę kąta północno-zachodniego lub metodę
maksymalnego elementu dla macierzy dochodów
jednostkowych.
Korzystając z metody potencjałów sprawdzamy, czy aktualnie
otrzymane rozwiÄ…zanie dopuszczalne jest optymalne. Jako
kryterium optymalności rozwiązania dopuszczalnego
przyjmujemy zachodzenie nierówności:
"ij 0
dla wszystkich niebazowych tras (i, j).
Nieoptymalne rozwiÄ…zanie dopuszczalne poprawiamy
wprowadzając do bazy w następnym rozwiązaniu tę trasę, dla
której dodatni wskaz
nik optymalności jest największy.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym, tzn. każde miasto
może być zarówno dostawcą, jak i odbiorcą towaru
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym, tzn. każde miasto
może być zarówno dostawcą, jak i odbiorcą towaru oraz cała masa
towarowa krąży tylko pomiędzy tymi miastami.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym, tzn. każde miasto
może być zarówno dostawcą, jak i odbiorcą towaru oraz cała masa
towarowa krąży tylko pomiędzy tymi miastami.
Dla każdej pary miast (i, j) znane są:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym, tzn. każde miasto
może być zarówno dostawcą, jak i odbiorcą towaru oraz cała masa
towarowa krąży tylko pomiędzy tymi miastami.
Dla każdej pary miast (i, j) znane są:
odległość dij pomiędzy tymi miastami,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym, tzn. każde miasto
może być zarówno dostawcą, jak i odbiorcą towaru oraz cała masa
towarowa krąży tylko pomiędzy tymi miastami.
Dla każdej pary miast (i, j) znane są:
odległość dij pomiędzy tymi miastami,
liczba pełnych środków transportu aij koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Pewne towary, nadające się do przewozu tym samym środkiem
transportu, przewożone są pomiędzy n miastami. Wymiana
towarów odbywa się w układzie zamkniętym, tzn. każde miasto
może być zarówno dostawcą, jak i odbiorcą towaru oraz cała masa
towarowa krąży tylko pomiędzy tymi miastami.
Dla każdej pary miast (i, j) znane są:
odległość dij pomiędzy tymi miastami,
liczba pełnych środków transportu aij koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j.
Liczba wi środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby pi środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zadanie MPP polega na znalezieniu optymalnego planu
zaopatrzenia w puste środki transportu tych miast, w których
wywóz towarów jest większy od przywozu.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zadanie MPP polega na znalezieniu optymalnego planu
zaopatrzenia w puste środki transportu tych miast, w których
wywóz towarów jest większy od przywozu. Brakujące środki
transportu powinny zostać przesłane z miast, w których przywóz
towarów jest większy od wywozu.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zadanie MPP polega na znalezieniu optymalnego planu
zaopatrzenia w puste środki transportu tych miast, w których
wywóz towarów jest większy od przywozu. Brakujące środki
transportu powinny zostać przesłane z miast, w których przywóz
towarów jest większy od wywozu. Plan przebiegu pustych środków
transportu uznajemy za optymalny, jeżeli jego realizacja zapewnia
zaopatrzenie wszystkich miast w niezbędną liczbę pustych środków
transportu,
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zadanie MPP polega na znalezieniu optymalnego planu
zaopatrzenia w puste środki transportu tych miast, w których
wywóz towarów jest większy od przywozu. Brakujące środki
transportu powinny zostać przesłane z miast, w których przywóz
towarów jest większy od wywozu. Plan przebiegu pustych środków
transportu uznajemy za optymalny, jeżeli jego realizacja zapewnia
zaopatrzenie wszystkich miast w niezbędną liczbę pustych środków
transportu, a łączny kilometraż pustych przebiegów jest
najmniejszy z możliwych.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zadanie MPP polega na znalezieniu optymalnego planu
zaopatrzenia w puste środki transportu tych miast, w których
wywóz towarów jest większy od przywozu. Brakujące środki
transportu powinny zostać przesłane z miast, w których przywóz
towarów jest większy od wywozu. Plan przebiegu pustych środków
transportu uznajemy za optymalny, jeżeli jego realizacja zapewnia
zaopatrzenie wszystkich miast w niezbędną liczbę pustych środków
transportu, a łączny kilometraż pustych przebiegów jest
najmniejszy z możliwych.
Zadanie MPP można przekształcić do postaci ZT poprzez
potraktowanie pustych środków transportu jako przewożonego
towaru i podzieleniu zbioru wszystkich miast na podzbióry:
dostawców i odbiorców tych środków transportu.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zadanie MPP polega na znalezieniu optymalnego planu
zaopatrzenia w puste środki transportu tych miast, w których
wywóz towarów jest większy od przywozu. Brakujące środki
transportu powinny zostać przesłane z miast, w których przywóz
towarów jest większy od wywozu. Plan przebiegu pustych środków
transportu uznajemy za optymalny, jeżeli jego realizacja zapewnia
zaopatrzenie wszystkich miast w niezbędną liczbę pustych środków
transportu, a łączny kilometraż pustych przebiegów jest
najmniejszy z możliwych.
Zadanie MPP można przekształcić do postaci ZT poprzez
potraktowanie pustych środków transportu jako przewożonego
towaru i podzieleniu zbioru wszystkich miast na podzbióry:
dostawców i odbiorców tych środków transportu.
Z warunków zadania MPP wynika, że tak otrzymane ZD jest
zadaniem zbilansowanym.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n

wi = aij
j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n n

wi = aij oraz pj = aij.
j=1 i=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n n

wi = aij oraz pj = aij.
j=1 i=1
Oczywiście
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n n

wi = aij oraz pj = aij.
j=1 i=1
Oczywiście
n n

wi = pj.
i=1 j=1
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n n

wi = aij oraz pj = aij.
j=1 i=1
Oczywiście
n n

wi = pj.
i=1 j=1
Miasta, dla których wi < pi, są dostawcami pustych środków
transportu z podażą ai = pi - wi.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n n

wi = aij oraz pj = aij.
j=1 i=1
Oczywiście
n n

wi = pj.
i=1 j=1
Miasta, dla których wi < pi, są dostawcami pustych środków
transportu z podażą ai = pi - wi.
Miasta, dla których wj > pj, są odbiorcami pustych środków
transportu z popytem bj = wj - pj.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb wi oraz pj zachodzą
równości:
n n

wi = aij oraz pj = aij.
j=1 i=1
Oczywiście
n n

wi = pj.
i=1 j=1
Miasta, dla których wi < pi, są dostawcami pustych środków
transportu z podażą ai = pi - wi.
Miasta, dla których wj > pj, są odbiorcami pustych środków
transportu z popytem bj = wj - pj.
Miasta, dla których wj = pj, pomijamy w dalszych
rozważaniach.
Jacek Rogowski BOwL Wykład 2: Zadanie sprowadzalne do ZT