3582328305

Zadanie transportowe

n dostawców (wiersze), m odbiorców (kolumn), jeden rodzaj towaru, dia 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)

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

b)    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)