线性分式规划的多项式算法

D0I:10.13374/j.issn1001-053x.1986.01.030 北京钢铁学院学报 1986年3月 Journal of Beijing University No.1 第1期 of Iron and Steel Technology March 1986 线性分式规划的多项式算法 周汉良 (数学第二教研室) 摘要 Charnes-一Cooper提出了一种线性分式规划的算法C1门。本文在此基础上证明了线性分式规划与一种特 定的线性规划等价。将Karmarkar算法C2门用于该线性规划，我们得到了线性分式规划的多项式算法。 关葡饲：多项式算法、Karmarkar主算法、严格内点、射影变换、滑动目标函数。 A Polynomial-Time Algorithm for Liner Fractional Programming Zhou Hanliang Abstract A.Charnes and W.W.Cooper presented an algorithm for liner fractio- nal programming(i).We prove that the liner fractional programming is an equivalent of a certain liner programming;then we use Karmarkar alg- orithm for the liner programming(2)to get the polynomial-time algorithm for liner fractional programming. Key words:polynomial-time algorithm,Karmarkar main algorithm,str- ictly interior point,projective transformation,sliding objectiv function. 米 线性分式规划的标准形式是： PrX+a min QTX+8 (1) s,t,AX=6 (2) X≥0 (3) 其中 X=(x1,x2,…,x)T, P=（p1,P2,…,p)T, 1985-10-08收到 ·150·

年 月 第 期 北 京 钢 铁 学 院 学 报 。 线性分式规划的多项式算法 周 汉 良 数学 第二教研室 摘 要 一 提 出了一 种线性 分 式规划 的算 法〔 〕 本 文 在此基 础 上证明 了线性 分式 规 划与一 种特 定 的线性规划等价 。 将 算法〔 〕 用于该线 性规 划 ， 我们得到 了线性 分式规 划的 多 项式算法 。 关 饲 多项式算法 、 主算 法 、 严 格内点 、 射 影 变换 、 滑 动目标函数 一 。 “ ” ’ 。 〔 〕 ‘ 〔 〕 一 。 了 一 ， ， 了 ， 刀 ， 辛 帝 线性分式规划 的标准形式是 尸 ， 刀 》 其中 二 ， 二 ， 尸 ， ， ， ， ， 一 一 收到 DOI ：10．13374／j ．issn1001－053x．1986．01．030

9=（91,92》…,9m）, A=(ai)是秩为m的m×n矩阵， a,B为常数。 我们知道，若qTX+B>0,则(1)~(3)的任意局部极小也是全部局极小(3)。 1 Charnes-一Cooper算法 令S={X引AX=b,X≥0}，设S非空有界。 先作变量替换： Y=ym+1X,yn+1≥0 (4) 考虑下述线性规划： min (prY+ay+1) (5) s.t.AY-by+1=0 (6) qY+Byn+1=Y,y≠0 (7) Y≥0，ym+1≥0 (8) Y是实数。 上述线性规划具有性质，对每个可行解（少.…），一定有>0。 事实上，若此性质不成立，即有ym+1=0,则由(6)、(8)，AY=0,Y≥0， 又由(7)， qTY=Y≠0， 所以 Y≠0 这样，对于(1)~(3)的可行解X及任意的1≥0， X+AY 也是(1)~(3)的可行解。这与S的边界性矛盾。所以，ym+1>0。 若qX+B>0,用单纯形法解(5)~(8)，由(5)~(8)的最优解可得(1)~ (3)的最优解。这就是： 定理1。如果(i),对(1)~(3)的某个最优解X°，gTX°+B及y都为正， (ii),(y◆T,y+1)T是(5)~(8)的最优解。 则 片，是1)~3)的最优解是（证明见3）。 2(1)~(3)与(5)~(8)的等价性 下面我们证明，定理1的逆定理亦成立。 定理2。计X◆是(1)~(3)的最优解，qTX+B>0,>0,令 qx+B,Yyx ·151·

二 ， ， ， … … ， ， ， ‘ ， 是秩为， 的， 。 矩 阵 ， ， 刀为常数 。 我们知道 ， 若 『 刀 ， 则 的任 意 局 部极小也是全 部局 极小〔 〕 。 一 算法 令 二 ， ， 设 非空有界 。 先作变量替换 二 。 ， ， 。 夕 考虑下 述线 性规划 。 ， 刁 一 夕 。 ， 了 十 刀 。 ， 夕， ，铸 ， 。 护是 实数 。 、 、 ，， ，’ ，、 。 一 ， ‘ 一 ， 一 、 一 工止戏任扰 划县月 往城 河 毋，、 田 仃麟 飞 ， ， ， 一正 月 。 、 了 了 事实上 ， 若此性质不成立 ， 邵有为 。 二 ， 则 由 的 、 ， 二 分， 奋分 又由 ， 俨 夕护 ， 析以 价 这样 ， 对于 的可 行解 及 任意的 之 ， 十 几 也是 的可行解 。 这与 的边界 性矛盾 。 所 以 ， ， ， ， 。 若 夕 ， 用单纯 形法解 ， 由 的最优 解 可 得 的最优解 。 这就是 定理 。 如果 ， 对 的某个最优解 。 ， 丁 。 刀及夕都为正 ， ， ， 份 十 是 的最优解 。 则 牛 是 一 的最优解是 证 明则 〕 食 与 一 的等价性 下 面我们证明 ， 定理 的逆定理亦成 立 。 定理 。 计 是 的最优解 ， 了 刀 。 ， ， 。 ， 令 夕舍 十 夕 刀 今 二 育

则(Y◆r,y+1)是(5)~(8)的最优解。 证明：反证。设(Y◆T,y+:)T不是(5)~(8)的最优解。因S非空有界，(5)~ (8)一定有最优解。 设(YT,y+1)T是(5)~(8)的最优解，则有 pryo+ayi+10,则线性分式规划(1)~(3)与 线性规划(5)~(8)等价。 上述定理中的条件qTX+>0只需在极小点附近成立即可。 如果极小点附近有： qX+80,则由定理3，(1)′(2)(3)即(1)~(3)与线性规划 min (-prY-ay+1) (5) s.t.AY-by+=0 (6) -qTY-By+1=Y,>0 (7) Y≥0，ya+:≥0 (8) 等价。一般解对应的线性规划时，Y可取任意的正数值。 了线性分式规划的多项式算法 下面为了讨论方：便，设qTx+B<0。 由于线性规划(5)~(8)的特殊结构， ·152·

则 ， 夕育 十 犷 是 的最优解 。 证 明 ， 反证 。 设 钾 ， 份 不 是 的最优解 。 因 非空 有 界 ， 一 定有最 优解 。 设 “ ， 言 是 的最 优解 ， 则 有 了 ” 对 尸 了 育 十 。 今 式 。 一 丫石一 少 。 尸丁 。 尸 。 万可 于不万一 了 瓜 丙熟 尸 丁 ’ 下 些今 竺业生 二二 尸 份 ， 尸 ， 一 万丁灭币 千刀 即 尸 。 尸 ， 了灭 石 千刀 、 砰灭币不刀 这与 是 ‘ 一 的最 优解矛盾矿定理得证 。 综合定理 和 定理 得 到 定理 设对任意 的 任 ， 有 刀 ， 夕 ， 则 线性分式规划 ’ 与 线性规 划 等价 。 上述定理 中的条件 ， 刀 只 需 在极小点 附近成立 即可 。 如果极小点 附近有 刀 我们可 以将 中的分 子 、 分母 同乘 以 一 ， 得 · 一 】 一 尸了 一 一 一 刀 祀 一 而 、 尹 、吸了 勺吕口内一 、少 ‘ 、尹了、 了、、‘了、 这时 ， 一 ， 一 刀 ， 则 由定理 ， 产 即 与线性规划 一 一 夕 十 ， 犷 一 少 ， 们 二 一 ， 一 刀夕 。 ， ，， 夕 ， 。 十 》 等价 。 一般解对 应的线性规划时 ， ，可 取任意 的正数值 。 线性分式规划的多项式算法 下 面为 了讨论方 了便 ， 设 ， 刀 。 。 由于线性规 划 的特殊结 构

1当()>0 start 时，通过简单的变换，不增加问题维数和约 束，可将(5)~(8)化为标准形式。为 此，先将(5)~(8)改写成： Given minCry x,a,9>0 s.t.A =0 and K=0 qT Y=Y,Y>0 (9) Y≥0 其中 x2> Yes Stop c-(d),a=(4-b) CTa No 9=(9),r() D=d1agfx…, 91 Q= 92 B Cp=红-B(BB'BJDc 是n+1阶对角矩阵，作变换： &=0n Y=_QV g· 5=a-t 1 又取 y=1gl 则(9)化为： min Cry bsDb e"Dh s.t.A/Y/=0 (10) eTy/=1 +11 K,Xb Y1≥0 1 其中C=Q-1C,A!=AQ1,e∈R"+1,其分量全为1。 如果线性规划(10)的目标函数的最小值等于零，它就是Karmarkar主算法能直接计 算的标准问题。所谓主算法是： 考虑标准问题： minCTX,C.X∈R"。 s.t.AX=0,Amxn。 eTX=1 X≥0 主算法（框图见右上） 已知Xo是标准问题(10)的严格内点，a=(分，，品r∈R巴，终止参数。 ·153·

心 、 当 气刀 ” 时 ， 通过简单的变 换 ， 不 增加 问题 维数 和 约 束 ， 可 将 化为标 准形式 。 为 此 ， 先将 改 写成 二 ， 二 护， ， 、 、刀 一一一 ， 了 ‘ 、 一 其中 二 言 ， 一 、 蒸 ， ， 一 。 令 卜 刀 是 阶对 角矩 阵 ， 作变 换 ， 二 一 犷 、 一 又取 则 ， 宁 化为 ， ， ， ， ， ， 二 ， 日 认 义 ，， ， 刀 二 二 “ 叫阶给 一 闪 ， 乃二 【 ， 二 卜畔 矛犷 ’ 二箫 东卜 戈湍洲 仑 “ ， 斋，丫准 其中 ， ， 一 ‘ ， ， 一 ‘ ， 〔 ’ ， 其分 量全为 。 如果线性规 划 的 目标 函数 的最小值等于零 ， 它就是 主算法能直 接 计 算的标准 问题 。 所 谓主算法 是 考虑标 准 间题 ， 任 。 月 ， 。 ， 主算法 框 图见 右上 已知 。 ’ 是 标 准间题 。 的严格 内点 ， 于 、 。 。 一 · ， 、 二 ” ’ ， 万尸 七 九 ” ， 羚 止参数

Step 1.K=0, CTX ( Step2.判别Cra≤29？ 若是，转step9, 若否，进行step3。 Step3。令D=diag〔xg),x2,…x)〕是对角矩阵， 日=〔1门，c=(,D为维胸意。 Step4.Cp=CI-BT(BBT)-1B〕DC。 sep.c。 Step8./=a-aC。a=} 1 Y=/n(m-1) 为单纯形{XeTX=1,X≥0}的内接球半径。 Db Step 7.b-eiDb Step8。k+1+k,令X(M)=b,转Step2. Step9。输出结果，停机。 如果线性规划(10)的目标函数的最小值不等于零，则可采用“滑动目标函数法”〔2)。 、当(2)>0不成立时，将(5)~(8)改写 minCry s.t,A Y=6 (11) y≥0 其中 c=(),A=(日) 0 6= 0..…… (+) 1 取P=1 显然，A是满秩的。若已知(11)的一个可行内点Y>0,作射影变换T: y= y:1y— +1 i=1,2,…yn+1。 y1+1 1 ，154·

夕 刀 ， ， 。 判别 ‘ 簇 一 若是 ， 转 夕 ， 若否 ， 进 行 。 夕 令 〔 三 由’ … 对 “ 〕 是对 角矩 阵 ， 〔 〕 ， 名 白 二 ， 卜 二 ， 为 。 维向量 。 刀 。 尸 二 〔 一 一 ’ 〕 。 尸 尸 匀口 一一 一 护 丫 ，牙 笼一一 二污育 月 月 一 为 单纯形 砂 ， 的内接球半径 。 夕 。 二 ， ， 。 ， ， 令 为 ， ， 转 尹 。 输 出结果 ， 停机 。 如果线性规划 的 目标 函数 的最小 值不 等于零 ， 则可 采 用 “ 滑动 目标 函数法 ” 〔 ” 〕 。 当 、 一 如 不成 立 时 ， 将 一 改 写成 刁一 、 其 中 显然 ， 一 刀 … ， 丫 “ 戈 夕 · ‘ 。 ， 取护 二 甘︸︸︹。占 、 、 一 一 是满秩 的 。 若 已知 的一 个可 行内点 “ ， 作 射影变换 ， 了 而边三吐一一 、 ， ， … ， 。 系 、 ， 、 十

+1 以。=1-∑ -1 可将(11)化为(10)的形式，只是Y'的维数是n+2维，齐约束方程的个数为n+1。其余 计算步骤同1°。 参考文献 [1]Charnes,A.and Cooper,W.W.:Naval Res.Logistics Quart.9,Sept-Dec.(1962),181. [2]Karmarkar,N..B New Polynomial--Tir Algorithm for Liner Programming,Procediugs of 16th Auuual ACM Symposium on Theory of Computing,Washington D.C.,1984,302 [3]Lasdon L.S.,Optimizaticu Theory for Large Sysiems 1970,185 e ·155·

月 另一 卜 艺 夕飞 ‘ 可将 化为 的形式 ， 只是 的维数是 维 ， 齐 约束方程 的个数 为 。 。 其余 计算步骤 同 “ 。 梢闷 参 考 文 献 〕 ， ， 〕 ， ， 一 ， ， 一一 口 ‘ ， 。 了 ， ， 〕 ， ‘ 。 宜 二 ， 一 飞卿 巴 嘴号曰 ·