Wykład 1
Zadanie transportowe
Jacek Rogowski
Instytut Matematyki
Politechnika Aódzka
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D1, D2, ..., Dm,
do n odbiorców: O1, O2, ..., On, przy czym dostawca Di dysponuje
ai jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru (j = 1, 2, . . . , n).
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D1, D2, ..., Dm,
do n odbiorców: O1, O2, ..., On, przy czym dostawca Di dysponuje
ai jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i, j) od dostawcy Di do odbiorcy Oj znany jest
koszt cij transportu jednostki towaru na tej trasie.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D1, D2, ..., Dm,
do n odbiorców: O1, O2, ..., On, przy czym dostawca Di dysponuje
ai jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i, j) od dostawcy Di do odbiorcy Oj znany jest
koszt cij 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.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D1, D2, ..., Dm,
do n odbiorców: O1, O2, ..., On, przy czym dostawca Di dysponuje
ai jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i, j) od dostawcy Di do odbiorcy Oj znany jest
koszt cij 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 znalezć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D1, D2, ..., Dm,
do n odbiorców: O1, O2, ..., On, przy czym dostawca Di dysponuje
ai jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i, j) od dostawcy Di do odbiorcy Oj znany jest
koszt cij 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 znalezć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiÄ…zania:
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Pewien towar jest wysyłany przez m dostawców: D1, D2, ..., Dm,
do n odbiorców: O1, O2, ..., On, przy czym dostawca Di dysponuje
ai jednostkami towaru (i = 1, 2, . . . , m), zaś odbiorca Oj zgłasza
zapotrzebowanie na bj jednostek towaru (j = 1, 2, . . . , n).Ponadto
dla każdej trasy (i, j) od dostawcy Di do odbiorcy Oj znany jest
koszt cij 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 znalezć najtańszy plan przewozu towaru od dostawców do
odbiorców zaspokajający oczekiwania obu stron.
Warunek konieczny istnienia rozwiÄ…zania:
m n
ai = bj. (1)
i=1 j=1
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
ZT spełniające warunek (1) nazywamy zbilansowanym.
Jacek Rogowski Wykład 1: Zadanie transportowe
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ń:
Jacek Rogowski Wykład 1: Zadanie transportowe
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,
Jacek Rogowski Wykład 1: Zadanie transportowe
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,
Jacek Rogowski Wykład 1: Zadanie transportowe
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 n
ai - bj ,
i=1 j=1
Jacek Rogowski Wykład 1: Zadanie transportowe
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 n
ai - bj ,
i=1 j=1
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0
Jacek Rogowski Wykład 1: Zadanie transportowe
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 n
ai - bj ,
i=1 j=1
wprowadzenie na fikcyjnych trasach jednostkowych kosztów
transportu równych 0 (lub innych, wynikających z warunków
zadania).
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Najczęściej dane ZT podaje się w postaci tabeli:
O1 O2 . . . On Podaż
D1 c11 c12 . . . c1n a1
D2 c21 c22 . . . c2n a2
. . . . .
. . . . .
. . . . .
Dm cm1 cm2 . . . cmn am
Popyt b1 b2 . . . bn
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Najczęściej dane ZT podaje się w postaci tabeli:
O1 O2 . . . On Podaż
D1 c11 c12 . . . c1n a1
D2 c21 c22 . . . c2n a2
. . . . .
. . . . .
. . . . .
Dm cm1 cm2 . . . cmn am
Popyt b1 b2 . . . bn
Tabelę tę nazywa się macierzą (tablicą) kosztów
jednostkowych.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Uwagi I.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby ai, bj oraz cij są
nieujemne.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby ai, bj oraz cij są
nieujemne.
Zbilansowane ZT ma zawsze rozwiÄ…zanie.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Uwagi I.
Oczywiste założenie: Wszystkie liczby ai, bj oraz cij są
nieujemne.
Zbilansowane ZT ma zawsze rozwiÄ…zanie.
Jeżeli w zbilansowanym ZT wszystkie liczby ai, bj oraz cij są
wymierne, to rozwiązanie ZT można znalezć w skończonej
liczbie kroków za pomocą tzw. algorytmu transportowego,
który zostanie omówiony w dalszym ciągu.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Uwagi II.
Jacek Rogowski Wykład 1: Zadanie transportowe
Klasyczne zadanie transportowe
Uwagi II.
Plan przewozów znaleziony w wyniku rozwiązania
niezbilansowanego ZT nie zaspokoi oczekiwań jednej ze stron.
Jacek Rogowski Wykład 1: Zadanie transportowe
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;
Jacek Rogowski Wykład 1: Zadanie transportowe
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.).
Jacek Rogowski Wykład 1: Zadanie transportowe
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.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 Wykład 1: Zadanie transportowe
ZT jako ZPL
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez xij wielkość transportu odbywającego się na trasie
(i, j) od dostawcy Di do odbiorcy Oj.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez xij wielkość transportu odbywającego się na trasie
(i, j) od dostawcy Di do odbiorcy Oj. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez xij wielkość transportu odbywającego się na trasie
(i, j) od dostawcy Di do odbiorcy Oj. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m n
cijxij min,
i=1 j=1
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez xij wielkość transportu odbywającego się na trasie
(i, j) od dostawcy Di do odbiorcy Oj. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m n
cijxij min,
i=1 j=1
n
xij = ai, dla i = 1, . . . , m,
j=1
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez xij wielkość transportu odbywającego się na trasie
(i, j) od dostawcy Di do odbiorcy Oj. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m n
cijxij min,
i=1 j=1
n
xij = ai, dla i = 1, . . . , m,
j=1
m
xij = bj, dla j = 1, . . . , n,
i=1
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Przyjmijmy wcześniej wprowadzone oznaczenia. Dodatkowo
oznaczmy przez xij wielkość transportu odbywającego się na trasie
(i, j) od dostawcy Di do odbiorcy Oj. Wówczas ZT można zapisać
w następującej formalnej postaci, jako ZPL:
m n
cijxij min,
i=1 j=1
n
xij = ai, dla i = 1, . . . , m,
j=1
m
xij = bj, dla j = 1, . . . , n,
i=1
xij 0, dla i = 1, . . . , m, j = 1, . . . , n.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo zauważyć, że ograniczenia tworzą układ zależnych
równań liniowych
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi.
Aatwo 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 Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n - 1 kolumn
macierzy jednostkowej Im+n-1.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n - 1 kolumn
macierzy jednostkowej Im+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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n - 1 kolumn
macierzy jednostkowej Im+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:
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n - 1 kolumn
macierzy jednostkowej Im+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,
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n - 1 kolumn
macierzy jednostkowej Im+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.
Jacek Rogowski Wykład 1: Zadanie transportowe
ZT jako ZPL
Uwagi c.d.
Pierwsza tablica sympleksowa rozważanego ZPL ze
zredukowanym układem ograniczeń zawiera m + n - 1 kolumn
macierzy jednostkowej Im+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 Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Algorytm rozwiÄ…zywania ZT,
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Algorytm rozwiÄ…zywania ZT, zwany dalej algorytmem
transportowym, (w skrócie: AT)
Jacek Rogowski Wykład 1: Zadanie transportowe
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:
Jacek Rogowski Wykład 1: Zadanie transportowe
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.
Jacek Rogowski Wykład 1: Zadanie transportowe
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,
Jacek Rogowski Wykład 1: Zadanie transportowe
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.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
RozwiÄ…zanie to zawiera m + n - 1 tras bazowych,
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
Rozwiązanie to zawiera m + n - 1 tras bazowych, a więc co
najwyżej m + n - 1 liczb xij jest dodatnich;
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
Rozwiązanie to zawiera m + n - 1 tras bazowych, a więc co
najwyżej m + n - 1 liczb xij jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
Rozwiązanie to zawiera m + n - 1 tras bazowych, a więc co
najwyżej m + n - 1 liczb xij jest dodatnich; przewozy na trasach
niebazowych są równe 0.
Uwaga: Przewóz na trasie bazowej też może być równy 0,
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
Rozwiązanie to zawiera m + n - 1 tras bazowych, a więc co
najwyżej m + n - 1 liczb xij 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,
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Rozwiązania dopuszczalne będziemy zapisywać w postaci macierzy
(tablicy, tabeli) przewozów wymiaru m × n:
x11 x12 . . . x1n
x21 x22 . . . x2n
X = .
. . .
. . .
. . .
xm1 xm2 . . . xmn
Rozwiązanie to zawiera m + n - 1 tras bazowych, a więc co
najwyżej m + n - 1 liczb xij 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 Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Trzy użyteczne pojęcia.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Trzy użyteczne pojęcia.
Definicja
Linią nazywamy każdy wiersz lub każdą kolumnę w macierzy X .
Jacek Rogowski Wykład 1: Zadanie transportowe
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.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Wyznaczanie poczÄ…tkowego rozwiÄ…zania dopuszczalnego
metodą kąta północno-zachodniego.
Jacek Rogowski Wykład 1: Zadanie transportowe
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Ä™.
Jacek Rogowski Wykład 1: Zadanie transportowe
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.
Jacek Rogowski Wykład 1: Zadanie transportowe
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(ai, bj) i blokujemy
(wykreślamy) wszystkie pola tej linii, dla której podaż/popyt
jest równy tej liczbie.
Jacek Rogowski Wykład 1: Zadanie transportowe
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(ai, bj) 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(ai, bj).
Jacek Rogowski Wykład 1: Zadanie transportowe
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(ai, bj) 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(ai, bj).
5
Czynności (2) (4) kontynuujemy dopóki istnieją
niewypełnione i niezablokowane pola na mapie.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Wyznaczanie poczÄ…tkowego rozwiÄ…zania dopuszczalnego
metodą minimalnego elementu macierzy kosztów.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 cij.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 cij.
2
W pole (i, j) macierzy X wpisujemy liczbÄ™ min(ai, bj) i
blokujemy (wykreślamy) wszystkie pola tej linii, dla której
podaż/popyt jest równy tej liczbie.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 cij.
2
W pole (i, j) macierzy X wpisujemy liczbÄ™ min(ai, bj) 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(ai, bj).
Jacek Rogowski Wykład 1: Zadanie transportowe
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 cij.
2
W pole (i, j) macierzy X wpisujemy liczbÄ™ min(ai, bj) 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(ai, bj).
4
Blokujemy odpowiednie pola w macierzy kosztów
jednostkowych transportu.
Jacek Rogowski Wykład 1: Zadanie transportowe
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 cij.
2
W pole (i, j) macierzy X wpisujemy liczbÄ™ min(ai, bj) 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(ai, bj).
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 Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u1, u2, . . ., um, v1, v2, . . ., vn
przyjmując u1 = 0 i rozwiązując układ równań
ui + vj = cij,
gdzie pary (i, j) przebiegają przez zbiór wszystkich tras
bazowych rozwiÄ…zania dopuszczalnego X .
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u1, u2, . . ., um, v1, v2, . . ., vn
przyjmując u1 = 0 i rozwiązując układ równań
ui + vj = cij,
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 = crs - (ur + vs).
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u1, u2, . . ., um, v1, v2, . . ., vn
przyjmując u1 = 0 i rozwiązując układ równań
ui + vj = cij,
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 = crs - (ur + vs).
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).
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Optymalność rozwiązania X . Metoda potencjałów.
1
Znajdujemy potencjały u1, u2, . . ., um, v1, v2, . . ., vn
przyjmując u1 = 0 i rozwiązując układ równań
ui + vj = cij,
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 = crs - (ur + vs).
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 wskazniki
optymalności "rs dla tras niebazowych są nieujemne.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "rs.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "rs. Trasa ta będzie trasą bazową w
nowym rozwiazaniu dopuszczalnym.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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Ä™.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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 “-.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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 “+.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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 ´.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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Ä™.
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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 ´,
Jacek Rogowski Wykład 1: Zadanie transportowe
Algorytm transportowy (AT)
Poprawianie nieoptymalnego rozwiÄ…zania X .
1
Spośród ujemnych wskazników optymalności wybieramy
najmniejszy wskaznik "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 Wykład 1: Zadanie transportowe
Wyszukiwarka
Podobne podstrony:
BOwL wyklad Beamer 14BOwL wyklad Beamer 14BOwL wyklad Beamer 15wykład 13 i 14 stacjonarneElectronic Commerce wyklad ie? 14 prawoSS wyklad nr 14 pptWyklad 05 14 15 GWPSM Wyklad 13 14wyklad 10 14 12 20100214 13 10 2009, wykład nr 14 , Układ pokarmowy, cześć II Paul EszWyklad 01 14 15 GWWyklad 02 14 15 GWWyklad 06 14 15 GWET DI2 ObwodySygnaly2 wyklad nr 1 5 14 w1ami wyklad1 12 14Wyklad4 OS 14Wyklad studport 14więcej podobnych podstron