[ Pobierz całość w formacie PDF ]
.2)-(1.4), (1.5)-(1.7), (1.8)-(1.11),(1.12)-(1.15) pozwalaj¹ zapisaæ ogóln¹ postaæ ekonomiczno-matematycznego modeluzadania programowania liniowego.Ogólnym zadaniem programowania liniowego (ÎZPL) nazywamy zadaniemax (min) Z = c1*x1+c2*x2+.+cn*xn = (1.16)przy ograniczeniach:ai1*x1+ai2*x2+.+ ain*xn £ bi, lub , (i=1,2,.m1) (1.17)ai1*x1+ai2*x2+.+ ain*xn = bi, lub , (i=m1+1, m1+2,.m2) (1.18)ai1*x1+ai2*x2+.+ ain*xn ³ bi, lub , (i= m2+1, m2+2,.m) (1.19)xj ³ 0, j=1,2,.n1 (1.20)xj - dowolne (j= n1+1, n1+2,.n) (1.21)gdzie ñj, aij, bi - dane rzeczywiste liczby; (1.16) — celowa funkcja; (1.17) —(1.21) —ograniczenia; õ=(õ1;.; xn) —plan zadania.Symetryczn¹ form¹ zapisu ZLP nazywamy zadaniemax Z = c1*x1+c2*x2+.+cn*xn = (1.22)przy ograniczeniach:ai1*x1+ai2*x2+.+ ain*xn £ bi, lub , (i=1,2,.m1) (1.23)xj ³ 0, j=1,2,.n (1.24)lub zadaniemin Z = c1*x1+c2*x2+.+cn*xn = (1.25)przy ograniczeniach:ai1*x1+ai2*x2+.+ ain*xn ³ bi, lub , (i= 1,2,.m) (1.26)xj ³ 0, j=1,2,.n (1.27)Kanoniczn¹ form¹ zapisu ZLP nazywamy zadaniemax Z = c1*x1+c2*x2+.+cn*xn = (1.28)przy ograniczeniach:ai1*x1+ai2*x2+.+ ain*xn = bi, lub , (i=1, 2,.m) (1.29)xj ³ 0, j=1,2,.n (1.30)Jak by³o pokazane wy¿ej, zadanie programowania liniowego mo¿e byæ zapisane wmacierzowej postaci.Jeœli jest to konieczne, zadanie minimalizacji mo¿na zamieniæ zadaniemmaksymalizacji i odwrotnie.Dla funkcji jednej zmiennej to twierdzenie jestrzeczywiste.Jeœli õ* — punkt minimum funkcji y=f{x), wtedy dla funkcji ó=-f{x) bêdzie onpunktem maksimum, bo wykresy funkcji f(x) i -f(x) s¹ symetryczne odnoœnie osiodciêtych, tj.min{f(x*)}= -max{-f(x*)}.To samo ma miejsce w przypadku funkcji n zmiennych:min{f(x1* , x2* ,., xn*)}= -max{-f(x1* , x2* ,., xn*)}.W zadaniach programowania liniowego wiêkszoœæ ograniczeñ stawia siê wnierównoœciach.Najczêœciej metody ZPL wykorzystuje siê tylko do zadañzapisanych w kanonicznej postaci.Zrealizowaæ przejœcie do ZLP zapisanych w kanonicznej postaci mo¿nanastêpuj¹co.Niech, na przyk³ad, wyjœciowa ZLP ma postaæ:max Z = c1*x1+c2*x2+.+cn*xn = (1.31)przy ograniczeniach:ai1*x1+ai2*x2+.+ ain*xn £ bi, lub , (i=1,2,.m1) (1.32)ai1*x1+ai2*x2+.+ ain*xn ³ bi, lub , (i= m1+1, m1+2,.m) (1.33)xj ³ 0, j=1,2,.n (1.34)Przekszta³cimy jego do kanonicznej postaci.Wprowadzimy ò dodatkowych(swobodnych, bilansowych) nieujemnych zmiennych xn+i ³ 0, (i=1,2,.m).Dlatego, ¿eby nierównoœci postaci £ w (1.32) przekszta³ciæ w równoœci, do ichlewych stron dodamy swobodne zmienne xn+i (i=1,2,.m1), po czym uk³adnierównoœci (1.32) przyjmie postaæ:ai1*x1+ai2*x2+.+ ain*xn + xn+i = bi, lub , (i=1,2,.m1) (1.35)¯eby nierównoœci postaci ³ w (1.33) przekszta³ciæ w równoœci, od ich lewychstron odejmiemy swobodne zmienne xn+i (i= m1+1, m1+2,.m).Otrzymamy:ai1*x1+ai2*x2+.+ ain*xn - xn+i = bi, lub , (i= m1+1, m1+2,.m) (1.36)Uk³ad równañ (1.35) ((1.36)) razem z warunkiem, ¿e zmienne swobodne s¹nieujemne nazywa siê ekwiwalentnym uk³adu nierównoœci (1.32) ((1.33)).Swobodne zmienne xn+i (i=1,2,.m) w celow¹ funkcjê wprowadzamy zewspó³czynnikami równymi zeru.Otrzymamy zadanie:max Z = c1*x1+c2*x2+.+cn*xn + 0* xn+1 +.+ 0* xn+m = + (1.37)ai1*x1+ai2*x2+.+ ain*xn + xn+i = bi, lub , (i=1,2,.m1) (1.38)ai1*x1+ai2*x2+.+ ain*xn - xn+i = bi, lub , (i= m1+1, m1+2,.m)(1.39)xj ³ 0, j=1,2,.n, xn+i ³ 0, i=1,2,.m (1.40)Zadania (1.37) - (1.39) maj¹ kanoniczn¹ postaæ.Zadania (1.31) - (1.34) i(1.37) - (1.40) s¹ œciœle powi¹zane pomiêdzy sob¹.Twierdzenie 1.1.Ka¿demu dopuszczalnemu rozwi¹zaniu (õ10;.; õn0) zadania(1.31) - (1.34) odpowiada ca³kiem okreœlone dopuszczalne rozwi¹zanie (õ10;.;õn0 ; õn+10;.; õn+m0) zadania (1.37) - (1.40), gdzie xn+i ³ 0, (i=1,2,.m), i odwrotnie, ka¿demu dopuszczalnemu rozwi¹zaniu (õ10;.; õn0 ; õn+10;.; õn+m0) zadania (1.37) - (1.40) odpowiada dopuszczalne rozwi¹zanie (õ10;.; õn0) zadania (1.31) — (1.34).Tak jak swobodne zmienne õn+i0 wchodz¹ w celow¹ funkcjê (1.37) zewspó³czynnikami równymi zeru, to znaczenia celowych funkcji (1.31) i (1.37) dlaodpowiednich dopuszczalnych rozwi¹zañ (õ10;.; õn0) i (õ10;.; õn0 ; õn+10;.; õn+m0) s¹ jednakowe.St¹d wnioskujemy , ¿e celowe funkcje (1.31) i (1.37)na zbiorze odpowiednich dopuszczalnych rozwi¹zañ osi¹gaj¹ ekstremalne znaczeniajednoczeœnie.Optymalnemu rozwi¹zaniu (õ1*;.; õn*) zadania (1.31) - (1.34)odpowiada optymalne rozwi¹zanie (õ1*;.; õn* ; õn+1*;.; õn+m*) zadania(1.37) - (1.40).Podkreœlimy ekonomiczny sens swobodnych zmiennych.W ka¿dym zadaniu s¹ oneœciœle zwi¹zane z jego ekonomiczn¹ zawartoœci¹.Na przyk³ad, dla zadania (1.2) - (1.4) o najlepszym wykorzystaniu zasobówswobodna zmienna pokazuje wielkoœæ niewykorzystanego zasobu.Dla zadaniach o mieszankach (1.5) - (1.7) swobodna zmienna pokazuje konsumpcjêodpowiedniego sk³adnika po¿ywnego w optymalnym planie powy¿ej normy.W niektórych produkcyjno-ekonomicznych sytuacjach, nie na wszystkie zmiennenak³adaj¹ siê warunki, ¿e nie s¹ one ujemne.W podobnych sytuacjach, nawetjeœli ograniczenia przedstawione s¹ w postaci równañ, zadanie nie bêdziekanonicznym.Dla przedstawienia takiego zadania w kanonicznej postaci ka¿d¹zmienn¹ õk, która ma warunek nieujemny, zast¹pimy ró¿nic¹ dwóch nieujemnychzmiennych õ’k i õ”k, tj.õk = õ’k - õ”k, gdzie õ’k ³ 0, õ”k³ 0.Niech ranga macierzy symetrycznego zadania programowania liniowego (1.29) jestrówna r i r
[ Pobierz całość w formacie PDF ]