性を考察した.その結果， MV モデルを実際に適用する的ポートフォリオの漸近的性質と事前・事後分析.lI，ためには，過去の実現収益率にもとづく標本平均をあて

日本応用数理学会，平成 4 年度年会予稿集，にせず， (1)あらかじめ，すべての銘柄の平均収益率を等

272 , 1993.

(2)しいものと見なして投資する(分散最小化戦略)か，

pp.271‑[4J JamesM. Poterba , LawrenceH.Summers ,市場の平均的パフォーマンスに比べたミーン・リパージ“ Mean Reversionin StockPrices ,… Evidence

ョンを積極的に利用し，やや低めの標本収益率ベースのand Implications... 九収益率を狙う(逆張り戦略)必要がある.ただし，(1)(2)の投資戦略を利用するにあたっては，次の工夫が求めら

Journalof FinancialEconomics22(1988) , pp.27-59 , North‑Holland.

[5J J. D. Jobson and Bob Korkie , “ Putting
MarkowitzTheorytoworkヘ The Journal ofれる

(1)分散最小化ポートフォリオにおいては，基本推定期

PortfolioManagement , Summer 1981 , pp.70‑

聞を適切(約 6 年間)に設定する必要がある.

74.

(2)逆張り戦略においては，基本推定期間は過去のデー[6J竹原均.“ AnEmpirical Study on theタをフルに利用で、きるものの).を適切(約 -500) に

Mean‑Variance Portfolio Selection Model設定する必要がある.

Risk Management and Mean‑Reversion in
Japanese Stock Pricesヘ参芳文献MTECWorkingPaperNo. T922 , (1992).

[1J Edwin J. Elton , Martin J. Gruber ,“ Modern Portfolio Theory And Investment
Analysis ヘ John Wiley& Sons , New York ,1987.

[7] 大森敬治， 'i
IMeanVariance Approach の適用性について.lI，

IBM 金融システム・ジャーナル，No.3(1992) , pp.67ー79.
[8J Richard O. Michaud , “ TheMarkowitz[2J HarryM.Markowitz ,“ Portfolio Selection.
"

OptimizationEnigma:ls'Optimized'Optimal?" ,Journal ofFinance , March 1952 , pp.77‑91.

Financial AnalysisJournal , January‑February[3J 白川浩， Ii'標本統計量に基づくマーコピッツ効率

1989, pp.31‑42.

第護学生論文賞受賞論文

要約繊単調多面体の性質とその集合分割問題への適用
田村直(東京理科大学大学院工学研究科経営工学専攻指導教官

1

現所属:エッソ石油紛)

山口俊和教授密接な関係があり，多商体理論を活用した解法を設計す

はじめにると L 、ぅ研究方法がある.この中でも，ある条件を満足組合せ最適化問題は，不等式や等式制約と，一部またする凸多面体のクラスを定義しその性質を分析していく

はすべての変数が整数に制限されると L 、う条件の下で，方法は，その凸多面体のグラスが多くの組合せ最適化問

目的関数を最大化または最小化する問題であり，さまざ題を包含できるため，さまざまな問題において導かれた

まな種類の問題をこのようなモデルとして表現すること間有の性質の統ーが可能である.

ができる.また，多くの組合せ最適化問題の実行可能解木研究では，単調多面体という凸多面体のグラスを定は，凸多面体として表現できる.線形計画問題に対する義する.そして，単調多聞体についての性質を導く.まDantzig によるシンプレックス法では，実行可能領域でた，導いた性質をもとにした局所探索手続きを提案する.

ある凸多面体の組合せ的な特徴が重要な役割を果たしてさらに，提案する局所探索手続きが集合分割問題に容易いる.このように，多面体理論と組合せ最適化問題とはに適用できることも示す.

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

オベレーションズ・リ+一千また，単調多面体の単調端点列の長さは単調多面体の2. 単調多面体とその性質次元を越えない.さらに，極大単調端点列では次のよう単調多面体とは，次のような 2 つの性質をもっ凸多面な定理が成り立つ.

体である.

定理 2.4性質 A.

(X O ， x 1 ， … ， x K ) が与えられたとき，凸多面体 P の任意の異なる 2 端点 ;X:， zが P で、隣接していないならば ，(;x:， y ， z) が単調端点列となるようP を単調多面体とする .P の単調端点列 μ=で、あるための必要十分条件は，な P の端点 u が存在する.

点がーにが，性質 B.

であるて，凸多面体 P の任意の異なる 3 端点 ;X:， Y ， zに対し(;X:， y ， z)

が P の単調端点列であるならばは ，w=xμ が極大単調端点列

μ のすべての隣り合う 2(iE{1 ， 2 ，"'， K}) が P で隣接していること

単調多面体は多くの重要な最適化問題の実行可能解のl当包として現われる.

-y+z は P の端点である.

ここで単調端点列とは，凸多面体の端点列(;x: O ， ;X: 1,…,

命題 2.5P を端点がすべて 0-1 ベクトルである凸多面;x: K) の各添字 j ごとに対して ， x O j ;5; x 1 j::三… -:;'XjK または体とする.そのときP は性質 A を満たす.

XOj:三 X1/2 ・・・ 2 X j K という条件を満たすものである.ま命題 2.6

A を m 行 n 列の要素が有理数の行列 ，b を要た，部分単調端点、列とは単調端点列のいくつかの端点、を素が有理数の n 次元ベクトルとする.そのとき ，{xE {O ,削除して得られるものであり，極大単調端点列とは他のl}nIA;x: =b} の凸包 P は単調多面体である.

任意の単調端点列の部分単調端点列とならないもの官い{x 正 {O， I}nIAx=b} として実行可能解の集合が表わされう.また，単調端点列の隣り合う 2 端点、の差を差分ベクる問題として，等式制約ナップサック問題，集合分割問

トノレという.単調多面体 P は次のようなさまざまな性質題などがある.特に集合分割問題とは，係数行列 A の要をもっている.

素がすべて O または 1 ，ベクトル b の要素がすべて 1 で定理 2.1P を性質 B を満たす凸多面体 ，P の単調端点列を μ::: (;x: o, ;X: 1 ，… ，;x:K) とする.また，差分ベクトルを
di= ;x: i ーが -1 ，(iE {1 , 2,… , K}) とする.

このとき，(1 ， 2 ，… ， K) 上の任意の置換 p= (pω ， pω ，"'， P(Kl) に
よって ，Vi ε{1 ， 2 ，・ 1XO= ;x: O, Xi=;
x:O+L: k=ldp(kl ,K} として生成される端点列 β(XO ，.f'， … ， x K ) は Pある問題である.

3. 局所探索手続き
線形な目的関数とレゴやクロージャーを実行可能解の集合としてもつ最適化問題を考える.

レゴ中の最適解は目的関数値を改善する差分ベクトノL のみを加えてできるの単調端点列となる.

端点、で与えられる.グローシャーでは，得ることのでき定理 2.2P を性質 B を満たす凸多面体とする .μ= (;x: o,るレゴの最適解を探索していき，解が改善されなくなる

Xl ， … ，a: K ) が P の単調端点列ならば，その差分ベクトルまで繰り返すことにより，クロージャーの最適解に近いの集合 {di = が_;x: i- 1 1 iE {1 ， 2 ，… ， K}} は線形独立であ解を得ることができる.提案する局所探索手続きの特徴る.

を活かすため，次のような適用方法が考えられる.いく

これらの定理により，

P の K+ 1~闘の端点をもっ単調つかのヒューリスティック解法によって初期実行可能解端点列の差分ベクトルの置換すべてで作られる P の端点、を得てから局所探索手続きを実行する.また，分校限定は全部で 2 K 個あり.この端点集合をレゴと名づける.そ法に局所探索手続きを組み込み，暫定解の更新のためにして ，用いる.

P の端点、の部分集合 V で，V 中の任意の 2 端点、を結ぶ単調端点列から生成されるレコ刀 ;v に含まれるもの

提案する局所探索手続きを有効に適用するには，任意の中で，極小な部分集合を V のクロージャーと名づける.の 2 端点、聞の極大単調端点列を生成することが望まし

また，目的関数が線形で，実行可領域が性質 B を満たす

い.集合分割問題の実行可能解は，その問題の実行可能凸多面体であるとき次のことが成り立つ.

解集合の凸包の接点に 1 対 l 対応している.また，集合定理 2.3

分割問題の 2 つの異なる実行可能解 x ， y が得られたとP を性質 B を満たす凸多面体とする.任意の目的関数ベクトル C に対して P の端点 xKを min{cTxl;
x:E P} の最適解の 1 っとする.このとき ， P の任意の単調端点列(;x: O ， x 1 ，… ， x K ) においてCTX K が成り立つ.

1993 年 12 月号

CT

X 0 2C T X 1

ミ…二三き，次のようにして極大単調端点列が生成できる.集合分害Ij問題の係数行列を A とし ，1=Ulxj 乎 Yj} とする.

このとき行列 A は，グラフの頂点集合が I に対応し，校集合が A の行に対応している 2 部グラフ G の接続行列の© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(45)651転置行列である.また，集合分割問題の実行可能解集合利用した局所探索手続きを提案した.提案した局所探索の凸包の 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.の隣接関係を中心に示した.また，単調多面体の性質を

獅学生論文賞受賞論文

要約機

OnEigenvaluesoftheRateMatrixinaPH/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 は推移

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

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