轉換非線性問題

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 $$

女子在畫布上作畫

選 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'

代換以線性化

以 $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.

含相依專案的資本預算

問題描述

專案 $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$

預算管理圖示

線性化：二元變數的乘積

以 $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}$$

含訓練成本的資源分配

分派 120 項任務以最小化成本
資深（$S$）、資淺（$J$）、實習生（$I$）
實習生訓練成本 $500
單一任務成本 $c$ = [30, 40, 5]
向量 $x$：最佳分配的任務量
二元 $o$：實習生是否受訓
$TC = 30x_S+40x_J+(5x_I+500)o$

手持鉛筆的人站在大型待辦清單旁

線性化：二元與連續變數乘積

BigM 方法引入一個足夠大的數 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 最佳化入門