数学软件求解线性规划数学建模论文学习教案

1、会计学1数学软件数学软件(run jin)求解线性规划数学建求解线性规划数学建模论文模论文第一页，共45页。问题一问题一 ： 任务分配问题：某车间有甲、乙两台机任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件床，可用于加工三种工件.假定这两台车床的可用台假定这两台车床的可用台时数分别为时数分别为800和和900，三种工件的数量分别为，三种工件的数量分别为400、600和和500，且已知用三种不同车床加工单位数量不，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表同工件所需的台时数和加工费用如下表.问怎样分配问怎样分配车床的加工任务，才能既满足车床的加工任务，才能既满

2、足(mnz)加工工件的要加工工件的要求，又使加工费用最低？求，又使加工费用最低？ 单位工件所需加工台时数 单位工件的加工费用 车床类 型 工件1 工件2 工件3 工件1 工件2 工件3 可用台时数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 两个两个(lin )引例引例第2页/共45页第二页，共45页。解解 设在甲车床上加工工件设在甲车床上加工工件1、2、3的数量分的数量分别别(fnbi)为为x1、x2、x3，在乙车床上加工工，在乙车床上加工工件件1、2、3的数量分别的数量分别(fnbi)为为x4、x5、x6,可建立以下线性规划模型：

3、可建立以下线性规划模型： 解答(jid)第3页/共45页第三页，共45页。问题二：问题二： 某厂每日某厂每日8小时的产量不低于小时的产量不低于1800件件.为了进行质量为了进行质量控制，计划聘请两种不同水平的检验员控制，计划聘请两种不同水平的检验员.一级检验员的标准为：一级检验员的标准为：速度速度(sd)25件件/小时，正确率小时，正确率98%，计时工资，计时工资4元元/小时；二级小时；二级检验员的标准为：速度检验员的标准为：速度(sd)15件件/小时，正确率小时，正确率95%，计时，计时工资工资3元元/小时小时.检验员每错检一次，工厂要损失检验员每错检一次，工厂要损失2元元.为使总检验为使总

4、检验费用最省，该工厂应聘一级、二级检验员各几名？费用最省，该工厂应聘一级、二级检验员各几名？解解 设需要一级和二级检验员的人数分别为设需要一级和二级检验员的人数分别为x1、x2人人,则应付则应付(yng f)检验员的工资为：检验员的工资为：212124323848xxxx因检验员错检而造成(zo chn)的损失为：21211282)%5158%2258(xxxx第4页/共45页第四页，共45页。故目标故目标(mbio)函数为：函数为：2121213640)128()2432(minxxxxxxz约束条件为：0, 0180015818002581800158258212121xxxxxx第5页/

5、共45页第五页，共45页。线性规划线性规划(xin xn u hu)模型：模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答(jid)返 回第6页/共45页第六页，共45页。11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目标目标(mbio)函数和所有的约束条件都是设计变函数和所有的约束条件都是设计变量量的线性函数的线性函数.min. s.tucxAxbvlbxvub矩矩阵阵形形式式：第7页/共45页第七页，共45页。实际问题实际问题(wnt)中中的优化模型的优化模型T1min(max)(

6、),(,)s.t.( )0,1,2,nizf xxxxg xim或x是决策是决策(juc)变量变量f(x)是目标是目标(mbio)函数函数gi(x) 0是约束条件是约束条件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划一般整数规划一般整数规划连续规划连续规划第8页/共45页第八页，共45页。用用MATLAB优化工具箱解线性规划优化工具箱解线性规划(xin xn u hu)min z=cX s.t.AXb1. 模型：命令(mng lng)：

7、x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令(mng lng)：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式： 存在，则令A= ，b= .bAX 第9页/共45页第九页，共45页。3. 模型：min z=cX s.t.AXbbeqXAeqVLBXVUB命令(mng lng)：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表示初始点 beqX

8、Aeq4. 命令：x,fval=linprog()返回(fnhu)最优解及处的目标函数值fval.第10页/共45页第十页，共45页。解解 编写编写(binxi)M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq

9、,beq,vlb,vub) To MATLAB (xxgh1)第11页/共45页第十一页，共45页。解解: 编写编写M文件文件(wnjin)xxgh2.m如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh2)123m in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxx第12页/共45页第十二页，共45页。s.t.Xz8121110913min改写为：

10、例例3 问题问题(wnt)一的解答一的解答 问题(wnt)第13页/共45页第十三页，共45页。编写编写(binxi)M文件文件xxgh3.m如下如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh3)第14页/共45页第十四页，共45页。

11、结果结果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲机床上加工即在甲机床上加工600个工件个工件(gngjin)2,在乙机床上加在乙机床上加工工400个工件个工件(gngjin)1、500个工件个工件(gngjin)3，可在满，可在满足条件的情况下使总加工费最小为足条件的情况下使总加工费最小为13800.第15页/共45页第十五页，共45页。例例2 问题问题(wnt)二的解答二的解答 问题(wnt)改写为：第16页/共45页第十六页，共45页。编写编写M文件文件xxgh4.m如下：如下：c =

12、 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9;15; %调用调用(dioyng)linprog函数：函数：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)第17页/共45页第十七页，共45页。结果结果(ji gu)为：为：x = 9.0000 0.0000fval =360即只需聘用即只需聘用9个一级检验员个一级检验员. 注：本问题应还有一个约束条件：注：本问题应还有一个约束条件：x1、x2取整取整数数.故它是一个整数线性规划问题故它是一个整数线性规划问题.这里把它当成

13、这里把它当成一个线性规划来解，求得其最优解刚好是整数：一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解，故它就是该整数规划的最优解.若若用线性规划解法求得的最优解不是整数，将其用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样取整后不一定是相应整数规划的最优解，这样的整数规划应用的整数规划应用(yngyng)专门的方法求解专门的方法求解.返 回第18页/共45页第十八页，共45页。用用LINDO、LINGO优化工具箱解线性规划优化工具箱解线性规划(xin xn u hu)第19页/共45页第十九页，共45页。 下面我们通过一

14、个例题来说明下面我们通过一个例题来说明(shumng)LINDO软件包的使用方法软件包的使用方法.第20页/共45页第二十页，共45页。 LINGO LINDO优 化 模 型优 化 模 型(mxng)线性规划线性规划(xin xn u hu)(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)第21页/共45页第二十一页，共45页。1桶牛奶 3千克A1 12小时 8小时 4千克A2 或获利24元/千克 获利16元/千克 50桶牛奶桶牛奶(ni ni) 时间时间(shjin): 480小时小时 至多至多(zhdu)加工加工100千克千克A1 制订

15、生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/千克，是否应改变生产计划？千克，是否应改变生产计划？ 每天：每天：第22页/共45页第二十二页，共45页。x1桶牛奶桶牛奶(ni ni)生产生产A1 x2桶牛奶桶牛奶(ni ni)生产生产A2 获利获利(hu l) 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx

16、加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 12max7264zxx每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)第23页/共45页第二十三页，共45页。max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRIC

17、ES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶桶牛奶(ni ni)生产生产A1, 30桶生产桶生产A2，利润，利润3360元元. 第24页/共45页第二十四页，共45页。 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW

18、 SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000原料原料(yunlio)无剩余无剩余时间时间(shjin)无剩余无剩余加工能力剩余加工能力剩余(shngy)40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 第25页/共45页第二十五页，共45页。模型模型(mxng)(mxng)求解求解 reduced cos

19、t值表示值表示当 该 非 基 变 量当 该 非 基 变 量(binling)增加一增加一个单位时（其他非个单位时（其他非基变量基变量(binling)保持不变）保持不变）,目标函目标函数减少的量数减少的量(对对max型问题型问题) . OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.0000

20、00 4) 40.000000 0.000000 NO. ITERATIONS= 2也可理解为：也可理解为：为了使该非基变为了使该非基变量变成基变量，量变成基变量，目标函数中对应目标函数中对应(duyng)系数应系数应增加的量增加的量第26页/共45页第二十六页，共45页。 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.00000

21、0 3) 0.000000 2.000000 4) 40.000000 0.000000结果结果(ji (ji gu)gu)解释解释 最优解下最优解下“资源资源”增加增加(zngji)1单位时单位时“效益效益”的增量的增量 原料增原料增1单位单位(dnwi), 利利润增润增48 时间增时间增1单位单位, 利润增利润增2 能力增减不影响利润能力增减不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 ”（或（或“=”（或（或“=”）功能相同）功能相同2.变量与系数间可有空格变量与系数间可有空格(甚至甚至(shnzh)回车回车), 但无运算但无运算符符3.变量名以

22、字母开头，不能超过变量名以字母开头，不能超过8个字符个字符4.变量名不区分大小写（包括变量名不区分大小写（包括LINDO中的关键字）中的关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义自动产生或人为定义.行名以行名以“）”结束结束7.行中注有行中注有“!”符号的后面部分为注释符号的后面部分为注释.如如: 8. ! Its Comment.9.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 对模型命名（最多对模型命名（最多72个字符），如：个字符），如：10. TITLE This Mode

23、l is only an Example第30页/共45页第三十页，共45页。9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10. 表达式中不接受括号表达式中不接受括号“( )”和逗号和逗号“,”等任何符号等任何符号, 例例: 400(X1+X2)需写为需写为400X1+400X211. 表达式应化简，如表达式应化简，如2X1+3X2- 4X1应写成应写成 -2X1+3X212. 缺省假定所有变量非负；可在模型的缺省假定所有变量非负；可在模型的“END”语句语句(yj)后用后用“FREE name”将变量将变量name的非负假定的非负假定取消取消13. 可在可在 “END

24、”后用后用“SUB” 或或“SLB” 设定变量设定变量上下界上下界14. 例如：例如： “sub x1 10”的作用等价于的作用等价于“x1=345.5 x1+x2=345.5; ; x1=98; x1=98; 2 2* *x1+x2=600 x1+x2=345.5 x1+x2=345.5 x1=98 x1=98 2 2* *x1+x2=600 x1+x21 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0

25、0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To MATLAB（xxgh5）第41页/共45页第四十一页，共45页。计算结果：计算结果：第42页/共45页第四十二页，共45页。五、五、 结果结果(ji gu)分分析析返 回4.4.在在a=0.006a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长附近有一个转折点，在这一点左边，风险增加很少时，利润增长(zngzhng)(zngzhng) 很快很快. .在这一点右边，风险增加很大时，利润增长在这一点右边，风险增加很