最小コスト多種フロー問題のT-領域

黒沢　馨 

誌名
電子情報通信学会論文誌 A  Vol.J65-A  No.9  pp.942-948
発行日: 1982/09/20
Online ISSN: 
Print ISSN: 0373-6091
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(476.6KB)

あらまし: 
最小コスト多種フロー問題のT−問題とは，総コストの上限が与えられた場合，その上限以下で流すことが可能な要求フローベクトルの領域を求める問題をいう．本問題はその重要性にもかかわらず，従来，考察されていなかった．本文は多種フロー問題用に開発された効率の良い線形計画法の一手法であるColumn generationの技法を用い，その領域が求まることを示すものである．本問題を線形計画法によって定式化した場合の最適基底解におけるシンプレックス乗数を用いたコストカット条件という一時不等式を新たに導入する．弱双対定理を利用することにより，T−領域は有限個のコストカット条件によって囲まれた凸領域となることが示される．さらに，「要求フローの微小変化に対する総コストの変化の大きさ」が，コストカット条件を用いて定量的に求まることを示す．また，最大多種フロー問題のT−領域が，従来の枝容量の消費−供給という考えを使わず，弱双対定理を利用して求めることも可能であることを示す．