Badania Operacyjne w Logistyce
Wykład 2
Zadania sprowadzalne do zadania transportowego
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Badania Operacyjne w Logistyce
Wykład 2
Zadania sprowadzalne do zadania transportowego
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
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 c
pq
zastępując jego dotychczasową wartość przez
liczbę większą od wszystkich wyrazów c
ij
, gdzie (i , j ) 6= (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ść c
pq
.
Jeżeli zablokowanych tras jest więcej niż jedna, należy powyższą
procedurę zastosować do każdej z nich.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana,
tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru.
Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q)
i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio.
Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d
i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Uogólnijmy poprzednią sytuację:
Załóżmy, że jedna z tras jest częściowo zablokowana, tzn. można
przewieźć nią co najwyżej d jednostek towaru. Przyjmijmy, że
częściowo zablokowaną trasą jest trasa (p, q) i załóżmy, że
d ¬ min(a
p
, b
q
).
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
0
oraz p
00
.
Dostawcę D
p
(którego podaż wynosi a
p
) zastępujemy dwoma
fikcyjnymi dostawcami: D
0
p
oraz D
00
p
umieszczonymi w wierszach p
0
oraz p
00
odpowiednio. Dostawcy D
0
p
przypisujemy podaż d i
przyjmujemy jednostkowe koszty transportu
c
p
0
j
= c
pj
na trasach od tego dostawcy.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d
i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych
zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Dostawcy D
00
p
przypisujemy podaż a
p
− d i przyjmujemy na trasach
od tego dostawcy jednostkowe koszty transportu
c
p
00
j
=
(
c
pj
dla
j 6= q,
M
dla
j = q,
gdzie M oznacza dostatecznie dużą liczbę.
Ostatecznie, wiersz
D
p
c
p1
. . .
c
pq
. . .
c
pn
a
p
z macierzy kosztów jednostkowych zastępujemy wierszami:
D
0
p
c
p1
. . .
c
pq
. . .
c
pn
d
D
00
p
c
p1
. . .
M
. . .
c
pn
a
p
− d
.
Jacek Rogowski
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy D
p
można analogiczną procedurę
przeprowadzić dla odbiorcy O
q
.
W przypadku, gdy min(a
p
, b
q
) ¬ d < max(a
p
, b
q
) dokonujemy
„rozdwojenia”
dostawcy, jeżeli d < a
p
,
odbiorcy, jeżeli d < b
q
.
Jeżeli d max(a
p
, b
q
), 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
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy D
p
można analogiczną procedurę
przeprowadzić dla odbiorcy O
q
.
W przypadku, gdy min(a
p
, b
q
) ¬ d < max(a
p
, b
q
) dokonujemy
„rozdwojenia”
dostawcy, jeżeli d < a
p
,
odbiorcy, jeżeli d < b
q
.
Jeżeli d max(a
p
, b
q
), 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
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy D
p
można analogiczną procedurę
przeprowadzić dla odbiorcy O
q
.
W przypadku, gdy min(a
p
, b
q
) ¬ d < max(a
p
, b
q
) dokonujemy
„rozdwojenia”
dostawcy, jeżeli d < a
p
,
odbiorcy, jeżeli d < b
q
.
Jeżeli d max(a
p
, b
q
), 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
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy D
p
można analogiczną procedurę
przeprowadzić dla odbiorcy O
q
.
W przypadku, gdy min(a
p
, b
q
) ¬ d < max(a
p
, b
q
) dokonujemy
„rozdwojenia”
dostawcy, jeżeli d < a
p
,
odbiorcy, jeżeli d < b
q
.
Jeżeli d max(a
p
, b
q
), 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
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy D
p
można analogiczną procedurę
przeprowadzić dla odbiorcy O
q
.
W przypadku, gdy min(a
p
, b
q
) ¬ d < max(a
p
, b
q
) dokonujemy
„rozdwojenia”
dostawcy, jeżeli d < a
p
,
odbiorcy, jeżeli d < b
q
.
Jeżeli d max(a
p
, b
q
), 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
ZT z częściowo zablokowaną trasą
Zamiast dla dostawcy D
p
można analogiczną procedurę
przeprowadzić dla odbiorcy O
q
.
W przypadku, gdy min(a
p
, b
q
) ¬ d < max(a
p
, b
q
) dokonujemy
„rozdwojenia”
dostawcy, jeżeli d < a
p
,
odbiorcy, jeżeli d < b
q
.
Jeżeli d max(a
p
, b
q
), 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
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n).
Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru. Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie, zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n). Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru.
Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie, zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n). Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru. Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie,
zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n). Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru. Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie, zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n). Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru. Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie, zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n). Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru. Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie, zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Zadanie transportowo-produkcyjne (ZT-P)
Pewien jednorodny towar jest produkowany przez m producentów
P
i
, (i = 1, 2, . . . , m), którzy zaopatrują w swoją produkcję n
odbiorców: O
j
, (j = 1, 2, . . . , n). Producent P
i
ma zdolność
produkcyjną a
i
jednostek towaru, zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru. Dla każdej trasy (i , j ) od
producenta P
i
do odbiorcy O
j
znany jest koszt c
ij
transportu
jednostki towaru na tej trasie, zaś dla każdego producenta P
i
znany jest koszt k
i
wytworzenia przez niego jednostki towaru.
Należy ustalić gdzie i w jakiej ilości podjąć produkcję towaru oraz
jak go przewieźć 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
X
i =1
a
i
>
n
X
j =1
b
j
.
(1)
Jacek Rogowski
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ę O
n+1
, któremu
przypisujemy popyt
b
n+1
=
m
X
i =1
a
i
−
n
X
j =1
b
j
.
Konstruujemy macierz [k
ij
] ∈ M
m×(n+1)
łącznych kosztów
produkcji i transportu
przyjmując
k
ij
=
(
h
i
+ c
ij
dla
i = 1, . . . , m, j = 1, . . . , n,
0
dla
i = 1, . . . , m, j = n + 1.
Jacek Rogowski
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ę O
n+1
, któremu
przypisujemy popyt
b
n+1
=
m
X
i =1
a
i
−
n
X
j =1
b
j
.
Konstruujemy macierz [k
ij
] ∈ M
m×(n+1)
łącznych kosztów
produkcji i transportu
przyjmując
k
ij
=
(
h
i
+ c
ij
dla
i = 1, . . . , m, j = 1, . . . , n,
0
dla
i = 1, . . . , m, j = n + 1.
Jacek Rogowski
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ę O
n+1
, któremu
przypisujemy popyt
b
n+1
=
m
X
i =1
a
i
−
n
X
j =1
b
j
.
Konstruujemy macierz [k
ij
] ∈ M
m×(n+1)
łącznych kosztów
produkcji i transportu
przyjmując
k
ij
=
(
h
i
+ c
ij
dla
i = 1, . . . , m, j = 1, . . . , n,
0
dla
i = 1, . . . , m, j = n + 1.
Jacek Rogowski
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ę O
n+1
, któremu
przypisujemy popyt
b
n+1
=
m
X
i =1
a
i
−
n
X
j =1
b
j
.
Konstruujemy macierz [k
ij
] ∈ M
m×(n+1)
łącznych kosztów
produkcji i transportu
przyjmując
k
ij
=
(
h
i
+ c
ij
dla
i = 1, . . . , m, j = 1, . . . , n,
0
dla
i = 1, . . . , m, j = n + 1.
Jacek Rogowski
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ę O
n+1
, któremu
przypisujemy popyt
b
n+1
=
m
X
i =1
a
i
−
n
X
j =1
b
j
.
Konstruujemy macierz [k
ij
] ∈ M
m×(n+1)
łącznych kosztów
produkcji i transportu przyjmując
k
ij
=
(
h
i
+ c
ij
dla
i = 1, . . . , m, j = 1, . . . , n,
0
dla
i = 1, . . . , m, j = n + 1.
Jacek Rogowski
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 b
j
,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m) oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
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 b
j
,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m) oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
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 b
j
,
(j = 1, 2, . . . , n),
a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m) oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
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 b
j
,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m) oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
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 b
j
,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m)
oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
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 b
j
,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m) oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
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 b
j
,
(j = 1, 2, . . . , n), a potencjalne zdolności produkcyjne w i -tej
lokalizacji są równe a
i
, (i = 1, 2, . . . , m).
Ponadto, dla każdej lokalizacji produkcji oszacowane zostały
jednostkowe koszty produkcji h
i
, (i = 1, 2, . . . , m) oraz znane są
przewidywane jednostkowe koszty transportu c
ij
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zadanie lokalizacji produkcji (ZLP)
Przyjmuje się następujące założenia:
m
X
i =1
a
i
>
n
X
j =1
b
j
.
Zachodzenie nierówności przeciwnej pociąga za sobą
konieczność wybudowania wszystkich zakładów.
a
i
<
n
X
j =1
b
j
dla pewnego i ∈ {1, 2, . . . , m}.
Gdyby dla każdego i zachodziła nierówność a
i
n
X
j =1
b
j
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
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom.
Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje
n odbiorcom. Znane są:
a
i
— podaż i -tego dostawcy, i = 1, 2, . . . , m,
b
j
— popyt j -tego odbiorcy, j = 1, 2, . . . , n,
k
i
— cena zakupu jednostki towaru u i -tego dostawcy,
i = 1, 2, . . . , m,
p
j
— cena sprzedaży jednostki towaru j -temu odbiorcy,
j = 1, 2, . . . , n,
c
ij
— jednostkowy koszt transportu na trasie (i , j ),
i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Należy znaleźć plan zakupu, transportu i sprzedaży towaru
przynoszący pośrednikowi maksymalny zysk.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Model matematyczny
Oznaczenia:
x
ij
— ilość jednostek towaru przewożona na trasie (i , j ),
d
ij
— dochód z przewiezienia jednostki towaru na trasie (i , j ).
Dochód jednostkowy z trasy (i , j ) obliczamy ze wzoru:
d
ij
= p
j
− k
i
− c
ij
,
gdzie i = 1, 2, . . . , m, j = 1, 2, . . . , n.
Może się zdarzyć, że d
ij
< 0 dla pewnej trasy (i , j ).
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Funkcja celu:
m
X
i =1
n
X
j =1
d
ij
x
ij
→ max
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.
Zadanie pośrednika jest ZPL.
Jacek Rogowski
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
a
m+1
=
n
X
j =1
b
j
.
Wprowadzamy fikcyjnego odbiorcę, któremu przypisujemy
podaż
b
n+1
=
m
X
i =1
a
i
.
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
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
a
m+1
=
n
X
j =1
b
j
.
Wprowadzamy fikcyjnego odbiorcę, któremu przypisujemy
podaż
b
n+1
=
m
X
i =1
a
i
.
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
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
a
m+1
=
n
X
j =1
b
j
.
Wprowadzamy fikcyjnego odbiorcę, któremu przypisujemy
podaż
b
n+1
=
m
X
i =1
a
i
.
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
Zagadnienie pośrednika (ZP)
Schemat sprowadzania ZP do zbilansowanego ZT
Wprowadzamy fikcyjnego dostawcę, któremu przypisujemy
podaż
a
m+1
=
n
X
j =1
b
j
.
Wprowadzamy fikcyjnego odbiorcę, któremu przypisujemy
podaż
b
n+1
=
m
X
i =1
a
i
.
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
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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 wskaźnik optymalności jest największy.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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ść d
ij
pomiędzy tymi miastami,
liczba pełnych środków transportu a
ij
koniecznych do
przewiezienia całej masy towarowej z miasta i do miasta j .
Liczba w
i
środków transportu potrzebnych do wywiezienia masy
towarowej z miasta i jest, na ogół, różna od liczby p
i
środków
transportu koniecznych do przywiezienia towaru do tego miasta.
Jacek Rogowski
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
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
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
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
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
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
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski
Minimalizacja pustych przebiegów (MPP)
Zauważmy, że zgodnie z definicją liczb w
i
oraz p
j
zachodzą
równości:
w
i
=
n
X
j =1
a
ij
oraz
p
j
=
n
X
i =1
a
ij
.
Oczywiście
n
X
i =1
w
i
=
n
X
j =1
p
j
.
Miasta, dla których w
i
< p
i
, są dostawcami pustych środków
transportu z podażą a
i
= p
i
− w
i
.
Miasta, dla których w
j
> p
j
, są odbiorcami pustych środków
transportu z popytem b
j
= w
j
− p
j
.
Miasta, dla których w
j
= p
j
, pomijamy w dalszych
rozważaniach.
Jacek Rogowski