数学建模--线性规划ppt课件.ppt

《数学建模--线性规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模--线性规划ppt课件.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 线性规划数学建模与数学实验为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益实验目的实验内容2.掌握用数学软件包求解线性规划问题.1.了解线性规划的基本内容.2.用数学软件包MATLAB求解线性规划问题.5.实验作业.3.用数学软件包LINDO、LINGO求解线性规划问题.1.两个引例.4.建模案例：投资的收益与风险.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人

2、单位和职工的合法权益问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？两个引例为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：解答为了规范

3、事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事

4、业单位工作人员聘用制度，保障用人单位和职工的合法权益故目标函数为：约束条件为：为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益线性规划模型：解答返回为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益线性规划模型的一般形式 目标函数和所有的约束条件都是设计变量的线性函数.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益实际问题中的优化模型x是决策变量 f(x)是目标函数gi(x)0是约束条件数学规

5、划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划 优化模型的分类为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益用MATLAB优化工具箱解线性规划minz=cX 1.模型：命令：x=linprog（c,A,b）2.模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和

6、职工的合法权益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.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益解 编写M文件xxgh1.m如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.0

7、3 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,beq,vlb,vub)ToMATLAB(xxgh1)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益解:编写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,

8、fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh2)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益s.t.改写为：例3 问题一的解答问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益编写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

9、0 1;beq=400 600 500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益结果:x=0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.为了规范事业单位聘用关系，建立和完善适

10、应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例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)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工

11、的合法权益结果为：x=9.0000 0.0000fval=360即只需聘用9个一级检验员.注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.返回为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益用LINDO、LINGO优化工具箱解线性规划为了规范事业单位聘用关系，建立和完善适应社会主义市场经济

12、体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益一、LINDO软件包 下面我们通过一个例题来说明LINDO软件包的使用方法.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益LINDO和LINGO软件能求解的优化模型 LINGO LINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益1桶牛奶3千克A112小时8小时4千克A2或获利24元/千克获利16元/千克50桶

13、牛奶 时间:480小时 至多加工100千克A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到 30元/千克，是否应改变生产计划？每天：例1 加工奶制品的生产计划为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应劳动时间加工能力决策变量 目标函数 每天获利约束条件非负约束线性规划模型(LP)建立模型为了规范事业单位聘用关系，建立和完善适应社会主义市场经

14、济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION V ALUE 1)3360.000 V ARIABLE V ALUE 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=

15、2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元.模型求解为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 OBJECTIVE FUNCTION V ALUE 1)3360.000 V ARIABLE V ALUE 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.

16、000000 4)40.000000 0.000000原料无剩余时间无剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益模型求解 reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）,目标函数减少的量(对max型问题).OBJECTIVE FUNCTION V ALUE 1)3360.000 V ARIABLE V ALUE RE

17、DUCED 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也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 OBJECTIVE FUNCTION V ALUE 1)3360.000 V ARI

18、ABLE V ALUE 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 48,应该买！聘用临时工人付出的工资最多每小时几元？2元！为了规范事业单位聘用关系，建立和完善适应社会主义

19、市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES V ARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 5

20、0.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最优解不变时目标系数允许变化范围 DO RANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x2系数范围(48,72)A1获利增加到 30元/千克，应否改变生产计划 x1系数由243=72 增加为303=90，在允许范围内 不变！(约束条件不变)结果解释 为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益结果解释

21、RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES V ARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围 原料最多增加10 时间最多增加53 35元可买到1桶牛奶，每天最多买多少？最多买10桶(目标函数不变)注意:充分但可能不必要