1、第四章第四章 線性規劃模型線性規劃模型4.1 兩個引例兩個引例4.2 線性規劃基本理論線性規劃基本理論4.3 用用MATLAB優化工具箱解線性規劃優化工具箱解線性規劃 4.4 加工奶制品的生產計劃建模及加工奶制品的生產計劃建模及 Lingo軟件求解軟件求解問題一問題一 ： 任務分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數分別為800和900，三種工件的數量分別為400、600和500，且已知用三種不同車床加工單位數量不同工件所需的臺時數和加工費用如下表。問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使加工費用最低？ 單位工件所需加工臺時數 單位工件的

2、加工費用 車床類 型 工件1 工件2 工件3 工件1 工件2 工件3 可用臺時數 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 4.1 兩個引例兩個引例解解 設在甲車床上加工工件1、2、3的數量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數量分別為x4、x5、x6?？山⒁韵戮€性規劃模型：6543218121110913minxxxxxxz 6 , 2 , 1, 09003 . 12 . 15 . 08001 . 14 . 0500600400 x . .654321635241ixxxxxxxxxxxxtsi 解答問題二：問

3、題二： 某廠每日8小時的產量不低于1800件。為了進行質量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解解 設需要一級和二級檢驗員的人數分別為x1、x2人,則應付檢驗員的工資為：212124323848xxxx因檢驗員錯檢而造成的損失為：21211282)%5158%2258(xxxx故目標函數為：故目標函數為：2121213640)128()2432(minxxxxxxz

4、約束條件為：0, 0180015818002581800158258212121xxxxxx線性規劃模型：線性規劃模型：213640minxxz0, 01594535 . .212121xxxxxxts 解答返 回1.1.線性規劃的標準形式：線性規劃的標準形式：xminz=)(xf. .ts )(xgi0 （), 2 , 1mi其中目標函數)(xf和約束條件中)(xgi都是線性函數min min f = = cxs.t. s.t. Ax = = b （1 1） x 0 0這里 A = (ija)m,n , x = T 21nxxx b= T 21nbbb, c= nccc21用單純法求解時，常

5、將標準形式化為：2. 線性規劃的基本算法線性規劃的基本算法單純形法單純形法4.2 線性規劃的基本理論線性規劃的基本理論例例 min z = 10 x1 + 9x2st6x1 + 5x2 60 10 x1 + 20 x2 150 x1 8 x1, x2 0引入松弛變量x3, x4, x5, 將不等式化為等式, 即單純形標準形: min z = 10 x1 + 9x2st6x1 + 5x2 + x3 = 60 10 x1 + 20 x2 - x4 = 150 x1 + x5 = 8 xi 0 (i = 1,2,3,4,5) 令非基變量 xN = 0, 解得基變量 xB = B1b, 稱(xB, x

6、N)為基基解解.基解的所有變量的值都非負，則稱為基基可可行行解解，此時的基稱為可可行行基基. 若可行基進一步滿足: cN cBB-1N0, 即: cBB-1N - cN0則對一切可行解x, 必有f(x) cBB-1b, 此時稱基可行解x = (B-1b, 0) T為最優解最優解. 3. 最優解的存在性定理最優解的存在性定理將A的列向量重排次序成A = (B, N), 相應x = (xB, xN) T, c = (cB, cN)基對應的變量xB稱為基變量基變量, 非基對應的變量xN稱為非基變量非基變量.定理定理1 1 如果線性規劃(1)有可行解，那么一定有基可行解.定理定理2 2 如果線性規劃(

7、1)有最優解，那么一定存在一個基可行解 是最優解.4.3 用用MATLAB優化工具箱解線性規劃優化工具箱解線性規劃min z=cX bAXts. .1、模型：命令：x=linprog（c，A，b） 2、模型：min z=cX bAXts. .beqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A= ，b= .bAX 3、模型：min z=cX bAXts. .beqXAeqVLBXVUB命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意

8、：1 若沒有等式約束: , 則令Aeq= , beq= . 2其中X0表示初始點beqXAeq4、命令：x,fval=linprog()返回最優解及處的目標函數值fval.解解 編寫編寫M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linpr

9、og(c,A,b,Aeq,beq,vlb,vub)例例1 max 6543216 . 064. 072. 032. 028. 04 . 0 xxxxxxz 85003. 003. 003. 001. 001. 001. 0. .654321xxxxxxt s 70005. 002. 041xx 10005. 002. 052xx 90008. 003. 063xx 6, 2 , 10jxj To Matlab (xxgh1)例例 2 321436minxxxz 120. .321xxxts 301x 5002 x 203x解解: 編寫編寫M文件文件xxgh2.m如下：如下： c=6 3 4;

10、A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh2)321)436(minxxxz32120030 xxx50120010111 .321xxxtsS.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X500600400100100010010001001X ，0654321xxxxxxX改寫為：例例3 問題一的解答 問題問題編寫編寫M文件文件xxgh3.m如下如下:f

11、 = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh3)結果結果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機床上加工600個工件2,在乙機床上加

12、工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800。例例2 問題二的解答 問題問題 213640minxxz s.t. )45(3521xx改寫為：編寫編寫M文件文件xxgh4.m如下：如下：c = 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9;15; %調用linprog函數：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh4)結果為：結果為：x = 9.0000 0.0000fval =360即只需聘用9個一級檢驗員。 注：注：本問題應還有一

13、個約束條件：x1、x2取整數。故它是一個整數線性規劃整數線性規劃問題。這里把它當成一個線性規劃來解，求得其最優解剛好是整數：x1=9，x2=0，故它就是該整數規劃的最優解。若用線性規劃解法求得的最優解不是整數，將其取整后不一定是相應整數規劃的最優解，這樣的整數規劃應用專門的方法求解。返 回企業生產計劃企業生產計劃 4.4 加工奶制品的生產計劃建模及加工奶制品的生產計劃建模及 Lingo軟件求解軟件求解工廠級：根據外部需求和內部設備、人力、原料等工廠級：根據外部需求和內部設備、人力、原料等條件，以最大利潤為目標制訂產品生產計劃；條件，以最大利潤為目標制訂產品生產計劃；車間級：根據生產計劃、工藝流

14、程、資源約束及費車間級：根據生產計劃、工藝流程、資源約束及費用參數等，以最小成本為目標制訂生產批量計劃用參數等，以最小成本為目標制訂生產批量計劃.時間層次時間層次若短時間內外部需求和內部資源等不隨時間變化，可若短時間內外部需求和內部資源等不隨時間變化，可制訂制訂單階段生產計劃單階段生產計劃，否則應制訂多階段生產計劃，否則應制訂多階段生產計劃. 加工奶制品的生產計劃加工奶制品的生產計劃1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或獲利獲利24元元/kg 獲利獲利16元元/kg 50桶牛奶桶牛奶 時間時間480h 至多加工至多加工100kgA1 制訂生產計劃，使每天獲利最大制訂生產計劃

15、，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/kg，應否改變生產計劃？，應否改變生產計劃？ 每天：每天：問問題題1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或獲利獲利24元元/kg 獲利獲利16元元/kg x1桶牛奶生產桶牛奶生產A1 x2桶牛奶生產桶牛奶生產A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 48081221 xx加工能力加

16、工能力 10031x決策變量決策變量 目標函數目標函數 216472maxxxz每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規劃規劃模型模型(LP)時間時間480h 至多加工至多加工100kgA1 50桶牛奶桶牛奶 每天每天基本基本模型模型模型分析與假設模型分析與假設 比比例例性性 可可加加性性 連續性連續性 xi對目標函數的對目標函數的“貢貢獻獻”與與xi取值成正比取值成正比 xi對約束條件的對約束條件的“貢貢獻獻”與與xi取值成正比取值成正比 xi對目標函數的對目標函數的“貢貢獻獻”與與xj取值無關取值無關 xi對約束條件的對約束條件的“貢貢獻獻”與與xj取值無關

17、取值無關 xi取值連續取值連續 A1,A2每千克的獲利是與各自每千克的獲利是與各自產量無關的常數產量無關的常數每桶牛奶加工每桶牛奶加工A1,A2的數量的數量, 時時間是與各自產量無關的常數間是與各自產量無關的常數A1,A2每千克的獲利是與相互每千克的獲利是與相互產量無關的常數產量無關的常數每桶牛奶加工每桶牛奶加工A1,A2的數量的數量,時時間是與相互產量無關的常數間是與相互產量無關的常數加工加工A1,A2的牛奶桶數是實數的牛奶桶數是實數 線性規劃模型線性規劃模型模型求解模型求解 圖解法圖解法 x1x2OABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約

18、束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472maxxxz目標目標函數函數 z=0z=2400z=3360z=c (常數常數) 等值線等值線c在在B(20,30)點得到最優解點得到最優解.目標函數和約束條件是線性函數目標函數和約束條件是線性函數 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標函數的等值線為直線目標函數的等值線為直線 最優解一定在凸多邊最優解一定在凸多邊形的某個頂點取得形的某個頂點取得. . 模型求解模型求解 軟件實現軟件實現 LINGO model:max = 72*x1+64*x2;mil

19、k x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000

20、CPCT 40.00000 0.000000 20桶牛奶生產桶牛奶生產A1, 30桶生產桶生產A2，利潤，利潤3360元元. 結果解釋結果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000

21、 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40結果解釋結果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Va

22、riable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000最優解下最優解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎桶牛奶，要買嗎?35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元聘用臨時工

23、人付出的工資最多每小時幾元? 2元！元！原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME