Wykład 1

Zadanie transportowe

Jacek Rogowski

Instytut Matematyki

Politechnika Łódzka

Jacek Rogowski

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

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

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

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

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

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

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

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

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 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

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 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

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 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

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 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

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 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

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 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

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 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

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)

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)

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)

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)

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)

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)

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:

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

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)

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)

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)

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.

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

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(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

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(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

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(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

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(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

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(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

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 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

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 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

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 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

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 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

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 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

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 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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe

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

Wykład 1: Zadanie transportowe