川l＝‖川‖＝ll＝‖＝‖＝ll川‖川Il‖‖‖‖…l＝lll‖‖川‖‖‖＝＝‖‖‖‖川Ill＝ll川l＝＝‖＝lllIlll‖l‖＝‖＝lll川‖川l＝‖l川‖l川‖日日＝ll＝川川‖＝＝川‖川l川‖l‖＝

論文誌掲載論文概要
JOR SJ

Vol．40，No．3
1‖川l＝‖＝‖川‖川‖川‖＝l川Ill‖＝‖‖‖‖＝l‖‖＝‖‖＝l‖‖‖＝ll‖＝ll‖ll＝＝＝仙川‖‖‖川‖川川‖‖＝‖川‖＝‖＝＝川‖川‖川‖‖川‖‖‖‖‖＝川‖‖‖州l

プEjツクGauss−Seidel法が幾何収束する

2次収束性をもった3段階主アフィンための必要十分条件についてスケーリング法Romesh Saigal（ミシガン大学）

住田潮（国際大学），井垣伸子（帝塚山大学）

ブロックGauss−Seidel法は大規模なマルコフ連鎖

本論文では線型計画問題に対する主アフィンスケーリング法を取り上げ，予測修正子法とみなすことのでの平衡確率を計算するための最も重要な反復法のひときる探索方向決定の方法を示す．2種類の探索方向決つである．本論文ではこの方法が大局的に幾何収束す走法を考える．1つ目は，1対の各予測子操作の間にるための必要十分条件を求めた．またこの収束性は，修正子操作を1つ挟むもので，これを2段階法と呼ぶ．

マルコフ過程の状態空間の分割の仕方に依存している

2つ目は，修正子操作を2つ挟むもので，これを3段が，・任意のエルゴディックな確率行列に対して，ブロ階法と呼ぶことにする．2段階法は次数1．5の超1次収ックGauss−Seidel法が大局的に幾何収束するような束すること，3長那皆法は2次収束することを示す．こ分割の仕方が少なくとも1つは存在することも示した．

れはTsuchiyaとMonteiroによる次数1．3の超1次目標探知確率を最大にする最適識別探索時間
飯田耕司，宝崎隆祐，海保健（防衛大学校）
現実の探索においては，目標信号に酷似した信号を収束に勝るものである．

基多面体の端点を列挙する多項式時間アルゴ
Ping Zhan（江戸川大学）

リズム

発する偽目標物の探知やシステム・ノイズにもとづく多面体の端点列挙はたとえば凹関数の多面体上での虚探知が頻発することが多い．その場合の探索は目標大域的最小解を求めることに応用できる．しかし一般物らしい信号（コンタクトと呼ぶ）を広く探索する広的に不等式系で与えられた多面体のすべての端点を入域探索と，それが真目標物であることを確認する精査

力と出力のサイズの多項式時間で求めることは難しい．の2段階探索となる．しかもノイズにもとづくコンタ

本論文では，劣モジュラ基多面体のすべての端点をクトは，信号の再現性がないために精査によって虚探0（乃3v）時間，0（乃2）空間で求めるアルゴリズムを紹介知であることが確認できないのが普通である．したがする．ここで乃は次元でⅤは出力される端点の数を表って精査をいつまで続けるかが問題になる．本研究はわす．さらに，これは多項式時間遅れのアルゴリズム

ある地域内に存在する1つの目標物の探索において，である．すなわち，出力過程において次の端点を出力探索時間が制限されているとき，目標探知確率を最大するまでに多項式時間しかかからない．またこのアルにする精査の最適打切り時間を求めたものである．広

ゴリズムはグラフの全域木列挙やマトロイドの基の列域捜索ではポアソン過程に従って信頼性の異なるコン挙にも応用できる．

タクトが発生する．探索者は直ちに広域探索を中断し一般的なブロッキング構造をもつFork／Joinて精査に取りかかり，精査中は新たなコンタクトは発生しない．ある時間精査して目標物が確認できなければ，探索者は次のコンタクトを求めて広域探索に戻る．

多段生産システムの確率的性質

申出康一，大野勝久（名古屋工業大学）

本研究では残り時間Jのときに得られた信頼性♪のコ

これまで，直列型生産ラインや通信型ブロッキング

ンタクトに対する最適精査時間を求め，そのふるまいをもつfork／join待ち行列について，確率順序を用いや最適条件の現象的な解釈，数値例による感度分析等た性能比較や，可逆性，ならびに構造的等価性に関すを示した．

る研究が個々になされてきている．本論文では，これらのモデルを特別な場合として含む，一般的なブロッ624（48）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

キングをもつfork／join型多段生産システムについて考察する．システムが停止しないという初期在庫量の条件のもとで，このシステムを一般化セミマルコフ（GSMP）に定式化し，GSMPにおける凸性が成り立つことを示す．これを用いて，確率順序による加工終時刻で取替えを行うという保全政策のことである．

片側または両側に境界があり，列方向に関して飛び越しをしない2次元マルコフ連鎖の推移確率について
Julian Keilson（ロチェスタ一大学）了時刻の性能比較を行うとともに，加工順序を逆向き増田靖（慶鷹義塾大学）にしたシステムとの加工終了時刻に関する等価性や，一部のステーション間の加工順序を逆向きにしたシステムとの構造的等価性を示す．

本論文では，片側または両側に境界があり，列方向に関して飛び越しをしないマルコフ連鎖において，推移確率が行列の形で級数構造をしていることが示され∽機械フローショップ型自動生産システムのる．グリーン関数法とNeutsによる行列級数法は，あ最適スケジューリング

るクラスのマルコフ連鎖の定常分布を求める方法とし

程金良巨木瀬洋，軽野義行（京都工芸繊維大学）てそれぞれ独立に開発されたわけであるが，この2つ本論文は研台の容量の大きいバッファを伴った加工の方法の関係は必ずしも明らかではない．本論文は，セル（たとえば，マシニングセンタ），1台のAGVこの関係も明らかにする．また，「推移率行列」の確率（Automated Guided Vehicle）お・よびローディング，的解釈も与えられる．

アンローディングステーションからなるフローショップ型自動生産システムに対し，最大完了時間を最小化する最適スケジューリング問題を論議する．まず，この問題を定式化した上で，近似的に古典的な（∽十1）機械フローショップスケジューリング問題に帰着させる．

パーフェクト双向グラフに対する一般化安定集合問題

田村明久（電気通信大学）

双向グラフは無向グラフを一般化したもので，各辺はさらに両端点に正または負の符号を持っている．・本

そして，この（椚＋1）機械フローショップスケジューリ

論丈では，無向グラフに対する最大量み安定集合問題

ング問題にもとづいて，ファジィ推論におけるメンバを双向グラフに一般化した問題を扱う．この間題を双ーシップ関数を構成し，それを近似アルゴリズムに利向グラフに対する一般化安定集合問題と呼ぶ．論文中用する．さらに，このファジィ近似を利用した分杖限では，ある種の施設配置問題（最大量み安定集合問題定法アルゴリズムを提案する．広範な数値実験によっとしては簡単に定式化できないように思われる）が一て，提案した近似解法は最適解あるいは最適解に近い般化安定集合問題として安定化されることを紹介する．

近似解を与えることを示す．また，提案した分枝限定最大量み安定集合問題は，無向グラフがパーフェク法アルゴリズムは∽＝3の場合，400ジョブまでの大規トならば多項式時間で解けることが知られている．一模な問題例に対して，実用的計算時間で90％を上回る方，パーフェクトという概念は双向グラフにも自然に高い割合で最通解を与えることを示す．

拡張される．また，ある種の自然な前提のもとで双向平均費用規範のもとでの最適小修理・取替え問題：（′，r）−政策の最適性大西匡光（大阪大学）
本論文では，平均費用規範のもとでの信頼性システムの最適取替え問題をセミ・マルコフ決定過程としてグラフがパーフェクトである必要十分条件は各辺．を無向辺で置き換えて得られる無向グラフがパーフェクトとなることが示されている．これらのことより，一般化安定集合問題がパーフェクト双向グラフに対しても多項式時間で解けることが期待される．
本論文では，以下のようにしてこのことを証明する．

定式化し，故障率関数が年齢に関して狭義に単調増加ある種の辺削除を定義し，これが双向グラフのパーフで無限に発散するという仮定のもとで，すべての可能ェクト性を保存することを示す．さらに，この辺削除な小修理・取替え政策の中で，いわゆる（′，T）政策がを用いて任意の双向グラフに対する一般化安定集合問最適であることを示す．ここで（′，r）一政策（0≦J≦

題がある無向グラフの最大量み安定集合問題に帰着でr≦＋∞）とは，年齢′以前の故障に対しては小修理きることを示す．また，この帰着はグラフの頂点数にを施し，年齢J以後は，最初の故障が発生するか，あ関する多項式時間で終了する．これらを総合し，最大るいは故障なく年齢rに達するかのいずれか早い方の量み安定集合問題に対する既存の多項式時間解法と組

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

（49）625

み合わせることで本論文の目的は達成される．

非線形最適化に対する主双対内点準ニュートン法の超1次収束性について
矢部博（東京理科大学），山下浩（数理システム）
線形計画法における内点法の成功に端を発して，近年，非線形最適化問題に内点法を適用する試みがなされている（見直されている）．本論文では，準ニュートン法にもとづいた主双対内点法が超1次収束するための必要十分条件を示す．そのための準備として，非線ガロy＝鋸とする．3V上での2つの演算，簡約和∪と交わり∩，を以下のように定義する．任意の（芳，㌣）∈3V（オ＝1，2）に対して（芳，n）∪（品，坑）＝（（XlU為）−（nUlち），（nUiち）−（凡∪義）），（一私，坑）∩（義，坑）＝（兄∩義，yniち）さらに，（∪，∩ト閉族ダ⊆3V上の関数／：ダ→Rが，任意の（ズォ，㌢）∈ダ（才＝1，2）に対して′（芳，y）＋／（義，坑）≧／（（芳，n）∪（義，坑））＋／（（ふ，坑）∩（義，坑））形方程式に対する修正ニュートン法と修正準ニュートを満たすとき，／をダ上の双劣モジュラ関数という．

ン法の局所的2次・超1次収束性を一般的に議論する．

（軋β）∈ダなる（∪，∩ト閉族ダ⊆3Vと／（鉄郎＝0を

これらの方法は，ヤコビ行列の一部分の近似，方程式満たす双劣モジュラ関数／：ダ→βに対して，対の摂動，ニュートン・ステップの成分ごとの減速を考（ダ，／）をⅤ上の双劣モジュラ・システムと呼ぶ．

慮したものである．これらの結果を非線形最適化問題

本論文において，基多面体と密接に関連する双劣モ・システムの2つのクラスを考察する．まず平に適用することによって，主双村内点準ニュートン法

ジュラが超1次収束するための必要十分条件が得られる．さ

衡双劣モジュラ・システムと呼ばれるクラスに対してらに，主変数と非負条件に対する双対変数に関する超その特徴付けを与え，関連する多面体がいくつかの基1次収束性のための必要十分条件も与える．この結果多面体の鏡映の凸包であることを示す．次に双向ネッ

は，逐次2次計画法等の従来の非線形最適化法で議論

トワークのカット関数によって定まるクラスに関連すされている変数の一部分（この場合は主変数のみ）のる多面体が，その双向ネットワークのフローの境界全超1次収束性の条件に対応するものである．

体からなる集合と一致し，与えられた双向グラフに対応する通常の有向ネットワークの境界多面体とある部

平衡双劣モジュラ・システムと双向フロー安藤和敏（筑波大学），藤重情（大阪大学），内藤雄

分空間との共通部分を射影したものになっていることを示す．

志（滋賀大学）

非空な有限集合Ⅴに対して，3V＝（（ズ，y）lズ，y⊆Ⅴ，『事例研究，研究レポート』 への論文投稿のお願い
本誌に掲載ぎれる論文としては，現在のところ事例るものであれば，積極的に採択します．

研究，研究レポート，総合報告の3つがあります．事

原稿の長さは図表を含め長くても刷り上がり6ペー

例研究，研究レポートは実際の状況にORの考え方・ジ程度（約12000字）が興味を持続して読むのに適当な手法を適用した際に得られた新しい経験・発見を論文長さだと思いますが，読者の理解のために必要とあれの形にまとめたものです．事例研究は実施にあたってば多少長くなっても構いません．投稿原稿はワープロの工夫，あるいは問題点の分析などがテーマになり，を使って作成し，3部を日本OR学会事務局（〒113文研究レポートはその際に得られた理論的な知見，ある京区弥生2−4嶋16）にお送りください．

いは新しい視点を提示したものです．特に事例研究になお，採択されました論文の本誌掲載につきましてついては適用している手法が完全にオリジナルではな

は，刷上り6ページまで￥3，000／ページ，刷上り7ペ

くとも，内容が実際の事例に関してのもので，その取ージ以上のものは，当該ページ以後￥5，000／ページ

り扱い方に新規性があり，学会員に対して，あるいは，（刷上り11ページ以上の論文は原則として認めない）

本誌を購読されている一般の読者に対して刺激を与え626（50）の掲載料が課されます．

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

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