Badania operacyjne

Prowadzący ćwiczenia

mgr inż. Piotr Betlej

Zagadnienie transportowe

Proces transportowy dotyczy najczęściej przemieszczania ładunków z miejsc ich nadania do miejsc odbioru. W aglomeracjach miejskich takim procesem jest na przykład dostawa towarów z hurtowni lub zakładów wytwór­czych do sieci sklepów, a w przemyśle dostawa materiałów, półproduktów i elementów z fabryk do innych przedsiębiorstw. Proces ten jest realizowany przez ustalony system transportowy przy użyciu wybranych typów środków transportowych, jak na przykład samochodów, wagonów kolejowych, samolo­tów itp. Przy realizacji procesu transportowego przez ustalony system trans­portowy pojawia się szereg zagadnień decyzyjnych, których efektywne rozwiązanie ma istotny wpływ na ekonomikę i sprawność działania całego procesu.

Decyzyjne problemy transportowe dzielimy na:

• Klasyczne zagadnienie transportowe (KZT), w którym szuka się sposobu
  możliwie jak najtańszego rozwiezienia towaru od dostawców do odbiorców (np. towarów masowych, cementu, rur itp.).

• Wieloetapowe zagadnienie transportowe (WZT), w którym oprócz dostawców i odbiorców istnieją jeszcze punkty pośrednie.

Klasyczne zagadnienie transportowe można zapisać następująco:

funkcja celu (najczęściej minimalizacja kosztów transportu)

ograniczenia dla dostawców:

, dla i = 1, 2, …, m

ograniczenia dla odbiorców:

, dla j = 1, 2, …, n

warunki nieujemności:

gdzie:

m - liczba dostawców,

n - liczba odbiorców,

- jednostkowy koszt transportu od i - tego dostawcy do j - tego odbiorcy,

- zmienna decyzyjna, określająca ile towaru należy przetransportować od i - tego dostawcy do j - tego odbiorcy,

- łączna ilość towaru u i - tego dostawcy (wielkość podaży towaru),

- łączne zapotrzebowanie na towar u j - tego odbiorcy (wielkość popytu towaru).

Wieloetapowe zagadnienie transportowe można zapisać podobnie jak klasyczne zagadnienie transportowe z tym, że do tego drugiego należy dodać ograniczenia dla punktów pośrednich, mówiące, że suma towaru wpływająca do danego punktu i wypływająca z niego równa się zeru. Istnieją jeszcze inne modele transportowe, umożliwiające wyznaczenie najkrótszych lub najtańszych - oczywiście z uwzględnieniem istniejących ograniczeń - tras rurociągów, sieci przesyłowych, dróg dojazdowych itp.

Przykład:

Dwie kopalnie, K₁ i K₂, dostarczają węgiel do czterech składów opało­wych S₁,S₂,S₃ i S₄, położonych - podobnie jak kopalnie - w różnych miejscowościach. Pierwsza kopalnia może dostarczyć D₁ = 800 t węgla, dru­ga D₂ = 800 t. Możliwości przyjmowania węgla przez składy opałowe są ograniczone i wynoszą odpowiednio: S₁ = 100t, S₂ = 300t, S₃ = 500t, S₄ = 700 t. Jednostkowe koszty transportu (zł/t) podano w tabeli poniżej.

Tabela. Macierz jednostkowych kosztów transportu

Kopalnia	Skład 1	Skład 2	Skład 3	Skład 4
1 2	50 10	20 50	20 80	60 70

Opracuj plan przewozu minimalizujący łączne koszty przewozu węgla z kopalń do składów.

Rozwiązanie

Ponieważ jest to przykład zagadnienia transportowego zamkniętego (popyt równoważy podaż), nie musimy wprowadzać dodatkowego obiektu (dodatkowego składu opałowego lub dodatkowej kopalni, gdzie zostałby przydzielony nadmiar lub niedomiar węgla).

Aby zbudować model decyzyjny, wprowadzamy zmienną decyzyjną
, która oznacza ilość ton węgla przewiezioną z i - tej kopalni do j - tego składu opałowego.

Budowa modelu:

Funkcję celu

Ograniczenia podaży dla dostawców:

(dla kopalni 1)

(dla kopalni 2)

Ograniczenia popytu dla odbiorców:

(dla składu 1)

(dla składu 2)

(dla składu 3)

(dla składu 4)

Warunki nieujemności:

Do rozwiązanie tego problemu wykorzystamy Metodę minimalnego elementu macierzy (metoda klatek zerowych). Polega on na rozmieszczaniu przewozów przede wszystkim na tych trasach, na których koszty jednostkowe są najniższe. W tym celu przekształca się macierz kosztów do takiej postaci, aby w każdym wierszu i w każdej kolumnie występowało co najmniej jedno zero. Uzyskuje się to odejmując najmniejszy element znajdu­jący się w danym wierszu od wszystkich elementów tego wiersza macierzy, a następnie odejmując - od poszczególnych kolumn otrzymanej w ten sposób macierzy - element najmniejszy znajdujący się w danej kolumnie.

Mając tak przekształconą macierz kosztów, staramy się rozmieścić wszyst­kie przewozy w klatkach zerowych. Rozdysponowanie zaczynamy od wiersza lub kolumny zjedna tylko klatką zerową.

Jeżeli uda się rozmieścić wszystkie prze­wozy wyłącznie w klatkach, w których występują zera, to otrzymane rozwią­zanie jest optymalnym planem przewozów. Jeżeli nie, to otrzymane rozwiąza­nie jest rozwiązaniem dopuszczalnym, ale nie rozwiązaniem optymalnym.

Tabela. Macierz jednostkowych kosztów transportu

Kopalnia	Skład 1	Skład 2	Skład 3	Skład 4
1 2	50 10	20 50	20 80	60 70

Wracając do naszego przykładu odejmując w powyższej tabeli najmniejsze ele­menty poszczególnych wierszy od pozostałych elementów tych wierszy otrzy­mujemy następującą tabelę:

Tabela. Przekształcenie macierzy kosztów

Kopalnia	Skład 1	Skład 2	Skład 3	Skład 4
1 2	30 0	0 40	0 70	40 60

Ponieważ jeszcze nie we wszystkich kolumnach występują zera, również od poszczególnych kolumn odejmujemy ich najmniejsze elementy. Rezultatem jest następująca tabela:

Tabela. Przekształcenie macierzy kosztów

Kopalnia	Skład 1	Skład 2	Skład 3	Skład 4
1 2	30 0	0 40	0 70	0 20	800
	100	300	500	700	800

Rozdysponowanie rozpoczynamy od którejś z klatek zerowych z jednoznaczną decyzją, np. od klatki (K2, S1), gdzie możemy wpisać tylko przewóz 100, bowiem tyle wynosi wartość S₂. Przechodząc do drugiej kolumny, do klatki (K1, S2) wpisujemy 300, następnie w klatce (K1, S3) liczbę 500 i w ten sposób mamy już rozdzieloną całą podaż kopalni 1. Pozostałe 700 ton wpisujemy do klatki (K2, S4). W tym momencie kończą się możliwości metody klatek zero­wych, która rzadko prowadzi do rozwiązania optymalnego. Metodę tę udoskonalono przez wprowadzenie algorytmu Forda-Fulkersona. W rozważanym przykładzie metoda ta wystarcza jednak dla uzyskania optymalnego rozwiąza­nia. Rozwiązanie to przedstawiono w poniższej tabeli.

Tabela. Optymalne rozwiązanie problemu transportowego

Kopalnia	Skład 1	Skład 2	Skład 3	Skład 4
1 2	100	300	500	700	800
	100	300	500	700	800

Po wymnożeniu przewozów na poszczególnych trasach z kosztami tych przewozów otrzymujemy koszt całkowity przewozu. Wynosi on 66000 zł.

Pozostałe zadania

Zadanie 1

Firma lotnicza Rajski Lot posiada cztery lotniska w różnych rejonach kraju, które musi zaopatrywać w paliwo z trzech firm zajmujących się dystrybucją produktów naftowych. Ponieważ koszty transportu benzyny lotniczej są znaczne, a odległości między poszczególnymi miejscowościami duże, postanowiono zastosować model optymalizacji kosztów transportu z wykorzystaniem badań operacyjnych. Jednostkowe koszty transportu paliwa, zapotrzebowanie poszczególnych lotnisk oraz możliwości firm naftowych przedstawiają się następująco:

Lotnisko	Zapotrzebowanie na paliwo (tony)	Jednostkowy koszt transportu (zł za tonę)
				Firma naftowa 1	Firma naftowa 2	Firma naftowa 3
1 2 3 4	110000 220000 333000 440000	10 10 9 11	7 11 12 13	8 14 4 9
Ograniczenia podaży (tony)		275000	550000	660000

Zaproponuj optymalny transport paliwa z firm naftowych na lotniska tak, aby łączne koszty transportu były możliwie jak najmniejsze.

Zadanie 2

Firma produkcyjno-handlowa Królikowski i Spółka planuje dystrybucję swoich towarów do czterech miast, daleko od siebie położonych. Firma posiada trzy zakłady produkcyjne w różnych rejonach kraju. Ponieważ koszty transportu są znaczne, dyrektor firmy postanowił je zminimalizować. W tym celu jego asystenci otrzymali polecenie opracowania optymalnego planu przewozów. Ilość towarów do wysyłki z poszczególnych zakładów, koszty transportu oraz zapotrzebowanie odbiorców w hurtowniach w różnych miastach przedstawiają się następująco:

Zakład	Jednostkowy koszt transportu (zł za sztukę)				Podaż towaru (sztuki)
		Odbiorca 1	Odbiorca 2	Odbiorca 3		Odbiorca 4
1 2 3	30 30 20	10 25 25	25 50 10	15 15 15	50 80 150
Zapotrzebowanie (sztuki)	40	50	50	80

Będąc asystentem dyrektora zaproponuj optymalny plan transportu towaru. Podaj minimalny koszt dystrybucji towaru.

Badania operacyjne mgr inż. Piotr Betlej

Strona 5/6

---