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公斤。,问题,市场
3、价格目前为每千克8元，但是预测每天会降低 0.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 的（相对）敏感度,生
4、猪每天体重增加量r 增加1%，出售时间推迟3%。,敏感性分析,研究 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辆， 那么最优的生
5、产计划应作何改变？,例1 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,制订月生产计划，使工厂的利润最大.,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3）模型中增加条件：x1, x2, x3 均为整数，重新求解.,Objective Value: 632.2581Variable Value Reduced CostX1 64.516129 0.000000X2 167.741928 0.000000X3 0.000000 0.946237Row Slack
6、 or Surplus Dual Price2 0.000000 0.7311833 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*x
7、3; 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.0000Extended solver steps: 0Total solver iterations: 3Variable Value Reduced CostX1 64.00000 -2.000000X2 168.0000 -3.000000X3 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.0000Variable Value Reduced CostX1 80.000000 -2.000000X2 150.000000 -3.000000X3 0.0
9、00000 -4.000000Y1 1.000000 0.000000Y2 1.000000 0.000000Y3 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.000Total solver iterations: 2Variable Value Reduced Cost X1 20.00000 0.000000X2 30.00000 0.000000Row Slack o
13、r Surplus Dual Price1 3360.000 1.000000MILK 0.000000 48.00000TIME 0.000000 2.000000CPCT 40.00000 0.000000,20桶牛奶生产A1, 30桶生产A2，利润3360元。,结果解释,Global optimal solution found.Objective value: 3360.000Total solver iterations: 2Variable Value Reduced CostX1 20.00000 0.000000X2 30.00000 0.000000Row Slack or
14、Surplus Dual Price1 3360.000 1.000000MILK 0.000000 48.00000TIME 0.000000 2.000000CPCT 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.000Total solver iterations: 2Va
15、riable Value Reduced CostX1 20.00000 0.000000X2 30.00000 0.000000Row Slack or Surplus Dual Price1 3360.000 1.000000MILK 0.000000 48.00000TIME 0.000000 2.000000CPCT 40.00000 0.000000,最优解下“资源”增加1单位时“效益”的增量,影子价格,35元可买到1桶牛奶，要买吗?,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,Ranges in which the basis is unchanged:
16、Objective Coefficient RangesCurrent Allowable Allowable Variable Coefficient Increase DecreaseX1 72.00000 24.00000 8.000000X2 64.00000 8.000000 16.00000Righthand Side RangesRow Current Allowable AllowableRHS Increase DecreaseMILK 50.00000 10.00000 6.666667TIME 480.0000 53.33333 80.00000CPCT 100.0000
17、 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 RangesCurrent Allowable Allowable Variable Coefficient Increase DecreaseX1 72
18、.00000 24.00000 8.000000X2 64.00000 8.000000 16.00000Righthand Side RangesRow Current Allowable AllowableRHS Increase DecreaseMILK 50.00000 10.00000 6.666667TIME 480.0000 53.33333 80.00000CPCT 100.0000 INFINITY 40.00000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶, 每天最多买多少?,最多买10桶!,(目标函数不变),充分条件
19、 !,生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大。,例3 运输问题,其他费用:450元/千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,例3运输问题-自来水输送,收入：900元/千吨,支出,总供水量：160,确定送水方案使利润最大,问题分析, 总需求量：120+180=300,总收入900160=144,000(元),收入：900元/千吨,其他费用:450元/千吨,支出,引水管理费,其他支出450160=72,000(元),供应限制,约束条件,需求限制,线性规划模型(LP),目标函数,水库i 向j 区的日供
20、水量为 xij（x34=0）,决策变量,模型建立,确定3个水库向4个小区的供水量,模型求解,部分结果： Objective Value: 24400.00Variable Value Reduced CostX11 0.000000 30.000000X12 50.000000 0.000000X13 0.000000 50.000000X14 0.000000 20.000000X21 0.000000 10.000000X22 50.000000 0.000000X23 0.000000 20.000000X24 10.000000 0.000000X31 40.000000 0.0000
21、00X32 0.000000 10.000000X33 10.000000 0.000000,利润=总收入-其它费用-引水管理费=144000-72000-24400 = 47600（元）,引水管理费 24400(元),目标函数,总供水量(320) 总需求量(300),每个水库最大供水量都提高一倍,利润 = 收入(900) 其它费用(450) 引水管理费,供应限制,B, C 类似处理,问题讨论,确定送水方案使利润最大,需求约束可以不变,求解,部分结果： Objective Value: 88700.00Variable Value Reduced CostX11 0.000000 20.000
22、000X12 100.000000 0.000000X13 0.000000 40.000000X14 0.000000 20.000000X21 30.000000 0.000000X22 40.000000 0.000000X23 0.000000 10.000000X24 50.000000 0.000000X31 50.000000 0.000000X32 0.000000 20.000000X33 30.000000 0.000000,运输问题,总利润 88700（元）,供需平衡或不平衡,优化模型历年真题题目,出版社资源配置 (2006A) 制动器试验台的控制方法(2009A) 储油罐的变位识别与罐容表标定 (2010A) 城市表层土壤重金属污染分析(2011A),
