字典序目标规划法在大型供水管网改、扩建工程优化决策中的应用

杨晓安 邱文心 王萍
（武汉市自来水公司 430034）

　　摘　要：本文将字典序线性目标规划基本模型应用于大型供水管网改、扩建优化决策，建立了大型供水管网改、扩建工程优化决策字典序线性目标规划模型，并用字典序线性目标规划多阶段算法进行计算，编制了相应的计算程序，且根据其计算特点，编制了字典序线性目标规划灵敏度分析程序，对所建立的模型进行灵敏度分析。计算实例表明：字典序线性目标规划法的理论和方法非常适合大型供水管网改、扩建工程优化决策计算，结果令人满意。所编制程序具有准确性和通用性，对生产具有科学和实际的指导意义。
　　关键字：字典序 目标规划 供水管网 灵敏度

The Lexicographic Linear Goal programming is applied to the
Optimal Decision-making of the large Water Networks
Rebuliding & Enlarging project

　　Abstract：The basic model of the lexicographic linear Goal programming is applied to calculating the optinal decision-making of the large water networks rebuliding & enlarging project.A model used for calculating the optimal decision-making of the large water networks rebuliding & enlarging project is constructed.The lexicographic linear Goal programming mutiplestage algorithm is used to calculate. A
correlative calculating program is programmed.According to its calculating characteristics, the procedure
of the lexicographic linear Goal programming sensitivity analysis is made to analyse the constructed
model.The calculating example indicates that，the theory and the method of the lexicographic linear Goal
programming is very suitable for the calculation of the optimal decision—making of the large water networks rebuliding & enlarging project.The result proves satisfactory.The programs are precise and stable.They have scientific and practical guiding value to production.
　　key words：LexiGographic Goal progrmming water networks sensitivity

1 字典序线性目标规划基本模型[1][2]

1.1字典序线性目标规划方法的概念
　　字典序线性目标规划(Lexicopraphic Linear Goal programming)简称LLGP是美国阿波罗计划工程师J.P伊格尼齐奥于1976年在研究目标规划法的基础上提出的一种用目标偏差量有序向量衡量多目标模型目标达成度的字典序最小方法。
1.2数学模型
　　LLGP方法的数学模型为：
　　求x（x₁,x₂,…,x_n）
　　使 Lexmin α={g₁(η,δ),g₂(η,δ),…,g_k(η,δ)}　（1-1-1）
　　　s.t ∑ⁿ_j=1=c_I,jx_j+η_i-δ_i=b_i ，i=1,2,…,m　　　　（1-1-2）
　　　x,η,δ≧0　　　　　　　　　　　　　　　　 　　　　（1-1-3）
　　其中：x—n维决策变量；η—负偏差变量；δ—正偏差变量； g_k(η,δ)—为第K个优先级别中目标偏差变量的线性系数：α—寻求字典序极小化达成系数；c_I,j—是对应于第i个目标或约束中第j个变量的系数；b_i—为目标或约束分端常数：（1-1-1）为LLGP问题的目标；（1-1-2）为目标的约束条件，可以有硬约束和软约束；（1-1-3）为非负约束，即x、η与δ均为非负变量；k—为优先次序数。m—为全部目标和约束数。
1.3字典序线性目标规划模型的求解方法：
　　字典序线性目标规划模型最常用的求解方法是多阶段单纯形算法，它的目标行里有多个目标存在，进行单纯形迭代时，按确定的优先次序分层次的解决问题，它得到多个目标满足约束条件下的满意解。

2 字典序线性目标规划模型灵敏度分析方法[3]

2.1灵敏度分析
　　灵敏度分析是考查模型结构中，某元素变化对问题解的影响。
2.2字典序线性目标规划灵敏度分析的三种方法：
　　(1) 结构性离散变化：①重捧优先级②增加新变量⑧增加变目标；
　　(2) 非结构性离散变化：有vh+毗k，yl+及h的离散变化：
　　(3) 在一个区域连续取值的参数分析：即参数线性目标规划。

3 大型供水管网改、扩建工程优化决策字典序线性目标规划计算模型

　　大型供水管网改、扩建工程优化决策问题的目标是多个的，既有总水量目标，又有各输送管道及转压站输送水量目标，还有控制费用目标，而且这些目标的重要程度是不同的：首先，须满足总水量目标，其次是控制费用及各输送输送管道及转压站输送水量目标，除满足上述目标外，还须满足在每种输送方式下各种输送管道及增压站的输送水量小于或等于该种输送方式下的输送水量。 下述表明：大型供水管网改、扩建工程优化决策问题，实际上是个多目标规划问题，其约束和目标方程都是线性的，因而完全适合字典序线性目标规划法求解条件。
3.1已知条件：
　　(1) 所考察的各类水量；S₁，S₂，……，S_p；
　　(2) 每种输送方式费用单价：C₁₁，C₁₂，…，C_1q1；…，…，…，…；
　　　　　　　　　　　　　　　　C_p1，C_p2，…，C_pqp；
　　(3) 各条输送管道及各转压站的输送水量；A₁，A₂，……，A_r
　　(4) 所有改.扩建管道及转压站项目的控制费用：W
3.2待求变量：
　　(1) 每类水量适宜的输送方式输送该类水量的量：
　　　　X₁₁，X₁₂，…，X_1q1；…，…，…，…；x_p1，x_p2，…，x_pqp；
　　(2) 每种输送方式下换输管道和转压站所输送水量：
　　　　x₁₁₁，x₁₁₂，…，x_11r11；…，…，…，…；x_pqp1，x_pqp2，…，x_pqprpqp；
　　(3) 各种输送方式下各种输送管道和转压站的输送水量：；
　　　　x₁₁A₁，x₁₁A₂，…，x₁₁A_r；…，…，…，…；x_pqpA₁，x_pqpA₂，…，x_pqpA_r；
3.3计算模型：
　　3.3.1目标：
　　(1)每类水量各输送方式所输送水量之和与该类水量相等，即：
　　　∑^q1_j1=1x_1j1=S₁；∑^q2_j2=1x_2j2=S₂；…；∑^qp_jp=1xp_jp=Sp；　　　　（3-1-1）
　　(2)输送各类水量各输送方式管道及转压站改、扩建费用之和等于总控制费用：
　　　∑^q1_j1=1C_1j1x_1j1+∑^q2_j2=1C_2j2x_2j2+…∑^qp_jp=1Cp_jpxp_jp=w；　　　（3-1-2）
　　(3)输送各类水量同一种管道求转压站所输送水量应该等于该管道求转压站所输送的水量：
　　　∑^q1_j1=1x_1j1A₁+∑^q2_j2=1x_2j2A₁+…∑^qp_jp=1x_pjpA₁；…；∑^q1_j1=1x_1j1A_r+∑^q2_j2=1x_2j2A_r+…∑^qp_jp=1x_pjpA_r=A_r
　　3.3.2约束条件：
　　(1) 水量约束：
　　每种输送方式下换输管道和转压站所送水量小于等于该输送方式所输送的水量：
　　(2) 非负约束：X≧0；
　　3.3.3优先级：一级为各类水量目标；二级为控制费用目标；三级为各管道和转压站输送水量日标；

4 大型供水管网改、扩建工程优化决策字典序线性目标规划模型灵敏度分析

4.1某些问题的处理：
　　(1)考虑到四舍五入带来的影响，为方便编程计算，特作如下规定：凡本模型灵敏度分析中间值的绝对值小于或等于0.00001的元素值均设为0.0。
　　(2)为方便编程计算：在本模型灵敏度分析中，用1.0e+35代替+∞，-(1.0e+35)代替-∞。
4.2单元素变化及多元素参数分析：
　　均针对第t个方案，在保持目前最优基的条件下，求满足下列不等式：B^-1(b+ub_t*)≧0的u的　　取值范围(因篇幅所限，公式推导及结果省略).
4.3离散变化的灵敏度分析：
　　从单元素变化及多元素参数分析所确定的各取一u值，计算X_Tb*B^-1(b+ub_t*)及a_tk*=∑^m+n_s=1W_k,s*X_Tb,s*+∑^m_I=1u_I,k*X_Tb,I*
　　其中：t—单元素变化或多元素参数分析的第t个方案；X_Tb,s*—问题变量中的负偏差变量值；X_Tb,I*—问题变量中的正偏差变量值。

5 大型供水管网改扩建工程优化决策字典序线性目标规划模型多阶段单纯形算法程序框图及灵敏度分析程序框图[4]

5.1多阶段单纯形算法程序框图

5.2灵敏度分析程序框图

6 例计算和分析

6.1实例
　　1.武汉武昌地区“湖改江”工程，含东湖水厂“湖改江”和团山水厂“湖改江”，根据武昌地区供水规划，实现东湖水厂“湖改江”须补充水量12万吨／日，实现团山水厂“湖改江”须增加水量18万吨／日。
　　2.实现东湖水厂"湖改江"有以下六种可能输送方式：

序号 前输 转输 改、扩建单位费用
(元／m3) 1 南湖北路转压站 南湖北路DN1200管 600 2 关山路转压站 南湖北路DN1200管 450 3 关山路转压站 南湖南路DN800管 300 4 关山路转压站 关山一路延长线DNl000管 300 5 南湖北路DNl200管 关山一路延长线DN1000管 450 6 湖边泵站 南湖北路DN1200 600

　　(B)实现团山水厂“湖改江”有以下十种可能输送方式：

序号 前输 转输 改、扩建单位费用
(元／m3) 1 三环路DN400管 三环路转压站 600 2 三环路DN400管 天京路DN300管 600 3 三环路DN400管 三环路DN100管 900 4 南湖北路转压站 鲁巷广场 600 5 关山路转压站 南湖南路 300 6 关山路转压站 关山路延长线DN1000管 300 7 关山路转压站 民院路DN400管 600 8 关山路转压站 天京路ON300管 900 9 湖边泵站 环湖路DN300管 450 10 三环路转压站 关山一路延长线DN1000管 300

　　3.根据管网水力计算，各转压站及管道增输水量(万吨)情况如下：
　　南湖北路转压站：12；南湖北路DNl200管：12；湖边泵站：3；三环路转压站：6；南湖南路DN800管；4.5；关山路转压站；7；关山一路延长线DNl000管；7：环湖路DN300；0.5；天泉路DN300：0.5；民院路DN400管：0.5；三环路DN400管：3；鲁巷广场DN800管：4。
　　4.根据控制费用：实现武昌地区"湖改江"管网及转压站改、扩建控制费用为：1.5亿元。
　　要求选择适宜的输送方式并求各适宜输送方式下各输送管道及转压站的转输水量。
6.2本问题是一个典型的大型供水管网，改、扩建工程优化决策问题。
　　它须满足总水量及单水量目标，还须满足控制费用目标，硬目标为是总水量目标，单水量及控制费用为软目标，因此，该问题属字典序线性目标规划问题，故可用本文的字典序线性目标规划模型求解程序求解，并进行模型的灵敏度分析。
　　6.2.1字典序线性目标规划分阶段算法程序求解结果及分析
　　(1) 东湖水厂"湖改江"

序号 前输 水量(万吨) 转输 水量(万吨) 1 南湖北路转压站 8 南湖北路DN1200管 8 2 关山路转压站 1 南湖北路DN1200管 1 3 关山路转压站 0 南湖北路DN800管 0 4 关山路转压站 0 关山一路延长线DN1000管 0 5 南湖北路DN1200管 0.5 关山一路延长线DN1000管 0.5 6 湖边泵站 2.5 南湖北路DN1200 2.5

　　(2) 团山水厂"湖改江"

序号 前输 水量(万吨) 转输 水量(万吨) 1 三环路DN400管 0 三环路转压站 0 2 三环路DN400管 0 天京路DN300管 0 3 三环路DN400管 1.5 三环路DN100管 1.5 4 南湖北路转压站 4.0 鲁巷广场 4.0 5 关山路转压站 4.5 南湖南路 4.5 6 关山路转压站 0.5 关山路延长线DN1000管 0.5 7 关山路转压站 0.5 民院路DN400管 0.5 8 关山路转压站 0.5 天京路ON300管 0.5 9 湖边泵站 0.5 环湖路DN300管 0.5 10 三环路转压站 6 关山一路延长线DN1000管 6

　　由上表可知：东湖水厂"湖改江"中改、扩建单位费较低的两种输送方式被淘汰，而在团山水厂"湖改江"中改、扩建单位费较高的输送方式被淘汰，这表明所确定的输送方式并不存在一致性偏向问题。
6.2.2单元素参数灵敏度分析结果(因篇幅所限，多元素参数分析及离散变化分析结果省略).
　　在保持原模型实例所求最优基仍为最优的条件下，各输送管道及转压站输送水量允许变化范围如下：南湖北路DN1200管，三环路转压站，天泉路DN300管：0—+∞；南湖北路转压站，湖边泵站，三环路DN400管，南湖南路DN800管，关山路转压站，关山路延长线DN1000管，蚌潮路DN300管，民院路DN400管，鲁巷广场DN800管分别为：0—1.3，0—1.3，0—1，0—1，0—6，0—1，0—2.5，0—1，0—2.5。

参考文献
　　[1]IGNIZIO,J.P “Goal programming：A pool for multiobjective Analysis”，Journal of operational Research，Vol，29，Ⅱ，1978．
　　[2]J．P．Ignizio，闽仲求 《单目标和多目标系统线性规划》上海：同济大学出版杜，1986．
　　[3]韩旭昆《线性觌划灵敏度分析》,系统工程，1992．(1)．
　　[4]潭浩强，《C程序设计》，北京：清华大学出版社，1991.

作者简介：
　　杨晓安(1968—)，男，汉族，湖南人，工程师，硕士，研究方向为城市供水管网优化，武汉市自来水公司。