Wykład 1
Zadanie transportowe
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Wykład 1
Zadanie transportowe
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).
Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D
1
, D
2
, ..., D
m
,
do n odbiorców: O
1
, O
2
, ..., O
n
, przy czym dostawca D
i
dysponuje
a
i
jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca O
j
zgłasza
zapotrzebowanie na b
j
jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i , j ) od dostawcy D
i
do odbiorcy O
j
znany jest
koszt c
ij
transportu jednostki towaru na tej trasie.
Dostawcy chcą wysłać całe swoje zapasy towaru, a dostawcy chcą,
aby ich popyt został w pełni zaspokojony.
Należy znaleźć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiązania:
m
X
i =1
a
i
=
n
X
j =1
b
j
.
(1)
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym.
Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
(lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym. Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
(lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym. Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
(lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym. Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
(lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym. Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
(lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym. Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
(lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym. Jeżeli
zadanie transportowe nie jest zbilansowane, należy je zbilansować
przez dodanie do rozważań:
fikcyjnego odbiorcy, jeżeli łączna podaż jest większa od
sumarycznego popytu,
fikcyjnego dostawcy, jeżeli łączna podaż jest mniejsza od
sumarycznego popytu,
przypisanie wprowadzonemu fikcyjnemu odbiorcy (dostawcy)
popytu (podaży) w wysokości
m
X
i =1
a
i
−
n
X
j =1
b
j
,
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0 (lub innych, wynikających z warunków
zadania).
Jacek Rogowski
Klasyczne zadanie transportowe
Najczęściej dane ZT podaje się w postaci tabeli:
O
1
O
2
. . .
O
n
Podaż
D
1
c
11
c
12
. . .
c
1n
a
1
D
2
c
21
c
22
. . .
c
2n
a
2
..
.
..
.
..
.
..
.
..
.
D
m
c
m1
c
m2
. . .
c
mn
a
m
Popyt
b
1
b
2
. . .
b
n
Tabelę tę nazywa się macierzą (tablicą) kosztów
jednostkowych.
Jacek Rogowski
Klasyczne zadanie transportowe
Najczęściej dane ZT podaje się w postaci tabeli:
O
1
O
2
. . .
O
n
Podaż
D
1
c
11
c
12
. . .
c
1n
a
1
D
2
c
21
c
22
. . .
c
2n
a
2
..
.
..
.
..
.
..
.
..
.
D
m
c
m1
c
m2
. . .
c
mn
a
m
Popyt
b
1
b
2
. . .
b
n
Tabelę tę nazywa się macierzą (tablicą) kosztów
jednostkowych.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby a
i
, b
j
oraz c
ij
są
nieujemne.
Zbilansowane ZT ma zawsze rozwiązanie.
Jeżeli w zbilansowanym ZT wszystkie liczby a
i
, b
j
oraz c
ij
są
wymierne, to rozwiązanie ZT można znaleźć w skończonej
liczbie kroków za pomocą tzw. algorytmu transportowego,
który zostanie omówiony w dalszym ciągu.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby a
i
, b
j
oraz c
ij
są
nieujemne.
Zbilansowane ZT ma zawsze rozwiązanie.
Jeżeli w zbilansowanym ZT wszystkie liczby a
i
, b
j
oraz c
ij
są
wymierne, to rozwiązanie ZT można znaleźć w skończonej
liczbie kroków za pomocą tzw. algorytmu transportowego,
który zostanie omówiony w dalszym ciągu.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby a
i
, b
j
oraz c
ij
są
nieujemne.
Zbilansowane ZT ma zawsze rozwiązanie.
Jeżeli w zbilansowanym ZT wszystkie liczby a
i
, b
j
oraz c
ij
są
wymierne, to rozwiązanie ZT można znaleźć w skończonej
liczbie kroków za pomocą tzw. algorytmu transportowego,
który zostanie omówiony w dalszym ciągu.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby a
i
, b
j
oraz c
ij
są
nieujemne.
Zbilansowane ZT ma zawsze rozwiązanie.
Jeżeli w zbilansowanym ZT wszystkie liczby a
i
, b
j
oraz c
ij
są
wymierne, to rozwiązanie ZT można znaleźć w skończonej
liczbie kroków za pomocą tzw. algorytmu transportowego,
który zostanie omówiony w dalszym ciągu.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Niekiedy jednostkowe koszty transportu przypisane fikcyjnym
trasom mogą być różne od 0;
dzieje się tak np. wtedy, gdy
należy uwzględnić pewne dodatkowe koszty jednostkowe
(magazynowania, produkcji itp.).
Początkowe wartości jednostkowych kosztów transportu na
„rzeczywistych” trasach mogą ulec zmianie w wyniku
uwzględnienia pewnych dodatkowych warunków.
Takim
warunkiem jest np. częściowa lub całkowita blokada trasy.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Niekiedy jednostkowe koszty transportu przypisane fikcyjnym
trasom mogą być różne od 0;
dzieje się tak np. wtedy, gdy
należy uwzględnić pewne dodatkowe koszty jednostkowe
(magazynowania, produkcji itp.).
Początkowe wartości jednostkowych kosztów transportu na
„rzeczywistych” trasach mogą ulec zmianie w wyniku
uwzględnienia pewnych dodatkowych warunków.
Takim
warunkiem jest np. częściowa lub całkowita blokada trasy.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Niekiedy jednostkowe koszty transportu przypisane fikcyjnym
trasom mogą być różne od 0;
dzieje się tak np. wtedy, gdy
należy uwzględnić pewne dodatkowe koszty jednostkowe
(magazynowania, produkcji itp.).
Początkowe wartości jednostkowych kosztów transportu na
„rzeczywistych” trasach mogą ulec zmianie w wyniku
uwzględnienia pewnych dodatkowych warunków.
Takim
warunkiem jest np. częściowa lub całkowita blokada trasy.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Niekiedy jednostkowe koszty transportu przypisane fikcyjnym
trasom mogą być różne od 0; dzieje się tak np. wtedy, gdy
należy uwzględnić pewne dodatkowe koszty jednostkowe
(magazynowania, produkcji itp.).
Początkowe wartości jednostkowych kosztów transportu na
„rzeczywistych” trasach mogą ulec zmianie w wyniku
uwzględnienia pewnych dodatkowych warunków.
Takim
warunkiem jest np. częściowa lub całkowita blokada trasy.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Niekiedy jednostkowe koszty transportu przypisane fikcyjnym
trasom mogą być różne od 0; dzieje się tak np. wtedy, gdy
należy uwzględnić pewne dodatkowe koszty jednostkowe
(magazynowania, produkcji itp.).
Początkowe wartości jednostkowych kosztów transportu na
„rzeczywistych” trasach mogą ulec zmianie w wyniku
uwzględnienia pewnych dodatkowych warunków.
Takim
warunkiem jest np. częściowa lub całkowita blokada trasy.
Jacek Rogowski
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Niekiedy jednostkowe koszty transportu przypisane fikcyjnym
trasom mogą być różne od 0; dzieje się tak np. wtedy, gdy
należy uwzględnić pewne dodatkowe koszty jednostkowe
(magazynowania, produkcji itp.).
Początkowe wartości jednostkowych kosztów transportu na
„rzeczywistych” trasach mogą ulec zmianie w wyniku
uwzględnienia pewnych dodatkowych warunków. Takim
warunkiem jest np. częściowa lub całkowita blokada trasy.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia.
Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
.
Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez x
ij
wielkość transportu odbywającego się na trasie
(i , j ) od dostawcy D
i
do odbiorcy O
j
. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m
X
i =1
n
X
j =1
c
ij
x
ij
→ min,
n
X
j =1
x
ij
= a
i
,
dla i = 1, . . . , m,
m
X
i =1
x
ij
= b
j
,
dla j = 1, . . . , n,
x
ij
0,
dla i = 1, . . . , m,
j = 1, . . . , n.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych
— jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych
— jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających.
Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych
tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1.
Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej.
Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi.
Łatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych — jedno z nich można usunąć bez szkody
dla warunków ograniczających. Po takim zabiegu pozostaje w
układzie m + n − 1 równań tworzących układ niezależnych
równań liniowych tzn. taki układ równań, że macierz jego
współczynników jest rzędu m + n − 1. Taki układ ograniczeń
bedziemy nazywać zredukowanym.
Chcąc rozwiązać to ZPL za pomocą algorytmu sympleks
należy wprowadzić do każdego ograniczenia w zredukowanym
układzie ograniczeń jedną zmienną sztuczną w celu
zapewnienia pojawienia się w każdym ograniczeniu zmiennej
bazowej. Wynika stąd, że postać kanoniczna rozważanego
ZPL zawiera m + n − 1 zmiennych bazowych.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n − 1 kolumn
macierzy jednostkowej I
m+n−1
.
ZPL (generowane przez ZT) zawiera mn + m + n − 1
zmiennych, co powoduje, że algorytm sympleks jest
praktycznie nieużyteczny przy „ręcznym” rozwiązywaniu ZT.
Na przykład, dla zadania z czterema dostawcami i pięcioma
odbiorcami liczba zmiennych wynosi:
4 · 5 + 4 + 5 − 1 = 28,
a usunięcie z bazy niezerowych wartości zmiennych sztucznych
wymaga zbudowania co najmniej ośmiu kolejnych tablic
sympleksowych.
ZT należy więc rozwiązywać korzystając z algorytmu
dostosowanego do postaci tego zadania.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT,
zwany dalej algorytmem
transportowym, (w skrócie: AT) składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania,
a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT)
składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania,
a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT) składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania,
a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT) składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania,
a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT) składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania,
a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT) składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania, a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Algorytm rozwiązywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT) składa się z dwóch niezależnych
kroków:
1
Krok początkowy: Znajdujemy pierwsze rozwiązanie
dopuszczalne ZT i sprawdzamy, czy jest to rozwiązanie
optymalne.
2
Krok iteracyjny: Dopóki ostatnie znalezione rozwiązanie
dopuszczalne nie jest optymalne, poprawiamy je i
otrzymujemy nowe rozwiązanie dopuszczalne o koszcie
niższym od kosztu poprzedniego rozwiązania, a następnie
sprawdzamy, czy nowe rozwiązanie jest optymalne.
W dalszym ciagu zostaną opisane procedury znajdowania
pierwszego rozwiązania dopuszczalnego, poprawiania rozwiązania i
sprawdzania optymalności rozwiązań.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych,
a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich;
przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0,
a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych,
ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
X =
x
11
x
12
. . .
x
1n
x
21
x
22
. . .
x
2n
..
.
..
.
..
.
x
m1
x
m2
. . .
x
mn
.
Rozwiązanie to zawiera m + n − 1 tras bazowych, a więc co
najwyżej m + n − 1 liczb x
ij
jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0, a więc
zbiór tras z dodatnimi przewozami zawiera się w zbiorze tras
bazowych, ale nie musi się z nim pokrywać.
Jacek Rogowski
Algorytm transportowy (AT)
Trzy użyteczne pojęcia.
Definicja
Linią nazywamy każdy wiersz lub każdą kolumnę w macierzy X .
Definicja
Cyklem nazywamy każdy zbiór Γ złożony z parzystej liczby pól
macierzy X mający tę własność, że każda linia tej macierzy jest
rozłączna ze zbiorem Γ albo ma z nim dokładnie dwa pola wspólne.
Definicja
Układem tras bazowych nazywamy każdy zbiór złożony z
m + n − 1 pól macierzy X , który nie zawiera żadnego cyklu.
Jacek Rogowski
Algorytm transportowy (AT)
Trzy użyteczne pojęcia.
Definicja
Linią nazywamy każdy wiersz lub każdą kolumnę w macierzy X .
Definicja
Cyklem nazywamy każdy zbiór Γ złożony z parzystej liczby pól
macierzy X mający tę własność, że każda linia tej macierzy jest
rozłączna ze zbiorem Γ albo ma z nim dokładnie dwa pola wspólne.
Definicja
Układem tras bazowych nazywamy każdy zbiór złożony z
m + n − 1 pól macierzy X , który nie zawiera żadnego cyklu.
Jacek Rogowski
Algorytm transportowy (AT)
Trzy użyteczne pojęcia.
Definicja
Linią nazywamy każdy wiersz lub każdą kolumnę w macierzy X .
Definicja
Cyklem nazywamy każdy zbiór Γ złożony z parzystej liczby pól
macierzy X mający tę własność, że każda linia tej macierzy jest
rozłączna ze zbiorem Γ albo ma z nim dokładnie dwa pola wspólne.
Definicja
Układem tras bazowych nazywamy każdy zbiór złożony z
m + n − 1 pól macierzy X , który nie zawiera żadnego cyklu.
Jacek Rogowski
Algorytm transportowy (AT)
Trzy użyteczne pojęcia.
Definicja
Linią nazywamy każdy wiersz lub każdą kolumnę w macierzy X .
Definicja
Cyklem nazywamy każdy zbiór Γ złożony z parzystej liczby pól
macierzy X mający tę własność, że każda linia tej macierzy jest
rozłączna ze zbiorem Γ albo ma z nim dokładnie dwa pola wspólne.
Definicja
Układem tras bazowych nazywamy każdy zbiór złożony z
m + n − 1 pól macierzy X , który nie zawiera żadnego cyklu.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą kąta północno-zachodniego.
1
Pustą macierz X (lub niezablokowaną jej część) traktujemy
jak mapę.
2
W każdym kroku wybieramy pole (i , j ) na tej mapie
wysunięte najdalej na północny-zachód.
3
W pole (i , j ) wpisujemy liczbę min(a
i
, b
j
) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
4
Od popytu/podaży drugiej linii zawierającej pole (i , j )
odejmujemy liczbę min(a
i
, b
j
).
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą kąta północno-zachodniego.
1
Pustą macierz X (lub niezablokowaną jej część) traktujemy
jak mapę.
2
W każdym kroku wybieramy pole (i , j ) na tej mapie
wysunięte najdalej na północny-zachód.
3
W pole (i , j ) wpisujemy liczbę min(a
i
, b
j
) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
4
Od popytu/podaży drugiej linii zawierającej pole (i , j )
odejmujemy liczbę min(a
i
, b
j
).
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą kąta północno-zachodniego.
1
Pustą macierz X (lub niezablokowaną jej część) traktujemy
jak mapę.
2
W każdym kroku wybieramy pole (i , j ) na tej mapie
wysunięte najdalej na północny-zachód.
3
W pole (i , j ) wpisujemy liczbę min(a
i
, b
j
) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
4
Od popytu/podaży drugiej linii zawierającej pole (i , j )
odejmujemy liczbę min(a
i
, b
j
).
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą kąta północno-zachodniego.
1
Pustą macierz X (lub niezablokowaną jej część) traktujemy
jak mapę.
2
W każdym kroku wybieramy pole (i , j ) na tej mapie
wysunięte najdalej na północny-zachód.
3
W pole (i , j ) wpisujemy liczbę min(a
i
, b
j
) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
4
Od popytu/podaży drugiej linii zawierającej pole (i , j )
odejmujemy liczbę min(a
i
, b
j
).
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą kąta północno-zachodniego.
1
Pustą macierz X (lub niezablokowaną jej część) traktujemy
jak mapę.
2
W każdym kroku wybieramy pole (i , j ) na tej mapie
wysunięte najdalej na północny-zachód.
3
W pole (i , j ) wpisujemy liczbę min(a
i
, b
j
) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
4
Od popytu/podaży drugiej linii zawierającej pole (i , j )
odejmujemy liczbę min(a
i
, b
j
).
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą kąta północno-zachodniego.
1
Pustą macierz X (lub niezablokowaną jej część) traktujemy
jak mapę.
2
W każdym kroku wybieramy pole (i , j ) na tej mapie
wysunięte najdalej na północny-zachód.
3
W pole (i , j ) wpisujemy liczbę min(a
i
, b
j
) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
4
Od popytu/podaży drugiej linii zawierającej pole (i , j )
odejmujemy liczbę min(a
i
, b
j
).
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
1
W macierzy jednostkowych kosztów transportu (lub jej
niezablokowanej części) znajdujemy najmniejszy element c
ij
.
2
W pole (i , j ) macierzy X wpisujemy liczbę min(a
i
, b
j
) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
3
Od popytu/podaży drugiej linii macierzy X zawierającej pole
(i , j ) odejmujemy liczbę min(a
i
, b
j
).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola w macierzy X .
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
1
W macierzy jednostkowych kosztów transportu (lub jej
niezablokowanej części) znajdujemy najmniejszy element c
ij
.
2
W pole (i , j ) macierzy X wpisujemy liczbę min(a
i
, b
j
) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
3
Od popytu/podaży drugiej linii macierzy X zawierającej pole
(i , j ) odejmujemy liczbę min(a
i
, b
j
).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola w macierzy X .
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
1
W macierzy jednostkowych kosztów transportu (lub jej
niezablokowanej części) znajdujemy najmniejszy element c
ij
.
2
W pole (i , j ) macierzy X wpisujemy liczbę min(a
i
, b
j
) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
3
Od popytu/podaży drugiej linii macierzy X zawierającej pole
(i , j ) odejmujemy liczbę min(a
i
, b
j
).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola w macierzy X .
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
1
W macierzy jednostkowych kosztów transportu (lub jej
niezablokowanej części) znajdujemy najmniejszy element c
ij
.
2
W pole (i , j ) macierzy X wpisujemy liczbę min(a
i
, b
j
) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
3
Od popytu/podaży drugiej linii macierzy X zawierającej pole
(i , j ) odejmujemy liczbę min(a
i
, b
j
).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola w macierzy X .
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
1
W macierzy jednostkowych kosztów transportu (lub jej
niezablokowanej części) znajdujemy najmniejszy element c
ij
.
2
W pole (i , j ) macierzy X wpisujemy liczbę min(a
i
, b
j
) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
3
Od popytu/podaży drugiej linii macierzy X zawierającej pole
(i , j ) odejmujemy liczbę min(a
i
, b
j
).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola w macierzy X .
Jacek Rogowski
Algorytm transportowy (AT)
Wyznaczanie początkowego rozwiązania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
1
W macierzy jednostkowych kosztów transportu (lub jej
niezablokowanej części) znajdujemy najmniejszy element c
ij
.
2
W pole (i , j ) macierzy X wpisujemy liczbę min(a
i
, b
j
) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
3
Od popytu/podaży drugiej linii macierzy X zawierającej pole
(i , j ) odejmujemy liczbę min(a
i
, b
j
).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
5
Czynności (2) – (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola w macierzy X .
Jacek Rogowski
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u
1
, u
2
, . . ., u
m
, v
1
, v
2
, . . ., v
n
przyjmując u
1
= 0 i rozwiązując układ równań
u
i
+ v
j
= c
ij
,
gdzie pary (i , j ) przebiegają przez zbiór wszystkich tras
bazowych rozwiązania dopuszczalnego X .
2
Dla każdej trasy niebazowej (r , s) wyznaczamy wskażnik
optymalności ∆
rs
= c
rs
− (u
r
+ v
s
).
3
Liczba ∆
rs
jest równa wartości o jaką zmieni się całkowity
koszt przewozu towarów, jeżeli trasą (r , s) zostanie
przewieziona jednostka towaru (przy jednoczesnej
odpowiedniej modyfikacji transportu na innych trasach).
4
Rozwiązanie X jest optymalne, jeśli wszystkie wskaźniki
optymalności ∆
rs
dla tras niebazowych są nieujemne.
Jacek Rogowski
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u
1
, u
2
, . . ., u
m
, v
1
, v
2
, . . ., v
n
przyjmując u
1
= 0 i rozwiązując układ równań
u
i
+ v
j
= c
ij
,
gdzie pary (i , j ) przebiegają przez zbiór wszystkich tras
bazowych rozwiązania dopuszczalnego X .
2
Dla każdej trasy niebazowej (r , s) wyznaczamy wskażnik
optymalności ∆
rs
= c
rs
− (u
r
+ v
s
).
3
Liczba ∆
rs
jest równa wartości o jaką zmieni się całkowity
koszt przewozu towarów, jeżeli trasą (r , s) zostanie
przewieziona jednostka towaru (przy jednoczesnej
odpowiedniej modyfikacji transportu na innych trasach).
4
Rozwiązanie X jest optymalne, jeśli wszystkie wskaźniki
optymalności ∆
rs
dla tras niebazowych są nieujemne.
Jacek Rogowski
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u
1
, u
2
, . . ., u
m
, v
1
, v
2
, . . ., v
n
przyjmując u
1
= 0 i rozwiązując układ równań
u
i
+ v
j
= c
ij
,
gdzie pary (i , j ) przebiegają przez zbiór wszystkich tras
bazowych rozwiązania dopuszczalnego X .
2
Dla każdej trasy niebazowej (r , s) wyznaczamy wskażnik
optymalności ∆
rs
= c
rs
− (u
r
+ v
s
).
3
Liczba ∆
rs
jest równa wartości o jaką zmieni się całkowity
koszt przewozu towarów, jeżeli trasą (r , s) zostanie
przewieziona jednostka towaru (przy jednoczesnej
odpowiedniej modyfikacji transportu na innych trasach).
4
Rozwiązanie X jest optymalne, jeśli wszystkie wskaźniki
optymalności ∆
rs
dla tras niebazowych są nieujemne.
Jacek Rogowski
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u
1
, u
2
, . . ., u
m
, v
1
, v
2
, . . ., v
n
przyjmując u
1
= 0 i rozwiązując układ równań
u
i
+ v
j
= c
ij
,
gdzie pary (i , j ) przebiegają przez zbiór wszystkich tras
bazowych rozwiązania dopuszczalnego X .
2
Dla każdej trasy niebazowej (r , s) wyznaczamy wskażnik
optymalności ∆
rs
= c
rs
− (u
r
+ v
s
).
3
Liczba ∆
rs
jest równa wartości o jaką zmieni się całkowity
koszt przewozu towarów, jeżeli trasą (r , s) zostanie
przewieziona jednostka towaru (przy jednoczesnej
odpowiedniej modyfikacji transportu na innych trasach).
4
Rozwiązanie X jest optymalne, jeśli wszystkie wskaźniki
optymalności ∆
rs
dla tras niebazowych są nieujemne.
Jacek Rogowski
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u
1
, u
2
, . . ., u
m
, v
1
, v
2
, . . ., v
n
przyjmując u
1
= 0 i rozwiązując układ równań
u
i
+ v
j
= c
ij
,
gdzie pary (i , j ) przebiegają przez zbiór wszystkich tras
bazowych rozwiązania dopuszczalnego X .
2
Dla każdej trasy niebazowej (r , s) wyznaczamy wskażnik
optymalności ∆
rs
= c
rs
− (u
r
+ v
s
).
3
Liczba ∆
rs
jest równa wartości o jaką zmieni się całkowity
koszt przewozu towarów, jeżeli trasą (r , s) zostanie
przewieziona jednostka towaru (przy jednoczesnej
odpowiedniej modyfikacji transportu na innych trasach).
4
Rozwiązanie X jest optymalne, jeśli wszystkie wskaźniki
optymalności ∆
rs
dla tras niebazowych są nieujemne.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
.
Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę.
Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
.
Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
.
Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę.
Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
.
Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę.
Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
.
Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę.
Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
.
Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
.
Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
.
Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
. Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
. Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ.
Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
. Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ. Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
. Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ. Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ,
wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiązania X .
1
Spośród ujemnych wskaźników optymalności wybieramy
najmniejszy wskaźnik ∆
rs
. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
2
W zbiorze tras bazowych rozwiązania X powiększonym o trasę
(r , s) znajdujemy cykl Γ zawierający tę trasę. Cykl ten
nazywamy cyklem korygującym.
3
Cykl korygujący dzielimy na dwa półcykle: dodatni Γ
+
i
ujemny Γ
−
w ten sposób, że w każdej linii zawierającej trasy
cyklu Γ znajdzie się jedna trasa z półcyklu Γ
+
i jedna trasa z
półcyklu Γ
−
. Trasę (r , s) zaliczamy do półcyklu Γ
+
.
4
Z tras w półcyklu Γ
−
wybieramy trasę o najmniejszym
przewozie równym δ. Trasa ta opuści bazę.
5
Wszystkie przewozy w półcyklu Γ
+
zwiększamy o δ, wszystkie
przewozy w półcyklu Γ
−
zmniejszamy o δ.
Jacek Rogowski