混合整数線形計画法（MILP）

Pythonで学ぶOptimization入門

Jasmin Ludolf

Content Developer

混合整数線形計画法

  • MILP
  • 制約変数が離散の場合に用いる最適化手法
Pythonで学ぶOptimization入門

ドレスかタキシードか

  • 需要:

    • ドレス: 最大$20$、価格$\$ 1000$
    • タキシード: 最大$12$、価格$\$ 600$

  • ドレス生産:

    • 生地 $\$ 110$
    • Mr. S 6時間（$\$40/h$）
    • Ms. T 3時間（$\$35/h$）
  • タキシード生産:
    • 生地 $\$ 75$
    • Mr. S 4時間（$\$40/h$）
    • Ms. T 1時間（$\$35/h$）

ドレスとタキシードを着たカップル

Pythonで学ぶOptimization入門

ドレスかタキシードか

  • 制約:
    • Mr. S 最大40時間
    • Ms. T 最大20時間

 

  • 利益最大化のための最適なドレス・タキシード数量を求める

赤い布をマネキンに当ててドレスを作る人

Pythonで学ぶOptimization入門

目的関数と制約

  • $g$: 1週間のドレス数
  • $t$: 1週間のタキシード数

  • $C$: 生地費 + Mr. S 賃金 + Mr. T 機会費用

  • 機会費用: 縫製を選ぶことで他の業務を捨てるコスト

$C=110g+240g+105g+75t+160t+35t$

$C=455g+270t$

費用 生地 Mr. S Ms. T
ドレス $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
タキシード $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Pythonで学ぶOptimization入門

目的関数と制約

  • 収益: $R=1000g+600t$
  • 費用: $C=455g+270t$
  • 利益: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • 制約:

    • 需要: $g\leq20$, $t\leq12$

    • 資源: $6g+4t\leq40$, $3g+t\leq20$

Pythonで学ぶOptimization入門

SciPyでのMILP

from scipy.optimize import milp, Bounds, LinearConstraint


result = milp([-545, -330],

              integrality=[1, 1],

              bounds=Bounds([0, 0], [20, 12]),

              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
Pythonで学ぶOptimization入門

SciPyでのMILP

print(result.message)
print(f'The optimal number of gowns produced is: {result.x[0]:.2f}')
print(f'The optimal number of tuxedos produced is: {result.x[1]:.2f}') 

Optimization terminated successfully. (HiGHS Status 7: Optimal)
The optimal number of gowns produced is: 6.00
The optimal number of tuxedos produced is: 1.00
Pythonで学ぶOptimization入門

整数性

result = milp([-545, -330],  
              bounds=Bounds([0, 0], [20, 12]), 
              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
...

The optimal number of gowns produced is: 6.67
The optimal number of tuxedos produced is: 0.00
Pythonで学ぶOptimization入門

整数性を無視した影響

  • 提案解: ドレス6.67着、タキシード0.00着 $\rightarrow$

    • 四捨五入: 7着と0着

      • Mr. S: $6g+4t=6\times7 + 4\times0 = 42$
      • $42 \gt 40$

    • 切り捨て: 6着と0着

      • Mr. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Ms. T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • 利益を$330（約10%）取り逃し！
Pythonで学ぶOptimization入門

練習しましょう！

Pythonで学ぶOptimization入門

Preparing Video For Download...