辺容量付き電力需給ネットワーク

丸田 真平  西関 隆夫  
(学生論文特集秀逸論文)

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.3   pp.333-342
発行日: 2015/03/01
Online ISSN: 1881-0225
論文種別: 特集論文 (学生論文特集)
専門分野: 情報・システム基礎
キーワード: 
アルゴリズム,  ,  最大供給率問題,  パラメトリックネットワーク,  分割問題,  

本文: FreePDF(656.7KB)


あらまし: 
辺容量付き電力需給ネットワークはグラフGで表現できる.Gの各点は供給点あるいは需要点であり,供給量あるいは需要量が割当てられており,各辺には辺容量が割当てられている.パラメトリックネットワークでは,供給量,需要量及び辺容量は変数λの関数である.各需要点は,丁度一つの供給点からグラフGの辺を通してその需要量だけの“電力”を受け取りたい.一方,各供給点は,幾つかの需要点へGの辺を通して“電力”を送ることができるが,送る電力の合計はその供給量以下である.無論各辺を流れる電力フローはその辺の容量以下でなければならない.このようなことが可能かどうか調べたい.また不可能ならば,全ての需要量を一様にr(0 ≤ r < 1)倍に減少させて,そのようなことを可能にしたい.このようなrの最大値r*を求めたい.本論文では,木であるグラフGに対してこれらの問題を解くアルゴリズムを与える.