2012MP 09 最近の更新履歴 小野 廣隆 (Hirotaka Ono)

担当： 経済工学部門 小 廣隆 hirotaka@en.kyushu-u.ac.jp

 線形計画 ーム理論

◦ ^{非協力 ーム}

◦ ^{協力 ーム}

 非線形計画 一部

 ー

◦ 11/21,12/5 (11/28 ^{曜 授業＇}

◦ 12/12,19: 休講

◦ ^1/9,16

◦ ^{1/23 教場試験}

 ₂ ベクト 存在し ，

◦

◦

満 ， _{2人ゼ 和} ーム

均衡解 いう

Y

X 

 , *

* y

x

*)

*,

( x y











i

n

j

j i ij m

i

n

j

j i

ij

^{x y a x y}

a

X

1 1

*

*

1 1

:

x















i

n

j

j i ij m

i

n

j

j i

ij

^{x y a x y}

a

Y

1 1

*

*

1 1

*

( )

)

(

:

(1)

(2)

 列プ ー ー 戦略 あ 場合，行プ ー ー 期待損失 最小化 戦略

 行プ ー ー 戦略 あ 場合，列プ ー ー 期待損失 最小化 戦略

*

x

*

y

*

x

*

y

均衡解 存在 ば，い プ ー ー

戦略 変更 得策 い

 _{う 支払い行列 A} 対し ，均衡解 存在

 均衡解 一意 定ま い場合，任意 二 均衡

解 対し ，

成立

)

'

,

'

(

*),

*,

( x y x y







i

n

j

j i

ij m

i

n

j

j i

ij

^{x y a x y}

a

1 1

1 1

*

*

' '



捕題

均衡解 あ 必要十分条件

成立 こ

 証明

◦ ^{見や さ ， く．}

Y

X 

 , *

* ^y

x

m

i

y

x

a

y

a

m

i

n

j

j i ij n

j

j

ij

^{, 1 , 2 ,...,}

1 1

*

* 1

*

_{  }



n

j

y

x

a

x

a

m

i

n

j

j i ij m

i

i

ij

^{, 1 , 2 ,...,}

1 1

*

* 1

*

_{  }



(3)

(4)





i

n

j

j i ij

^{x y}

a

1 1

*



 ＆十分性＇

(3),(4) 満 ^．

任意 _{対し，(3) 両辺 xi} け 辺々足し合わ

こ ₍₁₎ ．同様 (2) 成立．

 ＆必要性＇

(1) 満 ^， 第i単位ベクト

，

こ _{(3) ．同様 (4) 成立}

Y

X 

 , *

* y

x

 X

x



 



_

 

i

i m

i

i n

j

j

ij ^{y x x}

a

1

1 1

*

 X

*

x ^x











i

n

j

j i ij n

j

j ij m

i

n

j

j i

ij

^{x y a y a x y}

a

1 1

*

* 1

*

1 1

*

 行プ ー ー 支払い最小化問題(P) 最適解 列プ ー ー 利得最大化問題(D) 最適解

(x*, z*), (y*,w*) あ , (x*,y*) A ^{定義さ ーム 均衡解}

0 x 

















,..., 2 , 1 ,

0

1

t. s.

min

1 1

n j

z x

a x z

m

i ^{ij i}

m

i

i

0 y 

















,..., 2 , 1 ,

0

1

t. s.

max

1 1

m i

w y

a y w

n

j ^{ij j}

n

j

j

(P) ^(D)

 双対定理 , (x*, z*), (y*,w*) い , z*=w* ^成立

 ま ，

成立.

 こ ，

 _z*=w* ，

n j

z x

m a

i 1 ^{ij i * *, 1,2,...,}



m i

w y

n a

j 1 ^{ij j * *, 1,2,...,}



*

*

*

*

1 1^{a x} *^y 1^{z y z}

n j

n

j ^j

j m

i ^{ij i  }







*

*

*

*

1 1^{a x} *^y 1^{w x w}

n j

n

j ^j

j m

i ^{ij i  }







*

*

*

1 1^{a x} *^{y w z}

n

j ^j

m

i ^{ij i  }

 

 ，

成立.

 補題 ，(x*,y*) 均衡解 ^■

n j

y x a x

a ⁿ

j ^j

m

i ^{ij i}

m

i 1 ^{ij i * }

 



m i

y x a y

a ⁿ

j ^j

m

i ^{ij i}

n

j 1 ^{ij j * }

 



 _A 定義さ ーム 均衡解 (x*,y*) ^， x* ^{行プ ー ー} 支払い最小化問題(P) 最適解 y* ^{列プ ー ー} 利得最大化問題(D) 最適解

え

0 x 

















,..., 2 , 1 ,

0

1

t. s.

min

1 1

n j

z x

a x z

m

i ^{ij i}

m

i

i

0 y 

















,..., 2 , 1 ,

0

1

t. s.

max

1 1

m i

w y

a y w

n

j ^{ij j}

n

j

j

(P) ^(D)

 均衡解 (x*,y*) ^{目的関数値} z*, w* ^．

補題 ，

成立.

 _{(P), (D)} 定義 ，

(P), (D) ^{目的関数 最適値 双対定理 一致}

，こ _β く ，

，(x*, z*), (y*,w*) (P), (D) 最適解 あ

こ わ ． ■

m i

y x a y

a ⁿ

j ^j

m

i ^{ij i}

n

j 1 ^{ij j * }

 



n j

y x a x

a ⁿ

j ^j

m

i ^{ij i}

m

i 1 ^{ij i *}

 





 

 , *

* w

z





  z*  w* 

 プ ー ー 協力し 利益 最大化

 ＆ま 費用 最小化 ＇

 こ 際得 利益 う分配 満 く ．

 生産計画問題

◦ ^c_j : 第 j 製品 1単位生産し ^利益

◦ ^a_ij : 第 j 製品 1単位生産 必要 原材料 i

◦ ^b_i ^{: 原材料 i 利用可能}

◦ ^{仮定： こ 線形計画問題 最適解 ＆最適値 z*＇}

 プ ー ー： 1,2,…,k

◦ ^{プ ー ー p 原材料 i b}_i^{(p) 単位＆≧0＇所}

◦ ^成立

◦ ^{全プ ー ー} 生産 協力し 場合，最大利益 z^{* 達成}

0

x

b

Ax

cx







subject to

max

z



 ^k

p

p i

i ^b

b

1 ) (

 問題： プ ー ー 協力し 得 利益

う配分 ？

◦ ^{プ ー ー p z}_p ^{配分＆ わ 成立＇}

◦ ^z_p ^{う 値 あ ？}

 一部 プ ー ー 提携し

多く 利益 得 _，S 配分 納得し い



 ^k

p

zi

z

1

*

}

,...,

2

,

1

{ k

S 



＆S 属 ^{プ ー ー 利用} 原材料 i ^{総 ＇}

 _S 属 プ ー ー け 独立し

生産し 場合 得 最大利益 z(S): 以 LP ^最適値

 し _{ば，S 全体 協力} 独自

生産し ほう い

0

x

b

Ax

cx





)

(

subject to

max

S

m

i

b

S

b

S p

p i

i

^{( ) , 1 , 2 ,..,}

)

(

_

 _



)

) (

( z S

z

S p

p

i ^



 _{プ ー ー p} 配分 _zp

1. 2.

 ア ： こ 条件 満 配分 集合 こ

◦ ^{問題＆／＇ ア 存在性}

◦ ^{問題＆０＇ ア 計算可能性}

◦ ^{注意 点： 条件 2. 本質的 2k 個 制約}

含 い ！＆一般 可能＇



 ^k

p

zi

z

1

*

) ( :

} ,..., 2 , 1

{ k z^{( )} z S

S

S p

p

i ^





_



 ＆幸い こ ＇生産計画 ーム ア 非空， 多項式時間計算可能

 双対定理 利用

 _(D) 最適解 _y* ，以 配分

ア 属

0

y

c

Ay

by





subject to

min

t





p

^{b y}

z

(D)

証明：＆ ＇

 双対定理

 定義 あ ，

k

p

y

b

z

m

i

i p i

p

^{, 1 , 2 ,...,}

1

* )

(

_

 _



く ，(z

,z

,…,z

) ^{ア 属 配分 あ}



 ^k

p

zi

z

1

*



 ^m

i

i i ^y

b z

1

* *



 ^k

p

p i

i ^b

b

1 ) (

*

1

* 1

) (

* 1 1

) ( 1

z y

b y

b z

m

i

i k

p

p i i

k

p

m

i

p i k

p

p ^

_

_



証明：＆ ＇

 以 双対 二 線形計画問題 考え

 _(P) 現実的 生産計画問題 考え 界 実行可能解 _＆x=0＇

 双対定理 ，(P(S)),(D(S)) 最適解 z(S) ,w

(S)

(S) =

(S)

) ( :

} ,..., 2 , 1

{ k z^{( )} z S

S

S p

p

i ^





_



0

x

b

Ax

cx





)

(

subject to

max

S

0

y

c

Ay

y

b





subject to

)

(

min

t

t

S

(P(S)) (D(S))

 _(D(S)) 制約条件 _S 依存 _{，(D) 等しい} (D) 最適解 y* , 各(D(S)) 実行可能解

 ，

 こ ，

) ( )

( )

(

1

* w S z S

y S b

m

i

i

i ^{ }



















S p

p S

p

m

i

i p i m

i

i S

p

p i m

i

i

i ^{S y b y b y z}

b S

z

1

* ) ( 1

* ) ( 1

) *

( )

(