混合整數線性規劃（MILP）

Python 最佳化入門

Jasmin Ludolf

Content Developer

混合整數線性規劃

MILP
當限制變數為離散變數時使用的最佳化技術

禮服或燕尾服

需求：
- 禮服：至多 $20$ 件，價格 $\$ 1000$
- 燕尾服：至多 $12$ 件，價格 $\$ 600$
禮服生產成本：
- 布料 $\$ 110$
- S 先生 6 小時，$\$40/h$
- T 小姐 3 小時，$\$35/h$
燕尾服生產成本：
- 布料 $\$ 75$
- S 先生 4 小時，$\$40/h$
- T 小姐 1 小時，$\$35/h$

一對穿著禮服與燕尾服的情侶

禮服或燕尾服

限制：
- S 先生至多 40 小時
- T 小姐至多 20 小時

找到可使利潤最大的禮服與燕尾服產量

一個人拿著紅布為人台披上，製作洋裝

目標與限制

$g$：每週禮服件數
$t$：每週燕尾服件數
$C$：布料成本 + S 先生薪資 + T 小姐機會成本
機會成本：選擇縫製而放棄其他責任的成本

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

$C=455g+270t$

成本	布料	S 先生	T 小姐
禮服	$\$110$	$\$40/h \times 6h = \$240$	$\$35/h \times 3h = \$105$
燕尾服	$\$75$	$\$40/h \times 4h = \$160$	$\$35/h \times 1h = \$35$

目標與限制

收益： $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$

在 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]))

在 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

整數性（Integrality）

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

忽略整數性的後果

建議解為 6.67 件禮服與 0.00 件燕尾服 $\rightarrow$
- 四捨五入為 7 件禮服、0 件燕尾服
  - S 先生：$6g+4t=6\times7 + 4\times0 = 42$
  - $42 \gt 40$
- 截斷為 6 件禮服、0 件燕尾服
  - S 先生：$6g+4t=6\times6 + 4\times0 = 36$
  - T 小姐：$3g+1t=3\times6 + 1\times0 = 18$
  - $\Pi=545g+330t=545\times 6+330 \times 0=3270$
  - 少了 $330（約 10%）的利潤！

一起來練習吧！

Python 最佳化入門