【doc】线性规划的目标函数最速递减算法

【doc】线性规划的目标函数最速递减算法 线性规划的目标函数最速递减算法 第14卷第4期 2005年8月 运筹与管理 OPERATIONSRE,SEARCHANDMANAGEMENTSCIENCE Vo1.14.No.4 Aug.2005 线性规划的目标函数最速递减算法 唐建国 (湖南科技学院数学与计算科学系,湖南永州425006) 摘要:在对偶单纯形方法的基础上,提出了线性规划的目标函数最速递减算法.它避开求初始可行基或初始 基,以目标函数全局快速递减作为选基准则,将选基过程与换基迭代合二为一,从而大大减少了迭代次数.数值 算例显示了该算法的有效性和优越性. 关键词:线性规划;单纯形方法;对偶单纯形方法;目标函数最速递减算法 中图分类号:0221.1,0232文章标识码:A文章编号:1007.3221(2005)04.0055.05 AFastDecreasingAlgorithmofObjectiveFunctionforLinearPrograming TANGJian—guo (DepatrmentofMathematicsandComputationalScience,HunanCollegeofScienceandTechnol— ogy,Yongzhou425006,China) Abstract:Onthebasisofsimplexmethodfordual,afastdecreasingalgorithmofobjectivefunctionispro— posed.Thismethodneedn’tfindinitialfeasiblebasisorinitialbasis. TheprocessesofchoosingbasisandeX— changingbasisarecombinedintooneprocessbyusingtheobjectivefunctiongloblefastdecreasingcriterionof choosingbasis.Andthenthenumberofiterationsisgreatlyreduced. Numericalresultsshowitseffectiveness andsuperiority. Keywords:linearprograming;simplexalgorithm;dualsimplexalgorithm;fastdecreasingalgorithmofobjec. tivefuncti0n 0引言 考虑线性规划的标准型 maxZ:CX,AX=b,X0,b>0,(1) 这里A=(d)为m×矩阵,C=()l为元行向量,X=(z)l为元列向量,b= (b)l为m元列向量.假定0<m<n,且秩A=m. 线性规划(1)已有一系列算法,如单纯形方法[1--7],对偶单纯形方法 [1--7],原始一对偶算法[,内点算 法[,邻域跟踪算法[.】等,有关线性规划问题的研究一直持续不断[~1引.线性规划问题的关键是对计算 复杂性的控制,即对迭代次数的控制,它十分复杂而较难把握和处理.各种算法的提出从不同侧重点和角 度为解决这一问题提供了许多有效的方法和手段.仔细不难发现,目标函数的系数乘以一1之值也 即检验数在迭代过程中始终处于主导地位,它直接关系到目标函数值是否还有增长潜力.特别地,当所有 检验数都大于0或非负时,目标函数值不可能再增长.如果在迭代过程中始终保持检验数非负的要求,则 收稿日期:2004.09.29 基金项目:湖南省自然科学基全责助项目(03JJY3014);湖南省教育厅科研基全责助项目(02C355) 作者简介:詹建固(1965一).男.湖南冷水津人.博士.教授. 56运筹与管理2005年第14卷 迭代过程就是目标函数值单调递减趋于最优值的过程,可避免在迭代过程中目标函数值既上升又下降所 带来的不确定性.目标函数值递减得越快,就有了能使目标函数达到最优值所需的迭代次数就越少.基 于以上观点,本文在对偶单纯形法的基础上提出了线性规划的目标 函数最速递减算法,它直接从形式(1) 开始迭代,不需要求初始可行基或初始基,也无需求对偶单纯形方法的初始基,仅需求得对偶问题可行域 中的一点,以确保初始检验数非负.以目标函数全局最速递减为选基准则,因而选基过程与消元过程就构 成了迭代过程,避免了不必要的重复计算,减少了运算量.但本文的算法不同于[7]给出的最速下降边单 纯形方法和最速下降边对偶单纯形方法,主要表现在对初始基的要求不同,选基准则不同. 1目标函数最速递减算法 为记号简便,将线性规划的标准型(1)用矩阵形式表为 这里=一,=1,2,…,称为检验数. 情形1所有检验数三三=0,=1,2,…,,常数项b>0,i=1,2…,优. 第一步选取基变量,计算比值 . {罢In>olaoi (2) 取0=min{Oib}=,则将系数n对应的变量确定为基变量. ll研” 第二步消元.第r行乘以一加到第i行,1优,i?r;第r行乘以一加到第优十1行. arsars 重复第一,第二步,直至获得最优解,或判断出有无界解或无可行解,计算终止. 当所有检验数三三=0,J=1,2,…,时,表明目标函数值不可能再增加,因而0是目标函数的一个初始 上界.实际计算中,目标函数的初始上界不一定为0,它可正可负.以上基变量的取法保证了在迭代过程 中检验数非负的前提下,目标函数值以可能最快速度递减,故称为目标函数最速递减算法.从以上迭代过 程可以看出,每次迭代目标函数值将减少0.为了以最快的速度降低目标函数值,应避免出现常数项b 和检验数j为0的情况,除非该检验数对应变量已是基变量.因此若出现常数项为0的情况,应将常数项 为正的行加到该行;若出现非基变量检验数为0的情况,也应尽量通过矩阵初等变换将其化为正数,这样 就确保了目标函数值以单调递减的方式快速趋于目标函数的最优值.随着迭化次数的增加,迭代对目标 函数值递减的作用越来越小,因而其迭代价值也越来越小. 情形2有某些检验数<0.先求得由约束条件Ay三三=c(y无非负约束)所确定的可行域中的 一 点Y0=(2,Y2,…,),然后分别在第i行乘以?后加到第优+1行,可使(2)的所有检验数非负,此 时已化为情形1. 若矩阵(2)有某一行的元素全为正,则只需在该行乘以某个正数加到第优+1行,可使所有检验数均 大于0.更弱地,若矩阵(2)有某一行的元素全非负,且该行与负检验数对应的系数全为正,则只需在该行 乘以某个正数加到第m+1行,可使所有检验数均非负.若由约束条件Ay三三=c所确定的可行域是空 集,则原问题无可行解或有无界解.在大多数实际问题中,矩阵(2)往往有正行或非负行.对于一般情形, 由于只需要可行域中的一个点的要求较低,所以经初步计算容易达到. 2数值算例 例1试用目标函数最速递减算法解下面线性规划问题 ; O “““? : ,,,, 鲥; ,,,, 222: ; ll】 如 第4期唐建国:线性规划的目标函数最速递减算法57 maxZ:2x1+392—2x3十2x4—3x5—2x6 f—z1”4-5x2”4-2x3—2x4”4-3x5一X62 I3x1—4z3+5x4—2x5”4-z6=1 I2z1—2x2-4-z3-4-4x5+3x62 【z0,J=1,2,3,4,5,6 解下式第一个矩阵的第1,2,3行分别乘以1后加到第4行得第二个矩阵,此时所有检验数均大于 0.在第二个矩 中,1=min{2/5,1/2,8/3}:2/5,2=rain{2/3,1/5,5/1}=1/5,3=min{2/2,1/1,8/4,5/ 3}=1,=max{2?2/5,1?1/5,2?1}=2,所以取a31对应的变元z1作为主元. 同理可在第三,四个矩阵中 选取主元,计算过程如下: 一 2 5 0 — 2 3 — 2 4 3 — 410 — 1016 04 14 — 52943134 315—1223 29866165 4717616685 59595959 2 — 4 1 1 5 0 0 0 — 2 5 0 1 — 4 3 2 1 — 1 1 3 5 2 1 2 5 16 — 1223 72 23 fXl+102+2x310 Iz1+4x2+2x36 S’t”Iz1+5z2+6x3~>4 【xj>O,J=1,2,3. 060—1 3062 00—24—1 001 j 10 — 50 — 56 20 j 原线性规划问题有唯一最优解,最优解为X=(103,2/3,0,0,0,8/3)T,最大值为z=一22/3.迭代次 数为2,文[11]所用迭代次数为3,因而优于文献[11]的结果. 例3C试用目标函数最速递减算法解下面线性规划问题 2x4 maxZ=20x1”4-13x2—4x3— r3Xl-4-x2一x3-4-x53 I4:rl+3x2-4-x6=6 {z1”4-2x2一z4+z7=2 【xj>O,=1,2,3,4,5,6,7. 348:254 5028 固4 —3匡20050 21206423 l h1321732 212固n10000 2l62 50一一8一一4000 320020000 2 0020 5 0—00 1?1 5 —2—3— 2619—5 m000 固2—5 640 00—0 0—00 —000 2263 圆456 58运筹与管理2005年第14卷 解第一个矩阵的第二行乘以5加到第4行,可使所有检验数非负.在 第二个矩阵中,X5,X7已是基 变量,由于变量Xl的检验数为0,又口21>口i=1,3,所以取a21对应 变量为主元.类似前面两例,计算 过程如下: 3 4 1 — 2O 1—1 3O 2O 一 134 固4 3O 5O 24 4 — 3 1 2 5 O1 OO 一 1O 2O O O 一 4 2 — 4 O O O 一 4 3 — 1 18 5 540——43 O一303—1 01l1l一11 0号萼 原线性规划问题有唯一最优解,最优解为X’=(3/5,6/5,0,1,0,0,0)丁,最大值为Z’=128/5.迭代次数 为3,文献[15]所用迭代次数为4,因而优于文[15]的结果. 例4E加】试用目标函数最速递减算法解下面线性规划问题 4x5 minZ=2Xl——3x2x4—— 【31+2—2x3一4一x50 l—1+2x2—3x3+2x5=0 s.t.一Xl—x2+x3+2x4—3x5=0 lXl+X2+X3+X4+X51 【f0,=1,2,3,4,5 解令Z=一Z,则目标函数化为maxZ=一2x1+3x2一4+4x5,约束条件与原问题相同.本例中 约束条件只有一个常数项大于0,其余常数项均为0,检验数有正有负.第一个矩阵的第4行乘以5加到 第5行,第4行乘以1分别加到第1,2,3行,可使检验数及约束条件的常数项均大于0.采用目标函数最 速递减算法求解,计算过程如下: 1 2 — 1 1 — 3 O O O 3 O O 1 国 1 6 O 0 11 0 0 42—1 09—8 OO2 3国1 721 37OO OO37 OOO O37O OOO O 11 — 2 5 5 — 3O 38 — 5O 79 199 37 所以原线性规戈?问题有唯一最优解,最优解为 X’=(3/37,18/37,11/37,5/37,0)丁,最优值为Z’=一 (Z)’=一43/37(注:文献[10]的计算结果有误),迭代次数为最小次数4. 例5t试用目标函数最速递减算法解下面线性规划问题 minZ=12x1+8372+16x3”4-12x4 f2x1+2+4x32 s.t.2x1+2x2+4x43 【0,_f=1,2,3,4. 362?63.一5 l OO1OOO一0 O1O5 1OOO l OO一2 l —OO4 1322 3—4—1OO5O0 362o662?63.一5 OO1OOO4OOO一2 o1oo315319—5 O4OOO5OO 121233?5埔一” OO3OOOOOO 111153416”一? 21o3一..41”“一? 215onooo 23O12OOO?O 4oo.798一n OOO1O14125—3 134,2.2.455—3 l —O211OO3OO 23]==1一..o5一n一2..一3 116 3一一12—9O35 第4期唐建国:线性规划的目标函数最速递减算法59 解令Z=一Z,则目标函数化为maxZ=一12xl一8x2—16x3—12x4,约束条件与原问题相同.本 例若直接采用目标函数最速递减算法求解,则需3次迭代.为减少迭代次数,我们对约束条件作简单的变 换,即第一个矩阵的第2行加到第1行后,得到第二个矩阵.计算过程如下: 2140 22O4 1281612 4344——1 圉0国一4—2 詈0詈号 由于非基变量z3的检验数为0,所以原线性规划问题有多重最优解,一个基本最优解为x=(1/2, 1,0,0)T,另一个基本最优解为x=(0,3/2,1/8,0)丁,所以最优解为X=X+(1一)x,?[0, 1],最优值为Z=一(z):14,迭代次数为2,文[2]所用迭代次数为3,因而优于文[2]的结果. 3结束语 本文提出了线性规划的目标函数最速递减算法,数值算例显示该方法计算效果较好,因而具有一定的 优越性.与单纯形方法相比,可避开求初始可行基或初始基这一繁杂的过程,而直接将选基消元过程和换 基迭代过程合二为一,简化了计算.与对偶单纯形方法相比,也无需确定对偶单纯形方法的初始基,该算 法在每一迭代过程中,目标函数以全局最快的速度单调递减趋于最优值,从而大大减小了迭代次数.对于 初始有负检验数的情形,由于实际问题中约束条件大多有为正或非负的行,因而容易化为检验数非负的情 形.约束条件中即使没有为正或非负的行,也只需找到其对偶问题可 行域中的一点即可,比单纯形方法求 初始可行基要容易得多.目标函数最速递减算法虽然大大减少了迭代次数,但还不能保证对含个独立 约束条件的线性规划仅用不超过次迭代求得其最优解.这一点容易用动态规划理论来解释:将整个求 解过程看成是一个动态规划,每次迭代即是动态规划的一个阶段,目标函数最速递减算法虽然在动态规划 的每一阶段都取最优值,但整体却不一定能达到最优.我们将在本文方法的基础上,继续探索仅用不超过 矾次迭代求得最优解的算法,目前已得到初步结果,这一方法将在另文中介绍. 参考文献: [1]运筹学教材编写组.运筹学[M].北京:清华大学出版社,1990. [2]程理民,吴江,张玉林.运筹学模型与方法教程[M].北京:清华大学出版社,2003. [3]赵新泽.线性规划的新方法和应用[M].北京:世界图出版公司.1996. [4】席少霖,赵风治.最优化计算方法[M].上海;上海科学技术大学出版社.1983, [5]薛毅.最优化原理与方法[M].北京:北京工业大学出版社,2001. 【6]陈宝林.最优化理论与算法【M].北京:清华大学出版社,1989. [7]胡清淮,魏一鸣.线性规划及其应用[M].北京:科学出版社,2004. [8]艾文宝.线性规划的邻域跟踪法[J].中国科学A辑(数学),2004,34(1):4O一47. [9]张望明,黄崇超.一类非单调互补问题的高阶仿射尺度算法[j】.计算数学,2004,26(1):37—46. [1O]刑志栋,王若鹏,董建民.一类线性规划的调节熵函数法[J].西北大学(自然科学版),2004,34(1):1—3 [11]李炜.求线性规划初始可行基的新方法[J].运筹与管理,2004,13(1):7—1O. [12】夏少刚.线性规划联合算法的理论与应用[J].运筹与管理,2004,13(1):l1一l6. [13]夏少刚.对”求解线性规划问题的一种全搜索方法”的改进与修正[J].运筹与管理,2004,13(3):10—14. [14]吴振奎,王文全,刘振航.线性规划问题通解表示的注igEJ].运筹与管理,2004,13(1):63—67. [15]高国成,王卓鹏,孟艳双.关于使用最大改进规则的单纯形算法[J].运筹与管理,2004,13(2):5—7. [16]高国成,王卓鹏,刘晓妍.线性规划问题的规范型算法[J].运筹与管理,2004,13(3):35—37. 530 1?1? 一一O L 一00 44 40 国28 42 230 L 0—0 L —O0 4 l11一 L 一12 2 1—4 4 4—4 4 —80 100 020 5. ?一3 — 3 .8—