水害控制管理模型的求解方法———线性规划

Question

如题所述

Answer 1

线性规划是运筹学中研究较早、应用较广、比较成熟的一个重要分支，它研究具有线性关系的多变量函数，在变量满足一定线性约束条件下，如何求函数的极值问题。

4.4.1.1线性规划问题及其数学模型

地下水资源管理的线性规划问题，通常可分为两大类:一类是从社会效益或环境效益出发，即在一定水文地质条件下，寻找供水或排水工程的最佳方案;另一类是从经济效益出发，在满足供、排水工程规划的情况下，寻求完成此工程经济效益最高或成本最低的方案。

线性规划问题包括3个要素:

1)决策变量。根据已知条件及所要求的问题，用一组变量x₁，x₂，…，x_n来表示，这些变量称为决策变量，取值要求为非负。

2)目标函数。一个问题都有一个明确的目标，以决策变量的线性函数表示，称为目标函数，它是衡量决策方案优劣的准则。这种准则可用物理量(如水位、水量、水温、水质等)或经济指标(如利润、成本等)来衡量。

3)约束条件。每一个问题都有一定的限制条件，这些条件称为约束条件。它是用一组线性等式或不等式来表示的，其变量与目标函数变量必须是有机联系或者一致的。

因为目标函数和约束方程都是决策变量的线性表达式，所以这类模型称为线性规划模型。线性规划的数学模型可表示为:

目标函数:

煤矿水害防治与管理

约束条件:

煤矿水害防治与管理

式中:Z—目标函数值;n—决策变量数;m—约束方程数;a_i，j—结构系数;c_j—价格系数;b_i—常数项。

4.4.1.2线性规划问题的范式及标准式

线性规划问题有不同的数学表达式。为了便于讨论和求解，可归纳为两种统一的形式，即线性规划问题的范式及标准式。

如果线性规划问题的目标函数取极大值形式，即

煤矿水害防治与管理

且约束条件取“≤”形式，即:

煤矿水害防治与管理

此式为线性规划问题的范式。范式有利于对线性规划对偶问题的讨论。

如果线性规划问题的约束条件均取“=”形式，目标函数取极大或极小值，变量为非负。即:

煤矿水害防治与管理

此式为线性规划问题的标准式。式中新变量x_n+i称为松弛变量(slackvariables)。这样，标准式使线性规划问题化为一组具有n+m个未知量的m个线性代数方程式，它有利于直接用标准模型求解。

任何形式的线性规划问题，通过简单的变换，均可转化为标准式。然后用单纯形法求解线性规划问题。

4.4.1.3具有人工变量的单纯形法计算

用单纯形法求解线性规划问题时，需要有一个单位矩阵作为初始基，当约束条件都是“≤”时，约束条件标准化后，其松弛变量均为正数，在约束方程组的系数矩阵中，就形成了一个初始基。但是，实际问题中常常出现“≥”或“=”的约束条件，经标准化后，约束方程组系数不存在单位矩阵，因而没有一个现成的初始基本可行解。为了解决此问题，采用人造基的办法，在约束方程中引入非负的人工变量。这种人工变量与前述松弛变量不同，它没有物理意义，仅是为了求解方程方便而引入，所以解的结果必须使这些变量为零，才能保持改变后的问题与原题等价，否则，说明原题无解。

处理人工变量的方法有-M法和两阶段法。

(1)-M法

当线性规划数学模型中含有“≥”或“=”的约束方程时，需在其左端加一非负的人工变量y_i，构成单位矩阵。但加入y_i后的方程，就与原约束方程不等价，所以必须保证在最后的解中，y_i=0才能与原约束方程等价。为此，在目标函数式中，给加入的人工变量y_i一个很大的系数，对极大问题，系数用-M表示;对极小问题，系数用M表示(M本身为正值)。只有当y_i=0时，才能使-My_i=0，目标函数才达到最优化。y_i由于具有很大的系数而得到严格的控制，故这个-M称为“惩罚因子”。

当具有“≥”或“=”的约束方程加入人工变量y_i后，即可以y_i作为初始基本解，按上述单纯形法计算。

(2)两阶段法

两阶段单纯形法就是将线性规划问题分两个阶段求解。

第一阶段是判断原线性规划问题是否有解，并寻求一个初始基本可行解。为此，用人工变量的和代替原来的目标函数，以构造一个辅助规划，这个辅助规划具有一个单位矩阵，应用单纯形法，使辅助规划的目标函数最小化。若此辅助规划的最优解使其目标函数等于零，则说明没有一个人工变量在基本变量内取值，从而可得到原问题的一个基本可行解，转向第二阶段。否则，如果最小值为正，那么问题就以不存在可行解而结束。

第二阶段是求原问题的最优解。在第一阶段最后单纯形表的基础上，去掉人工变量，然后以第一阶段求得的最优解作为第一个基本可行解，以原问题的目标函数，继续用单纯形法进行迭代，直到求得最优解为止。

4.4.1.4线性规划的对偶问题和灵敏度分析

对偶理论是线性规划理论的发展和深化，也是线性规划的一个特性。它使线性规划理论更加丰富，应用领域更加广泛。对于任何求极大值的线性规划问题，都有一个与之对应的求极小值问题，其有关约束条件的系数矩阵具有相同的数据，但形式上互为转置，且目标函数与约束方程右端常数项互换，目标函数值相等。这就是线性规划的对偶问题。

可用一个简单例子来说明，例如，四边形的周长L一定，什么样形状的四边形面积最大?答案是正方形面积最大。其对偶问题为，四边形面积一定，什么样的四边形周长最短?答案仍然是四边形。可见前一问题的约束条件，即为后一问题的目标函数，反之亦然。

线性规划问题中，均假定各系数a_i，j，b_i，c_j是确定的常数，实际上这些系数往往不可能很精确，而且随着客观条件变化而改变。例如地下水资源管理中，当水位、水量或水质等约束条件改变时，b_i也随之改变;当市场情况或供求关系发生变化时，c_j也会改变;而开采工艺或水文地质条件的改变，同样也可引起a_i，j的改变。因此，规划者需要知道，某些系数改变后，现行的最优解是否改变?或者说，这些系数在多大范围内变化，其规划问题的最优解不变?以及当最优解发生变化时，如何用最简便的方法找出新的最优解?这些就是灵敏度分析所要研究和回答的问题。

对偶原理是进行灵敏度分析的理论依据。灵敏度分析的内容，应包括系数c_j、b_i、a_i，j变化及新增加变量和新增加约束条件对最优解的影响。但对地下水资源管理而言，主要分析c_j和b_i变化。

由于线性规划原问题与对偶问题之间互为对偶，所以，求极大值原问题的最优状况，等价于对偶问题的可行状况;而原问题的可行状况，就是对偶问题最优状况的负值。

从对偶特性可知，对c_j和b_i进行灵敏度分析的两条重要依据:①只要满足原问题的最优状况或对偶问题的可行状况，其最优解不变。以此可分析c_j变化对最优解的影响。②只要原问题保持可行状况或对偶问题最优状况，其最优解不变，以此可分析b_i变化对最优解的影响。