变量有广义界线性规划的叠累单纯形法.pdf

第卷第期经济数学
年月
变量有广义界线性规划的叠累单纯形法
梁远信
广西经济管理干部学院基础课部南宁
摘要本文建立变量有广义界线性规划一个新的转抽算法,称之为受系单纯形算法,新算法具有三个主要
特征对于检验数为“坏”的非基变量。,进行一轮子转轴运算,使得。进基,转轴中具有“好”的检验数的变
贵始终保持“好”的检验数进基的子转抽所产生的基既不是原始可行基,也不是对偶可行基,但子转抽结
束时产生的基是原始可行的目标函数值在整个转轴运算中是单调下降,从而算法可有限步终止
关键词广义界线性规划叠累单纯形法
对于中小型线性规划,的单纯形法是十分有效的求解方法,遗憾的是单纯形法
是非多项式时间算法,川借助于非线性规划的思想建立了一个多项式时间的内点
算法,内点算法和单纯形法各有利弊,另一种偿试是借鉴于单纯形法转轴的思想研究转轴型的
多项式时间算法〔‘一’〕,这无疑是一项有重要意义和高难度的工作,其中一种广泛的研究途径是
放松对可行性的要求队’,“〕然而这些转轴算法一般条件下仍不是多项式算法困,但在较强的条
件下,可建立转轴型的多项式算法队〕年和帝给出了标准型线性规
划的一个新型的叠累转轴算法,该算法最大特征是保证“好”的检验数在迭代中不被破坏,转轴
中的基是可行和不可行的交借列本文讨论实践中大量出现的有广义界线性规划,利用
和的思想在原模型上提出一个新的更广泛的叠累转轴算法通过有限次
迭代完成问题的求解文中给出了算法的实例求解
叠累单纯形法
本文讨论如下变量有广义界的线性规划
二,簇簇,
其中任”月,八,‘二,⋯,,,,,⋯,。,,⋯,人,,⋯,
,,“,任一,不妨设,“,中至少有一个为有限实数,且设点满
足,如能分解为
,,,二,、,,。一,一一’材几了一一,,
称和分别为的基阵和基解又如几镇匀簇“。,称为基可行解,为可行基,如再
有几。。,称为非退化的基可行解设为一个给定的可行基,为相应于基
的基可行解,且孟几,又,则任意满足的,有
每, 一
,,一
收稿日期一一
经济数学第卷
二。一一。一一‘。一一,、,二一。二一’一艺,一一万,,一,
夕任了

其中,。玄丫一‘,,⋯,。称为变量,的检验数,丫一’,。,二,⋯,,马
为的列,“,为的列
定理设为相应于基的基可行解,且乳九,失,如镇,任称,有
好的检验数。,任称,有好的检验数,则为的最优基解。
对于违返最优性条件的,构造新的满足的点

一哎对十△,一’,。一瑕
夕,△,夕, 一,,。一乙△
、了,〔,
如按单纯形法川的进出基规划转轴,会使好的检验数变坏,增加计算量。本文的转轴规则
以保证好的检验数不变坏为基本准则,为简便,下面直接给出本文转轴算法,其性质将在下一
节分析。
算法步骤
步骤任取初始基可行解,使,,,几,,,夕一‘一五刃盗
一“,成‘荪弃,形成如下单纯形表
表算法迭代的一般表格
材
一’一‘
七‘一‘一‘‘忍一,一

步骤如镇,任,,〔,则当前为的最优基解,停否则取
任,,或任,几,记。
步骤选出基变量气计算
叹一几二一几
,—￡、, 全“一二丁一一
￡矛‘少如
“一叹气一二
十,—勺