数理計画 資料 最近の更新履歴 小野 廣隆 (Hirotaka Ono)

担当： 経済工学部門 小 廣隆 [email protected]

1

 二人ゼ 和 _MinMax定理

◦ ^{双対定理 証明}

 協力 ア

◦ ^生産計画

 理論

◦ 1940年代 John von Neumann, Oskar Morgenstern 創始

◦ ^{経済学 基礎理論}

 _{2人ゼ 和}

◦ 1920年代 Borel ^定式化

◦ 1928年 von Neumann Minimax 定理 証明 不動点定理 利用

◦ Dantzig ^{線形計画 双対定理 証明}

3

 _{2人ゼ 和}

◦ ^{行プ ，列プ}

◦ ^{行プ 選 戦略：}_1,2,…,m

◦ ^{列プ 選 戦略：}_1,2,…,n

◦ ^各プ 戦略 選び，同時 公表

 支払い行列 payoff matrix

◦ ^行プ 戦略 i ^，列プ 戦略 j ^選

，行プ 列プ _aij 支払う ゼ 和



















mn m

m

n n

a a

a

a a

a

a a

a













2 1

2 22

21

1 12

11

A

 チョ ト パイナップ

◦ ^{け 何歩進 決}

◦ ^{勝 場合 相手} チョキ ：3歩進

◦ ^{チョキ 勝 場合 相手 パ} ：5歩進

◦ ^{パ 勝 場合 相手} ：7歩進

◦ あいこ：0歩進

◦ (戦略1, 2, 3)=( , チョキ, パ )

5

























0 5

7

5 0

3

7 3

0 A

 各プ 確率的 戦略 選択 混合戦略

 行プ _{戦略 i} 選択 _{確率： xi}

 列プ _{戦略 j} 選択 _{確率： yj}

 行プ 列プ 支払う

期待値 行プ 期待損失

 列プ 期待損失：





 



 ⁿ

j

j m

i

i ^y

x

1 1

1

, 0 1

: ,

0

:   

i x_i j y_j



  m

i

j i n

j

ij^{x y}

a

1 1



  m 

i

j i n

j

ij ^{x y}

a

1 1

) (

 行プ 期待損失 最小化 い

 ＝ 行プ ，列プ 最 うまく

振 舞 場合 期待損失 最小化 い

 わ

7



  m

i

j i n

j

ij^{x y}

a

1 1



 





m

1 1

max

min

i

n

j

j i ij Y

y X

x

^{a x y}

 ^{ (}

₁

^,

₂

^{,..., ) |  1 ,  0} 

 x x x

_m

_ x

_i

x

_i

X x

 ^{ (}

₁

^,

₂

^{,..., ) |  1 ,  0} 

 y y y

_n

_ y

_i

y

_j

Y y

証明：





8





  



^

m

1 m

1 1

max

max

i

i ij j

i

n

j

j i ij

Y

^{a x y a x}

y























 



 



 



 

m

1

m

1 1

m

1 1

m

1 1

max

max

i

i ij j

i

i ij j

n

j

j i

i ij n

j

j i

n

j

j i ij

x

a

x

a

y

x

a

y

y

x

a

max

m

1

r unit vecto th

- : m

1 1

m

1 1









 

 







i

i ij

j i y

n

j

j i ij i

n

j

j i ij Y

x

a

y

x

a

y

x

y

a





  



^

n

1 m

1 1

min

min

j

j ij i

i

n

j

j i ij

X

^{a x y a y}

x

再掲

 行プ 目的

 等価 線形計画問 Ｐ

9

0 x



 







1

t.

s.

max

min

1

1 m

i

i

m

i ^{ij i}

j

x

x

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

 列プ 目的

 等価 線形計画問 Ｄ

10

0

y 

 







1

t.

s.

min

max

1

1 n

j

j

n

j ^{ij i}

i

y

y

a

0 y 

















,..., 2

, 1 ,

0

1

t. s.

max

1 1

m i

w y

a y w

n

j ^{ij i}

n

j

j

 _(P)：

 ま 不等式標準形 変形

11

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



 m



i

x

i 1

1 _{ }













^m

i

i m

i

i

^x

x

1 1

1

)

(

,

1

z ( z  ) z

₁

 z

_2,

z

₁

 0 , z

₂

 0

 _(P’)：

 _(D’)：

12

 

0 x

0 x

A 1

1

1 1

x 0































































































2 1 2

1 2

1

, 1 1 0

0

0 0

s.t.

1 1

min

z z z

z z

z

 

0 y

0 y

A 1

1

1 1

y 0































































































2 1 2

1 2

1

, 1 1 0

0

0 0

s.t.

1 1

max

w w w

w w

w

t

双対

 _(D)：

13

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

0

w

,

0

)

( w  w

₁

 w

_2,

w

₁

 w

₂



 m×n 行列 A 定義さ 2人ゼ 和 対 ，以 成立 ：





  ^{ }  



 ^

m

i

n

j

j i ij X

Y m

i

n

j

j i ij Y

X ^{a x y a x y}

1 1 1 1

min max

max

min _{x y y x}

証明：

 _{(P) (D)} 双対関係 双対定理適用可能

 _{(P) (D)} 共 実行可能

例え _{，適当 j け xj=1} ， _{以外 0}

 双対定理 ，共 最適値 一致

15

 最大化 2x + 2y + 3 z

 条件 5x + 3 z ≦ 2 z 2

4y + z ≧ x, y, z 0

オ ン ト ト 収益

オ ン 5 2

ト ト 4 2

ッ 3 2 1 3

供給 8 2 9

収益 最大化

各作物 使用 供給 以

各 生産

非負

 複数 プ イ 提携 (coalition) 行動 可能

 例： 生産計画 ： 生産計画問 右

協力 版

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

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

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

◦ ^{生産計画問 設定 ，プ 原料 ，} 協力 生産

17

0

x

b

Ax

cx







subject to

max

z

 生産計画問

◦ 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 配分

納得 い

19





 ^k

p

zp

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 ,..,}

)

(

_

 _



) (S z z

S p

p ^





 プ

_p

配分

_z

_p

1. 2.

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

◦ ^{問 ア 存在性}

◦ ^{問 ア 計算可能性}

◦ ^{注意 点：} 条件 2. 本質的 2^{k 個 制約} 含 い ！ 一般 不可能

21





 ^k

p

zp

z

1

*

) ( :

} ,..., 2 , 1

{ k z z S

S

S p

p ^





_



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

 双対定理 利用

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

ア 属

0

y

c

Ay

by

 ^

subject to

min

t t

t







^m

i

i p i

p

^{b y}

z

1

* ) (

(D)

証明：

 双対定理

 定義 あ ，

23

k

p

y

b

z

m

i

i p i

p

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

1

* )

(

_

 _



く ，(z

₁

,z

₂

_,…,z

_k

) ^{ア 属 配分 あ}





 ^k

p

zp

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)

z

(S) =

w

(S)

) ( :

} ,..., 2

, 1

{ k z z S

S

S p

p ^





_



0

x

b

Ax

cx





)

(

subject to

max

S

0

y

c

Ay

y

b

 ^

subject to

)

(

min

t t

t

S

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

 _(D(

_S

₎₎ 制約条件

_S

依存 _{，(D) 等 い} (D) 最適解 y* , 各(D(

S

)) ^{実行可能解}

 ，

 こ ，

25

) ( )

( )

(

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

) *

( )

(