非线性问题的变换

Python 优化入门

Jasmin Ludolf

Content Developer

最大化非线性函数

  • 画家最多生产16幅画，成本 $C(q) = \sqrt q$，$q$ 为数量
  • 逆需求 $p=\frac{3}{\sqrt q}$，$p$ 为价格
  • $\max \Pi = pq - C=\frac{3}{\sqrt q}q-\sqrt q = 2\sqrt q$

$$\max 2\sqrt q$$

$$s.t. \ \ \ \ q\leq 16 $$

女性在画布上作画

Python 优化入门

SciPy 还是 PuLP？

  • SciPy：milp 需要线性目标
  • PuLP：
model = LpProblem('Artist', LpMaximize)
q = LpVariable('q', lowBound=0, upBound=16)
model += 2 * q**(1/2)

--> 3 model += 2 * q**(1/2)

TypeError: unsupported operand type(s) for ** or pow(): 'LpVariable' and 'float'
Python 优化入门

代换以线性化

  • 代换 $z = \sqrt q$
  • $\rightarrow$ $\Pi=2\sqrt q =2z$
  • $\rightarrow$ 产能约束 $z^2\leq 16\Leftrightarrow z\leq 4$
model = LpProblem('Artist', LpMaximize)
z = LpVariable('z', lowBound=0, upBound=4, cat='Integer')
model += 2 * z

model.solve() 
print(f"Solution is {LpStatus[model.status]}.")
print(f"The optimal number of paintings is {round(z.varValue**2)}.")

Solution is Optimal. 
The optimal number of paintings is 16.
Python 优化入门

含依赖项目的资本预算

问题描述

  • 项目 $A$、$B$、$C$；$A$ 是 $B$ 的先决条件
  • 利润 $V$ = [250, 200, 300]
  • 所需投资 $I$ = [2000, 1900, 2500]，仅有 $4600 可用

建模

  • $o_A$, $o_B$, $o_C$ 为二元变量；表示是否选择项目

$\max\ \ o_AV_A + o_Ao_BV_B + o_CV_C$

$s.t.\ \ \ \ o_AI_A + o_Ao_BI_B + o_CI_C\leq 4600$

预算管理图标

Python 优化入门

线性化：二元变量的乘积

  • 用 $o_Ao_B=o_{AB}$ 替换
  • 添加约束
    • $o_{AB}\leq o_{A}$
    • $o_{AB}\leq o_{B}$
    • $o_{AB}\geq o_{A} + o_{B} -1$
  • 问题化简为

$$\max\ \ o_AV_A + o_{AB}V_B + o_CV_C$$

$$s.t.\ \ \ \ o_AI_A + o_{AB}I_B + o_CI_C\leq 4600$$

$$ o_{A} + o_{B} -1 \leq o_{AB}\leq o_{A}, o_{B}$$

Python 优化入门

含培训成本的资源分配

  • 分配120个任务以最小化成本
  • 高级($S$)、初级($J$)与实习生($I$)
  • 实习生培训成本 $500
  • 处理单个任务成本 $c$ = [30, 40, 5]
  • 向量 $x$：最佳分配的任务量
  • 二元 $o$：是否给实习生培训
  • $TC = 30x_S+40x_J+(5x_I+500)o$

手持铅笔的人站在大型待办清单旁

Python 优化入门

线性化：二元与连续变量的乘积

  • Big-M 方法引入一个足够大的数 M
  • 用 $z = (5x_I+500)o$ 替代乘积
  • 施加
    • $-oM\leq z \leq oM$
    • $-(1-o)M \leq z- (5x_I+500)o \leq (1-o)M$
Python 优化入门

Vamos praticar!

Python 优化入门

Preparing Video For Download...