Lekcja 6. Zadanie transportowe.

6.1. Modele zadania transportowego. Zadanie transportowe i zadania programowania liniowego.

6.2. Podstawowy plan zadania transportowego.

6.3. Metoda potencjałów.

6.4. Przykład rozwiązania zadania transportowego metodą potencjałów.

6.1. 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 każdego punktu produkcji A_i, (i= 1, 2, ... , m) do każdego punktu konsumpcji B_j (j=1, 2, ... , n) jest znany i wynosi c_ij 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 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 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=[x_ij] 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 6.1 (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 x_ij oddzielnie według indeksów i i j, otrzymamy:

;

Rzeczywiście, że zsumujemy wszystkie elementy x_ij 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 x_ij zapiszemy przez dane zadania następująco:

(6.6)

Biorąc pod uwagę to, że а_i ≥ 0 i b_j ≥ 0, mamy, że A > 0, więc i x_ij ≥ 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 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 6.2 (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 p_i, otrzymamy

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

Stąd widać, że 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, ż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 x_1n, x_2n, ... , x_mn, x₁₁, х₁₂, ... , х_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.

6.2. 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 а₁, b₁, tj. x₁₁=min(a₁, b₁). Jeżeli а₁>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₂). Jeżeli (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.

Jeżeli 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 już 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 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ł.

6.3. 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 6.3. Jeżeli 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) 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 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, ż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. u_i + v_j = с_ij;

2) każdej 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ń, każdemu dostawcy (ograniczeniu zasobów) przyporządkujemy potencjał u_i (i=1,2,...m), a każdemu konsumentowi (ograniczeniu popytu) — potencjał v_j (j=1,2,...n).

Zgodne z twierdzeniem o potencjałach, każdej 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 niż ilość potencjałów. Więc żeby 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, ż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 u_i + v_j ≤ с_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. s_ij = u_i + v_j - с_ij < 0.

Jeżeli 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ąż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 (pętlą) 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(x₂₁;x₁₂;x₃₄)

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 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 = с_ij - u_i - v_j . Jeżeli wszystkie s_ij ≥ 0 (lub u_i + v_j ≤ с_ij - suma potencjałów nie przekracza „taryfy” ), to otrzymany plan jest optymalny. Przy tym, jeżeli 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ść.

Jeżeli 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). 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 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;

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

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

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.

6.4. Przykład rozwiązania ZT metodą potencjałów.

Zadanie. Banki komercyjne А_i (i=1,2,3,4) pozyczją na różne terminy kredyty dla przedsiębiorstw В_j (j=1,2,3,4) pod procenty c_ij z celem odzyskania maksymalnego zysku. Bank A_i pożycza kredyt wysokości a_i , zapotrzebowanie przedsiębiorstwa B_j jest b_j (tys. zł). Stopa procentowa c_ij .

Potrzebnie:

1) Sformułować ekonomiczno - matematyczny model zadania dystrybucji bankami kredytów dla przedsiębiorstw z celem odzyskania maksymalnego zysku;

2) Metodą potencjałów rozwiązać ZT;

3) Wskazać przedsiębiorstwa, który nie otrzymali całkowicie kredyty i jego sumę;

a₁=150 a₂=200 a₃=100 a₄=100 b₁=100 b₂=150 b₃=150 b₄=200 c₁₁=15 c₁₂=10 c₁₃=18 c₁₄=16 c₂₁=19 c₂₂=21 c₂₃=15 c₂₄=17 c_3l=10 c₃₂=15 c₃₃=20 c₃₄=21 c_4l=12 c₄₂=14 c₄₃=15 c₄₄=17

Rozwiązanie.

1) Zapiszemy początkowe warunki zadania w postaci tabeli 1.

Tabela 1
	B1		B2		B3		B4		
А1	x11	^-15	x12	^-10	x13	^-18	x14	^-16	150
А2	x21	^-19	x22	^-21	x23	^-15	x24	^-17	200
А3	x31	^-10	x32	^-15	x33	^-20	x34	^-21	100
А4	x41	^-12	x42	^-14	x43	^-15	x44	^-17	100
	100		150		150		200

Wskaźnikami kryterium optymalności będą sumę zysku, które otrzymują banki i, odpowiednie, wydatków przedsiębiorstw dla spłacenia procentów dla banków.

Wprowadzimy zmienne х_ij, (i=1,..4. j=1, .. 4) - ilość pieniędzy (zysk), które bank А_i otrzymuje od przedsiębiorstwa B_j jako procent, a przez f - ogólny zysk banków.

Znajdziemy ilość kredytów wypożyczanych bankami:  a_i = 150+200+100+100 = 550 , i sumę, którą potrzebują przedsiębiorstwa:  b_j = 100+150+150+200 = 600. Widać, że kredytów jest za mało na 600-550=50. Na taką sumę przedsiębiorstwa nie otrzymają kredyty (deficyt kredytów).

Funkcja celu zadania ma postać:

f = c_ijx_ij = c₁₁x₁₁+ … c₄₄x₄₄ → max

lub ekwiwalentna postać dla minimalizacji wydatków przedsiębiorstw na kredyty:

g = -f = c_ijx_ij = -(c₁₁x₁₁+ … c₄₄x₄₄ ) → min

Na zmienne х_ij nałożymy ograniczenia resursów kredytowych banków i zapotrzebowań przedsiębiorstw:

х₁₁+х₁₂+х₁₃+х₁₄ <= a₁

х₂₁+х₂₂+х₂₃+х₂₄ <= a₂

х₃₁+х₃₂+х₃₃+х₃₄ <= a₃

х₄₁+х₄₂+х₄₃+х₄₄ <= a₄

х₁₁+х₂₁+х₃₁+х₄₁ <= b₁

х₁₂+х₂₂+х₃₂+х₄₂ <= b₂

х₁₃+х₂₃+х₃₃+х₄₃ <= b₃

х₁₄+х₂₄+х₃₄+х₄₄ <= b₄

x_ij >=0, i=1,..4; j=1,…4.

Funkcja celu razem z ograniczeniami tworzą ekonomiczno - matematyczny model zadania.

2) Dla rozwiązania zadania metodą potencjałów wprowadzimy fikcyjny bank А5, który pożycza kredyt o wielkości dyzbilansu 50 jednostek. Liczymy, że stopa procentowa fikcyjnego banku równa się 0. Optymalizować będziemy funkcje g, która dąży do minimum. Dla tego weźmiemy potencjały komórek ze znakiem "-". Wtedy zadanie ma postać:

g = -(c₁₁x₁₁+ … c₄₄x₄₄ ) →min

х₁₁+х₁₂+х₁₃+х₁₄ <= 150

х₂₁+х₂₂+х₂₃+х₂₄ <= 200

х₃₁+х₃₂+х₃₃+х₃₄ <= 100

х₄₁+х₄₂+х₄₃+х₄₄ <= 100

х₅₁+х₅₂+х₅₃+х₅₄ <= 50

х₁₁+х₂₁+х₃₁+х₄₁+х₅₁ <= 100

х₁₂+х₂₂+х₃₂+х₄₂ +х₅₂ <= 150

х₁₃+х₂₃+х₃₃+х₄₃ +х₅₃ <= 150

х₁₄+х₂₄+х₃₄+х₄₄+х₅₄ <= 200

x_ij >=0, i=1,..4; j=1,…4.

Wprowadzimy podstawowy plan zadania. Zauważymy, że liczba zajętych podstawowym planem komórek odpowiednio z twierdzeniem 6.2 musi być równa m+n-1 = 4+5-1=8 komórek.

Tabela 2
	B1		B2		B3		B4		
А1	50	^-15		^-10	100	^-18		^-16	150
А2	50	^-19	150	^-21		^-15		^-17	200
А3		^-10		^-15	50	^-20	50	^-21	100
А4		^-12		^-14		^-15	100	^-17	100
А5		^0		^0		^0	50	^0	50
	100		150		150		200

Wprowadzimy podstawowy plan zadania metodą minimalnego elementu. Dla tego wybierzemy jedną z komórek z najmniejszą taryfą: komórka (А₂В₂) z taryfą (-21). Wpiszemy minimalną wartość wiersza А i kolumny В (wartość 150). Różnica 200-150=50 będzie wpisana w komórkę wiersza, która jest wolna i ma teraz minimalną wartość taryfy (-19). Dalej wprowadzimy wartości w pierwszej kolumnie tablicy, trzeciej i tak do końca tabeli (Tabela 2).

Zbadamy podstawowy plan na optymalność. Dla tego znajdziemy potencjały u_i banków i v_j przedsiębiorstw. Zapiszemy układ równań:

u₁+v₁=-15; u₁+v₃=-18; u₂+v₁=-19; u₂+v₂=-21; u₃+v₃=-20; u₃+v₄=-21; u₄+v₄=-17; u₅+v₄=0

Liczba równań jest na 1 mniej niż ilość zmiennych. Wtedy założymy, że u₁=0, i z układu równań znajdziemy:

u₂=-4 ; u₃= -2; u₄= 2; u₅=19 ; v₁=-15 ; v₂=-17 ; v₃=-18 ; v₄= -19.

Obliczymy potencjały pustych komórek:

u1+v2=-17 <= -10	u1+v2=-19 <= -16	u2+v3=-22 <= -15	u2+v4=-23 < -17
u3+v1=-17 <= -10	u3+v2=-19 <= -15	u4+v1=-13 <= -12	u4+v2=-15 <= -14
u4+v3=-16 <= -15	u5+v1=4 >0	u5+v2=2 >0	u5+v3=1 >0

Widać, że istnieją komórki z niedodatnimi ocenami (komórki А₅В₁, А₅В₂ i inni). Wnioskujemy, że ten plan nie jest optymalny. Wybierzemy komórkę А₅В₁ jako komórkę z największej ujemnej oceną i wprowadzimy w nią wartość kredytu. Dla tego wprowadzimy pętlę zamkniętą w kierunku: А₅В₁ - А₁В₁ - А₁В₃ - А₃В₃ - А₃В₄ - А₅В₄ - А₅В₁ . Pętla łączy niepusty komórki planu.

Tabela 3
	B1		B2		B3		B4		
А1		^-15		^-10	150	^-18		^-16	150
А2	50	^-19	150	^-21		^-15		^-17	200
А3		^-10		^-15		^-20	100	^-21	100
А4		^-12		^-14		^-15	100	^-17	100
А5	50	^0		^0		^0		^0	50
	100		150		150		200

Przy obejściu pętli zaczynając od komórki А₁В₁ kolejno dodajemy i odejmujemy w wierzchołkach minimalną wartość (50) z wierzchołków, gdzie odbywa się odejmowanie. Na końcu otrzymujemy tabelę 3.

Dla tabeli 3 ma miejsce układ równań:

u₁+v₃=-18; u₂+v₁=-19; u₂+v₂=-21; u₃+v₄=-21; u₄+v₄=-17; u₅+v₁=0;

Z układu równań znajdziemy:u₁=1; u₂=0; u₃= -2; u₄= 2; u₅=19; v₁=-19 ; v₂=-21 ; v₃=-19 ; v₄= -19.

Obliczymy potencjały pustych komórek:

u1+v1=-18 <= -15	u1+v2=-20 <= -10	u1+v4=-18 <= -16	u2+v3=-19 <= -15
u2+v4=-19 <= -17	u3+v1=-21 <= -10	u3+v2=-23 <= -15	u3+v3=-21 <= -20
u4+v1=-17 <= -12	u4+v2=-19 <= -14	u4+v3=-17 <= -15	u5+v2=-2 <= 0
u5+v3=0 <= 0	u5+v4=0 <= 0

Wyszło, że wszędzie w pustych komórkach oceny niedodatnie. Z tego na podstawie twierdzeń programowania liniowego wnioskujemy, że ten plan jest optymalnym.

Więc, z tabeli 3 wynika, że 1-szy bank pożycza 150 jednostek 3-mu przedsiębiorstwu, 2-gi bank 50 jednostek kredytu pożycza 1-mu przedsiębiorstwu i 150 jednostek - 2-mu przedsiębiorstwu, 3-ci bank pożycza 100 jednostek kredytu 4-mu przedsiębiorstwu, i 4-ty bank pożycza 100 jednostek kredytu 4-mu przedsiębiorstwu.

Maksymalny zysk banków jest f = -g = 150*18 + 50*19 + 150*21 + 100*21 + 100*17 = 10600 jednostek.

3) Na podstawie tabeli 3, nie otrzymuje w całości kredyt przedsiębiorstwo В₁ na sumę 50 jednostek, ponieważ z tabeli 3 wynika, że przedsiębiorstwo В₁ otrzymało kredyt od fikcyjnego banku. Inne przedsiębiorstwa uzyskali kredyt w całości odpowiednie ich zapotrzebowaniom.

1

7

Lekcja 6. Zadanie transportowe.

---