W12 zag transp id 526678

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

WYKŁAD 12

ZAGADNIENIA (ZADANIA) TRANSPORTOWE

– BADANIA OPERACYJNE

1.Zagadnienia programowania liniowego

Działanie intuicyjne rzadko prowadzi do podjęcia optymalnej decyzji, co moŜe

narazić nas utratę pewnych korzyści. Z pomocą przychodzą róŜnego typu metody

rozwiązywania problemów decyzyjnych. Opisanie sytuacji decyzyjnej w języku

matematycznym ma na celu sprowadzenie problemu wyboru najlepszej decyzji do

rozwiązania jednoznacznie określonego zadania matematycznego.

Aby rozwiązanie takiego zadania umoŜliwiło wybór najlepszej decyzji przy

ustalonych ograniczeniach naleŜy określić:

• jakie wielkości mają być wyznaczone (określenie zmiennych decyzyjnych),

• jakie wielkości są dane (określenie parametrów zadania),

• jakie są warunki ograniczające dla danych zmiennych decyzyjnych,

• funkcję celu jako funkcję zmiennych decyzyjnych.

JeŜeli w zadaniu decyzyjnym funkcja celu i wszystkie warunki ograniczające są liniowe, to zadanie takie nazywa się Liniowym Zadaniem Decyzyjnym. Jeśli dodatkowo wszystkie zmienne są ciągłe, to zadanie takie nazywamy Zadaniem Programowania Liniowego.

Ogólna postać takich zadań jest następująca:

• funkcja celu:

∑ c x

max(min)

→

j = 1

• ograniczenia:

∑ a x

≤

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

j = 1

∑ a x

≥

(i=m+1,...,p)

j = 1

∑ a x

(i=p+1,...,p)

j = 1

n 1 ≤

≥ 0 (j=1,2,...,n1)

gdzie:

gdzie:

cj - np. koszt wykonania zadania „ j”

KaŜdy wektor zmiennych decyzyjnych:

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

x = ( x1, x2 ,... ,x n)

spełniający warunki ograniczające nazywamy rozwiązaniem dopuszczalnym.

Rozwiązanie dopuszczalne, dla którego funkcja celu osiąga maksimum (minimum),

nazywamy rozwiązaniem optymalnym.

Przy rozwiązywaniu zadań decyzyjnych istotne jest załoŜenie, Ŝe zadanie z funkcją celu:

∑ c

max

→

j = 1

jest równowaŜne zadaniu z funkcją celu:

∑ ( − c

) x

min

→

j = 1

Zadania programowania liniowego w postaci macierzowej moŜemy zapisać następująco:

 cx → max(min)

 Ax = b



 x ≥ 0

gdzie:

 a



 11

1 n 

 21

2 n 

A = 

- macierz współczynników,







 a

mn 

 b







 b 2





- wektor wyrazów wolnych,







 b m



 x







 x 2 



 - wektor zmiennych decyzyjnych,





 x n 

c = [ c

n ] - wektor wag funkcji celu.

Podstawową metodą pozwalającą na rozwiązanie dowolnego zadania programowania

liniowego jest metoda Simpleks. Polega ona na sekwencyjnym, ściśle określonym przeglądzie tworzonych kolejno tablic simpleksowych.

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

Z kaŜdą zmienną xj związany jest wskaźnik kryterium optymalności. Dla zmiennych bazowych ma on zawsze wartość zero, natomiast dla zmiennych niebazowych wskaźnik ten określa, jak zmieni się wartość funkcji celu, gdy zmienna xj przyjmie wartość 1, a wartości zmiennych bazowych zostaną odpowiednio zmienione w celu zachowania

dopuszczalności rozwiązania.

Metoda Simpleks

ZałóŜmy, Ŝe dane jest zadanie programowania liniowego w postaci:

 cx

→

max

 Ax



 x ≥ 0

Przez B oznaczamy macierz kwadratową m- tego stopnia, składająca się z m liniowo niezaleŜnych kolumn macierzy A.

Macierz B nazywamy bazą, jej kolumny – kolumnami bazowymi, a pozostałe kolumny macierzy A – kolumnami niebazowymi.

Zmienne związane z kolumnami bazowymi nazywamy zmiennymi bazowymi, a

pozostałe zmienne – niebazowymi.

Z kaŜdą bazą związane jest rozwiązanie bazowe.

JeŜeli układ Ax=b jest niesprzeczny oraz n>m,

to układ ten ma nieskończenie wiele rozwiązań, ale skończenie wiele rozwiązań bazowych.

n !

Układ taki ma co najwyŜej: m ! ( n −

rozwiązań bazowych.

)

Dla zadań programowania liniowego prawdziwe jest twierdzenie:

JeŜeli zadanie ma rozwiązanie optymalne, to ma równieŜ rozwiązanie optymalne bazowe.

2. Zadania (Zagadnienia) transportowe

Jednym z ciekawszych szczególnych przypadków liniowych zadań decyzyjnych są z

tzw. zadania transportowe.

Charakteryzują się one specyficznym układem macierzy współczynników oraz

warunków ograniczających. Zadanie transportowe (sformułowane w 1934 r. przez L.

Kantorowicza) było jednym z pierwszych rozwiązanych problemów programowania liniowego. Noszą one czasem nazwę problemu Hitchcoca od nazwiska angielskiego badacza, który w 1941 r. opublikował wersję zadania i algorytmu zwanego dziś pod nazwą klasycznego zadania transportowego.

Sytuację klasycznego zagadnienia transportowego ilustruje rysunek 1.

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

punkt

przewóz na

punkt

nadania i

trasach ( i, j)

odbioru j

o daŜ

popyt

Rys.1. Schemat klasycznego zadania transportowego

Przy uŜyciu algorytmu słuŜącego do rozwiązywania zadań transportowych moŜna

rozstrzygać problemy decyzyjne:

• dotyczące przepływu dóbr pomiędzy -n- „dostawcami” dysponującymi ai

jednostkami produktu (i=....n)

oraz -m- „odbiorcami” wyraŜającymi zapotrzebowanie na

bj jednostek produktu (j=1 .. m).

ponadto:

• kaŜdy „dostawca” moŜe zaopatrywać dowolnego „odbiorcę”, a kaŜdy

„odbiorca” moŜe odbierać towar od dowolnego „dostawcy”,

• muszą być znane koszty jednostkowe cij związane z przepływem dóbr od dostawcy i do odbiorcy j.

Określając przez xij ( zmienne decyzyjne) wielkość dostawy od i-tego dostawcy do j-tego

odbiorcy, zadanie transportowe moŜna zapisać w następująco:

∑

1 , 2 ,...,

i = 1

∑

i ,

1 , 2 ,...,

j = 1

oraz:

≥

0 ,

1 , 2 ,..., n ; j

1 , 2 ,..., m

dla których funkcja celu:

∑

min

i = 1

j = 1

osiąga wartość minimalną.

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

Dodatkowo musi być spełniony warunek równości popytu i podaŜy:

jest to tzw. Zamknięte Zadanie Transportowe (ZZT) .

∑ a

= ∑

i = 1

j = 1

W praktyce spotykamy się przewaŜnie z problemami, w których podaŜ przewyŜsza popyt, bądź

teŜ zapotrzebowanie jest większe od dostępnej ilości towaru.

W takim przypadku mówimy o zadaniu niezbilansowanym i określamy je:

Otwartym Zadaniem Transportowym (OZT).

W celu rozwiązania tak postawionego problemu naleŜy go sprowadzić do postaci

zbilansowanej:

• Przypadek 1 – ze względu na niedobór zapasów nie moŜemy zaspokoić potrzeb wszystkich klientów (podaŜ mniejsza od popytu):

∑ a

< ∑

i = 1

j = 1

Aby uzyskać postać zbilansowaną do zadania wprowadzamy „fikcyjnego” dostawcę

posiadającego dokładnie am+1 produktów:

m + 1

= ∑

− ∑

j = 1

i = 1

Dodatkowo do macierzy kosztów wprowadzamy współczynniki

cm+1,1=0,...,cm+1,n=0 (koszty „fikcyjnego” transportu) .

• Przypadek 2 – zapotrzebowanie na produkty jest mniejsze niŜ zapasy magazynowe

(podaŜ większa od popytu).

∑ a

> ∑

i = 1

j = 1

W celu uzyskania postaci zbilansowanej, wprowadzamy „fikcyjnego” odbiorcę,

który potrzebuje dokładnie bn+1 produktów:

−

∑

i = 1

j = 1

Dodatkowo do macierzy kosztów wprowadzamy współczynniki

cn+1,1=0,...,cn+1,m= 0 (koszty „fikcyjnego” transportu).

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

W postępowaniach prowadzących do wyznaczenia wielkości dostaw wyróŜnia się dwa etapy:

Wyznaczany jest wstępny plan dopuszczalnego transportu, tzw. pierwsze bazowe

rozwiązanie dopuszczalne.

W tym celu moŜna zastosować jedną z metod:

• kąta północno-zachodniego,

• aproksymacji Vogel’a,

• minimalnego elementu macierzy kosztów.

Na podstawie pierwszego rozwiązania bazowego wyznaczane jest rozwiązanie

optymalne.

Najczęściej stosowaną metodą jest metoda MODI (Modified Distribution Methode).

•

Metoda kąta północno-zachodniego (kąta N-W)

Poszukiwanie rozwiązania bazowego rozpoczynamy od wartości xij dla trasy (1,1).

Wartość xij wyznaczamy wg wzoru:

xij=min{a1, b1}

Następnie od wartości a1, b1 odejmujemy x11 i otrzymane wyniki wstawiamy odpowiednio zamiast a1, b1. Z dalszych rozwaŜań eliminujemy wiersz lub kolumnę, dla której róŜnica wynosi 0. W kolejnym kroku przechodzimy do elementu xij połoŜonego w północno-zachodnim rogu, powstałej po eliminacji wiersza lub kolumny, macierzy i powtarzamy poprzednie czynności. Wyznaczanie rozwiązania kończymy po wyeliminowaniu wszystkich wierszy i kolumn.

• Metoda aproksymacyjna Vogel’a (metoda VAM)

Wybierając zmienną xij do wyznaczenia sprawdzamy róŜnicę pomiędzy najniŜszym a kolejnym co do wartości kosztem w kaŜdej kolumnie lub wierszu i tam gdzie jest ona największa określamy najniŜszy koszt, a dla jego współrzędnych określamy wartość zmiennej

xij.

Dla wybranego wiersza lub kolumny określamy:

xij=min{ai,bj}

Następnie, podobnie jak w przypadku metody kąta północno-zachodniego, od

wartości ai, bj odejmujemy xij i otrzymane róŜnice wstawiamy odpowiednio zamiast ai, bj. Z

dalszych rozwaŜań eliminujemy wiersz lub kolumnę, dla której róŜnica wynosi 0. Dla pozostałych wierszy i kolumn ponownie wybieramy zmienną xij i powtarzamy operacje.

Iteracje kończymy w momencie, gdy w macierzy nie ma juŜ wierszy ani kolumn

zawierających co najmniej dwa puste pola. W polu nie posiadającym przypisanej wartości przewozu wpisujemy pozostałą wartość dostawcy dla odpowiedniego wiersza lub odbiorcy dla kolumny.

•

Metoda minimalnego elementu macierzy kosztów (MEM)

Z macierzy kosztów wybieramy element o najmniejszej wartości i dla jego

współrzędnych określamy wartość xij.

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

Tak jak w przypadku poprzednich metod, z dalszych rozwaŜań eliminujemy wiersz

lub kolumnę, dla której róŜnica pomiędzy wartością odpowiednio ai lub bj a xij wynosi 0.

Następnie dokonujemy kolejnego wyboru współrzędnych zmiennej xij według kryterium najmniejszego kosztu. Iteracje powtarzamy aŜ do momentu, gdy nie ma juŜ Ŝadnych wierszy ani kolumn zawierających co najmniej dwa pola bez przypisanych wartości przewozów. W polu nie posiadającym przypisanej wartości wpisujemy pozostałą dla danego wiersza i kolumny wartość. Po znalezieniu jednego z rozwiązań dopuszczalnych

przechodzimy do etapu sprawdzania jego optymalności.

3. PRZYKŁAD

Trzech dostawców: D1, D2, D3

zaopatruje w odpady 4 spalarnie: S1, S2, S3 i S4.

Dane:

- jednostkowe koszty transportu (w zł za tonę);

- oferowane miesięcznie wielkości dostaw Ai (w tonach),

- miesięczne zapotrzebowanie spalarni Bj (w tonach)

podano w tablicy 1.

Tab. 1. Jednostkowe koszty transportu

SPALARNIE

Dostawcy

B j

200

Opracować plan przewozu odpadów do utylizacji:

od dostawców do spalarni, minimalizujący całkowite koszty transportu.

Rozwiązanie:

bilans podaŜy i popytu:

∑ A = ∑ B

= 200 t ,

i = 1

j = 1

a więc jest to przykład zamkniętego zagadnienia transportowego (ZZT).

Zmienne decyzyjne xij oznaczają ilość ton odpadów, jaka powinna być dostarczona od i-tego

dostawcy (i=1,2,3) do j-tej spalarni (j=1,2,3,4):

jest ich 3 * 4 = 12.

E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe

WyraŜają to warunki:

a) dla dostawców

x 11 + x 12 + x 13 + x 14 = ∑ x

= 70

1 j

i = 1

tzn: suma wielkości dostaw odpadów od dostawcy D1 do wszystkich spalarni powinna być równa podaŜy dostawcy; i analogicznie dla dostawców dla dostawców D2, D3:

x 21 + x 22 + x 23 + x 24 = ∑ x

= 50

2 j

i = 1

x 31 + x 32 + x 33 + x 34 = ∑ x

= 80

3 j

i = 1

b) dla odbiorców:

+ x

= ∑ x i = 40

i = 1

tzn . suma dostaw odpadów otrzymanych przez spalarnię S 1 od wszystkich trzech dostawców powinna być równa całkowitemu jej zapotrzebowaniu; podobnie dla pozostałych odbiorców (spalarni):

+ x

= ∑ x i

= 60

i = 1

+ x

= ∑ x i = 50

i = 1

+ x

= ∑ x i = 50

i = 1

Muszą być takŜe spełnione warunki brzegowe:

≥

0 (i=1,2,3; j=1,2,3,4),

a w funkcji celu naleŜy zminimalizować łączne koszty transportu, czyli:

K(xij) = 50x11 + 40x12 + 50x13 + 20x14 +

40x21 + 80x22 + 70x23 + 30x24 +

60x31 + 40x32 + 70x33 + 80x34 min

Rozwiązanie: do wyboru jedna z metod przedstawionych w rozdziale 2 (lub inne, np.

wykorzystujące algorytmy ewolucyjne).