Biến đổi bài toán phi tuyến

Nhập môn Tối ưu hóa với Python

Jasmin Ludolf

Content Developer

Tối đa hóa hàm phi tuyến

  • Họa sĩ sản xuất tối đa 16 bức, chi phí $C(q) = \sqrt q$ với $q$ là sản lượng
  • Nhu cầu nghịch $p=\frac{3}{\sqrt q}$ với $p$ là giá
  • $\max \Pi = pq - C=\frac{3}{\sqrt q}q-\sqrt q = 2\sqrt q$

$$\max 2\sqrt q$$

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

Người phụ nữ vẽ trên toan

Nhập môn Tối ưu hóa với Python

SciPy hay PuLP?

  • SciPy: milp yêu cầu mục tiêu tuyến tính
  • 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'
Nhập môn Tối ưu hóa với Python

Thay thế để tuyến tính hóa

  • Thay $z = \sqrt q$
  • $\rightarrow$ $\Pi=2\sqrt q =2z$
  • $\rightarrow$ ràng buộc công suất $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.
Nhập môn Tối ưu hóa với Python

Lập ngân sách vốn với dự án phụ thuộc

Bài toán

  • Dự án $A$, $B$, $C$; $A$ là điều kiện tiên quyết của $B$
  • Lợi nhuận lần lượt $V$ = [250, 200, 300]
  • Vốn đầu tư $I$ = [2000, 1900, 2500] và chỉ có $4600

Mô hình hóa

  • $o_A$, $o_B$, $o_C$ là nhị phân; chỉ báo chọn dự án

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

Biểu tượng quản lý ngân sách

Nhập môn Tối ưu hóa với Python

Tuyến tính hóa: tích của biến nhị phân

  • Thay $o_Ao_B=o_{AB}$
  • Thêm ràng buộc
    • $o_{AB}\leq o_{A}$
    • $o_{AB}\leq o_{B}$
    • $o_{AB}\geq o_{A} + o_{B} -1$
  • Bài toán rút gọn thành

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

Nhập môn Tối ưu hóa với Python

Phân bổ nguồn lực với chi phí đào tạo

  • Phân bổ 120 tác vụ để tối thiểu hóa chi phí
  • Nhân sự senior ($S$), junior ($J$), thực tập ($I$)
  • Chi phí đào tạo thực tập $500
  • Chi phí xử lý một tác vụ $c$ = [30, 40, 5]
  • Vector $x$: số tác vụ được phân bổ tối ưu
  • Nhị phân $o$: có đào tạo thực tập hay không
  • $TC = 30x_S+40x_J+(5x_I+500)o$

Người cầm bút chì đứng cạnh danh sách việc cần làm lớn

Nhập môn Tối ưu hóa với Python

Tuyến tính hóa: tích của nhị phân và liên tục

  • Phương pháp Big-M đưa vào số lớn M
  • Thay tích bằng $z = (5x_I+500)o$
  • Áp đặt
    • $-oM\leq z \leq oM$
    • $-(1-o)M \leq z- (5x_I+500)o \leq (1-o)M$
Nhập môn Tối ưu hóa với Python

Ayo berlatih!

Nhập môn Tối ưu hóa với Python

Preparing Video For Download...