D0I:10.13374/j.issn1001-一053x.1995.02.017 第17卷第2期 北京科技大学学报 Vol.17 No.2 195年4月 Journal of University of Science and Technology Beijing Ap.1995 线性规划问题最优解的表示 周汉良 北京科技大学数力系，北京100083 摘要本文指出了线性规划的最优解可表示为最优极点的凸组合和最优极方向的非负线性 组合之和，确定了最优极方向存在的条件， 关键词基本可行解，极点，极方向，最优解 中图分类号0221.1 Representation of Optimal Solution for Linear Programming Problem Zhou Hanliang Department of Mathematics and Mechanics,USTB,Beijing 100083,PRC ABSTRACT It is pointed out that optimal solution of linear programming can be represented as a sum of a convex combination of the optimal extreme points and a nonnegatively linear comabination of the optimal extreme directions.The existential condition of optimal extreme direction is determined. KEY WORDS basic feasible solution,extreme point,extreme direction,optimal solution Bazaraa等在文献[l]中指出：X∈D={X:AX=b,X≥0}当且仅当X能表示成所 有极点的凸组合和所有极方向的非负线性组合之和·本文将此结果推广到X是最优解 的情况，即X是线性规划的最优解当且仅当X可表示成它的最优极点的凸组合和最优 极方向的非负线性组合之和·同时指出用单纯形方法判断最优极方向存在的条件及寻求 最优极方向的方法· 1最优解的表示 考虑如下的线性规划问题： (Lp)minS=cX s.t.AX=b,X>0 其中A是m×n矩阵，r(A)=m,m<n,c=(C,c,…,Cn),b=(b,b,·,bm),X=(x1,x2, …,x) Bazaraa等在文献[1]中指出：若可行域D={X:AX=b,X≥O}非空，则极点集 非空；当且仅当D有界时极方向集是空集，如果D是无界的，则极方向集是非空的· 1993-11-30收稿第一作者男55岁副牧授第 17卷 第 2 期 1 9 9 5 年 4 月 北 京 科 技 大 学 学 报 Jo um a l o f U n i vrse it y o f S d ne ce a nd T ce h no l o g y Be ji ni g V o l . 17 N 0 . 2 A P r . 1 9 9 5 线 性规划 问题最优解 的 表示 周 汉 良 北 京 科 技 大 学 数 力 系 , 北 京 10 0 0 8 3 摘 要 本文 指 出了 线 性规 划 的最 优解 可 表 示 为最 优极 点 的 凸 组 合 和 最 优 极 方 向 的非 负 线 性 组 合 之 和 , 确 定 了 最 优极 方 向存在 的 条 件 . 关 健 词 基 本 可 行解 , 极点 , 极 方 向 , 最 优解 中 图分类 号 0 2 2 1 . 1 R e P r e s e n t a t i o n o f O P t i ma l S o l u t i o n fo r L i n e a r P r o g r a n u n i n g P r o b l e m Z h o u H a n li a n g D e P a rt m e n t o f M a t h e m a t i c s a n d M e e h a n ies , U S T B , B e i j i n g 10 0 0 8 3 , P R C A B S T R A C T It 1 5 P o i n t e d o u t t h a t o P t im a l s o l u t i o n o f li n e a r P r o g r a rnm i n g c a n b e r e P r es e n t e d a s a s u m o f a c o n v e x co m b i n a t i o n o f t h e o P t im a l e x t r e me P o i n t s a n d a n o n n e g a t i v e l y li n e a r c o i lL b i n a t i o n o f t h e o P t im a l e x t r e me d i r e c t i o n s . T h e e x i s t e n t i a l co n d it i o n o f o P t im a l e x t r e m e d i r e e t i o n 1 5 d e t e nT n e d . K E Y WO R D S b a s i e fe a s ib l e s o l u t i o n , e x t r e m e P o i n t , e x t r e m e d i r e e t i o n , o P t im a l s o l u t i o n aB az ar a 等 在 文献 [ l] 中指 出 : X 任 D 二 {:X A X = b , X ) 0} 当 且 仅 当 X 能 表 示 成 所 有 极 点 的 凸 组 合 和 所 有 极 方 向的 非 负 线 性 组 合 之 和 . 本 文 将 此 结 果 推 广 到 X 是 最 优 解 的情 况 , 即 X 是 线 性 规 划 的 最 优 解 当且 仅 当 X 可 表 示 成 它 的 最 优 极 点 的 凸 组 合 和 最 优 极 方 向的 非 负 线 性 组 合 之 和 . 同 时 指 出 用 单 纯 形 方 法 判 断最 优 极 方 向存 在 的条 件 及 寻 求 最 优 极 方 向 的方 法 . 1 最 优解 的表 示 考 虑 如 下 的线 性 规 划 问 题 : ( L P ) m 1 n s = c X 5 . t . A X = b , x ) 0 其中 通 是 m x n 矩 阵 , : (通 ) = m , m < 。 , e = ( e , , c Z , … , e , ) , b = ( b , , b Z , … , b , ) T , x = ( x l , x Z , ” ’ , x 。 ) T . aB az ar a 等 在 文 献 [ l] 中 指 出 : 若 可 行 域 D = {:X A X 二 b , X ) 哪 非 空 , 则 极 点 集 非 空 ; 当且 仅 当 D 有 界 时 极 方 向 集 是 空 集 , 如 果 D 是 无 界 的 , 则 极 方 向 集是 非 空 的 . 19 9 3 一 1 1 一 3 0 收 稿 第一 作者 男 5 岁 副教 授 DOI: 10. 13374 /j . issn1001 -053x. 1995. 02. 017