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

'字典序目标规划法在大型供水管网改、扩建工程优化决策中的应用摘要：本文将字典序线性目标规划基本模型应用于大型供水管网改、扩建优化决策，建立了大型供水管网改、扩建工程优化决策字典序线性目标规划模型，并用字典序线性目标规划多阶段算法进行计算，编制了相应的计算程序，且根据其计算特点，编制了字典序线性目标规划灵敏度分析程序，对所建立的模型进行灵敏度分析。计算实例表明：字典序线性目标规划法的理论和方法非常适合大型供水管网改、扩建工程优化决策计算，结果令人满意。所编制程序具有准确性和通用性，对生产具有科学和实际的指导意义。关键词：字典序目标规划供水管网灵敏度TheLexicographicLinearGoalprogrammingisappliedtotheOptimalDecision-makingofthelargeWaterNetworksRebuliding&Enlargingproject　　Abstract：ThebasicmodelofthelexicographiclinearGoalprogrammingisappliedtocalculatingtheoptinaldecision-makingofthelargewaternetworksrebuliding&enlargingproject.Amodelusedforcalculatingtheoptimaldecision-makingofthelargewaternetworksrebuliding&enlargingprojectisconstructed.ThelexicographiclinearGoalprogrammingmutiplestagealgorithmisusedtocalculate.Acorrelativecalculatingprogramisprogrammed.Accordingtoitscalculatingcharacteristics,theprocedureofthelexicographiclinearGoalprogrammingsensitivityanalysisismadetoanalysetheconstructedmodel.Thecalculatingexampleindicatesthat，thetheoryandthemethodofthelexicographiclinearGoalprogrammingisverysuitableforthecalculationoftheoptimaldecision—makingofthelargewaternetworksrebuliding&enlargingproject.Theresultprovessatisfactory.Theprogramsarepreciseandstable.Theyhavescientificandpracticalguidingvaluetoproduction.　　keywords：LexiGographicGoalprogrmmingwaternetworkssensitivity10 1字典序线性目标规划基本模型[1][2]1.1字典序线性目标规划方法的概念　　字典序线性目标规划(LexicopraphicLinearGoalprogramming)简称LLGP是美国阿波罗计划工程师J.P伊格尼齐奥于1976年在研究目标规划法的基础上提出的一种用目标偏差量有序向量衡量多目标模型目标达成度的字典序最小方法。1.2数学模型　　LLGP方法的数学模型为：　　求x（x1,x2,…,xn）　　使Lexminα={g1(η,δ),g2(η,δ),…,gk(η,δ)}　（1-1-1）　　　s.t∑nj=1=cI,jxj+ηi-δi=bi，i=1,2,…,m　　　　（1-1-2）　　　x,η,δ≧0　　　　　　　　　　　　　　　　　　　　（1-1-3）　　其中：x—n维决策变量；η—负偏差变量；δ—正偏差变量；gk(η,δ)—为第K个优先级别中目标偏差变量的线性系数：α—寻求字典序极小化达成系数；cI,j—是对应于第i个目标或约束中第j个变量的系数；bi—为目标或约束分端常数：（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)所考察的各类水量；S1，S2，……，Sp；10 　　(2)每种输送方式费用单价：C11，C12，…，C1q1；…，…，…，…；　　　　　　　　　　　　　　　　Cp1，Cp2，…，Cpqp；　　(3)各条输送管道及各转压站的输送水量；A1，A2，……，Ar　　(4)所有改.扩建管道及转压站项目的控制费用：W3.2待求变量：　　(1)每类水量适宜的输送方式输送该类水量的量：　　　　X11，X12，…，X1q1；…，…，…，…；xp1，xp2，…，xpqp；　　(2)每种输送方式下换输管道和转压站所输送水量：　　　　x111，x112，…，x11r11；…，…，…，…；xpqp1，xpqp2，…，xpqprpqp；　　(3)各种输送方式下各种输送管道和转压站的输送水量：；　　　　x11A1，x11A2，…，x11Ar；…，…，…，…；xpqpA1，xpqpA2，…，xpqpAr；3.3计算模型：　　3.3.1目标：　　(1)每类水量各输送方式所输送水量之和与该类水量相等，即：　　　∑q1j1=1x1j1=S1；∑q2j2=1x2j2=S2；…；∑qpjp=1xpjp=Sp；　　　　（3-1-1）　　(2)输送各类水量各输送方式管道及转压站改、扩建费用之和等于总控制费用：　　　∑q1j1=1C1j1x1j1+∑q2j2=1C2j2x2j2+…∑qpjp=1Cpjpxpjp=w；　　　（3-1-2）　　(3)输送各类水量同一种管道求转压站所输送水量应该等于该管道求转压站所输送的水量：　　　∑q1j1=1x1j1A1+∑q2j2=1x2j2A1+…∑qpjp=1xpjpA1；…；∑q1j1=1x1j1Ar+∑q2j2=1x2j2Ar+…∑qpjp=1xpjpAr=Ar　　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+ubt*)≧0的u的　　取值范围(因篇幅所限，公式推导及结果省略).4.3离散变化的灵敏度分析：　　从单元素变化及多元素参数分析所确定的各取一u值，计算XTb*B-1(b+ubt*)及atk*=∑m+ns=1Wk,s*XTb,s*+∑mI=1uI,k*XTb,I*10 　　其中：t—单元素变化或多元素参数分析的第t个方案；XTb,s*—问题变量中的负偏差变量值；XTb,I*—问题变量中的正偏差变量值。5大型供水管网改扩建工程优化决策字典序线性目标规划模型多阶段单纯形算法程序框图及灵敏度分析程序框图[4]5.1多阶段单纯形算法程序框图5.2灵敏度分析程序框图6例计算和分析6.1实例　　1.武汉武昌地区“湖改江”工程，含东湖水厂“湖改江”和团山水厂“湖改江”，根据武昌地区供水规划，实现东湖水厂“湖改江”须补充水量12万吨／日，实现团山水厂“湖改江”须增加水量18万吨／日。　　2.实现东湖水厂"湖改江"有以下六种可能输送方式：序号前输转输改、扩建单位费用(元／m3)1南湖北路转压站南湖北路DN1200管6002关山路转压站南湖北路DN1200管4503关山路转压站南湖南路DN800管300410 关山路转压站关山一路延长线DNl000管3005南湖北路DNl200管关山一路延长线DN1000管4506湖边泵站南湖北路DN1200600　　(B)实现团山水厂“湖改江”有以下十种可能输送方式：序号前输转输改、扩建单位费用(元／m3)1三环路DN400管三环路转压站6002三环路DN400管天京路DN300管6003三环路DN400管三环路DN100管9004南湖北路转压站鲁巷广场60010 5关山路转压站南湖南路3006关山路转压站关山路延长线DN1000管3007关山路转压站民院路DN400管6008关山路转压站天京路ON300管9009湖边泵站环湖路DN300管45010三环路转压站关山一路延长线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字典序线性目标规划分阶段算法程序求解结果及分析10 　　(1)东湖水厂"湖改江"序号前输水量(万吨)转输水量(万吨)1南湖北路转压站8南湖北路DN1200管82关山路转压站1南湖北路DN1200管13关山路转压站0南湖北路DN800管04关山路转压站0关山一路延长线DN1000管05南湖北路DN1200管0.5关山一路延长线DN1000管0.56湖边泵站2.5南湖北路DN120010 2.5　　(2)团山水厂"湖改江"序号前输水量(万吨)转输水量(万吨)1三环路DN400管0三环路转压站02三环路DN400管0天京路DN300管03三环路DN400管1.5三环路DN100管1.54南湖北路转压站4.0鲁巷广场4.05关山路转压站4.5南湖南路4.56关山路转压站10 0.5关山路延长线DN1000管0.57关山路转压站0.5民院路DN400管0.58关山路转压站0.5天京路ON300管0.59湖边泵站0.5环湖路DN300管0.510三环路转压站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“Goalprogramming：ApoolformultiobjectiveAnalysis”，JournalofoperationalResearch，Vol，29，Ⅱ，1978．　　[2]J．P．Ignizio，闽仲求10 《单目标和多目标系统线性规划》上海：同济大学出版杜，1986．　　[3]韩旭昆《线性觌划灵敏度分析》,系统工程，1992．(1)．　　[4]潭浩强，《C程序设计》，北京：清华大学出版社，1991.10'