数学建模中的优化模型

简要提纲1.优化模型简介2.简单的优化模型3.数学规划模型4.图论，动态规划(选讲)5.建模与求解实例1.优化模型简介优化问题的一般形式无约束优化:最优解的分类和条件约束优化的简单分类优化建模如何创新？•方法1：大胆创新，别出心裁----采用有特色的目标函数、约束条件等----你用非线性规划，我用线性规划----你用整数/离散规划，我用连续规划/网络优化----……•方法2：细致入微，滴水不漏----对目标函数、约束条件处理特别细致----有算法设计和分析，不仅仅是简单套用软件----敏感性分析详细/全面----……建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y<5改为x<5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)常用优化软件1.LINGO软件2.MATLAB优化工具箱3.EXCEL软件的优化功能4.SAS(统计分析)软件的优化功能5.其他2.简单的优化模型——生猪的出售时机饲养场每天投入4元资金，用于饲料、人力、设备，估计可使80千克重的生猪体重增加2公斤。问题市场价格目前为每千克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，若当前出售，利润为80×8=640（元）t天出售=10Q(10)=660>640g=0.1敏感性分析研究r,g变化时对模型结果的影响估计r=2，g=0.1

设g=0.1不变t对r的（相对）敏感度生猪每天体重增加量r增加1%，出售时间推迟3%。rt敏感性分析估计r=2，g=0.1研究r,g变化时对模型结果的影响

设r=2不变t对g的（相对）敏感度生猪价格每天的降低量g增加1%，出售时间提前3%。gt强健性分析保留生猪直到利润的增值等于每天的费用时出售由S(t,r)=3建议过一周后(t=7)重新估计,再作计算。研究r,g不是常数时对模型结果的影响w=80+rtw=w(t)p=8-gtp=p(t)若(10%),则（30%）每天利润的增值每天投入的资金3.

数学规划模型例1汽车厂生产计划例2加工奶制品的生产计划例3运输问题

如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.

小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234

制订月生产计划，使工厂的利润最大.设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解

3）模型中增加条件：x1,x2,x3

均为整数，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.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*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

IP结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划

若生产某类汽车，则至少生产80辆，求生产计划.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINGO中对0-1变量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1变量，化为整数规划

M为大的正数,本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生产某类汽车，则至少生产80辆，求生产计划.x1=0或

80x2=0或

80x3=0或

80最优解同前

max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;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或

80最优解同前.一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.

例2加工奶制品的生产计划1桶牛奶

3公斤A1

12小时

8小时

4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：问题1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天基本模型模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工A1,A2的数量,时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解

软件实现

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三种资源“资源”剩余为零的约束为紧约束（有效约束）原料无剩余时间无剩余加工能力剩余40结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最优解下“资源”增加1单位时“效益”的增量影子价格35元可买到1桶牛奶，要买吗?35<48,应该买！

聘用临时工人付出的工资最多每小时几元?2元！原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最优解不变时目标函数系数允许变化范围敏感性分析

(“LINGO|Ranges”)

x1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/公斤，应否改变生产计划?x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶,每天最多买多少?最多买10桶!(目标函数不变)充分条件!

生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大。例3运输问题其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例3运输问题---自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40<总需求量：120+180=300总收入900160=144,000(元)收入：900元/千吨

其他费用:450元/千吨

支出引水管理费其他支出450160=72,000(元)使引水管理费最小供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量模型求解

部分结果：ObjectiveValue:24400.00VariableValueReducedCostX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利润=总收入-其它费用-引水管理费=144000-