비선형 문제 변환

Python으로 배우는 Optimization 입문

Jasmin Ludolf

Content Developer

비선형 함수 최대화

화가는 비용 $C(q) = \sqrt q$ 로 최대 16점 제작, $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$; $B$는 $A$ 선행 필요
이익은 $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}$로 대체
제약 추가
- $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$

연필을 든 사람이 큰 할 일 목록 옆에 서 있음

선형화: 이진수와 연속변수의 곱

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$

Lass uns üben!

Python으로 배우는 Optimization 입문