線性規(guī)劃圖解法幾何意PPT學習教案

1、會計學1 線性規(guī)劃圖解法幾何意線性規(guī)劃圖解法幾何意 n ,j,x m,i,bxa xczmax :M j n j ijij n j jj 210 21 1 1 1 約束條件： 目標函數(shù)： 第1頁/共55頁 n,j; b b b b; a a a P; x x x X ;c ,c ,cC n,j,x bxP CXzmax:M m mj j j j n n j n j jj 21 210 2 1 2 1 2 1 21 1 1 約束條件： 目標函數(shù)： 第2頁/共55頁 () . . 0 max zCX LPAXb st X 則標準形式的矩陣表示：則標準形式的矩陣表示： mnm n aa aa A .

2、 . . 1 1111 (.) T m bbb， ， 1 (.) n Ccc， ， 1 (.)T n Xxx， ， 若令若令 A稱為系數(shù)矩陣稱為系數(shù)矩陣 b稱為資源向量稱為資源向量 C稱為價值向量稱為價值向量 X稱為決策變量向量稱為決策變量向量 第3頁/共55頁 zz 1.當目標函數(shù)為求極小值當目標函數(shù)為求極小值,即即 min z=c1x1+c2x2+.+cnxn 因為求因為求min z 等價于等價于max (-z) 故可令故可令 則目標函數(shù)化為則目標函數(shù)化為: 2.當右端項當右端項 bim)其秩為其秩為m,B是矩陣是矩陣A中中 的一個的一個mm階的滿秩子矩陣階的滿秩子矩陣,稱稱B是線性規(guī)劃是

3、線性規(guī)劃 問題的一個基問題的一個基。 第10頁/共55頁 mmm m aa aa B . . . 1 111 =(P1,P2,.,Pm ) B中的每一列向量中的每一列向量Pj(j=1,2,.m)稱為基向稱為基向 量量 基向量：基向量： 與基向量與基向量Pj的對應的變量的對應的變量xj 稱為基變稱為基變 量量 基 變 量基 變 量 ： 非基變量：非基變量： 線性規(guī)劃中的其余變量稱為非基向量線性規(guī)劃中的其余變量稱為非基向量 5.基解基解 設設X是（是（LP）的約束方程）的約束方程AX=b的一個解，的一個解，B是一是一 個基，個基，若若X中對應基中對應基B的非基變量取值全為零的非基變量取值全為零，則

4、，則 稱稱X為為(LP)關(guān)于關(guān)于基基B的基解的基解，記作，記作X(B) 不妨設基為不妨設基為 基解的個數(shù)不會超過 個 m n C 第11頁/共55頁 可證明可證明:一個基唯一地確定一個基解一個基唯一地確定一個基解. 6.基可行解：基可行解： 若基解若基解X(B)滿足非負條件滿足非負條件X(B)0， 則稱基解則稱基解X(B)為基可行解為基可行解 7.基最優(yōu)解：基最優(yōu)解： 若基可行解若基可行解X(B)是是(LP)的最優(yōu)解的最優(yōu)解,則則 稱稱X(B)為為(LP)的的基最優(yōu)解基最優(yōu)解. 最優(yōu)基：最優(yōu)基：基最優(yōu)解對應的可行基 基最優(yōu)解對應的可行基B稱為最優(yōu)基稱為最優(yōu)基. 可行基：可行基：基可行解對應的基

5、 基可行解對應的基B稱為可行基稱為可行基. 注注:基解沒有基解沒有X0的限制的限制,故基解不一定是可行解故基解不一定是可行解. X(B)= N B X X 0 1b B 第12頁/共55頁 8.退化解：退化解：若基本可行解若基本可行解X的所有基變量的值均大于的所有基變量的值均大于0 ，則稱，則稱X是非退化的是非退化的，否則稱，否則稱X為退化的為退化的。 若若(LP)的所有基本可行解都是非退化的所有基本可行解都是非退化 的的, 則稱則稱線性規(guī)劃問題是非退化的線性規(guī)劃問題是非退化的. 第13頁/共55頁 考慮線性規(guī)劃問題考慮線性規(guī)劃問題： 約束方程的系數(shù)矩陣約束方程的系數(shù)矩陣A 12345 123

6、 14 25 12345 23000 28 ()416 . . 412 ,0 max Zxxxxx xxx LPxx st xx x x x x x 10040 01004 00121 A 很顯然很顯然A中的后中的后3列是線性無關(guān)的，它們構(gòu)成一個基列是線性無關(guān)的，它們構(gòu)成一個基 1345 (,)BP P PE 基基B1對應的對應的變量變量x3,x4,x5是是基變量基變量, x1,x2是是非基變量非基變量 第14頁/共55頁 若令若令： 得得 12 0,xx 0,0,8,16,12 T X 該解是對應該解是對應B1的基解，它是基可行解，的基解，它是基可行解，B1是可行基是可行基 ； 如取如取 2

7、123 121 ( ,)400 040 BP P P 是（是（LP）的一個基，）的一個基， 若令若令： 4 5 0,xx 基基B2對應的對應的變量變量x1,x2,x3是是基變量，基變量， ,x4,x5是是非基變量非基變量 得得 4,3,-2,0,0 T X 該解是對應該解是對應B2的基解，它不是基可行解，的基解，它不是基可行解，B2不是可不是可 行基；行基； 第15頁/共55頁 AX=b的解的解 基解基解 若非基變量為若非基變量為 0 基可行解基可行解 基 最 優(yōu)基 最 優(yōu) 解解 B是是A的的m階子矩階子矩 陣陣 基基 B 若若 |B| 0 可 行 基可 行 基 B 當當B - 1b 0 最

8、優(yōu) 基最 優(yōu) 基 B 若基變量取非負若基變量取非負 若對應目標函數(shù)若對應目標函數(shù) 值最值最 優(yōu)優(yōu) 第16頁/共55頁 非可行解非可行解 可可 行行 解解 基基 可可 行行 解解 基基 解解 基基 可可 行行 基基 最最 優(yōu)優(yōu) 基基 第17頁/共55頁 第18頁/共55頁 凸集凸集: 如果集合如果集合K中任意兩個點中任意兩個點X(1),X(2),其連線上的所其連線上的所 有點也都是集合有點也都是集合K中的點中的點,則稱集合則稱集合K為凸集為凸集. 或或K=X|X=X(1)+(1-)X(2), X(1) K,X(2) K,01 定理定理: D xRn| Ax=b,x0是凸集是凸集 頂點頂點:凸集凸

9、集K中滿足下列條件的中滿足下列條件的點點X稱為頂點稱為頂點:如如 果果K中不存在任何兩個不同的點中不存在任何兩個不同的點X1,X2,使使X 成為這兩個點連線上的一個點成為這兩個點連線上的一個點. 定理定理: 有限個凸集的交集還是有限個凸集的交集還是凸集凸集 凸組合凸組合:設設 )()2()1( ,., k XXX是是n維歐氏空間中的維歐氏空間中的k個點個點 )()2( 2 )1( 1 . k k XXXX 10,1 ii 則稱則稱X是的凸組合是的凸組合 )()2()1( ,., k XXX 第19頁/共55頁 凸集凸集 不是凸集 頂點 不是凸集 第20頁/共55頁 定 理定 理 1 若線性規(guī)劃

10、問題存在可行解若線性規(guī)劃問題存在可行解,則問題的則問題的 可行域是凸集可行域是凸集. 定 理定 理 2 若線性規(guī)劃問題有非零可行解，則其必若線性規(guī)劃問題有非零可行解，則其必 有基可行解。有基可行解。 定 理定 理 4 若線性規(guī)劃問題有最優(yōu)解，一定存在一若線性規(guī)劃問題有最優(yōu)解，一定存在一 個基可行解是最優(yōu)解。個基可行解是最優(yōu)解。 定理定理3 線性規(guī)劃問題的基可行解線性規(guī)劃問題的基可行解X X對應線性規(guī)劃對應線性規(guī)劃 問題可行域問題可行域( (凸集凸集) )的頂點的頂點. . 引理引理1 線性規(guī)劃的可行解線性規(guī)劃的可行解X(x1,x2,xn)T為基為基 可行解的充要條件是可行解的充要條件是X的正分

11、量所對應的的正分量所對應的 系數(shù)列向量是線性無關(guān)的。系數(shù)列向量是線性無關(guān)的。 第21頁/共55頁 第22頁/共55頁 開始于某一個可行基及其對應的基開始于某一個可行基及其對應的基 可行解，從一個基可行解迭代到另一個基可行解，從一個基可行解迭代到另一個基 可行解，并且使目標函數(shù)值不斷增大，經(jīng)可行解，并且使目標函數(shù)值不斷增大，經(jīng) 過有限步必能求得線性規(guī)劃問題的最優(yōu)解過有限步必能求得線性規(guī)劃問題的最優(yōu)解 或者判定線性規(guī)劃問題或者判定線性規(guī)劃問題無有界的最優(yōu)解無有界的最優(yōu)解（ 無界解）。無界解）。 第23頁/共55頁 考慮線性規(guī)劃問題考慮線性規(guī)劃問題： 約束方程的系數(shù)矩陣約束方程的系數(shù)矩陣A 1234

12、5 123 14 25 12345 23000 28 ()416 . . 412 ,0 max Zxxxxx xxx LPxx st xx x x x x x 10040 01004 00121 A 很顯然很顯然A中的后中的后3列是線性無關(guān)的，它們構(gòu)成一個基列是線性無關(guān)的，它們構(gòu)成一個基 345 (,)BP P PE 基基B對應的對應的變量變量x3,x4,x5是是基變量，則基變量，則 第24頁/共55頁 即即： 將它們代入目標函數(shù)中得將它們代入目標函數(shù)中得 25 14 213 412 416 28 xx xx xxx 12 023zxx 令令非基變量非基變量x1=x2=0,得目標值得目標值z0

13、 一個基可行解一個基可行解X(0)(0,0,8,16,12) 為了使目標函數(shù)能更大，為了使目標函數(shù)能更大，讓讓x2變成基變量變成基變量，原基變量原基變量 的的x3，x4，x5要有一個變?yōu)榉腔兞恳幸粋€變?yōu)榉腔兞?當當x1=0,由最上式得由最上式得 0412 016 028 25 4 23 xx x xx 從上式可看出，當從上式可看出，當x2=3仍可保證仍可保證所有變量非負所有變量非負， 并使并使目標函數(shù)增大目標函數(shù)增大 第25頁/共55頁 為了得到以為了得到以x3,x4,x2為基變?yōu)榛?量的一個基可行解，則對量的一個基可行解，則對 左邊方程中的左邊方程中的x2與與x5互換互換 得得 25

14、 14 213 412 416 28 xx xx xxx 3 415 92zxx 再令再令非基變量非基變量x1=x5=0,得目標值得目標值z9 一個基可行解一個基可行解X(0)(0,3,2,16,0) 為了使目標函數(shù)能更大，為了使目標函數(shù)能更大，讓讓x1變成基變量，原基變量變成基變量，原基變量 的的x3，x4，x2要有一個變?yōu)榉腔兞恳幸粋€變?yōu)榉腔兞?12 315 41 14 25 2 164 3 xxx xx xx 目標函數(shù)變?yōu)槟繕撕瘮?shù)變?yōu)?第26頁/共55頁 這樣如此下去，可得這樣如此下去，可得 34 141.50.125zxx X(2)(2,3,0,8,0) 為了使目標函數(shù)能更大，為

15、了使目標函數(shù)能更大，讓讓x1變成基變量變成基變量，原基變量原基變量 的的x3，x4，x2要有一個變?yōu)榉腔兞恳幸粋€變?yōu)榉腔兞?此時目標函數(shù)變?yōu)榇藭r目標函數(shù)變?yōu)?X(3)(4,2,0,0,4) 由于目標函數(shù)中的變量系數(shù)都小于等于由于目標函數(shù)中的變量系數(shù)都小于等于0， 所以所以X(3)（4,2,0,0,4)為最優(yōu)解，為最優(yōu)解， 最優(yōu)值最優(yōu)值z 14 下面從幾何角度分析一下最優(yōu)解的尋求過程： 第27頁/共55頁 幾何意義：頂點轉(zhuǎn)移，目標增大 第28頁/共55頁 1.確定初始基可行解：確定初始基可行解： 對標準型的LP問題 1 max 1.1 . . 0,1,2,1.2 n jj j j zCX

16、P xb st xjn 在約束條件(1.1)的變量的系數(shù)矩陣中總會存在一個單位矩陣。 (2)當線性規(guī)劃的約束條件都為號時，其松弛變量對應的系數(shù)列向量構(gòu)成的矩陣即為單位陣； (3)當線性規(guī)劃的約束條件為或的情況，引入人工變量后也可實現(xiàn)。 (1)系數(shù)矩陣中可以直接觀察得到一個單位子矩陣； 第29頁/共55頁 2. 從一個基可行解轉(zhuǎn)換為相鄰的基可行解從一個基可行解轉(zhuǎn)換為相鄰的基可行解 ： 定義：兩個基可行解稱為相鄰的，如果他們之間變換且僅變換一個基變量。 設初始基可行解為： 0000 12 ,0,0 T m Xxxx 可知： 0 1 1.3 m ii i Pxb 其對應的系數(shù)矩陣的增廣矩陣為： 12

17、1 1,111 1 2,122 2 ,1 100 010 001 mmjn mjn mjn m mmjmn m PPPPPPb aaab aaab aaab 第30頁/共55頁 易得： 11 1.41, mm jijijiji ii Pa PPa Pjmn (1.3)+(1.4) (0), 得 0 1 1.5 m iijij i xaPPb 令： 1000 1122 , ,0 T jjmmj Xxaxaxa 顯然： 1 AXb 為使X(1)成為可行解，令： 00 min01.6 il ij i ijlj xx a aa 可證明:將(1.6)式代回到X(1)中,X(1) 為基可行解，此時完成了從

18、一個基可行解到另一個與其相鄰的基可行解的轉(zhuǎn)換。 第31頁/共55頁 證明：將與變量 x1,xl-1,xl+1,xm,xj對應的列向量 ，經(jīng)重新排列后加上b列有如下形式： 1211 11 22 11, 11, 10000 01000 00100 00000 00010 000001 ljlm j j llj llj llj m PPPPPP b ba ba ba ba ba b 因為 P1,P2, ,Pl-1， Pj,Pl+1,Pm 線性無關(guān)，故X(1)為基可行解。 第32頁/共55頁 3.最優(yōu)性檢驗與解的判別最優(yōu)性檢驗與解的判別 ： 將2中的基可行解X(0)與X(1)分別代入目標函數(shù)，得 00

19、 1 m ii i zc x 稱為檢驗數(shù) j 10 1 () m iiijj i zc xac 0 11 mm jiijii ii cc ac x 0 0 j z 第33頁/共55頁 (1)當所有的j0時 ，現(xiàn)行基可行解為最優(yōu)解； 當所有的j0且對應的列向量Pj 0時，該線性規(guī)劃 問題有無界解； (4)對線性規(guī)劃問題無可行解的判別將在后面討論。 (2)當存在某個j0且對應的列向量Pj 中有正分量時，說明 目標函數(shù)值還可以增大，需要進行基變換； 第34頁/共55頁 第35頁/共55頁 第一步：第一步：求初始基可行解，列出初始單純形表求初始基可行解，列出初始單純形表 XB bx1 x2 . xm

20、xm+1 . xj . xn x1 x2 . xm b1 b2 . bm 1 0 . 0 a1,m+1 . a1j . a1n 0 1 . 0 a2,m+1 . a2j . a2n . . . . . . . . . 0 0 . 1 am,m+1 . amj . amn c c1 c2 . cm cm+1 . cj . cn 首先寫出關(guān)于價值系數(shù)的表：（非單純形表） 第36頁/共55頁 1,1 1 m mii m i cc a 將基變量下方的價值系數(shù)通過變換化為零，得初始單純形表將基變量下方的價值系數(shù)通過變換化為零，得初始單純形表 XB bx1 x2 . xm xm+1 . xj . xn x

21、1 x2 . xm b1 b2 . bm 1 0 . 0 a1,m+1 . a1j . a1n 0 1 . 0 a2,m+1 . a2j . a2n . . . . . . . . . 0 0 . 1 am,m+1 . amj . amn -z 0 0 . 0 . . 1 m jiij i cc a 1 m niin i cc a 1 m i i i cb 第37頁/共55頁 第二步：第二步：最優(yōu)性檢驗最優(yōu)性檢驗 (1)當所有的j0時 ，現(xiàn)行基可行解為最優(yōu)解； 當所有的j0且對應的列向量Pj 0時，該線性規(guī)劃 問題有無界解； (3)當存在某個j0且對應的列向量Pj 中有正分量時，說 明目標函數(shù)

22、值還可以增大，需要進行基變換。 第38頁/共55頁 第三步：換基迭代第三步：換基迭代 (1)確定進基變確定進基變 量量 選擇檢驗數(shù)最大的非基變量為進基變量選擇檢驗數(shù)最大的非基變量為進基變量 k=max j| j0,j=1,2,.,n則則xk為進基變量為進基變量 (2)確定出基變確定出基變 量量 根據(jù)下列原則確定出基變量根據(jù)下列原則確定出基變量 則則l所對應的基變量所對應的基變量xl為出基變量為出基變量 元素元素alk為為軸心項軸心項(或稱為主元素或稱為主元素) (3)以以alk為軸心項進行換基迭代為軸心項進行換基迭代 即利用矩陣的初等行變換即利用矩陣的初等行變換 min|0,1,2,., il

23、 ik iklk bb aim aa 把元素把元素alk所在的列化為單位向量所在的列化為單位向量.得到新的單純形表得到新的單純形表 第39頁/共55頁 第四步：第四步：重復第二、三步，一直到計算結(jié)束為止。重復第二、三步，一直到計算結(jié)束為止。 第40頁/共55頁 例例 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃 12 12 1 2 12 max23 28 ()416 . . 412 ,0 zxx xx LPx s t x xx 解解 : 將原問題化為標準形為將原問題化為標準形為 ： 12 123 14 25 max2 28 416() . . 412 0(1,2,3,4,5) j zxx

24、xxx xxLP s t xx xj 得單純形初表為得單純形初表為: 第41頁/共55頁 XB b x1 x2 x3 x4 x5 x3 x4 x5 8 16 12 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 z 0 2 3 0 0 0 T(B1) x3 x4 x2 -z 21 0 1 0 -1/2 164 0 0 1 0 301 001/4 -9 2 000-3/4 T(B2) 第42頁/共55頁 XB b x1 x2 x3 x4 x5 x3 x4 x2 2 16 3 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4 -z -9 2 0 0 0 - 3/4

25、T(B2) x1 x4 x2 -z 21 0 1 0 -1/2 80 0 -4 1 2 301 0 01/4 -1300 -201/4 T(B3) 第43頁/共55頁 XB b x1 x2 x3 x4 x5 x1 x4 x2 2 8 3 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4 -z - 13 0 0 -2 0 1/4 T(B3) x1 x5 x2 -z 41 0 0 1/4 0 40 0 -2 1/2 1 201 1/2 -1/8 0 -1400-3/2 -1/8 0 T(B4) 第44頁/共55頁 在單純形終表中，x3,x4為非基變量，所有非基變量檢驗數(shù) 均小

26、于零，故該線性規(guī)劃問題有唯一最優(yōu)解唯一最優(yōu)解 X*=(4,2,0,0,4)T ，最優(yōu)值為 Z*=14。 第45頁/共55頁 例例2: 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃 解解 : 將原問題化為標準形為將原問題化為標準形為 ： 12 1 2 12 12 max2 4 ()3 . . 28 ,0 zxx x LPx s t xx xx 12 13 24 125 max2 4 3() . . 28 0(1,2,3,4,5) j zxx xx xxLP st xxx xj 得單純形初表為得單純形初表為: 第46頁/共55頁 XB b x1 x2 x3 x4 x5 x3 x4 x5 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 1 -z 0 1 2 0 0 0 T(B1) x3 x2 x5 -z 41 0 1 0 0 30 1 0 1 0 210 0-21 -6 100-20 T(B2) 第47頁/共55頁 XB b x1 x2 x3 x