Zadanie transportowe

Zadanie transportowe

Modele zadania transportowego. Zadanie transportowe i zadania programowania liniowego.

Podstawowy plan zadania transportowego.

Metoda potencjałów.

Modele zadania transportowego.

Transportowe zadanie (TZ) mające jako kryterium koszt przewozów formułujemy w następującej postaci. Mamy m punktów A₁, A₂, A_m, w których produkuje się pewien produkt odpowiednio w ilościach a₁, a₂, a_m jednostek. Ten produkt potrzeba dostarczyć do n punktów konsumpcji B₁, B₂, B_n, zapotrzebowania których wynoszą odpowiednio b₁, b₂, b_n jednostek. Koszt dostawy z kasdego punktu produkcji A_i, (i= 1, 2, , m) do kasdego punktu konsumpcji B_j (j=1, 2, , n) jest znany i wynosi c_ij jednostek. Nalesy znaleźć plan przewozu, dla którego byłyby spełnione wszystkie zapotrzebowania, a sumowany koszt wszystkich przewozów byłby minimalny.

Mosna liczyć, se . W tym przypadku model zadania transportowego nazywa się zamkniętym.

Jeseli , to wprowadzamy dodatkowy (fikcyjny) punkt konsumpcji z konsumpcją wynoszącą jednostek. Jeśli , wtedy wprowadzamy dodatkowy (fikcyjny) punkt produkcji z wartością produkcji wynoszącą jednostek. W tym przypadku spełnić zapotrzebowania konsumentów nie uda się. W dwóch ostatnich przypadkach model zadania transportowego nazywa się otwartym.

Oznaczymy przez x_ij ilość produktu, przewiezionego z punktu A_i, (i= 1, 2, , m) do punktu konsumpcji B_j (j=1, 2, , n). Jeśli f jest kosztem przewozu to

Przy tym z punktu A_i, (i= 1, 2, , m) będzie wywiezione razem jednostek produktu, a do punktu B_j (j=1, 2, , n) będzie dostarczone jednostek produktu. Więc,

Takim czynem, zadanie transportowe jest zadaniem liniowego programowania w kanonicznej postaci:

min (6.1)

(6.2)

(6.3)

(6.4)

Relacje (6.1) - (6.4) są ekonomiczno – matematycznym modelem transportowego zadania.

Macierz nazywa się macierzą przewozów. Macierz nazywa się macierzą taryfową.

Dla większej poglądowości warunki ZT mosna zapisać w postaci tabeli (tabela. 6.1), którą nazywa się rozdzielającą. Rozdzielającą tabelę nazywa się czasami tabelkowym lub macierzowym modelem ZT.

Będziemy nazywać plan przewozu X=[x_ij] dopuszczalnym, jeseli spełnia on ograniczenia (6.2) - (6.4).

Dopuszczalny plan przewozu, dla którego funkcja celu osiąga minimum (6.1), nazywa się optymalny.

ZT posiada właściwości:

Twierdzenie o istnieniu dopuszczalnego planu. Dlatego, seby ZT miało dopuszczalne rozwiązania konieczne i dostateczne jest spełnienie równości

(6.5)

Dowód. Po zsumowaniu w rozdzielającej tabeli 6.1 elementów x_ij oddzielnie według indeksów i i j, otrzymamy:

Rzeczywiście, se zsumujemy wszystkie elementy x_ij według wierszy oraz kolumn, rósnica polega tylko w kolejności elementów. Ale wartość sumy nie jest uzalesniona od kolejności elementów. Dlatego równość jest koniecznym warunkiem rozwiązalności ZT.

Dla dowodu dostateczności warunku (6.5) pokasemy, se jeseli ten warunek jest spełniony to zawsze istnieje dopuszczalny plan. Oznaczymy = А. Zmienne x_ij zapiszemy przez dane zadania następująco:

(6.6)

Biorąc pod uwagę to, se а_i ³ i b_j ³ , mamy, se A > 0, więc i  x_ij ³ 0 (i=1,2,m; j=1,2,n).

Pokasemy, se zmienne (6.6) są dopuszczalnym planem. Ten zbiór nieujemnych wartości będzie dopuszczalnym planem, jeseli spełnia on układ ograniczeń (6.2) - (6.4). Po zsumowaniu równości (6.6) według indeksu i. otrzymamy

(6.7)

Wykorzystując to ,se j nie zalesy od indeksu i, w równości (6.7) zapiszemy ze znakiem sumy i otrzymamy

Analogicznie, sumując równości (6.6) według indeksu j, otrzymamy

Więc, zbiór liczb spełnia układ ograniczeń zadania, dlatego jest dopuszczalnym planem.

Wykorzystując twierdzenie 6.1 mamy

Wniosek. Jeseli wszystkie liczby a₁, a₂, a_m i b₁, b₂, b_n — całkowite, przy czym , to zadanie transportowe (6.1) — (6.4) ma optymalne rozwiązanie z całkowitoliczbowymi współrzędnymi.

Twierdzenie o randze macierzy. Ranga macierzy А zadania transportowego jest o jeden mniejsza od liczby równań: rank(A) = m+n-1.

Dowód. Macierz układu ograniczeń (6.2) - (6.4) ma postać:

W kasdej kolumnie macierzy А są tylko dwa elementy, równe jedynce, pozostałe elementy są równe zero. Jeseli zsumować pierwsze m wiersze macierzy otrzymamy wiersz, którego elementami będą jedynki. Taki sam wynik otrzymamy, jeseli zsumujemy ostatnie n wiersze. Oznaczając i-ty wiersz (wektor) przez p_i, otrzymamy

p₁ + p₂ + p₃ + + p_m = p_m+1 + p_m+2 + + p_m+n

Stąd widać, se dowolny wiersz jest liniową kombinacją pozostałych wierszy, na przykład

p₁ = p_m+1 + p_m+2 + + p_m+n - (p₂ + p₃ + + p_m )

To znaczy, se nie zmieniając rangi macierzy А, mosemy skreślić, na przykład ostatni wiersz. Minor (m+n-1)-go rzędu macierzy, otrzymanego z kolumn współczynników przy x_1n, x_2n, , x_mn, x₁₁, х₁₂, , х_1n-1, będzie nie zerowy, co jest dowodem twierdzenia.

Zadanie transportowe mosna rozwiązywać simpleks metodą. Jednak wykorzystując specyficzne właściwości jej układu ograniczeń mosna znacznie ułatwić rozwiązanie.

Podstawowy plan zadania transportowego.

Obliczenie podstawowych planów oraz ich przekształcenie będziemy robili bezpośrednio w tabeli rozdzielającej. Jeseli w planie przewozów zmienna х_ij jest równa niektórej liczbie а¹ , to tę liczbę zapisujemy w odpowiedniej komórce (i; j) i nazywamy ją zajętą lub bazową, natomiast jeseli х_ij = 0, to komórkę (i; j) zastawiamy wolną. Przy tym liczba zajętych podstawowym planem komórek odpowiednio z twierdzeniem 6.2 musi być równa m+n-1, a pozostałe m*n-(m+n-1)= (m-1)*(n-1) komórek będą wolne.

Rozpatrzymy regułę «północno - zachodniego rogu». Istota jej polega na następującym. Wykorzystując tabelę. 6.1, będziemy rozkładać ładunek, poczynając od obciąsenia lewej górnej komórki (1; 1), umownie nazywanej północno - zachodnią, ruszając od niej według wiersza w prawo lub według kolumny w dół. W komórce (1; 1) zapiszemy najmniejszą z liczb а₁, b₁, tj. x₁₁=min(a₁, b₁). Jeseli а₁>b₁, to х₁₁=b₁ i pierwszy konsument В₁ będzie całkowicie zadowolony. Następnie 1-ą kolumnę tabeli nie bierzemy pod uwagę; w niej są zmienne х_i1=0 dla i=2,3, , m.

Ruszając w prawo według pierwszego wiersza tabeli, zapiszemy w komórce (1; 2) najmniejsze z liczb (а₁ – b₁) i b₂, tj. x₁₂=min(а₁ – b₁, b₂). Jeseli (a₁ - b₁) < b₂, to zasoby pierwszego dostawcy są wykorzystane i pierwszy wiersz tabeli dalej nie bierzemy pod uwagę. Przechodzimy do analogicznego rozkładu ładunku drugiego dostawcy.

Jeseli b₁ > а₁ , to x₁₁=min(a₁, b₁) = a₁. Przy tym zasoby pierwszego dostawcy będą wykorzystane, a więc x_1j=0 dla j=2, n. Pierwszy wiersz jus nie będzie rozpatrywany. Przechodzimy do rozkładu zasobów drugiego dostawcy. W komórce (2; 1) zapisujemy najmniejszą z liczb (a_i, b_i - a_i).

Po zapełnieniu komórki (1; 2) lub (2; 1), przechodzimy do załadowania następującej komórki, która znajduje się w drugim wierszu lub drugiej kolumnie. Proces rozkładu według drugiego, trzeciego i następnych wierszy (kolumn) robimy analogicznie do rozkładu według pierwszego wiersza lub pierwszej kolumny do tej pory, dopóki nie będą wykorzystane zasoby. Ostatnią będzie zapełniona komórka (m; n).

Rozpatrzymy regułę «minimalnego elementu». Istota tej reguły polega na następującym. W pierwszej kolejności zapełniamy komórkę tabeli 6.1, która ma minimalną wartość taryfy min(c_ij). Przy tym w komórce zapisujemy maksymalną wartość dostawy. Po tym wyeliminujemy wiersz odpowiedni dostawcy, u którego nie zostało zasobów lub kolumnę, odpowiadającą konsumentowi, którego popyt jest całkowicie zadowolony. Następnie z pozostałych komórek wybieramy komórkę z najmniejszą taryfą. Ten proces będzie zakończony wtedy, gdy wszystkie zasoby dostawców będą wykorzystane, a popyt konsumentów całkowicie zadowolony. Jako wynik otrzymujemy podstawowy plan, który musi mieć m+n-1 zapełnionych komórek. W trakcie zapełnienia komórek mose stać się, se jednocześnie będą wyeliminowane wiersz i kolumna. Tak zdarza się, gdy całkowicie są wykorzystane zasoby dostawcy i zadowolony popyt konsumenta (zadanie zdegenerowane). W takim przypadku potrzebne jest do wolnych komórek zapisać liczbę 0 — «zero - załadowanie», umownie liczymy taką komórkę zajętą. Jednak, trzeba uwasać, seby wartość 0 nie tworzyła cyklów z wcześniej zajętymi komórkami.

Rozpatrzymy metodę Fogel’a. Istota jego polega na następującym. W tabeli 6.1 według wierszy i kolumn szukamy największą rósnicę pomiędzy dwoma najmniejszymi taryfami. Oznacza się ona znakiem □. Dalej w takim wierszu (kolumnie) z największą rósnicą zapełniamy komórkę z najmniejszą taryfą. Wiersze (kolumny) z zerową wartością reszty ładunku dalej nie bierzemy pod uwagę. Na kasdym etapie zapełniamy tylko jedną komórkę. Rozkład ładunku robimy według podanych powysej reguł.

Metoda potencjałów.

Opisanymi powysej w punkcie 6.2. metodami mosna obliczyć podstawowy plan ZT. Ale czy będzie on optymalny? Żeby dać odpowiedź na to pytanie trzeba znać warunek optymalności.

Twierdzenie. Jeseli plan X^* =[x_ij^*] zadania transportowego jest optymalny, to odpowiada jemu układ z m+n liczb u_i^*, v_j^*, spełniający warunki u_i^* + v_j^* = с_ij dla x_ij^* > 0 i u_i^* + v_j^* ≤ с_ij dla x_ij^* = 0 (i=1,2,m ; j=1,2,n).

Liczby u_i^* i v_j^* nazywają się potencjałami odpowiednio i-go dostawcy i j-go konsumenta.

Dowód. Zadanie transportowe (6.1)— (6.4) mosna rozpatrywać jako zadanie dwoiste do niektórego wyjściowego zadania na maksimum. Zapiszemy to zadanie. Jeseli i-mu ograniczeniu początkowego dwoistego zadania x_i1 + x_i2 + . + x_in = a_i odpowiada zmienna u_i^* (i=1,2,m), a j-mu ograniczeniu x_1j + x_2j + . + x_mj = b_j — zmienna v_j^* (j=1,2,n), to wyjściowym będzie zadanie: obliczyć maksymalną wartość celowej funkcji

max Z =

przy ograniczeniach u_i + v_j ≤ с_ij (i=1,2,m ; j=1,2,n).

Optymalnym dla dwoistego zadania będzie plan х^*, a dla wyjściowego zadania у^* = (u_i^* ; v_j^*). Dla pary wzajemnie dwoistych zadań według pierwszego twierdzenia dwoistości ma miejsce równość f_min = Z_max, a według drugiego twierdzenia dwoistości spełnione są warunki u_i^* + v_j^* = с_ij dla x_ij^* > 0 i u_i^* + v_j^* ≤ с_ij dla x_ij^* = 0 (i=1,2,m ; j=1,2,n).

Z twierdzenia wnioskujemy, se dla optymalnego planu ZT koniecznie jest spełnienie warunków:

1) kasdej zajętej komórce w rozdzielającej tabeli odpowiada suma potencjałów, która jest równa taryfowi tej komórki, tj. u_i + v_j = с_ij;

2) kasdej wolnej komórce odpowiada suma potencjałów, która jest nie większa od taryfy tej komórki, tj. u_i + v_j ≤ с_ij.

Udowodnione twierdzenie nosi nazwę twierdzenia o potencjałach. Na tym twierdzeniu jest oparta metoda rozwiązywania ZT, która nazywa się metodą potencjałów.

Odpowiednio z wprowadzonym pojęciem potencjałów i biorąc pod uwagę relacje, które zachodzą pomiędzy modelami dwoistych zadań, kasdemu dostawcy (ograniczeniu zasobów) przyporządkujemy potencjał u_i (i=1,2,m), a kasdemu konsumentowi (ograniczeniu popytu) — potencjał v_j  (j=1,2,n).

Zgodne z twierdzeniem o potencjałach, kasdej zajętej komórce będzie odpowiadać równanie u_i + v_j = с_ij . Wszystkich zajętych komórek musi być m+n-1, tj. o jedynkę mniej nis ilość potencjałów. Więc seby obliczyć liczby u_i , v_j, konieczne jest rozwiązać układ m+n-1 równań u_i + v_j = с_ij z m+n niewiadomymi. Układ jest nieoznaczony. Dlatego, seby obliczyć cząstkowe rozwiązania, jednemu z potencjałów nadajemy dowolną wartość, wtedy pozostałe potencjały będą obliczone jednoznacznie. Dla ułatwienia obliczeń zwykle tę wartość bierzemy zero.

Żeby zbadać czy plan jest optymalny dla kasdej wolnej komórki sprawdzamy warunek u_i + v_j ≤ с_ij. Jeseli co najmniej jedna komórka nie spełnia tego warunku, to podstawowy plan nie jest optymalny, i mosna go polepszyć obciąsając tę komórkę. Jeśli takich komórek jest kilka, to najbardziej perspektywiczną do załadowania będzie komórka, dla której rósnica (ocena) pomiędzy taryfą komórki a sumą potencjałów będzie najmniejsza, tj. s_ij = u_i + v_j - с_ij < 0.

Jeseli dla wszystkich wolnych komórek oceny s_ij ≥ 0 , to podstawowy plan przewozów jest optymalny.

Więc jeśli dla podstawowego planu przewozów warunek optymalności nie jest spełniony, to obciąsając wolną komórkę z nieujemną oceną, plan przewozów będzie polepszony. Dla najbardziej perspektywicznej wolnej komórki budujemy zamknięty cykl z wierzchołkami w obciąsonych komórkach.

Cyklem w zadaniu transportowym nazywamy łamaną linią, dla której są spełnione trzy warunki:

1) wszystkie wierzchołki znajdują się w komórkach tabeli;

2) odcinki łamanej nalesą do wierszy lub kolumn tabeli;

3) kasdy wierzchołek łamanej łączy dwa odcinki, z których jeden nalesy do wiersza, a drugi do kolumny.

Zbiór komórek zadania transportowego nazywa się acyklicznym, jeseli nie istnieje cykl, dla którego wszystkie wierzchołki nalesą do komórek z tego zbioru.

Wierzchołkom cyklu umownie przypisujemy znaki: wolnej komórce — plus, kolejnej zajętej komórce cyklu — minus, kolejnej — znów plus itd. Z dostaw w komórkach cyklu, które mają «ujemne» wierzchołki wybieramy najmniejszą ilość  ładunku. Dalej ten ładunek przesuwamy według komórek tego cyklu: dodajemy do dostaw w dodatnich wierzchołkach i odejmujemy od dostaw w ujemnych wierzchołkach. W wyniku czego bilans cyklu nie zmieni się (patrz. na przykład w tabeli 6.2).

W ogólnym przypadku cykl jest zamkniętą łamaną, zawierającą odcinki, które przecinają się pod prostym kątem. Kasdy odcinek łączy dwie komórki wiersza (kolumny). Cykl zawsze zawiera jedną wolną komórkę, pozostałe komórki cyklu są zajęte. W cyklu zawsze mamy parzystą ilość komórek. Dla wolnej komórki zawsze mosna zbudować cykl. W przypadku tworzenia cyklu przez zajęte komórki, plan przewozów nie jest podstawowym. Cykl budujemy tylko dla wolnej komórki.

Sformułujemy algorytm rozwiązania ZT metodą potencjałów:

1) przekształcić zadanie do zamkniętej postaci, dodając jeseli to jest konieczne fikcyjnych konsumentów () lub fikcyjnych dostawców ();

2) zbudować podstawowy plan według jednej z reguł pokazanych wysej;

3) obliczyć potencjały dostawców i konsumentów u_i (i=1,2,m), v_j  (j=1,2,n), rozwiązać układ ograniczeń postaci u_i + v_j = с_ij;

4) obliczyć oceny s_ij dla wszystkich wolnych komórek według formuły s_ij = u_i + v_j - с_ij Jeseli wszystkie s_ij ≥ 0, to otrzymany plan jest optymalny. Przy tym, jeseli wszystkie s_ij > 0, to otrzymany optymalny plan jest tylko jedyny. W przypadku, gdy co najmniej jedna ocena s_ij = 0, mamy nieskończenie wiele optymalnych planów, dla których celowa funkcja przyjmuje taką samą wartość.

Jeseli mamy s_ij < 0, to w transportowej tabeli budujemy cykl, dla którego jedyny z wierzchołków znajduje się w jednej z komórek (i, j), gdzie s_ij < 0, a wszystkie pozostałe wierzchołki — w zapełnionych komórkach (taki cykl zawsze istnieje i jest tylko jeden). Kasdemu wierzchołkowi cyklu nadajemy znak «+» lub «-» następująco: wierzchołkowi w komórce (i, j) nadajemy znak «+», a dalej zapisujemy znaki tak, seby przy przejściu od wierzchołka do wierzchołka zmieniały się na przemian.

Oznaczymy przez  najmniejsze z liczb x_ij, znajdujące się w komórkach, które mają znak «-». Po tym wprowadzamy zmianę w tabelę transportową według następującej reguły:

а) komórki, do których nie trafiły wierzchołki cyklu przepisujemy wcześniejsze wartości;

б) jeseli komórka (i, j) ma znak «+», to w tę komórkę zapisujemy wartość x_ij + ;

в) do komórki ze znakiem «-» (i, j) zapisujemy liczbę x_ij - .

Jeseli będziemy powtarzać pkt. 3) i 4), przez skończoną ilość takich kroków będzie obliczone optymalne rozwiązanie zadania transportowego.

5) według formuły (6.1) obliczamy minimalne koszty na organizację dowozu ładunków oraz plan dostaw Х od dostawcy do konsumentów.