1、 1.1 1.1 線性規(guī)劃模型的三要素：線性規(guī)劃模型的三要素：p14p14（舉例）（舉例） nn xcxcxcz 2211 max(min) （1.1） ),2, 1(0 )( )( )( 2211 22222121 11212111 njx bxaxaxa bxaxaxa bxaxaxa j mnmnmm nn nn （1.2） （1.3） 1 1, , 2,.xj。 。 1 1 max(min) () (1,2,) 0,1,2, n jj j n ijji j j zc x a xb im xjn m ax (m in ) 0 zC X A Xb X 1122 11112211 21122

2、222 1122 max 01, 2,.01, 2, nn nn nn mmmnnm ji zc xc xc x axaxaxb axaxaxb axaxaxb xjn bim S.T 1 1 max (1,2,) 0(1,2, ) n jj j n ijji j j zc x a xb im xjn 1) S.T 2) 令 12 (,) n CCCC 1 2 n x x X x 1 2 m b b b b 1 2 j j j mj a a P a 0 max 1 j n j jj x bxp cxz 則 max 0 zCX AXb X 則 令 A= a11 a1n a m 1 amn min

3、max()zCXzCXzz 令 1122iiinni a xaxaxb 1122iiinnnli a xaxa xxb 1 12 2tttn nt a xa xa xb 1 12 2tttn nn tt a xa xa xxb ,0 jj xx jjj xxx 1122 1122 () iiinni iiinni a xa xa xb a xa xa xb 則 ， 1 () ni xb 1.4 1.4 舉例舉例 線性規(guī)劃的定義線性規(guī)劃的定義 （1）.尋求最優(yōu)解（工作目標）； （2）.客觀條件有限制（約束條件）； （3）.目標函數(shù)，約束條件均為線性。 線性規(guī)劃中數(shù)學模型建立的三個步驟線性規(guī)劃中數(shù)

4、學模型建立的三個步驟 （1）.確定變量 （2）.確定約束條件 （3）.確定目標函數(shù) 線性規(guī)劃的標準形式 1. 標準形式的特點 2. 非標準型向標準型的轉化 （1）.目標函數(shù)：MAX （1）.MIN （2）.約束方程右端常數(shù)：非負 （2）.約束方程右端常數(shù)為負值 （3）.變量符號：非負 （3）.變量符號不確定 自由變量 （4）.約束條件：等號 （4）.不等式約束 例:將下列線性規(guī)劃問題劃為標準形式：p16 MINS=X1+3X2 S.T. 6X1+7X28 -X1+3X2-6 X1-X2=3 X10 2 線性規(guī)劃一般算法 對于只有對于只有2個決策變量的線性規(guī)劃模型可以采用圖解法求解，個決策變量的

5、線性規(guī)劃模型可以采用圖解法求解， 其求解步驟如下：其求解步驟如下： （1）根據(jù)約束方程在圖上標畫出可行解區(qū)域；）根據(jù)約束方程在圖上標畫出可行解區(qū)域； （2）設定一個初始解）設定一個初始解Z0，按照目標函數(shù)繪制其等值線；，按照目標函數(shù)繪制其等值線； （3）平行于）平行于Z0等值線，繪制通過可行解區(qū)域邊界線交點等值線，繪制通過可行解區(qū)域邊界線交點 的等值線，由此確定最優(yōu)解。的等值線，由此確定最優(yōu)解。 2 線性規(guī)劃一般算法 12 12 12 2 12 m a x34 6 28 3 ,0 zxx xx xx x xx 例：s.t. x1 x2 X2=3 X2=-x1+6 X2=-1/2x1+4 X2=

6、-3/4x1+1/4z (0,3) (2,3) (4,2) (6,0) 12 12 1 2 12 :56 :5 5 3 0,0 MaximizeZxx Subject Toxx x x xx 。 例例2.3 按照上述三個步驟可以用圖解法求解該例，詳見按照上述三個步驟可以用圖解法求解該例，詳見P10。 5 4 3 2 1 0 0 1 2 3 4 5 x x2 x x1 Z0 0=5=5 12 5xx 1 5x 2 3x 12 56Zxx 可行解域可行解域 （5，3） 圖解法求解例圖解法求解例2.3 求解點求解點 Z*=43 12 6xx 線性規(guī)劃問題除了有唯一解的線性規(guī)劃問題除了有唯一解的 情況

7、外，有時還會出現(xiàn)下列情情況外，有時還會出現(xiàn)下列情 況：況： （1 1）無窮多最優(yōu)解（多重解）無窮多最優(yōu)解（多重解） 若將例若將例1 1的目標函數(shù)變?yōu)榈哪繕撕瘮?shù)變?yōu)?maxz=2x1+2x2maxz=2x1+2x2，則等值線的斜，則等值線的斜 率為率為1 1與的邊界線平行，當與的邊界線平行，當z z 由小變大時，將與由小變大時，將與ABAB段重合，段重合， ABAB段上任一點（可行解）都使段上任一點（可行解）都使 z z取相同最大值取相同最大值1212。x1 x2 X2=3 (0,3) (2,3) (4,2) (6,0) A B 12 12 12 12 max32 2 5 ,0 zxx xx x

8、x x x s.t x1x2=5 X1+x2=2 12 12 12 12 max2 3 3 ,0 zxx xx xx x x s.t 3 21 xx (0,-3) (0,3) (3,0) 12 3xx 對解的討論： .唯一解 .無窮解 .無解： 可行域空集， 可行域無界 第三節(jié) 線性規(guī)劃問題的基本性質 一基本概念p19 1可行域約束條件構成的解的空間約束條件構成的解的空間 2可行解滿足約束條件的解，所有可行解滿足約束條件的解，所有可行解 的集合構成可行域的集合構成可行域 3最優(yōu)解滿足目標函數(shù)的可行解滿足目標函數(shù)的可行解 4基 0X ： max ZCX AXb 例2-2 某線性規(guī)劃問題的約束方程

9、為 X1+3X2+4X3+X4=8 2X1+2X2+X3+X5=1 Xj0, j=1,2,3,4,5 n mnmm n PPP aaa aaa A , 21 21 11211 A為為m n矩陣（矩陣（ m為約束方程個數(shù)，為約束方程個數(shù)，n為變量個數(shù)）為變量個數(shù)） 約束方程組約束方程組 系數(shù)矩陣系數(shù)矩陣 n mnmm n PPP aaa aaa A , 21 21 11211 在在 A中取子矩陣中取子矩陣D，| D | 0，則稱，則稱D為該線性規(guī)劃問題為該線性規(guī)劃問題 的一個基的一個基 對應的對應的Pj為基向量為基向量 Xj為基變量，其余變量稱為非基變量為基變量，其余變量稱為非基變量 例1 某線

10、性規(guī)劃問題的約束方程組為某線性規(guī)劃問題的約束方程組為 X1+3X2+4X3+X4=8 2X1+2X2+X3+ X5=1 Xj 0, j=1,2,3,4,5 對應的系數(shù)矩陣對應的系數(shù)矩陣 1 0 1 2 2 0 1 4 3 1 A 1 0 1 2 2 0 1 4 3 1 A 取子矩陣取子矩陣D1， 1 0 0 1 1 D0 1 DD1為一個基 取子矩陣取子矩陣D2， 2 2 3 1 1 D0 1 D D2為一個基 在在 A中取子矩陣中取子矩陣D，| D | 0，則稱，則稱D為該線性規(guī)劃為該線性規(guī)劃 問題的一個基問題的一個基 對應的對應的Pj為基向量為基向量 Xj為基變量，其余變量稱為非基變量為基

11、變量，其余變量稱為非基變量 一般線性規(guī)劃問題的基不唯一。一般線性規(guī)劃問題的基不唯一。 對于對于D1 ，P4、P5為基向量，基變量為為基向量，基變量為X4、X5，X1、X2、X3為非基變量為非基變量 對于對于D2 ， P1、P2為基向量，基變量為為基向量，基變量為X1、X2，X3、X4、X5為非基變量為非基變量 5基解基解 令非基變量為令非基變量為0，可以從約束方程中求解出一個解，該，可以從約束方程中求解出一個解，該 解稱為基解解稱為基解 X1+3X2+4X3+X4=8 2X1+2X2+X3+ X5=1 Xj0, j=1,2,3,4,5 對于對于D1 ，基變量為，基變量為X4、X5，X1、X2、

12、X3為非基變量，令為非基變量，令 X1、X2、X3=0， X4 = 8、X5 = 1 對于對于D2 ，基變量為，基變量為X1、X2，X3、X4、X5為非基變量，令為非基變量，令 X3、X4、X5 =0， X1 = -13/4 、X2=15/4 6基本可行解：基本可行解：滿足非負條件滿足非負條件 7可行基：可行基：對應基本可行解的基，如對應基本可行解的基，如D1 對于對于D1 ，基變量為，基變量為X4、X5，X1、X2、X3為非基變量，令為非基變量，令 X1、X2、X3=0， X4 = 8、X5 = 1 對于對于D2 ，基變量為，基變量為X1、X2，X3、X4、X5為非基變量，令為非基變量，令

13、X3、X4、X5 =0， X1 = -13/4 、X2=15/4 12 12 12 2 12 max34 6 28 3 ,0 zxx xx xx x x x 12 123 124 25 12345 m ax34 6 28 3 ,0 zxx xxx xxx xx xxxxx 1 1 1 0 0 Amn= 1 2 0 1 0 r（Amn）=3 0 1 0 0 1 345 (,)(6,8,3)xxx 1 0 0 B1= 0 1 0 0 0 1 123 (,)(2,3,1)xxx B2= 1 2 0 0 1 0 1 1 1 124 (,)(3,3,1)xxx B3= 1 2 1 0 1 0 1 1 0

14、 125 (,)(4, 2,1)xxx B4= 1 2 0 0 1 1 1 1 0 234 ( ,)(3,3,2)x x x 235 ( , , )(4,2, 1)x x x 1 1 0 1 1 0 B5= 2 0 1 B6= 2 0 0 1 0 0 1 0 1 245 ( ,)(6, 4, 3)x x x 135 ( , ,)(8, 2,3)x x x 1 0 0 1 1 0 B7= 2 1 0 B8= 1 0 0 1 0 1 0 0 1 145 ( , , )(6,2,3)x x x 124 ( ,)x x x ( ) 1 0 0 1 1 0 B9= 1 1 0 B10= 1 0 1 0

15、0 1 0 0 0 B1B9都是基，而 B10非基。 1111 2122 1 1 (,) jm jm jm mmjmm aaa aaa Bppp aaa 1 2 j j j mj a a p a 則 1 B 2 B 0 11 mn jjjj jjm p xbp x 1 2 m m N mn x x x X 1 2 B m x x x X B N X X X= 12 (,) m Bp pp 12 0 mmn xxx B0 12 ( ,0,0)T m Xx xx Cm n 。 ： 12 459 0,0,6,8,3 ,2,31,0,0 , 4,2,0,0,1 ,0,3,3,2,0 ,6,0,0,2,

16、3 XX XXX 19 ,BB 二、基本變量與非基本變量基本變量與非基本變量 T bnbn AXA AX XB 由于約束方程數(shù)由于約束方程數(shù)m一般都小于決策變量數(shù)一般都小于決策變量數(shù)n，故線性規(guī)劃模型都沒有唯一，故線性規(guī)劃模型都沒有唯一 解，可將決策變量分為基本變量集合和非基本變量集合，分別記為解，可將決策變量分為基本變量集合和非基本變量集合，分別記為xb和和xn， 基本變量集合指在某一個約束方程中系數(shù)為基本變量集合指在某一個約束方程中系數(shù)為1的而在其他約束方程中系數(shù)的而在其他約束方程中系數(shù) 為為0的變量群，其變量數(shù)為的變量群，其變量數(shù)為m個?；咀兞恳酝獾臎Q策變量為非基本變量，個?；咀兞恳?/p>

17、外的決策變量為非基本變量， 有有n-m個。個。 約束方程可改寫為：約束方程可改寫為： 故：故： 1 bbnn XABA X 參照圖解法求解，當在可行解域的極點時，所有非基本變量均為參照圖解法求解，當在可行解域的極點時，所有非基本變量均為0，此時：，此時： 1 bb XAB 設非基本變量為設非基本變量為0時求解得到的基本變量解稱之為基本解，時求解得到的基本變量解稱之為基本解， 也即在可行解域中的極點，也稱作為也即在可行解域中的極點，也稱作為基本可行解基本可行解。 對于一個含有對于一個含有n個決策變量、個決策變量、m個約束方程的線性規(guī)劃模型而言，個約束方程的線性規(guī)劃模型而言， 進行基本解試運算的總

18、次數(shù)為進行基本解試運算的總次數(shù)為n!/m!(n-m)!。 對線性規(guī)劃模型的求解，便是通過試運算考察所有可能的基本對線性規(guī)劃模型的求解，便是通過試運算考察所有可能的基本 可行解，因而試運算的工作量很大，單純形法就是可行解，因而試運算的工作量很大，單純形法就是考察一小部分考察一小部分 基本可行解便可得到最優(yōu)解的方法?；究尚薪獗憧傻玫阶顑?yōu)解的方法。 例2 p19頁 二二.基本定理基本定理p20 1 1線性規(guī)劃問題的可行域是一個凸多面體。線性規(guī)劃問題的可行域是一個凸多面體。 2 2若線性規(guī)劃問題存在可行解，則一定存在一個基本可行若線性規(guī)劃問題存在可行解，則一定存在一個基本可行 解。若線性規(guī)劃問題存在

19、最優(yōu)解，一定存在基本最優(yōu)解。解。若線性規(guī)劃問題存在最優(yōu)解，一定存在基本最優(yōu)解。 3 3線性規(guī)劃問題的基本可行解線性規(guī)劃問題的基本可行解X X對應于可行域的頂點。對應于可行域的頂點。 4 4若可行域有界，則線性規(guī)劃問題的目標函數(shù)一定可以在若可行域有界，則線性規(guī)劃問題的目標函數(shù)一定可以在 其可行域的頂點達最大值。其可行域的頂點達最大值。 單純形法是由單純形法是由Dantzig于于1951年提出的，是一種年提出的，是一種通過反復迭通過反復迭 代尋求線性規(guī)劃問題最優(yōu)解代尋求線性規(guī)劃問題最優(yōu)解的方法。他的方法。他對標準形式的線性對標準形式的線性 規(guī)劃模型中的約束方程進行一系列的行初等變換規(guī)劃模型中的約束

20、方程進行一系列的行初等變換，變成，變成易易 于獲得基本可行解的正則形式。于獲得基本可行解的正則形式。 12 123 124 25 15 m a x34 6 28 3 0 zxx xxx xxx xx xx 當求解決策變量超過當求解決策變量超過2 2個時，圖解法就無法解決問題，需要采用數(shù)學的個時，圖解法就無法解決問題，需要采用數(shù)學的 方法求解。但必須將線性規(guī)劃模型轉換為標準形式。方法求解。但必須將線性規(guī)劃模型轉換為標準形式。 一個單純形是指一個幾何形體一個單純形是指一個幾何形體, ,它在它在N N維情況下維情況下, ,是由是由N+1N+1個點、所有相個點、所有相 互連接的線段以及多邊形面等組成的

21、多面體。若相鄰頂點之間的距離互連接的線段以及多邊形面等組成的多面體。若相鄰頂點之間的距離 都是相等都是相等, ,稱為正則單純形稱為正則單純形. .二維空間中的單純形即為三角形二維空間中的單純形即為三角形, ,三維空間三維空間 中的單純形是一個四面體。中的單純形是一個四面體。 單純形法的基本思路是：從某個基可行解（某個頂點）開始轉換到單純形法的基本思路是：從某個基可行解（某個頂點）開始轉換到 另一個基可行解（頂點），尋找使目標函數(shù)最大時的解另一個基可行解（頂點），尋找使目標函數(shù)最大時的解最優(yōu)解。最優(yōu)解。 12 123 124 25 15 m a x34 6 28 3 0 zxx xxx xxx

22、xx xx 一一.指導思想：指導思想：p21 選取一個初始的基本可行解 檢驗是否為最優(yōu)解 得到最優(yōu)解 是 替換變量 否 二二.求解過程求解過程 例例2-4 MAX Z=5X1+3X2 S.T. 3X1+5X2 15 5X1+3X2 10 X1,X2 0 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 （一）用方程法（一）用方程法 1、標準化、標準化 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x MAX Z=

23、5X1+4X2 S.T. 3X1+5X2 15 5X1+3X2 10 X1,X2 0 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 2、給出基本可行解、給出基本可行解 1 0 3 5 0 1 5 3 A 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x 系數(shù)矩陣 取一個基取一個基 1 0 0 1 0 D 令令X1、X2=0， 則則X3 =15、X4 = 10 基本可行解基本可行解X0=(0,0,15,10)，

24、相應，相應Z0=0 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 基變量基變量X3、X4 3、判斷基本可行解是否為最優(yōu)判斷基本可行解是否為最優(yōu) 非基變量（非基變量（ X1、X2 ）的系數(shù)大于）的系數(shù)大于0，說明了，說明了X1、X2的值增大時，的值增大時， Z值將增大。值將增大。 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 基本可行解基本

25、可行解X=(0,0,15,10)不是最優(yōu)解不是最優(yōu)解 Z0=0 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x 從一個基轉移到另一個基從一個基轉移到另一個基 從可行域的一個頂點轉移到另一個頂點從可行域的一個頂點轉移到另一個頂點 從一個基本可行解變換到另一個基本可行解從一個基本可行解變換到另一個基本可行解 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 4、確定換入變量、確定換入變量 原則原則：在所有系數(shù)為正值

26、的非基變量中，在目 標函數(shù)尋找系數(shù)最大的，作為換入變量。 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x 非基變量非基變量X1、X2 選擇選擇X1作為換入變量作為換入變量 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 5、確定換出變量、確定換出變量 原則原則：滿足非負條件滿足非負條件 使換入變量盡可能大（盡快使目標函數(shù)使換入變量盡可能大（盡快使目標函數(shù) 值達到最大）值達到最大） 其他變量保持非負其他變量保持

27、非負 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x 選擇選擇X1作為換入變量（不等作為換入變量（不等 于于0的變量）的變量） X X3 3、X X4 4中將誰換出？中將誰換出？ 原基變量原基變量X3、X4 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x X3=15-3X10X15 X X4 4=10-5X=10-5X1 100X X1 122 為了滿足非負條件，取為了滿足非負條件，取X X4 4作為換出變量作為換出變量 基變量基變量XX3 3、X X1 1 非基變量 非基變

28、量X2、X4 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 基本可行解基本可行解X1=(2,0,9,0) Z1=10，不是最優(yōu)解，不是最優(yōu)解 12 123 124 1234 max54 3515 5310 ,0 Zxx xxx xxx x xx x X3=3X1-5X2+15=9-16/5X20 X245/16 X X1 1=2-3/5X=2-3/5X2 200 X X2 210/310/3 為了滿足非負條件，取為了滿足非負條件，取X X3 3作為換出變量作為換出變

29、量 基變量基變量XX2 2、X X1, 1,非基變量 非基變量-X3、X4 .標準化標準化 .給出基本可行解給出基本可行解 .判斷基本可行解是否為最優(yōu)解判斷基本可行解是否為最優(yōu)解 .確定換入變量確定換入變量 .確定換出變量確定換出變量 .基變換基變換 選擇選擇X2作為換入變量（不等于作為換入變量（不等于0的變量）的變量） 令令X3、X4=0， 則則X1 =5/16、X2 = 45/16 因為非基變量在目標函數(shù)的系數(shù)都為因為非基變量在目標函數(shù)的系數(shù)都為0，所以此時得到最優(yōu)解。，所以此時得到最優(yōu)解。 X=( 5/16， 45/16，0,0）T。Z =205/16。 6、 （二）增廣矩陣法（二）增廣矩陣法 1、標準化、標準化 12 123 124 1234 max53 3515 5210 ,0 Zxx xxx xxx x xx x MAX Z=5X1+3X2 S.T. 3X1+5X2 15 5X1+2X2 10 X1,X2 0 2、給出基本可行解、給出基本可行解 1 0 3 5 0 1 5 3 A 0, 1035 1553 35max 4321 421 321 21 xxxx xxx xxx xxZ 系數(shù)矩陣 取一個基取一