中国电机工程学报
中國電機工程學報
중국전궤공정학보
ZHONGGUO DIANJI GONGCHENG XUEBAO
2012年
10期
134-141
,共8页
林济铿%王旭东%李胜文%吴鹏%邵广惠%徐兴伟%马新
林濟鏗%王旭東%李勝文%吳鵬%邵廣惠%徐興偉%馬新
림제갱%왕욱동%리성문%오붕%소엄혜%서흥위%마신
图分割%含连通图约束的背包问题%含图约束的背包问题%近似算法%电力系统最优主动解列
圖分割%含連通圖約束的揹包問題%含圖約束的揹包問題%近似算法%電力繫統最優主動解列
도분할%함련통도약속적배포문제%함도약속적배포문제%근사산법%전력계통최우주동해렬
图分割技术(网络分割技术)在互联网研究、交通运输、电网故障诊断和电力系统解列等方面有着重要的意义.首次建立一个新的图分割问题——含连通图约束的背包问题(connected graph constrained knapsack problem,CGKP),并提出其有效近似算法.引入与图连通性相关的4个新节点集合,证明这些新节点集合的性质,并提出这些节点集合的搜索方法;结合新节点集合的性质及搜索算法,通过对含图约束的背包问题近似算法进行扩展,提出求解 CGKP 的近似算法,并讨论此算法的计算复杂性.算例结果证明了该算法的有效性.因电力系统主动最优解列问题在一定条件下可归结为一个 CGKP,该研究成果为电力系统最优主动解列断面搜索问题的求解奠定了理论基础.
圖分割技術(網絡分割技術)在互聯網研究、交通運輸、電網故障診斷和電力繫統解列等方麵有著重要的意義.首次建立一箇新的圖分割問題——含連通圖約束的揹包問題(connected graph constrained knapsack problem,CGKP),併提齣其有效近似算法.引入與圖連通性相關的4箇新節點集閤,證明這些新節點集閤的性質,併提齣這些節點集閤的搜索方法;結閤新節點集閤的性質及搜索算法,通過對含圖約束的揹包問題近似算法進行擴展,提齣求解 CGKP 的近似算法,併討論此算法的計算複雜性.算例結果證明瞭該算法的有效性.因電力繫統主動最優解列問題在一定條件下可歸結為一箇 CGKP,該研究成果為電力繫統最優主動解列斷麵搜索問題的求解奠定瞭理論基礎.
도분할기술(망락분할기술)재호련망연구、교통운수、전망고장진단화전력계통해렬등방면유착중요적의의.수차건립일개신적도분할문제——함련통도약속적배포문제(connected graph constrained knapsack problem,CGKP),병제출기유효근사산법.인입여도련통성상관적4개신절점집합,증명저사신절점집합적성질,병제출저사절점집합적수색방법;결합신절점집합적성질급수색산법,통과대함도약속적배포문제근사산법진행확전,제출구해 CGKP 적근사산법,병토론차산법적계산복잡성.산례결과증명료해산법적유효성.인전력계통주동최우해렬문제재일정조건하가귀결위일개 CGKP,해연구성과위전력계통최우주동해렬단면수색문제적구해전정료이론기출.
