第三講：線性規(guī)劃

1、 線性規(guī)劃 優(yōu)化問題，一般是指用“最好”的方式，使用或分配有限的資源，即勞動力、原材料、機器、資金等，使得費用最小或利潤最大. 建立優(yōu)化問題的數(shù)學模型 1) 確定問題的決策變量 2) 構(gòu)造模型的目標函數(shù)和允許取值的范圍，常用一組不等式來表示.T1min(max)( ),(,)s.t.( )0,1,2,nizf xxxxgxim或（1）（2）由（1）、（2）組成的模型屬于約束優(yōu)化，若只有（1）式就是無約束優(yōu)化，f(x)稱為目標函數(shù)，g(x)稱為約束條件若目標函數(shù)f(x)和約束條件g(x)都是線性函數(shù)，則稱該模型是線性規(guī)劃. 線性規(guī)劃模型例一 、生產(chǎn)炊事用具需要兩種資源勞動力和原材料，某公司制定生

2、產(chǎn)計劃，生產(chǎn)三種不同的產(chǎn)品，生產(chǎn)管理部門提供的數(shù)據(jù)如下 A B C勞動力（小時/件）736原材料（千克/件）445利潤（元/件）423每天供應(yīng)原材料200kg，每天可使用的勞動力為150h. 建立線性規(guī)劃模型，使總收益最大，并求各種產(chǎn)品的日產(chǎn)量. 解解 第一步,確定決策變量. 用 分別表示A, B, C三種產(chǎn)品的日產(chǎn)量 第二步, 約束條件 原材料： 勞動力： 第三步，確定目標函數(shù) AxBxCx445200ABCxxx736150ABCxxx423ABCZxxx例2 一家廣告公司想在電視、廣播上做廣告，其目的是盡可能多的招來顧客，下面是調(diào)查結(jié)果： 電視無線電 廣播雜志白天最佳時間一次廣告費用（千

3、元）40753015受每次廣告影響的顧客數(shù)（千人）400900500200受每次廣告影響的女顧客數(shù)（千人）300400200100這家公司希望廣告費用不超過800（千元）還要求：1）至少要有200萬婦女收看廣告；2）電視廣告費用不超過500（千元） 3）電視廣告白天至少播出3次，最佳時間至少播出2次；4）通過廣播、雜志做的廣告要重復5到10次.123412341234121234m ax400900500200407530158003004002001002000. .40755003,2,510,510Zxxxxxxxxxxxxs txxxxxx令 分別白天，最佳電視、廣播、雜志廣告次數(shù) 1

4、234,xxxx，線性規(guī)劃問題的求解在理論上有單純形法，在實際建模中常用以下解法： 1. 圖解法 2. LINGO 軟件包； 3. Excel中的規(guī)劃求解； 4. MATLAB軟件包.3.2 用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX s.t.AXb1. 模型：命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A= ，b= .bAX 3. 模型：min z=cX s.t.AXbbeqXAeqVLBXVUB命令：1 x=linpr

5、og（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若沒有等式約束: , 則令Aeq= , beq= . 2其中X0表示初始點 beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標函數(shù)值fval.問題一問題一 ： 任務(wù)分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要

6、求，又使加工費用最低？ 單位工件所需加工臺時數(shù) 單位工件的加工費用 車床類 型 工件1 工件2 工件3 工件1 工件2 工件3 可用臺時數(shù) 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 兩個引例兩個引例解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型： 解答問題二：問題二： 某廠每日8小時的產(chǎn)量不低于1800件.為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員

7、的標準為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？解解 設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗員的工資為：212124323848xxxx因檢驗員錯檢而造成的損失為：21211282)%5158%2258(xxxx故目標函數(shù)為：故目標函數(shù)為：2121213640)128()2432(minxxxxxxz約束條件為：0, 0180015818002581800158258212121xxxxxx線性規(guī)劃模型：線性規(guī)劃模型：213640minxxz12121253459s.t.

8、150,0 xxxxxx 解答返 回線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目標函數(shù)和所有的約束條件都是設(shè)計變量目標函數(shù)和所有的約束條件都是設(shè)計變量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：實際問題中實際問題中的優(yōu)化模型的優(yōu)化模型T1min(max)( ),(,)s.t.( )0,1,2,nizf xxxxg xim或x是決策變量是決策變量f(x)是目標函數(shù)是目標函數(shù)gi(x) 0是約束條件是約束條件數(shù)學規(guī)劃數(shù)學規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二

9、次規(guī)劃二次規(guī)劃(QP)非線性規(guī)劃非線性規(guī)劃(NLP)純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃一般整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃連續(xù)規(guī)劃 優(yōu)化模型的分類優(yōu)化模型的分類解解 編寫編寫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=

10、0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh1)解解: 編寫編寫M文件文件xxgh2.m如下：如下： c=6 3 4; 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)123m in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxxs.t.Xz8121110913min 900800

11、3 . 12 . 15 . 000000011 . 14 . 0X改寫為：例例3 問題一的解答 問題問題編寫編寫M文件文件xxgh3.m如下如下:f = 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)結(jié)果結(jié)果:x = 0.0000 600.00

12、00 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機床上加工600個工件2,在乙機床上加工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; %調(diào)用linprog函數(shù)：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)結(jié)果為：結(jié)果為：x = 9.0000 0.0000fval =360即只需聘用9個一級檢驗員. 注：注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù).故它是一個整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題.這里把它當成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.返 回實驗作業(yè)實驗作業(yè) 某廠生產(chǎn)