Zagadnienie i algorytm 

transportowy

 

 

Zagadnienie transportowe

Ekonomiczne 

sformułowanie 

problemu 

transportowego

Istnieje  pewna  liczba  punktów  nadania  i  punktów  odbioru 
jednorodnego towaru.

Należy  tak  powiązać  ze  sobą  miejsca  dostaw  z  miejscami 
odbioru,  ażeby  łączne  koszty  transportu  były  jak 
najmniejsze

 

 

Wymagana jest znajomość następujących wielkości:

1. Limity dostaw dostawców.

2. Zapotrzebowanie odbiorców.

3. Jednostkowe  koszty  transportu  we  wszystkich 

relacjach.

 

 

Matematyczne sformułowanie zagadnienia transportowego

0

,

,

2

,

1

    

,

)

(

,

,

2

,

1

    

,

min

)

(

1

1

1

1































ij

j

m

i

ij

i

n

j

ij

m

i

n

j

ij

ij

x

n

j

b

x

m

i

a

x

x

c

x

L





 

 

Oznaczenia:
x

ij

—  wielkość  przewozu  towaru  od  i-tego 
dostawcy do j-tego odbiorcy,

c

ij

—  jednostkowy  koszt  przewozu  towaru  od  i-
tego dostawcy do j-tego odbiorcy,

a

i

— limit dostaw i-tego dostawcy,

b

j

— zapotrzebowanie j-tego odbiorcy,

m — liczba dostawców,
n — liczba odbiorców.

 

 

Tablica transportowa

     Odb.

Dost.

1

2



n

Limity 

dostaw

1

x

11

x

12



x

1n

a

1

2

x

21

x

22



x

2n

a

2













m

x

m1

x

m2



x

mn

a

m

Zapotrz

ebowani

e

b

1

b

2



b

n

 

 

Macierz kosztów jednostkowych



























mn

m

m

n

n

ij

c

c

c

c

c

c

c

c

c

c















2

1

2

22

21

1

12

11

 

 

Rozwiązywanie zadań 

transportowych – algorytm 

transportowy

Algorytm transportowy to zmodyfikowana metoda 
simpleks  służąca  do  rozwiązywania  zadań 
transportowych.

Podstawowym  warunkiem  stosowania  algorytmu 
transportowego  jest,  ażeby  zadanie  transportowe 
było  zbilansowane.  Oznacza  to,  że  suma  dostaw 
musi być równa sumie zapotrzebowania.

 

 

Możliwe sytuacje:

a) a

i

 > b

j

 – rynek konsumenta;

wprowadzamy 

fikcyjnego 

odbiorcę 

o 

zapotrzebowaniu:
b

n + 1

 = a

i

 – b

j

a) a

i

 < b

j

 – rynek producenta;

wprowadzamy  fikcyjnego  dostawcę  o  limicie 
dostaw:
a

m + 1

 = b

j 

–

 

a

i

 

 

Zadanie transportowe zbilansowane

0

,

,

2

,

1

    

,

,

,

2

,

1

    

,

min

)

(

1

1

1

1

1

1







































ij

m

j

j

m

i

i

j

m

i

ij

i

n

j

ij

m

i

n

j

ij

ij

x

b

a

n

j

b

x

m

i

a

x

x

c

x

L





 

 

Algorytm transportowy

1.

Ustalenie rozwiązania bazowego wyjściowego.

2.

Sprawdzenie optymalności rozwiązania.

3.

Jeżeli  rozwiązanie  wyjściowe  nie  jest  jeszcze 
optymalne, 

należy 

wyznaczyć 

zmienną 

wprowadzaną do bazy.

4.

Wyznaczenie nowych wartości zmiennych bazowych.

5.

Powyższe  kroki  powtarza  się,  aż  uzyskamy 
rozwiązanie optymalne.

 

 

Metody ustalania rozwiązania wyjściowego

1. Metoda  lewego-górnego  rogu  (metoda  kąta 

północno-zachodniego).

2. Metoda minimum macierzy.

3. Metoda aproksymacji Vogla.

Rozwiązanie  bazowe  zadania  transportowego 
zapisuje się w tablicy transportowej, która ma tyle 
wierszy,  ilu  jest  dostawców  (wiersz  odpowiada 
dostawcy)  oraz  tyle  kolumn,  ilu  odbiorców 
(kolumna odpowiada odbiorcy).

Zatem tablica transportowa ma wymiary m  n.
Liczba zmiennych bazowych każdego rozwiązania 
podstawowego jest równa m + n – 1.

 

 

Sprawdzenie optymalności rozwiązania 

bazowego

Wyznaczamy  macierz  wskaźników  optymalności 


ij

 według wzoru:

,

ij

ij

ij

c

c 





gdzie:

c

ij

—  elementy  macierzy  jednostkowych 
kosztów transportu,

 elementy macierzy kosztów pośrednich.

ij

c

 

 

Wyznaczanie macierzy kosztów pośrednich

1. Na polach bazowych przepisujemy wartości z 

macierzy c

ij

.

2. Pozostałe  pola  uzupełniamy  w  myśl  jednej  z 

dwóch zasad:

a) metody jednakowych różnic:

porównujemy  ze  sobą  dowolne  dwa 

wiersze  albo  dowolne  dwie  kolumny. 

Puste pola wypełniamy tak, ażeby różnice 

pomiędzy  elementami  porównywanych 

kolumn (wierszy) były jednakowe.

b) metody potencjałów:

dla 

wartości 

kosztów 

pośrednich 

leżących na polach bazowych korzystamy 

z następującej zależności:

 

 

,

j

i

ij

v

u

c





gdzie:

u

i

 potencjały dla wierszy,

v

j

 potencjały dla kolumn.

Najpierw  wyznaczamy  potencjały  dla  pól  bazowych 
(w  pierwszym  wierszu  wpisujemy  u

1

  =  0),  a 

następnie 

z 

tak 

wyliczonych 

potencjałów 

wyznaczamy  wartości  kosztów  pośrednich  dla  pól 
niebazowych.

 

 

Sprawdzenie optymalności rozwiązania 

bazowego.

1. Jeżeli  wszystkie  wyznaczone  wartości  wskaźników 

optymalności  

ij

  są  niedodatnie,  wówczas  badane 

rozwiązanie jest optymalne.

2. Jeżeli  zaś  przynajmniej  jeden  element  macierzy  

ij

 

jest dodatni, wówczas rozwiązanie należy poprawić.

 

 

Ulepszanie rozwiązania bazowego

1. W  macierzy  wskaźników  optymalności  znajdujemy 

największą wartość dodatnią.

2. W  wybrane  pole  wprowadzamy  nową  zmienną 

bazową.

3. Budujemy graf przesunięć.

Graf  przesunięć  jest  to  linia  łamana  zamknięta, 
utworzona  z  odcinków  leżących  na  polach 
bazowych.  W  miejscu,  gdzie  dwa  odcinki  się 
stykają, 

jest 

kąt 

prosty. 

Budowę 

grafu 

rozpoczynamy  od  pola,  w  które  wprowadzamy 
nową  zmienną.  Pole  to  oznaczamy  „+”.  Kolejne 
pole oznaczamy „–”, kolejne „+”, i tak dalej. Pola z 
„+”  tworzą  półcykle  dodatnie,  a  pola  z  „–”  – 
półcykle ujemne.

4. Wyznaczamy wartość nowej zmiennej bazowej:

 = min z półcykli ujemnych.

 

 

5. Przeliczamy  wartości  zmiennych  bazowych 

w  taki  sposób,  że  w  miejscu  półcykli 
dodatnich dodajemy wartość  , a w miejscu 

półcykli ujemnych – odejmujemy.

6. Uzyskujemy nowe rozwiązanie bazowe.

Całą  procedurę  ulepszania  stosujemy,  aż 
uzyskamy rozwiązanie optymalne.

 

 

Twierdzenia dotyczące algorytmu 

transportowego

1. Jeżeli 

wielkości 

dostaw 

oraz 

wielkości 

zapotrzebowania w zagadnieniu transportowym są 

liczbami całkowitymi, to każde rozwiązanie bazowe 

także jest wyrażone w liczbach całkowitych.

2. Zadanie  transportowe,  w  którym  łączna  objętość 

dostaw  jest  równa  łącznej  sumie  zapotrzebowania 

(czyli  jeżeli  jest  zbilansowane),  zawsze  posiada 

rozwiązanie.

3. Warunkiem  koniecznym  i  wystarczającym  na  to, 

ażeby  rozwiązanie  zadania  transportowego  było 

niezdegenerowane  jest,  aby  nie  było  takiej 

niepełnej  liczby  punktów  nadania,  dla  których 

łączna  objętość  dostaw  jest  równa  sumarycznemu 

zapotrzebowaniu pewnej grupy punktów odbioru.