《数学建模中的优化模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模中的优化模型ppt课件.ppt（38页珍藏版）》请在三一办公上搜索。
1、简要提纲,1. 优化模型简介2. 简单的优化模型3. 数学规划模型 4. 图论，动态规划(选讲) 5. 建模与求解实例,1. 优化模型简介,优化问题的一般形式,无约束优化:最优解的分类和条件,约束优化的简单分类,优化建模如何创新？, 方法1：大胆创新，别出心裁- 采用有特色的目标函数、约束条件等- 你用非线性规划，我用线性规划- 你用整数/离散规划，我用连续规划/网络优化- 方法2：细致入微，滴水不漏- 对目标函数、约束条件处理特别细致- 有算法设计和分析，不仅仅是简单套用软件- 敏感性分析详细/ 全面- ,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用
2、光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103),常用优化软件,1. LINGO软件2. MATLAB优化工具箱3. EXCEL软件的优化功能4. SAS(统计分析)软件的优化功能5. 其他,2.简单的优化模型生猪的出售时机,饲养场每天投入4元资金，用于饲料、人力、设备，估计可使80千克重的生猪体重增加2公斤。,问题,市场价格目前为每千克8元，但是预测每天会降低 0
3、.1元，问生猪应何时出售。,如果估计和预测有误差，对结果有何影响。,分析,投入资金使生猪体重随时间增加，出售单价随时间减少，故存在最佳出售时机，使利润最大,求 t 使Q(t)最大,10天后出售，可多得利润20元,建模及求解,生猪体重 w=80+rt,出售价格 p=8-gt,销售收入 R=pw,资金投入 C=4t,利润 Q=R-C=pw -C,估计r=2，,若当前出售，利润为808=640（元）,t 天出售,=10,Q(10)=660 640,g=0.1,敏感性分析,研究 r, g变化时对模型结果的影响,设g=0.1不变,t 对r 的（相对）敏感度,生猪每天体重增加量r 增加1%，出售时间推迟3
4、%。,敏感性分析,研究 r, g变化时对模型结果的影响,设r=2不变,t 对g的（相对）敏感度,生猪价格每天的降低量g增加1%，出售时间提前3%。,强健性分析,保留生猪直到利润的增值等于每天的费用时出售,由 S(t,r)=3,建议过一周后(t=7)重新估计 , 再作计算。,研究 r, g不是常数时对模型结果的影响,w=80+rt w = w(t),p=8-gt p =p(t),若 (10%), 则 （30%）,3. 数学规划模型,例1 汽车厂生产计划例2 加工奶制品的生产计划例3 运输问题,如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？,例1 汽车厂生产计划,汽车厂
5、生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,制订月生产计划，使工厂的利润最大.,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3）模型中增加条件：x1, x2, x3 均为整数，重新求解.,Objective Value: 632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 Row Slack or Surplus Dual Pr
6、ice 2 0.000000 0.731183 3 0.000000 0.003226,结果为小数，怎么办？,1）舍去小数：取x1=64，x2=167，算出目标函数值 z=629，与LP最优值632.2581相差不大.,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.,但必须检验它们是否满足约束条件. 为什么？,IP可用LINGO直接求解,整数规划(Integer Programming,简记IP),IP 的最优解x1=64，x2=168，x3=0，最优值z=632,max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x
7、3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2);gin(x3);,Global optimal solution found. Objective value: 632.0000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 64.00000 -2.000000 X2 168.0000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 结果输出,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加
8、上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划.,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最优值z=610,LINGO中对0-1变量的限定：bin(y1); bin(y2); bin(y3);,方法2：引入0-1变量，化为整数规划,M为大的正数,本例可取1000,Objective Value: 610.0000 Variable Value Reduced Cost X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.00
9、0000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0 或 80,最优解同前,max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);,方法3：化为非线性规划,非线性规划（Non- Linear Programming，简记NLP）,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0 或 80,最优解同前.,一般地，整数规划和非线性规划的求
10、解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.,例2 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,问题,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,基本模型,模型分析与假设,比例性,可加
11、性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工A1,A2的数量, 时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c (常数) 等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形
12、,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINGO,model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Du
13、al Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,20桶牛奶生产A1, 30桶生产A2，利润3360元。,结果解释,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Su
14、rplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Va
15、riable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,最优解下“资源”增加1单位时“效益”的增量,影子价格,35元可买到1桶牛奶，要买吗?,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,Ranges in which the basis is unc
16、hanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.000
17、00 CPCT 100.0000 INFINITY 40.00000,最优解不变时目标函数系数允许变化范围,敏感性分析 (“LINGO|Ranges” ),x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/公斤，应否改变生产计划?,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Incre
18、ase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶, 每天最多买
19、多少?,最多买10桶!,(目标函数不变),充分条件 !,生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大。,例3 运输问题,其他费用:450元/千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,例3运输问题-自来水输送,收入：900元/千吨,支出,总供水量：160,确定送水方案使利润最大,问题分析, 总需求量：120+180=300,总收入900160=144,000(元),收入：900元/千吨,其他费用:450元/千吨,支出,引水管理费,其他支出450160=72,000(元),供应限制,约束条件,需求限制,线性
20、规划模型(LP),目标函数,水库i 向j 区的日供水量为 xij（x34=0）,决策变量,模型建立,确定3个水库向4个小区的供水量,模型求解,部分结果：Objective Value: 24400.00 Variable Value Reduced Cost X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.00
21、0000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000000,利润=总收入-其它费用-引水管理费=144000-72000-24400 = 47600（元）,引水管理费 24400(元),目标函数,总供水量(320) 总需求量(300),每个水库最大供水量都提高一倍,利润 = 收入(900) 其它费用(450) 引水管理费,供应限制,B, C 类似处理,问题讨论,确定送水方案使利润最大,需求约束可以不变,求解,部分结果：Objective Value: 88700.00 Variable V
22、alue Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000,运输问题,总利润 88700（元）,供需平衡或不平衡,优化模型历年真题题目,出版社资源配置 (2006A)制动器试验台的控制方法(2009A)储油罐的变位识别与罐容表标定 (2010A)城市表层土壤重金属污染分析(2011A),
