最小コストフローアルゴリズムに基づく管路網解析問題の一解法
スポンサーリンク
概要
- 論文の詳細を見る
上水道の管路網において運用の策定を実施する際,効率的な管路網解析手法が必要である.本文では,管路網に代表される凸な非線形特性を有するネットワークの最適化手法の一つであるPrimal-Dual法の計算量の効率化を提案した.Primal-Dual法は,管路の流量-圧力特性を階段状に近似した後,最小コストフローを求めるアルゴリズムであり,ネットワークの構造(接続関係)情報を利用して計算を効率的に実行する.そのアルゴリズムでは,計算の繰り返しごとにネットワークの最短径路木を求めている.本文では,階段状に近似するときに制約を加えることで,毎回の最短径路木の変化が1回の木の初等変換である性質を示した.この性質を利用して,最短径路木を求める計算時間を削減するアルゴリズムを提案した.その結果,1回の最短径路木を求める操作は,問題の規桟(節点数十枝数)に比例する手間であることを示した.計算実験結果からも,提案したアルゴリズムの効果が確かめられた.本文で提案したアルゴリズムは,管路網の例で代表されるネットワーク上で非線形凸関数の段適化を行う問題に適用できるアルゴリズムである.
- 一般社団法人情報処理学会の論文
- 1988-11-15
著者
関連論文
- ゲート敷き詰め型ゲートアレイ用配置アルゴリズム
- 階層クラスタリング手法を用いたゲートアレイ配置手法
- 条件分岐に対する演算器の共用と制御論理生成の一手法
- 複雑な制御構造を持つアルゴリズムからの高速なステートマシン合成手法
- 信号値の変化に着目したテスト生成手法
- ハイレベルシンセシスの動向 (回路自動合成と最適化論文特集)
- 多層チャネルルータ
- 最小コストフローアルゴリズムに基づく管路網解析問題の一解法
- ネットワ-ク問題におけるシンプレックス法--LSIコンパクション問題の一考察 (ネットワ-ク問題論文)
- 規則構造に注目したLSI機能ブロックの自動生成
- 水運用計画における予測問題とタンクモデル
- 区分線形近似による管網解析手法
- 配電系障害復旧計画システムの基本方式