選挙調査の最適化 PuLP

選挙調査の最適化

選挙調査に関する最適化問題として、以下の問題を考えます。

問題:

🔹選挙区ごとに最小の調査費用で有権者の意見を調査する。

制約条件:

1️⃣ 全ての選挙区には少なくとも1つの調査所が必要である。
2️⃣ 調査所ごとの調査費用は異なる。
3️⃣ 各選挙区の調査人数は制約されており、最小と最大の人数がある。

解法

PuLPを使用してこの問題を解くためには、以下のステップを実行します。

1. 必要なモジュールをインポートする。
1
from pulp import LpProblem, LpVariable, LpInteger, LpMinimize, lpSum, value
2. 問題を作成する。
1
problem = LpProblem("Election Survey", LpMinimize)
3. 変数を定義する。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 選挙区の数
num_districts = 5

# 調査所の数
num_polling_stations = 3

# 調査費用
survey_costs = [10, 15, 12]

# 各選挙区の調査人数の制約
min_surveyors = [2, 3, 1, 2, 2]
max_surveyors = [5, 6, 4, 5, 4]

# 変数の作成
x = {}
for i in range(num_polling_stations):
    for j in range(num_districts):
        x[i, j] = LpVariable(f"x_{i}_{j}", lowBound=0, cat=LpInteger)
4. 目的関数を定義する。
1
2
# 目的関数（調査費用の最小化）
problem += lpSum(survey_costs[i] * x[i, j] for i in range(num_polling_stations) for j in range(num_districts))
5. 制約条件を追加する。
1
2
3
4
5
6
7
8
# 各選挙区には少なくとも1つの調査所が必要
for j in range(num_districts):
    problem += lpSum(x[i, j] for i in range(num_polling_stations)) >= 1

# 各選挙区の調査人数の制約
for j in range(num_districts):
    problem += lpSum(x[i, j] for i in range(num_polling_stations)) >= min_surveyors[j]
    problem += lpSum(x[i, j] for i in range(num_polling_stations)) <= max_surveyors[j]
6. 問題を解く。
1
problem.solve()
7. 最適解を出力する。
1
2
3
for i in range(num_polling_stations):
    for j in range(num_districts):
        print(f"Polling Station {i+1} in District {j+1}: {value(x[i, j])}")

上記のコードは、選挙調査に関する最適化問題をPuLPを使用して解く方法の一例です。

選挙区ごとに最小の調査費用で有権者の意見を調査するために、調査所の割り当てと調査費用の最小化を目指しています。

最適解は、各調査所が各選挙区にどれだけの調査人数を割り当てるかを示し、最小の調査費用も表示されます。

全ソースコード

以下に、選挙調査に関する最適化問題をPuLPで解くための全コードを示します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from pulp import LpProblem, LpVariable, LpInteger, LpMinimize, lpSum, value

# 選挙区の数
num_districts = 5

# 調査所の数
num_polling_stations = 3

# 調査費用
survey_costs = [10, 15, 12]

# 各選挙区の調査人数の制約
min_surveyors = [2, 3, 1, 2, 2]
max_surveyors = [5, 6, 4, 5, 4]

# 問題の作成
problem = LpProblem("Election Survey", LpMinimize)

# 変数の作成
x = {}
for i in range(num_polling_stations):
    for j in range(num_districts):
        x[i, j] = LpVariable(f"x_{i}_{j}", lowBound=0, cat=LpInteger)

# 目的関数（調査費用の最小化）
problem += lpSum(survey_costs[i] * x[i, j] for i in range(num_polling_stations) for j in range(num_districts))

# 各選挙区には少なくとも1つの調査所が必要
for j in range(num_districts):
    problem += lpSum(x[i, j] for i in range(num_polling_stations)) >= 1

# 各選挙区の調査人数の制約
for j in range(num_districts):
    problem += lpSum(x[i, j] for i in range(num_polling_stations)) >= min_surveyors[j]
    problem += lpSum(x[i, j] for i in range(num_polling_stations)) <= max_surveyors[j]

# 問題を解く
problem.solve()

# 最適解を出力
print("Optimization Status:", problem.status)
print("Minimum Survey Cost:", value(problem.objective))

# 各調査所の割り当て結果を表示
for i in range(num_polling_stations):
    for j in range(num_districts):
        print(f"Polling Station {i+1} in District {j+1}: {value(x[i, j])}")

上記のコードを実行すると、最適解と各調査所の割り当て結果が出力されます。

[実行結果]
Optimization Status: 1
Minimum Survey Cost: 100.0
Polling Station 1 in District 1: 2.0
Polling Station 1 in District 2: 3.0
Polling Station 1 in District 3: 1.0
Polling Station 1 in District 4: 2.0
Polling Station 1 in District 5: 2.0
Polling Station 2 in District 1: 0.0
Polling Station 2 in District 2: 0.0
Polling Station 2 in District 3: 0.0
Polling Station 2 in District 4: 0.0
Polling Station 2 in District 5: 0.0
Polling Station 3 in District 1: 0.0
Polling Station 3 in District 2: 0.0
Polling Station 3 in District 3: 0.0
Polling Station 3 in District 4: 0.0
Polling Station 3 in District 5: 0.0

最適化の結果、調査費用の最小値は100.0となりました。

調査所の割り当て結果を見ると、例えば”Polling Station 1 in District 1”では2人の調査員が配置されています。

また、”Polling Station 1 in District 4”や”Polling Station 1 in District 5”ではそれぞれ2人ずつの調査員が配置されています。

各調査所の割り当て結果は、有権者の意見を調査するための最適な配置を示しています。

この結果を元に、最小の調査費用で選挙区ごとに調査を行うために必要な調査所の配置と調査人数を計画することができます。