3582322533

Badania operacyjne: 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 At(i=l, 2...... R) jednostkami tego

towaru, zaopatruje N odbiorców. Zapotrzebowanie każdego z odbiorców wynosi Bj (j=l, 2, ..... N). Każdy

z dostawców może zaopatrywać dowolnego odbiorcę i odwrotnie - każdy odbiorca maże otrzymać towar od dowolnego dostawcy. Dodatkowo mamy podane koszty jednostkowe transportu od i-tego dostawcy do j-tego

odbiorcy C_y (i=l, 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

R    N

odbiorców    ^ y B _{f (}jeżeli:

i=i    j=i

R    N

1.    ZZT zamknięte zagadnienie transportowe,

i=l    J=i

R    N

2.    ^ Ą > y.B;    OZT otwarte zagadnienie transportowe.

>=1    ;=1

Zmienne decyzyjne x_y    ilość przewiezionego towaru od i-tego dostawcy do j-tego odbiorcy, Cy koszty

przewozu tego towaru

R N

Funkcja celu    yy.£,;*» ~ min fminimalizacja łącznych kosztów transportu od wszystkich

i=i j=i

dostawców do wszystkich odbiorców).

Warunki strukturalne:

a) dla dostawców (i-ty dostawca ma dostarczyć wszystkim odbiorcom tyle towaru, ile posiada; warunków

N

tych jest tyle, ilu jest dostawców, czyli NI y.    — A :

	*12 -*“	• +*11V
*21-*-	*22 -*”	• -*-*uv
*R1 -*“	*R2 "	• -*-*RiV

b)

dla odbiorców (j-ty odbiorca ma otrzymać od wszystkich dostawców tyle towaru, ile potrzebuje;

R

warunków tego typu jest tyle ilu odbiorców, czyli R) y = Bj:

i=l

9

1

Opracowanie teoretyczne na podstavńe: Karol Kukula (red.), Badania operacyjne w przykładach i zadaniach. Wydawnictwo Naukowe PWN, Warszawa 1996