Gilmore-Gomory算法避免产生循环的迭代规则

D0I:10.13374/j.issn1001-053x.1985.01.023 北京钢铁学院学报 1985第1期 Gilmore-Gomory算法避免产生 循环的迭代规则 数学第二教研室李宗元 摘要 分式规划在管理模型中时常遇到，而且在一般情况下变量个数很多。Gilm ore 和Gom ory提出一种算法1]，将分式规划用变形的单纯形法来求解。 本文论述了Gilm ore-一Gom ory算法在迭代过程中有可能产生死循环，从而 造成计算失败。为克服这个缺陷，本文给出了一种避免死循环的迭代规则，使该算 法臻于完善。 分式规划的约束是线性不等式组或线性方程组，其目标函数为两个线性函数之比，故分 式规划模型的标准形式为： minf(x)=pTx+a q Tx +B Ax=b (1) s.t x≥0 其中：设计向量x=(x1x2…xn)T 系数向量p=(p1p2…pn)T g=(g192…qn)T 约束矩阵A=(a11)i=1,2…m影j=1,2…n;a,B为常数。 若使设计向量x增加一个分量xn+1,且令xn+1=1,或等价地，增加约束： xn+1≥1，Xn+1≤1 又使系数向量P,q分别增加一个分量：Pm+1=-a,9。+1=一B,则(1)中目标函数可 消去分子与分母的常数项。 基于上述讨论，分式规划模型可以不失一殷性地表示为： miaf(x)=(x)-Cux Z:(x)C:Tx Ax=b (2) s.t 1x≥0 其中：X=（x1X2…xn)T C1=(Ci1c12…c1n)T C2=(c21C22…C2n)T A=(a1y)i=1,2…m,j=1,2…n。 87

北 京 钢 铁 学 院 学 报 第 期 一 算法避免产生 循环的迭代规则 数 学第二 教研 室 李宗 元 摘 要 分 式规 划在管理 模 型 中时常遇 到 ， 而 且 在 一 般情况 下 变 量 个 数很 多 。 和 提 出一 种 算 法 ‘ ， 将分 式规 划用 变形 的单纯 形 法 来 求解 。 本 文论 述 了 一 算法 在迭 代过 程 中有可 能产 生死 循环 ， 从 而 造成 计算失 败 。 为克服 这个缺 陷 ， 本文给 出 了 一 种 避 免 死 循环 的迭 代 规则 ， 使该 算 法 臻 于 完 善 。 分式 规划 的约 束是线 性不 等式 组或线 性方程 组 ， 其 目标 函数 为两个线 性函数之 比 ， 故 分 式 规划 模型 的标准形 式为 卫 日 二 》 其 中 设 计 向量 … … 系数 向量 … … 。 … … 约束矩阵 ， 二 ， 一 ， 二 若 使设 计 向量 增 加一个 分量 。 十 ，， 且 令 。 ， ， 二 ， ， 》 ， 又 使 系数 向量 ， 分别增 加一 个 分 量 。 十 ， 二 一 ， 消去分子 与分母 的 常数 项 。 ” · ‘ · ， 日为 常数 。 或 等价 地 ， 增 加 约 束 ， 一 日 ， 则 中目标函数可 基 于 上述讨 论 ， 分式规划 模型可 以 不 失一 般 性地 表示为 二 聋 ， ‘ 乙 气 一 二 其中 ， … … ， … … ， 。 … … 。 ， ， … … ， ， DOI ：10．13374／j ．issn1001－053x．1985．01．023

本文以模型(2)为研究对象，并约定：在约束域R={x|Ax=bx≥0}上，目标函数中 的分母z2(x)恒为正。 分式规划管理模划放其它馍型中广泛应州，今学例： 例1.露天金属矿矿石采掘正作量作业计划模型：： 某金属矿矿体由三个露天矿开来，矿石分为三种茶本类型：标准型；难选型；极难选 型。经验及论分析表明：难选型矿石占混合矿石的百分率对选矿过程的影响最为主要，故 需针村该矿的县体情况，使这个百分率尽可能稳定（即与计到规定百分率的偏差最小）。 这就要对作业班采掘工作量进行合理安徘。 以第i个采工面向选厂提供的矿石总至Y,(=1、2…ǜ)为设计.：量，问采掘工 作量作业计划的优化溴型如下： m i n 5.t:①产量约束： 三V1≥A。(A。-计划产量) KA>三V≥KAk(k=3,3) V,'≤V1≤V,”(i=1,2…n) ②品位约束： |a:-aoc|≤△c ③各类矿石百分率上下界约束： 是VW K2≤- ≤K11(j=2,3) V, 1■1 ④非负约束： V,≥0(i=1,2…n) 说明：n一露天矿采矿工作面数： V,1一由第i个工作面向选厂提供的第j种矿石量（为下，的线性函微）.j=1,2,3, 别代表雄选型；被难选型和标准型； K。1一开采和矿石总量中难选矿行刷计刘百分率多 A。k-一第k个露天矿(k=1,2,3)的计划产量， Kx-一第k个露天的作业不均衡系数； nk一一第k个露天矿的工作数； V,'一一第i个工作的最低允许运出量多 V,”-一第i个作电铲的最大可能生产诈力J: ac,aoe一分别代枝入选混台矿石中成方c的计算含避（为V,的线性的裁)与计划含 88

本文以模型 为研究 对象 ， 并约定 在约束域 二 二 》 叶 上 ， 目标 函 数 中 的 分母 恒为正 。 分式 规 划在 管 理模 到 及其 己棋 型 中厂 一 泛应 用 ， 今举一 例 例 露 天 金属矿矿石采掘工 作量作业 计划 模型 泛 二 某 金属矿 矿 一 体 由三个露天矿 开来 ， 矿石 分为三 种基 本类型 标 准型 难选 型 极 难选 型 。 经 验 及 理论 分析 表明 难选 型矿石 占混合矿石 的百 分率 对选 矿 过 涅的 影 响最 为主要 ， 故 需针 对该 矿 门 具体情况 ， 使这个百 分率 尽可 能稳 定 口与计 ’ 规 定 亡 ‘ 百 分率 的 偏差 最小 。 这 就要 对 作业 班采 掘工 作 量进 行 合 理安徘 。 以 第 个 采 口 一 工 千自面向选 一 提供 的矿石 尝 、 量 叭 二 ， 乡 · · … 。 习 艾计 量 ， 问采掘工 作 量 作业 计划 的 优化模型 如 下 弓 ， ‘ ，二 ’ 、 ， 一 ’ 、 。 ’ ① 产量约束 习 。 。 一 计划 产量 ， 》 、 。 二 ， ， 一 ‘，一 产 “ 二 ② 品 位约 束 ， 一 。 。 △ 。 ③ 各类矿石 百 分率 上下界约 束 · · … 艺 ， 一 一一 」 ， ④ 非 负约束 ， ， … … 说 明 － 露 天矿 采矿工 作面数 ， － 由 第 个工 作面 向选 厂 ‘ 提 洪灼 第 孔卜犷石 量 为 ，的 线 性函 数 二 ， ， 价 别 代表难选 型 做 难选 型和 标 准型 。 ， － 开采矿石 总量 中难选矿 石 日 宋 划 耳分 率 ， 。 、 一 一第 个 露天 矿 ， ， 的 计 划 产 量 ， 一第 个露 天 矿 的 作业 不 均衡 系数 ‘ － 第 个露 天矿 的工 作面数 ，尹 一 一 第 个工 作面 的 最 低 允许 运 出量 ，“ 一 第 个 几作而 电铲 均最 火可能生 产 能 力 。 ， 。 － 分 对 代 茂入选 昆台矿石 中成 分 门 汁算含量 为 的线 性 函 数 少 与 计划 含

量： △c一ac与aoc的允许偏差； K:1,K21一一分别点示采矿总量中第j种矿石的最小及最大百分率。 显然，这个模型是矿山经济管理中遇到的一个分式规划模型。分式规划模型在经济管理 及其它领域中相当常见，这里不作赘述。 (-)Gilmore一Gomor y算法 分式规划的算法有多种，其中最常用的是Gi1more一Gom ory算法（以下简称为G一G 算法)。 我们首先概述一下分式规划求解的理论基础和G一G算法的要点。 定义1（拟凸函数）：一个函数f(x)称为凸集S上的拟凸函数(quasiconvex fun~ ction),只要满足： (1) {xIf(x)≤cx∈S}对所有的c为凸集： (2) Vx ()x (2)ES,f(x (2))>f(x () f(入x(2)+(1-入)x1)≤f(x)(0>入>1) 定义2（严格拟凸函数）：f(x)为拟凸函数，且(2)中为严格不等式，则f(x)称为凸集S 上的严格拟凸函数(Strictly quasiconvex function)。 易证：分式规划的目标匠数【(x)=☑)=Cx(Z,(x)>0)在约束城R={xAx Z2(x)C27x =b,x≥0}.上是强拟凸函数。 严格拟凸函数有良好的性质： 〔定理1)格拟凸函数的任何局部最优解都是整体（全屙）最优解。（证明见2]） 〔推论)：分式规划(2)的局部最优解也是整体最优解。 关于分式规划的最优解，有如下重要定理： (定理2)如果分式规划的约束域R育界，刚百标函效(x)在R的某个极点处达到最小 值。（证明见3】） 定理2为以单纯形方法作为求解分式规划的基础，提供了重的前提。但要在：确定进基 变量时，需知道极点转移时的下降方向，这可由下面的定理3给出。 (定理3)设(x)=:X}Z,(x)=c1Tx,乙：(x)=c:Tx定义在集金R上，且 Z2(x) Z2(x)>0。若y∈R,且d为一个给定的方向，如果： ① y+ad∈R00) ② g(0)= df(y ad) <0 da a=0 则h(a)=f(y+ad)对0<a≤ò上任意的a,是一个单调减函数。（证明见t]) 在定理1~定理3的基础上，可以建立G一G算法。 〔Gi1more一Gom ory算法)对于分式规划(2)，不失一般性，设矩阵A的秩为m,且 初始基为B(1)=(P:P2…Pm)。 step1.写出扩充的单纯形矩阵(3) 89

量 △ 。 － 。 与 。 。 的允许 偏差 ， ，， ， － 分别 表示 采矿 总量 中第 种矿 石 的 最 小 及最 大百 分率 。 显 然 ， 这 个模型 是 矿 山经 济管 理 中遇 到 的一 个分 式 规划 模 型 。 分 式规划 模型 在 经 济管理 及其 它领域 中相 当常见 ， 这 里不 作赘述 。 一 一 算法 分 式 规划 的 算法有 多种 ， 其 中最 常用 的 是 一 算法 以 下简 称为 一 算法 。 我 们 首先概述一 下分 式规划求解 的 理论 基 础和 一 算法 的 要点 。 定义 拟 凸 函数 一 个 函 数 称为 凸集 士几的 拟 凸 函数 ， 只要满 足 ’ ， 二 〔 对所有 的 为 凸集 竺 〔 ， ’ 心 灾入 “ 一 入 川 《 ， 入 一 定 义 严 格拟 凸函 数 为拟 凸 函数 ， 且 中为 严 格 不等 式 ， 则 称为 凸集 上的 严格拟 凸函数 二 。 一 一产、 一 ‘了，︸、 、 易证 分式规划 的 目标 函数 一 在 约 束域 ， 》 叶 上是 强 拟 凸函数 。 严 格拟 凸 函数 有 良好 的 性质 〔定理 〕 严 格拟 凸 函 数 的任 何 局部 最 优解都是整 体 全局 最 优解 。 证 明见 川 〔推论 〕 分 式 规划 的局 部 最 优解 也是 整 休最 优解 。 关 于分式 规划 的最 优解 ， 有 如下 重要 定 理 〔定 理 〕 如 果 分 式 规划 的 约 束域 有界 ， 则 目标 函数 在 的 某 个极 点 处 达 到最小 值 。 证 明见 定 理 为 以 单纯形 方 法作为求解 分式规划 的 基 础 ， 提供 了 重 要 的 前提 。 但 要在确 定进 基 变 量 时 ， 需知 道极 点转移 时 的 下 降方 向 ， 这可 由下面 的 定 理 给 出 。 定理 〕 设 ， ， ， 定义 在集 合 上 ， 且 一 一 一 。 若 〔 ， 且 为一 个给 定 的 方 向 ， 如果 ① 〔 各 各 ② 仪 则 二 十 对， 各上任 意 的 ， 是一 个单调 减 函 数 。 证 明见 在 定理 一 定 理 的 基础 上 ， 可 以 建立 一 算法 。 〔 一 算法 〕 对 于 分 式 规划 ， 不 失一 般 性 ， 设 矩阵 的秩 为 ， 且 初 始基 为 ‘ 二 … … 。 。 ， 工 写 出扩充的 单纯形 矩阵

X1 X2…Xm Xm+I…Xn 1 0……0 a1m+1…a1n bi 0 1……0 a2m+l…a2n b2 (3) 0 0*…1 amm+1…amn bo 0 0*…0 cim+1..Cin -Z1 0 0…0 C2m+..C2n -Z2 step2. 计算(x2对非装变量x,行=+，…a治偏号数，并记作r,品： r1=02/2)=22czc21 222 j=m+1,…n (4) 0x1 称r,为“导数检验数” step3.若r1≥0(j=m+l,…n)则停，已达最优。最优解x*=(b:b2…bm 0,…0)影 若否，即某个（些）r,<0,则选x,进基； step4. 对(3)施行单纯形法运算，得新表，转向step3。 (二)Gilmore一Gomor y算法避免死循环的规则 在一般情况下，G一G算法是有效的，但在某些情况，即退化的情况下，则有可能产生 程序的死循环，造成计算的失败。（值得注意的是：在管理模型中，退化情况并非罕见。） 今构造反例如下： 例2 19 1 20 minf(x)=21(x)=24x+20x:-2x:+ 3x4 Z2(x) x2+x3+X7 1X1-8x2-X3+9x4+X5 =0 4 s.t 2X1-12x2- -Xs+3x4+X8 =0 2 X3 +X7=1 X1≥0i=1,2…7 解：用G一G算法，用(4)式计算导数检验数r1,每次迭代取绝对值最大的负导数检验数 r,对应的变量x,进基。计算表格如下： X1 X2 X3 X4 Xs X 8 X1 b 1/4 -8 -1 9 0 0 0 A 1/2 -12 -1/23 0 1 0 0 表 0 0 1 0 0 0 1 1 CI -19/2420 -1/220/3 0 0 0 0(-z1) C2 0 1 00 0 0 0 -1(-22) -19/2420 -1/2 20/3 0 0 0 0(f) 90

曰 ， “ ” ‘ 匕 二 ， … … … ’ … 一 ’ …” ’ 二 ’ 二 … … ， … … ， … 、 哥 … … … 二 ” 二 ” ‘ 二 二 … ’ 沙 几 计 算 对非基 变 量 ， 二 ， … … 的偏 导数 。 一 一 口 且 并记 作 ， 即 过 鱼旦生上 二 正妇 ， · “ 一 一 一 ﹂ 一 称 ，为 “ 导数 检 验数” ， 若 ， 》 二 ， … … 则停 ， 已达最 优 。 最优解 朴 ， … … ， … … 若 否 ， 即 某个 些 ， 。 ， 则选 进基 对 施行单纯形 法运 算 ， 得新 表 ， 转向 。 二 一 算法避免死循环 的规 则 在一 般情 况 下 ， 一 算法是 有 一 效 的 ， 但在 某些情 况 ， 即退 化的 情 况 下 ， 则有可 能产生 程序 的 死循 环 ， 造 成计 算的失败 。 今 构造反例 如下 例 值 得注意 的 是 在管 理模型 中 ， 退 化情 况 并非罕见 。 一 ‘ 艺 一 几厂 丁 ‘ 八甘 一 ， 一 一 一 、 。 · 一 一 ’ 一 工乙 。 ， … … 解 用 一 算法 ， 用 式 计 算导数 检验数 ，， 每 次 迭 代取 绝对值最 大 的 负导数 检 验数 ，对应 的变量 ，进基 。 计 算表格如下 一 ’ · 一 ’ · 一 ’ · · 。 · ’ 一下 一，一而一万一几 一 万一 一二一 。 一 一” “ ‘ 一 ‘ ， 一 ‘ ‘ 一 一 卜 ‘ · ” ” ‘ ” ‘ ‘ ， ‘ 一 ‘ ‘ 。 一 ‘ 。 。 ” 。 ‘ 一 竺一一生一一二 一 二 二 一一生一卫一一 兰一一 卫二 一 ‘ ， 一 ‘ “ 一 ‘ “ ” ” ” ” 户“

X 1 X Xi X 7 b -32 -4 36 4 0 0 A 0 3/2-15 -2 1 0 0 表 0 0 0 0 0 1 cl 0 -16/3-11/3 211/619/6 0 0 0 2 C2 0 1 0 0 0 0 0 -1 0 -16/3 -11/3 211/6 19/6 0 0 0 1 0 8 -84 -12 8 0 0 A 0 1 3/8 -15/4-1/2 1/4 0 0 表 0 0 1 0 0 0 1 1 C: 0 0 -5/3 91/6 1/2 4/3 0 0 3 Cz 0 0 -3/8 15/4 1/2 -1/4 0 -1 y 0 -5/3 91/6 1/2 -4/3 0 0 1/8 0 1 -21/2 -3/2 0 0 A -3/64 1 0 3/16 1/16 -1/8 0 0 表 -1/8 0 0 21/2 3/2 -1 1 1 ci 5/24 0 -7/3 -2 0 0 4 3/64 0 0 3/16-1/16 1/8 0 -1 5/24 0 0 -7/3 -2 3 0 0 -5/2 56 1 0 2 -6 0 0 -1/4 16/3 0 1 1/3-2/3 0 0 表 5/2 -56 0 0 -2 6 1 1 -3/8 112/9 0 0 -11/9 13/9 0 0 5 C2 0 1 0 0 0 0 0 -1 -3/8 112/90 0 -11/7 13/9 0 0 -5/4 28 1/2 0 -3 0 0 1/6 -4 -1/6 0 1/3 0 0 表 0 0 1 0 0 0 1 1 C: -137/72 140/3 11/18 0 0 -20/9 0 0 6 C2 0 1 0 0 0 0 0 -1 、 -137/72 140/3 11/18 0 0 -20/9 0 0 鼠 1/4 -8 -1 ⊙ 1 0 0 0 表 A 1/2 -12 -1/2 0 1 0 0 0 0 1 0 0 0 1 C -19/24 20 -1/2 20/3 0 0 0 7 0 1 0 0 0 0 0 -1 -19/24 20 -1/2 20/3 0 0 0 0

一 ‘ 表 一 一 一 丈 一 一 表 一 一 一 ， 一 一 一 一 一 一 一 一 一 一 ， 一 一 表 一 一 一 八 一 一 一 一 一 一 一 一 一 一 表 一 一 一 一 一 一 一 一 一 一 一 表 一 一 一 一 一 一 ， 一 一 一 盈 表 一 一 一 一 一 一 。 一 一 一 石

表7与表1完全相同，即发生了送代的死循环，计算失败。 下面，我们给出一个防止G一G算法发生死循环的规则，它可以看做Bland【!规则的 充，不妨称为“补充的Bland规则”。 〔扩充的B1and规则)在分式规划的G一G算法中，如果： ①同时有多个负导数检验数，时，则取其中下标最小者对应的非基变量x。作为进基变 量，即1=min{jr,0 0:1 as1 〔定理4)按补充的B1and规明，对分式规则(2)施G一G算法，一定不会产生死循 环 [游：归反证法。如其不然，即按扩充的Blan d规划对分式规刘(2)施G一G算法， 发了B的循环。这个循环的过程记作： B(0)→B()+B(2).→-，B()-+B(o) (B()表示第i阶段的基) 用T表示在这个循环过积中，由非共变赋变为基变量的变量下标集。并记g=max{j!j∈T}。 设xg在第r次迭代时由非基变量变为基变量，则由G一G算法及扩充的Blan d规则①知： 导数检验数 rg=Z2c18-21C28<0 g=min{jlr,<0j∈R} 此时，分式规划(2)的表达式可写作： f=21。+c11x1 jER Z20+Ec21x, ∫x1=b!-Ba11x1 iES (5) s.t x1≥0i=1,2…n 其中：R,S分别为B()中非基变景与基变量下标集。 设×，在第k次迭代时，由基变量变为非某变量，同时，x,由非基变量变为基变量，则 有： 导数检验数 r,=2C1!,21c2t<0 2 叶时，分式规划(2)的表达式可写作： f=10+卫eX) j∈R' 220+□c21x1 了X1=b,-Da11x; jES (6) s.t x1≥0i=1,2…n 其中：R',S′分别表示Bk)中非基变量与基变量下标集。 并且，由扩充的Bland规则②知： 92

表 与表 完全相 同 ， 即发生 了 迭 代的 死循环 ， 计 算失败 。 下而 ， 我们给 出一 个防止 一 算法发生 死循 环 的规 则 ， 它可 以看做 ‘ 规则 的扩 充 ， 不妨称为 “ 补充 的 规则” 。 扩充 的 规 则 在 分式规划 的 一 算法 中 ， 如果 ① 同时有 多个负 导数 检 验数 ，时 ， 则取 其 中下 标最 小者 对应 的非基 变 量 。 作 为进 基 变 髦 ， 即 、 ， ‘ 、 ， ， ， ， 一 、 人 ， ， 一 、 ， 卜 ， ， 卜 ， ， 卜 ， ， ， ， 气岁 仕 进 推 夕，厂 一 匕’川 明湘 乡 ‘ ， ‘ “ 匕但百井 一 还羊”最 “ 、 目于 ， 罗 取 具 甲 曰尔最 “ “ 省 对应 的 基父 重 为离基 变 量 ， 即 二 。 、 、 二 左 日 ‘ 一 一 户 全 〔定理 〕 按 补充 的 规 则 ， 对 分 式 规 则 施行 一 算法 ， 一 定 不会 产生 死循 环 。 证 明 用 反 证法 。 如 其 不 然 ， 即按 扩 充 的 规划 对分 式 规戈勺 施布 一 乞算法 ， 发生 了 从 的循环 。 这 个循 环 的过 程记 作 “ 川 … … 川 表示 第 阶段 的 基 用 广 次示在这 个循环 过 积 中 ， 由非 从变 量变 为基 变 量 的变 量下 标集 。 并记 二 王」 〔 ’ 。 设 在 第 次迭 代时 由非基 变 昆变 为基 变 量 ， 则 由 一 算法 及扩 充 的 规 则① 知 号数 检验数 一 召 一 吕 艺 么 ， 此 时 ， 分 式 规 划 的表达 式可 写作 立 、 上旦鱼 呼 ， 又 ， 〔 〔 二 ， 一 兄 ， 〔 》 ， … … 产、矛、 工 其 中 ， 分别 为 《 中非基 变 最 一 与基 变量 下标集 。 没 。 在 第 次 迭代时 ， 由墓 变量 变 为非 毕变量 ， 同时 ， 由非华 变量 变 为基变 量 ， 则 导数检验数 ， 兰 一 今生 二 厂 ， “ 兰 ， 此 时 ， 分 式 规划 的 表达 式可 写 作 之 。 名 王 〔 乙一 一 ， ， ， 〔 产 二 ， · · … 列 其 中 ‘ ， ’ 分别 表示 “ 中非基变 量 与基 变量下标集 。 并且 ， 由扩充的 规 则②知

(7) as t 将第k次迭代的起始极点记作：，即在(6)式中，变量为x。令非基变量作如下改变： (△X:=E (e>0,且足够小) (8) (△x,=0 j∈R't} 则(6)中基变量相应的改变量为： △x,=-ea1:i∈S' (9) (6)中目标函数值的改变量为： △f=f(元+△x)-f(x) =21(x+△x)_21(x) z2(z+△x)z2(x) =1+1(x)+Ax1）-10+cx1 j∈R' 220+DC21(x」+△x;）g20+已c2,X； =名20C1t-810C21e (z:o+ecz1)220 d =Kr,0 (11) z2。+ec21 注意到：(5)(6)是等价方程组，故在同一极点处，对于(8)式，(9)式，(5)中目标函 数的改变量应与(10)式中的△f相等，即有： z20(∑c1)△x)-z1(c21△x1）0,即rn>0与(10)(11)式矛盾影 2.hR'/{t}。这是由于：若h∈R'/t},则由(8)式知：△xn=0,(13)式不可能成 立，由1.2.知：hR'。.h∈S',而h∈R(见(12)式)h∈T。 3.h≠g。这是由于：若h=g则rg0,又由(13)式知rn0,则由(13)式知rn>0。,h<g.在第r次迭代时应 93

丝 、 。 －一 了 ‘ 将 第 次 迭 代 的起 始极 点记 作沁 即 在 式 中 ， 变 量 为 劣 。 令 非基 变 量作如下改 变 。 ， 且 足够 小 〔 ， 产了且，△ 一 ︸ 、硬口 、 则 中基 变量相应 的改变量 为 么又 ， 一 ， ， 任 中 目标 函数值 的改变量 为 么 二 牙 八 一 毖 ， 玉 △ 牙 △ 名 一 △ 牙 。 石 一 ， △ ， 名 一 。 之 。 兄 」〔 ‘ ， ， 谁含羚篡 瞻认 ’ · 二 其 中 一吕至。 些 名 。 注意到 是 等价方 程组 ， 故在 同一极点法处 ， 对 于 式 ， 式 ， 中 目标函 数 的改 变量应 与 式 中的 △ 相 等 ， 即有 全赵旦勺 」李客毕护 一 生三到 全匹 口 。 气 十 山 凸 一 〔 则 必 有下标 ， 使得 ， 。 ， 一 么 一 ， 。 ， 么 八 戈 芭 或 。 一 。 八 。 △ 今 证 式 不可 能成立 。 因若 不 然 ， 可 作如下讨 论 铸 。 这 是 由于 若 ， 则 由 〔 知 〔 ， 故 。 则 由扩充 的 规则 ②得 ， 导致 ， ， 即 与 式矛盾 桩 ， 。 这是 由于 若 〔 ， 八 ， 则 由 式知 △ ， 式 不可 能成 立 ， 由 知 必 ， 。 ， 〔 产 ， 而 〔 见 式 几 〔 。 笋 。 这是 由于 若 二 则 ， 但 由 式 及 式得 △ ， ， 从 而 与 式矛盾 ， 。 分 两种 情 况 情 况 △ 二 一 。 ， 又 由 式知 ， 则 由 得 在 第 次迭 代 时应选 、 进 基 ， 与选 。 进 基 矛盾 。 情况 △ 一 。 ， ， 即 ， 。 ， 则 由 式知 、 。 ‘ … 在 第 次 迭 代时应

令Xn离基，与选xg离基矛盾。 综合上述讨论可知，定理4成立。证毕。 用扩充的B1and规则和G一G算法去求解反例（例2），.经三次送代，可得出最优解x*: x*=(a,0,1,0,号，0,0)r f0=-31 24 (迭代表格略) 参考文献 (1 P.C.Gilmore and R.E.Gomory:"A.Linear Programming App- roach to the Cutting'Stock Problem-Part I"Operations Res 11. 1963pp863-888. (2)J.Ponstain:"Seven llinds of Convexity"SIAM Rev 9 N1 1967 (3)L.S.Lasdno:"Qptimization Theory foy Large Systems"pp 185- 1951970. 〔4)R.G.Bland:“New finite pivoting Rules for the Simplex Method” Mathematics of Operations Research Vo12.N02 1978. 〔5)B.M.阿列尼切夫：“用计算机编制作业计划是提高入选和矿石质量的有效办法” 载“国外金属矿采矿”1984年第7期。 Pivoting Rules for Avoiding Cycles in the Gilmore-Gomory Algorithm Li Zongyuan Abstract Fractional programming appears often in the management model.It can be Solved by the Gilmore-Gomory algorithm. In our paper.we have constructed counterexample Showing that the Gilmore-Gomory algorithm may produce cycles,so that the computation is impossible.In'this paper.we also give new finite pivoting rules and show that using this new pivoting rules cycles are avoided. 94

令 。 离基 ， 与选 离基矛盾 。 综合 上述讨 论可知 ， 定理 成立 。 证 毕 。 用扩 充 的 规则和 一 算法 去求解 反例 例 ， 经三 次 迭 代 ， 一 可得 出最 优解 气 ‘ ‘，， 。 ， ‘ ， 。 ， 令 ， “ ， ” ， · ， 一 卫 迭 代表格略 参 考 文 献 〔 〕 － ” 一 〔 〕 ” 入 抛 〔 〕 “ ” 一 〔 〕 “ ” 加 〔 〕 阿列 尼 切夫 “ 用计算机编制作业计划是提高入 选矿石质 量 的 有效办法 ” 载 “ 国外 金属矿 采矿” 年 第 期 。 一 一 一 ， · 只 · 万 “ “ 叫