線性規劃數學建模實驗實驗目的實驗內容2、掌握用數學軟件包求解線性規劃問題。1、了解線性規劃的基本內容。*2線性規劃的基本算法。3用數學軟件包求解線性規劃問題。1兩個引例。問題一：

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

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

解答問題二：

某廠每日8小時的產量不低于1800件。為了進行質量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15件/小時，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解設需要一級和二級檢驗員的人數分別為x1、x2人,則應付檢驗員的工資為：因檢驗員錯檢而造成的損失為：故目標函數為：約束條件為：線性規劃模型：解答返回1.線性規劃的一般形式：用單純法求解時，常將標準形式化為：2.線性規劃的基本算法——單純形法線性規劃的基本算法——單純形法引入松弛變量x3,x4,x5,將不等式化為等式,即單純形標準形:顯然A的秩ran(A)=3,任取3個線性無關的列向量,如P3P4P5稱為一組基,記為B.其余列向量稱為非基,記為N.于是f=cBxB+cNxN,Ax=BxB+NxN=b,

則xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN

若可行基進一步滿足:

cN–cBB-1N≥0,即:cBB-1N-cN≤0則對一切可行解x,必有f(x)≥cBB-1b,此時稱基可行解x=(B-1b,0)T為最優解.3.最優解的存在性定理將A的列向量重排次序成A=(B,N),相應x=(xB,xN)T,c=(cB,cN)基對應的變量xB稱為基變量,非基對應的變量xN稱為非基變量.定理1如果線性規劃(1)有可行解，那么一定有基可行解.定理2如果線性規劃(1)有最優解，那么一定存在一個基可行解是最優解.4.基可行解是最優解的判定準則因為f=cBB-1b+(cN–cBB-1N)xN，即f-0?xB+(cBB-1N-cN)xN=cBB-1b5.基可行解的改進改進方法：返回用MATLAB優化工具箱解線性規劃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(…)返回最優解ｘ及ｘ處的目標函數值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)

D:/MATLAB6p1/bin/win32/matlab.exeMatlab(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函數：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh4)結果為：x=9.00000.0000fval=360即只需聘用9個一級檢驗員。

注：本問題應還有一個約束條件：x1、x2取整數。故它是一個整數線性規劃問題。這里把它當成一個線性規劃來解，求得其最優解剛好是整數：x1=9，x2=0，故它就是該整數規劃的最優解。若用線性規劃解法求得的最優解不是整數，將其取整后不一定是相應整數規劃的最優解，這樣的整數規劃應用專門的方法求解。返回用Mathematica軟件包解線性規劃問題LinearProgramming[c,m,b]findsthevectorxwhichminimizesthequantityc.x

subjecttotheconstraintsm.x≥bandx≥0.例:In[1]:=LinearProgramming[{2,-3},{{-1,-1},{1,-1},{1,0}},{-10,2,1}]Out[1]={6,4}ConstrainedMin[f,{inequalities},{x,y,…}]findstheglobalminimumoffinthedomainspecifiedbytheinequalities.Thevariablesx,y,…areallassumedtobenon-negative.例In[2]:=ConstrainedMin[2x-3y,{x+y<10,x-y>2,x>1},{x,y}]Out[2]={0,{x->6,y->4}}ConstrainedMax[f,{inequalities},{x,y,…}]findstheglobalmaximumoffinthedomainspecifiedbytheinequalities.Thevariablesx,y,…areallassumedtobenon-negative.例In[2]:=ConstrainedMax[x+3y+7z,{x-3y<7,2x+3z>=5,x+y+z<=10},{x,y,z}]Out[2]={70,{x->0,y->0,z->10}實驗作業