主金子f 三士長圭謝王室会古・却rr.司王
日開 ~ 防Q\ ~ 弔~ It
Ill
J ~ 1~地 3ζ

J0R SJ

Vol.34, No.2
可 111111111111111111111111111111111111111111111111111 ・ H ・ 111111111111111111111111111111111111111111111111111111111 ・ '"11111111111111111111 ・ 1111111111111111111111111111111111111111111111111111111111111111111111111111111111'-;非凸関数の最小化技法による同時補給製品の最適発注政策の新解法
高千穂商科大学田中孝男

ンジュ乗数の探索ルーチンから織成されており，また上界算出のアルゴリズムは下界を得るときに算出されるラグランジュ子問題の解を用いた実行可能解の探索と貧欲Hanoi

Instituteo
fMathmaticsPhanThiem Thach ，上智大学鈴木誠道的な手法による改良ルーチンから構成される.
さらに提案したアルゴリズムの有効性を確認するために数値実験を行なう.立地候補地点が 25 ，需要地点が 100

在庫問題でよく知られた joint replenishment シス

テムの最適発注周期を求める問題は，特殊なタイプの 1変数非凸関数の最小化問題に変換できる.そこで従来の方法と違って，非凸関数の最小化という観点から解法の開発を試み， 2 つの解法を提案した.

1 つは successive

underestimation method と L 、 L 、 ，A/t+Bt

関数がもっ性質をうまく利用したもので，の型のまでの種々の問題に対する結果では下界と上界の相対比はすべて 1% 以内であり，また計算時間の増加も比較的穏やかであり，提案したアルゴリズムを用いることによって比較的大規模な問題に対して，ある程度の保証をもった解を短時間で得ることができることが示される.

建設時期を考慮した施設配置問題のー解法

効率の良い

一建設期間数が 2 の場合一underestimator を構成できる.もう l つは多変数の非東京理科大学桧垣正浩，西国重矩凸関数の最小化問題のために開発された relief indicaｭtor method を当該問題に適した形に修正したものであ

混合整数計画問題の代表的な問題である施設配置問題

る.この 2 つの解法の利点は，従来のヒェーリスチック

は，下界値計算，下界値の強化，分校方法などさまざまな解法と異なり，任意の許容誤差内に収まる大域解を得な研究により比較的大規模な問題も解けるようになってられる点にある.数値実験の結果でも，両者は共に良い結果を得ている.

さらにこの解法は，他のある績の問きた.しかし，問題構造が単純であるため，実際の問題に適用するにはし、ろいろな問題点が生じる.

本論文では，施設の供給上限制約の下で，最適な施設題，たとえばminimize (Clx) ・ (C2X)

S.t.

Ax=b , X;;;;Oの建設方法とその建設時期を求める施設配置問題の解法のような問題の解法に適用できることを指摘しておく.

アルゴリズムを提案する.本論文では凹型の費用関数をもっ施設配置問題に対すを考慮した施設配置問題を対象として分校限定法にもとるラグランジュ緩和を用いた解法
早稲田大学久保幹雄，春日井博

2 期の建設時期づいたアルゴリズムを提案している.また，問題を効率良く解くために，下界値計算，下界値強化法を工夫している.問題の拡張した部分を適切に表現できるネットワ

従来の立地問題では，生産量を増加させることによるークでモデル化し，下界値を計算している.本論文で提単価の減少，いわゆる規模の経済(エコノミー・オブ・案する解法アルゴリズムの有効性を示すために数値実験スケール)を，立地費用を国定および変動費に分けるこ

結果として演算時間，分枝回数，下界値計算回数などをとによって表現していた.本研究では，規模の経済をよ示している.

り現実的な表現にするために，生産費用および輸送費用が一般の凹関数である場合を考え，ラグヲンジュ緩和法を用いて，上界および下界を導くアルゴリズムを提案し先行順序制約をもっ巡回セールスマン問題
早稲田大学久保幹雄，春日井博ている.下界算出のアルゴリズムは，ラグランジュ子問本研究では，巡回セールスマン問題の一般化である先題を多項式時間で解く手法，ラグランジュ乗数の初期調

行順序制約を考慮した巡回セールスマン問題に対するア整法，および劣勾配法による最良の下界を与えるラグラルゴリズムについて考察している.

520 (42)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

本研究では，まず先行順序を制約として表現し，さらにこれら制約をラグランジュ緩和することによるいくつかの下界導出のアルゴリズムを構築している.このアルゴリズムは制限をつけた意味でのラグランジュ双対法であり，れた.

議員定数配分問題に対するパラメトリック除数法について
埼玉大学大山達雄

Balasand Christofides によって巡回セールスマン問題に適用され成功をおさめたものの拡張である.

議員定数配分問題は，これまで 200 年以上ものあいだまた，下界を組み込んだ分校限定法を構築している.こ

多くの応用数学者やオベレーションズ・リサーチの研究の手法には，変数固定のテスト先行順序を利用した分校者たちによって活発な研究がなされてきた問題で、ある.

ノレール，上界を求めるいくつかのヒューリスティックス

Balinski , Young の 2 人は，も導入されている.

広範囲にわたる業績を残している.

この問題に対して多くのノード数 49 までの問題に対する数値実験によれば，本本論文では，議員定数配分問題に対するー解法とし研究で示した分校限定法は，中規模の問題の最適解を求て，パラメトリック除数法を提起し，この解法がこれまめることが可能であること，計算時間の上昇は比較的ゆでに提起された多くの伝統的な方法を“統合"する方法るやかであることが示される.

であることを示す.まず，それぞれの選挙区への議員定GI/G/s 待ち行列の待ち時間に対する数配分に際して，安定領域という概念を導入し，多くの近似式議員定数配分方法と安定領域の概念との関係を明らかにする.次に議員定数配分方法を制約条件っき最適化問題

北海道大学木村俊一
待ち行列が生じる現実のシステムには，複数窓口待ちという観点から眺め，ここで提起したパラメトリック除数法に対応する最適化問題を示す.

行列モデルに帰着されるものが多い.なかでも，客のサ最後に，わが国の衆議院のデータを用いて，パラメトーピス時間分布の一般性を仮定するモデルの必要性は高リック除数法を含めたいくつかの議員定数配分方法によいものがある.しかし，解析的にはこのようなモデルをる配分結果を示し，パラメトリック除数法の“最適"パ解くことは非常に難しいことが知られている.

ラメタ値を提示する.

本論文では，先着順サーピス規範にしたがう GI/G/s

待ち行列における平均待ち時間と待ち確率に対し，それらの漸近的性質を利用して，到着時間間隔とサーピス時間の 2 次までのモーメントのみに依存する簡便な近似式を提案する，これらの近似式は

ム，3 つの基本的なシステ

M/M/s , M/D/s , D/M/s における平均待ち時間の値を内挿する形で与えられ，待ち行列数表を利用する平衡ゲームのコアを計算するシンプリシャ
ル・アルゴリズム
大阪大学神谷和也，テイルパーグ大学 Dolf Talan
別払いのない協力ゲームにおいて，平衡性と呼ばれる条件がコアの存在を保証することは，よく知られている.また，このようなゲームのコアを計算する方法に関ことで容易に計算することができる.これまでに知られしでも，ている Page と著者による同様の 2 つの内挿近似式が本方法では，アルゴリズムの初期値として定義域の内点、を~、くつかの方法が知られている.しかし従来の論文の特殊な場合として統一的に含まれ，本論文の近似取ることができなかった.

式がこれら 2 つの近似式よりも安定した高い精度をもつ

and Talman の( 2 n + L 2)-ray 法と類似のアルゴリズ

本論文ではDoup ，Laan ,ことが示される.また，近似式の取り扱いをさらに容易ムを使って，定義域の内点を初期値とする方法を提唱すにするために ， M/M/s の平均待ち時間のみを用いたほる.われわれのアルゴリズムは，定義域を単体分割し解ぼ同程度の近似精度をもっ簡約式もあわせて導かれる.

を近似する小単体を発見する，

厳密解の知られているシステムとの数多くの数値比較実ル・アルゴリズムの一種である.したがって，いかなる験により，本論文で提案した近似式が外挿近似としても内点も初期値となりうるわれわれの方法を使えば，近似いわゆるシンプリシャ有効であり，到着時間間隔とサーピス時間の変動係数がコアの近似度が低い場合，単体分害Ijを細かくして近似コある範囲内にあれば，相対誤差にして，中程度の負荷にアからアルゴリズムを restart することができ，対しては高々 5%程度，重負荷に対しては高々 1%程度精度の高い近似コアを簡単に計算できる.

よりの実用上まったく問題のない精度をもつことが確かめら
1991 年 10 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(43)521