Badania operacyjne

dr inż. W. Zalewski

23

ZAGADNIENIE TRANSPORTOWE

Model ogólny zwykłego (klasycznego) zadania transportowego

Danych

jest

m dostawców pewnego jednorodnego produktu. Zasoby

tego produktu znajdujące się u i-tego dostawcy wynoszą a

i

(i = 1, 2, ..., m).

Produkt jest przeznaczony dla n odbiorców, których zapotrzebowanie

wynosi odpowiednio b

j

(j = 1, 2, ..., n). Koszt transportu jednostki

produktu od i-tego dostawcy do j-tego odbiorcy wynosi c

ij

(i = 1, 2, ..., m;

j = 1, 2, ..., n). Należy określić plan przewozów pomiędzy dostawcami

a odbiorcami tak, aby po uwzględnieniu dostępnych zasobów towaru

u dostawców i wymaganego zapotrzebowania odbiorców łączne koszty

transportu były minimalne.

Model matematyczny zadania

Funkcja

celu:

( )

min

x

c

x

f

m

1

i

n

1

j

ij

ij

ij

→

=

∑∑

=

=

przy warunkach ograniczających:

(1)

m

,

,

2

,

1

i

a

x

n

1

j

i

ij

!

=

≤

∑

=

(2)

n

,

,

2

,

1

j

b

x

m

1

i

j

ij

!

=

=

∑

=

(3)

n

,

,

2

,

1

j

;

m

,

,

2

,

1

i

0

x

ij

!

!

=

=

≥

Warunek (1) nosi nazwę warunku bilansującego dostawców.

Warunek (2) nosi nazwę warunku bilansującego odbiorców.

Badania operacyjne

dr inż. W. Zalewski

24

Własności zadania transportowego

Jeżeli

∑

∑

=

=

=

m

1

j

j

n

1

i

i

b

a

to zadanie nazywamy zbilansowanym lub

zamkniętym zadaniem transportowym.

Zbilansowanie zadania niezbilansowanego polega na:

Jeśli

∑

∑

=

=

>

m

1

j

j

n

1

i

i

b

a

wprowadza się fikcyjnego odbiorcę z zapotrzebowaniem wynoszącym

∑

∑

=

=

−

=

m

1

j

j

n

1

i

i

0

b

a

b

oraz przyjmuje się c

i0

= 0. Dostawy do fikcyjnego odbiorcy należy

traktować jako niewykorzystanie zasobów produktu u poszczególnych

dostawców. Formalnie operacja ta oznacza wprowadzenie zmiennych

dodatkowych do warunku (1).

Jeśli

∑

∑

=

=

<

m

1

j

j

n

1

i

i

b

a

wprowadza się fikcyjnego dostawcę z zasobem produktu wynoszącym

∑

∑

=

=

−

=

n

1

i

i

m

1

j

j

0

a

b

a

oraz przyjmuje się c

0j

= 0. Dostawy do fikcyjnego dostawcy reprezentują

niezaspokojone zapotrzebowanie odbiorców.

HACKED BY VIPER :)

Badania operacyjne

dr inż. W. Zalewski

25

Twierdzenia dotyczące zadania transportowego

T1. W każdym zbilansowanym zadaniu transportowym zbiór rozwiązań

dopuszczalnych jest niepusty i ograniczony.

Z powyższego wynika, że każde zbilansowane zadanie transportowe

posiada skończone rozwiązanie optymalne.

T2. Rząd macierzy A warunków ograniczających zadania

transportowego jest równy m + n –1.

Z powyższego wynika, że w rozwiązaniu optymalnym zadania

transportowego co najwyżej m + n –1 zmiennych jest niezerowych.

T3. Jeżeli wszystkie a

i

i b

j

w zadaniu transportowym są liczbami

całkowitymi, to każde rozwiązanie bazowe (również optymalne) jest

utworzone z liczb całkowitych.

T4. Rozwiązanie dopuszczalne zadania transportowego jest

rozwiązaniem bazowym wtedy i tylko wtedy, gdy odpowiadający mu

graf jest grafem spójnym i bez cykli.

T5. Na to aby graf rozwiązania zadania transportowego był grafem

spójnym i bez cykli potrzeba i wystarcza, żeby zawierał dokładnie

m + n –1 wierzchołków.

Badania operacyjne

dr inż. W. Zalewski

26

Metody wyznaczania rozwiązań wstępnych

Metoda kąta północno-zachodniego

j
i

1 2 ...

m

a

i

1

2

...

n

x

11

x

12

... x

1m

x

21

x

22

...

x

2m

... ... ... ...

x

11

x

11

...

x

11

a

1

a

2

...

a

n

b

j

b

1

b

2

... b

m

{

}

1

1

11

b

,

a

min

x

=

{

}

1

p

j

1

p
i

ij

b

,

a

min

x

−

−

=

gdzie

ij

1

p
i

p
i

x

a

a

−

=

−

ij

1

p

j

p

j

x

b

b

−

=

−

,

ponadto:

i

0
i

a

a

=

j

0

j

b

b

=

Metoda minimalnego elementu macierzy kosztów

Reguła wyboru numeru (k,l) zmiennej x

kl

na zmienna bazową:

( )

{

}

J

I

×

∈

=

j

,i

:

c

min

c

ij

kl

gdzie I – zbiór numerów dostawców,

J – zbiór numerów odbiorców.

HACKED BY VIPER :)

Badania operacyjne

dr inż. W. Zalewski

27

Problemy sprowadzalne do zagadnienia transportowego

Zadanie transportowo-produkcyjne i transportowo -magazynowe

Danych

jest

n producentów pewnego jednorodnego produktu P

1

,

P

2

, ..., P

n

. Każdy z nich ma określone zdolności produkcyjne a

1

, a

2

, ..., a

n

.

Odbiorcy, których jest m zgłaszają odpowiednio zapotrzebowanie b

1

,

b

2

, ..., b

m

takie, że

∑

∑

=

=

≥

m

1

j

j

n

1

i

i

b

a

Znane

są ponadto jednostkowe koszty produkcji określone dla

poszczególnych producentów p

1

, p

2

, ..., p

n

oraz tablica jednostkowych

kosztów transportu [c

ij

].

Należy wyznaczyć taki plan transportu i produkcji (transportu

i wykorzystania mocy produkcyjnych poszczególnych producentów) aby

łączny koszt był minimalny.

Powyższe zadanie transportowo-produkcyjne można sprowadzić do

zadania transportowego przez:

1)

wprowadzenie fikcyjnego odbiorcy O

m+1

, który będzie

reprezentować nie wykorzystane moce produkcyjne poszczególnych

producentów i dla którego zapotrzebowanie określamy jako:

∑

∑

=

=

+

−

=

m

1

j

j

n

1

i

i

1

m

b

a

b

2)

skonstruowanie macierzy kosztów transportu i produkcji

w następujący sposób:

c

*

i m+1

= 0

c

*

ij

= c

ij

+ p

i

,

dla j = 1, 2, ..., m oraz i = 1, 2, ..., n.

Badania operacyjne

dr inż. W. Zalewski

28

Uogólnione zadanie transportowe

Niech

będzie dana sieć G = <S, U>, gdzie S jest zbiorem węzłów

sieci, a U zbiorem połączeń między węzłami. W zbiorze S węzłów sieci

wyróżniamy dwa rozłączne podzbiory: D – zbiór dostawców i O – zbiór

odbiorców: D

⊂

S, O

⊂

S i D

∩

O =

∅

.

Dla

każdego z s

i

∈

D określone są wielkości a

i

, które będziemy

interpretować jako wielkość podaży, dla s

i

∈

O – wielkości b

j

,

odzwierciedlające popyt w punkcie S

j

, dla s

k

∈

S – {D

∪

O} – wielkości

p

k

, oznaczające przepustowość. Zbiór P = S – {D

∪

O} jest zbiorem

punktów pośrednich.

Na zbiorze S określona jest pewna relacja R opisująca możliwe

połączenia między punktami, a każde z połączeń scharakteryzowane jest

przez pewną nieujemną liczbę k

ij

oznaczającą przepustowość połączenia.

Relację R można opisać za pomocą funkcji wielowartościowych:

Γ

+

(s

i

) = {s

j

: (s

i

,s

j

)

∈

U} – zbiór poprzedników węzła s

i

,

Γ

-

(s

i

) = {s

k

: (s

k

,s

i

)

∈

U} – zbiór następników węzła s

i

,

Niech

c

ij

oznacza koszt (odległość, czas) przewozu jednostki towaru

z punktu s

i

do s

j

.

Zadanie polega na wyznaczeniu takiego planu przewozu towaru

z punktów należących do zbioru O do punktów ze zbioru D, aby

zaspakajając zapotrzebowanie odbiorców nie przekroczyć możliwości

dostawców, przepustowości połączeń oraz przepustowości punktów

pośrednich a jednocześnie spełnić określone kryterium optymalności

rozwiązania problemu.

HACKED BY VIPER :)

Badania operacyjne

dr inż. W. Zalewski

29

Jeżeli przez x

ij

oznaczymy wielkość przewozu towarów z punktu s

i

do s

j

, to dopuszczalne wartości x

ij

muszą spełniać warunki:

! dopuszczalnej przepustowości połączeń

0

≤

x

ij

≤

k

ij

(1)

! ilości towaru wwiezionego i wywiezionego z węzła

( )

( )

{

}

O

D

S

s

dla

x

x

i

s

s

ij

s

s

ki

i

j

i

k

∪

−

∈

=

∑

∑

+

−

Γ

∈

Γ

∈

(2)

! dopuszczalnej przepustowości węzłów

( )

{

}

O

D

S

s

dla

p

x

i

s

s

i

ki

i

k

∪

−

∈

≤

∑

−

Γ

∈

(3)

! nieprzekroczenia podaży poszczególnych dostawców

( )

D

s

dla

a

x

i

s

s

i

ik

i

k

∈

≤

∑

+

Γ

∈

(4)

! zaspokojenia zapotrzebowania poszczególnych odbiorców

( )

O

s

dla

b

x

j

s

s

j

kj

k

k

∈

=

∑

+

Γ

∈

(5)

Dopuszczalne plany przewozów można ocenić za pomocą

następujących przykładowych kryteriów:

( )

min

c

x

U

s

,

s

ij

ij

j

i

→

∑

∈

( )

min

c

max

r

j

i

L

s

,

s

ij

→

















∑

∈

HACKED BY VIPER :)