第4章線性規(guī)劃

第四章線性規(guī)劃模型4.1兩個引例4.2

線性規(guī)劃基本理論4.3

用MATLAB優(yōu)化工具箱解線性規(guī)劃

4.4加工奶制品的生產(chǎn)計劃建模及Lingo軟件求解問題一：

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

兩個引例解

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

解答問題二：

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

線性規(guī)劃的基本理論引入松弛變量x3,x4,x5,將不等式化為等式,即單純形標(biāo)準(zhǔn)形:

若可行基進(jìn)一步滿足:cN–cBB-1N≥0,即:cBB-1N-cN≤0則對一切可行解x,必有f(x)≥cBB-1b,此時稱基可行解x=(B-1b,0)T為最優(yōu)解.

3.最優(yōu)解的存在性定理將A的列向量重排次序成A=(B,N),相應(yīng)x=(xB,xN)T,c=(cB,cN)基對應(yīng)的變量xB稱為基變量,非基對應(yīng)的變量xN稱為非基變量.定理1如果線性規(guī)劃(1)有可行解，那么一定有基可行解.定理2如果線性規(guī)劃(1)有最優(yōu)解，那么一定存在一個基可行解是最優(yōu)解.4.3用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

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

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令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]若沒有等式約束:,則令A(yù)eq=[],beq=[].[2]其中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=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh1)解:編寫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.改寫為：例3問題一的解答

問題編寫M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];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個工件2,在乙機(jī)床上加工400個工件1、500個工件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)ToMatlab(xxgh4)結(jié)果為：x=9.00000.0000fval=360即只需聘用9個一級檢驗(yàn)員。

注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù)。故它是一個整數(shù)線性規(guī)劃問題。這里把它當(dāng)成一個線性規(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è)生產(chǎn)計劃

4.4

加工奶制品的生產(chǎn)計劃建模及Lingo軟件求解工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計劃；車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計劃.時間層次若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可制訂單階段生產(chǎn)計劃，否則應(yīng)制訂多階段生產(chǎn)計劃.

加工奶制品的生產(chǎn)計劃1桶牛奶

3kgA1

12h

8h

4kgA2

或獲利24元/kg獲利16元/kg50桶牛奶時間480h至多加工100kgA1

制訂生產(chǎn)計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/kg，應(yīng)否改變生產(chǎn)計劃？每天：問題1桶牛奶3kgA1

12h8h4kgA2

或獲利24元/kg獲利16元/kgx1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動時間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時間480h至多加工100kgA1

50桶牛奶每天基本模型模型分析與假設(shè)

比例性可加性連續(xù)性xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對約束條件的“貢獻(xiàn)”與xi取值成正比xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān)xi對約束條件的“貢獻(xiàn)”與xj取值無關(guān)xi取值連續(xù)A1,A2每千克的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工A1,A2的數(shù)量,時間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每千克的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工A1,A2的數(shù)量,時間是與相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線性規(guī)劃模型模型求解

圖解法

x1x2OABCDl1l2l3l4l5約束條件目標(biāo)函數(shù)

z=0z=2400z=3360z=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解.目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點(diǎn)取得.模型求解

軟件實(shí)現(xiàn)

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元.結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無剩余時間無剩余加工能力剩余40結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最優(yōu)解下“資源”增加1單位時“效益”的增量影子價格35元可買到1桶牛奶，要買嗎?35<48,應(yīng)該買！聘用臨時工人付出的工資最多每小時幾元?2元！原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍敏感性分析(“LINGO|Ranges”)

x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/kg，應(yīng)否改變生產(chǎn)計劃?x1系