数学建模中的优化模型

简要提纲1.优化模型简介2.简单的优化模型3.数学规划模型4.图论，动态规划(选讲)5.建模与求解实例1.优化模型简介优化问题的一般形式无约束优化:最优解的分类和条件约束优化的简单分类优化建模如何创新？•方法1：大胆创新，别出心裁----采用有特色的目标函数、约束条件等----你用非线性规划，我用线性规划----你用整数/离散规划，我用连续规划/网络优化----……•方法2：细致入微，滴水不漏----对目标函数、约束条件处理特别细致----有算法设计和分析，不仅仅是简单套用软件----敏感性分析详细/全面----……建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y5改为x5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)常用优化软件1.LINGO软件2.MATLAB优化工具箱3.EXCEL软件的优化功能4.SAS(统计分析)软件的优化功能5.其他2.简单的优化模型——生猪的出售时机饲养场每天投入4元资金，用于饲料、人力、设备，估计可使80千克重的生猪体重增加2公斤。问题市场价格目前为每千克8元，但是预测每天会降低0.1元，问生猪应何时出售。如果估计和预测有误差，对结果有何影响。分析投入资金使生猪体重随时间增加，出售单价随时间减少，故存在最佳出售时机，使利润最大trtgttQ4)80)(8()(求t使Q(t)最大rggrt240410天后出售，可多得利润20元建模及求解生猪体重w=80+rt出售价格p=8-gt销售收入R=pw资金投入C=4t利润Q=R-C=pw-C估计r=2，若当前出售，利润为80×8=640（元）t天出售=10Q(10)=660640g=0.1敏感性分析研究r,g变化时对模型结果的影响估计r=2，g=0.1rggrt2404•设g=0.1不变5.1,6040rrrtt对r的（相对）敏感度rrttrtS/Δ/Δ),(trdrdt3604060),(rrtS生猪每天体重增加量r增加1%，出售时间推迟3%。1.522.5305101520rt敏感性分析估计r=2，g=0.1rggrt2404研究r,g变化时对模型结果的影响•设r=2不变15.00,203gggtt对g的（相对）敏感度tgdgdtggttgtS/Δ/Δ),(32033),(ggtS生猪价格每天的降低量g增加1%，出售时间提前3%。0.060.080.10.120.140.160102030gt强健性分析保留生猪直到利润的增值等于每天的费用时出售由S(t,r)=3建议过一周后(t=7)重新估计,再作计算。wwpp,,,研究r,g不是常数时对模型结果的影响w=80+rtw=w(t)4)()()()(twtptwtpp=8-gtp=p(t)若(10%),则（30%）2.28.1w137t0)(tQ每天利润的增值每天投入的资金ttwtptQ4)()()(3.数学规划模型例1汽车厂生产计划例2加工奶制品的生产计划例3运输问题•如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234•制订月生产计划，使工厂的利润最大.设每月生产小、中、大型汽车的数量分别为x1,x2,x3321432xxxzMax600535.1..321xxxts60000400250280321xxx0,,321xxx汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解3）模型中增加条件：x1,x2,x3均为整数，重新求解.ObjectiveValue:632.2581VariableValueReducedCostX164.5161290.000000X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大.2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.•但必须检验它们是否满足约束条件.为什么？IP可用LINGO直接求解整数规划(IntegerProgramming,简记IP)IP的最优解x1=64，x2=168，x3=0，最优值z=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;@gin(x1);@gin(x2);@gin(x3);Globaloptimalsolutionfound.Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCostX164.00000-2.000000X2168.0000-3.000000X30.000000-4.000000321432xxxzMax600535.1..321xxxts60000400250280321xxx为非负整数321,,xxx模型求解IP结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：80,0,0321xxx0,80,0321xxx80,80,0321xxx0,0,80321xxx0,80,80321xxx80,0,80321xxx80,80,80321xxx0,,321xxx方法1：分解为8个LP子模型汽车厂生产计划•若生产某类汽车，则至少生产80辆，求生产计划.321432xxxzMax600535.1..321xxxts60000400250280321xxxx1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINGO中对0-1变量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1变量，化为整数规划M为大的正数,本例可取1000ObjectiveValue:610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000•若生产某类汽车，则至少生产80辆，求生产计划.x1=0或80x2=0或80x3=0或80}1,0{,80,11111yyxMyx}1,0{,80,22222yyxMyx}1,0{,80,33333yyxMyx最优解同前max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;x1*(x1-80)0;x2*(x2-80)0;x3*(x3-80)0;@gin(x1);@gin(x2);@gin(x3);方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）•若生产某类汽车，则至少生产80辆，求生产计划.x1=0或80x2=0或80x3=0或800)80(11xx0)80(22xx0)80(33xx最优解同前.一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.例2加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天：问题1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天基本模型模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工A1,A2的数量,时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解图解法x1x20ABCDl1l2l3l4l55021xx48081221xx10031x0,21xx约束条件50:211xxl480812:212xxl1003:13xl0:,0:2514xlxl216472xxzMax目标函数Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解软件实现LINGOmodel:max=72*x1+64*x2;[milk]x1+x250;[time]12*x1+8*x2480;[cpct]3*x1100;endGlobaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.00000020桶牛奶生产A1,30桶生产A2，利润3360元。结果解释Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000model:max=72*x1+64*x2;[milk]x1+x250;[time]12*x1+8*x2480;[cpct]3*x1100;end三种资源“资源”剩余为零的约束为紧约束（有效约束）原料无剩余时间无剩余加工能力剩余40结果解释Globaloptimalsoluti