llllllllllllllllllllllllllllllllllllllllllllllllllllllll1111111111111111111111111111111111111111111111111111111I111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111IIIIIIIIIII~

論文誌掲載論文概要
Vol.34 , No.3,;-.1111111111111111111111111111111111111111111111111111I1111111111111111111I1111111111111111111“

1111111111111111111111111111111111111111111111111111111111111111111111111111“

11111111111111111“

1IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIh

ある種の非対称巡回セールスマン問題

非線形最小費用流問題に対する双対における緩和問題の選択

エュ一トン法

防衛大学校

片岡鏑調

早稲田大学森戸晋

京都大学茨木智，福島雅夫，茨木俊秀
非線形な目的関数を持つネットワーク最適化問題は，

Salesman Problem (TSP) を理論的にも実際的にも重要である.本論文の目的は，分分校限定法で解く際に用いる緩和問題としては，割当問離可能な費用関数を持つ非線形最小費用流問題に対する題が効果的と通常信じられている.この論文では，非対効率的なアルゴリズムを提案することである.与えられ称 TSP に定式化できるある現実問題のインスタンスにた問題の費用関数が狭義凸かっ共有限 (co ・ finite) であ

非対称 Traveling

おいて，緩和問題の選択に関する上記の常識が必ずしもるとき，その双対問題は微分可能な目的関数を持つ，制適切ではないことを示す.さらに，この実際問題に即し約なしの凸最小化問題となることが知られている.ここた非対称 TSP のインスタンス群として2 次元平面上

ではその性質に着目し，双対問題に対して，問題のネッの TSP の距離をある方法で歪めて生成されたものを考トワーク構造を利用した，ニュートン法にもとづく降下

え，ここでは SLOPE と名づけた.

法のアルゴリズムを構成する.さらに，アルゴリズムのこのタイプのインスタンスでも，分枝限定法における大域的収束性を示すとともに，探索方向の計算および直緩和問題で割当問題を用いることが，非効率的であるこ線探索の実用的な方法を与える.計算実験の結果，かなとを確かめ，り大規模な問題(節点数 =4900 ，最小有向い木を用いることを提案する.

校数= 14490)まで解

これは対称型 TSP で成功している最小 l ・木の非対称くことができ，収束の速さも従来の方法に劣らないこと型ととらえられる.さらにアルゴリズムの効率をより上が確かめられた.

げるために，根になるノードの適切な選択方法と，下界値を上昇させるためのラグランジュ乗数の与え方について述べる.

非線形最小 2 乗問題に対する構造化
準ニュートン法の数値比較
東京理科大学矢部樽

SLOPE に属するものと，実際問題の両方に対して計

鹿島建設胸算機実験を行なった結果，ここで、提案したものが，割当問題を緩和問題としたものよりもよい計算効率を得たことがわかった.

高橋俊彦

非線形最小 2 乗問題に対する数値解法として，構造化
準ニュートン法がよく知られている.しかし，この方法は百分率にもとづく回帰分析法

ないとし、う問題点もかかえている.この課題を解決する

オハイオ州立大学

ビジネススクール

探索方向が必ずしも目的関数の降下方向になるとは限ら

末吉俊幸

手段として，分解型準ニュートン法が Sheng

Songbaiand Zou Zhihong (1988) や Yabe and Takahashi

本論文は目標計画法を使い，回帰分析を行なう手法に(1988) らによって，それぞれ独立に研究されている.

ついて考察する.本論文で提示する手法の特長は，従属

Sheng Songbai らのアプローチは iNewton 方程式」

変数の回帰式に対する誤差の分布が百分率て‘表現されると「残差関数の 1 次モデルの変形」を組み合せたものところにある.この結果，本手法による回帰分析では誤で，ある種の行列方程式を解く問題に帰着される.彼ら差の正規性やサンフ。ル数に関する仮定をなくすことがでは 1 つの更新公式 (SZ 公式)を提案しているが，導出きる.

する際の条件が暖味であるように忠われる.そこで本稿て、は，行列方程式の可解性等を考察して，

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

sz 公式を合オベレーションズ・リサーチむような更新公式を生成し，また，サイジングを sz 公

この方法は，これまで，通信型のプロッキングメカニ式に利用することを試みる.これによって，残差が大きズムをもっ待ち行列ネットワークなどに適用された.しい問題にも，小さい問題にも適用できることが期待され

かし，生産型のプロッキングメカニズムをもっ直列型待る.さらに，数値実験を行なって，われわれの方法とち行列システムでは，ノード聞の独立性を自然な形で仮sz 法との性能比較を行なし、，定することが難しく，また，サイジングの影響

この Cross

Aggregation Meｭ

thod を直接適用することはできない.

も調べた.

M/G/m システムの過渡的な拡散近似法

本論文では，システムの状態に対する 2 種類のラベルつけを提案し，おのおののラベルづけにおいて，Cross

AggregationMethod が適用できることを示す.比較韓国高等科学技術研究所的自然なラベルづけである記述法 A では，BongDaeChoi, YangWωShin
本論文では ， MIGlm システムにおける顧客数の基本復帰境界を，拡散プロセスの過渡的な拡散近似で計算する方法について論ずる.われわれは，可変係数を伴なう前進型拡散方程式に問題を定式化して，それを解く.その解は，待ち行列長分布の過渡的な近似を与えるものである.数値例によると，これらの拡散近似は，すべてのトラヒックケースに対して，きわめて正確な結果を与えている.本論文では，さらに，木村による定常的な近似も，この過渡的な拡散近似法によって得られることを示の近似は可能であるが，レベル 2 以上レベル 1 の近似はできない.また，プロックされた窓口を次のノードのバッファーとみなす新しいラベルづけで、は，すべてのレベルの近似を適用することができる.

50例を越す数値実験の結果，ル 3 の近似は，十分に精度が高く，レベ

レベル 2 の近似でもたいていの場合，実用上十分な精度をもつことがわかった.

無限容量のバッファを持つ無人化 2機械フローショップスケジューリン
グ問題についてす.

京都工芸繊維大学木瀬洋

アグリゲーション法による生産型ブロッキングをもっ直列型待ち行列の近似解析
東北大学宋東京工業大学

宇高橋幸雄

この論文では，生産型プロッキングメカニズムをもっ本論文では，AGV のような自動搬送車を伴った 2 機

械フローショップにおいて，最大完了時間最小化を求めるスケジューリング問題を取り上げる.本論文の主な成果は次の点に集約される. (1)この問題は，各機械が無限容量のノミッファを持つ場合，これまで未解決であった 3機械フローショップ問題の特殊例(第 2 機械におけるジ直列型待ち行列システムを数値的に近似解析するひとつョブ処理時間が一定の場合)と等価で，かつ， NP 完全の方法として Cross Aggregation Method を適用すである.

る.

する従米の結果とから解の得られる場合もいくつか存在

Cross Aggregation Method では，いくつかのノ(2) この結果と3 機械フローショップ問題に対することも指摘される.

ート'からなるシステムの確率的ふるまいを表現するマル

近年，いちじるしく発展・普及してきた FMC(Flexible

コフ連鎖に対して，ノード聞の独立性に関して何レベル

Manufacturing Cell) は，ここで取り上げたシステムかの仮定を置くことによって，の典型的な例であり，この点からも，本論文で得られた近似値を導くことができる.

1992 年 1 月号

レベルの異なった複数の結果は有意義である.

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

49