最优化模型及其计算方法,

这里将简单介绍水资源系统分析中较常用的几种类型的最优化模型：线性规划模型、随机线性规划模型、灰色线性规划模型、动态规划模型、非线性规划模型。较详细的介绍和计算方法请查阅有关“运筹学”书籍。

1.确定性线性规划模型

在“运筹学”中，一般介绍的线性规划模型是确定性线性规划模型，亦即经典线性规划模型，常简称为线性规划模型。它具有如下三点共同特征：

（1）每一具体问题都用一组决策变量（x1，x2，…，xn）表示某一方案。这组决策变量的值就代表一个具体的方案。一般这些变量取值是非负的。

（2）存在一定的约束条件，这些约束条件都可以用一组线性等式或线性不等式表示。

（3）都有一个要求达到的目标，它可以用决策变量的线性函数来表示，即目标函数。根据问题的不同，要求目标函数达到最大或最小。

满足以上三个条件的数学模型称为线性规划模型。其一般形式为

目标函数：

max（min）z=c1x1+c2x2+…+cnxn

约束条件：

求解线性规划模型的常用方法是单纯形法，即根据问题的标准，在由约束条件切割成的凸多面体各极点中，从一个极点转移到相邻极点，使目标函数值逐步增加（或减小），直到目标函数值达到最大（或最小）时为止。此时，极点所对应的决策变量值就是最优解。

2.随机线性规划模型

在水资源系统分析中，常常要考虑某些变量、参数的随机性。运用线性规划模型研究水资源系统问题同样遇到这一现象。在线性规划模型中，如果含有带随机性的参数、变量或约束方程，就称为随机线性规划模型。这类模型要比确定性线性规划模型复杂，因此，在处理一个随机线性规划问题时，总是按照随机事件的规律，设法把它转化成一个确定性的线性规划问题来求解。这样，求解随机线性规划模型，实质上就变成如何把随机线性规划问题转化为确定性线性规划模型问题。

由于随机事件本身的复杂性和多样性，目前对各类随机线性规划问题还没有固定的、通用的数学模型形式和计算方法。本节仅介绍两种简单的随机线性规划模型及其转化方法。

（1）随机目标规划：

这类随机线性规划模型一般是指线性随机系统中，只有目标函数的系数ci是随机的，其他系数aij和bj都是确定的。

对这种随机线性规划模型的处理，可用ci的期望值E（ci）代替ci。即线性规划模型方程式为

目标函数：max（min）z=E（c1）x1+E（c2）x2+…+E（cn）xn

约束条件：

（2）随机约束规划：

这类规划模型的特点是：允许以小的概率违背约束。它是由Charnes和Cooper首先提出的，以下列假设条件为基础：

约束方程的系数aij是常数；

约束方程的限制系数bj为已知的多元正态分布；

目标函数的系数ci的分布为已知，且与bj统计独立；

在每一个随机参数取值之前，需先确定变量xi。

这类规划问题的目标函数和约束方程均为随机的。其线性规划模型可归结为如下形式：

目标函数：max（min）z=E（c1）x1+E（c2）x2+…+E（cn）xn

约束条件：

这里的约束方程P［aj1x1+aj2x2+…+ajnxn≤（=，≥）bj］≥αj（j=1，2，…，m）的含义是指：约束方程aj1x1+aj2x2+…+ajnxn≤（=，≥）bj成立的概率要大于或等于αj。

求解此类模型的方法，就是要把概率约束转化为确定性的线性约束。转化的基本思路就是利用前面给定的假设条件，使bj变为标准的正态分布，再利用标准正态分布表来确定随机变量的值。从而把随机约束规划模型转化为确定性线性规划模型，接着就可以采用确定性线性规划模型求解方法进行求解。

3.灰色线性规划模型

这类规划模型是指含有灰元的线性规划模型。下面仅介绍王清印和左其亭最先提出的模型系数含区间型灰数的线性规划模型，即区间灰线性规划模型。

一般性区间灰线性规划模型表达式为

其求解的基本思路也是通过转化要把原规划模型变成确定性线性规划模型，再求解。其求解过程简单介绍如下（详细过程请查阅参考文献）：

第一步：模型标准化。把原模型化成如下标准型：

第二步：确定约束条件下的最大取值范围和狭义最小取值范围。

最大取值范围：

狭义最小取值范围：

第三步：把模型转化为两个一般确定性线性规划模型。目标函数记为

求minZ下限z1的线性规划模型为

求minZ上限z2的线性规划模型为(www.zuozong.com)

第四步：利用确定性线性规划模型，得出结果。

设上述的两个线性规划模型求解得到的目标值分别为z1和z2（有可能无解），对应的规划值分别为x'1，x'2，…，x'n和x"1，x"2，…，x"n。于是，得到目标值：

minZ=［z1，z2］

规划值可记成：

4.动态规划模型

动态规划模型的基本思路是把一个复杂的系统分析问题分解，形成一个多阶段的决策过程，并按一定顺序或时序，从第一阶段开始，逐次求出每段的最优决策，最终求得整个系统（全阶段）的最优决策。动态规划模型在水资源系统中的应用比较广泛，如水库优化调度的多阶段决策过程、水资源工程最优投入次序、施工组织安排、最佳输水线路选择等。

动态规划没有标准的数学形式，也没有通用的计算机程序，只能是针对具体的问题写出相应的数学模型，编制相应的计算机程序。

为了便于介绍，先对动态规划中常采用的一些术语进行定义：

（1）阶段及阶段变量：把所给问题的过程，恰当地分成若干相互联系的序列单元，称为阶段。这样，便于按一定的次序去求解。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程。描述阶段的变量称为阶段变量，常用k表示。

（2）多阶段决策过程：由若干阶段组成的整个过程中，如果每一阶段都有相应的决策，该过程称为多阶段决策过程。

（3）状态：表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。

（4）无后效性：当给定某一阶段状态后，过程的未来演变不再受此阶段以前各阶段状态的影响，这种性质就称为无后效性。

（5）状态变量：是指描述过程状态的变量，常用sk表示。

（6）决策、决策变量及允许决策集合：当过程处于某一阶段的某一状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量。它可用一个数、一组数或一向量来描述。常用uk（sk）表示第k阶段当状态处于sk时的决策变量，它是状态变量的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用Dk（sk）表示第k阶段从状态sk出发的允许决策集合，显然有uk（sk）∈Dk（sk）。

（7）策略与最优策略：是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或k子过程）。由每段的决策按顺序排列组成的决策函数序列｛uk（sk），…，un（sn）｝称为k子过程策略，简称子策略，记为ps，n（sk）。即

pk，n（sk）=｛uk（sk），uk+1（sk+1），…，un（sn）｝

当k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为p1，n（s1）。

即

p1，n（s1）=｛u1（s1），u2（s2），…，un（sn）｝

把可供选择的策略的范围称为允许策略集合，用P表示。从允许策略集合中找出达到最优效果的策略称为最优策略。

（8）状态转移方程：是描述过程从一个状态到另一个状态的演变过程。若给定第k阶段状态变量sk的值，如果该阶段的决策变量uk一经确定，第k+1阶段的状态变量sk+1的值就完全确定。即sk+1的值随sk和uk的值变化而变化，这种对应关系记为sk+1=Tk（sk，uk）。它描述了由k阶段到k+1阶段的状态转移规律，称为状态转移方程。

（9）指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数，常用Vk，n表示。即

Vk，n=Vk，n（sk，uk，sk+1，…，sn+1）（k=1，2，…，n）

指标函数的最优值，称为最优值函数，记为fk（sk）。它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采用最优决策所得到的指标函数值。即

动态规划模型基本方程，可写成第k阶段与k+1阶段的递推关系式形式：

边界条件为

fn+1（sn+1）=0

式中：vk为第k阶段的阶段指标。

在求整个动态规划问题的最优解时，由于初始状态是已知的，且每段的决策都是该段的状态函数，故最优策略所经过的各段状态便可通过逐次变换得到，从而确定了最优路线。关于动态规划模型的求解方法，可以采用逆向的和顺向的递推方法。上面给出的动态规划模型基本方程式是逆向递推方法的基本形式，其求解过程，是根据边界条件，从k=n开始，由后向前逆推，从而逐步可求得各段的最优决策和相应的最优值，最后求出f1（s1）时，就得到整个问题的最优解。

顺向递推方法求解动态规划模型的基本方程式如下：

边界条件为

f0（s1）=0

其求解过程，是根据边界条件，从k=1开始，由前向后顺推，从而逐步可求得各段的最优决策和相应的最优值，最后求出fn（sn+1）时，就得到整个问题的最优解。

5.非线性规划模型

当目标函数或约束方程中有一个或多个非线性函数时，就称为非线性规划模型。这类模型在水资源系统分析中常常被应用。

当非线性规划模型比较简单时，实际中常采用线性化技术，把非线性方程近似地用一系列线性函数表示，再用线性规划方法求解。常用的线性化技术有变量分割法、可分规划法等。

如果非线性规划模型比较复杂，不能采用线性化技术进行处理，就只能用非线性规划方法求解。求解的方法不外乎两类，一类是解析解；一类是数值解。

解析法的使用条件是：目标函数可用解析式表达。当无约束条件时，可简单对目标函数求导数，使导数等于零，就可得到极值（极大值或极小值）；当目标函数受等式条件约束时，可采用拉格朗日乘子法求极值，即引入拉格朗日乘子λ，将目标函数与等式约束联系起来，把约束问题转变为等价的无约束极值问题求解；当目标函数受不等式条件约束时，可采用H.W.Kuhn和A.W.Tucker提出的不等式约束条件下的非线性优化问题理论。

采用数值法，求解非线性规划模型，根据计算方法的不同，有多种类型。对于单变量函数，常采用黄金分割法，逐渐逼近最优解；对于多变量函数，则可用爬山法和以梯度法为基础的数值法（如最速下降法、牛顿法、共轭梯度法等）。当有约束条件时，常采用罚函数法，把有约束问题转化为无约束问题，再求解。