混合整数线性规划（MILP）

Python 优化入门

Jasmin Ludolf

Content Developer

混合整数线性规划

MILP
当约束变量为离散变量时使用的优化方法

礼服还是西装

需求：
- 礼服：至多 $20$，售价 $\$ 1000$
- 西装：至多 $12$，售价 $\$ 600$
礼服生产：
- 面料 $\$ 110$
- S 先生 6 小时，$\$40/小时$
- T 女士 3 小时，$\$35/小时$
西装生产：
- 面料 $\$ 75$
- S 先生 4 小时，$\$40/小时$
- T 女士 1 小时，$\$35/小时$

一对穿着礼服和礼服西装的情侣

礼服还是西装

约束：
- 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

整数性

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%）的利润！

Passons à la pratique !

Python 优化入门