1 n
1 1 2 2 3 3 3.1............................ 3 3.2............................. 6 3.2.1.............. 6 3.2.2................. 7 3.2.3........................... 10 4 11 4.1.......................... 11 4.2.............................. 12 4.2.1 n = 2........................... 13 4.2.2 n = 3........................... 15 4.2.3..................... 19 5 20
1 [1] (Supply Chain Management: SCM) SCM SCM ( ) [2] (Generalized Nash Equilibrium Problem: GNEP) GNEP [3] min x ν θ ν (x ν, x ν ) s.t. x ν X ν (x ν ) } (ν = 1,..., N) (1) N x R n x ν R n ν (ν = 1,..., N) ( x = (x 1,..., x N ) T n = ) N ν=1 n ν ν (ν = 1,..., N) x x ν 1
x ν x = (x ν, x ν ) θ ν ν X ν (x ν ) ν x ν GNEP [3] 1 n (n 2) ( ) ( ) 2 3 4 5 2 D(> 0): h(> 0): l i (> 0): u i ( l i ): p i (> 0): c i (> 0): k i (> 0): K i (> 0): r i (l i r i u i ): λ i (0 λ i 1): ( ) ( ) 1 i (i = 1,..., n) i (i = 1,..., n) i (i = 1,..., n) 1 ( p 1 p 2 p n ) i (i = 1,..., n) 1 i (i = 1,..., n) 1 i (i = 1,..., n) 1 i (i = 1,..., n) ( ) i (i = 1,..., n) ( n i=1 λ i = 1) 2
1: 2: 1 0 i (i = 1,..., n) 1 Q i Q i = λ i D/r i 2 3 n r = (r 1,..., r n ) T λ = (λ 1,..., λ n ) T λ r 3.1 i Q i 0 I i I i = r iq 2 i 2D = λ2 i D 2r i 3
C(r, λ) C(r, λ) = n (p i λ i D + hi i ) = i=1 ( ) n p i λ i D + h λ2 i D = D 2r i i=1 ( ) n p i λ i + hλ2 i 2r i i=1 r C(λ) := C(r, λ) λ = (λ 1,..., λ n) T min λ s.t. ( ) n p i λ i + hλ2 i 2r i=1 i n λ i = 1 i=1 λ i 0 (i = 1,..., n) (2) (2) (2) Karush-Kuhn-Tucker (KKT ) λ L 0 (λ, v, w) = 0 (3) 0 w λ 0 (4) n 1 λ i = 0 (5) i=1 L 0 (λ, v, w) = n i=1 (p iλ i + hλ 2 i /2r i ) + v(1 n i=1 λ i) n i=1 w iλ i, w = (w 1,..., w n ) T a b ab = 0 (3), (4) w i = p i + hλ i r i v 0 (i = 1,..., n) λ i r i h (v p i) (i = 1,..., n) 4
(4) λ i ( λ i = max 0, r ) i h (v p i) (i = 1,..., n) f i (v) = max(0, r i (v p i )/h) (5) λ i n i=1 f i(v) = 1 v λ i = max(0, r i (v p i )/h) (i = 1,..., n) p 1 p 2 p n [4] λ = r 1 (v n p 1 ) h r 2 (v n p 2 ) ḥ. r n (v n p n ) h r 1 (v n 1 p 1 ) ḥ. r n 1 (v n 1 p n 1 ) h 0. 1 0. 0 ( v n := ( n k=1 r k) 1 ( n k=1 r kp k + h) > p n ) (v n p n, v n 1 > p n 1 ) (v n p n, v n 1 p n 1,, v 2 p 2 ) (6) 0 λ i > 0 (i = 1,..., n) (6) λ = ( r1 h (v n p 1 ), r 2 h (v n p 2 ),..., r ) T n h (v n p n ) (7) v n = ( n k=1 r k) 1 ( n k=1 r kp k + h) λ i λ i = r i r 1 + r 2 + + r n [ 1 + 1 h ] n r j (p j p i ) j=1 5 (i = 1,..., n) (8)
i = 1,..., n r i l i > 0, λ i > 0 r n r j (p i p j ) h ε (i = 1,..., n) j=1 ε 3.2 3.2.1 i (i = 1,..., n) Φ i (r, λ) (i = 1,..., n) Φ i (r, λ) = (p i c i k i ) λ i D r i K i (i = 1,..., n) (8) Φ i (r, λ) Φ i (r) Φ i (r) = (p [ i c i k i ) r i 1 + 1 r 1 + r 2 + + r n h ] n r j (p j p i ) D r i K i (i = 1,..., n) j=1 1. p i > c i + k i (i = 1,..., n) p i (i = 1,..., n) Φ i (r) (i = 1,..., n) Φ i (r) r i r = (r 1,..., r n) T max r i Φ i (r i, r i ) s.t. r S } (i = 1,..., n) (9) 6
{ S = r } n j=1 r j (p i p j ) h ε, l i r i u i, i = 1,..., n r i r i S i S i r i S i (r i ) r S r i S i (r i ) (i = 1,..., n) (9) min r i Φ i (r i, r i ) s.t. r i S i (r i ) } (i = 1,..., n) (10) 1 GNEP(1) (x ν N θ X ν r i n Φ S i ) S i (10) 3.2.2 GNEP (10) p 1 p 2 p n S n n j=1 r j (p i p j ) h ε (i = 1,..., n) 1 n j=1 r j (p n p j ) h ε S S = { r } n r j (p n p j ) h ε, l i r i u i, i = 1,..., n j=1 g(r) = n j=1 r j(p n p j ) (h ε) (10) min r i Φ i (r i, r i ) s.t. g(r i, r i ) 0 r i u i 0 l i r i 0 (i = 1,..., n) (11) (11) KKT 7
ri L i (r, µ i, α i, β i ) = 0 0 µ i g(r) 0 0 α i u i r i 0 0 β i r i l i 0 (i = 1,..., n) (12) L i (r, µ i, α i, β i ) = Φ i (r) + µ i g(r) + α i (r i u i ) + β i (l i r i ) (i = 1,..., n) L (r, µ, α, β) = ( r1 L 1 (r, µ 1, α 1, β 1 ),..., rn L n (r, µ n, α n, β n )) T µ = (µ 1,..., µ n ) T g(r) = (g(r),..., g(r)) T α = (α 1,..., α n ) T, β = (β 1,..., β n ) T, u = (u 1,..., u n ) T, l = (l 1,..., l n ) T n KKT (12) L (r, µ, α, β) = 0 0 µ g(r) 0 0 α u r 0 0 β r l 0 (13) GNEP KKT r r GNEP(10) r GNEP KKT (13) ( µ, α, β ) i (11) (r, µ, α, β) GNEP KKT (13) r GNEP(10) 1. r GNEP(10) r GNEP KKT (13) ( µ, α, β ) (Variational Inequality:VI) find r S such that (s r) T ( ri Φ i (r)) n i=1 0, s S (14) ( ri Φ i (r)) n i=1 S (14) KKT [5] 8
( ri Φ i (r)) n i=1 + µ ( r i g(r)) n i=1 + (α i) n i=1 (β i) n i=1 = 0 0 µ g(r) 0 0 α i u i r i 0 (i = 1,..., n) 0 β i r i l i 0 (i = 1,..., n) (15) r VI(14) r VI KKT (15) ( µ, α 1,..., α n, β 1,..., β n ) r (r, µ, α 1,..., α n, β 1,..., β n ) VI KKT (15) r VI(14) 2. r VI(14) r VI KKT (15) ( µ, α 1,..., α n, β 1,..., β n ) 2. GNEP KKT (13) VI KKT (15) µ = µ 1 = µ 2 = = µ n 2 GNEP KKT (13) GNEP(10) r ( µ, α, β ) r ( µ, α 1,..., α n, β 1,..., β n ) VI KKT (15) VI(14) VI KKT (15) VI(14) r ( µ, α 1,..., α n, β 1,..., β n ) 2 r ( µ, α, β ) GNEP KKT (13) GNEP(10) [6] [7] 3. VI KKT (15) VI(14) 2 GNEP KKT (13) GNEP(10) 3 VI KKT (15) VI(14) GNEP(10) VI [5] r i (i = 1,..., n) (8) λ i (i = 1,..., n) 9
3.2.3 VI(14) VI(14) ( ri Φ i (r)) n i=1 VI(14) [8] F (r) F (r) r [8] A A + A T [9] 4. VI(14) A := ( ri Φ i (r)) n i=1 A + A T A A = 2 Φ 1 (r) r1 2 2 Φ 2 (r) r 1 r 2. 2 Φ n (r) r 1 r n 2 Φ 1 (r) 2 Φ 1 (r) r 1 r 2 r 1 r n 2 Φ 2 (r) 2 Φ 2 (r) r2 2 r 2 r n..... 2 Φ n (r) 2 Φ n (r) r 2 r n rn 2 a ii := 2 Φ i (r) r 2 i a ij := 2 Φ i (r) r i r j = 2a id R 3 = a id R 3 [ ] 1 + 1 n r k (p k p i ) (R r i ) (i = 1,..., n) h k=1 [ { n }] 1 + 1 r k (p k p i ) r j (p j p i ) (2r i R) h k=1 a i(p j p i )D hr 3 (2r i r j + R 2 r j R) (i = 1,..., n, j = 1,..., n, j i) a i = p i c i k i (i = 1,..., n), R = n k=1 r k A + A T 10
A + A T = 2a 11 a 12 + a 21 a 1n + a n1 a 12 + a 21 2a 22 a 2n + a n2...... a 1n + a n1 a 2n + a n2 2a nn 4 2 A + A T 2a ii > j i a ii > 0 (i = 1,..., n) (16) a ij + a ji (i = 1,..., n) (17) Φ i (r) 1 (16) (17) n < 4, p 1 = p 2 = = p n, c 1 + k 1 = c 2 + k 2 = = c n + k n 4 VI KKT (15) r 4.1 VI KKT (15) r VI KKT (15) 0 µ g(r) 0 0 α i u i r i 0 (i = 1,..., n) 0 β i r i l i 0 (i = 1,..., n) (18) Fischer-Burmeister (FB )ϕ(a, b) = a + b a 2 + b 2 FB ϕ(a, b) = 0 a 0, b 0, ab = 0 11
(18) ϕ(µ, g(r)) = 0 ϕ(α i, u i r i ) = 0 (i = 1,..., n) ϕ(β i, r i l i ) = 0 (i = 1,..., n) x = (r, µ, α 1,..., α n, β 1,..., β n ) T Ψ i (x) = ri Φ i (r) + µ ri g(r) + α i β i (i = 1,..., n) ϕ(µ, g(r)) (i = n + 1) ϕ(α j, u j r j ) (i = n + j + 1, j = 1,..., n) ϕ(β j, r j l j ) (i = 2n + j + 1, j = 1,..., n) VI KKT (15) Ψ(x) = Ψ 1 (x) Ψ 2 (x). Ψ 3n+1 (x) = 0 (19) θ FB (x) = Ψ(x) T Ψ(x) (19) (19) min θ FB (x) (20) 4.2 n = 2, 3 CPU Intel(R)Core(TM)2Quad 2.83GHz 4GB (20) MATLAB lsqnonlin 12
4.2.1 n = 2 n = 2 5 D = 1.0, h = 1.0, ε = 0.001 1.1: c 1 = c 2 = 0.3, k 1 = k 2 = 0.1, K 1 = K 2 = 0.2, l 1 = l 2 = 0.1, u 1 = u 2 = 2.0 p 1 = 1.0 p 2 1.0, 1.25, 1.5, 1.75, 2.0 1.2: p 1 = p 2 = 1.0, K 1 = K 2 = 0.2, l 1 = l 2 = 0.1, u 1 = u 2 = 2.0 c 1 + k 1 = 0.4 c 2 + k 2 0.4, 0.6, 0.8 1.3: p 1 = p 2 = 1.0, c 1 = c 2 = 0.3, k 1 = k 2 = 0.1, l 1 = l 2 = 0.1, u 1 = u 2 = 2.0 K 1 = 0.2 K 2 0.2, 0.4, 0.6 1.4: c 1 = c 2 = 0.3, k 1 = k 2 = 0.1, K 1 = K 2 = 0.2, l 1 = l 2 = 0.6, u 1 = u 2 = 2.0 p 1 = 1.0 p 2 1.0, 1.25, 1.5, 1.75, 2.0 1.5: c 1 = c 2 = 0.3, k 1 = k 2 = 0.1, K 1 = K 2 = 0.2, l 1 = l 2 = 0.1, u 1 = u 2 = 0.9 p 1 = 1.0 p 2 1.0, 1.25, 1.5, 1.75, 2.0 1 5 1: 1.1 (p 1, p 2 ) (1.0, 1.0) (1.0, 1.25) (1.0, 1.5) (1.0, 1.75) (1.0, 2.0) r1 0.7500 0.9020 0.9749 0.9157 0.8041 r2 0.7500 0.8211 0.6829 0.4756 0.3186 λ 1 0.5000 0.6309 0.7889 0.8929 0.9444 λ 2 0.5000 0.3691 0.2111 0.1071 0.0556 13
2: 1.2 (c 1 +k 1,c 2 +k 2 ) (0.4, 0.4) (0.4, 0.6) (0.4, 0.8) r1 0.7500 0.7200 0.5625 r2 0.7500 0.4800 0.1875 λ 1 0.5000 0.6000 0.7500 λ 2 0.5000 0.4000 0.2500 3: 1.3 (K 1,K 2 ) (0.2, 0.2) (0.2, 0.4) (0.2, 0.6) r1 0.7500 0.6667 0.5625 r2 0.7500 0.3333 0.1875 λ 1 0.5000 0.6667 0.7500 λ 2 0.5000 0.3333 0.2500 4: 1.4 (p 1, p 2 ) (1.0, 1.0) (1.0, 1.25) (1.0, 1.5) (1.0, 1.75) (1.0, 2.0) r1 0.7500 0.9020 0.9749 1.0155 1.0000 r2 0.7500 0.8211 0.6829 0.6000 0.6000 λ 1 0.5000 0.6309 0.7889 0.9115 1.0000 λ 2 0.5000 0.3691 0.2111 0.0885 0.0000 5: 1.5 (p 1, p 2 ) (1.0, 1.0) (1.0, 1.25) (1.0, 1.5) (1.0, 1.75) (1.0, 2.0) r1 0.7500 0.9000 0.9000 0.9000 0.8041 r2 0.7500 0.8217 0.7500 0.5051 0.3186 λ 1 0.5000 0.6301 0.7500 0.8832 0.9444 λ 2 0.5000 0.3699 0.2500 0.1168 0.0556 14
1 2 r λ 1.1 2 1 λ 1 2 λ 2 r (p 1, p 2 ) = (1.0, 1.25) (p 1, p 2 ) = (1.0, 1.0) 1 r1, 2 r2 (p 1, p 2 ) = (1.0, 1.5) (p 1, p 2 ) = (1.0, 1.25) 1 r1 2 r2 (p 1, p 2 ) = (1.0, 1.75), (1.0, 2.0) (p 1, p 2 ) = (1.0, 1.5) 1 r1, 2 r2 1.2, 1.3 2 1.1 1 λ 1 2 λ 2 r 1 r1, 2 r2 1.4, 1.5 2 1 λ 1 2 λ 2 r 1.1 1.4 (p 1, p 2 ) = (1.0, 1.75), (1.0, 2.0) 2 r2 1.5 (p 1, p 2 ) = (1.0, 1.25), (1.0, 1.5), (1.0, 1.75) 1 r1 1.1 2 r2 1.1 1.4 1 r1 1 r1 1.1 1.5 2 r2 4.1 p 1 = p 2, c 1 + k 1 = c 2 + k 2 4.2.2 n = 3 n = 3 4 n = 2 D = 1.0, h = 1.0, ε = 0.001 15
2.1: c 1 = c 2 = c 3 = 0.3, k 1 = k 2 = k 3 = 0.1, K 1 = K 2 = K 3 = 0.2, l 1 = l 2 = l 3 = 0.1, u 1 = u 2 = u 3 = 2.0 p 1 = 1.0 (p 2, p 3 ) (1.0, 1.0), (1.1, 1.2), (1.1, 1.3), (1.2, 1.4) 2.2: p 1 = p 2 = p 3 = 1.0, K 1 = K 2 = K 3 = 0.2, l 1 = l 2 = l 3 = 0.1, u 1 = u 2 = u 3 = 2.0 c 1 + k 1 = 0.4 (c 2 + k 2, c 3 + k 3 ) (0.4, 0.4), (0.5, 0.6), (0.6, 0.8) 2.3: p 1 = p 2 = p 3 = 1.0, c 1 = c 2 = c 3 = 0.3, k 1 = k 2 = k 3 = 0.1, l 1 = l 2 = l 3 = 0.1, u 1 = u 2 = u 3 = 2.0 K 1 = 0.2 (K 2, K 3 ) (0.2, 0.2), (0.25, 0.3), (0.3, 0.4) 2.4: c 1 = c 2 = c 3 = 0.3, k 1 = k 2 = k 3 = 0.1, K 1 = K 2 = K 3 = 0.2, l 1 = l 2 = l 3 = 0.6, u 1 = u 2 = u 3 = 0.9 p 1 = 1.0 (p 2, p 3 ) (1.0, 1.0), (1.1, 1.2), (1.1, 1.3), (1.2, 1.4) 6 9 6: 2.1 (p 1, p 2, p 3 ) (1.0, 1.0, 1.0) (1.0, 1.1, 1.2) (1.0, 1.1, 1.3) (1.0, 1.2, 1.4) r1 0.6667 0.8474 0.8757 0.9423 r2 0.6667 0.7768 0.8289 0.8336 r3 0.6667 0.5874 0.3892 0.2371 λ 1 0.3333 0.4580 0.5017 0.5906 λ 2 0.3333 0.3421 0.3920 0.3557 λ 3 0.3333 0.1999 0.1062 0.0537 16
7: 2.2 (c 1 +k 1,c 2 +k 2,c 3 +k 3 ) (0.4, 0.4, 0.4) (0.4, 0.5, 0.6) (0.4, 0.6, 0.8) r1 0.6667 0.7451 0.7357 r2 0.6667 0.5698 0.4571 r3 0.6667 0.3068 0.1000 λ 1 0.3333 0.4595 0.5691 λ 2 0.3333 0.3514 0.3536 λ 3 0.3333 0.1892 0.0774 8: 2.3 (K 1, K 2, K 3 ) (0.2, 0.2, 0.2) (0.2, 0.25, 0.3) (0.2, 0.3, 0.4) r1 0.6667 0.7467 0.7407 r2 0.6667 0.5333 0.4444 r3 0.6667 0.3200 0.1481 λ 1 0.3333 0.4667 0.5556 λ 2 0.3333 0.3333 0.3333 λ 3 0.3333 0.2000 0.1111 9: 2.4 (p 1, p 2, p 3 ) (1.0, 1.0, 1.0) (1.0, 1.1, 1.2) (1.0, 1.1, 1.3) (1.0, 1.2, 1.4) r1 0.6667 0.8475 0.8981 0.9000 r2 0.6667 0.7753 0.8260 0.8749 r3 0.6667 0.6000 0.6000 0.6000 λ 1 0.3333 0.4566 0.4879 0.5362 λ 2 0.3333 0.3402 0.3662 0.3413 λ 3 0.3333 0.2032 0.1460 0.1175 17
n = 2 1 2 3 r λ 2.1 2 3 1 λ 1 2 λ 2 3 λ 3 r 1 r1, 2 r2 3 r3 2.2 2 3 1 λ 1, 2 λ 2 3 λ 3 (c 1 + k 1, c 2 + k 2, c 3 + k 3 )=(0.4, 0.5, 0.6) (c 1 + k 1, c 2 + k 2, c 3 + k 3 )=(0.4, 0.4, 0.4) 1 r1 2 r2, 3 r3 (c 1 + k 1, c 2 + k 2, c 3 + k 3 )=(0.4, 0.6, 0.8) (c 1 + k 1, c 2 + k 2, c 3 + k 3 )=(0.4, 0.5, 0.6) 1 r1, 2 r2, 3 r3 2.3 2 3 1 λ 1 2 λ 2 3 λ 3 r (K 1, K 2, K 3 ) = (0.2, 0.25, 0.3) (K 1, K 2, K 3 ) = (0.2, 0.2, 0.2) 1 r1 2 r2, 3 r3 (K 1, K 2, K 3 )=(0.2, 0.3, 0.4) (K 1, K 2, K 3 ) = (0.2, 0.25, 0.3) 1 r1, 2 r2, 3 r3 2.4 2 3 2.1 1 λ 1 2 λ 2 3 λ 3 r (p 1, p 2, p 3 )=(1.0, 1.1, 1.2), (1.0, 1.1, 1.3), (1.0, 1.2, 1.4) 3 r3 (p 1, p 2, p 3 ) = (1.0, 1.2, 1.4) 1 r1 2.1 1 r1 3 r 3 2.1 1 r1 2 r2 1 r 1 3 r3 2.1 2 r2 4.1 p 1 = p 2 = p 3, c 1 + k 1 = c 2 + k 2 = c 3 + k 3 18
4.2.3 n i=1 (hλ2 i /2r i ) 1.1, 2.1 2 i (i = 1,..., n) Φ i (r) 1 r i Φ i (r) Φ i (r) r i Φ i (r)/ r i > 0 Φ i (r) Φ i (r)/ r i < 0 Φ i (r) r i r i r i r i Φ i (r)/ r i < 0 1 1.2, 1.3 r 1/r 2 = λ 1/λ 2 2.2, 2.3 r i /r j = λ i /λ j (i, j = 1, 2, 3) i (i = 1,..., n) λ i λ i = r i / n k=1 r k 1.4, 1.5, 2.4 19
5 1 n 4.2.3 VI(14) GNEP(10) 20
[1].., 2004. [2] A. Y. Ha, L. Li, and S.-M. Ng. Price and delivery logistics competition in a supply chain. Management Science, Vol. 49, pp. 1139 1153, 2003. [3] F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. A Quarterly Journal of Operations Research, Vol. 5, pp. 173 210, 2007. [4] R. T. Rockafellar. Network Flows and Monotropic Optimization. Wiley, 1984. [5] F. Facchinei and J.-S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, 2006. [6] P. T. Harker. Generalized Nash games and quasi-variational inequalities. European Journal of Operational Research, Vol. 54, pp. 81 94, 1991. [7] F. Facchinei, A. Fischer, and V. Piccialli. On generalized Nash games and variational inequalities. Operations Research Letters, Vol. 35, pp. 159 164, 2007. [8].., 2001. [9] R. W. Cottle, J.-S. Pang, and R. E. Stone. The Linear Complementarity Problem. Academic Press, 1992. 21