Mapa Serwisu
|
| Zadanie transportowe |
|
Admin1 dnia marzec 15 2007 17:12:25
|
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 A1, A2, ... Am, w których produkuje się pewien produkt odpowiednio w ilościach a1, a2, ... am jednostek. Ten produkt potrzeba dostarczyć do n punktów konsumpcji B1, B2, ... Bn, zapotrzebowania których wynoszą odpowiednio b1, b2, ... bn jednostek. Koszt dostawy z każdego punktu produkcji Ai, (i= 1, 2, ... , m) do każdego punktu konsumpcji Bj (j=1, 2, ... , n) jest znany i wynosi cij jednostek. Należy znale¼ć plan przewozu, dla którego byłyby spełnione wszystkie zapotrzebowania, a sumowany koszt wszystkich przewozów byłby minimalny.
Można liczyć, że . W tym przypadku model zadania transportowego nazywa się zamkniętym.
Jeżeli , 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 xij ilość produktu, przewiezionego z punktu Ai, (i= 1, 2, ... , m) do punktu konsumpcji Bj (j=1, 2, ... , n). Jeśli f jest kosztem przewozu to
Przy tym z punktu Ai, (i= 1, 2, ... , m) będzie wywiezione razem jednostek produktu, a do punktu Bj (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 można zapisać w postaci tabeli (tabela. 6.1), którą nazywa się rozdzielającą. Rozdzielającą tabelę nazywa się czasami tabelkowym lub macierzowym modelem ZT.
Tabela 6.1
Dostawca Konsument Zapas ładunku ai
B1 B2 ... Bn
Koszty przewozu 1 ki. ładunku
А1 c11 c12 ... c1n a1
x11 x12 x1n
А2 c21 c22 ... c2n a2
x21 x22 x2n
... ... ... ... ... ...
Аm cm1 cm2 ... cmn am
xm1 xm2 xmn
Zapotrzebowanie na ładunek bj b1 b2 ... bn
Będziemy nazywać plan przewozu X=[xij] dopuszczalnym, jeżeli 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, żeby 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 xij oddzielnie według indeksów i i j, otrzymamy:
;
Rzeczywiście, że zsumujemy wszystkie elementy xij według wierszy oraz kolumn, różnica polega tylko w kolejności elementów. Ale wartość sumy nie jest uzależniona od kolejności elementów. Dlatego równość jest koniecznym warunkiem rozwiązalności ZT.
Dla dowodu dostateczności warunku (6.5) pokażemy, że jeżeli ten warunek jest spełniony to zawsze istnieje dopuszczalny plan. Oznaczymy = А. Zmienne xij zapiszemy przez dane zadania następująco:
(6.6)
Biorąc pod uwagę to, że аi 0 i bj 0, mamy, że A > 0, więc i xij 0 (i=1,2,...m; j=1,2,...n).
Pokażemy, że zmienne (6.6) są dopuszczalnym planem. Ten zbiór nieujemnych wartości będzie dopuszczalnym planem, jeżeli 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 ,że j nie zależy 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. Jeżeli wszystkie liczby a1, a2, ... am i b1, b2, ... bn — 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 każdej kolumnie macierzy А są tylko dwa elementy, równe jedynce, pozostałe elementy są równe zero. Jeżeli zsumować pierwsze m wiersze macierzy otrzymamy wiersz, którego elementami będą jedynki. Taki sam wynik otrzymamy, jeżeli zsumujemy ostatnie n wiersze. Oznaczając i-ty wiersz (wektor) przez pi, otrzymamy
p1 + p2 + p3 + ... + pm = pm+1 + pm+2 + ... + pm+n
Stąd widać, że dowolny wiersz jest liniową kombinacją pozostałych wierszy, na przykład
p1 = pm+1 + pm+2 + ... + pm+n - (p2 + p3 + ... + pm )
To znaczy, że nie zmieniając rangi macierzy А, możemy skreślić, na przykład ostatni wiersz. Minor (m+n-1)-go rzędu macierzy, otrzymanego z kolumn współczynników przy x1n, x2n, ... , xmn, x11, х12, ... , х1n-1, będzie nie zerowy, co jest dowodem twierdzenia.
Zadanie transportowe można rozwiązywać simpleks metodą. Jednak wykorzystując specyficzne właściwości jej układu ograniczeń można 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. Jeżeli w planie przewozów zmienna хij jest równa niektórej liczbie а0, to tę liczbę zapisujemy w odpowiedniej komórce (i; j) i nazywamy ją zajętą lub bazową, natomiast jeżeli х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ążenia 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 а1, b1, tj. x11=min(a1, b1). Jeżeli а1>b1, to х11=b1 i pierwszy konsument В1 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 (а1 – b1) i b2, tj. x12=min(а1 – b1, b2). Jeżeli (a1 - b1) < b2, to zasoby pierwszego dostawcy są wykorzystane i pierwszy wiersz tabeli dalej nie bierzemy pod uwagę. Przechodzimy do analogicznego rozkładu ładunku drugiego dostawcy.
Jeżeli b1 > а1 , to x11=min(a1, b1) = a1. Przy tym zasoby pierwszego dostawcy będą wykorzystane, a więc x1j=0 dla j=2, n. Pierwszy wiersz już nie będzie rozpatrywany. Przechodzimy do rozkładu zasobów drugiego dostawcy. W komórce (2; 1) zapisujemy najmniejszą z liczb (ai, bi - ai).
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(cij). 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 może stać się, że 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 uważać, żeby 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óżnicę pomiędzy dwoma najmniejszymi taryfami. Oznacza się ona znakiem □. Dalej w takim wierszu (kolumnie) z największą różnicą zapełniamy komórkę z najmniejszą taryfą. Wiersze (kolumny) z zerową wartością reszty ładunku dalej nie bierzemy pod uwagę. Na każdym etapie zapełniamy tylko jedną komórkę. Rozkład ładunku robimy według podanych powyżej reguł.
Metoda potencjałów.
Opisanymi powyżej w punkcie 6.2. metodami można obliczyć podstawowy plan ZT. Ale czy będzie on optymalny? źeby dać odpowied¼ na to pytanie trzeba znać warunek optymalności.
Twierdzenie. Jeżeli plan X* =[xij*] zadania transportowego jest optymalny, to odpowiada jemu układ z m+n liczb ui*, vj*, spełniający warunki ui* + vj* = сij dla xij* > 0 i ui* + vj* ≤ сij dla xij* = 0 (i=1,2,...m ; j=1,2,...n).
Liczby ui* i vj* nazywają się potencjałami odpowiednio i-go dostawcy i j-go konsumenta.
Dowód. Zadanie transportowe (6.1)— (6.4) można rozpatrywać jako zadanie dwoiste do niektórego wyjściowego zadania na maksimum. Zapiszemy to zadanie. Jeżeli i-mu ograniczeniu początkowego dwoistego zadania xi1 + xi2 + .... + xin = ai odpowiada zmienna ui* (i=1,2,...m), a j-mu ograniczeniu x1j + x2j + .... + xmj = bj — zmienna vj* (j=1,2,...n), to wyjściowym będzie zadanie: obliczyć maksymalną wartość celowej funkcji
max Z =
przy ograniczeniach ui + vj ≤ сij (i=1,2,...m ; j=1,2,...n).
Optymalnym dla dwoistego zadania będzie plan х*, a dla wyjściowego zadania у* = (ui* ; vj*). Dla pary wzajemnie dwoistych zadań według pierwszego twierdzenia dwoistości ma miejsce równość fmin = Zmax, a według drugiego twierdzenia dwoistości spełnione są warunki ui* + vj* = сij dla xij* > 0 i ui* + vj* ≤ сij dla xij* = 0 (i=1,2,...m ; j=1,2,...n).
Z twierdzenia wnioskujemy, że dla optymalnego planu ZT koniecznie jest spełnienie warunków:
1) każdej zajętej komórce w rozdzielającej tabeli odpowiada suma potencjałów, która jest równa taryfowi tej komórki, tj. ui + vj = сij;
2) każdej wolnej komórce odpowiada suma potencjałów, która jest nie większa od taryfy tej komórki, tj. ui + vj ≤ с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ń, każdemu dostawcy (ograniczeniu zasobów) przyporządkujemy potencjał ui (i=1,2,...m), a każdemu konsumentowi (ograniczeniu popytu) — potencjał vj (j=1,2,...n).
Zgodne z twierdzeniem o potencjałach, każdej zajętej komórce będzie odpowiadać równanie ui + vj = сij . Wszystkich zajętych komórek musi być m+n-1, tj. o jedynkę mniej niż ilość potencjałów. Więc żeby obliczyć liczby ui , vj, konieczne jest rozwiązać układ m+n-1 równań ui + vj = сij z m+n niewiadomymi. Układ jest nieoznaczony. Dlatego, żeby 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 każdej wolnej komórki sprawdzamy warunek ui + vj ≤ сij. Jeżeli co najmniej jedna komórka nie spełnia tego warunku, to podstawowy plan nie jest optymalny, i można go polepszyć obciążają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óżnica (ocena) pomiędzy taryfą komórki a sumą potencjałów będzie najmniejsza, tj. sij = ui + vj - сij < 0.
Jeżeli dla wszystkich wolnych komórek oceny sij ≥ 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ążają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ążonych 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 należą do wierszy lub kolumn tabeli;
3) każdy wierzchołek łamanej łączy dwa odcinki, z których jeden należy do wiersza, a drugi do kolumny.
Zbiór komórek zadania transportowego nazywa się acyklicznym, jeżeli nie istnieje cykl, dla którego wszystkie wierzchołki należą do komórek z tego zbioru.
Tabela 6.2
B1 B2 B3 B4 ai
A1
c11 c12 c13 c14 a1
x12 x14
A2 c21 c22 c23 c24 a2
x21 x22
A3 c31 c32 c33 c34 a3
x32 x34
bj b1 b2 b3 b4
m=3; n=4; m+n-1=6; =min(x21;x12;x34)
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. Każdy 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 można 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 jeżeli to jest konieczne fikcyjnych konsumentów ( ) lub fikcyjnych dostawców ( );
2) zbudować podstawowy plan według jednej z reguł pokazanych wyżej;
3) obliczyć potencjały dostawców i konsumentów ui (i=1,2,...m), vj (j=1,2,...n), rozwiązać układ ograniczeń postaci ui + vj = сij;
4) obliczyć oceny sij dla wszystkich wolnych komórek według formuły sij = ui + vj - сij. Jeżeli wszystkie sij ≥ 0, to otrzymany plan jest optymalny. Przy tym, jeżeli wszystkie sij > 0, to otrzymany optymalny plan jest tylko jedyny. W przypadku, gdy co najmniej jedna ocena sij = 0, mamy nieskończenie wiele optymalnych planów, dla których celowa funkcja przyjmuje taką samą wartość.
Jeżeli mamy sij < 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 sij < 0, a wszystkie pozostałe wierzchołki — w zapełnionych komórkach (taki cykl zawsze istnieje i jest tylko jeden). Każdemu wierzchołkowi cyklu nadajemy znak «+» lub «-» następująco: wierzchołkowi w komórce (i, j) nadajemy znak «+», a dalej zapisujemy znaki tak, żeby przy przejściu od wierzchołka do wierzchołka zmieniały się na przemian.
Oznaczymy przez najmniejsze z liczb xij, 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;
б) jeżeli komórka (i, j) ma znak «+», to w tę komórkę zapisujemy wartość xij + ;
в) do komórki ze znakiem «-» (i, j) zapisujemy liczbę xij - .
Jeżeli 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.
|
|
|
Zaloguj się, żeby móc dodawać komentarze.
|
|
|
Dodawanie ocen dostępne tylko dla zalogowanych Użytkowników.
Proszę się zalogować lub zarejestrować, żeby móc dodawać oceny.
Brak ocen.
|
|
|
|
