PROBLEMY TRANSPORTOWE I PRZYDZIAŁU

Zagadnienie transportowe zostało po raz pierwszy sformułowane przez F. L. Hitchcocka w r. 1941, jako sposób zaplanowania przewozu jednorodnego produktu od określonej liczby dostawców do określonej liczby odbiorców. Zagadnienie transportowe jest szczególnym przypadkiem programowania liniowego - można je rozwiązać za pomocą metody simpleks. Jednak dzięki charakterystycznej strukturze warunków ograniczających, w zagadnieniu transportowym opracowano metody pozwalające otrzymać rozwiązanie w sposób bardziej efektywny.

Opracowany w roku 1951 przez G.B. Dantziga schemat metody rozwiązania zagadnienia transportowego nazywany algorytmem transportowym, pozostał w użyciu do dziś.

Charakterystyka zagadnienia transportowego:

R dostawców pewnego jednorodnego towaru, z których każdy dysponuje A_i (i=1, 2, ...., R) jednostkami tego towaru, zaopatruje N odbiorców. Zapotrzebowanie każdego z odbiorców wynosi B_j (j=1, 2, ...., N). Każdy z dostawców może zaopatrywać dowolnego odbiorcę i odwrotnie - każdy odbiorca może otrzymać towar od dowolnego dostawcy. Dodatkowo mamy podane koszty jednostkowe transportu od i-tego dostawcy do j-tego odbiorcy C_ij (i=1, 2, ..., R j=1, 2, ..., N). Zamiast kosztów transportu mogą być podane odległości lub czas transportu (zwłaszcza w przypadku towarów szybko psujących się). Wówczas mówimy o zagadnieniach transportowych z kryterium kosztów, odległości lub czasu.

Należy opracować plan przewozu towaru między dostawcami, a odbiorcami tak, aby łączne koszty transportu były możliwie najniższe. Plan taki ma określić, ile towaru powinien dostarczyć i-ty dostawca j-temu odbiorcy.

Zakłada się, że całkowita łączna podaż dostawców powinna być nie mniejsza niż łączne zapotrzebowanie odbiorców:
, jeżeli:

1. 
   ZZT zamknięte zagadnienie transportowe,

2. 
   OZT otwarte zagadnienie transportowe.

Zmienne decyzyjne x_ij ilość przewiezionego towaru od i-tego dostawcy do j-tego odbiorcy, C_ij koszty przewozu tego towaru.

Funkcja celu
(minimalizacja łącznych kosztów transportu od wszystkich dostawców do wszystkich odbiorców).

Warunki strukturalne:

1. dla dostawców (i-ty dostawca ma dostarczyć wszystkim odbiorcom tyle towaru, ile posiada; warunków tych jest tyle, ilu jest dostawców, czyli N)
   :

sumuję po wierszach,

2. dla odbiorców (j-ty odbiorca ma otrzymać od wszystkich dostawców tyle towaru, ile potrzebuje; warunków tego typu jest tyle ilu odbiorców, czyli R)
   :

sumuje po kolumnach,

3. brzegowe:

OZT można sprowadzić do ZZT poprzez:

a) wprowadzenie fikcyjnego N+1 odbiorcy, którego zapotrzebowanie
jest równe nadwyżce podaży nad popytem:
;

b) wprowadzenie fikcyjnego R+1 dostawcy, dysponującego podażą
, która jest równa nadwyżce popytu nad podażą:
;

W rzeczywistości najczęściej zakłada się, że nadwyżka towaru pozostanie w magazynach dostawców.

Mogą być dodatkowo podane jednostkowe koszty magazynowania u poszczególnych dostawców (
) lub też zakłada się, że koszty magazynowania są pomijalnie małe w porównaniu z kosztami transportu (tj.
). W funkcji celu minimalizuje się łączne koszty transportu i magazynowania.

Metody stosowane do rozwiązania:

1. Kąta północno zachodniego.

Polega na wypełnieniu macierzy przewozów, rozpoczynając od lewego górnego pola (stąd nazwa). Wpisujemy w nią mniejszą z wartości A_i lub B_j odpowiadającej tej kratce. Następnie przesuwamy się w prawo, gdy towar od pierwszego dostawcy nie został w pełni rozdysponowany, lub w dół, gdy cała podaż tego dostawcy została rozdzielona odbiorcom.

2. Minimalnego elementu.

Polega na rozmieszczeniu przewozów przede wszystkim na tych trasach, gdzie koszty są jak najmniejsze. Przekształcamy macierz tak aby w każdym wierszu i kolumnie było przynajmniej jedno zero. Odejmujemy od elementów poszczególnych wierszy macierzy kosztów najmniejszy element znajdujący się w danym wierszu, a następnie od poszczególnych kolumn otrzymanej macierzy odejmujemy element najmniejszy w danej kolumnie. W klatki zerowe rozdysponowujemy towar.

3. Aproksymacji Vogla (VAM):

W każdym wierszu/kolumnie szukamy najmniejszego elementu. Odejmujemy go od kolejnego najmniejszego elementu w każdym wierszu/kolumnie Spośród nich wybieramy wartość maksymalną, która wskazuje, gdzie należy przesunąć środki.

Charakterystyka zagadnienia przydziału:

Istnieje możliwość obsadzenia N stanowisk roboczych przez N osób. Znane są efekty pracy i-tego pracownika na j-tym stanowisku. Efekty te mogą być oceniane pozytywnie (wydajność, wartość produkcji na jednostkę czasu) lub negatywnie (liczba braków, czas wykonywania pracy, koszty pracy). Efekty dane są macierzą

Należy przydzielić pracowników do poszczególnych stanowisk tak, aby zmaksymalizować pozytywne lub zminimalizować negatywne efekty pracy całego zespołu.

Zakłada się, że każde stanowisko może być obsadzone przez jednego pracownika (tym samym każdy pracownik może pracować na jednym stanowisku).

Rozwiązaniem problemu jest kwadratowa macierz permutacji

, przy czym:

1, gdy i-ty pracownik zostanie przydzielony na j-te stanowisko,

= 0 w pozostałych przypadkach.

Zdefiniowana jw. macierz X nazywana jest macierzą przydziału.

Liniowy zapis zagadnienia przydziału:

- każde stanowisko może być obsadzone przez jednego pracownika,

- każdy pracownik może zostać przydzielony do jednego stanowiska.

lub
,
.

Rozwiązanie optymalne można uzyskać za pomocą algorytmu węgierskiego:

1. Przekształcić macierz współczynników funkcji celu
   tak, aby w każdym wierszu i w każdej kolumnie występowało co najmniej jedno zero.

2. W przekształconej macierzy współczynników funkcji celu skreślić wiersze i kolumny zawierające zera za pomocą możliwie najmniejszej liczby linii (poziomych i pionowych). Jeżeli liczba linii potrzebnych do skreślenia wszystkich zer jest równa wymiarowi macierzy czyli N, można wyznaczać rozwiązanie optymalne - przejść do punktu 3. Jeżeli liczba ta jest mniejsza od N - przejść do punktu 4.

3. Ustalić rozwiązanie optymalne, polegające na takiej konstrukcji macierzy
   , aby jedynki znalazły się tylko w tych klatkach, w których w przekształconej macierzy współczynników funkcji celu występują zera (w każdym wierszu i w każdej kolumnie może wystąpić tylko jedna jedynka).

4. Jeżeli liczba linii pokrywających zera jest mniejsza od wymiaru macierzy (N), w przekształconej macierzy należy znaleźć najmniejszy nie skreślony element a następnie:

1. odjąć go od elementów nie skreślonych,

2. dodać do elementów podwójnie skreślonych.

Elementy skreślone jedną linią pozostają bez zmian.

Następnie wrócić do punktu 2 i powtórzyć procedurę aż do uzyskania rozwiązania optymalnego.

UWAGI:

1. Metoda powyższa ma zastosowanie tylko do problemów minimalizacji. Aby rozwiązać problem maksymalizacji, należy macierz współczynników funkcji celu przekształcić tak, aby jej elementy miały przeciwne znaczenie, np. odejmując od największego elementu wszystkie pozostałe.

2. Powyższy algorytm zakłada, że liczba stanowisk do obsady jest równa liczbie pracowników, czyli że macierz A jest kwadratowa. W przypadku gdy tak nie jest - należy dopisać dodatkowy wiersz lub kolumnę (fikcyjnego wykonawcę lub fikcyjne zadanie), których elementy
   .

3. Czasem zdarza się, ze pewne przydziały są niedopuszczalne (tzn. określone elementy macierzy X z założenia są równe 0). Wówczas do macierzy współczynników funkcji celu w klatkach gdzie musi być spełniony warunek
   , wprowadza się bardzo dużą liczbę, np. M - taką, że odjęcie od niej jakiejkolwiek liczby praktycznie nie zmieni jej wartości.

Twierdzenie.

Jeżeli uda się rozdysponować wszystkie środki, odbiorcy otrzymają tyle ile wynosiło ich zapotrzebowanie, a dostawcy oddadzą cały towar, to takie rozwiązanie dopuszczalne jest zarazem rozwiązaniem optymalnym.

Zadanie 1

Trzy magazyny M₁ M₂ M₃ zaopatrują w mąkę cztery piekarnie P₁ P₂ P₃ P₄. Jednostkowe koszty transportu (w złotych za tonę), oferowane miesięczne wielkości dostaw A_i (w tonach) oraz miesięczne zapotrzebowanie piekarń B_j (w tonach) podano w tablicy:

Magazyny	Piekarnie				Ai
		P1	P2	P3		P4
M1	50	40	50	20	70
M2	40	80	70	30	50
M3	60	40	70	80	80
Bj	40	60	50	50

• Zbuduj model matematyczny i rozwiąż go korzystając z metod: kąta północno-zachodniego, minimalnego elementu, Vogla.

• Na skutek podpisania intratnych umów wiążących, podaż magazynu 1 zwiększyła się o 30 ton. Pozostałe dane nie ulegają zmianie. Podaj plan przewozu mąki i magazynowania nadwyżki mąki minimalizując łączne koszty transportu i magazynowania, które wynoszą odpowiednio: 5zł, 5zł i 6zł za tonę.

Zadanie 2

Trzy fermy drobiu mają odstawić do trzech punktów skupu drób w ilościach I ferma - 100 ton, II ferma - 250 ton, III ferma - 50 ton. Punkty skupu mogą przyjąć drób w ilościach A - 150 ton, B - 100 ton, C - 150 ton. Jednostkowe koszty dostarczenia (w złotych za tonę) drób z ferm do punktów skupu podano w tablicy:

Fermy	Punkty skupu
		A	B	C
I	50	100	100
II	150	200	50
III	20	100	20

Zbuduj model matematyczny zagadnienia. Wyznacz wielkość dostaw z poszczególnych ferm do punktów skupu, tak, aby łączny koszt transportu był minimalny. Podaj wielkość minimalnego kosztu.

Rozwiązanie:
, F(x*)=33500, i=1, 2, 3. j=1, 2, 3.

Zadanie 3

Trzy gospodarstwa ogrodnicze G₁ G₂ G₃ zaopatrują w morele cztery przetwórnie owocowe P₁ P₂ P₃ P₄. Poszczególne gospodarstwa mogą dostarczyć dziennie odpowiednio 1200, 800 i 1200 kg owoców, a przetwórnie określiły swoje dzienne zdolności przetwórcze (a tym samym zapotrzebowanie) na 700, 700, 1000 i 800 kg. Opracuj plan transportu moreli, który umożliwi przewóz owoców w możliwe jak najkrótszym czasie. Czas przejazdu między dostawcami a odbiorcami (w godzinach) podaje tablica:

Gospodarstwa	Przetwórnie
		P1	P2	P3	P4
G1	6	1	3	3
G2	4	3	5	2
G3	3	2	4	5

Rozwiązanie:
, F(x)=7900

i=1, 2, 3 j= 1, 2, 3, 4.

Zadanie 4

Betonbud zaopatruje w beton pochodzący z trzech cementowni: C₁ C₂ C₃ cztery spółdzielnie mieszkaniowe budujące domy: SM₁ SM₂ SM₃ SM₄. Cementownie mogą dostarczyć odpowiednio: 100, 50, 80 ton betonu, a poszczególne spółdzielnie zgłosiły zapotrzebowanie na: 40, 70, 30 i 50 ton betonu. Koszty transportu 1 tony betonu pomiędzy dostawcami i odbiorcami podaje tablica:

Cementownie	Spółdzielnie
		SM1	SM2	SM3	SM4
C1	900	1400	1500	1300
C2	700	1500	800	300
C3	500	300	1000	1200

Nadwyżka betonu ponad zapotrzebowanie odbiorców pozostaje w magazynie dostawców. Koszty magazynowania wynoszą odpowiednio: 200, 250 i 200 zł.

Zadanie 5

Jesteś odpowiedzialny za transakcje walutowe w banku. Zasoby walutowe banku na otwarcie dnia wynoszą (w mln): $ 10, £ 2, Euro 8, ¥ 0, CHF 6. Zapotrzebowanie na zamknięcie kształtuje się w wysokości odpowiednio $ 6, £ 3, Euro 1, ¥ 10 oraz CHF 7. Jakich transakcji powinieneś dokonać w trakcie dnia chcąc zmaksymalizować wartość zasobów walutowych na zamknięcie wyrażoną w dolarach, jeśli kursy wymiany na rynku w dniu 29 marca 2006 roku kształtowały się następująco (w stosunku do złotówki): 1 $=3,3008, 1 £=5,7345 1 Euro=3,9617, 100 ¥=2,7997 oraz 1 CHF=2,5182. Dla uproszczenia przyjmij, że kurs kupna jest równy kursowi sprzedaży, a dokonując transakcji nie płacisz prowizji. Czy Twoje decyzje ulegną zmianie, jeśli celem Twojego działania stanie się maksymalizacja wartości zasobów walutowych wyrażona w Euro?

Zadanie 6

Dana jest tablica K, której elementy charakteryzują koszt przewozu jednostki pewnego towaru od i-tego dostawcy do j-tego odbiorcy:

Załóż, że popyty i podaże wynoszą odpowiednio: 45, 20, 30, 30 oraz 35, 50 i 40 jednostek. Sformułuj zagadnienie programowania liniowego, którego użyjesz do wyznaczenia planu przewozów minimalizującego łączny koszt przewozu oraz odpowiadające mu zagadnienie dualne. Rozwiąż problem stosując metodę kąta północno-zachodniego (minimalnego kosztu). Wyznacz macierz przewozów minimalizującą łączny koszt przewozu oraz minimalny koszt przewozu.

Zadanie 7

Operatorka przedsiębiorstwa taksówkowego odebrała trzy wezwania od pasażerów. Dysponuje pięcioma wolnymi taksówkami. Czas dojazdu poszczególnych taksówek do pasażerów (w minutach) przedstawiono w tabeli:

Taksówka	Pasażer
		P1	P2	P3
T1	10	11	18
T2	6	7	7
T3	7	8	5
T4	5	6	4
T5	9	4	7

Pomóż operatorce skierować wozy do klientów w taki sposób, aby zminimalizować łączny czas dojazdu.

Zadania 8

Przedsiębiorstwo ,,Czyścioch'' zatrudnia 5 studentów do sprzątania. Posprzątanie Twojego domu polega na odkurzaniu elektroluksem, czyszczeniu kuchni, czyszczeniu łazienki oraz trzepaniu dywanów. Czas wykonania poszczególnych czynności (w godzinach) przez każdego studentka podano w tablicy:

Student	Czynności
		odkurzanie	czyszczenie		trzepanie dywanów
				kuchni		łazienki
S1	6	5	2	1
S2	9	8	7	3
S3	8	5	9	4
S4	7	7	8	3
S5	5	5	6	4

Pomóż kierownikowi przedsiębiorstwa przydzielić poszczególne prace studentom w taki sposób, aby sprzątanie zajęło im jak najmniej czasu. Pamiętaj, że każdy student może wykonać tylko jedną czynność. Sformułuj odpowiednie zagadnienie programowania liniowego.

Zadanie 9

Dwie bazy transportowe (I i II) wysyłają samochody marki TIR do czterech dystrybutorów: D₁ D₂ D₃ D₄. Przejazdy między bazami a dystrybutorami są traktowane jako puste przebiegi. Zaproponuj rozdział samochodów pomiędzy dystrybutorów, minimalizujące puste przebiegi. W tabeli podano odległości między bazami a dystrybutorami, liczbę samochodów, którymi dysponują bazy transportowe A_i, oraz zapotrzebowanie dystrybutorów B_j.

Bazy	Dystrybutorzy				Ai
		D1	D2	D3		D4
I II	15 5	12 18	10 24	17 7	100 150
Bj	40	65	45	60

Zadanie 10

Przedsiębiorstwo zrzesza pięć zakładów, z których każdy może z różną wydajnością produkować pięć wyrobów. W tablicy podano wydajność zakładów (w szt./godz.) przy produkcji poszczególnych wyrobów:

Zakłady	Wyroby
		1	2	3	4	5
A	4	3	7	12	3
B	2	-	8	1	9
C	6	4	8	-	6
D	-	2	4	5	6
E	7	9	3	2	-

Zadanie 11

Przedsiębiorstwo transportowe dysponuje pięcioma samochodami, które dostarczają towar do pięciu miast. Do każdego z miast dostarczany jest inny towar i w zależności od jego masy różne jest zużycie paliwa przez samochody. W tablicy podano zużycie paliwa w zależności od towaru i odległości pokonywanej przez samochody:

Samochody	Zużycie paliwa (w l/trasę)
		T1	T2	T3	T4	T5
S1	35	45	45	50	40
S2	38	45	42	52	43
S3	34	48	42	53	38
S4	41	42	46	55	41
S5	36	44	40	57	40

Dokonać przydziału samochodów na poszczególne trasy tak, aby zużycie paliwa było jak najmniejsze.

Zadanie 12

Przedsiębiorstwo zrzesza pięć zakładów, z których każdy może z niejednakową wydajnością produkować pięć wyrobów. W tablicy podano wydajności zakładów przy wytwarzaniu poszczególnych wyrobów (w setkach szt./godz.):

Zakłady	Wyroby
		1	2	3	4	5
I	4	3	7	12	3
II	2	5	8	1	9
III	6	4	8	8	6
IV	3	2	4	5	6
V	7	9	3	2	5

Biorąc pod uwagę konieczność specjalizacji każdego zakładu w produkcji jednego tylko wyrobu, przydzielić produkcję wyrobów poszczególnym zakładom tak aby zmaksymalizować ich łączną wydajność.

Zadanie 13

W pewnym zakładzie są cztery obrabiarki: O₁, O₂, O₃ i O₄, na których można wykonywać trzy rodzaje czynności: 1, 2 i 3. Każdą czynność można realizować jednocześnie tylko na jednej obrabiarce i każda obrabiarka może być zajęta wykonywaniem tylko jednej czynności. W tablicy podano nakłady czasu (w godz.) niezbędne do realizacji na i-tej obrabiarce j-tej czynności:

Obrabiarka	Czynność
		1	2	3
O1	24	12	18
O2	18	20	16
O3	10	8	12
O4	16	14	6

Określić najbardziej racjonalny rozdział czynności pomiędzy obrabiarki, zapewniając minimalizację łącznych nakładów czasu.

Zadanie 14

Pewna firma handlowa zamierza zatrudnić maszynistki do korespondencji w trzech jezykach: angielskim, niemieckim i włoskim. W konkursie na te stanowiska wzięły udział cztery kandydatki. W tablicy podano ilość uderzeń na minutę i-tej maszynistki w j-tym języku. Znak „x” oznacza, ze maszynistka nie zna danego języka.

Maszynistki	Język
		angielski	niemiecki	włoski
1	80	105	79
2	109	x	90
3	100	97	x
4	95	80	85

Przydzielić maszynistki do korespondencji w poszczególnych językach tak, aby zmaksymalizować efekty ich pracy.

Zadanie 15

Trzy piekarnie zlokalizowane na terenie miasta są zaopatrywane w mąkę z trzech magazynów znajdujących się na peryferiach. Zasoby mąki w magazynach wynoszą: w magazynie I - 5 ton, w magazynie II - 15 ton, w magazynie III - 6 ton. Zapotrzebowanie piekarni wynosi odpowiednio 9, 13 i 4 tony. Jednostkowe koszty dostawy mąki do piekarń podano w tabeli:

	P1	P2	P3
M1	17	10	12
M2	10	4	5
M3	3	6	3

Opracowanie teoretyczne na podstawie: Karol Kukuła (red.), Badania operacyjne w przykładach i zadaniach. Wydawnictwo Naukowe PWN, Warszawa 1996

1

Przydzielić zakłady do produkcji wyrobów w taki sposób, aby każdy zakład specjalizował się w produkcji jednego wyrobu i przydział ten był optymalny pod względem wielkości produkcji.

Wyznaczyć taki plan przewozów aby z minimalizować łączny koszt transportu mąki.

---