To tylko jedna z 6 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
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)
w macierzy X znaleźć kąt północno zachodni , czyli trasę w lewym górnym rogu)
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)
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
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
... zobacz całą notatkę
Komentarze użytkowników (0)