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