《确定线性规划全部最优解的方法.doc》由会员分享，可在线阅读，更多相关《确定线性规划全部最优解的方法.doc（8页珍藏版）》请在三一文库上搜索。
1、第35卷第1期数学的实践与认识2005 年 1 丿 MATHEMATICS IN PRACTICE A ND T HEORYVol. 35 No. 1Jan., 2005确定线性规划全部最优解的方法薛声家，左小德(洗南大学管理学院广东 广州510632)摘要：便用凸多面体的衣示定理导出了标准型线性规划垠优解的一般农达式并某单纯形法,给出般 优解唯一性条件以及当唯一性条件不满足时求出全部最优解的计算步骤，同时附右数值例子.关键词：线性规划：凸多面体;最优解：单纯形法一般说来，实际上的经济管理问题所形成的线性规划的最优解给出了该实际问题的最 佳实施方案.当线性规划冇不止一个最优解时，便存在无穷多个
2、最优解，求出线性规划的多 个最优解是件很有意义的工作，因为它可以提供更多的最优方案供决策者选择.目前虽有 不少文献对线性规划无穷多个最优解的情况进行了讨论，但有些存在错误和缺陷"4,另一 些则讨论得不够完整、深入，缺乏详细有效的求解方法.本文使用凸多而体的表示(分解)定 理，导出了标准型线性规划最优解的一般表达式，给出确定全部最优解的计算步骤，并附有 数值例子.1线性规划最优解的一般表达式考虑标准型线性规划问题：Max z = c x(SLP) 4 s. t. Ax = I)、x > 0其中，4为m X n阶矩阵,c和篇为维列向量为zn维列向量，设rank(4) = m <
3、; n.(SLP)的可行集D二x Ax = /人% > 0为一凸多面体，文献引给出了如下的表示定 理：定理1设D = x Ax= 6, % > 0非空，则它的极点集非空且包含有限多个点 %2, ，,而且的极方向集非空当且仅当无界.若无界，则它的极方向集包含有限 个向量d d，/此外，兀WD当且仅当兀可以表示为汽 ，J的凸组合与心，/的非负线性组合之和，即k/x -工 Nxl + 工 PjdJ( 1)i= I;= 1k其中，工入二 1,入 N 0, i = 1, 2,，k; Xj > 0, J = 1, 2,，/.收稿日期：2001-07-03基金顶目:暫箱鋤1由Electro
4、nic Publishing House. All rights reserved, http:/1期薛声家，等：确定线性规划全部最优解的方法105设(SLP)有最优解，则必存在基最优解(最优极点)，记(SLP)的最优极点集为/ i e /另外，由(1)式不难看出,(SLP)有最优解当且仅当对于所有的极方向/有/三o.设/为(SLP)的最优解，若D的某极方向/满足c%二0(即应与c正交)，则易见，对 于任意的入N 0,/ +入刃都是最优解.我们称满足二0的极方向为最优极方向记 (SLP)的最优极方向集为£) e J,则有：定理2若(SLP)的最优解集非空，则最优极点集非空.而且，最优
5、极方向集非空当且 仅当最优解集无界.此外，%为(SLP)的最优解当且仅当咒可以表示为最优极点的凸组合 与最优极方向的非负线性组合之和，即x = 1 入咒'+ 工 口 d，(2)©j&J其中，工入二1,入二0W / ； w > 0, J e j.iWl证明 记(SLP)的最优值为若尤可表示为(2)的形式，则咒WD且cG二/ ,因此 %为最优解.反过来，设久为最优解，为证明(2)式，只需证明(1)式中有:对于仟意iW /有入二0和 对于任意)住丿有闪二0.用反证法.反设存在h比I使& > 0,则cT xh < z* ,因此exh <辰*,从
6、而2* = ex -工 Xc x + £工 cT x1 (因为 jCT(P 三 0)*= i；= i<= iV工入2= z 矛盾i- I/同样，若反设存在沁丿,使门>(X则/< 0,因此p.cTdl< 0,所以刀吹 < 0,从7= i而k/kr =刀入/+为吠卍< 刀入/*= 1QGk<工入/ = Z* 矛盾(=1定理2证毕.2最优解唯一性条件和确定全部最优解的计算步骤假定我们用单纯形法求解得(SLP)的基最优解不妨设相应的基指标集为二1,2,，m,贝lj相应的典式为:nz - z + 工(Jxj(3)j= 1n(4)x i +1 aijXj
7、 = bg i = 1, 2, , mj= 1xj 05 j = 15 2, , n(5)©宜42013 China Academic Journal Electronic Publishing House. All rights reserved, http:/mmz =0)= cj -工 ado, y = n? + 1, ni- I心 Ix* = (Zh,，/”，0,，0)T由于已达到最优，故er < o,y =加+ 1,*.使用式子(3)可以证明如下定理.定理3/为唯一最优解的充分条件是所有的非基变量的检验数5 < 0.若/非退化，则上述条件也是必要的.证明 设所有
8、非基变量的检验数4 < 0,任取一异于/的可行解第，若心=0Q w /, 则由(4)式可得尤二/之矛盾.故存在h左/«,使xh > 0,从而(Jhx h < 0.使用(3)式计算第的目标值nz = z* + 工 OjXj < z + (ThXh < z* j= 1由此可以看出是唯一最优解.反之，设/是唯一最优解且非退化，即厶0, i e Ib若存在人弋/，使d二0,则我 们可构造如下的可行解元：Xi =l)i i 已 In%A =a闪=o.j w /，j由于/儿> 0. i Ib.故8 > 0充分小时，壬为可行解，且x x* .元的冃标值为z
9、 - z +1 (Jjxj = z + 0? 9 = zj =1即壬也是最优解.这与：/是唯一最优解的假设矛盾.因此必定有所有非基变量的检 验数s V 0.证毕.若唯一性条件不满足，即存在某非基变量庆的检验数口= 0.则可能出现下而两种情 况：情况1:对于心1, 2,，叫a.< 0.这时，根据极方向的代数特征曰，我们可以得到 一个极方向，其分量为di = 一i E： I a< (b = I,(6)d =0, j 总"，j 工 kmI大I为cTd - ck - 1 aikCi二G = 0，|大I此，所得到的极方向(I是最优极方向.工I情况2：存在i e /,使-> 0
10、,则以-为入基变量，使用8规则(最小比值规则)fff0 = in iii I)11 aik (iik > 0lG/j确定出基变量.若B> 0,则转轴后可得到新的基最优解;若8= 0,则转轴后虽然得到 了新的基，但基最优解/保持不变.下面给出求所有基最优解和最优极方向的计算步骤.步骤1：使用单纯形法解(SLP)若在最优单纯形表中所有非基变量的检验数q < 0, 则(SLP)有唯一最优解；否则进入步骤2.锣勦2魁碱滩的口2 唧?脱咚舸磧购列气甌 极方恸害则进廖骤ghttp：/步骤3：以为入基变量，使用8规则确定出基变量，转轴后可得到新的基最优解或原 基最优解的新最优单纯形表.对每
11、个最优单纯形表，重复进行步骤2和步骤3,直到处理完所有满足«= 0的非基变 量Xk.由于各个基最优解都是两两和邻”的，所以在冇限步后（必要时可以使用避免发生基循 环的方法），可找出（SLP）的所有基最优解和所有最优极方向，因而确定了（SLP）的全部最 优解.例：考虑下列线性规划问题max z 二一 x I + 3x3 一 %4 1.X 1- X2+ X5=3-3x1 + 2%2 + 9x3 + 2x 4-2x6=22咒2一兀6=24x1 + 3% 2 + 5% 3+ X5-%7 = 4使用单纯形方法求解可得最优单纯形表（表I）表1Cj-103-1000e5X IIbX 1XI*3IX
12、5兀6X70X55|1|0001-1053尤32-0. 333010. 2220000XI17-4. 667001. 1110-410X2201000-106000-1.667000由表1可以得到基最优解（0,2,2,0,5,0,17）卩,最优值z* = 6.由于非基变量兀6的检验数二0,且各"三0,根据（6）式便得到一个最优极方向/二 （0,1,0, 0,1, 1,4） r.在表1中还有非基变量 I的检验数6二0.且各仏I中存在正元素，令咒5出基兀1进基, 转轴后得到另一个最优单纯形表（见表2）表2ci-103-1000CHXBbX 1X2X3X4兀5X6XI-1X I510001
13、-103兀33.6670010. 2220. 333-0.33300XJ40. 3330001. 1114. 667-8.66710XI2()1000-106000一 1. 667000表 2 给出了另一个基最优解2 = （5,2,3.667,0,0,0,40. 333）7.由于非基变量检验数二0,且所有6 < 0,因此得到另一个最优极方向/二（L1,0. 3观 淤珂垃貓严牠醫喙袈男曲牝訥罷潮劉骄摘畤绸轉,$敌讦囁卫切：/本例最优解的一般表达式为：x = Av 1 + 其中 0三 A< 1, pi, P2> 0.参考文献：1|钱颂迪等.运筹学(修订版)M.北京：清华大学出版社
14、,1990,23-25.2赵风治.线性规划计算方法M.北京：科学出版社，1981. 55-60.| 3| Bazaraa M S. J arvis J J. Sherali H D. Linear Programming and Network Flows. 2",-E(htio训 M | . John Wiley, New York. 199Q 6070.|4|郑义建.线性规划问题最优解集的结构与仅有唯-最优解的充分条件J.应用数学与计算数学学报.1992, 6( 1): 4246.|5|张新辉仃无穷多最优解线性规划问题J.运筹与管理.1995. 4( 1): 1-4.|6|李军.
15、线性规划无穷多最优解的讨论J.运筹与管理.1999. 8(1):87-92.|7|徐增坤.数学规划引论M|.北京：科学出版社.20()(). 7-9.An Approach for Determining all OptimizationSolutions of Linear ProgrammingXUE Shengjia, ZUO Xiao-cle(Management College Jinan U niversity, (juangzliou (Guangdong 51 ()632, China)Abstract:With the represent at io n theorem of
16、 co nv ex polyhedro n. t his paper derives thegeneral expression for optimal solutio ns to standard linear program m ing. Based on t he si in pl ex inetho(L w e give the unicjueness con (lit ion of optimal solution and t he coni putational proceduies to find all optimal solut ions if the uniqneness oondit ioin is not satisfied. A numerical exam pie is also given.Keywords： linear pro gram mi»g： co nv ex poly h edr on； opt imal solut ion； si mplex method© 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved, http:/