⒈ 优化问题及其数学模型

假设有一个问题，它有几个因素来决定，当这些因素处于某个状态时，可以使问题得到我们最想要的结果。优化问题就是寻求这个状态的过程。例如：

某工厂生产A，B两种产品，所用原料均为甲、乙、丙三种；生产一件产品所需原料和所获利润以及库存原料情况如下所示： 产品A 产品B 库存原料 原料甲 8 6 380 原料乙 4 8 300 原料丙 4 6 220 利润(元) 7000 10000 问题：在该厂只有库存原料甲380单位，原料乙300单位，原料丙220单位的情况下如何安排A，B两种产品的生产数量可以获得最大的利润？

设生产A中产品x1件，生产B中产品x2件，z为所获得的利润，于是有关系式： z?7000x1?10000x2 我们称它为目标函数。生产的条件我们可以表示为：

8x1?6x2?380 4x?8x?300

124x1?6x2?220我们把上面的不等式称为约束条件。

产品A的产量x1和B的产量x2是优化问题的变量。在满足约束条件的前提下使目标函数得到最优的值成为最优解。根据以上定义，也可以说优化运算是通过某种计算寻求最优解的过程。

以上这个用等式或不等式来表达我们要解决的问题的过程就是优化问题的建模过程。我们平时遇到的问题常常不是上面的这几个数学表达式就能表达得清清楚楚的，但是建立像上面类似的数学模型却是优化求解的第一步。优化问题常常表现为在多约束条件下求某一函数的极值问题，例如上面的这个例子。

Matlab有一个优化工具箱，可以帮助我们方便的解决好这类问题。 ⒉ 优化工具箱

Matlab的优化工具箱有一些对普通非线性函数求解最小化或最大化（求极值）的函数组成，另外还包括一些解决诸如线性规划等标准矩阵问题的函数。所有的优化函数都是用Matlab语言编写的m文件，我们可以通过在命令窗口里输入type function_name来查看这些函数。

优化工具箱的优化功能包括： ⑴ 求无约束非线性最小化； ⑵ 求有约束非线性最小化； ⑶ 二次和线性规划问题；

⑷ 非线性最小二乘法和曲线拟合问题； ⑸ 非线性等式的求解； ⑹ 约束线性最小二乘法； ⑺ 稀疏和结构化大尺度问题。

工具箱中求非线性函数极小值的命令函数如下表所示： 问题类型 线性规划问题 函数用法 x=linprog(f,A,b) 含义 在条件Ax?b下求minf(xi) xi无限定标量问题 无限定条件矩阵问题 有限定条件 目标条件 最小最大极值 非线性二次平方极值 非线性方程 半无穷条件 x=fminunc(‘f’,x) x=fminunc(‘f’,x) x=fmincon(‘fg’,x) minf(x)，x为标量 xminf(X)，X为矩阵 Xminf(X)，条件为 G(X)?0 X?min?，条件为F(x)?W?goal x=fgoalattain(‘f’,x,goal,w) Xx=fminmax(‘fg’,x) x=lsqnonneg(‘f’,x) x=fsolve(‘f’,x) x=fsemimf(‘ft’,n,x) min{maxf(X)}，条件为 G(X)?0 Xmin?(F(X)*F(X)) F(X)?0 minf(X)，条件为任意给定w值?(X,w)?0 上面表中函数可以对标量、向量和矩阵进行运算；我们一般用大写字母表示矩阵，用小写字母表示向量和标量。在Matlab中用符号“*”表示矩阵的元素乘。当然，上述运算是在定义好了一个最小化函数的前提下进行的，也就是说要先建立数学模型。

注：Matlab自身提供了一个优化演示示例，其命令为optdemo。 ⒊ 线性规划问题

前面6-1中所举的例子就是一个典型的线性规划问题。线性规划数学模型的特点是：在线性不等式或线性等式的约束条件下，求能满足目标函数取得最大值或最小值的一组变量的值，目标函数也要求是线性函数。

命令：linprog

格式：X= linprog(f,A,b)

[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options) 功能：计算使目标函数f(x)取得最小值的一组变量的值。

说明：这里f为由目标函数的系数组成的向量。A是一个矩阵，b是一个向量，A和b构成了线性规划的不等式约束条件A?xi?b。X是一个向量，为返回的满足目标函数取得极小值的一组变量的值。Aeq是一个矩阵，Beq是一个向量，Aeq和Beq构成了线性规划的等式约束条件Aeq?xi?Beq。LB和UB分别是变量的下界和上界约束。X0是给出的变量的初始值。Exitflag、output、lambda的意义我们放在后面的示例中给出解释。

注：如果要计算的是使目标函数f(x)取得最大值的情况，则通过转化为计算?f(x)的最小值的办法来实现。

例6-1 对前面6-1中所举的例子进行线性规划问题的计算。 分析：① 优化的目标为使函数f(x)?7000x1?10000x2取得最大值，也就是使函数?f(x)??7000x1?10000x2取得最小值，故线性规划目标函数的系数组成的向量为

f??[7000,10000]；

② 约束条件为三个不等式：8x1?6x2?380,4x1?8x2?300,4x1?6x2?220，所以由不等式约束条件的系数构成的矩阵为：A=[8,6;4,8;4,6]，而b=[380,300,220]。

程序：

clear

f=-[7000,10000]; A=[8,6;4,8;4,6]; b=[380,300,220]; [X,fval]=linprog(f,A,b)

运行结果：

Optimization terminated. X =

40.0000 10.0000 fval =

-3.8000e+005

注：① 优化的结果，目标函数值fval = -3.8000e+005，由于我们的目标函数是-f(x)，所以最后应该是maxf(x)=3.8000e+005。

② 在优化问题中，涉及到优化结果只能取整数值的情况时，如果我们对优化结果随意的进行取整，可能导致最后结果不是最优，这一点需要注意。

例2 中国石油天然气集团公司天然气的运送案例分析

中国石油天然气集团公司在东海有一个油气田（节点vs），该公司要将开采的天然气通过管道运送到上海的一个配送中心（节点vt），天然气在运送途中要经过两次管道换接点（节点B和C），换接前后管道长短不一，而且不同的管道对应不同的单位流量运费。如图，天然气运送的管道网络图，弧线表示管道，弧旁的数字为（bij,cij）,其中bij表示管道上的单位流量费用，cij表示管道上的容量。公司希望选择一个经济实惠的管道路线运送天然气，既运送最多的天然气又使总的运输费用最少。

B1 (1,4) （3,3） C1 (2,5） (2,1) vs (3,5) (1,1) (1,3) vt (4,2) B2 (4,2) C2

这是一个最小费用最大流问题。为了建立该问题的数学模型，首先设每段管道上的流量作为问题的决策变量，分别记为x1,x2,x3,x4,x5,x6,x7,x8,x9，称分段流量。

从始点vs处，可得流量函数f?x1?x2, 且有约束条件：（1）xi?0,1?1,2,?9；

（2）x1?4,x2?5,x3?1,x4?3,x5?1,x6?2,x7?3,x8?5,x9?2；

x1?x3?x4?x5?0（3）

x2?x3?x6?0x4?x7?x8?0x6?x5?x7?x9?0；

一方面要使流量最大，另一方面要是费用最小。

所以分两部分计算，先求出最大流，再求最小费用最大流。