规划模型、案例及软件求解

历届竞赛赛题基本解法,历届竞赛赛题基本解法,历届竞赛赛题基本解法,历届竞赛赛题基本解法,规划模型、案例及软件求解,一、引言,二、线性规划模型及软件求解,三、整数规划模型,四、0-1规划模型,五、几种常用的线性规划模型,八、非线性规划模型,六、多目标规划模型,七、二次规划,在数模竞赛过程中，规划模型是最常见的一,类数学模型.从92-09年全国大学生数模竞赛试题,的解题方法统计结果来看，规划模型共出现了18,次，占到了近50%，也就是说每两道竞赛题中就有,一道涉及到利用规划理论来分析、求解.,如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在数学建模中处于中心的地位.这类问题一般可以归结为数学规划模型.规划模型的应用极其广泛，其作用已为越来越多的人所重视.,一、引言,（一）规划模型的数学描述,规划模型的一般意义,“受约束于”之意,（二）规划模型的分类,1.根据是否存在约束条件有约束问题和无约束问题。2.根据决策变量的性质静态问题和动态问题。,3.根据目标函数和约束条件表达式的性质线性规划，非线性规划，二次规划，多目标规划等。,（1）非线性规划目标函数和约束条件中，至少有一个非线性函数。,（2）线性规划（LP）,目标函数和所有的约束条件都是设计变量的线性函数。,（3）二次规划问题目标函数为二次函数，约束条件为线性约束,5.根据变量具有确定值还是随机值确定规划和随机规划。,4.根据决策变量的允许值,整数规划（0-1规划）和实数规划。,（三）建立规划模型的一般步骤,1.确定决策变量和目标变量；2.确定目标函数的表达式；3.寻找约束条件。,二、线性规划模型及软件求解,例1：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用两种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,解答,例2：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,线性规划模型：,解答,返回,线性规划模型的求解,Lingo与Lindo求解,Matlab求解,Lingo与Lindo,Lindo与Lingo都是LINDO系统公司开发的专门用于求解最优化问题的软件包。与Lindo相比，Lingo软件主要具有两大优点：（1）除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题。（2）LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中。,例1的Lingo求解,model:min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6;x1+x4=400;x2+x5=600;x3+x6=500;0.4*x1+1.1*x2+x3800;0.5*x1+1.2*x2+1.3*x3=45;x1=9;x2=15;end,例3加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,时间480小时,至多加工100公斤A1,综上所述,Maxz=72x1+64x2；s.t.x1+x250，12x1+8x2480，3x1100，x1，x20,Matlab解答,Lingo模型,这是一个（连续）线性规划（LP）问题,“LINGO|Solve”求解结果报告,“LINGO|Range”敏感性分析,max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;,灵敏度分析,敏感性分析的作用是给出“Rangesinwhichthebasisisunchanged”，即研究当目标函数的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基（矩阵）保持不变。注意：这里LINGO不询问是否进行敏感性分析。如果需要进行敏感性分析，必须用“LINGO|Options”命令打开系统选项对话框，在“GeneralSolver”标签下的“DualComputations”下拉列表中选中“Prices常数列表（value_list）中数据之间可以用逗号“,”分开，也可以用空格分开（回车的作用也等价于一个空格）“变量名=?;”运行时赋值（4）初始段（INIT）赋初值（5）计算段（CALC）预处理,MATLAB中有关求解线性规划问题的指令,X=linprog(c,A,b,Aeq,beq)X=linprog(c,A,b,Aeq,beq,vlb,vub)X=linprog(c,A,b,Aeq,beq,vlb,vub,x0)X=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options)x,fval,exitflag,output=linprog(),用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：minz=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2x=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),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),例1的Matlab求解,问题,编写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的Matlab求解,问题,改写为：,编写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，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。,例3的Matlab求解,问题,max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x11c=-0.05-0.27-0.19-0.185-0.185;Aeq=11.011.021.0451.065;beq=1;A=00.025000;000.01500;0000.0550;00000.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);ax=xQ=-valplot(a,Q,.)axis(00.100.5)holdona=a+0.001;endxlabel(a),ylabel(Q),ToMatlab（xxgh5）,计算结果：,五、结果分析,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度收益x0 x1x2x3x40.00600.201900.24000.40000.10910.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应