【doc】规范形式LP问题的改进对偶单纯形法

【doc】规范形式LP问题的改进对偶单纯形法 规范形式LP问题的改进对偶单纯形法 第2l卷 V01.2l 第3期 No.3 重庆工学院(自然科学版) JoumaldcllInstituteofTechnology(NaturalScienceEdition) 20cr7年3月 Mar.20cr7 【数理化科学】 规范形式LP问题的改进对偶单纯形法’ 张劲松,赵冬梅2 (1.九江学院理学院,江西九江332005;2.北京丰台王佐学校,北京100074) 摘要:通过分析对偶单纯形法迭代的实质,就所给LP问题的规范形式,不引进剩余变量而直接得 出另一种改进的对偶单纯形法,使变量个数不增且运算规模缩小. 关键词:IV问题;规范形式;对偶单纯形法 中图分类号:O221.1文献标识码:A文章编号:1671—09U(2007}03—0100—03 hnprovedDualSimplexAlgoritlnnonLinear ProgrammingwithNormalForm song,ZHAODong-mei2 ZHANGJin— (1.CollegedScience,JiujiangUniversity,Jiujiang332005,China; 2.WangzuoSchool,Fengtal,100074,China) Abstract:Bya~dyzmgtheessenceofiterationonthedualsimplex~tgonthmandbasedonLinearh一 IIlingwithnormalform,thispapergai璐anotherimproveddualsimplexalg 耐tllmwithoutIlgiIlginsurplus variables,whichresultsinthesamenumberofvariablesandreducedoperationalsize. Keywords:LinearProgrammingproblem;normalform;dualsimplextllm O引言 对于一类含有初始基(但不是正则基)的LP问题,可 以添加人工约束,或直接迭代来求得初始正则基【1I2】.因 此,只要所给LP问题含有初始基,总可以找到初始正则 基,从而开始对偶单纯形法迭代.容易看出:若所给LP问 题是规范形式,只要添加剩余变量,将”“型约束不等式 组变为约束方程组,再将各个方程分别左右两边同乘以 (一1),则立即得到一个初始基. 但通过表上作业,在对偶单纯形法迭代到最优表时, 发现剩余变量所对应的列可以说是不起作用的.因为对原 问题来讲,剩余变量本身就不存在,而所需要的解(包括最 优解)的分量也不必含有剩余变量.既然这样,是不是对于 规范形式的LP问题可以不引进剩余变量而直接应用对偶 单纯形法呢?毋庸置疑,这样做对于具有规范形式的大规 模LP问题将是意义重形式LP问题的改进对偶单纯形法101 f:=c’’ {8.t./ix—Xa=b(2)【 0,‰0 列出问题(2)的初始表(表1). 本文中在不违背基的定义的基础上,省略在各个方程 两边同乘以(一1)的工作,人工变量所在列即第n+(i= 1,2,…,m)列是初始基列,将其涂成灰色.相应地,+i为 基变量,由一cs0知,初始解是正则解.对于初始基来说, bi>0(iEl1,2,…,m})意味着原始不可行. 表1问题(2)的初始表 I…Xk…靠+I…靠+r…+6 :一…一…一0…0…00 +Igill’”(Ilk…(1I—l…0…06I ; —rarl…d…am一l6, ; n+m口_I…口_…am0…0…一l 定理1用对偶单纯形法求解问题(1),可以省略表1 +.一+区域中人工变量所在列及其迭代过程. 证明:考察问题(2)的初始表(表1),这时,若bs0(f, 1,2,…,m),初始解具有原始可行性,即是最优解.因此考 虑b(i=1,2,…,m)不全小于或等于零的情形. 情形1:考察某个b,>0,若s0(.『=1,2,…,n),则第 r行对应于问题(2)中的方程是矛盾方程,问题(2)无解. 情形2:进行对偶单纯形法迭代.由对偶单纯形法选转 轴元的最小比值规则,迭代始终保持对偶可行性且逐步减 少原始不可行性.从表1来看,每一步迭代,无非就是从A 中各个非基列中选取一列来替代灰色区域中的某一基列 (由Bland规则防止出现循环),这其实等价于在A中来寻 找基列.对于初始基来说,bi>0(?l1,2,…,m})意味着原 始不可行,而若人工变量+i出基,A中某一列入基,则变 为原始可行.因此,在所有大于零的b所在的行由最小比 值规则寻找转轴元,从而确定人基列即可.若所得基列的 个数小于m,当然不能构成一个新的基,这时必定有某个 人工变量+i还是基变量,但其对应的bi0(?{1,2,…, m}),具有原始可行性.为使新基的列统一都是单位列向 量,只要将所在行乘以(一1)即可. 这些工作都无须涉及灰色区域. 证毕. 2算法步骤 根据定理1,考虑b(=1,2,…,m)不全小于或等于零 的情形. 第1步:列出初始单纯形表(它含有一个正则解,但隐 藏了正则基); 第2步:置,:=l1,2,…,m},求b,=max{b’I?,}; 第3步:若b,0,将第r行乘以(一1),并在该行最左 面标注*,表示其为基变量,转第7步,否则,转第4步; 第4步:若0(.『=1,2,…,n),停止,原问题无可行 解,否则,转第5步; 第5步:求nfin{l岛/1.ao>0,.『=1,2,…,n}= /; 第6步:以为转轴元作一次旋转变换,成为基变 量,将其标注在该行最左面; 第7步:若基变量个数等于m,停止,已得最优解,否 则置,:=,一{r},转第2步. 3算例 例1解下面的LP问题: rnfin:=Xl+X2+X3 Is.t.3xl+X2+31 I—Xl+4x2+X32 Ll,2,30 解:迭代过程见表2.得最优解=(,7,0),最优 值:=9. 表2例1迭代过程 XlX2X3b 一 1—1—10 3111 — 1412 一 0一1 4u42 13,,31u 2 一 1,1 X2一4’42 00一景913 Xl10132 1.,13 2o1舌713 例2解下面的LP问题: frain3xl+2x2+x3 ls.t.Xl+x2+x3s6 X34 {Xl— lX2一X33 LXl,X2,X30 解:将第一个不等式约束化为:一l—2一3一6,原 问题即为规范形式.迭代过程见表3.由表3中最后一块单 纯形表第l行知,原问题无解. 102重庆工学院 表3例2迭代过程 XlX2X3b :一3—2—10 — 1—1—1—6 10—14 01—13 0—2—412 0—1—2—2 Xl10—14 0r一13 00—618 00—31 Xl10一14 13 X201— {. 杂,但其在相当大的程度上减少了变量的个数.更为重要 的是,该算法突破了其它许多算法都依赖于LP问题的标 准形式这一思维定势.事实上,由线性规划的基本知识不 难知道,任何一个LP问题都可以化到规范形式,这说明了 该算法在应用上具有一般性.当然,该算法最适用的是已 含初始正则解的LP问题. 表4例3迭代过程 XlX2b 一 2—40 2—3一10 — 113 — 6012 — 10—1 X2—113 — 6012 1101 2—113 参考文献: 解:迭代过程见表4.得最优解=(0,3),最优值[13~. ff--宗.线性规划[M].武汉:武汉大学出版社, :=12.20O4:128— 130. 4结束语 文献[33将改进单纯形法的思想应用到对偶单纯形法 上,使运算规模缩小而变量的个数没有改变.本文中所给 算法可以看作是对偶单纯形法的简化,主要思想并不复 [2]陆宗元.广义对偶单纯形方法[J].上海师范大学学 报:自然科学版,2oo2(2):4—6. [3]罗雁,简金宝,吴志远.线性规划一种改进的对偶单纯 形法[J].桂林工学院,2o05(2):263—266. (上接第95页)交流量对本身的行程时间的边际影响大于 等当量的摩动流量对常规公交行程时间的边际影响,反之 亦然.即说明了目标函数的Hessian矩阵是正定的.则目标 函数为严格的凸函数,因此模型具有唯一的最优解. 3结束语 在城市交通需求预测中,由于传统的四阶段法中各个 阶段相对独立和分割,导致了预测工作量大,人力物力耗 费巨大,并且也会出现很多不切实际的情况,造成很多弊 端.而本文中正是立足于克服这些弊端,建立了城市交通 需求预测组合模型,证明了组合模型的最优性条件等价于 Wardrop均衡原理以及路段流量解的唯一性.至于该模型的 算法在许多专着中都能够找到,这里由于篇幅限制,不再 具体说明.在实际的工程运用中,努力地优化模型,不断的 提高算法的效率才是更重要的.对于大规划问题,传统的 算法如凸组合算法就显得无能为力,因此下一步的工作是 对于模型的传统算法进行改进,拟用遗传算法GA(genetic (责任编辑刘舸) algorithm)来求解模型,使该模型能够适合于大型规划问题 和提高算法的效率. 参考文献: [1]陆化普.交通规划理论与方法[M].北京:清华大学出 版社.1998. [2]王炜,徐吉谦,杨涛,等.城市交通规划理论及其应用 [M].南京:东南大学出版社,1998. [3]刘安,扬佩昆.混合交通均衡配流模型及其算法的研 究[J].公路交通科技,1996,13(3):21—28. [4]黄海军.城市交通网络平衡分析理论与实践[M].北 京:人民交通出版社.1994. [5]周溪召.混合交通运量分布与均衡配流组合模型研究 [J].系统工程,2000,15(2):153—157. (责任编辑刘舸)