最优化模型的建立步骤

（优选）最优化模型的建立步骤目前一页\总数九十四页\编于十五点

本次数学建模集训班（2011年全国大学生数学建模竞赛预备班）共有来自全校13个分院328位同学报名，经过数学建模教练组的认真审查遴选，共有232名同学进入提高班学习。

提高班将分两个班进行，其中提高班1班，将采用上午上课，下午上机练习；提高班2采用下午上课，晚上上机练习方式进行，每周末提高课结束后将会有适当的练习留给大家，请大家务必在次周周三晚21点前上交作业电子版，作业提交邮箱，提高班1：;提高班2：，作业以附件形式提交，文件名：XXX第X次作业

集训班概况及相关要求目前二页\总数九十四页\编于十五点

上机地点：求中502，503；主要提供给没有电脑的同学使用，并请自备U盘，有电脑的同学也可选择到机房或在宿舍里自行完成，我们需要的是过程，更重要的是实效，因此请每个人都自觉完成。

机房开放时间：每周周六下午、晚上；周日全天；上午：8：30～11：30下午1：30～16：30，晚：18：00～21：00

个人电脑需要安装的软件：matlab,lingo,spss等,其中word里要把公式编辑器装上，或装上mathtype;

目前三页\总数九十四页\编于十五点

2010计量数模QQ群：94504719，请大家加入；其中群共享里可以下载到每次课的课件；另外有问题也可以在里面询问，讨论，这是一个大家共同探讨心声的地方。

提高班将在5月底结束，根据个人意愿、提高班表现、校赛成绩等择优选拔120人左右进入暑假全国大学生数学建模竞赛集训队，根据集训效果再选拔约100人左右参加全国比赛，本部组队25支左右，其中现科单独组队5～8支。目前四页\总数九十四页\编于十五点我们的数模之旅。。。2010年9月中旬cumcm华山论剑2010年4月启程2010年5月底jlmcm小试牛刀2010年7月中旬cumcm集训第一阶段（3weeks）2010年8月下旬cumcm集训第二阶段（15d）2010年11月mcm&icm集训第一阶段2011年1月mcm&icm集训第二阶段2011年2月mcm&icm武林大会目前五页\总数九十四页\编于十五点本次提高班的具体安排1.第6周周六：规划模型、案例及软件求解（王义康）2.第7周周六：统计回归模型及软件求解（刘学艺）3.第8周周日：微分方程模型及软件求解（尚绪凤）4.第10周周六：多元统计模型及软件求解（沈进东）5.第11周周日：排队论模型及蒙特卡洛模拟（柴中林）6.第12周周六：网络优化模型及案例分析（赵承业）

第二届中国计量学院数学建模竞赛（5.24～5.31）目前六页\总数九十四页\编于十五点历届竞赛赛题基本解法赛题解法93A非线性交调的频率设计拟合、规划93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划94B锁具装箱问题图论、组合数学95A飞行管理问题非线性规划、线性规划95B天车与冶炼炉的作业调度动态规划、排队论、图论96A最优捕鱼策略微分方程、优化96B节水洗衣机非线性规划目前七页\总数九十四页\编于十五点历届竞赛赛题基本解法97A零件的参数设计非线性规划97B截断切割的最优排列随机模拟、图论98A一类投资组合问题多目标优化、非线性规划98B灾情巡视的最佳路线图论、组合优化99A自动化车床管理随机优化、计算机模拟99B钻井布局0-1规划、图论00ADNA序列分类模式识别、Fisher判别、人工神经网络00B钢管订购和运输组合优化、运输问题目前八页\总数九十四页\编于十五点历届竞赛赛题基本解法01A血管三维重建曲线拟合、曲面重建01B工交车调度问题多目标规划02A车灯线光源的优化非线性规划02B彩票问题单目标决策03ASARS的传播微分方程、差分方程03B露天矿生产的车辆安排整数规划、运输问题04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化目前九页\总数九十四页\编于十五点历届竞赛赛题基本解法05A长江水质的评价和预测

聚类、模糊评判主成分分析、多目标决策

05BDVD在线租赁

多目标规划06A出版社的资源配置

线性规划、多目标规划

06B艾滋病疗法评价及疗效预测

回归线性规划

07A中国人口增长预测问题

微分方程、差分方程07B乘公交，看奥运问题

图论、0-1规划、动态规划

08A数码相机定位问题几何、优化08B高等教育学费标准探讨多元回归、多目标优化目前十页\总数九十四页\编于十五点规划模型、案例及软件求解目前十一页\总数九十四页\编于十五点一、引言

二、线性规划模型及软件求解三、整数规划模型

四、0-1规划模型

五、几种常用的线性规划模型

八、非线性规划模型（暑假）

六、多目标规划模型

七、二次规划（暑假）目前十二页\总数九十四页\编于十五点

在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-09年全国大学生数模竞赛试题的解题方法统计结果来看，规划模型共出现了18次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解.

如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在数学建模中处于中心的地位.这类问题一般可以归结为数学规划模型.规划模型的应用极其广泛，其作用已为越来越多的人所重视.一、引言目前十三页\总数九十四页\编于十五点（一）规划模型的数学描述下的最大值或最小值，其中决策变量目标函数将一个优化问题用数学式子来描述，即求函数在约束条件和可行域规划模型的一般意义目前十四页\总数九十四页\编于十五点“受约束于”之意目前十五页\总数九十四页\编于十五点（二）规划模型的分类1.根据是否存在约束条件有约束问题和无约束问题。2.根据决策变量的性质静态问题和动态问题。3.根据目标函数和约束条件表达式的性质线性规划，非线性规划，二次规划，多目标规划等。目前十六页\总数九十四页\编于十五点（1）非线性规划目标函数和约束条件中，至少有一个非线性函数。目前十七页\总数九十四页\编于十五点（2）线性规划（LP）

目标函数和所有的约束条件都是设计变量的线性函数。目前十八页\总数九十四页\编于十五点（3）二次规划问题目标函数为二次函数，约束条件为线性约束目前十九页\总数九十四页\编于十五点5.根据变量具有确定值还是随机值

确定规划和随机规划。4.根据决策变量的允许值整数规划（0-1规划）和实数规划。目前二十页\总数九十四页\编于十五点（三）建立规划模型的一般步骤1.确定决策变量和目标变量；2.确定目标函数的表达式；3.寻找约束条件。目前二十一页\总数九十四页\编于十五点二、线性规划模型及软件求解目前二十二页\总数九十四页\编于十五点例1：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用两种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？目前二十三页\总数九十四页\编于十五点解

设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：

解答目前二十四页\总数九十四页\编于十五点例2：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：目前二十五页\总数九十四页\编于十五点故目标函数为：约束条件为：目前二十六页\总数九十四页\编于十五点线性规划模型：

解答返回目前二十七页\总数九十四页\编于十五点线性规划模型的求解Lingo与Lindo求解Matlab求解目前二十八页\总数九十四页\编于十五点Lingo与LindoLindo与Lingo都是LINDO系统公司开发的专门用于求解最优化问题的软件包。与Lindo相比，Lingo软件主要具有两大优点：（1）除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题。（2）LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中。目前二十九页\总数九十四页\编于十五点例1的Lingo求解model:min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6;x1+x4=400;x2+x5=600;x3+x6=500;0.4*x1+1.1*x2+x3<800;0.5*x1+1.2*x2+1.3*x3<900;end目前三十页\总数九十四页\编于十五点例2的Lingo求解!例2的Lingo求解;model:min=40*x1+36*x2;5*x1+3*x2>=45;x1<=9;x2<=15;end目前三十一页\总数九十四页\编于十五点例3加工奶制品的生产计划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

原料供应

劳动时间

加工能力

决策变量

目标函数

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

时间480小时至多加工100公斤A1

50桶牛奶每天目前三十三页\总数九十四页\编于十五点综上所述Maxz=72x1+64x2；s.t.x1+x2≤50，

12x1+8x2≤480，

3x1≤100，

x1，x2≥0Matlab解答目前三十四页\总数九十四页\编于十五点Lingo模型这是一个（连续）线性规划（LP）问题目前三十五页\总数九十四页\编于十五点“LINGO|Solve”求解结果报告“LINGO|Range”敏感性分析max=72*x1+64*x2;x1+x2<=50;12*x1+8*x2<=480;3*x1<=100;目前三十六页\总数九十四页\编于十五点灵敏度分析敏感性分析的作用是给出“Rangesinwhichthebasisisunchanged”，即研究当目标函数的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基（矩阵）保持不变。注意：这里LINGO不询问是否进行敏感性分析。如果需要进行敏感性分析，必须用“LINGO|Options”命令打开系统选项对话框，在“GeneralSolver”标签下的“DualComputations”下拉列表中选中“Prices&Range”，再按下“OK”按钮激活敏感性分析功能。修改了系统选项后，以后只需调用“LINGO|Range”命令即可进行敏感性分析了。

目前三十七页\总数九十四页\编于十五点修改运行时的内存限制激活灵敏度分析目前三十八页\总数九十四页\编于十五点结论应该批准用35元买1桶牛奶的投资，但每天最多购买10桶牛奶。可以用低于2元/h的工资聘用临时工人以增加劳动时间，但最多增加53.3333h。若每千克A1的获利增加到30元，则x1系数变为30×3=90，在允许的范围内，所以不应改变生产计划，但最优值变为90×20+64×30=3720。目前三十九页\总数九十四页\编于十五点

例4SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元，假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？目前四十页\总数九十四页\编于十五点

DEM——需求量，RP——正常生产的产量，OP——加班生产的产量，INV——库存量

目标函数：

约束条件：

能力限制RP(I)≤40，I=1，2，3，4

产品数量的平衡方程

INV（I）＝INV（I－1）＋RP（I）＋OP（I）－DEM（I）Ｉ＝１，２，３，４ INV（０）＝10；

变量的非负约束目前四十一页\总数九十四页\编于十五点Lingo优化模型集合属性集合的属性相当于以集合的元素为下标的数组目前四十二页\总数九十四页\编于十五点Lingo模型的基本要素（1）集合段（SETS）（2）目标与约束段（3）数据段（DATA）：作用在于对集合的属性（数组）输入必要的常数数据。格式为：

attribute(属性)=value_list(常数列表);

常数列表（value_list）中数据之间可以用逗号“,”分 开，也可以用空格分开（回车的作用也等价于一个空 格） “变量名=?;”——运行时赋值（4）初始段（INIT）——赋初值（5）计算段（CALC）——预处理目前四十三页\总数九十四页\编于十五点MATLAB中有关求解线性规划问题的指令X=linprog(c,A,b,Aeq,beq)

X=linprog(c,A,b,Aeq,beq,vlb,vub)X=linprog(c,A,b,Aeq,beq,vlb,vub,x0)X=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options)[x,fval,exitflag,output]=linprog(…)目前四十四页\总数九十四页\编于十五点用MATLAB优化工具箱解线性规划minz=cX

1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].目前四十五页\总数九十四页\编于十五点3、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点4、命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.目前四十六页\总数九十四页\编于十五点解编写M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

xxgh1.m目前四十七页\总数九十四页\编于十五点解:编写M文件xxgh2.m如下：

c=[634];A=[010];b=[50];Aeq=[111];beq=[120];vlb=[30,0,20];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh2)目前四十八页\总数九十四页\编于十五点S.t.改写为：例1的Matlab求解

问题目前四十九页\总数九十四页\编于十五点编写M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh3)目前五十页\总数九十四页\编于十五点结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004

即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。目前五十一页\总数九十四页\编于十五点例2的Matlab求解

问题改写为：目前五十二页\总数九十四页\编于十五点编写M文件xxgh4.m如下：c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%调用linprog函数：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh4)目前五十三页\总数九十四页\编于十五点结果为：x=9.00000.0000fval=360即只需聘用9个一级检验员。

注：本问题应还有一个约束条件：x1、x2取整数。故它是一个整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。目前五十四页\总数九十四页\编于十五点例3的Matlab求解

问题max=72*x1+64*x2;x1+x2<=50;12*x1+8*x2<=480;3*x1<=100;编写M文件如下：c=[-72-64];A=[11;128;30];b=[50480100];Aeq=[];beq=[];%调用linprog函数：[x,fval]=linprog(c,A,b,Aeq,beq)结果为：x=20.000030.0000fval=-3.3600e+003即用20桶牛奶生产X1，30桶牛奶生产X2。

目前五十五页\总数九十四页\编于十五点五、几种常用的线性规划模型

设某种物资共有m个产地A1，A2，…，Am，各产地的产量分别是a1，a2，…，am；有n

个销地B1，B2，…，Bn

，各销地的销量分别为b1，b2，…，bn.

假定从产地Ai（i=1，2，…，m）向销地Bj（j=1，2，…，n）运输单位物资的运价是cij，问怎样调运才能使总运费最小？问题1运输问题目前五十六页\总数九十四页\编于十五点1、产销平衡问题即

设

xij

表示产地

Ai

运往销地

Bj

(i=1,2,…,m;

j=1,2,…,n)

的运量.目前五十七页\总数九十四页\编于十五点2、产销不平衡问题当当目前五十八页\总数九十四页\编于十五点

问题2生产组织与计划问题

工厂用种设备生产种产品在一个生产周期内,已知第台设备只能工作个机时.工厂必须完成产品至少件.设备生产所需要的机时和成本分别为试建立相应的数学模型,使设备能在计划周期内完成计划但又使成本达到最低.目前五十九页\总数九十四页\编于十五点

模型为目前六十页\总数九十四页\编于十五点

问题3工厂选址问题

设有个需求点（城市,仓库,商店等）,有个可供选择的建厂地址,每个地址最多可建一个工厂.在地址建立工厂的生产能力为在地址经营工厂,单位时间的固定成本为需求点的需求量为从厂址到需求点的单位运费为问应如何选择厂址和安排运输计划,使相应的成本为最小.目前六十一页\总数九十四页\编于十五点

模型为目前六十二页\总数九十四页\编于十五点上式中的意义是:在地址建厂,不在地址建厂.这样的线性规划称为混合型的整数线性规划.目前六十三页\总数九十四页\编于十五点

问题4设备购置和安装问题

工厂需要种设备设备的单价为工厂已有第种设备台,今有资金元,可用于购置这些设备.该厂有处可安装这些设备,

处最多可安装台,将一台设备安装在处,经济效益为元,问应如何购置和安装这些设备,才能使总的经济效益最高.

以表示设备在处安装的台数,表示购置目前六十四页\总数九十四页\编于十五点的台数,则模型为目前六十五页\总数九十四页\编于十五点目前六十六页\总数九十四页\编于十五点

问题5货郎问题

货郎要到个地方去卖货.已知两个地方和之间的距离为如何选择一条道路,使得货郎每个地方走一遍后回到起点,且所走的路径最短.

定义货郎选择的路线包含从到的路径否则目前六十七页\总数九十四页\编于十五点则相应的模型为目前六十八页\总数九十四页\编于十五点

问题6系统可靠性问题

选择个元件,组成一个并联系统.设第个位置所用的元件可从集合中挑选.对元件用表示元件在第个位置上的花费,表示其可靠性的概率,问应如何配置各位置上的元件,使得系统的可靠性不小于且使总费用最小.

定义若元件且元件用在位置上若元件且元件不用在位置上目前六十九页\总数九十四页\编于十五点总费用为其可靠性为若记则上式可写成相应的模型转化为规划.目前七十页\总数九十四页\编于十五点

模型为目前七十一页\总数九十四页\编于十五点六、多目标规划模型

在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个生产计划的例子.目前七十二页\总数九十四页\编于十五点目前七十三页\总数九十四页\编于十五点目前七十四页\总数九十四页\编于十五点目前七十五页\总数九十四页\编于十五点目前七十六页\总数九十四页\编于十五点目前七十七页\总数九十四页\编于十五点目前七十八页\总数九十四页\编于十五点目前七十九页\总数九十四页\编于十五点目前八十页\总数九十四页\编于十五点目前八十一页\总数九十四页\编于十五点目前八十二页\总数九十四页\编于十五点

投资的收益和风险目前八十三页\总数九十四页\编于十五点二、基本假设和符号规定目前八十四页\总数九十四页\编于十五点三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…n}4.模型简化：目前八十五页\总数九十四页\编于十五点a.在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/M≤a，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。目前八十六页\总数九十四页\编于十五点b．若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。目前八十七页\总数九十四页\编于十五点c．投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0＜s≤1)，s称为投资偏好系数.目前八十八页\总数九十四页\编于十五点四、模型1的求解

由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：目前八十九页\总数九十四页\编于十五点a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];