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.