Zadanie transportowe

n dostawców (wiersze), m odbiorców (kolumn), jeden rodzaj towaru, dla i-tego dostawcy (wiersza) dana liczba sztuk, którą może on wysłać (podaż(i)), dla j-tego odbiorcy (kolumny) dana liczba sztuk, jaką może (chce) on odebrać (popyt(j)), w macierzy dane są koszty przewozy jednostki towaru od dostawcy-wiersza do odbiorcy-kolumny.

Poszukiwane są liczby sztuk,

jakie należy przewieźć od każdego dostawcy-wiersza do każdego odbiorcy-kolumny, aby cały transport kosztował jak najmniej.

Przed rozpoczęciem poszukiwania rozwiązania należy sprawdzić, czy problem jest zbilansowany, czyli czy suma popytów = sumie podaży. Jeśli nie, problem należy najpierw zbilansować (patrz dalej).

PRZYKŁAD i: Wyjściowa tablica transportowa (tablica C):

	D	E	F
A	3	5	7	50
B	12	10	9	70
C	13	3	9	30
	20	40	90

Poszukiwana tablica transportowa (tablica X):

	D	E	F
A				50
B				70
C				30
	20	40	90	150=150

I krok: wyznaczenie dowolnego rozwiązania dopuszczalnego (musi używać n+m-1 z n*m tras)

II krok: pętla - sprawdzenie czy dane rozwiązanie jest optymalne, jeśli nie, wyznaczenie lepszego, aż sprawdzenie pokaże, iż zostało otrzymane rozwiązane optymalne.

Krok I (jedna z metod)

1. w macierzy X znaleźć kąt północno zachodni , czyli trasę w lewym górnym rogu)

2. wpisać w niej minimum z odpowiedniego popytu i podaży (w niektórych przypadkach to może być zero, traktujemy je wtedy jak każdą inną liczbę i normalnie wpisujemy)

3. sprawdzić, czy kolumna, czy wiersz są „załatwione”. Jeśli tylko kolumna jest „załatwiona”, skreślić kolumnę, jeśli tylko wiersz, skreślić wiersz, jeśli to i to, skreślić jedno z nich (dowolnie

4. uaktualnić podaże i popyty , iść do a) dopóki można.

Wynik:

Poszukiwana tablica transportowa (tablica X - krok I):

	D	E	F
A	20	30		50
B		10	60	70
C			30	30
	20	40	90

3+3-1=5

Krok II

1. dla każdej nieużywanej trasy należy wyznaczyć współczynnik optymalności:

- wyznaczyć zamkniętą krzywą, złożoną wyłącznie z odcinków poziomych i pionowych, której „rogi - zakręty” są wyłącznie w rozpatrywanej trasie nieużywanej i w trasach używanych

- ponumerować „rogi” naprzemiennie +1, -1, przy czym rozpatrywana trasa nieużywana dostaje numer +1

- dodać lub odjąć do(od) siebie wartości leżące w rogach z Tablicy C, (dodać tam gdzie +1, odjąć tam gdzie -1)

b) jeśli wszystkie współczynniki optymalności są nieujemne, dane rozwiązanie jest optymalne, jeśli nie, idź do kroku c) - wyznaczanie lepszego rozwiązania, poprzez włączenie do użytku trasy z najmniejszym współczynnikiem optymalności..

BD

	D	E	F
A	20	30		50
B		10	60	70
C			30	30
	20	40	90

	D	E	F
A	3 (-1)	5 (+1)	7	50
B	12 (+1)	10 (-1)	9	70
C	13	3	9	30
	20	40	90

12-3+5-10=4

AF

	D	E	F
A	20	30		50
B		10	60	70
C			30	30
	20	40	90

	D	E	F
A	3	5 (-1)	7 (+1)	50
B	12	10 (+1)	9 (-1)	70
C	13	3	9	30
	20	40	90

7-5+10-9=3

CD

	D	E	F
A	20	30		50
B		10	60	70
C			30	30
	20	40	90

	D	E	F
A	3 (-1)	5 (+1)	7	50
B	12	10 (-1)	9 (+1)	70
C	13 (+1)	3	9 (-1)	30
	20	40	90

13-3+5-10+9-9=5

CE

	D	E	F
A	20	30		50
B		10	60	70
C			30	30
	20	40	90

	D	E	F
A	3	5	7	50
B	12	10 (-1)	9 (+1)	70
C	13	3 (+1)	9 (-1)	30
	20	40	90

3-10+9-9=-7 - ta trasa ma ujemny współczynnik optymalności, czyli rozwiązanie nie jest optymalne, zatem trzeba je polepszyć.

Krok c): polepszenie rozwiązania poprzez włączenie do użytku trasy o najmniejszym współczynniki optymalności: dla łamanej dla tej trasy wybrać (z tabeli X) min z tych rogów, które są oznaczone „-1”, i liczbę tę (w Tabeli X) dodać (przy +1) i odjąć (przy -1) od rogów łamanej w Tabeli X. Jeśli 0 wyszło w jednym z rogów, trasa ta przestaje być używana. Jeśli 0 wyszło więcej niż w jednym rogu, dowolny wyrzucamy z użytku, pozostałe pozostają w użytku (trasy „zdegenerowane”). Używanych tras ma być m+n-1.

U nas: CE

Tabela C:

	D	E	F
A	3	5	7	50
B	12	10 (-1)	9 (+1)	70
C	13	3 (+1)	9 (-1)	30
	20	40	90

Tabela X

	D	E	F
A	20	30		50
B		10	60	70
C			30	30
	20	40	90

min (10,30)=10

	D	E	F
A	20	30		50
B		10-10=0	60+10	70
C		+10	30-10	30
	20	40	90

Nowe rozwiązanie:

	D	E	F
A	20	30		50
B			70	70
C		10	20	30
	20	40	90

Jest tańsze od poprzedniego o 70 jednostek pieniężnych (sprawdzić)

Wróć do a) Kroku II

Rozwiązanie optymalne:

	D	E	F
A	20	10	20	50
B			70	70
C		30		30
	20	40	90

Inny przykład (degeneracja):

PRZYKŁAD ii: Wyjściowa tablica transportowa (tablica C):

	D	E	F
A	7	4	4	10
B	3	6	1	20
C	2	3	5	30
	10	20	30

************************* algorytm

Rozwiązanie optymalne:

	D	E	F
A			10	10
B			20	20
C	10	20	0	30
	10	20	30

Niezbilansowanie:

PRZYKŁAD iii: Wyjściowa tablica transportowa (tablica C):

	D	E
A	3	5	50
B	12	10	70
	30	40	70<120

Należy zbilansować:

	D	E	Fikcyjny
A	3	5	0	50
B	12	10	0	70
	30	40	50

To, co w rozwiązaniu będzie wysyłane do Fikcyjnego, w ogóle nie będzie wysyłane.

PRZYKŁAD iIV: Wyjściowa tablica transportowa (tablica C):

	D	E
A	3	5	20
B	12	10	70
	80	40	120>90

	D	E
A	3	5	20
B	12	10	70
Fikcyjny	0	0	30
	80	40

To, co w rozwiązaniu będzie wysyłane od Fikcyjnego, w ogóle nie będzie wysyłane.

---