非線形問題の変換

Pythonで学ぶOptimization入門

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$

大きなToDoリストの横で鉛筆を持つ人物

線形化：バイナリ×連続の積

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$

Passons à la pratique !

Pythonで学ぶOptimization入門