• 検索結果がありません。

大規模複雑 なシステムの 最適化理論 と均衡化理論

N/A
N/A
Protected

Academic year: 2021

シェア "大規模複雑 なシステムの 最適化理論 と均衡化理論"

Copied!
18
0
0

読み込み中.... (全文を見る)

全文

(1)

大規模複雑 なシステムの 最適化理論 と均衡化理論

田 和

1

.緒

大規模複雑 なシステムを対象 に した従来の最適化手法は,分割原理 [1]み られるように部分 システム間の相互関係 を満た し,システム全体 の最適化 を達 成することを統合原則 としている

そのために分割原理では,部分 システムの 最適性 をある程度犠牲 にす ることによってシステム全体の最適化 を達成 してい 自律 した部分 システムが独 自の 目的関数に基づいて最適化 を達成 しょうと す るとき, このような方法では部分 システムの最適性 は保証 されない。

本論文では,大規模複雑 なシステムに対する上記の ような従来の最適化法の 問題点 を指摘 し,指摘 した問題点 を解決す るための方法 を提案す る。それは 「シ ステム全体 の最適化」の概念 に代 る 「部分 システム間の均衡化」の概念である。

この均衡化 を達成 す るために,本論文ではゲーム理論 の一分野である非協力 ゲームを適用 し,決定 に優先権が ない場合 の

Na s h

均衡解 と,決定 に優先権が ある場合 の

St a c ke l be r g

均衡解 を得 るための条件 を導 き,その妥当性 について 検討す る。

2.

最適化理論

2. 1

最適化問題

最適化問題 を一般的に記述す ると次の ようになる

〔 73〕

(2)

7 4

Mi n. /( α)

s ub.t o g( x) <

b

h( x) ≦0

≧0

商 学 討 究 第47 巻 第 4 号

1HnHu1

日山川一

しiiZ

IHhH川1

1

2

3

4

iZg

iZlt

iZq

nⅦトロ

ここで

x∈R n , b∈Rl ,

9,

h

m

次ベ ク トル関数,

n ‑ ∑ 77 =1 ni

である。

この最適化問題が

1 1 1

Mi n. i Z ‑ 1 fi ( xi )

nl

s ub.t o ∑ gi ( xi ) ≦b

i ‑I

hL ( xi ) ≦ 0, i ‑1, ‑・ , m xi ≧0

,

i ‑1 ,‑ ・ , m

と書 き換 えることがで き, これが 別 個 の部分最適化 問題

Mi n. f i ( xi )

s ub.t o gi ( xi )≦bi hi ( xi ) ≦O xi ≧0

) 1 1 7 \ノ 9 0 「⊥ 2 ( l 1 1 i Zq lHはt u iⅦ 相川p

に分割で きる場合 を考 える。 ここで

xi ∈Rn i , bi ∈RL

,

∑ ? = lbi ‑b

であるo ま

xi ‑( xi ∈Rn L r gi( xi )≦

bi

,hi ( xi ) ≦0 ,xi ≧0 )

とす る 大規模複雑 なシステム は,その最適化問題 の決定変数 xや制約条件式 9,

h

の数が単 に多 い とい う規 模 の大 きさだけでな く,式

( 9 ) 〜( 1

2)め部分最適化 問題で記述で きる局所性 を持つ 部分 システムの存在 を認識で きるシステムである

2.2

分割原理 による最適化

大規模複雑 なシステムを対象 に した従来の最適化手法 は,分割原理 にみ られ るように部分 シス テム問の相互 関係 を満たすために,それ らを統合 す る コー ディネータを部分 システムの上位 に設置 している。 このコーディネー タは部分

(3)

大規模複雑なシステムの最適化理論と均衡化理論

7 5

システム間の相互関係 を満た し,かつ システム全体 を最適 にす るために部分 シ ステム間の調整 を行 う す なわち,式(

5) 〜( 8)

の最適化 問題 に対す る

Lagr a nge

関数 を

L( x i ,A) 全三 i = l fi ( xi )

+

l T(三

gi(

Xi )‑a)

+三

( L i Thi ( xi )

i =l i =1

l l

J

‑ i

i

( fi ( xi ) + }Tgi ( xi )+pi T hi ( xi )) ‑1T

b

と定義す ると,部分最適化 問題 は次のようになる。

Mi n. fi ( xi ) + }T gi ( xi ) s ub.t o hi ( xi ) ≦O

x , . ≧0

( 1 3)

Eii Z] 円■ー山川 一 ー ノー 4 5 6 1 1 1 ( ( ./し

ここで

ス∈ R E , f Li∈ R k L

Lagr a nge

乗数である

これは

Lagra nge

乗数 )を統合変数 とす るもので, コーデ ィネー タはシステ ム全体 の最適イヒを達成す るため に統合変数 )を適当に定める (図 1) この方 法 は "価格 による統合 "と呼ばれてお り, この方法以外 にも

b

iを統合変数 とし た ''資源配分 による統合 ''な どがある

Coo一 di nat Or

Subs ys t e m

i

入F i +1‑入K+

Mi n. f i ( 訂i )

+

T

g i ( 正i ) s ub.t o hi ( Ci )≦0

1

価格 による統合 (K :繰返 し回数, ∈ステ ップ幅)

(4)

7 6 商 学 討 究 第47巻 第 4 号

2.3

これ らの統合原則では,システム全体 の最適化問題が与え られているとき,

( 1 )

のシステム全体 の 目的関数 と式

( 2 ) ,( 3 )

の制約条件が式

( 5 ) 〜( 7 )

の ように分離 して記述することがで きるとい う"分割可能性 に関する前提条件 '',あるいは 逆 にシステム全体の最適化問題が存在せず,式

( 9)

の部分 システムの 目的関数 と 式(10)の制約条件式が式

( 5) ,( 6)

のように加算することがで きるとい う "加算性 に 関する前提条件 ''を必要 としている。前記の統合原則 は,この前提条件 に基づ いて行 われるのであるが,従来の研究で これ らの前撞条件 を明示 しているもの はほとん どない。 これは, システム全体 の 目的関数

f( x)

が存在す るか,ある いは

f( x) ‑¢V l( xl )

,fZ

( x2

),

・ , f m ( x m) )

とい うようにシステム全体 の 目的 関数を部分 システムの 目的関数を持いて構成す ることがで きる, という仮定 を 暗黙の うちに認知 していることによる

システム全体 の 目的関数がすでに存在 している場合,これを分割 して小規模 な最適化問題 をい くつか作成することは,計算効率の立場か らその必要性 を認 識することがで きる。他方,部分 システムの 目的関数のみが存在 し,システム 全体の 目的関数が存在 しない場合,前述の加算性 に関する前提条件 の妥当性 と 共 に,システム全体 の目的関数を構成す ることがで きるのか とい う問題点 を檎 討す る必要がある。経済学

[2]

や組織論 [

3

],システム理論

‑[4]

ではシ ステム全体の 目的関数が存在 しない場合 の最適化問題が論 じられている。

これ らの議論 は,部分 システムの目的関数によってシステム全体の 目的関数 が必ず しも構成で きないこと,すなわち

f( x)

‑4)V

l( xl )

,

f2( x2 )

,,f m

( xm))

が成 り立たないことを示唆 している。 とくに部分 システムの 自律性が高い 自律 分散システムなどの場合,部分システムが独 自の 目的関数 を最適に しょうとす るとき,加算性 に関す る前提条件 などによってシステム全体の 目的関数を構成 し,システム全体の最適化 を行 うと,部分 システムの最適化が達成 される保証 はない。 このように部分 システムの 目的関数でシステム全体の 目的関数を構成 で きる保証はな く,た とえ構成で きるとして も,部分 システムの最適化 を達成 で きるという保証 もない。

(5)

大規模複雑なシステムの最適化理論 と均衡化理論

77

分割原理で は,部分 システム間の相互関係 の調整 は上位 レベルの コーディ ネータが行 うので,部分 システムはコーディネー タによって提示 された統合変 数 を用いて式(14)〜(16)で与 え られる最適化 問題 を他 の部分 システム とは独立 して 最適化 を行 う。 したがって,他の部分 システムの変化 はコーディネータの統合 変数の変化 を通 じて知 ることになるので,最適化 の繰 り返 し過程で変化 に対す る反応が遅れる。 これは各部分 システムの情報が コーディネータに集中 してい るためで,部分 システムはコーデ ィネー タが これ らの情報 に基づいて決定 した 統合変数 を介 して間接的に しかその変化 を知 ることがで きないか らである

2.4

多 目的最適化,同時最適化

あ るシステムを異 なった視点 に基づ いて記述す ることをス トレー タと呼ぶ (

2) [5

〕。ス トレー タ化 されたシステムは,相互関係 を持つ複数の部分 シ ステムで構成 され, システム全体 の 目的関数が定義 されない場合がある。ある システムを相互関係が存在す る異 なったい くつかの最適化問題で記述すること がで き,それ らの最適化問題 を同時に最適化す る場合 な どがス トレータ化 の例 である

この ようなシステム全体 の 目的関数が存在せず,部分 システムのみが 目的関数 を持 ち,部分 システム間に相互関係が存在す る最適化問題 の場合,意

2

ス トレータによる記述

(6)

7 8 商 学 討 究 第47 巻 第 4 号

思決定主体 について検討する必要がある。

システム全体 に対 して意思決定主体が唯一であ り,かつ部分 システムの 目的 関数が競合 している場合,最適化問題は下記の ような多 目的最適化問題 となる。

Mi n. I( x) ‑ Vl ( xl ) , f 2 ( x2 )

,‑ ,

f m( xm ) )T

J I ‡

s ub.t o i ∑gi ‑1 ( xi ) ≦b

hi ( xi ) ≦ 0, i ‑1, ‑・ , m xi 20

,

i ‑

1,・・

, m

(

1

7) ( 1 85

( 19 ) ( 20)

この場合,意思決定主体 はパ レー ト最適解の中か ら妥協解 を合理的に兄いだす 必要がある [

6

] 。 この安協解 を選択するための基準が明確であれば,式

[ 17]

で与 えられるベク トル目的関数はスカラー化することがで き,問題は単一 目的 最適化問題 となる。妥協解 を選択す るための基準 は一般的には明確でないので,

これを行 うために例 えば

Ha i me s

らが提案 している

SWT

[7]

のように意 思決定主体 のパ レー ト解 に対す る評価 を定量化す る必要がある

。 SWT

法では 意思決定主体の評価基準の連続性 を仮定 して代用価値関数 を近似的に求めてい

るが,この仮定には無理があるといえる。

意思決定主体が各部分・システムに存在 している場合,すなわちシステム全体 では複数の意思決定主体が存在するとき,各部分 システムの意思決定主体 は部 分 システム問の相互関係 を満たす ように自らの目的関数を最適に しなければな らない。 この ときの部分 システムの最適化 問題 は,

個の最適化問題 を同時 に最適化する次の ような同時最適化問題 となる。

Mi n.

fi(xl*,

, X

た1

, X

i

,菰

1,

,Xm *)

s ub.t o g

j(xl*,・・

,X, f

̲1

, X

i

,虎

1,・・

,Xm *) hi ( xi ) ≦O

xi 20

p nr EⅣn u pn Hl M ■.■1mH一 1 2 3 4 2 2 2 2 /̲\ ′し ( ./し

このような状況では,部分 システムの意思決定主体 は他の部分 システムの最適

(7)

大規模複雑なシステムの最適化理論と均衡化理論

7 : 9

決定

x

,

F, j辛i , j=

1,

, m

を知 る必要がある。いま,すべての

x, F∈ xj

に対 し

ri ( x

l*,‑・

, X

た1

, X i *

.1,

‑ ,Xm * )

‑f x i * ∈Xi J f i ( x

l*,・・・

, X , ・ *

̲1

, a , F , x i *

.1,

,3m *)

≦J;I(xl*,・‑

,

1 ,Xi ,菰 1,‑ ,Xm *))

(25)

を定義す る. この riは (最適)反応戦略集合 と呼ばれ,すべ ての

xj∈ X,

・に対 して riが唯一存在す るとき,

r

iを反応関数 とい う。各意思決定主体 は,他 の部 分 シス テムの決定

x ,

Fを推測 して この反応戟略集合 に基づいて 自らの決定 を行 わなければな らない。 この推測 に基づいて行われた決定 は他 の部分 システムに よって推測 されるので,部分 システムの問で推測が繰 り返 されることになる。

3. 均衡化理論

3. 1

情報交換 と均衡解

本章ではシステム全体の 目的関数が存在せず,各部分 システムに意思決定主 体が存在す る場合 を取 り上 げる。 システム全体 の 目的関数が存在 しない場合, 部分 システムの情報が集中す るコーディネータが存在 しないので,部分 システ ム間の相互関係 を満 たす ように部分 システムが調整 しなければな らない。 これ を行 うために,各部分 システムが持つ情報 (目的関数や制約条件の構造,係数 の値 な ど) を最適化 を行 う前 に互いに交換すれば,相互関係 を満たす最適決定 を行 うことがで きる。この ような決定問題 はゲーム的決定問題 [8]と呼ばれ, ゲーム理論 における非協力 ゲームの理論 を適用す ることがで きる

とくにある 意思決定主体が他の意思決定主体 の決定の もとに自らの決定 を行 うときを "汰 定 に優先権がある "といい,その ときの解 を

St a c ke l be r g

均衡解 といい,決定

に優先権がない場合 の解 を

Na s

b均衡解 とい う

部分 システム間で交換で きる情報 には,最適決定 を行 う前 に知 ることので き る事前情報 と,最適決定後 に初めて明 らかになる事後情報がある。前者 は 目的 関数や制約条件式の構造,あるいはデー タとしてあ らか じめ与 えられている係

(8)

80 商 学 討 究 第47 巻 第 4 号

数の値,過去の決定変数の値な どであ り,後者は最適化問題 を解 くことによっ て決定 される変数の値やその ときの 目的関数の値 などである。各部分 システム は他 の部分 システムの事後情報 を最適決定前 には知 ることがで きないので,情 報交換が全 くなされなければ,推測の繰 り返 しとなる。各部分 システムが事前 情報 を部分 システム間で交換す ることによって相互関係の調整 を行 うことがで きれば,部分 システムの最適解 を得 ることがで きる このようにして得た最適 解 は部分 システム間の相互関係 を満た しているが,システム全体の最適解 には 必ず しもなっていないので,本論文ではこれを "均衡解 ''と呼び, この均衡解

を求めることを "均衡化 "と呼ぶ ことにする

3.2

非協力ゲームによる均衡化

3. 2. 1

決定に優先権がない場合 の均衡化

部分 システムの決定 に優先権がない ときの均衡解 は

Na s h

均衡解 として知 ら れてお り,次のように定義 される。

個の部分 システムが

Na s h

均衡解 を採用 しているとき,いず れの部分 システムについても自己の 目的関数 を改良するような解

は存在 しない。

この定義 を式el)を用いて表現す ると以下のようになる

o

v x i ∈Xi

N

, i‑1

,

, m

に対 して

f i ( x

l*,・‑

, 虎

1

, 戒 菰

1,

,Xm *) ≦ fi ( x

l*,I

,虎 1 ,Xi ,菰 1

,‑・

,Xm *) ( 26 )

であれば, この とき

x ∈xi N

Na s h

均衡解である [

9

]。 ここで

xi N‑( xi ∈Rn L lgi ( x

l*,

,

1

,Xi ,

1,

,Xm *)≦bi ,hi ( xi ) ≦0 ,xi ≧0)

である。いいかえれば,式(紬は,

m

個 の部分 システムの相互関係 を満たす均 衡解 を得 るためには,それぞれの均衡化問題が同時に均衡化 されなければな ら

ない ことを意味 している この

Na s h

均衡解 の存在性 は

Na s h

自身によって証 明されてお り,存在定理の証明は

[ 1 0 ]

で不動点定理 を用いて証明されている

e l )

〜e4)で記述 される部分 システムの均衡化問題の

La gr a nge

関数を

(9)

大規模複雑なシステムの最適化理論と均衡化理論

87

Li ( 3

1,‑

, X m

,ん

,F l i )

f i ( x

l,

,X m)

+

} T( gi ( xl

,・‑

, X m)‑ bi

)+ELiT

hi ( xi )

と定義す る と,式郎)によって定義 される xi*

, i ‑1,

・‑

, m

が均衡化問題の

Na s h

均衡解 であるための必要条件 は

∀i

に対 して以下の ようである

aL

i =

意 fi(xl*・・‑

,Xm * )・1㌢ T 怠g i ( x l * ・ ・ ・

,Xm*)

・pT

T

孟 hi

(

x,P)

‑o

普 ‑gi ( x

l*,

IXm *)

帖 0 些 a pt ⊥‑hi ( xl f ) ≦o

}㌢T( gi ( xl * ,

‑ ,Xm *)‑ bi )‑0 F E ET hi ( 扉 )‑0

ス㌢

≧0,

F L f

≧0

( 27 ) ( 28 ) ( 29 ) ( 30 ) ( 31 ) ( 3 2 )

一般的には,式¢

7 ) 〜( 3

2)の必要条件 を満たす

Na s h

均衡解 は唯一 には定 まらず, 解集合 の形 になる。 しか しなが ら,部分 システムの均衡化 問題がある種 の

2

計画問題の とき,

Na s h

均衡解 は唯一存在す ることが知 られている

[ 1 1 ] 。

3. 2 . 2

決定 に優先権がある場合 の均衡化

St a c ke l be r g

均衡解

[ 1 2

]は,次の ような規則 の もとで決定が行 われる

[ 1 3

]。

決定 に先手

( l e a de r )

と後芋

( f o l l o we r )

の区別が あ り,先手 が戦略 を示 した後 に,後手がそれを知 って 自分の戟略 を決定 し, ゲームは終了す る。

これは先手である部分 システムにとって最 も良好 な解 を合理的に決定す るため の規則 である 後手である部分 システムは先手に対 して受動的で,先手が示 し た解の もとで 自らの問題 を最適化す る。

い ま,部分 システムが

2

つの場合

( 〟 ‑2)

を考 える

部分 システム

1

が先 手で決定 に優先権があ り,部分 システム

2

が後手であるとす る

部分 システム

(10)

8 2 商 学 討 究 第47巻 第 4号 2

は部分 システム

1

の任意の決定

xI S∈x

lに対 して,

f2 ( X

I

S ,x2 S )≦f2 ( X

I

S ,x2 ),x2 ∈x2 ( 33)

となるように

x2 S‑T( XI S )

を選ぶ。 ここで

T(

)は任意の関数である。 この とき

f l ( X

I

S ,T( XI S ) )≦ fl ( xl ,T ( xl

))

,Xl ∈X l ( 34)

となるような

xI S∈x

l

,x2 S‑T( XI S )

が存在すれば

,( X

I

S ,x2 S )

は部分 システム 1を 先手 とす る

St a c ke l be r g

均衡解である。 この均衡解の存在性 については

[ 1 4]

で証明されている。

部分 システム

2

の均衡化問題は,任意の

xl O ∈x

lに対 して

Mi n. f2 ( x 1 0 ,x2 )

s ub.t o g2 ( X I O ,x2 ) ≦b 2

h

2 ( x2 )≦0

∬2 ≧0

と書 くことがで きる この間題に対する

La gr a nge

関数は

L 2 ( X

I

O ,x2 ,}2 ,P2 )

f2 ( X

I

O ,x2 ) + } r( g2 ( X

I

O ,x2 )‑ b 2 ) + I L Ih 2 ( x2 )

これより最適性の条件 は以下のようになる。

慧 一 志 f2 ( X I O ,x2 *) ・}2 *T孟 92 ( X I O , x2 * )

・p*2 T % h 2 ( x2 * )‑0

% ‑g2 ( x I O ・x2 *)‑ b 2 <0 些 旦‑h2 ( x2 * )≦0

∂〝2

} 2 *T ( g2 ( X I O ,x2 *) ‑b 2 )‑0

灯 れu EliZ I ー ノー IU 5 6 7 8 3 3 3 3 ′し ′し ( (

( 39) ( 40) ( 41)

( 42)

(11)

大規模複雑 なシステムの最適化理論 と均衡化理論

F E 2 *T h 2 ( x2 *) ‑0 ス 2 * ≧0 , E L 2 * ≧0

83

決定 に優先権 のある部分 システム

1

の均衡化問題 は,上記の部分 システム

2

最適条件式 を考慮 して次の ようになる

Mi n. f l ( xl ,x2 )

s ub.t o g l ( xl ,x2 ) ≦b l hl ( xl ) ≦0

監 + j I慧 ・p 濃 ‑o

g2 ( xl ,x2 ) ≦b 2 h2 ( x2 ) ≦0

∬ 1 ≧0

この間題の

Lagr a nge

関数 は

Ll ( xl ,x2 ,A

l

,ス2 , Fll ,F

EZ

, i) 1 ,リ2 ,リ3 )

全fl ( ∬ 1 ,x2 )

+

} T( gl ( 3 1 ,32 )‑ b l ) 十 F E T h l ( xl )

h T ( 監 ・増 . 穏 )・y !( 92( xl

・x2

,‑b 2

,

h lhB( x2 )

となる。 これ より最適性 の条件 は,以下のようになる

aL

l

有 志 fl ( x

I

S ・x2 S ,・が ま gl ( x

I

S ・x2 S ,・pfT孟 hl ( XI S ,

・ u f Tf ( 監 ・lf T 豊 ・p言T 慧 )

・y2 ST

g2 ( x I S ・x2 S ,‑o

F nu lp肌H I ー nu一 5 6 7 4 4 4 nⅦ川 U nⅦ■川p iⅦ t

( 48)

Eiii ZI p nu R■In u 9 0 1 4 5 5 inlL川U iZE iZq

( 5 2 )

(12)

84 商 学 討 究 第47巻 第 4 号

∂エ 1

= gl ( X I S ,

x

2 S ) ‑b l

≦0

土‑hl ( XI S) ≦0 aF L l

a ‑% ・} fT e ・ p

f

T 2 ‑o

aL 1

‑ ‑92 ( X I S , x2 S )‑b2 < ̲0

∂2 ) 2

些 ‑h2 ( x2 S )≦o

∂Z J 3

}f T( g l ( X I S ,x2 S )‑

b

l) ‑ 0

F L f T hl ( XI S )‑o

L ' 2 S T ( g2 ( S I S ,x2 S )‑b2 )‑0

リ , S T h2 ( x2 S )‑o

} f ≧0,1

O

,f L f ≧

O

,F l 雷 ≧ O, i , f≧

O

,L J 2 S ≧

O

,z J 3 S≧o

) ) ) ) ) 3 4 5 6 7 5 5 5 5 5 ( ( ( ( ( ) ) ) ー ) 8 9 0 1 2 5 5 6 6 6 ( ( ( ( (

この条件 において,x2S,

}

,EL言が,た とえば任意の関数

T(

・),

H

(・),

K(

・) を用いて

x2 S‑T( XI S )

,

}言‑H ( XI S )

,

p言‑K ( XI S )

と陽的に表す ことがで きれば, 式(52)〜(62)は,xl

, ll , FLl , リ1 ,2

)

2 , y3

について解 くことがで きる

f i ,

g

i

,hiが ともに線形関数である場合

[ 1 5 ]

と,先手の最適化問題が線形 計画問題で,後手の最適化問題が

2

次計画問題の ときの最適化解析が行われて いる

[ 1 6 ] 。

3. 3

いままでに述べてきた均衡化問題の妥当性 を検討するために,

2

つの部分 シ ステムで構成 されるシステムを考える各部分 システムの最適化問題 は次の よ

うであるとする

部分 システム 1 :

Ma x ・fl ( x l ・x2 )‑一 言( 31 2 ・x 1 32十 x2 2 )・10xl ・1432 ( 63)

(13)

大規模複雑なシステムの最適化理論 と均衡化理論 部分 システム 2 :

Ma x ・f2 ( x l ,x2 ) ‑ 一 言( 231

2

・2xI x2 ・か 1531 ・1232 ( 6 4) 85

flとf2を図示す ると図

3

のようになる。点

A

は部分 システム

1

を単独 で最適化 した ときのの最適解で

xl *‑4,32 *‑12,j i *( x

l*

,x2 *)‑104

である。点

B

は部分 システム

2

の最適解でx

l *‑3

,x

2 *‑9

,f

2 *( xl * , x2 * )‑79. 5

である。

fl,f2が加算可能で,次の ようにシステム全体 の 目的関数

f ( xl , x2)

f l( xl, x2)

f2( xl, x2)

によって構成で きるとす る。

I( 3 1 ,32 )‑ f l ( x l ,x2 )+f2 ( xl ,x2 )

一言( 3 x1 2 ・33 1 x2 ・2 x 2 2 ) ・25 xl +26 x 2 ( 65)

これを最大 にす る最適解 は国中の点

C

x l g

‑普,

x 2 8

‑号 であ り,その ときの 各部分システムの目的関数の最適値は

fl g( x

l

g,

32g

)‑102. 07 , f2 g( x

lg

,

X2g

)‑75. 00

である。

意思決定主体が単一の とき,最適化問題 は次の多 目的最適イヒ問題 になる.

Ma x. t fl ( x

l

,x2 ),f2 ( 3

1

,32 )) ( 6 6 )

この間題のパ レー ト最適解 は曲線

ACB

で,その近似関数 は次のようである

.

32 ‑‑ 1. 54x1 2 +12. 21x 1 ‑1 2. 23 ( 67)

部分 システム

1 , 2

の反応関数は

a fl /∂ xl , a f2 /∂x2

よ りそれぞれ次の ようになる

rl(

x 2 ) ‑ 1 0一

書x2

Y 2( xl )‑12‑31

(14)

86 商 学 討 究 第47 巻 第 4 号

3

最適解 ,パ レー ト解 ,均衡解

表 1

最適解 ,パ レー ト解 ,均衡解

xl

l

x2

l

fl

l

f 2

A 4. 00 1 2. 0 0 1 0 4. 00

ち 3. 00 9. 00 7 6. 5 0

C 2. 9 3 1 0. 8 0 1 02. 07 75. 0 0

D 8. 00 4. 0 0 8 0. 0 0 6 4. 0 0

E 2. 00 1 0. 0 0 9 8. 0 0 76. 0 0

F 5. 5 0 9. 0 0 1 0 0. 6 3 70. 25

ACE x2‑ ‑ 1 .54x 2 1 + 12.21x1‑ 12.23

(15)

大規模複雑なシステムの最適化理論と均衡化理論

87 Na s h

均衡解 は図中の点

D

で,

ガ ‑8

,

∬ Ⅳ2 ‑4

。 この ときの 目的関数の最適値

fl N‑80 ,f2 N ‑64である。

部分 システム

1

が先手の

St a c ke l be r g

均衡解 は,後手である部分 システム

2

の最適条件 を制約条件 とした次の間題 を解 くことによって求めることがで き る。

Ma x ・ fl ( 3 1 ,32 ) ‑‑ i( x1 2 +xI x2 +x2 2 )+10 31 +1432 s ub.t o xl

+

x2 =12

J l ≧0

制約条件式(71)よ りx

2 ‑T ( xl ) ‑12‑ xl

.これを式仔2)に代入すると

fl ( x l ) ‑‑ix 1 2 +231 +96

田 川1 Gid F nu O 1 2 7 7 7 iZq nⅦ 柑u iR

( 73 )

これを解 くと先手である部分 システム 1の均衡解 は

xI S l‑2

となる。 これより 後手の最適決定は

x2 S 1 ‑1 2‑ x I S 1 ‑10

となる (

E)。

その ときの 目的関数の 値 は

f l S 1‑98 ,f2 S 1‑7

である。

部分・システム

2

が先手の場合 は,次のようになる。

Ma x ・ f2 ( xl ,x2 )

‑一

書( 231 2 ・231 x2

+

x 2 2 ).15xl +1232 ( 7 4) s ub.t o 2∬1 +∬2 ‑20

x2 ≧ 0

この場合の

St a c ke l be r g

均衡解 は図中の点

F

GI S 2 ‑5 . 5 ,x2 S 2 ‑9 ,f l S 2 ‑1 00. 6 3

,

/㌔2‑72. 25

である これ らの解 をまとめると表 1のようになる。

flとf2が加算可能であるときのシステム全体 の最適解 は点 Cであった。 こ の点は図か らも明 らかなように各部分 システムの最適解 にはなっていない。 シ ステム全体の最適化 よりも部分 システムの最適化 を優先す るのであれば,各部 分 システムは

x f

,j=1,2に対す るri(xfl,xf)

‑0 ,i

≠jとなる

xf

lなる解 を選 択す る。いまの場合,部分 システム

1

x2 g‑1 0. 80

,に対 してxlg1

1 . 53を選択

(16)

ββ 47 巻 第 4 号

し,部分 システム

2

は X

l g ‑2 . 9 3

に対 して

x2 g 1 ‑9 . 0 7

を選択す るC さらに

x

l

g

l 対する部分 システム

2

の最適決定は,x2

g 2 ‑7 . 40

であ り,

x2 g

lに対す る部分 シス テム 1の最適決定は

xl g 2 ‑5 . 4 7

となる. この ように各部分 システムの最適決定 は,

ri

上 を移動 していき,点

D

に収束する. また任意の

xj' 0

'を初期値 として

j i ( x l ,x2 ) ,i

tjを最適化 し,その解

xi ' 1

'を用いて

f j ( x

i

' l ' ,xj )

を最適化すると い う繰 り返 し計算 を行 って も解 は点

D

に収束す る。 この ように点

D

Na s h

均衡解 は,

2. 4

節で述べたス トレータ化 された最適化問題の最適解である。

これは自律 した部分 システムで構成 されるシステムにおける決定に優先権のな い場合の最適解 となる。

決定 に優先権がある場合,

St a c ke l be r g

均衡解 は後手の反応戦略関数上 に必 ず存在す るので後手の最適性 は保証 されている。 この後手の最適性 を保証する とい う条件の もとに先手の最適化 を行 うので点 Eあるいは点 F以外 に最適解 は存在 しない。

4

.結

本論文では,以下のことを行 った。

・大規模複雑 なシステムに対す る従来の最適化手法 として分割原理 を取 り上 げ,その問題点 を指摘 した。

・システム全体の 目的関数が存在 しない場合 の大規模複雑 なシステムを対象 に,従来の最適化の概念 に変わる均衡化の概念 を提案 した。

・均衡化の方法 としてゲームの理論の一分野である非協力ゲームを適用 し, 決定 に優先権がない場合 の

Na s h

均衡解 と,優先権がある場合 の

St a c ke l ‑ be r g

均衡解 を求めるための条件 をそれぞれ導いた。

・提案 した方法の妥当性 を検討 した。

(17)

大規模複雑 なシステムの最適化理論 と均衡化理論 89

本論文 を執筆するにあた り多大なご協力 を賜 った小樽商科大学情報処理セ ン

ターに対 して謝意 を表する。

(18)

90 47 巻 第 4 号 参考文献

[1] た と え ば L. S. La s d o n: O pt i mi z at i o n The o r yfo rLar geS ys t e ms , Ma Cmi l l a n , ( 1 9 7 0 ) ,志水清 孝 ( 釈) :大規模 シス テ ムの最 適化 理論 , ( 1 9 7 3 ) , 日刊 工 業 新 聞社 。

[2]K. J . Ar r o w: So c i alCho i c eandI ndi v i du alVa l ue s ,Ya l eUni v. Pr . , ( 1 9 51 ) ,長名 寛 明 (釈 ) : 社 会選択 と個人的評価 , ( 1 9 7 8 ) ,日本経済新 聞社 。

[3]Y. S. Li nc o l n( ed . ) . ・07 ga m' z at i o nalThe o ry andI nq ui r y/The p ar a

d

i gm r e v o l u‑

t i o n,SagePub. ,( 1 9 85 ) ,寺本 ,神 田,小林,岸 ( 釈) :組織理論 のパ ラダイ ム革命 ,( 1 9 9 0 ) , 白桃書房 ,43‑8 2 0

[4] 中野文平 :大親模 シス テム理論,計測 と制御 , Vo l . 2 5 , No . 3 ,( 1 9 8 6 ) , 2 0 4 ‑ 21 00 [5 ]M. D. M e s a r o v i e , D . M a c ko , & Y . Taka ha r a:Th e o r y o f m e r a r c h i c al , Mu l t i l e ve l

S ys t e ms ,( 1 9 7 0 ) , Ac a de mi cPr e s s .

[6 ]た と え ば J. L. Co ho n: M ul t i ob j e c t i v ePr o gr ammi n gandPl anni n g,( 1 9 7 8 ) , Ac a de mi cPr e s s .

[7 ]Y. Y. Ha i me s , W. A. Ha l l , & H. T. Fr e ed ma n: Mul t i ob j e c t i v e O pt i mi z at i o n i n Wat e rRe s o ur c e sS ys t e ms , ( 1 9 7 5 ) , EI s e vi rSc i e nt i f i cPub. .

[8 ]市川惇信 :意思決定論 ,( 1 9 8 3 ) ,共立 出版 ,2 0‑21 。

[9]J . Na s h: No n‑ Co o pe r a t i veGa me s , An7 1 a l so fMa i he mat i c s ,Vo l . 5 4 , No . 2 , ( 1 9 51 ) . [ 1 0 ]∫ . B. Ro s e n:Exi s t e nc ea ndUni que ne s so fEqui l i br i um Po i nt sf o rCo nc a veN‑

Pe r s o nGa me s , Ec o no me i r i c a ,Vo l . 3 3 , No . 3 ,( 1 9 6 5 ) , 5 2 0 ‑ 5 3 4 .

[ 1 1 ]T

.

Ba ! r ,G. T. 01 s de r . I Dynami cNo nc o o pe r at i v eGameThe o r y ,( 1 9 8 2 ) ,Ac ade mi c Pr e s s , 2 4 3 ‑ 2 4 5 .

[ 1 2 ]H. Yo n St a c ke l be r g: The The o r y o f t heMa r ke tEc o no my,( 1 9 5 2 ) , Wi u i a m Ho dgea ndCo . .

[ 1 3 ]鈴木光男 :ゲーム理論入 門, ( 1 9 81 ) ,共立出版 ,5 4 。

[ 1 4]M. Si ma nn:Ont heSt a c ke l be r gSt r a t e gyi nNo nz e r o ‑ Sum Ga me s J. o f

O

pt i 一 mi z at i o nThe o r yand4秒I i c at i o ns ,Vo

l.l

l , No . 5 , ( 1 9 7 3 ) .

[ 1 5 ] 奥 田和 垂 :分権 的 シス テム にお け る資源 配分 に よる統合 問題 の解析 , シス テ ム と制御 , Vo l . 29 , No . 9 ,( 1 9 8 5 ) ,6 01 ‑ 6 0 80

[ 1 6 ] K. Okuda :St udi e so fCo o r di na t i o nPr o bl e m i nDe c e nt r a l i z edPr oduc t i o nSys ‑

t e ms , Z nt .Co n fe r e nc eo nEc o no mi c s

/

Ma na ge me nta ndI n fo r mat i o nTe c hno l O ‑

gy ,To kyo I J a pa n , ( 1 9 9 2 ) ,1 81 1 1 8 4.

参照

関連したドキュメント

1989 年 AT&amp;T LP ソルバ KORBX と専用コンピュータ (8.9M$) の抱き合わせ販 売を開始..

(「 best な解」であるか どうかは運任せ , あるいは探索の仕方に工夫をこらす...

ベルタランフィは生物をエネルギーの開放システムとしてとらえたが,彼の言うような実体

●乗務員の輸送手段への割り当て ●保全や点検のスケジュールの決定およびその実施 5.輸送計画最適化

略が存在するならば,それは唯一であり 研一志) (山王)=(∽+志・ となる.存在の必要十分条件は,任意の∬<椚に対し

MGST ではシステムは集合論的関係すなわち集合で あるから,システムを集めて大きいシステムを考えるこ とが可能である.すなわち S&#34; …,めをおのおのシステ

本稿では , ロバスト Nash 均衡解の一意性 について , コスト関数の不確実性を考慮しない場合でかっ, Nash 均衡解が一意であるものを取り

良い特徴付け (good characterization) というのは,単なる褒め言葉ではなく,厳密な 意味の定義された専門用語なのです.答えが Yes か No