電力網の供給率最大化問題

電力網の供給率最大化問題
西関研究室
9527 森下志保
2015/9/30
1
研究背景
2015/9/30
2
分割問題
需要点
8
2
2
15
15
3
3
2
2
8
4
3
需要点
2
1
18
1
5
20
2
供給点
2015/9/30
供給点
必要な需要量
1
1
6
5
1
2
供給可能な供給量
3
分割問題
13
線形時間アルゴリズム[Ito et al.2005]
8
2
15
2
2
3
15
8
供給点
需要点
2015/9/30
3
2
18
3
15
2
1
18
1
5
20
4
2
1
1
5
6
1
2
全ての需要点に電力を供給 18
する分割がある
4
供給率最大化問題
必ず分割があるとは限らない
分割がない
供給量の合計：84需要量の一部を供給する
需要量の合計：120
16
14
8
6
12
10
28
8
10
14
12
18
4
2
42
全ての需要点に一定の割合𝑟だけ供給する
この割合の最大値𝑟 ∗ （最大供給率）を求める
2015/9/30
5
供給率最大化問題
供給率： 𝑟
14
8
10
28
8
（0 ≤ 𝑟 ≤ 1）
10
6
16
12
14
12
18
4
2
42
各需要点𝑣の需要量 dem(𝑣)
各需要点𝑣の新しい需要量 dem′ 𝑣 = 𝑟 ∙ dem(𝑣)
2015/9/30
6
供給率最大化問題
供給量の合計：84
需要量の合計：74
供給率：𝑟=0.6
3.6
9.6
7.2
14
7.2
10.8
4.8
2.4
1.2
42
分割がある
12
8.4
4.8
6.0
28
24
2015/9/30
6.0
38
7
供給率最大化問題
供給量の合計：84
需要量の合計：84
供給率：𝑟=0.7
9.8
5.6
7.0
28
28
5.6
7.0
4.2
11.2
8.4
14
8.4
12.6
2.8
1.4
42
14
最大供給率𝑟 ∗ ：
分割が存在するような供給率の最大値
2015/9/30
42
𝑟 ∗ =0.7
8
供給率最大化問題
• グラフを木に限定
• 全ての需要点にそれらの需要量の
一定の割合𝑟（0 ≤ 𝑟 ≤ 1）だけ供給
• 全ての需要点に電力を供給できる
ような𝑟 の最大値𝑟 ∗ を求める
2015/9/30
9
本研究の結果
• 供給率最大化問題に対して完全多項式
時間近似スキーム（FPTAS）を与えた
• 任意の正実数を𝜀
• 相対誤差
𝑟 ∗ −𝑟
𝑟∗
≤ 𝜀であるような近似解
1
log
𝜀
𝑟を𝑂 log 𝑛 + log𝑚𝑑 +
𝑛 時間
で求める
（𝑛:点数,𝑚𝑑 :需要量の最大値）
2015/9/30
10
課題
• 供給率最大化問題に対する多項式
時間厳密アルゴリズムがあるか,ある
いはこの問題は木に対してすらNP完
全であることの証明.
• 節電率最小化問題に対するFPTAS.
（節電率＝１－供給率）
2015/9/30
11
2015/9/30
12
二分探索法
0
2015/9/30
0.5
0.75
1
13
二分探索法
0
2015/9/30
0.25
0.5
1
14
去年の4年生との違い
去年：二分探索法を用いた近似アルゴリズムを
与えた
今年：誤差を自分で決めて近似アルゴリズムを
与えた
2015/9/30
15
供給率最大化問題（分割のない例）
供給量の合計：84
需要量の合計：96
供給率：𝑟=0.8
11.2
6.4
0.8
28
6.4
0.8
4.8
12.8
9.6
14
9.6
14.4
3.2
1.6
42
供給量の合計＜需要量の合計
2015/9/30
分割がない
16
供給率最大化問題
供給率： 𝑟
14
8
10
28
（0 ≤ 𝑟 ≤ 1）需要量の最大値𝑚𝑑
10
6
16
12
14
12
18
4
2
42
8
1
1
𝑛 = 15, 𝑚𝑑 = 18 𝑟 ≥
=
𝑛 ∙ 𝑚𝑑 15 ∙ 18
∗
2015/9/30
17
補題１
点数を𝑛,需要量の最大値を𝑚𝑑 としたとき,
𝑟=
1
𝑛∙𝑚𝑑
′
とし,各点𝑣の新しい需要量を
dem 𝑣 = 𝑟 ∙ dem(𝑣)とすると, dem′ 𝑣
に対して木𝑇には分割があり,
∗
𝑟 は区間
0
2015/9/30
𝟏
𝒏 ∙ 𝒎𝒅
1
,1
𝑛∙𝑚𝑑
に入っている.
𝑟∗
1
18
𝑟 ∗ −𝑟
𝑟∗
∗
𝑟 −𝑟
≤
𝜀
𝑟∗
∗
𝑟 −𝑟
𝑟∗
1
≤ 𝑟∗
𝑛 ∙ 𝑚𝑑
2015/9/30
≤ 𝜀の証明
絶対誤差 𝑟 ∗ − 𝑟 ≤ 𝜀
𝑟∗ − 𝑟 ≤
1 𝛿
2
𝛿
1
𝑟∗ − 𝑟
2
≤
∗
1
𝑟
𝑛 ∙ 𝑚𝑑
19
𝛿
1
𝑟∗ − 𝑟
𝑛 ∙ 𝑚𝑑
2
≤
=
≤𝜀
∗
𝛿
1
𝑟
2
𝑛 ∙ 𝑚𝑑
になるには
𝑛 ∙ 𝑚𝑑
𝛿 = log
𝜀
に選べばよい
2015/9/30
20
任意の正実数を𝜀とする. 相対誤差が
𝑟 ∗ −𝑟
𝑟∗
≤ 𝜀なる近似解𝑟を,
𝛿 = log 𝑛 + log𝑚𝑑 +
1
log
𝜀
回だけ伊藤ら
の線形時間分割アルゴリズムを繰り返す
二分探索法で求める.
2015/9/30
21
計算時間は
𝑂
1
log 𝑛 + log𝑚𝑑 + log 𝑛
𝜀
であり,
2015/9/30
𝑟 ∗ −𝑟
𝑟∗
≤ 𝜀である.
22
点𝑣が供給点のとき
需要点
11 𝑣
10
25
3
4
供給点
5
20
分割なし
𝐷
2015/9/30
23
点𝑣が供給点のとき
18 𝑣
10
25
3
4
6
5
𝑣
20
𝐷
2015/9/30
24
点𝑣が需要点のとき
8
10
25
3
𝑣
4
20 𝑣
5
𝐷
2015/9/30
20
10
25
20
𝑤
25
点𝑣が需要点のとき
20 𝑣
5
𝑣
25
𝑤
2015/9/30
26
点𝑣が需要点のとき
30 𝑣
30 𝑣
25
𝑤
2015/9/30
27
研究背景
• 電力配送問題（分割問題）
— 全ての需要点にそれらの需要量だけの電力を供給で
きるか?
線形時間アルゴリズム[Ito et al.2005]
• 供給率最大化問題
—全ての需要点にはそれらの需要量だけの電力を供給
することができないとき,全ての需要点にそれらの需要
量の一定の割合𝑟（0 ≤ 𝑟 ≤ 1）だけ供給することにし,そ
の割合を最大化したい.その最大の割合𝑟 ∗ はいくら
か？この𝑟 ∗ を最大供給率と呼ぶ.
—供給率最大化問題を解く完全多項式時間近似
スキーム（FPTAS）を与える。
2015/9/30
28

Download Report