无界凸多面体由_和形式_向_交形式_的转化

1、无界凸多面体由“和形式”向“交形式”的转化魏权龄1 , 汪俊1 , 闫洪2(1. 中国人民大学运筹学与数量经济研究所, 北京 100872; 2. 香港理工大学商学院, 香港)摘要: 凸多面体可以表示成一组线性不等式的交, 称这种表示为凸多面体的“交形式”; 同时, 它也可以由其全部极点和对应的凸多面锥的全部极方向生成, 称之为“和形式”. 将一个凸多面体在“和形式”与 “交形式”之间进行转化是数学规划中的一个基本问题. 本文使用类似线性规划中的“大M 2方法”, 构造 性地将无界凸多面体“和形式”的凸多面体转化为“交形式”, 并用数值例子说明了该算法的应用过程.关键词:无界凸多面体; “和形

2、式”; “交形式”; “大M 2方法”中图分类号: O 221文献标识码:AT h e M e tho d o f T ran sfe r r in go f Sum 2fo rm to It sth e U n bo u n ded Po lyh ed ro nIn te r sec t io n 2fo rmW E I Q u an 2lin g1 , W A N G J u n 1 , YA N H o n g2( 1. In st itu te o f O p e ra t io n s R e sea rch and M a th em a t ica l E co nom ic s

3、, R enm in U n ive r sity o f C h ina, B e ijing 100872, C h ina;2.F acu lty o f B u sine ss, T h e H o ng Ko ng Po ly tech n ic U n ive r sity, H ung H om , Kow loo n, H o ng Ko ng, C h ina)A bstrac t: A po lyh ed ro n can be rep re sen ted by a se t o f linea r co n st ra in t s, w h ich w e ca ll

4、“in te r sec t io n2 fo rm ”, o r by a co nvex com b ina t io n o f f in ite ex t rem e po in t s and no n 2nega t ive com b ina t io n o f f in ite ex2 t rem e ray s, w h ich w e ca ll“sum 2fo rm ”. T o t ran sfe r a po lyh ed ro n be tw een th e“sum 2fo rm ”and th e“in2 te r sec t io n2fo rm ”is a

5、 fundam en ta l p ro b lem in th e m a th em a t ica l p ro g ramm ing. T h is p ap e r supp lie s am e tho d o f t ran sfe r r ing th e unbo unded po lyh ed ro n o f sum 2fo rm to it s in te r sec t io n2fo rm by u sing th e “B ig2M M e tho d”. N um be r ica l exam p le is a lso g iven to dem o n s

6、t ra te th e p ro ce sse s o f o u r t ran sfe r r ing a l2 go r ithm.Key words: unbo unded po lyh ed ro n; “Sum 2fo rm ”; “in te r sec t io n2fo rm ”; “B ig2M M e tho d”前言考虑凸多面体1P = x | a i x bi ,x 0, i = 1, 2, , m 其中x = (x 1 , x 2 , , x n ) T E na Ti = (a i1 , a i2 , , a in )Tn E , i = 1, 2, , mbi

7、 E 1 , i = 1, 2, , m一般, 上述有限多个不等式所确定的凸多面体 P 被称为“交形式”. 由凸多面体分解定理 ( 见 1) 可知, 它 也可由其全部极点和相应凸多面锥的全部极方向生成, 即:kkk 6d i i | 66y j j | j Q =i =1,i 0, i = 1, 2, , k +0, j = 1, 2, , k i= 1i= 1j = 1其中 d i E n , i= 1, 2, , k 是凸多面体的 k 个极点; y j E n , j = 1, 2, , k 是凸多面锥 y | a i y 0, y 0, i= 1, 2, , m 的 k 个极方向. 这种

8、表示被称为凸多面体的“和形式”.特别, 当 Q 为有界凸多面体时, 可以表示成其全部极点的凸组合, 即kk6d i i | 6i =Q =1,i 0, i = 1, 2, , ki= 1i= 1当 Q 为凸多面锥时, 可以表示成其全部极方向的非负组合, 即k 6y j j | j 0, j = 1, 2, , k Q =j = 1将凸多面体在两种形式之间转化的算法是数学规划中的一个重要而基本的问题. 凸多面体由“交形式”向“和形式”的转化即求一个“交形式”凸多面体的全部极点及对应的凸多面锥的极方向. 许多文献, 如文献2 - 6等都提出了转化的算法, 但在处理退化问题时, 通常会比较复杂. 我

9、们提出了一种递归算法, 有效地避免了因退化带来的麻烦7- 10 . 在数学规划中, 这种转化具有广泛的应用11- 13 .将 凸多面体由“和形式”向“交形式”转化是上述问题的逆问题. 若能将一个凸多面体由“和形式”转 化为“交形式”, 即可知道一个凸多面体顶点及极方向的性质和结构. 在数据包络分析 (D EA , D a ta E n ve l2 opm en t A n a ly sis) 中, 可以利用这种转化研究生产前沿面的结构7, 9 . 对凸多面体结构的研究还可以用来 得到线性多目标规划有效解的结构14 .文 献 8 给出了有界凸多面体及凸多面锥由“和形式”向“交形式”转化的方法,

10、并用凸集分离定理对 相关的结论进行了证明. 本文考虑将无界凸多面体由“和形式”转化为“交形式”. 我们使用类似线性规划中 的“大2M 方法”, 构造性地将“和形式”的凸多面体转化为“交形式”, 并对相关的结论进行了证明. 最后文章给出了一个数值例子演示了该方法的应用过程.2凸多面体由“和形式”向“交形式”的转化考虑“和形式”的无界凸多面体 Q :kkk 666j 0, j = 1, 2, , k d i ii = 1, i y j jQ =0, i = 1, 2, , k+i= 1i= 1j = 1其中 d i E n , i= 1, 2, , k 是 E n 中的 k 个点; y j E n

11、 , j = 1, 2, , k 是 E n 中的 k 个方向. 构造集合 S (M ) 0 是一个很大的数. 可知 S (M ) 是 E n+ 1 中的一个凸多面锥, 它可以表示成其全部极方向的非负组合 (求凸多面锥全部极方向的算法可见文献7 - 10). 设 S (M ) 的全部极方向为l = 1, 2, , ma l (M ) T , bl (M ),T由文献7 ,有ma l (M )6S (M ) =l 0, a l (M ) E n , bl (M ) E 1 , l = 1, 2, , m(2)ll= 1 bl (M )由文献8 ,可知Q (M ) =a T (M )x bl (M

12、 ) , l = 1, 2, , mxl有下面的定理.定理 1对M 0 有 Q (M ) 0, 有kk k 66 6d i i +(d i +M y j ) ijQ (M ) =i 0, i = 1, 2, , k;i= 1i= 1 j = 1kk k66 6ij 0,i =1, 2, , k ,j = 1, 2, , k ;i +i j =1i= 1i= 1 j = 1kkk kk 666M 66d i i +d i ij +y j i j=i 0, i =1, 2, , ki= 1i= 1 j = 1i= 1 j = 1kkk 666ij 0,i = 1, 2, , k , j = 1,

13、2, , k ;i +ij = 1 .i= 1i= 1 j = 1kk k k66+ M 6y j (6ij )d i (i +ij )i =0, i = 1, 2, , k;i= 1j = 1j = 1 i= 1kk k66 6ij 0, i = 1, 2, , k , j = 1, 2, , k ;i +i j = 1i= 1i= 1 j = 1 Q得证.引理 1对 0 M M , 有 Q (M ) Q (M ).证明对 0 M M , 易见 (0, 1) 有d i + M y j = d i + (1 - ) (d i + M y j ) ,从而 Q (M ) 0 使得 x Q (M 0

14、 ).k对任意 x 0 Q , 存在 i 0 0, 6 0 = 1, 0 0,证明i= 1,k 2, ,k; j = 1, 2, , k ,使得iji= 1kx 0 =d i 0 +66y j 0.iji= 1j = 1k 1 61j0 , 则不妨设 1 0 0, 令M 0 =0 0, 0 =0 j = 1jjM01kk kk k1 66660 =0 +0 =0 +0 =i +1(3)jiji1M 0 j = 1i= 2j = 1i= 2i= 2故kk kk 6666x 0 =d i 0 +y j 0 =d i 0 +d 1 0 +y j 0iji1ji= 1kj = 1i= 2j = 1k

15、k d 1 ( 1 666d i 0 +0 ) +y jM 0 0=ijjM 0k i= 2kj = 1j = 1k kk 6d 1 6666d i 0 +0 +M 0 y j 0 =d i 0 +(d 1 + M 0 y j ) 0=ijjiji= 2j = 1j = 1i= 2j = 1由 (3) , 可得 x 0 Q (M 0 ). 得证.由定理 1, 定理 2 及引理 1,定理 3对M 0, 有容易得到如下定理.Q = Q (M ) = lim Q (M )使用“大M 2方法”构造出 S (M ) 后, 通过求凸多面体全部极方向的方法即可得到集合 Q (M ).M M 0上述定理表明,

16、 当M 时, Q (M ) = Q. 这实际上给出了一种将无界凸多面体由“和形式”向“交形式”转化的方法.数值例子在本节中, 我们用一个例子演示将一个一般的凸多面体由“和形式”向“交形式”转化.考 虑一个凸多面体 Q E 2 , Q 有两个极点 (0, 0) T , (0, 1) T 和两个极方向 ( 1, 0) T , ( 1, 1) T , 即 Q 具有下 面的“和形式”300011110Q =1 +21 + 2 = 1, 1 0, 2 0 +1 +21 0, 2 0依式 (1) 构造集合 S (M ) E 3 如下00M M M M01M0M +1x 1x 2x 3x 1x 2S (M

17、) = x 31其 中 M 是一个很大的数. S (M ) E 3 是一个凸多面锥. 由 10可求得 S (M ) 的全部极方向为 ( 1, 0, 0) T ,(0, 1, 0) T , (- 1, 0, - M ) T , (1, -1, - 1) T ,1, - M - 1) T , 从而(0, -100010-0-11-0-S (M ) =i 0, i = 1, 2, , 51 +2 +3 +114 +1M -5M1于是x 1x 2Q (M ) =x 1 x 2 0, x 1 M , x 1 - x 2 - 1, x 2 M + 10,当M + 时, 有x 1x 2lim Q (M )

18、= Q =M x 1 0, x 2 0, x 1 - x 2 - 1,即为本例中 Q 的“交形式”. 如图 1 所示.图 1参考文献:12D an tzig G B. L inea r P ro g ramm ing and E x ten sio n M . P r ince to n U n ive r sity P re ss, 1963.A v is D , F uk uda K. A p ivo t ing a lgo r ithm fo r co nvex h u lls and ve r tex enum e ra t io n o f a r rangem en t s and

19、 po lyh ed raJ . D isc re te Com p u ta t io na l Geom e t ry,1992, 8: 295- 313.34B a lin sk iM L. A n a lgo r ithm fo r enum e ra t ing a ll ve r t ice s o f a co nvex po lyh ed ra J . Com p u t ing, 1975, 15: 181- 193.C h a rne s A , Coop e r W W , H uang Z M , Sun D B. R e la t io n s be tw een h

20、 a lf2sp ace and f in ite ly gene ra ted co ne s in po ly2h ed ra l co ne2ra t io D EA m o de ls J . In te rna t io na l Jo u rna l o f Sy stem Sc ience,1991, 22: 2057- 2077.5D ye r M E. T h e com p lex ity o f ve r tex enum e ra t io n m e tho d sJ . M a th em a t ic s o f O p e ra t io n s R e sea

21、 rch , 1983, 8: 381-402.G reenbe rg H. A n a lgo r ithm fo r de te rm in ing redundan t inequa lit ie s and a ll so lu t io n s o n po lyh ed ra J . N um e r ica l6M a th em a t ic s,1975, 24: 19- 26.W e i Q L , Yan H. A m e tho d o f t ran sfe r r ing co ne s o f in te r sec t io n2fo rm to co ne s

22、 o f sum 2fo rm and it s app lica t io n s in da ta enve lopm en t ana ly sis m o de lsJ . In te rna t io na l Jo u rna l o f Sy stem s Sc ience, 2000, 31 (5) : 629- 638.W e i Q L , Yan H. A m e tho d o f t ran sfe r r ing po lyh ed ro n be tw een th e in te r sec t io n2fo rm and th e sum 2fo rm J . Com 278p u te r s and M a th em a t ic s w ith A pp lica t io n s,2001, 41: 1327- 1342.9W e i Q L , H ao G, Yan H. C h a rac te r ist ic s and co n st ruc t io n m e tho d o f su rface and w eak su rface o f D EA p ro