3179027792

Elementy Badań Operacyjnych

Model zagadnienia transportowego zamkniętego ma postać:

M N

J',J'_J^cii^xu ^{= m}'^{n _} funkcja celu

(minimalizacja łącznych kosztów transportu - od wszystkich dostawców do wszystkich odbiorców).

5>_y. = A, (i = 1,2- warunki dla dostawców

(i-ty dostawca ma dostarczyć wszystkim odbiorcom tyle towaru ile posiada; warunków tych jest tyle ilu dostawców, czyli R)

y>, = Bj (j = 1,2,..., N) - warunki dla odbiorców

(j-ty odbiorca ma otrzymać od wszystkich dostawców tyle towaru, ile potrzebuje; warunków tego typu jest N) x,j>0 (i = j= l,...,N) - warunki brzegowe

Modele zagadnień transportowych są szczególnym przypadkiem modeli liniowych, można zatem je rozwiązywać za pomocą algorytmu simpleks. Jednak specyficzna struktura warunków ograniczających w tych modelach sprawia, że mogą one być rozwiązywane za pomocą algorytmów bardziej efektywnych.

Uniwersalną metodą rozwiązywania zagadnień transportowych jest algorytm transportowy (raczej są, bo istnieje wiele alternatywnych algorytmów transportowych). Jest to procedura iteracyjna. W pierwszym kroku stosując jedną z wielu znanych metod, wyznacza się początkowe rozwiązanie dopuszczalne, które następnie poprawia się w kolejnych iteracjach, aż do momentu stwierdzenia, że dalsza poprawa (obniżka wartości funkcji celu) jest niemożliwa. Podobnie jak nie omawialiśmy algorytmu simpleks, tak nie będziemy też omawiać algorytmów transportowych, bo są procedury pracochłonną i dzisiaj realizowane bez większych problemów za pomocą gotowych pakietów komputerowych. Pokazujemy jedynie jak można wyznaczyć początkowe rozwiązanie dopuszczalne.

Algorytm transportowy zakłada, że zadanie jest zbilansowane (zamknięte). Zagadnienie otwarte (OZT) można sprowadzić do zamkniętego (ZZT) przez wprowadzenie fikcyjnego Af+l-szego odbiorcy, którego zapotrzebowanie B^+i jest równe nadwyżce podaży nad popytem, tzn. B_N+l = y',Ą B, . W rzeczywistości fikcyjnym odbiorcą jest najczęściej magazyn znajdujący się u dostawców, tzn. zakłada się że nadwyżka towaru pozostanie w magazynach dostawców. Mogą być podane dodatkowo jednostkowe koszty magazynowania u poszczególnych dostawców (Cj,Ar+i) lub też zakłada się, że koszty magazynowania są pomijalnie małe w porównaniu z kosztami transportu (tzn. c,jv+i = 0) . W funkcji celu minimalizuje się łączne koszty transportu i magazynowania.

Poniżej po lewej stronie przedstawiono ogólny model zagadnienia otwartego, po stronie prawej zagadnienie otwarte jest sprowadzone do zamkniętego.

Antoni Goryl, Anna Walkosz: Programowanie liniowe strona 19