第1講線性規(guī)劃

線性規(guī)劃數(shù)學(xué)建模培訓(xùn)講義2009年8月要求在人們的生產(chǎn)實(shí)踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟(jì)效益的問題。此類問題構(gòu)成了運(yùn)籌學(xué)的一個(gè)重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(LinearProgramming簡記LP)則是數(shù)學(xué)規(guī)劃的一個(gè)重要分支。自從1947年G.B.Dantzig

提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實(shí)用中日益廣泛與深入。特別是在計(jì)算機(jī)能處理成千上萬個(gè)約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。2、掌握用數(shù)學(xué)軟件包求解線性規(guī)劃問題。1、了解線性規(guī)劃的基本內(nèi)容。問題一：

任務(wù)分配問題：某車間有甲、乙兩臺機(jī)床，可用于加工三種工件。假定這兩臺車床的可用臺時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用兩種不同車床加工單位數(shù)量不同工件所需的臺時(shí)數(shù)和加工費(fèi)用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？兩個(gè)引例解

設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：變量x1、x2、x3、x4、x5、x6稱為決策變量，（1）式被稱為問題的目標(biāo)函數(shù)，（2）中的幾個(gè)不等式是問題的約束條件，記為s.t.(即subjectto)。由于上面的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題?？傊?，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。問題二：

某廠每日8小時(shí)的產(chǎn)量不低于1800件。為了進(jìn)行質(zhì)量控制，計(jì)劃聘請兩種不同水平的檢驗(yàn)員。一級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15小時(shí)/件，正確率95%，計(jì)時(shí)工資3元/小時(shí)。檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元。為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級、二級檢驗(yàn)員各幾名？解設(shè)需要一級和二級檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：在解決實(shí)際問題時(shí)，把問題歸結(jié)成一個(gè)線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選適當(dāng)?shù)臎Q策變量，是我們建立有效模型的關(guān)鍵之一。故目標(biāo)函數(shù)為：約束條件為：線性規(guī)劃模型：1.線性規(guī)劃的標(biāo)準(zhǔn)形式：2.求解線性規(guī)劃的Mtlab解法線性規(guī)劃問題的解及Matlab解法可行解滿足約束條件（4）的解，稱為線性規(guī)劃問題的可行解，而使目標(biāo)函數(shù)（3）達(dá)到最小值的可行解叫最優(yōu)解?？尚杏?/p>

所有可行解構(gòu)成的集合稱為問題的可行域.

單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。這里我們就不介紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的Matlab解法。minz=cX

1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A(yù)=[]，b=[].3、模型：minz=cX

LB≤X≤UB命令：[1]x=linprog（c，A，b，Aeq,beq,LB，UB）

[2]x=linprog（c，A，b，Aeq,beq,LB，UB,X0）

注意：[1]若沒有等式約束:,則令A(yù)eq=[],beq=[].[2]其中LB，UB分別是變量的下、上界，

X0表示初始點(diǎn)4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.解編寫M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];

Aeq=[];beq=[];lb=[0;0;0;0;0;0];ub=[];[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub)

解:編寫M文件xxgh2.m如下：

c=[634];A=[010];b=[50];

Aeq=[111];

beq=[120];lb=[30,0,20];

ub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)S.t.改寫為：例3問題一的解答編寫M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];lb=zeros(6,1);ub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)結(jié)果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004

即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800。例2問題二的解答改寫為：編寫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)結(jié)果為：x=9.00000.0000fval=360即只需聘用9個(gè)一級檢驗(yàn)員。

注：本問題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù)。故它是一個(gè)整數(shù)線性規(guī)劃問題。這里把它當(dāng)成一個(gè)線性規(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)用專門的方法求解?？梢赞D(zhuǎn)化為線性規(guī)劃的問題很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃的問題來解決。如：例3規(guī)劃問題：其中，和為相應(yīng)維數(shù)的矩陣和向量。要把上面的問題變換成線性規(guī)劃問題，我們只要取這樣，記從而我們可以把上面的問題變成

例4其中

對于這個(gè)問題，如果我們?nèi)∵@樣，上面的問題就變換成

此即我們通常的線性規(guī)劃問題。另外線性規(guī)劃問題還有對偶理論、靈敏度分析及參數(shù)線性規(guī)劃等思考題：投資的收益和風(fēng)險(xiǎn)基本假設(shè)和符號規(guī)定模型的建立與分析1.總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來衡量,即max{qixi|i=1，2,…n}4.模型簡化：模型1的求解

由于a是任意給定的風(fēng)險(xiǎn)度，到底怎樣給定沒有一個(gè)準(zhǔn)則，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從a=0開始，以步長△a=0.001進(jìn)行循環(huán)搜索，編制程序如下：a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];

Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];

vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')計(jì)算結(jié)果：結(jié)果分析4.在a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤增長很快。在這一點(diǎn)右邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤增長很緩慢，所以對于風(fēng)險(xiǎn)和收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20%，所對應(yīng)投資方案為:

風(fēng)險(xiǎn)度收益x0x1x2x3x40.00600.201900.24000.40000.10910.22123.曲線上的任一點(diǎn)都表示該風(fēng)險(xiǎn)水平的最大可能收益和該收益要求的最小風(fēng)險(xiǎn)。對于不同風(fēng)險(xiǎn)的承受能力，選擇該風(fēng)險(xiǎn)水平下的最優(yōu)投資組合。2.當(dāng)投資越分散時(shí)，投資者承擔(dān)的風(fēng)險(xiǎn)越小，這與題意一致。即:

冒險(xiǎn)的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。1.風(fēng)險(xiǎn)大，收益也大。練習(xí)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲