（运筹学与控制论专业论文）带有软硬约束的线性目标规划的两种算法.pdf

兰州大学2007 届硕士学位论文 摘要 目标规划是一种解决实际生活中多目标问题的有效方法，它作为一个强大而实 用的工具，近几年来一直是国际学术界研究的热门话题，特别是对那些具有众多而 相互矛盾的星标，以及软硬约束共存的问题，在理论和应用方面都取得了很大的进 展但是，对这类姆题用常规的方法进行求解时，通常都要作许多简化的( 往往是有 一定问题的) 假定，这使得有些问题失去了原来的实际应用意义 本文结合线性目标规划自身的特点，将基线算法和对偶基线算法推广到了线性 目标规划问题，构造了基线算法和对偶基线算法中所没有的检验数行，将目标函数 按照优先因素多阶段化，形成了目标规划的多阶段基线算法和多阶段对偶基线算 法，并解决了带有软硬约束条件的目标规划问题，给出了寻找初始可行基的可行的 方法文中给出了这两种算法的计算步骤并讨论了他们的收敛性，通过编程与目标 规划的单纯形法进行了比较数值实验表明，多阶段基线算法和多阶段对偶基线算 法较通常的单纯形法更易操作、迭代次数更少、数值稳定性更强 关键词：线性目标规划，基线算法，对偶基线算法，软约束，硬约束，多阶段基 线算法，多阶段对偶基线算法 兰州大学2007 届硕士学位论文 a b s t r a c t t h e0 b j e c t i v ep r o g r a m m i n g 培a ne f f e c t i v em e t h o dt os o l v em u l t i - o b j e c t i v e o p t i m i z a t i o np r o b l e mi no u rd a i l yl i f e a 8ap o w e r f u la n dp r a c t i c a lt 0 0 1 i th a s b e e na t t r a c t i n gm o r ea n dm o r ea t t e n t i o n sa n db e c o m i n gah o t - d i s c u s s e dt o p i ci n t h ew h o l eg l o b a la c a d e m eo v e rt h er e c e n ty e a r s i th a sg a i n e dm u c hi m p o r t a n t p r o g r e s si nb o t ho ft h et h e o r e t i c a lr e s e a r c ha n di t sa p p l i c a t i o n ，e s p e c i a l l yi ns o l v i n g t h ep r o b l e m sw h i c hc o n t a i nm u l t i p l eb u ts e l f - c o n t r a d i c t o r yo b j e c t i o n sa n dp r o b l e m s i n c l u d i n gb o t hs o f ta n dh a r dr e s t r i c t i o n h o w e v e r ，a p p l y i n gc o n v e n t i o n a lm e t h o d t os o l v es u c hk i n do fp r o b l e mi sa l w a y sb a s e do nm a n ya s e u m p t i o n sr u s u a l l y , s o m e o fw h i c ha r ep r o b a b l yi n c o r r e c t ) ，w h i c hm a d et h em o d e ll o o s ei t sp r a c t i c a lv a l u e i nt h i sp a p e r ，c o m b i n e dw i t ht h ec h a r a c t e r i s t i co ft h el i n e a l0 b j e c t i v ep r o - g r a m m i n g ，t h eb a s i cl i n ea l g o r i t h m ( b 己a ) a n dt h ed u a lb a s i cl i n ea l g o r i t h m ( d b l a ) w e r ee x t e n d e di n t os o l v i n gt h el i n e a lo b j e c t i v ep r o g r a m m i n g t h ec o n - c e p to ft e s tn u m b e ra r r a yw h i c hd i d n tu s e di nb l aa n dd b l aw a sc o n s t r u c t e d t h r o u g hd i v i d i n gt h eo b j e c t i v ef u n c t i o ni n t od i f f e r e n ts t a g e sa c c o r d i n gt ot h e i rp r i - o r i t yf a c t o r s ，am u l t i - s t a g eb l aa n dam u l t i - s t a g ed b l af o rt h eo b j e c t i v ep r o - g r a n n n i n gp r o b l e mw e r ef o r m e d t h eo b j e c t i v ep r o g r a m m i n gp r o b l e mw i t hs o f ta n d h a r dr e s t r i c t i o nw a sa l s os o l v e da n daw a yt of i n do u tt h ei n i t i a lf e a s i b l eb a s i so fi t w a sg i v e n ；f i n a l l y , t h ep r o c e d u r e sa n dt h e c o n v e r g e n c eo ft h em u l t i - s t a g eb l a a n d t h em u l t i - s t a g ed b l aw e r ea l s od i s c u s s e dr e s p e c t i v d y b yc o m p a r i n gw i t ht h e s i m p l e xm e t h o di no b j e c t i v ep r o g r a m m i n g ，t h en u m e r i ce x p e r i m e n td i s p l a 辨dt h a t t h em u l t i - s t a g eb l aa n dt h e m u l t i - s t a g ed b l a a l em u c hm o r ee a s i l yt 0o p e r a t e a n dn e e dl e s si t e r a t i v es t e p s ，a n dt h en u m e r i cs t a b i l i t ya l es h o w e db e t t e r k e y w o r d s ：l i n e a ro b j e c t i v ep r o g r a m m i n g ，b a s i cl i n ea l g o r i t h m ，d u a l b a s i cl i n ea l g o r i t h m ，s o f tr e s t r i c t i o n ，h a r dr e s t r i c t i o n ，m u l t i - s t a g eb a s i c l i n ea l g o r i t h m ，m u l t i - s t a g ed u a lb a s i cl i n ea l g o r i t h m 2 原创，陛声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导f 独立进行 研究所取得的成果学位论文中凡引用他人已经发表或未发表的成果、数 据、观点等：均已明确注明出处除文中已经注明引用的内容外，不包含 任何其他个人或集体已经发表或撰写过的科研成果对本文的研究成果 做出重要贡献的个人和集体，均已在文中以明确方式标明 本声明的法律责任由本人承担 论文作者签名：三乒差孓日期：j 至孕二址 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属 兰州大学本人完全了解兰州大学有关保存、使用学位论文的规定，同意 学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论 文被查阅和借阅；本人授权兰州大学可以将奉学位论文的全部或部分内 容编入有关数据阵进行检索，可以采用任何复制手段保存和汇编本学位 论文本人离校后发表、使用学位论文或与该论文直接相关的学术论文 或成果时，第一署名单位仍然为兰州大学 保密论文在解密后应遵守此规定 论文作者签名：毫阻导师签名：垄当塑缮_ 日期：兰牡口 第一章 引言 目标规划是一种多目标规划技术，其基本思想源于s i m o n 的目标满意概念 1 1 ， 即每一个目标都有一个要达到的标靶或目标值，然后使距离这些目标的偏差最小 化目标规划作为运筹学的一个重要分支，是国外于2 0 世纪6 0 年代初开始兴起的 一种数学规划方法c h a r n e s 、c o o p e r 和f e r g u s o n 等人在1 9 5 5 年发表的一篇关 于用线性规划来最优地测算经理人员的酬劳的文章中，为目标规划的产生打下了基 础【2 l ，但目标规划这一术语则是1 9 6 1 年在c h a r n e s 和c o o p e r 所著的管理模型 与线性规划的工业应用( m a n a g e m e n tm o d e l 8a n di n d u s t r i a la p p l i c a t i o n so fl i n e a r p r o g r a m m i n g ) 一书中首次提出的【3 】 l e e 在其1 9 7 2 年出版的决策分析的目标规划( g o a l p r o g r a m m i n g f o r d e c i s i o n a n a l y s i s ) 一书中介绍了目标规划的基本概念、解法及其在生产计划、财务决策、市 场决策、公司计划、学院计划、政府决策、医疗保健计划等多方面的应用，是致 力于讨论目标规划的第一本专著1 4 】i g n i z i o 在他1 9 7 6 年所著的目标规划及其 扩展( g o a lp r o g r a m m i n ga n de x t e n s i o n ) 一书中详细讨论了目标规划的应用f 5 】 s c h n i e d e r j a n s 在其1 9 8 4 年出版的线性目标规划( l i n e a rg o a lp r o g r a m m i n g ) 一 书中详细讨论了目标规划的应用【6 1 r o m e o 在其1 9 9 1 年出版的目标规划关键 问题手册( h a n d b o o ko fc r i t i c a li s s u e si ng o a lp r o g r a m m i n g ) 一书中探讨了目标 规划的建模方法 7 1 ，并给出了详尽的( 3 5 0 篇以上) 参考文献目录在i g n i z i o 和 c a v a l i e r 于1 9 9 4 年出版的线性规划( l i n e a rp r o g r a m m i n g ) 一书中对目标规划 及其向人工智能领域的扩展进行了综述【8 】 大体上说，7 0 年代到8 0 年代初期是目标规划蓬勃发展的阶段，许多学者进行 了多方面的探索，发表了数百篇研究论文，在理论和实践两方面都有不少进展；但 8 0 年代中期以后对目标规划的研究却有所减退：从9 0 年代中期开始，目标规划又 开始引起人们的注意1 9 9 4 年6 月1 日至3 日在英国p o r t s m o u t h 大学召开了第 一届多目标规划与目标规划理论与应用国际会议( m o p g p 9 4 ) 1 9 】，会上共宣读了 1 0 篇目标规划方面的论文，i g n i z i o 教授在会议上作了有关目标规划的主题演讲 1 9 9 6 年5 月1 6 至1 8 日在西班牙的t o r r e m o l i n o s 召开了第二届多目标规划与目 标规划理论与应用国际会议【1 0 】，会上宣读了8 篇有关目标规划的论文，从中可以 看到目标规划在理论和应用方面的一些新进展 我国学者在目标规划方面的研究大致开始于2 0 世纪8 0 年代初期，主要侧重 于其应用，不仅翻译了i g n i z i o 、l e e 等人的著作，宣家骥、方爱群【l l 】、陈景艳1 1 2 、 赵可培f 1 3 】、陈昌年【1 4 】、裴鑫德 15 】等人还编写了目标规划方面的专著近年来国内 学者每年都有十多篇论文发表，但其研究深度及应用广度都远远逊于线性规划、整 1 兰州大学2o07 届硕士学位论文 数规划及动态规划等其它数学规划方法 目标规划作为一种较新的处理多目标问题的数学规划方法，近几年来一直是国 际学术界研究的热门话题，特别是在改进大型目标规划的算法问题上，至今还没有 发现可以取代用单纯形法解目标规划的新算法。由于线性目标规划是从线性规划引 申而来，因此，一般而论，线性规划中基于单纯形法的各种方法都可用于解线性目 标规划问题i s , t 6 , t 7 ，1 8 1 我们一直在研究是否存在一种新的算法可以取代单纯形算法， 从而使得线性目标规划的算法能够得到改善1 9 7 9 年，k h a c h i y a n 得到了线性规 划的第一个多项式时闻算法：椭球算法1 1 9 l ，其算法复杂性为d ( 7 ) ，理论价值重大 但不大实用，使得其不能和单纯形法抗争；1 9 8 4 年，k a r m a r k a r 提出投影法( 内 点算法) 例，理论上证明了此法是o ( n a 5 ) 级的多项式时间算法，曾被声称对解大 规模线性规划将比单纯形法快5 0 倍，但经过1 0 年多来的努力改进，至今平均约 快2 4 倍，而且技术较复杂，难以普及1 9 9 6 年，由阮国桢等人先后提出了基线算 法( 也称流动含优面法) 【2 1 纠及对偶基线算法 2 5 1 ，是一种解线性规划问题的高效 新算法，该算法是否能成为一种求解线性规划的快速而有效的实用算法，而与单纯 形法媲美，这有待于今后的实践来验证 单纯形算法是基于从多面体的一个顶点移到另一个顶点，同时使其费用得到改 善，因此，这个算法能在有限步内找出线性规划的最优解该算法是由g b d a n t z i g 在1 9 4 7 年发现的，在著作1 1 6 】中详细介绍了线性规划的起源及单纯形算法的发展过 程单纯形算法的主要优点是每一步迭代只作一次旋转，方法简单易操作，对于解 几百个变量和几千个约束的线性规划问题是相当有效的但是，也确有一些特殊构 造出来的问题，对这些问题单纯形算法所需的步数是指数的如：1 9 7 2 年v k l e e 和g m i n t , y 构造的一个体个变量，2 竹个不等式约束的例子，其计算次数为2 n 该算法还存在一些缺陷，如：同一变量往往反复进基离基，因而迭代次数随问题规 模的增大而急剧增加，有时由于反复的迭代还会出现数据不稳定现象在实际问题 中，单纯形算法也会出现循环的现象嗍，为了避免循环，b l a n d 给出了反循环法 则1 2 7 ，勰】，k u h n 和q u a n d t 将关于选择列( 即换入变量的选择) 的不同算法进行了 比较【2 9 i ，结果表明在约束方程不多于2 5 个的情况下，全变量梯度法比非基梯度法 及最大增量法迭代步数少，并且收敛速度也快，但是由于非基梯度法具有非常简单 的重要优点，使其成为了最常用的方法上述的几种方法的不同点在于运用了不同 的策略选择换入基列和换出基列，但其本质相同，都是进行基变换使得其费用函数 能够得到改善 基线算法和对偶基线算法保留了单纯形算法的表格运算形式，使它具有单纯形 法易学好用的特点但其构思方法与单纯形法完全不同，基线算法是将费用函数作 为约束条件，把费用值口看成参数待定，通过计算给出费用值口的可行区域，然后 由口的界值来控制选择旋转元进行旋转，使得费用值口得到改善而对偶基线算 2 兰州大学2007 届硕士学位论文 法是基线算法的发展，它保留了基线算法的特点，只是在由”的界值来控铝4 选择旋 转元时，它所选择的旋转元每次旋转可同时改善最优值的上界和下界，是用“两边 夹”的方式逐渐逼近最优值，使其比基线算法迭代效率高，收敛速度快两种算法都 没有单纯形算法中的检验数行，都是利用界值u 来控制旋转元进行基变换，而且一 张基线表可以同时具有原始可行性和对偶可行性，但却不是最优解，这是单纯形算 法无法做到的但其本质与单纯形法相同，只是在选择基列进行旋转时采取了不同 的方法无论从理论上还是从测试结果看，基线算法在其运算机理、迭代次数、算 法稳定性等方面都较单纯形法有很大的改进【舯1 一个单纯形法发生循环的著名例 子( b e a l e ，1 9 5 5 1 3 1 j ) ，用基线算法只需两次迭代即可得最优解【3 2 】 由于基线算法具有操作简单、易掌握、迭代次数少、数值稳定性好等特点，我 们陆续将此算法推广到与线性规划相关的其它规划，文l 中讨论了用基线算法解 有界变量线性规划问题，交中用基线算法解决了完全分层多目标规划，较单纯 形法解此类问题而言，取得了更好的结果 因此，本文也将基线算法和对偶基线算法进行了推广，用于解决线性目标规划 问题由于线性目标规划自身具有的特点，我们将目标函数按照优先因素分阶段进 行讨论，并且构造了基线算法和对偶基线算法中没有的检验数行，给出了目标规划 的多阶段基线算法和多阶段对偶基线算法我们还对带有软硬约束条件的目标规划 进行了进一步的讨论，给出了具体的可行的方法最后，讨论了这两种算法的收敛 性，并编程与目标规划的单纯形法进行了比较，得到了满意的数值结果 本文的其余部分安排如下： 第二章基本概念及预备知识 第三章线性目标规划的多阶段基线算法 第四章线性目标规划的多阶段对偶基线算法 第五章带有硬约束的目标规划的讨论及算法之间的比较 第六章主要结论和进一步要做的工作 3 第二章基本概念及预备知识 2 1 线性目标规划基础 1 线性目标规划的基本概念 线性目标规划是线性规划的扩展，下面我们举例说明如何将线性规划演变成目 标规划 例：考虑下列线性规划问题( l p ) 鲥麓2 ( 2 1 ) ( 2 2 ) 问题的约束条件见图2 1 显然该( l p ) 问题的可行解域为空集，即没有可行解 存在然而，将问题做些修改，即把约束( 2 2 ) 式的前两个约束看作是资源约束，而 把后两个约束做为目标对于这两个目标来说，不一定非达到目标值( 7 和3 ) 不可， 4 兰州大学2007 届硕士学位论文 而是尽量接近它，在尽可能接近目标值的前提下，使原问题的函数值z 最大，这时 问题变成了是可解的且问题改写成 m i n p l ( w l i z l + z 2 7 i + 劬i z l + z 2 3 i ) + 恳( 一7 叠l 一2 勋) ( 2 3 ) l 缸l + 2 2 2 1 2 s z 2 4 i $ 1 ，勋 o ( 2 4 ) ( 2 3 ) 和( 2 4 ) 式中z 1 ，z 2 为泱策变量，只，恳表示优先级别因素，且p 1 b ， 表示县比恳具有绝对的优先权，即首先要保证b 级目标实现后，其次才能再 考虑恳级目标的实现w l 和w 2 表示权数，它的大小根据相应目标x l + 现一7 和z 1 + $ 2 3 在问题中的重要性而定 现引进目标的偏差变量矿和d 一，其中d + 为正偏差变量，表示大于目标值( 7 或3 ) 的数值，d 一为负偏差变量，表示小于目标值( 7 或3 ) 的数值，因而上式可写 成如下形式的目标规划问题 m i n p l w 1 ( 对+ d - ) + 耽( 砑+ 商) 】+ 忍( 商一对) ( 2 5 ) z 1 + 2 ：2 + d f d j _ - - x l + 勋+ d 2 - 一露 7 x l + 2 2 2 + 露一薅 3 x l + 2 x 2 $ 2 x l ，霉2 = 7 5 3 = 一 0 岔 时 + 一 才 一r 柚 = 矿溉吡 兰州大学2007 届硕士学位论文 2 2 基线算法及对偶基线算法的基本理论 1 基线算法的基本理论 基线算法是近几年来研究的一种解线性规划的新算法，因为每张运算表格对应 着一条基线而得名，它可以看作是单纯形法( 基点算法) 的发展 考虑标准型线性规划问题( l p ) 懈口= 口 ( 2 8 ) “ a x 薹： 其中，c ，。j 矿m ，b 矽，且不必要求b 0 ，n 是( 二p ) 的维数，m 是约束 个数( j 表示n 维欧几里得空间，如不特别指明，z j p + m 视情况可以是行向量 或列向量) x = 扛舻+ ”i a z = b ，z o ) 是仁p ) 的可行集x 是一个凸多面体， 本文假定c 0 ，并且原点不是最优解 把口看作参数，原问题可解释为在z 满足z 0 和约束方程组 ( 勾z = g ) 的条件下求参数”的最大值恒假设矩阵( j ) 中存在( m + 1 ) ( m 4 - 1 ) 非奇异子矩 阵b ，称b 为基，改写( 分为( n ，1 3 ) ，相应地改写霉为( 嚣) 其中。形，z _ 的分量称为非基变量，z b 尼“+ l ，z b 的分量称为基变量。于是方程组 可写成 以b 一1 左乘，得 z = ( ：) n 。n + b 。b ：l 心 o b _ 1 鲫+ 幻= b - g ) = 口+ 触 其中n ，卢舻卜卜1 ，令x n = 0 ，得z b = o + 励称点集 l 一 z = ( z ，b ) = ( o ，a + 跏) e j 妒+ ”i v r 为对应于基b 的基线( 2 9 ) 式的系数表称为基线表( b l 表) 7 ( 2 , 9 ) 兰州大学2007 届硕士学位论文 表1 基线表( b l 表) l x l vz b b b 。1 n日1q + 8 其中层叶l 为( m + 1 ) ( 仇+ 1 ) 单位矩阵 不失一般性，为了叙述方便，本文恒把正在讨论的基线表对应的方程组( 必要 的话可重新编号) 写作 嘶1 0 1 + 8 让z 2 + + 8 i j 十+ 在“t 卜1 z n 一1 + o n + i = 铫+ 绣移( = 0 ，1 ，m ) 其中z l ，z 2 ，z 。l 为非基变量，z n ，z n + l ，x n - 1 4 r 。为基变量 b l 表的特点是它有n 一1 个非基变量和m + 1 个基变量( 对应着系数矩阵 的m + 1 个单位向量) ，且右端含有作为参数的目标函数值口，并且没有单纯形表中 那种固定的检验数行 每个巧= 0 ，j 1 ，n + m ) 是( l p ) 的一个约束面当为基变量时， 称z ，= 0 是基约束面，当为非基变量时，称劫= 0 为非基约束面 令z ；0 ，如果线性不等式组g 口= n + 励0 对 有解，则其解集是一个 区间i = k ，- 】或( 一o 。，- 】或【马+ o 。) ，此区间称为可行值区间，其端点墅，可叫做 在该基线表的极可行值，这时称基线l 和基线表l 是可行的易知。对任意口i ， 点z = 0 ，幻) = ( 0 ，口+ 励) x 是可行点( 因满足茹0 ，且满足约束方程组) 对每个i o ，1 m ，当屈0 时，由啦+ 触= 0 确定一个界值吨= 一啦腮 和基线l 上的一个基点= ( x g ，z b ) = ( 0 ，口+ 卢坼) ；当屈= 0 ，o t 0 时，约定基 点为无穷远点，当成= 啦= 0 时，为不定的 如果是n 兰o ( n 。+ 风 ) = 0 的k 重根，称饥是k 重界，特别当k = 1 时， 称饥为单界，基线上的k 重基点算作k 个基点，k 2 时，k 重基点称为退化基点 于是每张b l 表对应着一条基线和该基线上的m + 1 个基点 把x 投影到舻上，基线l = 仁r 衅mf 甜= 0 ，$ b = q + 伽； 兄) 就是 一1 ) 个非基约束面o = 0 的交线，而基线上的( m + 1 ) 个基点就是其余( 仇+ 1 ) 个基约束面与该基线的交点 如果也，一j 是t ，在基线l 上的可行值区间，点茁。= ( 知，x b ) = ( 0 ，o + 脚 和= ( 。，z b ) = ( 0 ，a + p 豇) 都是x 的极点( 即l p 的基可行解) ，并称为下 极点，o ”为上极点线段，z “】是x 的一条棱边 对每个i o ，1 m ，令啦+ 劬0 若反 0 解得u2 一啦展，称= 一啦风为下界；当反= 0 时， 若啦 0 ，把仇= + o o 定义为它的上界或把地= 一0 0 定义为它的下界，若o q 0 ， 把饥= + o 。定义为它的下界或把仇= 一o o 定义为它的上界；若风= 啦= 0 则对 8 兰州大学2007 届硕士学位论文 应的界值v i 是不定的易知，基线表是可行的，当且仅当它的最大下界不超过它的 最小上界 若佻= 一啦屈是上界且第i 行的每个系数啦，0 ，j = 1 ，2 竹一1 ，我们称q 为硬上界若不存在硬上界，每个上界就都叫做软上界若存在硬上界，小于最小硬 上界的上界叫做软上界，按定义可能有些上界既不是硬上界也不是软上界( 如此上 界大于最小硬上界，且该上界所在的行中存在小于零的系数) 对于每个软上界v i ， 第i 行中至少存在一个负系数毗j 0 类似地，若姣= 一啦反是下界且第i 行的每个系数啦j 0 ，j = 1 ，珏一1 ， 则称忱为硬下界若不存在硬下界，每个下界都叫做软下界若存在硬下界，大于 最大硬下界的下界叫做软下界，同样也可能存在有些下界既不是硬下界也不是软下 界同样对于每个软下界钆，第i 行中至少存在一个负系数a o 0 如果界值钝( 有限) 是b l 表的硬上界，那么对￥霉x 有 啦l 霉l + + a i j x j + 啦m i ) x n 一1 + f i g n + i = 啦+ 屈口0 ， = 0 ，1 ，2 ，m 所以口一o 屈( 屈0 ) 牟= t ，= c 譬一啦屈= 仉 由此可得 定理2 1 【2 1 】若b l 表可行且存在有限的硬上界，那么l p 存在最优解( 最 优值有限) ；如果b l 表可行且最小上界钆是硬上界，则地= v 是l p 的最优 值这时矿= ( z ，z 占) = ( 0 ，血+ z v ) 是三p 的极点最优解如果b l 的可行上 界v i = + o 。，则l p 无界如果b l 表的最大硬下界大于最小硬上界，则l p 无可 行解 今后我们恒假设基线表没有一o o 硬上界( 因而也没有+ o o 硬下界) ，否则l p 无可行解 如果以基线表中的系数啦f 0 为主元像旋转单纯形表那样旋转基线表，得到 的仍然是一张基线表，如果得到的基线表是可行的，称0 为可旋元下面我们 给出基线算法的相关基本理论 定理2 ，2 ( 2 4 1 设当前的b l 表的可行值区间是注，碣，若当前b l 表存在软上 ( 下) 界，则可( 型) 是最小( 大) 软上( 下) 界 证明：【! ! ，- 】是( b l ) 表的可行值区间，因此型是最大的下界，移是最小的上界， 可必是软上界，否则( b l ) 表中对应可的行无负系数或可不小于最小硬上界，后者 是不可能的，而前者说明当前( b 功无软上界，与题设矛盾故移必是软上界同理 可证明堑是软下界 定理2 3 【3 2 】如果基线表可行，那么它的最小上界行的每个非零系数都是可旋 元 9 兰州大学2007 届硬士学位论文 定理2 4 1 3 2 1 如果基线表可行，那么以它的最小软上界行的负可旋主元旋转，极 可行值不减，特别地，如果基线表的上极点不是退化的，那么以它对应的软上界行 的负可旋元旋转，极可行值将严格增加 2 对偶基线算法的基本理论 对偶基线算法是从基线算法发展而来的一种解线性规划的新算法，相对基线算 法，它具有更高效的迭代速度 如果基线表存在硬上界，称该基线表是对偶可行的 定义2 1 设基线表对偶可行，讯是硬上界( 可以为+ o o ) ，q 是软上界( 仇 忱) ，对应行的方程分别是： 口k l x l + + a k j z + m ( n 1 ) 1 + n 础= o t k + 风u 啦! z l + + a 缸+ 啦( n t ) x n l + x n + i = a b + 屈” 其中。姆0 ，；i ，l 一1 ，凤0 6 a , = 0 时口k o ) ，m i 挖 毗i ，啦o 1 1 0 如果 = r a i n 一鲰。o “l 伍妇 o ，= - a k j 则称啦j 0 是第i 行对第k 行的保硬主元 由上述定义可知，如果基线表存在硬上界和软界，那么每个软上界行都有保硬 主元下面我们讨论在极大化问题中选取保硬主元的两种具体方法 仍设是基线表的最小硬上界如果 儡+ 屈 0( 2 ，1 0 ) 称v i = 一啦屈是错位界叩= 啦+ 屈叫做错位界v i 的错位值，错位值总是负数 由( 2 1 0 ) ， 当岛 镪，错位界螺是大于魄的下界 当屈= 0 时，必有啦 0 ，按约定错位界地= 0 0 是大于的下界或错位 界饥= 一o o 是小于的软上界 可见错位界只能是软上界( 小于最小硬上界) 或大于最小硬上界的下界由此 不难得出 定理2 51 2 5 】设基线表对偶可行，那么 ( a ) 基线表是最终最优表当且仅当它没有错位界 ( b ) 如果基线有错位界是硬下界，则l p 无可行解 1 0 兰州大学2007 届硕士学位论文 定理2 6 嘲如果让是软上界( v d ，以保硬主元 0 ，则 其中 知= m i n - a k 。6 i 啦。 o ) = 一n 蜥o 巧 对偶基线算法的基本作法是选择最小软上界行对最小硬上界行的负保硬主元 进行旋转，对于同时具有原始可行性和对偶可行性的基线表，由定理2 4 和定理2 6 可知，选择这样的负保硬主元进行旋转后，得到的基线表仍然同时具有原始可行性 和对偶可行性，且每次迭代可以同时改善最优值的上界和下界，用“两边夹”的方 式逐步逼近最优值，而单纯形法及基线算法仅从一个方向逼近最优值，因此对偶基 线算法比单纯形法及基线算法的迭代效率高 1 1 第三章线性目标规划的多阶段基线算法 3 1 极小化问题中的基线算法理论 在讨论线性目标规划的多阶段基线算法之前，为了便于运用基线算法对目标规 划进行求解，我们先给出求极小化问题的线性规划的基线算法理论 考察下列线性规划问题 r a i n 静2c z “ a z 蓁： 上式中的符号意义与2 2 节中对式( 2 8 ) 的说明相同将函数值口作为参数，与 费用函数构成新的约束条件，把该约束的系数放在基线表的第0 行 在极小化问题中，我们通常只使用有限软下界行的负可旋主元进行旋转若v i 为软下界( 有限) ，并存在 0 是第i 行的负可旋主元，那么以d t j 为主元旋转 后他将变成上界因而b l 表的极可行值可能减小，并称这样的软下界为可反软下 界下面我们证明在极小化问题中基线算法基本理论依然成立 如果界值吨( 有限) 是b l 表的硬下界，那么对垤x 有 啦l 。1 + + + n ( n 一1 ) x n 一1 + “= 啦+ 展 0 ，i = 0 ，l ，2 ，m 所以甜一n 屈( 觑0 ) 幸= 净t ，= c z 一o q 屈= 由此可得 定理3 1 若b l 表可行且存在有限的硬下界，那么l p 存在最优解( 最优值 有限) ；如果b l 表可行且最大下界是硬下界，则让= v 是( l p ) 的最优值 这时矿= ( x n ，z b ) = ( 0 ，口+ 卢p ) 是l p 的极点最优解如果b l 的可行下 界= 一o o ，则三尸无界如果b l 表的最大硬下界大于最小硬上界，则l p 无 可行解 定理3 2 如果基线表可行，那么它的最大下界行的每个非零系数都是可旋元 证明；设v i 是最大下界，由于基线表可行，让= 一a f 岛满足 啦+ 岛= 0 且啦+ 尻钝0t i 以0 为主元旋转基线表后，右端变成 1 2 兰州大学2007 届硕士学位论文 正+ 碰 = ( 啦一啦。巧8 a ) + ( 反一屈。纡“扣 = ( c h + 展口) 一( a t + 屈t ，) o 巧叼 i + 虞w = ( 啦+ 屈口) 当口= 婊日寸，嘶+ 屈饥= 0 + 鹾驰= ( o l t + 成峨) 一( 啦+ 房地) o 巧口玎 = 啦+ 反q 一0 = 啦+ 风研0 即+ t ，20 有解t ，= q 按定义旋转后得到的基线表可行故最大下界行 的每个非零系数都是可旋元 释 定理3 ，3 如果基线表可行，那么以它的最大软下界行的负可旋主元旋转，极可 行值不增，特别地，如果基线表的下极点不是退化的，那么以它对应的软下界行的 负可旋元旋转，极可行值将严格减少 证明：设也是最大软下界，由于基线表可行，则让= 一啦壤满足 啦+ 岛叻= 0 且啦+ 岛0t i 以 一爰 同乘( 一1 ) 屈( 屈+ a 岛) = 辛n t 屈+ a o 危 o 风+ a 啦屈 停啦 一静 铮啦+ 反他 o 陬= 一爰) 兰州大学2007 届硕士学位论文 得出矛盾因此，极可行值不增。即：s 仇 当取等号时，即= 时，可得 一口t 风= 一n t 反= = 专 仇= 地 所以下极点退化，与条件矛盾故有下极点不是退化的基点时，极可行值将严 格减小 孝 3 2 线性目标规划的多阶段基线算法 定义3 1 我们称问题( 2 7 ) 为线性目标规划的典型形式，如果该问题中不包含 硬约束条件，没有涉及松驰变量、剩余变量和人工变量，而且每个目标都含有负偏 差变量和正偏差变量 下面我们考虑典型形式的线性目标规划问题 3 t j a z + i d 一一时= 6 l 为d 一，矿0 上式中，j 为m ) 维单位距阵，其他符号的意义与2 1 节中对式( 2 7 ) 的 说明相同像目标规划的单纯形算法一样，我们首先要给出问题的初始表，我们把它 称为目标规划的初始基线母表( b l 表) x b卫1 g 。 d id 二d 旗 b z b la l l q i n 哆l ( 叶1 ) ，- a l ( n + m )0 1 ( n 十m + 1 ) a l ( n + 2 m ) b 1 i r , b 2n 2 l0 2 n a 2 0 , + 1 ) n 2 ( n 训啦( 卅m + 1 ) 幻( n + 圳 幻 ： ：，： x b m8 m l啦赫嘶+ 1 )o m 扣+ # 0o 叫r + 冲1 ) n 钆“+ 2 嘲 k 只加1 1 伽1 n w i ( n + i ) 叫l ( f i + m )伽1 ( 咖+ 1 ) 1 ( 仆+ 加) 钉l 足址堙1 钳加 铆2 ( n + 1 ) t f j 2 似+ f 帕 t v 2 ( n + m - l - 1 ) 钮2 加- l - 2 m ) 忱 ： ： 靠w k i - d ) k n t 咏( 1 )- t 加+ ，1 ) w n ( n - h m - l - i ) 钍w ( n + 2 m ) v k 1 4 矿 时 + 扩 一 r 。腻 = 矿n廊 兰州大学2007 届硕士学位论文 在线性目标规划中，我们将目标函数作为约束条件，构成k 个新的约束条件， 即i 1 ，2 ，r e + k ，j l ，2 ，n + 2 m ) ，形成( m + k ) ( n + 2 m ) 维的初始 基线母表，它与线性规划单纯形表不同之处在于按优先级顺序排序的多级目标函数 行这些行中右端数值”i 咏为对应于优先级p l ，玖的各级目标函数值，在 这里作为参数待定叫幻忙= 1 ，k , j = l n + 2 m ) 为目标函数中各级目标的偏 差量的权系数，( b l 表) 用矩阵形式表示为 i x zd一 扩b ix b a1一ib po叫一叫+t ， 式中有巧，j 1 ，n ) ，最，k 1 ，：， ，钟一，伽+ 分别为k 级目标中相应 负、正偏差向量的权系数矩阵( k m 维) ，与式( 2 7 ) 中给出的 t t ) - - ，缸，+ 相同将多 级目标函数行中对应基变量列的元素变成零后，这些目标函数中的系数便称为检验 数，各级目标函数行便称为检验数行变换后其矩阵形式表示为 x z i d 一舻b 1 a li b p 一伽一a0叫一+ 叫+ 一坩一b 由于目标规划中含有优先因素p k ，k 1 ，k ，即在目标规划中的目标具有 优先级别之分，我们在求解过程中，必须按优先级别的顺序依次对各级目标函数作 最优化计算目标规划的多阶段基线算法就是基于其目标具有优先级别之分的特点， 将目标函数分成个阶段，然后分阶段利用基线算法对目标规划进行求解因此， 我们可把多级目标函数按照每一级分开化成k 个独立的目标，将日级目标函数 ( 此时暂不考虑易，b 最级目标) 与约束条件构成一个特殊的线性规划，称为单 目标线性规划，便可利用线性规划的基线算法求出最小值”，此时，p 1 级目标函数 达到最优，用同样的方法依次考虑恳，只最级目标函数，分别求得w ，w w ， 我们把v = ( w ，w ，垤唆) 称为最优达成向量，它反应了各级目标实现期望值 的程度 同时，在对较低级别的目标函数进行最优化计算时，必须不破坏其较高级别的 目标函数行的最优性即当某级目标已经达到最优时，目标函数行中对应的非基变 量的检验数必大于零，则该大于零的元素对应的列在以后级别的计算中，不管其检 验数是正数还是负数，都不再作为换入基列进基，故有以下消除规则存在 定理3 4 【3 纠( 消去定理) ：从第1 级( 阶段) 开始，如果某级检验数已达到最优， 则该级目标函数行中对应非基变量的检验数严格大于零，这些大于零的元素对应的 列在以后的计算中不再作为基列入基，可从单纯形表中消去 兰州大学2007 届硕士学位论文 综上所述，我们给出线性目标规划的多阶段基线算法 s t e p l 列出问题的初始基线母表，令k = 1 ，转s t e p 2 ； s t e p 2 将k 级目标函数行中对应基变量列的元素变为0 即得k 级目标函数 的检验数行，转e p 3 ； s t e p 3 考察该检验数行中的所有负元素，选择其中最小者为旋转元，像旋转 单纯形表一样进行旋转，转s t e p 4 ；若不存在负元素，则该级目标函数值已达最优， 计算口。+ l + 月k + 1 0 ，记嵋= 一。概+ 1 岛叶1 ，并用馆替换表中的珧，将该检验 数行中所有大于零的元素对应的歹l j 删去，并毋4 去该检验数行，转s t e p 6 ； s t e p 4 求解b = 啦+ 展强0 ，“= 1 ，2 ，m + 1 ) ，算出当前基线表对应的可 行值区域孤匝，_ 】，若型不存在，则无解，否则令打m g 一啦屈，屈o 卜= 一唧纬， 转s t e p 5 ； s t e p5 若第p 行中存在负元素，取最小者作为旋转元像旋转单纯形表一样迸 行旋转，转s t e p 4 ；否则，着第p 行中无负元素，型为最优解，令w = 型并用w 替换 表中的v k ，将第p 行中所有大于零的元素对应的列删去，并删去第p 行，转s t e p 6 ； s t e p 6 若k = k ，则当前解为最优解，否则，置k = k + 1 ，转s t e p 2 下面用一个例子来说明此算法的运算过程 例1 ：m i nv = p , ( d t + 对) + p 2 喀+ p 3 对+ p 4 ( d i + 2 町) s t z l + x 2 + d t d = 3 0 2 + d i 一避= 1 5 2 x l + 3 x 2 + 靠一对= 1 2 0 z 1 + 2 x 2 + d i 一对= 4 0 x l ，x 2 ，町，茚0i = 】，2 ，3 ，4 解：构造起始基线母表 x sx l x 2d i -