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
Wyszukiwarka
Podobne podstrony:
BOwL wyklad 03 Beamer 2014
BOwL wyklad 01 Beamer 2014
Młoda Polska WYKŁAD (02 04 2014)
BOwL wyklad 04 Beamer 2015
Młoda Polska WYKŁAD (02 04 2014)
pdf wykład 02 budowa materii, podstawowe prawa chemiczne 2014
2014 10 12 ZUSO Wykład 02
Wyklad 02 2014 2015
Wykład 1$ 02 2014
Etyka w zarządzaniu wykład 3 02 2014
Postępowanie adm. - wykład 02, UKSW prawo stacjonarne, Postępowanie administracyjne i sądowo-adminis
Wykład 1 02 2014
Postępowanie?m wykład 02 2014
wykład( 02 2014
Wykład I & 02 2014
Logika Wykład 1 02 2014
pdf wykład 02 budowa materii, podstawowe prawa chemiczne 2014
2013 2014 wyklad 02 Psychologia Ekonomiczna EMagier Lakomy st
więcej podobnych podstron