予算配分（ナップサック問題）

🔥 Vibe プロンプト

「CTOが500万ドルの予算で10のプロジェクトから最適な組み合わせを選択。依存関係と相互排他制約あり。」

予算配分問題とは？

予算配分は、現実世界のナップサック問題です。予算制約、依存関係、相互排他などの複雑な制約下で、最適なプロジェクト組み合わせを選択します。

| 制約タイプ | 例 | |----------|------| | 予算 | 総コスト ≤ $5M | | 依存関係 | AIチャットボットにはデータプラットフォームが必要 | | 相互排他 | アプリかAPIプラットフォーム、両方は不可 | | 最低限 | 最低1つのセキュリティプロジェクト |

CP-SATによる実装

from ortools.sat.python import cp_model

# プロジェクト: (名前, コスト, リターン)
projects = [
    ("AIチャットボット", 150, 400),
    ("データプラットフォーム", 200, 350),
    ("アプリ開発", 180, 300),
    ("SEO最適化", 50, 180),
    ("パフォーマンス改善", 120, 250),
    ("自動テスト導入", 80, 200),
    ("セキュリティ監査", 60, 150),
    ("国際化対応", 100, 220),
    ("APIプラットフォーム", 160, 280),
    ("BIダッシュボード", 90, 190),
]

budget = 500  # $500K
n = len(projects)

model = cp_model.CpModel()
x = [model.NewBoolVar(f'x_{i}') for i in range(n)]

# 予算制約
model.Add(sum(projects[i][1] * x[i] for i in range(n)) <= budget)

# 依存関係: AIチャットボットにはデータプラットフォームが必要
model.Add(x[0] <= x[1])

# 相互排他: アプリとAPIプラットフォームは両方選べない
model.Add(x[2] + x[8] <= 1)

# 最低1つのセキュリティプロジェクト
model.Add(x[6] >= 1)

# 目的: リターン最大化
model.Maximize(sum(projects[i][2] * x[i] for i in range(n)))

# 求解
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 予算配分結果 ===")
    print(f"総リターン: ${int(solver.ObjectiveValue())}K")
    
    total_cost = 0
    selected = []
    for i in range(n):
        if solver.Value(x[i]):
            total_cost += projects[i][1]
            selected.append(projects[i])
    
    print(f"使用予算: ${total_cost}K / ${budget}K")
    print(f"残余予算: ${budget - total_cost}K")
    
    print(f"\n選択プロジェクト ({len(selected)}):")
    for name, cost, ret in selected:
        roi = (ret - cost) / cost * 100
        print(f"  ✅ {name}: コスト${cost}K, リターン${ret}K, ROI{roi:.0f}%")

拡張: ポートフォリオ最適化

# 株式ポートフォリオに適用
stocks = [
    ("AAPL", 180, 0.25),
    ("GOOGL", 140, 0.20),
    ("MSFT", 330, 0.22),
    ("AMZN", 150, 0.30),
]

# ちょうど3銘柄を選択
model.Add(sum(x[i] for i in range(len(stocks))) == 3)

# 1銘柄に60%以上投資不可
for i in range(len(stocks)):
    model.Add(stocks[i][1] * x[i] <= 1000 * 0.6)

まとめ

| 項目 | 詳細 | |------|------| | 問題 | 予算内でプロジェクトを選択しリターン最大化 | | 制約 | 予算、依存関係、相互排他、最低数 | | CP-SAT | すべての制約タイプを自然に処理 | | ROI分析 | 解から自動計算可能 | | 応用 | 投資、採用、リソース配分 |

組合せ最適化コース完了！🎉

✅ 箱詰め問題
✅ ジョブスケジューリング
✅ 多次元ナップサック
✅ 2D切断・包装
✅ 予算配分
✅ 依存関係と相互排他
✅ ポートフォリオ最適化