第4章線性規(guī)劃

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

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

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

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

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

兩個引例解

設在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：

解答問題二：

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

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

若可行基進一步滿足: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),相應x=(xB,xN)T,c=(cB,cN)基對應的變量xB稱為基變量,非基對應的變量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=[]，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]若沒有等式約束:,則令Aeq=[],beq=[].[2]其中X0表示初始點4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標函數(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)結果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800。例2問題二的解答

問題改寫為：編寫M文件xxgh4.m如下：c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%調用linprog函數(shù)：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh4)結果為：x=9.00000.0000fval=360即只需聘用9個一級檢驗員。

注：本問題應還有一個約束條件：x1、x2取整數(shù)。故它是一個整數(shù)線性規(guī)劃問題。這里把它當成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解。若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應用專門的方法求解。返回企業(yè)生產計劃

4.4

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

加工奶制品的生產計劃1桶牛奶

3kgA1

12h

8h

4kgA2

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

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

12h8h4kgA2

或獲利24元/kg獲利16元/kgx1桶牛奶生產A1

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數(shù)

每天獲利約束條件非負約束

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

50桶牛奶每天基本模型模型分析與假設

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

圖解法

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

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

軟件實現(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桶牛奶生產A1,30桶生產A2，利潤3360元.結果解釋

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結果解釋

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

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

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

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

A1獲利增加到30元/kg，應否改變生產計劃?x1系