无界凸多面体由“和形式”向“交形式”的转化魏权龄1,汪俊1,闫洪(1.中国人民大学运筹学与数量经济研究所,北京100872;2.香港理工大学商学院,香港)摘要:凸多面体可以表示成一组线性不等式的交,称这种表示为凸多面体的“交形式”;同时,它也可以由其全部极点和对应的凸多面锥的全部极方向生成,称之为“和形式”.将一个凸多面体在“和形式”与“交形式”之间进行转化是数学规划中的一个基本问题.本文使用类似线性规划中的“大M2方法”,构造性地将无界凸多面体“和形式”的凸多面体转化为“交形式”,并用数值例子说明了该算法的应用关键词:无界凸多面体;“和形式”;“交形式”;“大M2方法”:O221文献标识码:ATheMethodofTransferringofSum2formtoItstheUnboundedPolyhedronIntersection2formWEIQuan2ling1,WANGJun1,YANHong2(1.InstituteofOperationsResearchandMathematicalEconomics,RenminUniversityofChina,Bei激ng100872,China;2.FacultyofBusiness,TheHongKongPolytechnicUniversity,HungHom,Kowloon,HongKong,China)Abstract:Apolyhedroncanberepresentedbyasetoflinearconstraints,whichwecall“intersection2form”,orbyaconvexcombinationoffiniteextremepointsandnon2negativecombinationoffiniteex2tremerays,whichwecall“sum2form”.Totransferapolyhedronbetweenthe“sum2form”andthe“in2tersection2form”isafundamentalprobleminthemathematicalprogramming.Thispapersuppliesamethodoftransferringtheunboundedpolyhedronofsum2formtoitsintersection2formbyusingthe“Big2MMethod”.Numbericalexampleisalsogiventodemonstratetheprocessesofourtransferringal2gorithm.Keywords:unboundedpolyhedron;“Sum2form”;“intersection2form”;“Big2MMethod”前言考虑凸多面体1P={x|aixΕbi,xΕ0,i=1,2,⋯,m}其中x=(x1,x2,⋯,xn)T∈EnaTi=(ai1,ai2,⋯,ain)Tn∈E,i=1,2,⋯,mbi∈E1,i=1,2,⋯,m一般,上述有限多个不等式所确定的凸多面体P被称为“交形式”.由凸多面体分解定理(见1)可知,它也可由其全部极点和相应凸多面锥的全部极方向生成,即:kkk′6diΚi|66yjΒj|ΒjΕQ=Κi=1,ΚiΕ0,i=1,2,⋯,k+0,j=1,2,⋯,k′i=1i=1j=1其中di∈En,i=1,2,⋯,k是凸多面体的k个极点;yj∈En,j=1,2,⋯,k′是凸多面锥{y|aiyΕ0,yΕ0,i=1,2,⋯,m}的k′个极方向.这种表示被称为凸多面体的“和形式”.特别,当Q为有界凸多面体时,可以表示成其全部极点的凸组合,即kk6diΚi|6Κi=Q=1,ΚiΕ0,i=1,2,⋯,ki=1i=1当Q为凸多面锥时,可以表示成其全部极方向的非负组合,即k′6yjΒj|ΒjΕ0,j=1,2,⋯,k′Q=j=1将凸多面体在两种形式之间转化的算法是数学规划中的一个重要而基本的问题.凸多面体由“交形式”向“和形式”的转化即求一个“交形式”凸多面体的全部极点及对应的凸多面锥的极方向.许多文献,如文献2-6等都提出了转化的算法,但在处理退化问题时,通常会比较复杂.我们提出了一种递归算法,有效地避免了因退化带来的麻烦7-10.在数学规划中,这种转化具有广泛的应用11-13.将凸多面体由“和形式”向“交形式”转化是上述问题的逆问题.若能将一个凸多面体由“和形式”转化为“交形式”,即可知道一个凸多面体顶点及极方向的性质和结构.在数据包络分析(DEA,DataEnvel2opmentAnalysis)中,可以利用这种转化研究生产前沿面的结构7,9.对凸多面体结构的研究还可以用来得到线性多目标规划有效解的结构14.文献8给出了有界凸多面体及凸多面锥由“和形式”向“交形式”转化的方法,并用凸集分离定理对相关的结论进行了证明.本文考虑将无界凸多面体由“和形式”转化为“交形式”.我们使用类似线性规划中的“大2M方法”,构造性地将“和形式”的凸多面体转化为“交形式”,并对相关的结论进行了证明.最后文2凸多面体由“和形式”向“交形式”的转化kkk′666ΒjΕ0,j=1,2,⋯,k′diΚiΚi=1,ΚiΕyjΒjQ=0,i=1,2,⋯,k+i=1i=1j=1其中di∈En,i=1,2,⋯,k是En中的k个点;yj∈En,j=1,2,⋯,k′是En中的k′个方向.构造集合S(M)<En+1:TT{di}TxΕ(di+Myj)xΕxxn+1xn+1,xn+1,S(M)=x∈En,i=1,2,⋯,k;j=1,2,⋯,k′记kkk′666diΚi+(di+Myj)Q(M)...
