数学软件求解线性规划数学建模优秀论文公开课一等奖优质课大赛微课获奖课件.pptx

线性规划线性规划数学建模与数学试验数学建模与数学试验第1页第1页实验目试验内容试验内容2.掌握用数学软件包求解线性规划问题掌握用数学软件包求解线性规划问题.1.理解线性规划基本内容理解线性规划基本内容.2.用数学软件包用数学软件包MATLAB求解线性规划问题求解线性规划问题.5.试验作业试验作业.3.用数学软件包用数学软件包LINDO、LINGO求解线性规划问题求解线性规划问题.1.两个引例两个引例.4.建模案例：投资收益与风险建模案例：投资收益与风险.第2页第2页问题一：任务分派问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床可用台时数分别为800和900，三种工件数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需台时数和加工费用以下表.问怎样分派车床加工任务，才干既满足加工工件要求，又使加工费用最低？两个引例两个引例第3页第3页解解 设在甲车床上加工工件1、2、3数量分别为x1、x2、x3，在乙车床上加工工件1、2、3数量分别为x4、x5、x6,可建立下列线性规划模型：解答第4页第4页问题二：某厂每日8小时产量不低于1800件.为了进行质量控制，计划聘请两种不同水平检验员.一级检验员标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解解 设需要一级和二级检查员人数分别为x1、x2人,则应付检查员工资为：因检查员错检而造成损失为：第5页第5页故目的函数为：故目的函数为：约束条件为：第6页第6页线性规划模型：线性规划模型：解答返回第7页第7页线性规划模型普通形式线性规划模型普通形式 目的函数和所有约束条件都是设计变量目的函数和所有约束条件都是设计变量线性函数线性函数.第8页第8页实际问题中实际问题中优化模型优化模型x是决议变量是决议变量f(x)是目的函数是目的函数gi(x)0是约束条件是约束条件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划普通整数规划普通整数规划连续规划连续规划 优化模型分类优化模型分类第9页第9页用用MATLAB优化工具箱解线性规划优化工具箱解线性规划minz=cX 1.模型：命令：x=linprog（c,A,b）2.模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.第10页第10页3.模型：minz=cX VLBXVUB命令：1x=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.第11页第11页解解 编写编写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;vubx,fval=linprog(c,A,b,Aeq,beq,vlb,vub)xxgh1.m第12页第12页解解:编写编写M文献文献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)ToMATLAB(xxgh2)第13页第13页s.t.改写为：例例3 问题一解答问题问题第14页第14页编写编写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;b800;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)ToMATLAB(xxgh3)第15页第15页结果结果:x=0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件情况下使总加工费最小为13800.第16页第16页例例2 问题二解答问题问题改写为：第17页第17页编写编写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)第18页第18页结果为：结果为：x=9.0000 0.0000fval=360即只需聘用9个一级检查员.注：注：本问题应尚有一个约束条件：x1、x2取整数.故它是一个整数线性规划整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划最优解.若用线性规划解法求得最优解不是整数，将其取整后不一定是相应整数规划最优解，这样整数规划应用专门办法求解.返回第19页第19页用用LINDO、LINGO优化工具箱解线性规划优化工具箱解线性规划第20页第20页一、一、LINDO软件包软件包 下面我们通过一个例题来阐明下面我们通过一个例题来阐明LINDO软件包使用办法软件包使用办法.第21页第21页LINDOLINDO和和LINGOLINGO软件能求解优化模型软件能求解优化模型 LINGO LINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)第22页第22页1桶牛奶3公斤A112小时8小时4公斤A2或赢利24元/公斤赢利16元/公斤50桶牛奶桶牛奶 时间时间:480小时小时 至多加工至多加工100公斤公斤A1 制定生产计划，使天天赢利最大制定生产计划，使天天赢利最大 35元可买到元可买到1桶牛奶，买吗？若买，天天最多买多少桶牛奶，买吗？若买，天天最多买多少?可聘用暂时工人，付出工资最多是每小时几元可聘用暂时工人，付出工资最多是每小时几元?A1赢利增长到赢利增长到 30元元/公斤，是否应改变生产计划？公斤，是否应改变生产计划？天天：天天：例例1 加工奶制品生产计划加工奶制品生产计划第23页第23页x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 赢利赢利 243x1 赢利赢利 164 x2 原料供应原料供应劳动时间劳动时间加工能力加工能力决议变量决议变量 目的函数目的函数 天天赢利天天赢利约束条件约束条件非负约束非负约束线性线性规划规划模型模型(LP)建立模型建立模型第24页第24页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 PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元元.模型求解模型求解第25页第25页 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.000000 4)40.000000 0.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零约束为紧约束（有效约束）剩余为零约束为紧约束（有效约束）结果解释结果解释第26页第26页模型求解模型求解 reduced cost值值表表示示当当该该非非基基变变量量增增长长一一个个单单位位时时（其其它它非非基基变变量量保保持持不不变变）目目的的函函 数数 减减 少少 量量(对对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.000000 4)40.000000 0.000000 NO.ITERATIONS=2也可理解为：也可理解为：为为了了使使该该非非基基变变量量变变成成基基变变量量，目目的的函函数数中中相相应应系数应增长量系数应增长量第27页第27页 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.000000 4)40.000000 0.000000结果解释结果解释 最优解下最优解下“资源资源”增长增长1单位时单位时“效益效益”增量增量 原料增原料增1单位单位,利润增利润增48 时间增时间增1单位单位,利润增利润增2 能力增减不影响利润能力增减不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35”（或（或“=”（或（或“=”）功效相同）功效相同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超出变量名以字母开头，不能超出8个字符个字符4.变量名不区别大小写（包括变量名不区别大小写（包括LINDO中关键字）中关键字）5.目的函数所在行是第一行，第二行起为约束条件目的函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义自动产生或人为定义.行名以行名以“）”结束结束7.行中注有行中注有“!”符号后面部分为注释符号后面部分为注释.如如:!Its Comment.8.在模型任何地方都能够用在模型任何地方都能够用“TITLE”对模型命名对模型命名（最多（最多72个字符），如：个字符），如：TITLE This Model is only an Example第31页第31页9.变量不能出现在一个约束条件右端变量不能出现在一个约束条件右端10.表示式中不接受括号表示式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表示式应化简，如表示式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负；可在模型缺省假定所有变量非负；可在模型“END”语句后用语句后用“FREE name”将变量将变量name非负假定取消非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上下设定变量上下界界 比如：比如：“sub x1 10”作用等价于作用等价于“x1=345.5 x1+x2=345.5;x1=98;x1=98;2*x1+x2=600 2*x1+x2=345.5 x1+x2=345.5 x1=98 x1=98 2*x1+x2=600 2*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 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)ToMATLAB（xxgh5）第42页第42页计算结果：计算结果：第43页第43页五、五、结果分析结果分析返回4 4.在a=0.006附近有一个转折点，在这一点左边，风险增长很少时，利润增长 不久.在这一点右边，风险增长很大时，利润增长很缓慢，因此对于风险和 收益没有特殊偏好投资者来说，应当选择曲线拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所相应投资方案为:风险度收益x0 x1x2x3x4 0.0060 0.0 0.2400 0.4000 0.1091 0.2212 3.曲线上任一点都表示该风险水平最大可能收益和该收益要求最小风险.对于不同风险承受能力，选择该风险水平下最优投资组合.2.当投资越分散时，投资者承担风险越小，这与题意一致.即:冒险投资者会出现集中投资情况，保守投资者则尽也许分散投资.1.1.风险大，收益也大.第44页第44页试验作业试验作业某厂生产甲乙两种口味饮料,每百箱甲饮料需用原料6公斤,工人10名,可赢利10万元;每百箱乙饮料需用原料5公斤,工人20名,可赢利9万元.今工厂共有原料60公斤,工人150名,又由于其它条件所限甲饮料产量不超出800箱.问如何安排生产计划,即两种饮料各生产多少使赢利最大.进一步讨论:1)若投资0.8万元可增长原料1公斤,问应否作这项投资.2)若每100箱甲饮料赢利可增长1万元,问应否改变生产计划.返回第45页第45页