l＝l＝＝＝川‖＝ll‖＝l＝‖＝＝‖‖‖＝＝＝川＝＝‖＝＝川＝川＝‖仙＝＝‖＝＝＝＝lll‖＝＝l一日‖‖川‖t‖＝＝川＝＝‖川Ill州‖‖＝川‖川＝＝‖t＝‖川＝川＝日日川州＝t

論冤誌掲載論文概要』OR SJ￣‥ ■ ▼ 一
日‖川＝＝‖＝ll川l州＝ltll‖＝川‖＝川Ill＝‖l川‖川‖＝‖＝＝‖＝＝l‖lll＝＝川＝＝t＝川川川川Il＝川川川1川川＝日日＝川＝＝川Il川‖川＝仙Il川‖＝＝ll＝l‖l＝＝＝川＝‖l

動的計画法臆よる配管の最適溶接位置決定法
松本 輝夫（㈱日立情報ネットワーク）9 土屋 昇（㈱創源システム），濃紺 順ニ（㈱日立製作所），仁尾都（明星大学）

確率的推移過程における加法型評価の最適化問題はマルコフ決産過程として1960年代より研究されてきた。
ここでは，この確率的推移過程上での乗法型評価の最適化問題を考える。もし各段での利得関数がすべて非負の場合，特に問題はなく通常の加法型評価系の場合

本論文ではプラント配管の溶接費用を最小にするよと同様に扱うことができるひ しかし，負の値が利得にうな最適溶接位置決定問題への動的計画法の適用につ含まれる場合，状況は−一変する。最適政策は必ずしもいて述べる。配管はエルボやT継ぎ手，素材管を組マルコフ政策の中に存在するとは限らないからである。

立溶接して作られる。搬送可能な大きさに分割された・・・・1般にこの樵の問題では，その議論においで最適政

スプールと呼ばれる部分配管を工場溶接で製作し，現策のマルコブ性が暗黙のうちに認められているようで地で配管仝ノ体を組み立て現地溶接している。

ある。ところが加法型以外の評価系（乗法型，最小型，ここで考慮した条件は工場溶接及び現地溶接の単価，…）を考えた場合，最適政策のマルコフ性は保証され輸送限界で制限されたスプー州ルの大きさ，配管中で溶ない。この事実は，マルコフ過程に適用されてきた通接できない溶接禁止領域や，溶接しなければならない常の動的計画の手法がそのままでは通用しないことを溶接必要領域9 素材管の長さの制約である。

意味する申 そこで我々はこの乗法型評価の▼最適化問題

溶接費用が最小となる関数を以下に示す￠
鞠）＝に対し3つの解法を提案する。それは両決定過程と不変埋没原理の2つの手法を用いた方法と，すべての場ッ）紬∬）＝

合を列挙する方法としての多段確率決定ツ牛←法である。最後に最適政策がマルコフにならない数値例を挙′．T）

ここで9 ￡，タ，fは配管上の位置を表し，配管の中心線をメッシュに分割した時のメッシュの境界に始点側から付けた番号である。始点の番号を0，終点の番号を∽とする。
y（∬）は9 γから∬までが1つの輸送可能なスプールとなりうるスプ、−ルの開始位置夕の集合で9 開′（ッ，ヱ）

げて各解法を用いた計算プロセスを紹介する。

捜索経路が与えられた場合の移動目標に封ずる確率的ルック戦塵

璧崎 隆楓 飯田 耕乱 木山 雅晶（防衛大学校）
本論文は，移動日標に対する捜索者の最適ルック戦は，夕と∬の間にあってタに最も近い工場溶接となりう略を求める問題を取り扱っている。目標はある確率法

る位置才の集合である

則で自分の通る経路を選択する。捜索者はあらかじめダ（ヱ）は始点から∬までの現地溶接費用と工場溶接費与えられた経路にそって移動しつつ，離散時点で自ら用の和の最小値であり，G（ッ，∬）はヲ γから￡までのスの現在地をルックすることにより目標探知に努める。

プール内にある工場溶接費用の最小値である。Clと

ただし9 そこに目標が存在し，かつルックを実施した

C2はそれぞれ現地溶接と工場溶接の単価であるu場合に限り目標探知の可能性はあり，またその探知確

最後に，提案した方法による溶接費用の計算結果は率も，時点によって異なる。捜索者のルック戦略を各従来の手法に比較して10％少ない値を示し9 人手によ時点においてルックする確率によって示される確率的る作業時間の20％の二虹数で溶接位置を計算できている伊なものとし，目標探知により得られる期待獲得価値からルック実施により消費される期待捜索コストを引い負債乗法型関数の期待値最適化

た期待利得を最大にする最適ルック戦略を求めるのが9

藤田 敬治（九州工業大学）ヲ 津餞崎 和義（九州大学）

5⑳鴎（38）

本論文の目的である。論文では，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

この間題のNP完
オペレーションズ侍 りサーチ仝性の証明や動的計画法による解法の提案を行っていど（〃））は原点（0，0，…，0）と単位立方体U乃の頂点（1，る．また，最通解のいくつかの性質を解析的に明らか1，…，1）を含む連続体を成す．にし，数値例を用いた解空間の分析も行っている．

このノートでは点対集合関数が単価であるとき，つまり点対点関数のときこの定理に対してBrowderのデリバティブのモンテカルロ法による価格づけにおけるranl（）乱数生成器の異常性につ不動点定理を使って簡潔な証明を与える．

いて正値逆数行列の性質と不完全一対比較行列の田島 玲，＝宮 祥一，手塚 集（日本アイ・ピー・ウェイトの評価法

エム㈱）白石 俊輔（富山大学），小畑 経史（大分大学），醍

モンテカルロ法は，金利デリバティブの価格づけに

醐 元正（同志社大学）

おいて，特にモデルが複雑な場合に有効であることが正道数行列の固有多項式はいくつかの特筆すべき性知られている．しかし，そうした複雑なモデルの一種，質を有している．それらはAI］：Pにおける一対比較行CMOの価格決定において，NumericalRecipesin列の整合性と深く関っている．これらの性質に基づき，

C First Editionで紹介されている疑似乱数生成アル不完全な一対比較行列の欠圭員データを推定する手法をゴリズムranl（）を用いると，その初期化の値によっ新たに提案する．て，結果が誤った値に収束することがPaskovにより報告された．こうした疑似乱数の異常性は，連続，離散を問わずシミュレーション全般に影響を与える問題である．

本論文では，Paskovの実験をトレースし，問題のサ鵬ビス効率の降下／上昇をともなうM／G／1
待ち行列モデルについて
井垣 伸子（帝塚山大学），住田 潮（国際大学），小和田 正（名古屋工業大学）

乱数生成器の特性とアルゴリズムを解析し，間違ったM／G／1待ち行列システムの拡張モデルについて考値に収束した原因を解明する．次に，その異常を避けえる．そこでは，ビジー期間に処理された客数に応じる一方法を提示し，分散減少法と併用することにより，たサーバーの疲労やサーバーへの要請などによって，バイアスのない正確な備に収束することを確認する．

サービス効率が変化する．つまり，ビジー期間内の々また，一般に知られている乱数の統計的テストによっ番目に到着した客は，引こ依存した長さのサービス時て，この異常性を発見できるかどうかを検討する．

間がかかる．ここで，0番目の客がビジー期間を開始連続体をなすゼロ点についての定理に関するノ岬卜

郭 宝霧，山本 芳嗣（筑波大学）
1994年，Herings，Talman，Yangは次の興味深いさせるものとする．客のサービス時間は，互いに独立であるが，分布は異なってもよい．このモデルは，1番目以降の客のサービス分布が同じであるような遅れをともなうM／G／1待ち行列モデルを特別な場合として含んでいる．時刻チでシステムがアイドルである確定理を単体的アルゴリズムを作ることによって構成的率，ビジー期間の長さの分布，そのビジー期間内ですに証明している．

でに∽人の客が退出しているという条件付の時刻オに定理：乃次元ユークリッド空間内の乃次元単位立方体おける系内客数分布などをラプラス変換形で求めた．

U乃から乃次元ユークリッド空間への点対集合関数どまた，2番目以降の客のサービス分布が同じであるよが以下の性質うな場合のクローズドな解を求めた．

1．点対集合関数どは上半連続であり，その値は非空コンパクト凸集合である．

2．単位立方体び乃の各点仔でど（す）はqJ＝0ならろ≧0，射＝1ならろ≦0なる点zを含む．
3．単位立方体U乃の各点すに対して正のベクトルカが存在し，任意のz∈訳す）に対して〆之＝0が成り

待ち行列システムに対する定常状態確率の陽解について
Andreas Frey（Ulm大学），高橋 敬隆（NTTマルチメディアネットワーク研究所）

本論文では仝処理型遊休時間のある単一サーバ有限立つ．
を持つときその関数のゼロ点集合（す】す∈U乃；0∈

1998年9月号

全処理型遊休時間のある有限容量M／G／1／N

容量待ち行列システムを解析している．客の到着過程© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）501

はポアソンに従うとし；サービス時間，遊休（バケーを適用すると，各方向の車が到着してから橋に進入すション）時間は各々独立で一般分布に従うと仮定してるまでの平均待ち時間が厳密に求められることを示す①いる。本待ち行列システムは通信分野において時分割多重アクセス方式（TI〕MA）を採用した際のバッフ

海止監視活動にお柑る経路設定問題

か宮：諷 森 雅尭（東京工業大学）

ァ設計にしばしば現れる基礎的なものであり，従来か田本周辺海域においては，一般船舶の航路保全。不ら活発に研究されている押しかしながら，ここで対象とした有限容量システム

審船舶の早期発見／対処を目的とする，航空機によるに対しては，いずれも状態方程式に関する漸化式を利海上監視活動が定期的に実施されている ．この際の基用して定常状態確率を数値的に解くもので，陽解は知準となる飛行経路の設定に閲し，季節的に変動する漁られていなかった。ここでは従来より簡略化した（サ船位置情報や将来位置が予測される船舶の分布に関すービス終了時点のみからなる）マルコフ連鎖法を用いる情報等が考慮されてこなかった。本研究では，これて，状態方程式の漸化構造をより簡単化し，」それにもらの情報を考慮に入れた，限られた飛行時間内での効とづきシステム内客数に対する定常状態確率を陽に求率的な飛行基準経路を設定する方法を提案し，モデルめることに成功している。さらに，遊休（バケーショ例によりその妥当惟を検証したむ この方法により，船ン）時間をゼロとする極限操作により，通常の（遊休舶の将来位置からの逸脱が少ない基準経路の設定が可時間のない）待ち行列システムに対する陽解も得てい能となる。

る。
ヨスト制約のある整数資源配分問題

発進遅れを伴う交互交通流の平・均遅れ時間
鈴木 誠遥（千葉工業大学）9 山下 英明（東北大学）

宝嶋 隆祐，飯田 耕司（防衛大学校）
本論文は，コスト制約の下で指数型の目的関数を最狭い橋などのために2車線の道路が部分的に1車線大化する整数計画問題を取り扱っている。制約が資源になっている道路における交互交通流の解析を行う。

総量である場合は比較的容易に解けるものの，コスト一方から到着した草が橋に進入すると，他方から到着制約である場合は，問題が整数ナップサック問題を特した車は，反対側のすべての辛が橋を渡るまで橋の手殊ケースとして含むためNP完全となる。問題にお前で待つことになる。このような状況は，違法駄車やける目的関数は指数関数の総和の形で与えられるが，道路工事によその個々の指数関数の屑には整数変数の重み付き総和っても発生しうる。本研究では，橋の両端に信号を設置し9 一方の車がいなくなり優先権が他がのっているゆ 主要な制約式は総コスト制約1つで与方に移ったときその方向の車の待ちがなくても，あるえられ，このシンプルなモデルの形は割当問題や捜索一定時間以上は優先権を保持するよう制御する場合を問題等種々の研究分野においても見られるものであり，考える。ここでは，各方向の車の到着過程が独立なポ

ここで提案する解法は応用の面からも価値があると思アソン分布にしたがい，橋を通過するのに一定時間かわれる。論文では，この間題に対して，動的計画法およかると仮定する。さらに9 一度橋の前で停止した車は，

び線形緩和と貪欲法を用いた分岐限定法の2つの解法一定の発進遅れを伴うとする。このようなモデルに対を提案する。そしてヲ 数値実験により種々の感度分析し，ある仮定のもとで優先権の持続時間の1次。2次や計算時間についての分析を行うとともに，食欲法にモーメントを解析的に求め，これに確率的分解可能性よる近似解法の精度が極めてよいことを明らかにする。

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

オペレーションズ0リサーチ