PANSTWOWA WYŻSZA SZKOŁA ZAWODOWA W NOWYM SĄCZU

INSTYTUT TECHNICZNY

Teoria podejmowania decyzji

Projekt 2 :

Temat: Zagadnienia transportowe

Wykonał:

Henryk Zelek MPS-2(s)

1. Wprowadzenie do zagadnień transportowych

Zagadnienie transportowe jest na ogół przedstawiane jako problem opracowania

optymalnego planu (wyboru) tras przewozu produktów z różnych źródeł zaopatrzenia

do punktów odbioru, które zgłaszają zapotrzebowanie na ten produkt.

Przy z góry określonych liczbach źródeł zaopatrzenia (dostawców) i punktów

odbioru (odbiorców) oraz znanych wielkościach podaży oferowanej przez dostawców

i popytu zgłaszanego przez odbiorców oraz znanych kosztach jednostkowych

transportu między dostawcami i odbiorcami należy znaleźć taki plan przewozów,

który minimalizuje łączne koszty transportu.

Tak sformułowane zadanie transportowe można zapisać w formie modelu

liniowego, który da się rozwiązać metodą simpleks, lecz rozwiązanie takie nie byłoby

zbyt wygodne. Zarówno cechy charakterystyczne zagadnień transportowych, jak

i teoria dualności pozwalają na przyjęcie wygodniejszej metody optymalizacji

problemów transportowych – zwanej metodą potencjałów. Metoda ta, w porównaniu

do algorytmu simpleks, pozwala na znaczne skrócenie i uproszczenie obliczeń. Ma

również charakter iteracyjny i czynności obliczeniowe sprowadzają się do podobnych

kroków jak w metodzie simpleks. Na początku musimy znaleźć dopuszczalne

rozwiązanie bazowe, sprawdzić jego optymalność, a następnie utworzyć schemat

poprawy rozwiązania poprzez wprowadzenie do bazy nowej zmiennej bazowej

w miejsce usuwanej z bazy innej.

Aby rozpocząć obliczenia za pomocą metody potencjałów, musimy najpierw

doprowadzić postać sformułowanego problemu transportowego do pierwszej

dopuszczalnej postaci bazowej. Można to uzyskać kilkoma metodami. Najprostsza

z nich to metoda kąta północno-zachodniego, która nie posiada żadnych cech metody

optymalizacyjnej, gdyż w swojej istocie nie odnosi się do znanych jednostkowych

kosztów transportu. Dlatego też uzyskane tą metodą rozwiązania zazwyczaj dalekie

są od optymalnych i wymagają większej liczby iteracji przy poszukiwaniu rozwiązania

końcowego.

Metody, które wykorzystują informacje o jednostkowych kosztach transportu

na poszczególnych trasach to: metoda minimalnego elementu macierzy kosztów

oraz metoda VAM (Vogel’s Approximati)

1. Etapy rozwiązywania zagadania transportowego

Rozwiązanie zagadnienia transportowego odbywa się w trzech etapach:

1. Wyznaczenie pierwszego (wstępnego) dopuszczalnego rozwiązania

bazowego, czyli planu przewozowego (transportowego). Stosuje się tutaj

jedną z trzech metod:

– metoda kąta północno-zachodniego,

– metoda minimalnego elementu macierzy kosztów,

– metoda aproksymacyjna VAM (Vogel’s Approximation Method).

2. Ocena optymalności przyjętego pierwszego planu transportowego przy

pomocy tzw. potencjałów. Jeżeli przy tym okaże się, że przyjęty wstępny

plan przewozowy jest optymalny, to rozwiązywanie zagadnienia jest

zakończone. W przypadku, gdy wyznaczony plan (rozwiązanie bazowe)

nie jest optymalny, to przystępujemy do etapu trzeciego.

3. Modyfikacja planu nieoptymalnego metodą cykli zamkniętych. Polega

ona na wyznaczeniu metodą cykli zamkniętych następnego, lepszego

planu przewozowego, pozwalającego zmniejszyć całkowity koszt transportu,

a następnie sprawdzić jego optymalność jak w kroku pierwszym.

Postępując w ten sam sposób dla kolejnych planów przewozowych, wreszcie

otrzymujemy plan optymalny, a więc rozwiązanie X zagadnienia transportowego,

minimalizujące funkcję celu.

3.

	ośrodki dystrybucyjne
	O1
zakłady wytwórcze	D1
	D2
	D3

Zacznijmy więc od budowy modelu matematycznego naszego zadania

transportowego w postaci liniowej. Celem jest minimalizacja kosztów transportu

między wszystkimi zakładami wytwórczymi a ośrodkami dystrybucji. Oznaczając

prze xij wielkość przewozu na trasie (ij) od i-tego dostawcy (zakładu wytwórczego)

do j-tego odbiorcy (ośrodka dystrybucyjnego), możemy zapisać funkcję kryterium

oraz warunki ograniczające po jednym dla każdego odbiorcy i jednym dla każdego

dostawcy.

Funkcja celu

F(x₁₁,x₁₂,x₁₃,x₁₄,x₂₁,x₂₂,x₂₃,x₂₄,x₃₁,x₃₂,x₃₃,x₃₄,)= 8x₁₁+9x₁₂+11x₁₃+11x₁₄+7x₂₁+8x₂₂+8x₂₃+9x₂₄+11x₃₁+12x₃₂+8x₃₃+13x₃₄-min

Warunki ograniczające

x₁₁+x₁₂+x₁₃+x₁₄=11

x₂₁+x₂₂+x₂₃+x₂₄=14

x₃₁+x₃₂+x₃₃+x₃₄=12

x₁₁+ x₂₁+ x₃₁=7

x₁₂+ x₂₂+ x₃₂=9

x₁₃+ x₂₃+ x₃₃=9

x₁₄+ x₂₄+ x₃₄=12

4. Metoda kąta północno-zachodniego

Obliczenia najlepiej jest wykonywać w tabeli. Konstrukcja tabeli oparta jest

na podobieństwie do tabeli zadania transportowego. Zasadniczą część tabeli stanowi macierz X.

			metoda konta północno zachodniego
	rozwiązanie początkowe	podaż
	7	4	0
	0	9	5
	0	0	4
	0	0	0

Tabela przedstawiająca pierwszy plan przewozowy, czyli pierwsze dopuszczalne

rozwiązanie bazowe, zawiera wartości w węzłach bazowych pogrubione.

Jak łatwo zauważyć, rozwiązanie to składa się z:

N = m+ n −1= 3+ 4 −1= 6

węzłów dodatnich. Możemy więc stwierdzić, że uzyskany plan przewozowy nie jest

zdegenerowany, a każdy jego wiersz i każda kolumna są oddzielnie zbilansowane.

Zmienne decyzyjne w tej postaci bazowej to zmienne:

x₁₁=7 , x₁₂=4, x₂₂=9, x₂₃=5, x₃₃=4, x₃₄=12

Obliczmy odpowiadającą temu rozwiązaniu wartość funkcji celu:

Fc =8 * 7 + 9 * 4 + 8 * 9 + 8 * 5 + 8 * 4 + 13 * 12 = 56 + 36 + 72 + 40 + 32 + 156 = 392

Znamy już rozwiązanie optymalne i wiemy, że to uzyskane metodą kąta

północno-zachodniego nie jest dalekie od optymalnego. Trudno zresztą się

spodziewać rozwiązania optymalnego, gdy nie uwzględnialiśmy w tej metodzie

macierzy kosztów C.

4. Metoda minimalnego elementu macierzy kosztów

Podobnie jak w poprzedniej metodzie, zbudujmy dla dowolnego zagadnienia

transportowego tabelkę, której centralną częścią będzie macierz wynikowa X oraz

w wyróżnionych komórkach elementy macierzy kosztów C (koszty jednostkowe

transportu na poszczególnych trasach)

		metoda minimalnego elementu macierzy kosztów
		O1	O2	O3	O4	ai
	D1	0	2	9	0	0
	D2	7	7	0	0	0
	D3	0	0	0	12	0
	bj	0	0	0	0

Podobnie jak w poprzedniej metodzie, zmienne bazowe zostały wyróżnione

pogrubioną czcionką. Zadanie, jak poprzednio, nie wykazuje cech zadania

zdegenerowanego, a kolumny i wiersze są wzajemnie zbilansowane.

Zmienne bazowe w tym rozwiązaniu to

x₂₁=7 _, x₂₂=7 , x₁₂=2, x₁₃=9, x₃₄=12

Wartość funkcji celu dla tej postaci bazowej można obliczyć następująco:

Fc= 7 * 7 + 9 * 2 + 7 * 8 + 9 * 11 + 12 * 13 = 49 + 18 + 99 + 56 + 156 = 378

Widzimy, że otrzymany koszt transportu według planu wyznaczonego

metodą najmniejszego elementu macierzy kosztów jest dużo niższy niż wyznaczony

metodą kąta północno-zachodniego. Metoda najmniejszego elementu macierzy jest

więc w tym przykładzie bardziej efektywna od poprzedniej.

4. Metoda aproksymacyjna VAM

Metoda aproksymacyjna jest nieco bardziej skomplikowana (tzn. rozbudowana)

niż poprzednie dwie metody, ale też bardziej od nich obydwu efektywna i bardzo

często wyznaczony przy jej pomocy wstępny plan przewozów jest już planem

(rozwiązaniem) optymalnym. Podobnie jak poprzednio, rozpoczynamy od skonstruowania odpowiedniej tabeli, zawierającej te same informacje co wstępne tabele w poprzednich dwóch metodach. Tabelę tę będziemy rozbudowywać, dodając do niej kolejno, w każdej iteracji, równocześnie informacyjny wiersz i kolumnę mierników ułatwiających nam podjęcie decyzji wyboru odpowiedniego węzła.

W pierwszej iteracji do tabeli dodamy dodatkowy wiersz i dodatkową

kolumnę, w których umieszczamy obliczone dla poszczególnych wierszy i kolumn

macierzy kosztów bezwzględne wartości różnicy dwóch najmniejszych elementów

odpowiadających danemu wierszowi i danej kolumnie. Spośród wszystkich

obliczonych bezwzględnych wartości różnic dla wierszy i kolumn wybieramy liczbę

największą i oznaczamy (cechujemy) je w określony sposób. Spośród węzłów

znajdujących się w linii o ocechowanej największej bezwzględnej wartości różnicy

wybiera się jako węzeł bazowy węzeł o najmniejszym koszcie jednostkowym.

W węźle tym umieszczamy wartość mniejszą, zgodnie z formułą i dokonujemy

odpowiednich korekt w wierszach lub kolumnach, zgodnie z formułami.

			metoda VAM
		O1	O2	O3	O4	ai	I	II	III
	D1	7	4	0	0	11	1	1	1
	D2	7	5	9	0	14	0	1	1
	D3	0	0	0	12	12	3
	bj	7	9	9	12
	I	1	1	0	2
	II	1	1	3
	III	1	1

Analiza tabeli wskazuje, że uzyskane rozwiązanie również nie jest

zdegenerowane, kolumny i wiersze są wzajemnie zbilansowane. Postać bazowa tego

zadania wygląda teraz następująco:

x₁₁=7 , x₁₂=4, x₂₂=5, x₂₃=9, x₃₄=12

Wartość funkcji kryterium przy tym rozwiązaniu bazowym wynosi:

Fc= 7 * 8 + 9 * 4 + 5 * 8 + 9 * 8 + 12 * 13 = 56 + 36 + 40 + 72 + 156 = 360

Jak łatwo zaobserwować, metoda VAW w tym zadaniu okazała się

najefektowniejsza, ponieważ wartość funkcji kryterium przy tym rozwiązaniu

bazowym jest najmniejsza z wszystkich trzech przedstawionych metod.