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∈R0<a≤8(8>0) ② 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

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