線形計画法を用いた区分的線形回路の全解探索法

山村 清隆  田中 茂  

誌名
電子情報通信学会論文誌 A   Vol.J83-A   No.8   pp.965-975
発行日: 2000/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 回路理論,回路解析
キーワード: 
区分的線形回路,  回路解析,  全解探索,  線形計画法,  

本文: PDF(365.8KB)>>
論文を購入




あらまし: 
区分的線形回路のすべての解を求める方法として,LPテストを用いたアルゴリズムが知られている.LPテストとは与えられた領域の中に方程式の解が存在しないことを線形計画法(単体法)を用いて確認するもので,このテストを用いて解の存在領域を絞り込んでいくことにより,非常に効率良くすべての解を求めることができる.本論文では,このようなLPテストアルゴリズムの計算効率を飛躍的に改善する手法を提案する.本手法は,単体法のタブローを修正・再利用し,LPテストを主として単体法のフェーズIIで行うことにより,LPテストにおけるピボット演算回数を大幅に減少させるものである.それにより従来のアルゴリズムと比べて計算時間の飛躍的な短縮が可能となり,200変数,線形領域数 10200 という超大規模問題の全解探索にも成功している.