論文誌掲載

魂繭旨醐

∬ORS∬

概要

Vol．43，Nom2…l……ll……lllL川l…11…llllttl……‖‖＝‖‖‖‖＝＝‖＝‖‖＝＝‖＝‖＝‖＝＝＝‖＝‖＝＝‖＝‖‖‖＝‖‖＝‖‖‖＝＝‖＝＝＝＝‖＝＝＝＝＝＝＝＝＝＝＝＝＝＝‖‖＝‖＝‖‖＝＝＝‖＝＝＝＝‖＝＝＝‖＝＝＝＝＝＝‖川………＝＝＝‖‖＝‖‖‖‖＝‖‖‖＝‖＝‖＝＝＝＝‖＝＝＝州…llll…

肝一レット戦略を取り9 発生頻度が最も高い個体（解）囚Åのジレンマ臆お駐サる先見的安定性が期待値儀式を与える個体となることを確率的最適配

鈴木 明宏（東北大学）
武藤 滋尭（東京i二業大学）

本論文においては9 逸脱の連鎖を考慮した安定集合および調和集合の2つの解概念を用いて9 囚人のジレンマにおいてプレイヤーが先を見通して行動したとき分問題と確率的ナップサック問題を用いて実証した。
さらに，近年メディア情報処理分野で重要性が増してきた画像圧縮を確率計画問題として定式化し9 本法を適用した。

以上のことから9 本法は，GAのコーディングが可能な種々の確率計画問題への適用が可能な有望な手法の安定な状態を考察する。

2ÅのプレイヤーⅦがそれぞれ「協力」，「非協力」の2つの選択肢をもつ通常の囚人のジレンマでは，2つの解は同じ結果を与える。2人のプレイヤーが独立にとして期待できる爪

集線装置配置問題の厳密解法
椎名 孝之（（郷電力中央研究所）

行動する場合には9（「協力」，「協力」），（「非協力」，「非協力」）の2つの戦略の組が，また，2先のプレイ最適なコンピューターネットワークを設計するには，ヤー叩が共甘司して行動することも許す場合には9（「協ネットワー・クを構成する要素の規模り機能。性能に関力」，「協力」）のみが安定な状態として得られる。

して，最も調和のとれたものを選択し，それらを適切しかしながら9プレイヤーのとり得る選択肢が多くなに配置しなければならない。一般には，サービス品質った場合には，2つの解は全く異なった結果をJラーえる。安と利川■肯側からの要求との両者の制約条件を満たし，定集合では，2八のプレイヤーが独立に行動する場合に敲も経済的なネットワークを選択するp 本論又では，はすべての個人合理的な戦略の組が安定となるが，2人既知の需要要球を満たすように，端末の集合を接続すのプレイヤーが共同して行動することも許す場合には，2る3階′酌む伏ネットワークの設計を考える3 集線装置

火のプレイヤーにとって効率的な戦略の組のみが安定配置間接（Concemtrator Location Problem）とは，となるQそれに対して9調和集合では，いずれの場合に集線装置を設置する候補地とユーザーを表す端末の分も個人合理的な戦略の組それぞれがすべて安定となる。

布が・′，才一えられたとき，（i）実際に集線装置を設置する位置および ，（ii）各端末と集線装置の接続を表すトポ

不確定環境型遺伝的欝ル滅相ズ息臆よる確率ロジーを決定する問題である。この問題は，端末一集計画問題毎の解法

線装置間の接続コストと集線装置の設置コストの総和
苦冨 康成（宮崎大学）

池之恩 情予（熊本電波Ⅱ業高等専門学校）
竹菓 顛史（メイテック）冨田 重章（宮崎大学）

確率計画問題の解法として，遺イ云的アルゴリズム（GA）の環境に確率変動を導入する手法（不確定環境型GA）を提案した。本法では，惟代ごとに，確率変数の分布に応じて適応度関数（目的関数，制約条件）を変イヒさせ9 全世代を通じて個体の集合とその出現頻度を算出する。そして，まず9 期待値最大の解を得ることを目標とした。このため，選択方式として，ル2忍窃（34）を最小化する0一一1整数計画問題として定式イヒされる中本論文では9 問題固有の構造を利用して効率的に最適解を求める厳密解法を開発し，数値実験により解法の有効性を示す。この解法は，切除平面法と分枝限定法とを組み合わせたものであり，また標準的な数理計画ソフトウェアを用し−た実装法についても示す。
対称なポ脚旨』ングシステムにおける待ち時間、●●・、∵・−￣●・‥ ．・′

王藤 誠惚9 高木 英明9 橋田 温（筑波大学）
ポーリングシステムと呼ばれる巡回サービス多重待© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレザションズ。リサーチ

ち行列システムは，巡回的資源割り当てを伴う通信シットワークにおける通信需要と，集線装置への容量増

ステムや製造システムの性能評価モデルに広く使われ設費用に対するある単調性の仮定の下でこの間題を搾てきた．本論文では，全処理式及びゲート式サービス個のシナリオを持つT個の部分問題へと分解する．のポーリングシステムについて，待ち行列の数が2，論文では，計算実験によりこの計算効率が示される．

3，及び4の場合に，今まで得られていなかった待ち時間の2次モーメントを解析的な式で明示的に与える．
さらに，数値例を用いて待ち行列数への依存性を調べる．また，Ⅳ個の待ち行列をもつシステムに対し，待ち時間の2次モーメントの編棒時の漸近形を推測する．

確率変動を有する多期間の集線装置配置問題の解法

非増加かつ区分線形な需要を考慮した木構造
ネットワーク上の複数施設配置問題
梅澤 正史，西野 寿岬（慶鷹義塾大学）
本論文では，木構造を持つネットワーク上での最適施設配置問題（樹上施設配置問題）を考えている．サービスを求める顧客がネットワークの項点上にいるとし，顧客の需要は各項点ごとに非増加かつ区分線形な椎名 孝之（㈲電力中央研究所）

関数によって与えられているものとする．ここで需要現実の数理計画問題には，目的関数および制約条件関数は有限個の不連続点を持っても構わない．このネに不確実要素を伴う場合が多い．例えば，コンピューットワーク上に新たに設置する施設数カが任意に与ターネットワークの設計においては，与えられたパラえられた時，サービスの供給者が顧客から得る利得をメータ，特に各端末で発生する需要値などは確定値と最大にする♪個の配置場所を見つけるのが樹上施設して取り扱うことが困難であることがある．本論文で配置問題の趣旨である．この間題はMegiddo−Zemel−

は，確率計画法を応用したコンピューターネットワー

Hakimiの問題及びカーメディアン問題の拡張になっク設計問題を取り扱う．罰金に対する償還請求を有すている．また，木構造でない一般のネットワーク上でる（リコースを有する）確率計画法に対してはBen−の最適施設配置問題はNP一因難である．

dersの分解法を応用したL−Shaped法による解法が本論文では，樹上施設配置問題において施設の配置知られている．これに対して，整数制約などを持つ離地点がノード数に関して多項式オーダーの有限地点に散的な確率計画問題は，取り扱いが難しい．本論文で限られることを示し，多項式時間内で最適解を求めるは，L−Shaped法と整数計画法を加えた解法の枠組をアルゴリズムを提案する．このアルゴリズムは示す．このモデルの応用として，集線装置配置問題をMegiddo−ZemelJHakimiのアルゴリズムに基づいて取り扱う．多期間モデルでは，各期の決定がその期まいるが，最適利得関数がβに関して凹であるというでに生じたシナリオの履歴に依存するため，複雑な問彼らの解法の前提条件には依存しない．実際，設置す題となる．r期間の各期において乃個のシナリオがる施設数に関して最適利得関数が凹にはならない例を起こりうる場合，通常では全体として符丁個のシナリ具体的に示しているが，この場合でもここで提案するオを考慮しなければならない．開発した方法では，ネアルゴリズムは機能する．

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

2000年6月号（35）2約