저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할수없습니다. 변경금지. 귀하는이저작물을개작, 변형또는가공할수없습니다. 귀하는, 이저작물의재이용이나배포의경우, 이저작물에적용된이용허락조건을명확하게나타내어야합니다. 저작권자로부터별도의허가를받으면이러한조건들은적용되지않습니다. 저작권법에따른이용자의권리는위의내용에의하여영향을받지않습니다. 이것은이용허락규약 (Legal Code) 을이해하기쉽게요약한것입니다. Disclaimer
- Method development on energy-flow networks by using critical pathes 2014 8
- Method development on energy-flow networks by using critical pathes. 2014 6. 2014 6 ( ) ( ) ( )
-,,. - NP-Hard... : -,,, NP-Hardness : 2010 21095
i 1 2 1.1..................... 2 1.2............................. 4 1.3............................. 6 2 7 2.1............................. 7 2.2........................ 8 2.2.1......................... 8 2.2.2........................ 9 2.2.3 /................. 9 2.2.4......................... 10 2.3........................ 11 2.4............................ 13 2.5....................... 13 3 18 3.1.......................... 18 3.2 (Critical Path).................. 21 4 27 4.1 כ............................. 27 4.2 (1).......................... 27 ii
4.3 (2)..................... 30 4.4 (3)........... 30 4.5 (4).................. 32 4.6 כ............................. 33 5 34 5.1............................. 34 5.2 כ............................. 36 5.3............................. 36 6 38 39 41 iii
2.1 -.............. 11 2.2 -................. 12 5.1....................... 36 5.2.......................... 36 5.3 כ.............. 36 iv
2.1 -.................... 12 2.2-1....... 15 2.3-2....... 16 3.1 -...................... 19 3.2 -............. 19 3.3 cover(i, j)............................. 22 3.4.......................... 23 4.1....................... 30 4.2..................... 33 1
1. 1.1,, כ. כ כ, (storage or buffer).,, כ., k k = 1 special case (transportation problem).. -. - (flow balance) (energy balance) כ. כ, כ. - - כ. 2
,.,. successive linear programming(slp)[5], piecewise linear programming(plp)[7], generalized reduced gradient(grg) method[9], simulated annealing(sa)[3]. -. - - / כ, / /.,,.. -,, כ,. 3
1.2 -..,.,.. - :.,, כ. - : /. - :.,,.. - כ כ (minimalכ guaranteed pressure)., כ, (compressor),,., - (nonlinear flow-pressure relations), /., -. on/off 4
mixed integer model. [4], [1]. O Neill et al.[5] successive linear programming(slp). Wolf and Smeers[8] piecewise linear programming(plp)[7], Martin et al.[4] piecewise linear constraints. Mahlke et al.[3] branch-and-cut, simulated annealing(sa). -. -., כ,,,.,, /. (water head, m). Hazen-Williams, 1.85. Yu et al.[9] generalized reduced gradient(grg) method., (water distribution network, WDN) (hydraulic).. Brion and Mays[1] KYPIPE 5
. 1.3 6. 2 -,,. 3 -. 4, 5. 6. 6
2. -,. NP-hard. 2.1 - / כ. D = (N, A). N N t N n, A A p A d A n. - D = (N, A), - N = N n N t, - A = A n A p A d. כ, (multiperiod) t(t = 1,, T ). fij t, πi t. - f t ij, - π t i. 7
, (1), (2), (3) /. -.. 2.2 2.2.1 כ. כ Si t Dt i. כ. כ. b t i, b i. Bi 1,.. j (j,i) A j (j,i) A f t ji + St i = f t ji + St i = j (i,j) A j (i,j) A f t ij + Dt i i N n, t, f t ij + Dt i + bt+1 i b t i i N t, t, b 1 i = B1 i i N t, b 1 i = bt i i N t, 0 b t i b i i N t, t. - כ S t i, Dt i, - b t i, - B 1 i, - b i. 8
2.2.2 כ. /.. L ij (fij t ), (nondecreasing convex function).., L ij (f t ij ) = µ ij(f t ij )2, L ij (f t ij ) = µ ij(f t ij )1.85, L ij (f t ij ) = µ ijf t ij.. on/off. כ, (post-processing) on/off.,.. π t i πt j = L ij(f t ij ) π t i πt j π t i πt j (i, j) A n, t, (i, j) A p, t, (i, j) A d, t. - L ij (f ij ), - : µ ij (f t ij )2 ( ), µ ij (f t ij )1.85 ( ), µ ij f t ij ( ). µ ij :. 2.2.3 / /. 9
/.. כ. כ. /.. π i π t i π i i N, t, 0 f t ij f ij (i, j) A, t. 2.2.4 - כ., כ. g(f, π). -. min g(f, π) = Cij t f ij t (πt j πt i ) (water), t (i,j) A p min g(f, π) = Cij t f ij t (( πt j ) κ 1 π t i t 2κ 1) (κ 1.4) (gas). (i,j) A p * κ 1.1 1.6 כ.[2][6] 10
2.3 -. 2.1: - N -, N = N n N t. N t N n.. A -, A = A n A p A d. A p A d A n f t ij π t i b t i L ij (f t ij ) S t i D t i f ij π i π i B 1 i b i g(f, π)... t, (i, j). t, i. t, i. (i, j). t, i. t, i כ. (i, j). i. i. i. i. -. 11
-. 2.2: - כ -. 2.1: - 12
2.4 -. 2.4.1 min g(f, π) s.t fji t + St i = j (j,i) A j (j,i) A f t ji + St i = j (i,j) A j (i,j) A f t ij + Dt i i N n, t, f t ij + Dt i + bt+1 i b t i i N t, t, b 1 i = B1 i i N t, b 1 i = bt i i N t, π t i πt j = L ij(f t ij ) π t i πt j π t i πt j π i π t i π i (i, j) A n, t, (i, j) A p, t, (i, j) A d, t, i N, t, 0 b t i b i i N t, t, 0 f t ij f ij (i, j) A, t. 2.5 - כ, כ. NP-hard כ. - (optimization problem) (decision problem). -. 2.5.1 - ( ) : - ( ), K. : - כ K? 13
2.5.1 NP-hard כ NP-hard כ. Proposition 2.5.2 - ( ) NP-hard. : - ( ) NP-hard.. 2.5.3 : n N = {a 1,, a n }. :,? -.. - : n + 1, 2n, - : 2n, n. - - - - n. 1,, n. 1,. n n. 2.2. כ. 2. a i D., i D + a i, 0. כ 14
2.2: - 1, i 0, D כ. כ a i /2 כ.. - : L ij (fij t ) = π D (f ij t )2, - : L ij (fij t ) = (f ij t )2. π (> 0) 0.. /,.. g(f, π) = fij t (πt j πt i ) 2.2 t a A p 2.3., כ D a i כ כ. 15
2.3: - 2 כ K. K = i N(Dπ + a i (π + a 2 i )) - ( ) 2.3 כ K,., - ( ) כ. N A, B., a i A, i a i, D. a i B,. A B a i /2 כ, כ. a i π + a 2 i, D π.. 16
, כ K. כ K - ( ). - ( ) כ., כ. i (x, a i x). i π + x 2, π + (a i x) 2. כ π. כ כ כ,, (D, 0) (0, D) D. (D, 0) (0, D), (0, a i ), (a i, 0) כ כ., כ כ כ כ. K., כ K, כ כ. 17
3. -.. 3.1 -. -..:., -. 6. (1) = t Si t(πt i 0). i N (2) ( ) = t (3) ( ) = t (4) ( ) = t (5) = t (6) = t i N t (b t+1 fij t (πt j πt i ). (i,j) A p fij t (πt i πt j ). (i,j) A d fij t (πt i πt j ). (i,j) A n i b t i )πt i. Di t(πt i 0). i N 18
Proposition 3.1.1 : + = (, ) + +. : - 3.1. 3.1: - / כ / כ.. s 0, כ. 3.2: - 19
- - 3.2 (, ) כ. (b t+1 i b t i )πt i = (b T i b1 i )πt i. t i N t i N t b T i b 1 i = 0 0. (, ) כ. s s.. s. כ.,. ( + = (, ) + + ) כ. 3.1.1. 0., כ.,,, כ כ.. 20
fij(π t i t πj) t = fijl t ij (fij). t t (i,j) A n t (i,j) A n Proposition 3.1.2. : F (fij t ) = f ij t L ij(fij t ) כ. F (fij t ). F (f t ij) = 2L ij(f t ij) + f t ijl ij(f t ij) L ij L ij 0, L ij 0, f t ij. F (fij t ) 0 F (f ij t ),.,,.. Kij t f ij t L ij(fij t ) t (i,j) A d. 3.2 (Critical Path) -. -,.., - 1-2 - 3 - כ. - 1-2 - 3 -. 21
.., N. 3.3: cover(i, j). (i, j) cover(i, j). 3.2.1 (i, j) j k, k cover(i, j). cover(i, j).. (i, j) cover(i, j). cover.... 5 π5 t π 5 2 π2 t 22
3.4: π 5 +L 3,5 (f3,5 t )+L 2,3(f2,3 t )., k cover(i, j), j LBk t. LBk t. LB t k (f t ) := π k + (a,b) pathj k L ab (f t ab ), (k cover(i, j)). (i, j) j cover(i, j) LB t k (f t ). π j max k cover(i,j) {LB t k (f t )}, t. כ.. (i, j) LB כ כ. LB כ כ כ. כ, כ 23
. כ LB כ כ. (Critical Path).. g (f, π). g (f, π) = g (f, π) = t t Cij t f ij t (max k cover(i,j){lbk t (f t )} π i ) (water) (i,j) A p Cij t f ij t (( max k cover(i,j){lbt k (f t )} ) κ 1 πi t 2κ 1) (gas) (i,j) A p g (f, π). cover(i, j) k ij g LB (f).,. g (f, π) = t t t t t Cij t f ij t (max k cover(i,j){lbk t (f t )} π i ) (i,j) A p Cij t f ij t ({LBt k ij (f t )} π i ) (i,j) A p Cij t f ij t ( L ab (fab t ) + π k ij π i ) (i,j) A p (a,b) pathj k ij Cij t ( fab t L ab(fab t ) + π k ij f ij π i f ij ) (i,j) A p (a,b) pathj k ij Cij t ( fab t L ab(fab t ) + π k ij f ij π i f ij ) (i,j) A p (a,b) pathj k ij = g LB (f) Proposition 3.2.2, g LB (f). : g LB (f) π kij f ij π i f ij., fab t L ab(fab t ) (a,b) pathj k ij Proposition 3.1.2, g LB (f). 24
,. g (f, π) = t t t t t Cij t f ij t (i,j) A p Cij t f ij t (i,j) A p (i,j) A p C t ij f t ij (( (i,j) A p C t ij (( = g LB (f) (i,j) A p C t ij (( (( max k cover(i,j){lbt k (f t )} πi t LBt k (f t ) (( ij πi t ) κ 1 2κ 1) (a,b) pathj k ij L ab (f t ab )+π k ij π t i ) κ 1 2κ 1) ) κ 1 2κ 1) (a,b) pathj k ij (f t ab ) 2κ κ 1 L ab (f t ab )+π k ij (f t ab ) 2κ κ 1 π t i (a,b) pathj k ij (f t ab ) 2κ κ 1 L ab (f t ab )+π k ij (f t ab ) 2κ κ 1 Proposition 3.2.3, g LB (f). π t i ) κ 1 2κ f t ij ) ) κ 1 2κ f t ij ) : µ ij (f t ij )2, g LB (f) = t µ ab (fab t ) 2κ Cij(( t (a,b) pathj k ij (i,j) A p πi t κ 1 +2 + π kij (f t ab ) 2κ κ 1 ) κ 1 2κ f t ij ). 1.1 κ 1.6 2κ κ 1 1. f ij t ) F (x). F (x). F (x) = ( n x i α i ) β (α 1 α n 0, α n β 1). i=1 F (x). F (x) = f 3 (f 2 (f 1 (x))). α 1 αn f 1 (x) = (x1,, x αn αn n ), f 2 (x) = ( n i=1 x i αn ) 1 αn, f 3 (x) = x αnβ. f 2 (x) Minkowski inequality, f 3 (x) α n β 1 25
. f 2 (f 1 (x)). f 2 (f 1 (λx + (1 λ)y)) = f 2 ((λx 1 + (1 λ)y 1 ) α 1 αn,, (λx n + (1 λ)y n ) α n αn ) f 2 (λ(x 1 ) α 1 αn + (1 λ)(y 1 ) α 1 αn,, λ(x n ) α n αn α 1 αn αn αn αn λf 2 (x1,, xn ) + (1 λ)f 2 (y1,, y = λf 2 (x) + (1 λ)f 2 (y). α 1 + (1 λ)(y n ) α n αn ) ( α i α n 1) αn αn n ) ( f 2 is convex.) f 2 (f 1 (x)), f 2 (x), f 3 (x), F (x). g LB (f).,. 4. 26
4. -.. 4.1 3.,. כ כ.,, כ כ כ. 4.,.,. 4.2 (1) 3.1. - כ כ כ.,,... 27
cover(i, j) Cij t. K t ab = Ct ij (a, b cover(i, j)). g loss (f) = t (i,j) A d K t ijf t ijl ij (f t ij) g loss (f). π t i πt j = L ij (fij t ) πt i πt j L ij(fij t ),. 4.2.1 min g loss (f) + ɛ πi t t i N s.t fji t + St i = j (j,i) A j (j,i) A f t ji + St i = j (i,j) A j (i,j) A f t ij + Dt i i N n, t, f t ij + Dt i + bt+1 i b t i i N t, t, b 1 i = B1 i i N t, b 1 i = bt i i N t, π t i πt j L ij(f t ij ) π t i πt j π t i πt j π i π t i (i, j) A n, t, (i, j) A p, t, (i, j) A d, t, i N, t, 0 b t i b i i N t, t, 0 f t ij f ij (i, j) A, t. 4.2.1,.. g loss (f) כ, ɛ πi t t i N כ כ. 28
,. Proposition 4.2.2 4.2.1 (π t i πj t = L ij(fij t )). :, (i, j). i, j (i, j) δ. i כ (πi t) δ πi t. π t i = (πt i ) δ. i (k, i) k, i (k, i) δ. כ k כ, כ δ.. 29
4.3 (2) 4.2 (f, π ). LBk t (f t ). כ. π π i, כ. 4.1: 4.4 (3) 3.2. cover(i, j) j k ij, g LB (f). g LB (f) = t g LB (f) = t Cij t ( fab t L ab(fab t ) + π k ij f ij π i f ij ) (i,j) A p (a,b) pathj k ij (i,j) A p C t ij (( (a,b) pathj k ij (f t ab ) 2κ κ 1 L ab (f t ab )+π k ij (f t ab ) 2κ κ 1 π t i (water) ) κ 1 2κ f t ij ) (gas) 30
.. 4.4.1 min g LB (f) + ɛ πi t t i N s.t fji t + St i = j (j,i) A j (j,i) A f t ji + St i = j (i,j) A j (i,j) A f t ij + Dt i i N n, t, f t ij + Dt i + bt+1 i b t i i N t, t, b 1 i = B1 i i N t, b 1 i = bt i i N t, π t i πt j L ij(f t ij ) π t i πt j π t i πt j π i π t i (i, j) A n, t, (i, j) A p, t, (i, j) A d, t, i N, t, 0 b t i b i i N t, t, 0 f t ij f ij (i, j) A, t. 4.4.1 4.2.1. g LB (f) כ... 31
4.5 (4). 4.5.1. 4.5.1 min g LB (f) + ɛ πi t + wi tλt i t i N t i N s.t fji t + St i = fij t + Dt i j (j,i) A j (j,i) A f t ji + St i = j (i,j) A j (i,j) A i N n, t, f t ij + Dt i + bt+1 i b t i i N t, t, b 1 i = B1 i i N t, b 1 i = bt i i N t, π t i πt j L ij(f t ij ) π t i πt j π t i πt j π i π t i (i, j) A n, t, (i, j) A p, t, (i, j) A d, t, i N, t, 0 b t i b i i N t, t, 0 f t ij f ij (i, j) A, t, λ t i πt i π i λ t i 0 i N, t, i N, t. λ,. 32
4.6 כ. כ כ. (1) (2) (3) (4) 4.2: 33
5.. 5.1. כ.. on/off. כ כ. -.,,. -. 24 15 96.. 34
5.1.1 min s.t t Cij t f ij t (πt j πt i ) (i,j) A p fji t + St i = fij t + Dt i j (j,i) A j (j,i) A f t ji + St i = j (i,j) A j (i,j) A i N n, t, f t ij + Dt i + bt+1 i b t i i N t, t, b 1 i = B1 i i N t, b 1 i = bt i i N t, π i = π i + bt i A i i N t, π t i πt j = L ij(f t ij ) π t i πt j π t i πt j π i π t i π i (i, j) A n, t, (i, j) A p, t, (i, j) A d, t, i N, t, 0 b t i b i i N t, t, 0 f t ij f ij (i, j) A, t. -.. π i = π i + bt i A i,. (A i i ) 35
5.2.. 5.1: 1 41 40 2 6 12 2 100 98 5 14 27 3 146 145 7 21 34 1 0 23 24. SLP. 5.3. 5.2: SLP 1 6.5 10.8-5.3 (1.7 ) 2 20.5 41.7-21.2 (2.0 ) 3 29.2 81.5-52.3 (2.8 ) 5.3: כ SLP 1 7.8% 7.6% +0.2% 2 6.8% 6.0% +0.8% 3 7.2% 5.9% +1.3% 36
כ 7%. SLP. SLP 2-3,. 37
6., -. -,. כ 7%, SLP. SLP 2-3, כ.,.. כ. כ. כ. 38
[1] L. M. Brion and L. W. Mays. Methodology for optimal operation of pumping stations in water distribution systems. Engineering, 117(11):1551 1569, 1991. Journal of Hydraulic [2] John A. Dean. Lange s Handbook of Chemistry. McGraw-Hill, 10th edition, 1967. [3] D. Mahlke, A. Martin, and S. Moritz. A mixed integer approach for timedependent gas network optimization. Optimization Methods & Software, 24(4):625 644, 2010. [4] A. Martin, M. Moller, and S. Moritz. Mixed integer models for the stationary case of gas network optimization. Math Programming, 105:563 582, 2006. [5] R. P. O Neill, M. Williard, B. Wilkins, and R. Pike. A mathematical programming model for allocation of natural gas. Operations Research, 27(5):857 873, 1979. [6] F. M. White. Fluid Mechanics. McGraw-Hill, 7th edition, 2009. [7] D. De Wolf and Y. Smeers. The simplex algorithm extended to piecewiselinearly constrained problems. CORE DP No.9119, Universite Catholique de Louvain, Belgium. [8] D. De Wolf and Y. Smeers. The gas transmission problem solved by an extension of the simplex algorithm. Management Science, 46(11):1454 1465, 2000. 39
[9] G. Yu, R. S. Powell, and M. J. H. Sterling. Optimized pump scheduling in water distribution systems. Journal of Optimization Theory and Applications, 83(3):463 488, 1994. 40
ABSTRACT Jong-Eun Kim Department of Industrial Engineering The Graduate School Seoul National University Energy-Flow network problem is the problem that minimizes total energy cost with flow-balance, energy balance and upper and lower bound of energy and flow constraints. In this paper, we define the E-F network problem which includes various problems in field such as water distribution problem and gas pipeline problem. The problem is NP-hard. We present the Critical Path algorithm which is faster than the most common algorithm and print out the feasible solution and lowerbound of objective. The results show that the proposed method achieves lowerbound-close solution. Keywords : Energy-Flow Network, Water Distribution Network, Gas Pipeline Network, NP-Hardness Student number : 2010-21095