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

線性規(guī)劃優(yōu)化問(wèn)題，一般是指用“最好”的方式，使用或分配有限的資源，即勞動(dòng)力、原材料、機(jī)器、資金等，使得費(fèi)用最小或利潤(rùn)最大.建立優(yōu)化問(wèn)題的數(shù)學(xué)模型1)確定問(wèn)題的決策變量2)構(gòu)造模型的目標(biāo)函數(shù)和允許取值的范圍，常用一組不等式來(lái)表示.（1）（2）由（1）、（2）組成的模型屬于約束優(yōu)化，若只有（1）式就是無(wú)約束優(yōu)化，f(x)稱(chēng)為目標(biāo)函數(shù)，g(x)稱(chēng)為約束條件若目標(biāo)函數(shù)f(x)和約束條件g(x)都是線性函數(shù)，則稱(chēng)該模型是線性規(guī)劃.線性規(guī)劃模型例一、生產(chǎn)炊事用具需要兩種資源－勞動(dòng)力和原材料，某公司制定生產(chǎn)計(jì)劃，生產(chǎn)三種不同的產(chǎn)品，生產(chǎn)管理部門(mén)提供的數(shù)據(jù)如下ABC勞動(dòng)力（小時(shí)/件）736原材料（千克/件）445利潤(rùn)（元/件）423每天供應(yīng)原材料200kg，每天可使用的勞動(dòng)力為150h.建立線性規(guī)劃模型，使總收益最大，并求各種產(chǎn)品的日產(chǎn)量.

解第一步,確定決策變量.用分別表示A,B,C三種產(chǎn)品的日產(chǎn)量第二步,約束條件原材料：勞動(dòng)力：第三步，確定目標(biāo)函數(shù)例2一家廣告公司想在電視、廣播上做廣告，其目的是盡可能多的招來(lái)顧客，下面是調(diào)查結(jié)果：電視無(wú)線電廣播雜志白天最佳時(shí)間一次廣告費(fèi)用（千元）40753015受每次廣告影響的顧客數(shù)（千人）400900500200受每次廣告影響的女顧客數(shù)（千人）300400200100這家公司希望廣告費(fèi)用不超過(guò)800（千元）還要求：1）至少要有200萬(wàn)婦女收看廣告；2）電視廣告費(fèi)用不超過(guò)500（千元）3）電視廣告白天至少播出3次，最佳時(shí)間至少播出2次；4）通過(guò)廣播、雜志做的廣告要重復(fù)5到10次.令分別白天，最佳電視、廣播、雜志廣告次數(shù)線性規(guī)劃問(wèn)題的求解在理論上有單純形法，在實(shí)際建模中常用以下解法：1.圖解法2.LINGO軟件包；3.Excel中的規(guī)劃求解；4.MATLAB軟件包.3.2用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1.模型：命令：x=linprog（c,A,b）

2.模型：minz=cX

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

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

[2]

x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒(méi)有等式約束:,則令A(yù)eq=[],beq=[].[2]其中X0表示初始點(diǎn)4.命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.問(wèn)題一：

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

設(shè)在甲車(chē)床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車(chē)床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型：

解答問(wèn)題二：

某廠每日8小時(shí)的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員.一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時(shí)，正確率95%，計(jì)時(shí)工資3元/小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：故目標(biāo)函數(shù)為：約束條件為：線性規(guī)劃模型：解答返回線性規(guī)劃模型的一般形式

目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù).實(shí)際問(wèn)題中的優(yōu)化模型x是決策變量f(x)是目標(biāo)函數(shù)gi(x)0是約束條件數(shù)學(xué)規(guī)劃線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP)純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃優(yōu)化模型的分類(lèi)解編寫(xiě)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=[];

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

ToMATLAB(xxgh1)解:編寫(xiě)M文件xxgh2.m如下：

c=[634];A=[010];b=[50];Aeq=[111];beq=[120];vlb=[30,0,20];vub=[];

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh2)s.t.改寫(xiě)為：例3問(wèn)題一的解答

問(wèn)題編寫(xiě)M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400;600;500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)結(jié)果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿(mǎn)足條件的情況下使總加工費(fèi)最小為13800.例2問(wèn)題二的解答

問(wèn)題改寫(xiě)為：編寫(xiě)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)ToMATLAB(xxgh4)結(jié)果為：x=9.00000.0000fval=360即只需聘用9個(gè)一級(jí)檢驗(yàn)員.

注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù).故它是一個(gè)整數(shù)線性規(guī)劃問(wèn)題.這里把它當(dāng)成一個(gè)線性規(guī)劃來(lái)解，求得其最優(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)用專(zhuān)門(mén)的方法求解.返回實(shí)驗(yàn)作業(yè)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,