2次目的関数の最適配分問題の考察とそのアルゴリズム

概要

論文の詳細を見る
本論文では一つの資源総使用量制約と各配分量の上下限制約、2次目的関数の最適配分問題(APQと略す)について考察している。APQは配分問題の中では最も基本的な問題の一つであるが、より一般的な配分問題の部分問題となっており、この問題を詳細に調べることは重要である。APQに対して、ラグランジュ緩和法を適用すれば、ラグランジュ関数の変数分離形から双対関数D(λ)を陽に求めることができ、D(λ)の微分可能性から双対変数が最適解において満すべき方程式、δ(λ)=B、を導くことができる。(但し、Bは資源の総量)本論文で得られた結果の一つは、非減少線型区分関数δ(λ)の性質に関するものである。すなわち、δ^0(λ)=BをAPQから配分量の上下限制約を取り除いた問題から得られたλが満すべき方程式とする。このとき、性質1、δ(λ)とδ^0(λ)の関係は、問題により決まるパラメータαとβの大小により区間〔α、β〕で一致する、又は、〔β、α〕の一点λにおいて交わる、のいずれかである。性質2、δ(λ)は非減少線型区分関数であり、λ〓βにおいて凸、λ≧αにおいて凹の関数である。さらに、線型区分関数δ(λ)の各セグメントの方程式を決定する添字集合を計算する漸化式を与えている。得られたもう一つの結果は、上述の性質を利用して三つのアルゴリズムを提案し、数値計算によりその効率を確かめたことである。計算結果によれば、100変数で約8ミリ秒であり、計算時間はほぼ変数の数に比例している。
社団法人日本オペレーションズ・リサーチ学会の論文

2次目的関数の最適配分問題の考察とそのアルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク