転置行列である.また，集合分割問題の実行可能解集合利用した局所探索手続きを提案した.提案した局所探索の凸包の 2 つの端点が隣接していると L 、う必要十分条件

手続きは，ある特定の解法や問題に依存しないためかな

は 2 部グラフ G が接続していることである [1]. この性質

り広範囲な適用が可能である.さらに，提案した局所探を用いて，グラフ G が連結でなければ，索手続きが集合分割問題に対して容易に適用可能である

G の連結成分をすべて求めることにより，極大単調端点列を求めることことも示した.

ができる.
参芳文献

4.

おわりに[1] E. Balas and M. Padberg , “Set P
artiｭ

本研究では，単調多面体という凸多面体のクラスを定義した.そして，単調多面体の性質を，主にその端点閣8(4)(1976)
tioning:A Survey ," SIAMReview , 1710‑761.の隣接関係を中心に示した.また，単調多面体の性質を

獅学生論文賞受賞論文

要約機

OnE
igenv
aluesoftheRateMatrixi
naPH/PH/cQueue
高野正次(東京工業大学大学院理工学研究科情報科学専攻

現所属; NTT)

指導教官高橋幸雄教授

1.

速度行列の小行列である(次節参照).

はじめにそこで，待ち行列システムの定常的挙動を解析しよう

到着問摘分布やサービス時間分布が相型分布 (PH)であるような PH/PH/c 型待ち行列システムにおいて，その定常状態確率ベクトル π は，いわゆる matrix­

geometricform をもつことが知られている.とする立場からは ，R を実際に計算することなく ，Rの重要な特性を引き出すことができることが望ましい .Rの絶対値最大固有値，つまり，ベロン・フロベニウス固

すなわ

有値は，到着間隔分布とサービス時間分布のラプラス変をその待ち行列システム内に n 人の客がし、る定換を含む代数方程式の解として与えられることが知られ常確率ベクトルの部分ベクトんとすると，公比行列と呼ており，上の立場での最も重要な成果となっている.そばれるある非負行列 R が存在して，して，ベロン・フロベニウス周有値に対応する固有ベク

ち，7rη

πn= 7r c

Rn‑c (n ミ c)(1)

トルはc+1 個のベクトルのクロネッカー積として与matrix‑geometricform をもつことという関係が成り立つ.このことは，定常状態確率ベクえられる .π が，トルが無限次元であるにもかかわらず，有限個の有限次からすぐにわかることであるが，元ベクトル{ 7r o. "'，民}と行列 R により，完全に決定さR の比較的に絶対値の大きい固有値が支配している.こπ犯の漸近的挙動は，れることを示している.したがって，公比行列 R は定常のことが， π の裾の近似的数値計算の高速化や評価を可状態確率ベクトル π に対して非常に重要な情報を含ん能にしている.

でし、る.この重要性のために ，R を実際に数値的に求め本研究は，上のような R のベロン・フロベニウス固有る計算の手続きがし、くつか提案されている.しかし，現値に関する結果を ，実的な問題として，この手続きが有効に働くのは ，ることを意図したものである.

Rの次元が比較的小さいときに限定されてしまう.というのfì , Rf

R2A+RB+C=02.

準R のすべての固有値に対して拡張す

備(2)

ここで扱うシステムは，窓口ごとにサービス時間分布と L 、う非線形行列方程式の非負最小解として求めなけれが異なる場合も許す PH/PH/c 型待ち行列システムでばならな L 、からである.ここで，行列 A ，ある.ただし到着間隔分布 T =PH (ao , Qo)

658 (46)

B , C は推移© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.とすべ

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

てのサービス時間分布ぬ =PH (at , Qt) (i=I ,…, c)

U=Uo ⑧ U ⑧・・ ⑧ Uc

は原点、において質量をもたないものとする.また，各分とあらわすことができる.ただし，⑧はクロネッカー積

布についてラプラス変換のかわりに，ラプラス変換を全をあらわす.

複素平面上に解析接続させた関数 Tホ ， S戸(ただい極では定義しな L 、)を用いて議論を進めていく.
このシステムに対応するマルコフ連鎖を支配する推移
速度行列 G は，三重プロック対角構造

R のすべての固有値の候補が求められることになる.

さらに. ~3. 3 では.

Bo CoI 守|く 1 であるような(めの方程式系の解の集合が，公比行列 R の非零固有値の集合と多重A1 B1 C1度を含めて一致するための十分条件を考察した (Theo­九九、

G=(5)式を守とお ι … ， ~c についての連立方程式と考えれば，この方程式を解くことによって ，(めAC‑1 BC‑1 CC‑1
Ac B C

ABrem 3.10).

この条件は，一見，非常に強い条件である

ようにみえるが .

C

Ek/ET/C 型待ち行列システムの公比行列 R に対しては，実際に適用が可能である (~3.4).
したがって，このような場合には公比行列 R を計算によをもっ.ただし，部分行列 A ，B , C は，到着間隔分布およびザーピス時間分布を表現する行列とベクトルのクロネッカー積や和であらわされる正方行列で，その次元は ， Q; の次元を St としたとき ， S
o $1".. らである.

3.

り求めることなし (5) の方程式系を解くことによって，固有値と葺釘〈クトレど芯l!:こ捻与ることう:できる4. 陽な条件へ
Lemma 3.7 の応用を考える上で，条件( 1)と( 11)が公比行列 R の固有値成り立っかどうかを知ることが大切である.しかし，こまず，システムが複数の窓口をもっとき，公比行列 Rれは一般には簡単ではない.そこで，この条件を別の条(So‑ 1) SI'"

件によって置き換えることを考える. 7J1jの条件とは，到Sc であることを示した (~3 ， 1 )，公比行列 R が，非零固着間隔分布とサービス時間分布が，条件(1)と (11 )に相有値守をもっと仮定すると，当する性質をもつための十分条件であり，その意味で陽が固有値として O をもち，その多重度は(2)式を用いて，対応する国有ベクトルは，行列な条件への置き換えであると考えることができる.

Qo(I-t叫 EBQ1(I一例 )EB.. ， 悦EBQ
仏eμμ(げI一甲伊抑州
e伺a
叫叫c) μの固有値 O に対応する固有ベクトノル
L でで、あることが示される.ここで .EBはクロネッカー和をあらわす.このとき，(1)Qo(I ー1/哲問。)，

Q;(Iー守 ea;)のすべての固有値が固有多項式の単根である.

(11) Qo と Qo(Iー1/守 eao) が共通の固有値をもたず ， Qi と Q;(Iー亨 ea;)も共通の固有値をもたなL 、.とし、う条件の下で，次の lemma が成り立つ (~3 ， 2).

公比行列 R の非零固有値守が条件(1)と( 11)を満たすならば，ある複素数の集合 {~o ， ÇIo… ， ~c} が存在し，次の方程式を満たす.

T* (~o)可Si*(ﾇi) =1/甲 ， i=l , ..'， C ，卜 (5)1993 年 12 月号

これらをふまえ.

PH 分布のある部分集合を定義し，Feedback PH 分布(FPH 分布)と名づけた.

FPH

分布のクラスは，アーラン分布や超指数分布をはじめ，通常用いられる主な PH 分布のほとんどすべてを含み，-1(4)式の小行列の固有値の幾何的多重度は，代数的多重度にかかわらず，いつも 1 である.このことを用いると，その固有値に対応する固有ベクトルはもちろん，すべてしたがって， F PH/FPH/c 型待ち行列システムについては，Lemma 3.7 と同様の方程式系が条件なしに成り立つこ

R の固有値に対応する固有ベクトル U は，
守 I-Q;)(~4. 2) ,の根ベクトルを求めることができる (~4. 3).

ゐ +~1+ …+ゐ =0.

Ui= α

H 分布の表現について，いくつかの概念を定義し，上の園有値の代数的多重度と幾何的多重度について考察した

しかもそれらはいくつかのよい性質をもっ.たとえば，

Lemma3.
7とすると，まず，仏)式の小行列の固有値を求めるために特性多項式を解いた (~4.1 ). 次に， O'Cinneide にならって P, i=O , I , ・・ ， cとが示される (~4.4).

なお，詳しい条件および結果については，本論文を参照していただきたい.

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

(47)659