《数学建模中的优化模型（课堂PPT）》由会员分享，可在线阅读，更多相关《数学建模中的优化模型（课堂PPT）（38页珍藏版）》请在金锄头文库上搜索。
1、1,简要提纲,1. 优化模型简介 2. 简单的优化模型 3. 数学规划模型 4. 图论，动态规划(选讲) 5. 建模与求解实例,2,1. 优化模型简介,3,优化问题的一般形式,4,无约束优化:最优解的分类和条件,5,约束优化的简单分类,6,优化建模如何创新？, 方法1：大胆创新，别出心裁 - 采用有特色的目标函数、约束条件等 - 你用非线性规划，我用线性规划 - 你用整数/离散规划，我用连续规划/网络优化 - 方法2：细致入微，滴水不漏 - 对目标函数、约束条件处理特别细致 - 有算法设计和分析，不仅仅是简单套用软件 - 敏感性分析详细/ 全面 - ,7,建模时需要注意的几个基本问题,1、尽量
2、使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求 最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变 量的个数（如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于103),8,常用优化软件,1. LINGO软件 2. MATLAB优化工具箱 3. EXCEL软件的优化功能 4. SAS(统计分析)软件的优化功能 5. 其他,9,2.简单的优化模型 生猪的出售时机,饲养场每天投入4元资金，用于饲料、人力、设备，估计可使80千克
3、重的生猪体重增加2公斤。,问题,市场价格目前为每千克8元，但是预测每天会降低 0.1元，问生猪应何时出售。,如果估计和预测有误差，对结果有何影响。,分析,投入资金使生猪体重随时间增加，出售单价随时间减少，故存在最佳出售时机，使利润最大,10,求 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,11,敏感性分析,研究 r, g变化时对模型结果的影响,
4、设g=0.1不变,t 对r 的（相对）敏感度,生猪每天体重增加量r 增加1%，出售时间推迟3%。,12,敏感性分析,研究 r, g变化时对模型结果的影响,设r=2不变,t 对g的（相对）敏感度,生猪价格每天的降低量g增加1%，出售时间提前3%。,13,强健性分析,保留生猪直到利润的增值等于每天的费用时出售,由 S(t,r)=3,建议过一周后(t=7)重新估计 , 再作计算。,研究 r, g不是常数时对模型结果的影响,w=80+rt w = w(t),p=8-gt p =p(t),若 (10%), 则 （30%）,14,3. 数学规划模型,例1 汽车厂生产计划 例2 加工奶制品的生产计划 例3
5、运输问题,15,如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？,例1 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,制订月生产计划，使工厂的利润最大.,16,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,汽车厂生产计划,模型建立,线性规划模型(LP),17,模型求解,3）模型中增加条件：x1, x2, x3 均为整数，重新求解.,Objective Value: 632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167
6、.741928 0.000000 X3 0.000000 0.946237 Row Slack or Surplus Dual Price 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，通过比较可能得到更优的解.,但必须检验它们是否满足约束条件. 为什么？,18,IP可用LINGO直接求解,整数规划(Integer Programming,简记IP)
7、,IP 的最优解x1=64，x2=168，x3=0，最优值z=632,max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3600; 280*x1+250*x2+400*x3 60000; 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
8、-3.000000 X3 0.000000 -4.000000,模型求解,IP 结果输出,19,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划.,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最优值z=610,20,LINGO中对0-1变量的限定： bin(y1); bin(y2); bin(y3);,方法2：引入0-1变量，化为整数规划,M为大的正数,本例可取1000,Objective Value: 610.0000 Variable Val
9、ue Reduced Cost X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0 或 80,最优解同前,21,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：化为非线性规划,非线性规划（N
10、on- Linear Programming，简记NLP）,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0 或 80,最优解同前.,一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.,22,例2 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,问题,23,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164
11、x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,基本模型,24,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工A1,A2的数量, 时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数,加工A1
12、,A2的牛奶桶数是实数,线性规划模型,25,模型求解,图解法,约束条件,目标函数,z=c (常数) 等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,26,模型求解,软件实现,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
13、iterations: 2 Variable 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,20桶牛奶生产A1, 30桶生产A2，利润3360元。,27,结果解释,Global optimal solution found. Objective value: 3360.000 To
14、tal solver iterations: 2 Variable 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,model: max = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,三种资源
15、,“资源” 剩余为零的约束为紧约束（有效约束）,28,结果解释,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 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元！,29,Ranges in which the basis is unchanged: Objective Coefficien
