食糧供給最適化 Google OR-Tools

食糧供給最適化

Google OR-Toolsは最適化問題を解くためのライブラリであり、主にルーティング、ネットワークフロー、線形プログラミングなどの問題を扱います。

具体的な貧困問題として、一定の予算で最大数の家庭に食糧を供給するという問題を考えてみます。

この問題は整数線形プログラミング問題として定式化で、Google OR-ToolsのLinearSolverを用いて解くことができます。

それぞれの家庭が必要とする食糧の量と、運搬コスト（距離や時間に基づいた値）が既知であるとします。

以下に、この問題を解くためのPythonコードを示します。

（ただし、このコードはあくまで一例であり、実際の問題はより多くの要素や複雑な制約を考慮する必要があります。）

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
from ortools.linear_solver import pywraplp
import matplotlib.pyplot as plt

# データ
families = [0, 1, 2, 3, 4]  # 表現の一部として家族を表すインデックス
food_required = [3, 7, 2, 5, 4]  # 各家族が必要とする食糧の量
transport_costs = [10, 20, 5, 15, 10]  # 各家族への食糧配達のコスト

# ベクトル全体で最小化するためのスカラー乗数
scalar_multiplier = 10

# 問題を作成
solver = pywraplp.Solver.CreateSolver('SCIP')

# 変数を作成
x = []
for i in families:
    x.append(solver.IntVar(0, 1, 'x[%i]' % i))  # x[i] = 家族iに食糧を配達するかどうか (0 または 1)

# 制約を定義
budget = 30  # 予算
solver.Add(sum(transport_costs[i] * x[i] for i in families) <= budget)

# 目的関数を定義
solver.Maximize(scalar_multiplier * sum(food_required[i] * x[i] for i in families) - sum(transport_costs[i] * x[i] for i in families))

# 問題を解く
solver.Solve()

# 結果を出力
print("Total food delivered = ", sum(food_required[i] * x[i].solution_value() for i in families))
delivered = [x[i].solution_value() for i in families]
plt.figure(figsize=(10,5))
plt.bar(range(len(families)), delivered)
plt.title("Food delivered to each family")
plt.xlabel("Family")
plt.ylabel("Food quantity")
plt.xticks(range(len(families)), families)
plt.show()

[実行結果]

ソースコード解説

このコードは、Google OR-Toolsを使用して最適な食糧配達問題を解決し、結果を可視化するものです。

詳細について見ていきましょう。

1. ライブラリのインポートとデータの定義

1
2
3
4
5
6
7
from ortools.linear_solver import pywraplp
import matplotlib.pyplot as plt

families = [0, 1, 2, 3, 4]  # 家族を表すインデックス
food_required = [3, 7, 2, 5, 4]  # 各家族の食糧必要量
transport_costs = [10, 20, 5, 15, 10]  # 各家族への食糧配達コスト
scalar_multiplier = 10  # 最小化するためのスカラー乗数

まず、Google OR-ToolsとMatplotlibをインポートし、最適化のためのデータを定義しています。
familiesは家族を表すインデックスのリスト、food_requiredは各家族の食糧必要量のリスト、transport_costsは各家族への食糧配達コストのリストです。
また、scalar_multiplierは後で使われるスカラー乗数です。

2. 問題の作成と変数の定義

1
2
3
4
5
solver = pywraplp.Solver.CreateSolver('SCIP')

x = []
for i in families:
   x.append(solver.IntVar(0, 1, 'x[%i]' % i))  # 家族iに食糧を配達するかどうか (0 または 1)

Google OR-Toolsの線形ソルバーを作成し、バイナリ変数 x を定義しています。
x[i] は家族 i に食糧を配達するかどうかを示す変数で、$0$か$1$の値を取ります。

3. 制約の定義

1
2
budget = 30
solver.Add(sum(transport_costs[i] * x[i] for i in families) <= budget)

予算制約を設定しています。
すべての家族への食糧配達コストの合計が budget 以下である必要があります。

4. 目的関数の定義と最適化

1
2
solver.Maximize(scalar_multiplier * sum(food_required[i] * x[i] for i in families) - sum(transport_costs[i] * x[i] for i in families))
solver.Solve()

目的関数は、家族への食糧配達量を最大化し、同時にコストを最小化するように設定されています。
そして、ソルバーを使って問題を解決しています。

5. 結果の出力と可視化

1
2
3
4
5
6
7
8
9
print("Total food delivered = ", sum(food_required[i] * x[i].solution_value() for i in families))
delivered = [x[i].solution_value() for i in families]
plt.figure(figsize=(10,5))
plt.bar(range(len(families)), delivered)
plt.title("Food delivered to each family")
plt.xlabel("Family")
plt.ylabel("Food quantity")
plt.xticks(range(len(families)), families)
plt.show()

最後に、配達された食糧量を表示し、Matplotlibを使用して各家族への食糧配達量を可視化しています。
print文で配達された総食糧量を表示し、棒グラフで各家族の配達量を示しています。

[実行結果]