Badania operacyjne : p roblemy 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 tra nsportowego: 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: ZZT zamknięte zagadnienie transportowe, 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 : 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, 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, brzegowe: OZT można sprowadzić do ZZT poprzez:
(…)
…, 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: C1 C2 C3 cztery spółdzielnie mieszkaniowe budujące domy: SM1 SM2 SM3 SM4…
… 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…
... zobacz całą notatkę
Komentarze użytkowników (0)