最大平衡フロー問題に対する多項式時間確率モデルを仮定するが，そのモデルにおける対数最小二分探索アルゴリズム二乗法 (LL S) による推定を提案し，これによる推定が n 話 3 の場合は主固有ベクトんによるものと一致する

小樽商科大学中山

明

ことを証明する.また n ミ 4 の場合もある条件の下では2 端子ネットワーク N上での最大平衡フロー問題といLLS 法は主固有ベクトルによるもののきわめてよい近うのは最大フロー問題の一種で，最大フロー問題に 1 つ似を与えることをシミュレーションによって検証した.の制約条件が加わった問題である.制約条件は平衡係数線形計画問題の諸解法の最適解近くでの関数と呼ばれる関数日 :A→ R+ 一 {O} ，を使って示される.

振舞いについて

ただし A は N の校集合，

R+ は非負実数の集合とする.

この論文では，ネットワーク N の中で、与えられたすべ

統計数理研究所土谷隆，田辺圃士
双対標準形線形計画問題 (n 変数 ， m 制約式 ， n<m)ての関数が有理関数であるという条件のもとで，最大平minimize ctx ,衡フロー問題を解く多項式時間のアルゴリズムを提案す

subjectto Atx-b ミ 0 ，る.これは一種の二分探索アルゴリズムとパラメタを取

A=[ah …, amJERnxm ,り入れた Dinic の最大フローアルゴリズムを組み合わ

at (i =I , …, m) , c ， xERη ， bERm

せたもので，その手聞は O(max {l og(c*) , mlog( ず)，nm}T(n ， m)) である.ただし，げは技の容量の最大値，が =max{ ザ (a) :a ε A} (C(a) ， 甲 (a)(aôA) は ， a(a)=α a)j甲 (a) 豆 1となる自然数)， T(n , m) は ，n 個の点とm=IAI 本の枝を持つネットワークに対して最大フロー問題を解くのに必要な計算時間である.

トルが，“ dAF :dual affine-scaling 法による探索ベクトル"と“ dc: 制約式からなる線形不等式系の中心を見つけるためのNewton 法の探索ベクトル"によって張られる超平面上にあることを示した.本論文では“目的BIBD による AHP の解析
筑波大学高橋磐郎
AHP の数学的骨子は，一対比較のデータにもとづいた行列の主回有ベクトノL-に対する伊理一今井法，山下法はそれぞれ 2 次収束性，多項式性を持つ内点法である.山下は両方法の探索ベク関数 c が非退化である"とし、う仮定のみのもとで，山下の分解の 2 つのベクトルおよび伊理一今井法，山下法の探索ベクトルによる反復を解析し，それらが解の十分近くで次の 5 つの興味深い性質を持つことを示す.

(最大固有値に対する固有ベク(i)dc を(ー 1) 倍したベクトルによる反復は，最適解のトル)の成分をもって対象の評価値の推定値とするもの

十分近くから出発して適当にステップ幅を l に近づけてである.しかし対象の数 n が大きいと，一対比較の総数やると，可能領域内から最適解へ 2 次収束する. I 日)最適はきわめて大き〈なり人の観測者がそれらをすべて解の十分近くから，ステップ帽を μjctx(O< μ<1) とし一度に処理するのは困難あるいは不可能となる.て dAF による反復を行なうと，得られる点列は可能領域

そこて‘一対比較の全体をいくつかのグループに分割しの内点に留まり，目的関数値は最低 l 反復あたり約 μ /kて各グループに l 人の観測者を対応させて処理することより大きい割合で減少する(ここで k( ミ n) は解で activeが考えられる.本論文では，実験計画法や組合せ論の分な制約式の数).

野で古くから培われてきた，BIBD(balanced incompｭ

さらに，そのとき生成される点、列は，

central trajectory に引きつけられ， centraltrajecｭlete block design) による分割を提案し，これがわれtory の方向から解に漸近していく.

われの目的に適合するものであることをいくつかのシミ

探索ベクトルはュレーションによって検証する.に近づく. li吋制約式が退化していても，正確な直線探索

なおこの実験にさいして一対比較データに対するある250 (60)lüi)伊理一今井法の-dc ベクトルを l/lm-k) 倍したものを行なうと伊理一今井法は 2 次収束する. \v)最適解の十© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

分近くでは，山下法の探索方向は dual

affine‑scaling

法の探索方向に近づく.の問題である.
現在のところ，理論的に最も効率のよい内点法の計算時間は ， O(n 3 L) である.線形計画問題に対して計算時分散最小化問題の e ・近似解法

間が O( が L) で抑えられるアルゴリズムは Gonzaga と神戸商科大学加藤直樹

Vaidya がはじめて提案した.その後，小島，水野，吉分散最小化問題とは，たとえば，所与の資源を与えら瀬が線形相補性問題に対して Monteiro and Adler がれた有限個の活動に対して，配分された資源から生じる2 次計画問題に対して O(n 3 L) のアノL ゴリズムを提案し各活動の利得の分散が最小になるような資源の配分方法た.これらの O( が L) アルコリズムは，すべてセンターを求める問題である.

パス追跡法である.したがって，センターに近い初期点

厳密には次のように定式化される.有限集合 E と REの部分集合 S( 実行可能集合)および各 eEE に対して実数値関数 he (x(e)) が与えられているとき，S に属する

エ ={x(e) :eEE} に対してが得られる場合のみ適用できる.

本論では，広範囲の初期点に対して ，時間で解を求められるアノレコリズムを提案する.そのアルゴリズムは，水野が提案した点列を使った 0(n 3 . 5 L) のr(x) 三.E[he(x(e)) 一一J".Ehe(x(e))
J2e~E L...-f:，\-\-"
IEle~E

方法を基礎とする.水野の方法は反復あたり 0(11 3 )を z の分散と呼ぶことにする.この時，分散最小化問題とは， var(x) を最小にする XES を求める問題である.
本論文は最初にその問題の最適解を次のパラメトリック問題の最適解と結びつける性質について論じる.の計算を 0( 1Io.s L) 回繰り返す.

1 反復あたりの平均計算時聞を 0(11 2 • 5 ) に下げるために，Karmarkar が提案したランク・ワン・アップデイトを使用する.本論では，線形相補性問題を対象とし，しかも広範囲の初期点から出発するために，P(:l) :z (:l) 三

Karmarkar と同じような基準で行列をアップ・デイトしていない.したがって，独自の評価

minimize{.
E ({h e (x(e)) }2 ーえん (x(e))) IXES}.
eeE

すなわち，ある適当なパラメータ A に対するパラメト

リック問題 P (:l) の最適解が分散最小化問題の最適解と方法により 0( 1I 3 L) という計算時聞を求めている.

革新的技術進歩下の設備更新行動
東京都立商科短期大学なることを示す.この性質にもとづいて，ある仮定の下で，0( 1I 3 L) の計算

Pp) を入力データ長と泰夫

筑波大学鈴木久敏

1/ε の多項式回数解くことを必要とする←近似解法を提案する.次に，その解法が目下現有設備から新設備への更新を検討するさい，操業コ

1 番目ストの大幅な低下をもたらす革新的な設備が近い将来出のクラスはんが線形増加関数で S が.E x(e) が定数と現するなら，それが出現するまで現有設備の更新を延期

全多項式近似解法となる 3 つのクラスを与える.

eeEなる条件を含む線形不等式(または等式)で記述される場合で2 番目は，んが線形増加関数で， S が劣モジュラーシステムの基(または整数基)の集合である場合でし，逆に，それが近い将来に出現しないならば現有設備をそれと同じ旧系列の新設備で更新しようと考えることは自然であろう.

3 番目はんがある非線形関数で S がポリマトロ

本研究では，漸進的技術進歩とともに革新的技術進歩イドの基(または整数基)の集合である場合である，最が発生しうるような設備更新問題をとりあげ，従来漠然ある.

後にS が通常の単純な資源配分問題で現われる簡単な構造をしている場合，動的計画法にもとづく準多項式時と従えられていた上述の革新的技術進歩下の設備更新行動特性を，DP の定式化にもとづくコント口ーノl ・リミット政策によって理論的および実験的に解明する.特に間の手聞を持つ解法を提案する.

この設備更新行動特性が，本問題の特別かつ現実的な場線形相補性問題に対する点列を使ったo(n3L) アルゴリズムて基本的に規定されることを明らかにする.ついで，革東京工業大学水野真治
本論では，線形相補性問題に対して，計算時間が3O(n L) で抑えられる内点法を提案する.線形相補性問

題は，線形計画問題，
1990 年 4 月号

合としての複数代替案からの更新決定問題の構造によっ新的技術進歩の出現時点が予想されるときの設備更新をコントロール・リミットによって具体的に決定する方法を与える.

2 次計画問題等を含む広いクラス© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(61)251