线性规划问题最优解的表示.pdf_大学文库

第 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

Vol.17 No.2 周汉良：线性规划问题最优解的表示 ,179. 设X,…,X是D的全部极点，d,,d,是D的全部极方向，则X∈D当且仅当它可表示成X,…,X*的凸组合和d,,d,的非负线性组合之和，即： X=N+∑，d, 1 ,=1≥0，j=1,2.,k54≥0.j=1,210 由上式，(Lp)可变换为变量为2，…，入k,4,…,4,的如下线性规划问题： min8=2(cX0A+2(ed)加，st2A,=15≥0，j=1,2.,k:4≥0.j=12,,12 由(2)可得出(Lp)有如下3种情况：情况1因为4可以任意大，当有某个j1≤j≤1，使cd,<0时，则目标函数的最小值为-o,因而(Lp)无有限最优解). 情况2如果对所有j=1,2,…,l,cd,≥0，则4，=0，若存在{1,2，…，k}的一个子集R, 使对任意ieR, cX'=min {cX,j=1,2,.,k 则X,i∈R都是(Lp)的最优极点，在式(2)中当jR时元，=0，所以(Lp)的最优解为： X=,N点，=152≥0，eR 即(Lp)的最优极点的凸组合都是它的最优解· 情况3如果除情况2中的子集R外，还有{1,2，…，1}的一个子集Z,使得对每个 jeZ,有cd,=0,则(Lp)的最优解可表示为： X=盟2x+马4，点2，=1：人20，iR:4≥0，eZ (3) 对于情况3，给出如下定义：定义设d是可行域D的极方向，如果满足cd=O,则称d为(Lp)的最优极方向· 由上面的讨论，可有：定理1若X,i∈Rc{1,2,…,k}是(Lp)的最优极点，d,jeZc{1,2,…,是(Lp) 的最优极方向，则(LP)的最优解能表示为它的最优极点的凸组合与最优极方向的非负线性组合之和，即(3)式· 2最优极方向的存在性及求法求最优极点和判断最优极方向的存在性问题，可以用单纯形方法解决，即：定理2设X是(Lp)的最优基本可行解，则： (1)如果X的所有非基变量的检验数都小于零，则X是(Lp)的唯一最优极点，且(Lp)无最优极方向· (2)如果X°的非基变量有零检验数，且某个零检验数对应的列中有正数，则只要主元所在行的基变量值不为零，用单纯形法可求出不同于X°的另一个最优极点· (3)如果X的非基变量有零检验数，且所有零检验数对应的列的各行元素为系数、对应非基变量为变量组成的m个线性表达式小于等于零（即线性不等式组）有不全为零的非负解，则(Lp)存在最优极方向·

Vo l . 17 N 6 . 2 周汉良 : 线性规划问题最优解的表示 · 17 .9 设 Xl , … , 丫是 D 的全部极点 , d l , … , d , 是 D 的全部极方向 , 则 X 6 D 当且仅当它可表示成 Xl , … , 厂的凸组合和 d l , … , d , 的非负线性组合之和 , 即 : k l 人 X 一置 “ 少 X) +瓜 “ , d 少落 1又 , 一 ’ ; “ , ) O , 了一 ` , 2 , ” ’ , “ ; “ , ) 0 , 了一 ` , 2 , ” ’ , ` ( , ’ 由上式 , ( L )P 可变换为变量为只 1 , … , 又二 , # 1 , … , 拼 ` 的如下线性规划问题 : 几 1 m `n “ 一落 1 ( c 尸 ,又 , 十万 , ( “ “ , , “ , S · 艺又 , 一 1 ; 又 , ) o , j 一 1 , 2 , … , k ; ; , 列 , j 一 1 , 2 , … , l (2) 由 ( 2 ) 可得出 ( L p ) 有如下 3 种情况 : 情况 1 因为拜J 可以任意大 , 当有某个 j , 1 毛 j 簇 l , 使 cd , < 0 时 , 则目标函数的最小值为一的 , 因而 ( L )P 无有限最优解 [ 2 } . 情况 2 如果对所有 j 一 1 , 2 , … , l , cd , ) O , 则拜, = 0 , 若存在 l{ , 2 , … , k }的一个子集 R , 使对任意 i e R , C X ’ = m i n { c 尸 , j 一 l , 2 , … , k } 则 r , i E R 都是 ( L p ) 的最优极点 · 在式 (2 ) 中当j 诺R 时凡二 o , 所以 ( L p ) 的最优解为 : x 一艺凡x ! 艺又 : 二 1 ; 又 . ) 0 , 沂 R 即 ( L p ) 的最优极点的凸组合都是它的最优解 . 情况 3 如果除情况 2 中的子集 R 外 , 还有 { 1 , 2 , … , }I 的一个子集 Z , 使得对每个 j e Z , 有 cd , 二 0 , 则 ( L p ) 的最优解可表示为 : X 一馨 “ ! 丫 + 黔风只 “ ` 一 ’ ; “ · ) 0 , `任“ ; 践 ) O , ’ 任 Z ( 3 ) 对于情况 3 , 给出如下定义 : 定义设 d 是可行域 D 的极方向 , 如果满足 cd = O , 则称 d 为 ( L p ) 的最优极方向 . 由上面的讨论 , 可有 : 定理 l 若尸 , i 任 R C { l , 2 , … , k } 是 ( L p ) 的最优极点 , d , , j ` Z C { l , 2 , … , l } 是 ( L p ) 的最优极方向 , 则 ( L p ) 的最优解能表示为它的最优极点的凸组合与最优极方向的非负线性组合之和 , 即 ( 3) 式 . 2 最优极方向的存在性及求法求最优极点和判断最优极方向的存在性问题 , 可以用单纯形方法解决 , 即 : 定理 2 设尸是 ( L )P 的最优基本可行解 , 则 : ( l) 如果尸的所有非基变量的检验数都小于零 , 则尸是 (L p ) 的唯一最优极点 , 且 ( L p ) 无最优极方向 . ( 2) 如果 X ” 的非基变量有零检验数 , 且某个零检验数对应的列中有正数 , 则只要主元所在行的基变量值不为零 , 用单纯形法可求出不同于 X “ 的另一个最优极点 . ( 3) 如果 X0 的非基变量有零检验数 , 且所有零检验数对应的列的各行元素为系数、对应非基变量为变量组成的 m 个线性表达式小于等于零 (即线性不等式组 ) 有不全为零的非负解 , 则 ( L )P 存在最优极方向

北京科技大学学报 19 9 5 年 N O . 2 证 : 不失一般性 , 设 X0 对应的单纯形表为 : X a R H S S 夕0 0 … 0 夕。 , 十 l … 夕。川 + * ” ’ 夕。。 o y 一, 十 l x , 夕。 0 0 ( l) 已知 y oj 0 , j = 。 + 1 , … , ” , 故月 S 一 y 。挥 + , y 。 , X : > y 。因此 , X0 是 ( L p ) 的唯一最优解 , 当然也就无最优极方向 ( 2 ) 设 , 。 , + * 一。 , 且、 n }~ : , , . 十 * , 。不 - ( y 、二 + k J y 一, + k 得另一基本可行解 Xl = x( } , … , 式) T , 其中川变为非基变量 , ( 3 ) 设夕0j = o , j = 。 + l , … , m + k ; 夕。, 0 . 则以夕1 , + * 为主元换基所以有 X , 并尸 . … , n . 如果线性不等式组龙 “ , “ ’ , 次 ( 4 ) 了 = m + l y ` ] x , 蕊 0 有不全为零的非负解 : x , = y , j = 川 + l , … , m + k d = ( 一艺产 lj y , , ” ” m + k , 一菩 + 产 , 了 y , , , 川 · 1 , 一 y 川 + * , 0 , … , 0 ) J = 用 + 为 ” 的极方向 · 且 cd 一 , 一菩 + l yoj yj 一 O · 即 “ 是 ( L ” ’ 的最优极方向 · 下面指出线性不等式组 ( 4) 是否有不全为零的非负解的几种明显的情况 (并不是全部情况 ) : 情况 a 若对某个 i , y 。 > o , j 一 m 十 1 , … , m + 从或存在 { m + 1 , … , m + 日的一个子集 R , 有 iy , 二 0 , 厂 R , 只 , > 0 , j 任 { 。 + 1 , … , 。 + 料 \ R , 而对某个 l 笋 i 有 y 。 > 0 , j 任 R , 则不等式组 ( 4) 只有零解 , 即 ( L p ) 不存在最优极方向 . 情况 b 若有有最优极方向 d = m + l , … , , + 、 } 的某个非空子集尺 , 使艺夕。簇 o , i = 1 , 2 , … , m . 则 ( L p ) ( y l , … , 夕。 ) T . y o i 二 1 , 2 , … , 次 i任 R i任王。 + l , … , 。 + k } \ R 011 艺尽丈`l之其中 y 一例 l , 设 ( L p ) 为 : m i n s = 5 + x s x l + x s 一 Z x s = l x Z + x s + x 6 + 2 x 7 + x s = 2

V b l . 1 7 N b . 2 周汉良线性规: 划问题最优解的表示 · 1 1 8 · 3 x + s 一 x 2 x 6 + x 7 + 3 s = x 2 一 xs 4 一x x 6 + 厂 x Z x : = 4 符合定理的 2 ) ( 2 , 除了最估极点 Xl = ( 1 , 2 , 2 , 4 , O , 0 , 0 , O) T 外 , 用单纯形法可求出另外 3 个最优极点 : r = ( 0 , 3 , l , 5 , l , O , 0 , 0 )T , X , = ( 0 , 0 , 7 , 8 , l , 3 , O , 0 )T , X 4 = ( 0 , O , 0 , 19 / 5 , l , l / 5 , 7 / 5 , O丫 . 再考察相应的不等式组 ( 4) : { x s ( 0 一 x s + x 6 + 2 x 7 ( 0 x s 一 2 x 6 + x 7 毛 0 一 x s 一 x 6 + x 7 成 0 由第 1 、第 2 式看出属情况 :a 由第 l 式 x s = 0 , 代人第 2 式 x 6 + x 7 簇 0 , 得 x 6= x 产 0 . 故不存在最优极方向 . 所以该问题的最优解为 : x 一艺* ` x l , 艺又i 一 l , 又i ) o , 2 , 3 , 4 例 2 , 设 ( L p ) 为 : m i n s = 6 一 x 3 一 x 4 + Z x s 一 x 6 + 4 x 7 5 . t . x 一 + Z x ` 一 4 x s + x 6 一 2 x 7 = 2 x Z + 3 x 3 + Z x ; 一 7 x s + 4 x 6 一 3 x , = 1 0 x 3 + x 一 2 x 5 + x 6 一 x 7 + x s = 3 x , ) 0 , j = 1 , … , 8 经单纯形法迭代化为 : m i n s = 3 + 3 x 7 + x s 5 . t . x 一 + 2 x 4 一 4 x s + x 6 一 2 x 7 = 2 x Z 一 x 4 一 x s + x 6 一 3 x : = l x 3 + x 4 一 Z x s + x 6 一 x 7 + x s = 3 x , ) 0 , j = l , … , 8 除了最优极点 x , = ( 2 , 1 , 3 , o , o , o , 0 , 0 ) T 外 , 因丸、 x 6 的检验数为零 , 且对应列有正数 , 非退化 , 用单纯形法可求出另两个最优极点 : 矛 = ( o , 2 , 2 , l , O , o , 0 , 0 ) T , x , = ( l , O , 2 , O , 0 , l , 0 , 0 ) T . 求最优极方向对应的不等式组 ( 4) 为 : 2 x 4 一 4 x s + x 6 簇 0 一 x 4 一 x s + x 6 ( O x ; 一 2 x 5 + x 6 簇 O 属情况 b . 属笋 , ` 0 , d : = ( 2 , 2 , 优解为 : { 4 , 5 , 6 } 有 4 个非空子集 R l = { 5 } , R Z = { 4 , 5 } , R 3 = { 5 , 6 } , R 4 = { 4 , 5 , 6 } , 使得 : i = l , 2 , 3 , k = l , 2 , 3 , 4 . 对应有 4 个最优极方向 : d , = ( 4 , l , 2 , 0 , l , 0 , O , O) T , l , l , l , 0 , 0 , 0 ) T , d 3 = ( 3 , O , l , 0 , l , l , 0 , 0 ) , d 4 = ( l , l , 0 , l , l , l , 0 , O ) . 该问题的最 3 4 X 一落 1 “ ` X ’ 十万 , “ , d , 艺又 : = 1 ; 又 ` ) 0, , 2 , 3 ; 拜, ) O , j = l , 2 , 3 , 4 (下转 18 6 页 )

·186 北京科技大学学报 1995年No.2 准加以确定· 3.4综合评价企业的经济效益迄今为止的企业产值的计算（国民生产总值的计算也同样），只是局限在企业内部投人产出的成本、收人的计算，如果考虑环保因素和企业的外部因素，则传统的产值计算法是不合理的·比如说，林业部门每年采伐的树木，采伐多少都计算到国民生产总值中去，而没有计算由于采伐可能引起的水土流失，生态环境的破坏，又如钢厂的产值总是以产钢量的多少来计算产值的，而没有计算钢厂排出的废气、废水造成的污染所带来的损失及治理污染的投入·德国经济学家韦曼教授在他的新著作中探讨了企业外部效应的计算方法【. 若钢厂的生产函数受钢厂的自变量劳动力、资源的影响，而鱼场的生产函数除了受其资源和劳动力影响之外，还受到钢厂废水量的影响，也可以说受到钢厂产量的影响，因为钢厂的污水量与钢产量是成正比的，于是传统的Cobb-Douglas生产函数应该改写为： Q=AKku 式中，x、a小K、.≥0,4十xk+x。≤1，：环境因素，A:劳动力，K:资本，a:产出弹性系数· 可以利用这种模型进一步探讨，如何考虑受环境因素影响的外部效应，运用生产函数定量评价企业的有效生产问题· 4结束语用环境保护思想对成本理论加以改进，赋子企业生产成本以新的内涵·从防止污染的角度出发，可以只考虑产品和污染物；从节约利用有限的自然资源的角度出发，有些中性物如水资源的消耗也应算作成本，只有这样才能使成本核算更好地为决策服务· 参考文献 1 Dyckhoff H.Betriebliche Produktion.Springer-Lehrbuch,1992.30~50 2 Weimann.Umweltokonomik,2.Auflage.Springer-Lehrbuch,1991.23~25 (上接181页) 参考文献 1 Bazaraa M S,Jarvis JJ.Linear Programming and Network Flows.New York:John Wiley and Sons,1977 2 Laston L S.Optimization Theory for Large Systems.New York:Macmillan,1970

1 86 北京科技大学学报 199 5 年 N o . 2 准加以确定 . .3 4 综合评价企业的经济效益迄今为止的企业产值的计算 ( 国民生产总值的计算也同样 ) , 只是局限在企业内部投人产出的成本、收人的计算 . 如果考虑环保因素和企业的外部因素 , 则传统的产值计算法是不合理的 . 比如说 , 林业部门每年采伐的树木 , 采伐多少都计算到国民生产总值中去 , 而没有计算由于采伐可能引起的水土流失 , 生态环境的破坏 . 又如钢厂的产值总是以产钢量的多少来计算产值的 , 而没有计算钢厂排出的废气、废水造成的污染所带来的损失及治理污染的投人 . 德国经济学家韦曼教授在他的新著作中探讨了企业外部效应的计算方法 2[] . 若钢厂的生产函数受钢厂的自变量劳动力、资源的影响 , 而鱼场的生产函数除了受其资源和劳动力影响之外 , 还受到钢厂废水量的影响 , 也可以说受到钢厂产量的影响 , 因为钢厂的污水量与钢产量是成正比的 , 于是传统的 C o b b 一 D o u g l as 生产函数应该改写为 : Q = : 。 A “ · 兀二。 · 。式中 , , 、 : , 、 : 、、 : 。妻 o , : , + : 、 + : 。毛 l , u : 环境因素 , A : 劳动力 , K : 资本 , , : 产出弹性系数 . 可以利用这种模型进一步探讨 , 如何考虑受环境因素影响的外部效应 , 运用生产函数定量评价企业的有效生产问题 . 4 结束语用环境保护思想对成本理论加以改进 , 赋予企业生产成本以新的内涵 . 从防止污染的角度出发 , 可以只考虑产品和污染物 ; 从节约利用有限的自然资源的角度出发 , 有些中性物如水资源的消耗也应算作成本 , 只有这样才能使成本核算更好地为决策服务 . 参考文献 D y e k h o f H . B e t r i e b li c h e P r o d u k t i o n . S P r i n g e r 一 L e h r b u e h , 19 9 2 . 30 一 5 0 2 W e i m a n n . U m we l t 6 k o n o m ik , 2 . A u fl a g e . S P r i n g e r 一 L e h r b u e h , 1 9 9 1 . 2 3 一 2 5 (上接 1 8 1 页 ) 参考文献 1 B a z a r a a M S , J a r v i s J J . L i n e a r P r o g r a m m i n g a n d N e t w o r k F l o w s . N e w Y o r k : J o h n w il e y a n d S o ns , 1 9 7 7 2 L a s t o n L S . O P t i m i z a ti o n T h e o r y fo r L a r g e S y s t e ms . N e w Y o r k : M a c m il l a n , 19 70