2009暑期数学建模集训专题-数学规划(完整课件含711712上课内容)

一、引言二、线性规划模型三、整数规划模型数学建模专题----规划理论及模型四、0-1规划模型五、几种常用的线性规划模型六、非线性规划模型七、多目标规划模型八、LINGO入门一、引言我们从2005年“高教社杯〞全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而到达人们期望目标的优化分配数学模型.它在数学建模中处于中心的地位.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁〞问题的第二问和第三问规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-08年全国大学生数模竞赛试题越多的人所重视.随着计算机的逐渐普及，它越的解题方法统计结果来看，规划模型共出现了16次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解.

二、线性规划模型线性规划模型是所有规划模型中最根本、最例1.〔食谱问题〕设有n种食物，各含m种营养素，第j种食物中第i种营养素的含量为aij,n种食物价格分别为c1,c2,…,cn，请确定食谱中n种食物的数量x1,x2,…,xn，要求在食谱中m种营养素简单的一种.

2.1线性规划模型的根本形式的含量分别不低于b1,b2,…,bm的情况下，使得总总的费用最低.首先根据食物数量及价格可写出食谱费用为其次食谱中第i种营养素的含量为因此上述问题可表述为：解上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大〔小〕值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，线性规划的数学模型maxz=线性规划、线性规划的可行解，最优解的概念线性规划一般可写作min(ormax)f=s.t.

线性规划问题还可以用矩阵表示minf=

s.tAx≥b,x≥0其中f被称作目标函数，目标函数下的等式或不等式被称作约束条件，

A=,b=一组满足约束条件的变量的值称为一组可行解。可行解的集合称为可行解域，或可行解空间。线性规划问题也就是在可行解域上寻找使目标函数取得极小〔或极大〕值的可行解，称之为最优解。

针对标准形式的线性规划问题，其解的理论分析已经很完备，在此根底上也提出了很好的算单纯形方法是线性规划问题的最为根底、也法——单纯形方法及其相应的变化形式〔两阶段2.2线性规划模型的求解

法，对偶单纯形法等〕.是最核心的算法。它是一个迭代算法，先从一个特殊的可行解〔极点〕出发，通过判别条件去判断该可行解是否为最优解〔或问题无界〕，假设不是最优解，那么根据相应规那么，迭代到下一个更好的可行解〔极点〕，直到最优解〔或问题无界〕.关于线性规划问题解的理论和单纯形法具体的求解过程可参见相关文献.然而在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有LINGO、LINDO和MATLAB。MATLAB中有关求解线性规划问题的指令X=linprog(f,A,b,Aeq,beq)X=linprog(f,A,b,Aeq,beq,lb,ub)X=linprog(f,A,b,Aeq,beq,lb,ub,x0)X=linprog(f,A,b,Aeq,beq,lb,ub,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=[].1/12/2023143、模型：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.1/12/202315解编写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)1/12/202316解:编写M文件如下：c=[-7-5];A=[32;46;07];b=[90;200;210];Aeq=[];beq=[];vlb=[0,0];vub=[inf,inf];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)问题2解答1/12/202317线性规划中的特殊形式----运输问题例2.

设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.每吨运费如表所示.同的调拨方案，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨方案？1572521甲15375151乙DCBA表1.1销地运费产地乙甲DCBA解一般的运输问题可以表述如下：数学模型：

假设其中各产地的总产量等于各销地的总销量，即类似与将一般的线性规划问题转化为其标准否那么，称为不平衡的运输问题，包括：，那么称该问题为平衡的运输问题.总产量>总销量和总产量<总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题.从而，我们的重点就是解决平衡运输问题的求解.显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解.但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解.关于运输问题及其解法的进一步介绍可参考相关文献.对于线性规划问题，如果要求其决策变量取整数值，那么称该问题为整数线性规划问题.平面法和分枝支定界法是两种常用的求解整数线性对于整数线性规划问题的求解，其难度和运算量远大于同规模的线性规划问题.Gomory割规划问题的方法(参见相关文献).此外，同线性规划模型一样，我们也可以运用LINGO和LINDO软件包来求解整数线性规划模型.三、整数线性规划模型以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包如何求解整数线性规划模型。例3.有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度〔t，以cm计〕及重量〔w，以kg计〕是不同的.表1给出了每种包装箱的厚度、重量以及数量。每节平板车有m长的地方可用来装包装箱〔像面包片那样〕，载重为40t.由于当地货运的限制，对于C5,C6,C7类包装箱的总数有一个特别的限制：这类箱子所占的空间〔厚度〕不能超过cm.试把包装箱装到平板车上，使得浪费的空间最小.种类C1C2C3C4C5C6C7t/cm48.753.061.372.048.752.064.0w/kg200030001000500400020001000n/件8796648为在第节车上装载第件包装箱的解令下面我们建立该问题的整数线性规划模型。1)约束条件两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：每节车可装的重量不超过车能够承受的重量：对于C5,C6,C7类包装箱的总数的特别限制：2)目标函数浪费的空间最小，即包装箱的总厚度最大：3)整数线性规划模型由上一步中的求解结果可以看出，4)模型求解运用LINGO软件求解得到：5)最优解的分析说明的装车方案，此时装箱的总长度为cm，两节车共装箱的总长度为cm.即为最优但是，上述求解结果只是其中一种最优的装车方案，即此答案并不唯一.0-1整数规划是整数规划的特殊情形，它要求线性规划模型中的决策变量xij只能取值为0或1.单隐枚举法，该方法是一种基于判断条件〔过滤0-1整数规划模型的求解目前并没有非常好的算法，对于变量比较少的情形，我们可以采取简条件〕的穷举法.我们也可以利用LINGO和LINDO软件包来求解0-1整数规划模型.四、0-1整数规划模型背包问题例4.有n个物品，编号为1,2,…,n，第i件物品重ai千克，价值为ci

元，现有一个载重量不超过大，应如何装载这些物品？a千克的背包，为了使装入背包的物品总价值最用变量xi

表示物品i是否装包，i=1,2,…,n，并令：解可得到背包问题的规划模型为：指派问题例5.有n项任务，由n个人来完成，每个人只能做一件，第i个人完成第j项任务要cij小时，如何合理安排时间才能使总用时最小？引入状态变量xij

，并令：解那么总用时表达式为：可得到指派问题的规划模型为：上面介绍的指派问题称为指派问题的标准形式，还有许多其它的诸如人数与任务数不等、及但一般可以通过一些转化，将其变为标准形式.某人可以完成多个任务，某人不可以完成任务，某任务必须由某人完成等特殊要求的指派问题.对于标准形式的指派问题，我们可以利用匈牙利算法实现求解.它将指派问题中的系数构成一个矩阵，利用矩阵上简单的行和列变换，结合解的判定条件，实现求解〔见相关文献〕.五、几种常用的线性规划模型问题1生产组织与方案问题工厂用种设备生产种产品在一个生产周期内,已知第台设备只能工作个机时.工厂必须完成产品至少件.设备生产所需要的机时和成本分别为试建立相应的数学模型,使设备能在计划周期内完成计划但又使成本达到最低.1/12/202340模型为1/12/202341问题2工厂选址问题设有个需求点（城市,仓库,商店等）,有个可供选择的建厂地址,每个地址最多可建一个工厂.在地址建立工厂的生产能力为在地址经营工厂,单位时间的固定成本为需求点的需求量为从厂址到需求点的单位运费为问应如何选择厂址和安排运输计划,使相应的成本为最小.1/12/202342模型为1/12/202343上式中的意义是:在地址建厂,不在地址建厂.这样的线性规划称为混合型的整数线性规划.1/12/202344问题3设备购置和安装问题工厂需要种设备设备的单价为工厂已有第种设备台,今有资金元,可用于购置这些设备.该厂有处可安装这些设备,处最多可安装台,将一台设备安装在处,经济效益为元,问应如何购置和安装这些设备,才能使总的经济效益最高.以表示设备在处安装的台数,表示购置1/12/202345的台数,那么模型为1/12/2023461/12/202347问题4货郎问题货郎要到个地方去卖货.已知两个地方和之间的距离为如何选择一条道路,使得货郎每个地方走一遍后回到起点,且所走的路径最短.定义货郎选择的路线包含从到的路径否则1/12/202348那么相应的模型为1/12/202349问题5系统可靠性问题选择个元件,组成一个并联系统.设第个位置所用的元件可从集合中挑选.对元件用表示元件在第个位置上的花费,表示其可靠性的概率,问应如何配置各位置上的元件,使得系统的可靠性不小于且使总费用最小.定义若元件且元件用在位置上若元件且元件不用在位置上1/12/202350总费用为其可靠性为若记则上式可写成相应的模型转化为规划.1/12/202351模型为1/12/202352DVD在线租赁第二个问题的求解问题二的分析经营本钱和会员的满意度是被考虑的两个相互制约的重要因素.在忽略邮寄本钱的前提下，经营本钱主要表达为DVD的数量.我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得DVD的数量尽量小，会员满意度最大.假设按照公历月份进行的租赁业务，即会员无论两次租赁还是一次租赁，必须在当月内完成DVD的租与还.同时假设网站对其会员进行一次租赁业务时，只能向其提供3张该会员已经预定的DVD，否那么不进行租赁.经观察，可以认为在线订单中每个会员的预定DVD的表示偏好程度的数字反映了会员对所预定不同DVD的满意程度，且当会员租到其预定排序为1，2，3的三张DVD时，满意度到达100%.会员没有预定的DVD对其满意度的奉献为0.利用层次分析法，对此满意指数的合理性进行简单分析.该问题要求根据现有的100种DVD的数量和当前需要处理的1000位会员的在线订单，制定分配策略，使得会员到达最大的满意度.因而我们认为只需对这些DVD进行一次性分配，使得会员的总体满意度到达最大.为此考虑建立优化模型，进行求解.问题二的模型及求解经营本钱和会员的满意度是被考虑的两个相互制约的重要因素.在忽略邮寄本钱的前提下，经营本钱主要表达为DVD的数量.我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得DVD的数量尽量小，会员满意度最大.由此，可得问题二的0-1整数线性规划模型如下：根据所得的0-1整数线性规划模型，利用LINGO软件进行求解，我们得到了一组最优分配方案.该组最优解其目标函数会员总体最大满意度为91.56%，只有6人未成功租赁〔如：前30名会员中C0008被分配到DVD〕，其余994个会员全都得到了3张预定的DVD.六.非线性规划模型

前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际问题建模过程中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划问题.非线性规划问题的标准形式为：非线性规划模型按约束条件可分为以下三类：⑴无约束非线性规划模型：⑵等式约束非线性规划模型：⑶不等式约束非线性规划模型：1)无约束的非线性规划问题.针对上述三类非线性规划模型，其常用求解的根本思路可归纳如下：

在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要因素.非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，一维搜索方法主要有进退法和黄金分割法.二维的非线性规划也可以像解线性规划那样用图形求解.对于二维非线性规划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法.2)只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为无约束问题求解.3)

具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，用线性逼近的方法将非线性规划问题化为线性规划问题.最速下降法是一种最根本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1．最速下降法〔共轭梯度法〕算法步骤：(一)无约束优化问题的根本算法1/12/2023702．牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，那么用牛顿法经过一次迭代就可到达最优点,如不是二次函数，那么牛顿法不能一步到达极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.1/12/2023713．拟牛顿法1/12/2023721/12/202373返回1/12/202374Matlab优化工具箱简介求解优化问题的主要函数1/12/2023752.优化函数的输入变量

使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:1/12/2023763.优化函数的输出变量下表:1/12/2023774．控制参数options的设置(3)MaxIter:允许进行迭代的最大次数,取值为正整数.Options中常用的几个参数的名称、含义、取值如下:(1) Display:显示水平.取值为’off’时,不显示输出;取值为’iter’时,显示每次迭代的信息;取值为’final’时,显示最终结果.默认值为’final’.(2) MaxFunEvals:允许进行函数评价的最大次数,取值为正整数.1/12/202378例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8)该语句创立一个称为opts的优化选项结构,其中显示参数设为’iter’,TolFun参数设为1e-8.控制参数options可以通过函数optimset创立或修改。命令的格式如下：(1)options=optimset(‘optimfun’)创立一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构options.〔2〕options=optimset(‘param1’,value1,’param2’,value2,...)创立一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.(3)options=optimset(oldops,‘param1’,value1,’param2’,value2,...)创立名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.返回1/12/202379用Matlab解无约束优化问题其中〔3〕、〔4〕、〔5〕的等式右边可选用〔1〕或〔2〕的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：〔1〕x=fminbnd(fun,x1,x2)〔2〕x=fminbnd(fun,x1,x2，options)〔3〕[x，fval]=fminbnd〔...〕〔4〕[x，fval，exitflag]=fminbnd〔...〕〔5〕[x，fval，exitflag，output]=fminbnd〔...〕1/12/202380

主程序为:f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作图语句

[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)1/12/202381例2对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解先编写M文件如下:functionf=myfun(x)f=-(3-2*x).^2*x;主程序调用fminbnd:[x,fval]=fminbnd('fminbndtest',0,1.5);xmax=xfmax=-fval运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为米时水槽的容积最大,最大容积为2立方米.1/12/202382命令格式为:〔1〕x=fminunc〔fun,X0〕；或x=fminsearch〔fun,X0〕〔2〕x=fminunc〔fun,X0，options〕；或x=fminsearch〔fun,X0，options〕〔3〕[x，fval]=fminunc〔...〕；或[x，fval]=fminsearch〔...〕〔4〕[x，fval，exitflag]=fminunc〔...〕；或[x，fval，exitflag]=fminsearch〔5〕[x，fval，exitflag，output]=fminunc〔...〕；或[x，fval，exitflag，output]=fminsearch〔...〕2、多元函数无约束优化问题标准型为：minF(X)1/12/202383[3]fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=’quadcubic’(缺省值)，混合的二次和三次多项式插值；LineSearchType=’cubicpoly’，三次多项式插使用fminunc和fminsearch可能会得到局部最优解.说明:fminsearch是用单纯形法寻优.fminunc的算法见以下几点说明：[1]fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=’on’(默认值),使用大型算法LargeScale=’off’(默认值),使用中型算法[2]fminunc为中型优化算法的搜索方向提供了4种算法，由options中的参数HessUpdate控制：HessUpdate=’bfgs’〔默认值〕，拟牛顿法的BFGS公式；HessUpdate=’dfp’，拟牛顿法的DFP公式；HessUpdate=’steepdesc’，最速下降法1/12/202384例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1、编写M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、输入M文件如下:x0=[-1,1];x=fminunc('fun1',x0);y=fun1(x)

3、运行结果:1/12/2023852.画出Rosenbrock函数的等高线图,输入命令：contour(x,y,z,20)holdonplot(-1.2,2,'o');text(-1.2,2,'startpoint')plot(1,1,'o')text(1,1,'solution')1/12/2023863.用fminsearch函数求解输入命令:f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])运行结果:fvalexitflag=1output=iterations:108funcCount:202algorithm:'Nelder-Meadsimplexdirectsearch'1/12/2023874.

用fminunc函数(1)建立M-文件fun1.m

functionf=fun1(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2(2)求解主程序oldoptions=optimset('fminunc')options=optimset(oldoptions,'LargeScale','off')

options11=optimset(options,'HessUpdate','dfp')[x11,fval11,exitflag11,output11]=fminunc('fun1',[-1.22],options11)1/12/202388(二)有约束优化问题的根本算法1/12/202389有约束非线性规划的根本解法SUTM外点法SUTM内点法〔障碍罚函数法〕1.罚函数法2.

近似规划法1/12/202390

罚函数法罚函数法根本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这类方法称为序列无约束最小化方法.简称为SUMT法．其一为SUMT外点法,其二为SUMT内点法．1/12/202391其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚:当时，满足各，故罚项=0，不受惩罚．当时，必有的约束条件，故罚项>0，要受惩罚．SUTM外点法1/12/202392罚函数法的缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误．1、任意给定初始点X0，取M1>1，给定允许误差，令k=1；2、求无约束极值问题的最优解，设为Xk=X(Mk)，即；3、假设存在，使，那么取Mk>M()令k=k+1返回〔2〕，否那么，停止迭代．得最优解.计算时也可将收敛性判别准那么改为.

SUTM外点法(罚函数法)的迭代步骤1/12/202393SUTM内点法〔障碍函数法〕1/12/202394

内点法的迭代步骤1/12/202395

近似规划法的根本思想：将问题中的目标函数和约束条件近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题,再用单纯形法求解之，把其符合原始条件的最优解作为原问题的解的近似．近似规划法每得到一个近似解后，都从这点出发，重复以上步骤．这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验说明，这样的序列往往收敛于非线性规划问题的解。1/12/202396

近似规划法的算法步骤如下1/12/2023971/12/202398用MATLAB软件求解,其输入格式如下:1. x=quadprog(H,C,A,b);2. x=quadprog(H,C,A,b,Aeq,beq);3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6. [x,fval]=quaprog(...);7. [x,fval,exitflag]=quaprog(...);8. [x,fval,exitflag,output]=quaprog(...);1.二次规划1/12/202399例1

minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2≤2-x1+2x2≤2x1≥0,x2≥01、写成标准形式：2、输入命令：

H=[1-1;-12];c=[-2;-6];A=[11;-12];b=[2;2];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、运算结果为：

s.t.1/12/20231001.首先建立M文件fun.m,定义目标函数F〔X〕:functionf=fun(X);f=F(X);其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，根本步骤分三步：2.一般有约束非线性规划1/12/20231013.建立主程序.非线性规划求解的函数是fmincon,命令的根本格式如下：(1)x=fmincon(‘fun’,X0,A,b)(2)x=fmincon(‘fun’,X0,A,b,Aeq,beq)(3)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)(4)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)(5)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)

(6)[x,fval]=fmincon(...)(7)[x,fval,exitflag]=fmincon(...)(8)[x,fval,exitflag,output]=fmincon(...)输出极值点M文件迭代的初值参数说明变量上下限1/12/2023102注意：[1]fmincon函数提供了大型优化算法和中型优化算法。默认时，假设在fun函数中提供了梯度〔options参数的GradObj设置为’on’〕，并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。[2]fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。[3]fmincon函数可能会给出局部最优解，这与初值X0的选取有关。1/12/20231031、写成标准形式：

s.t.

2x1+3x26s.tx1+4x25x1,x20例21/12/20231042、先建立M-文件fun3.m:

functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^23、再建立主程序youh2.m：x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)4、运算结果为：1/12/20231051．先建立M文件fun4.m,定义目标函数:

functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);x1+x2=0s.t.1.5+x1x2-x1-x20-x1x2–10

0例32．再建立M文件mycon.m定义非线性约束：function[g,ceq]=mycon(x)g=[x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];1/12/20231063．主程序youh3.m为:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')3.运算结果为：

1/12/2023107例4

1．先建立M-文件fun.m定义目标函数:functionf=fun(x);f=-2*x(1)-x(2);2．再建立M文件mycon2.m定义非线性约束：function[g,ceq]=mycon2(x)g=[x(1)^2+x(2)^2-25;x(1)^2-x(2)^2-7];1/12/2023108为:x0=[3;2.5];VLB=[00];VUB=[510];[x,fval,exitflag,output]=fmincon('fun',x0,[],[],[],[],VLB,VUB,'mycon2')1/12/20231094.运算结果为:x=exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:[1x44char]firstorderopt:[]cgiterations:[]1/12/2023110非线性规划建模实例(一)：供给与选址某公司有6个建筑工地要开工，每个工地的位置〔用平面坐标系a，b表示，距离单位：千米〕及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。〔1〕试制定每天的供给方案，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。〔2〕为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？1/12/2023111〔一〕、建立模型

记工地的位置为(ai，bi)，水泥日用量为di，i=1,…,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。1/12/2023112〔二〕使用临时料场的情形

使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：设X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

1/12/2023113计算结果为：x=[3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000]’1/12/2023114〔三〕改建两个新料场的情形

改建两个新料场,要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小.这是非线性规划问题。非线性规划模型为：1/12/2023115设X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

x1=X13,y1=X14,x2=X15,y2=X16

〔1〕先编写M文件liaoch.m定义目标函数。(2)取初值为线性规划的计算结果及临时料场的坐标:x0=[35070100406105127]';编写主程序gying2.m.1/12/2023116(3)计算结果为：10.07076.38754.39435.75117.1867]’exitflag=11/12/2023117(4)假设修改主程序gying2.m,取初值为上面的计算结果:x0=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’得结果为:x=[3.00005.00000.30947.00000.01080.6798003.690605.989210.32025.53694.91945.82917.2852]’exitflag=1总的吨千米数比上面结果略优.(5)假设再取刚得出的结果为初值,却计算不出最优解.1/12/2023118(6)假设取初值为:x0=[35471000005115.63484.86877.24797.7499]',那么计算结果为:x=[3.00005.00004.00007.00001.0000000005.000011.00005.69594.92857.25007.7500]’exitflag=1总的吨千米数89.8835比上面结果更好.通过此例可看出fmincon函数在选取初值上的重要性.1/12/2023119非线性规划建模实例(二)高速公路问题

1/12/2023120A城和B城之间准备建一条高速公路，B城位于A城正南20公里和正东30公里交汇处，它们之间有东西走向连绵起伏的山脉。公路造价与地形特点有关，以下图给出了整个地区的大致地貌情况，显示可分为三条沿东西方向的地形带。你的任务是建立一个数学模型，在给定三种地形上每公里的建造费用的情况下，确定最廉价的路线。图中直线AB显然是路径最短的，但不一定最廉价。而路径ARSB过山地的路段最短，但是否是最好的路径呢？你怎样使你的模型适合于下面两个限制条件的情况呢？1.当道路转弯是，角度至少为1400。2.道路必须通过一个地点〔如P〕。1/12/20231211/12/2023122问题分析

在建设高速公路时，总是希望建造费用最小。如果要建造的起点、终点在同一地貌中，那么最正确路线那么是两点间连接的线段，这样费用那么最省。因此本问题是一个典型的最优化问题，以建造费用最小为目标，需要做出的决策那么是确定在各个地貌交界处的集合点。1/12/2023123变量说明

xi：在第i个集合点上的横坐标〔以左下角为直角坐标原点〕，i＝1，2，…，4；x5＝30〔指目的地B点的横坐标〕

li：第i段南北方向的长度〔i＝1，…，5〕Si：在第i段上地所建公路的长度〔i＝1，2，…，5〕。由问题分析可知，1/12/2023124C1：平原每公里的造价〔单位：万元/公里〕C2：高地每公里的造价〔单位：万元/公里〕C3：高山每公里的造价〔单位：万元/公里〕1/12/2023125模型假设1、假设在相同地貌中修改高速公路，建造费用与公路长度成正比；2、假设在相同地貌中修改高速为直线。在理论上，可以使得建造费用最少，当然实际中一般达不到。1/12/2023126模型建立

在A城与B城之间建造一条高速公路的问题可以转化为下面的非线性规划模型。优化目标是在A城与B城之间建造高速公路的费用。1/12/2023127模型求解

这里采用Matlab编程求解。模型求解时，分别取Ci如下。平原每公里的造价C1＝400万元/公里；高地每公里的造价C2＝800万元/公里；高山每公里的造价C3＝1200万元/公里。

〔注意：实际建模时必须查找资料来确定参数或者题目给定有数据〕1/12/2023128模型结果及分析

通过求解可知，为了使得建造费用最小。建造地点的选择宜采取以下结果。建造总费用为亿元。总长度为公里。

1/12/2023129求解模型的主程序文件model_p97

functionx=model_p97clearallglobalCLC=[4008001200];L=[44444];x=fmincon('objfun_97',[1,1,1,1],[],[],[],[],zeros(1,4),ones(1,4)*30,'mycon_p97');optans=objfun_97(x)C=ones(3,1);len=objfun_97(x)

1/12/2023130模型中描述目标函数的Matlab程序

functionobj=objfun_97(x)globalCLobj=C(1)*sqrt(L(1)^2+x(1)^2)+C(2)*sqrt(L(2)^2+(x(2)-x(1))^2)+...C(3)*sqrt(L(3)^2+(x(3)-x(2))^2)+C(2)*sqrt(L(4)^2+(x(4)-x(3))^2)+...C(1)*sqrt(L(5)^2+(30-x(4))^2);

1/12/2023131描述约束条件的Matlab函数

function[c,ceq]=mycon_p97(x)c(1)=x(1)-x(2);c(2)=x(2)-x(3);c(3)=x(3)-x(4);c(4)=x(4)-30;ceq=[];1/12/2023132主程序运行结果model_p97optans

=2.2584e+004len

=

ans

=

1/12/2023133七、多目标规划模型

在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个生产方案的例子.我们希望购置DVD的总数量最小，即:由此，可以得到问题三的双目标整数线性规划模型如下：表6当时最小购置量的值DVD编号D01D02D03D04D05D06D07D08D09D10最少购买量14211724121719212214DVD编号D11D12D13D14D15D16D17D18D19D20最少购买量18181717172418161823DVD编号D21D22D23D24D25D26D27D28D29D30最少购买量20182214181715121624DVD编号D31D32D33D34D35D36D37D38D39D40最少购买量19222019222213171717DVD编号D41D42D43D44D45D46D47D48D49D50最少购买量32201621221620152020续上表DVD编号D51D52D53D54D55D56D57D58D59D60最少购买量24171917191819172021DVD编号D61D62D63D64D65D66D67D68D69D70最少购买量16191920171917212019DVD编号D71D72D73D74D75D76D77D78D79D80最少购买量21221520151412171917DVD编号D81D82D83D84D85D86D87D88D89D90最少购买量18101412211322151317DVD编号D91D92D93D94D95D96D97D98D99D100最少购买量24171514251522201122

我们利用规划模型求得每种DVD的购置量后，需要对其进行可行性校验，测试此结果是否可以满足一个月内比例为95%的会员得到他想看的DVD，且具有尽可能大的总体满意度.校验方法：〔一〕根据订单和求得的DVD购置数量，利用问题二的规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0，即不考虑对其进行第二次分配.〔二〕随机从第一次得到DVD的会员中抽取60%，将这局部人所还回的DVD与第一次分配余下的DVD合在一起，作为第二次分配时各种DVD的现有量.然后，利用问题二的0-1线性规划模型对第一次未分配到DVD的会员进行第二次分配；〔三〕统计出经过两次分配后，得到DVD的会员的比例，假设大于95%，那么此次分配成功.利用这种算法进行屡次随机模拟，假设大多数情况下可以使得到DVD的会员大于95%，那么认为模型三是合理的.校验结果：因为每次检验需时约1小时，我们只对问题三求得的结果进行了7次模拟，其中6次符合要求〔观看比例大于95%〕.下面给出7次模拟得到的观看比例〔表7〕：表77次模拟结果每次的观看比例列表验证次数1234567观看比例95.8％96.6％93.4％95.3％95.9％96.1％95.7％八、Lingo入门1/12/20231611在Lingo中使用Lindo模型Lindo与Lingo都是LINDO系统公司开发的专门用于求解最优化问题的软件包。与Lindo相比，Lingo软件主要具有两大优点：〔1〕除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题。〔2〕LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中。1/12/20231621在Lingo中使用Lindo模型完全支持Lindo模型程序的书写格式。在模型窗口中选择菜单命令“File|Open(F3)〞注意在以前的版本中〔如〕，“File|ImportLINDOFile(F12)〞命令可以将Lindo模型文件转化成Lingo模型。这个菜单命令的意思是“导入Lindo文件〞〔在中已无必要，所以该命令已经被取消了〕。1/12/2023163·后缀“ldt〞表示LINGO数据文件；·后缀“ltf〞表示LINGO命令脚本文件；·后缀“lgr〞表示LINGO报告文件；·后缀“mps〞表示MPS〔数学规划系统〕格式的模型文件；·“*.*〞表示所有文件。后缀“lg4〞表示LINGO格式的模型文件，是一种特殊的二进制格式文件，保存了我们在模型窗口中能够看到的所有文件和其他对象及其格式信息，只有LINGO能读出它，用其他系统翻开这种文件时会出现乱码；后缀“lng〞表示文本格式的模型文件，并且以这个格式保存模型时LINGO将给出警告，因为模型中的格式信息〔如字体、颜色、嵌入对象等〕将会丧失；LINDO格式的模型文件1/12/20231642用Lingo求解二次规划〔QP〕模型例2.1某厂生产的一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总的利润最大。所谓产销平衡指工厂的产量等于市场上的销量，没有卖不出去的产品的情况。显然，销售总利润既取决于两种牌号产品的销量和〔单件〕价格，也依赖于产量和〔单件〕本钱，按照市场经济规律，甲的价格p1固然会随其销量x1的增长而降低，同时乙的销量x2的增长也会使甲的价格有稍微的下降，可以简单地假设价格与销量成线性关系，即p1=b1－a11x1－a12x2，b1,a11,a12>0，a11>a12；类似地，乙的价格p2遵循同样的规律，即有p2=b2－a21x1－a22x2，b2,a21,a22>0，a22>a21.例如，假定实际中b1=100，a11=1，a12，b2=280；a21，a22=2。此外，假设工厂的生产能力有限，两种牌号产品的产量之和不可能超过100件，且甲的产量不可能超过乙的产量的两倍，甲乙的单件生产本钱分别是q1=2和q2=3(假定为常数)。求甲、乙两个牌号的产量x1，x2使总利润最大。1/12/2023165优化模型

决策变量：决策变量就是甲、乙两个牌号的产量〔也是销量〕x1，x2目标函数：显然，目标函数就是总利润z(x1，x2)，即 z(x1，x2)＝〔p1－q1〕x1＋〔p2－q2〕x2＝〔100－x1－2－２〕x1＋〔280－1－ 2x2－3〕x2＝98x1＋277x2－x12－0.3x1x2－2x22约束条件：题中假设工厂的生产能力有限，两种产品的产量之和不可能超过100件，且产品甲的产量不可能超过乙的产量的两倍。写成数学表达式，就是x1＋x2≤100,x1≤2x21/12/2023166综上所述maxｚ＝98x1＋277x2－x12－0.3 x1x2－2x22〔〕

s．t． x1＋x2≤100〔〕x1≤2x2〔〕x1，x2≥０〔〕1/12/2023167LINGO中的变量名由字母和数字组成，但必须以字母开头，长度不能超过32个字符〔只能是英文字符，不能含有中文字符〕行号、“TITLE〞语句和注释语句是LINGO中唯一可以使用汉字字符的地方行号必须以字母或下划线开头；LINGO中不区分大小写字母LINGO中已假定所有变量非负1/12/2023168通过“LINGO|Generate|DisplayModel(Ctrl+G)〞命令可以看到完整的模型以及每行语句对应的行号了。1/12/2023169可使用“LINGO|Picture〞命令检查模型中的简单错误，该命令将目标函数和约束表达式中的非零系数通过列表〔或图形〕显示出来。1/12/2023170用“LINGO|Solve〔Ctrl+S〕〞命令来运行这个程序。〔如果想要了解运行状态窗口中各项的含义，可先点击工具栏上的图标，再点击运行状态窗口，屏幕上自动弹出运行状态窗口的帮助信息。〕1/12/2023171求解结果报告窗口1/12/20231723敏感性分析敏感性分析的作用是给出“Rangesinwhichthebasisisunchanged〞，即研究当目标函数的系数和约束右端项在什么范围变化〔此时假定其他系数保持不变〕时，最优基〔矩阵〕保持不变。注意：这里LINGO不询问是否进行敏感性分析。如果需要进行敏感性分析，必须用“LINGO|Options〞命令翻开系统选项对话框，在“GeneralSolver〞标签下的“DualComputations〞下拉列表中选中“Prices&Range〞，再按下“OK〞按钮激活敏感性分析功能。修改了系统选项后，以后只需调用“LINGO|Range〞命令即可进行敏感性分析了。1/12/2023173修改运行时的内存限制激活敏感性分析1/12/2023174 例3.1一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在甲车间用12h加工成3kgA1，或者在乙车间用8h加工成4kgA2。根据市场需求，生产出的A1，A2全部能售出，且每千克A1获利24元，每千克A2获利16元。现在加工厂每天能得到50桶牛奶的供给，每天正式工人总的劳动时间为480h，并且甲车间的设备每天至多能加工100kgA1，乙车间的设备的加工能力可以认为没有上限限制〔即加工能力足够大〕。试为该厂制定一个生产方案，使每天获利最大，并进一步讨论以下3个附加问题： 〔1〕假设用35元可以买到1桶牛奶，是否作这项投资？假设投资，每天最多购置多少桶牛奶？ 〔2〕假设可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？ 〔3〕由于市场需求变化，每千克A1的获利增加到30元，是否应该改变生产方案？1/12/2023175优化模型 决策变量： 设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2 目标函数： 设每天获利为z〔元〕，x1桶牛奶生产3x1(kg)A1，获利24×3x1，x2桶牛奶生产4x2(kg)A2，获利16×4x1，故z=72x1+64x2. 约束条件： 原料供给：生产A1，A2的原料〔牛奶〕总量不得超过每 天的供给，即x1+x2≤50〔桶〕； 劳动时间：生产A1，A2的总加工时间不得超过每天正式 工人总的劳动时间，即12x1+8x2≤480〔h〕； 设备能力：A1的产量不得超过甲车间设备每天的加工 能力，即3x1≤100； 非负约束：x1，x2均不能为负值。1/12/2023176综上所述Maxz=72x1+64x2；s.t.x1+x2≤50，12x1+8x2≤480，3x1≤100， x1，x2≥0线性规划模型〔LP〕1/12/2023177模型分析与假设

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

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。1/12/2023179Lingo优化模型这是一个〔连续〕线性规划〔LP〕问题1/12/2023180“LINGO|Solve〞求解结果报告〔1〕假设用35元可以买到1桶牛奶，是否作这项投资？假设投资，每天最多购置多少桶牛奶？〔2〕假设可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？〔3〕由于市场需求变化，每千克A1的获利增加到30元，是否应该改变生产方案？“LINGO|Range〞敏感性分析1/12/2023181结论应该批准用35元买1桶牛奶的投资，但每天最多购置10桶牛奶。可以用低于2元/h的工资聘用临时工人以增加劳动时间，但最多增加。假设每千克A1的获利增加到30元，那么x1系数变为30×3=90，在允许的范围内，所以不应改变生产方案，但最优值变为90×20+64×30=3720。1/12/2023182 例SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元，假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？4在LINGO中使用集合1/12/2023183

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； 变量的非负约束1/12/2023184Lingo优化模型集合属性集合的属性相当于以集合的元素为下标的数组1/12/2023185Lingo模型的根本要素〔1〕集合段〔SETS〕〔2〕目标与约束段〔3〕数据段〔DATA〕：作用在于对集合的属性〔数 组〕输入必要的常数数据。格式为： attribute(属性)=value_list(常数列表); 常数列表〔value_list〕中数据之间可以用逗号“,〞分 开，也可以用空格分开〔回车的作用也等价于一个空 格〕 “变量名=?;〞——运行