ネットワークフローの応用例（輸送問題）

輸送問題は、物流や交通における効率的な資源配分を最適化するための問題です。この問題は通常、特定の供給地点から需要地点へ物資を輸送する際のコストを最小化することを目的としています。ここでは、Pythonを用いて輸送問題を解決するための基本的な手法を学びます。

輸送問題の定式化

輸送問題は次のように定式化できます。

• 供給地点：各供給地点の供給量は一定です。
• 需要地点：各需要地点の需要量は一定です。
• 輸送コスト：供給地点から需要地点への輸送コストは異なります。

この問題を解決するためには、最適な輸送割り当てを見つける必要があります。

サンプルコード

以下のコードは、Pythonを使って簡単な輸送問題を解決する方法を示しています。

コード

次に、輸送問題を解決するためのコードを見ていきます。

# 供給量と需要量の定義
supply = [20, 30, 25]  # 供給地点の供給量
demand = [15, 25, 35]  # 需要地点の需要量

# 輸送コスト行列の定義
cost_matrix = [
    [8, 6, 10],  # 供給地点1から各需要地点へのコスト
    [9, 12, 13], # 供給地点2から各需要地点へのコスト
    [14, 9, 16]  # 供給地点3から各需要地点へのコスト
]

# 最適輸送割り当てを計算
def transport_problem(supply, demand, cost_matrix):
    total_cost = 0
    assignments = []
    supply_copy = supply[:]
    demand_copy = demand[:]

    for i in range(len(supply)):
        for j in range(len(demand)):
            if supply_copy[i] == 0 or demand_copy[j] == 0:
                continue
            # 輸送量は供給量と需要量のうち小さい方
            amount = min(supply_copy[i], demand_copy[j])
            total_cost += amount * cost_matrix[i][j]
            assignments.append((i + 1, j + 1, amount))
            supply_copy[i] -= amount
            demand_copy[j] -= amount

    return assignments, total_cost

# 結果の計算
assignments, total_cost = transport_problem(supply, demand, cost_matrix)

# 結果の表示
print("最適な輸送割り当て:")
for assign in assignments:
    print(f"供給地点 {assign[0]} から 需要地点 {assign[1]} へ {assign[2]} 輸送")
print(f"総コスト: {total_cost}")

コードの解説

1. 供給量と需要量の定義:
   • 供給地点（supply）と需要地点（demand）の供給量と需要量をリストで定義します。
2. 輸送コスト行列の定義:
   • 各供給地点から各需要地点への輸送コストを2次元リスト（行列）として定義します。
3. アルゴリズム:
   • 各供給地点から各需要地点へ、供給量と需要量の小さい方を輸送します。
   • 輸送量をコストと掛け算し、総コストを計算します。
   • 各供給量と需要量がゼロになるまで繰り返します。
4. 結果の表示:
   • 各供給地点と需要地点の輸送割り当てを表示します。
   • 最終的な総コストを表示します。

このコードを実行すると、最適な輸送割り当てとその総コストが出力されます。これにより、どの供給地点からどの需要地点にどれだけの量を輸送すればコストを最小化できるかがわかります。

実行結果

最適な輸送割り当て:

• 供給地点 1 から 需要地点 1 へ 15 輸送
• 供給地点 1 から 需要地点 2 へ 5 輸送
• 供給地点 2 から 需要地点 2 へ 20 輸送
• 供給地点 2 から 需要地点 3 へ 10 輸送
• 供給地点 3 から 需要地点 3 へ 25 輸送
• 総コスト: 905

まとめ

輸送問題はネットワークフローの重要な応用例であり、効率的な資源配分を実現するためのアルゴリズムを学ぶことができます。ここでは、標準的なPythonのみを使用して基本的な輸送問題を解決しました。このアルゴリズムの基本を理解することで、より高度な最適化問題や実務への応用が可能になります。