2. Bài toán tối ưu

Bài toán tối ưu hóa (Optimization Problem) là bài toán mà ở đó ta phải cực tiểu hay cực đại hóa một hàm số trên một tập cho trước.

• Hàm số được cực tiểu hay cực đại hóa gọi là hàm mục tiêu (objective function).
• Tập hợp cho trước được gọi là miền chấp nhận được (feasible region).

▸ BÀI TOÁN CỰC TIỂU HÓA

▸ BÀI TOÁN CỰC ĐẠI HÓA

Trong đó:

• Biến $x = (x_1, x_2,...,x_n)$.
• Hàm mục tiêu $f$.
• Điều kiện ràng buộc $x \in \mathcal{X}$ (tập nghiệm chấp nhận được $\mathcal{X}$). Thông thường $\mathcal{X}$ không được cho dưới dạng tập hợp mà được xác định bởi các đẳng thức và bất đẳng thức.

$\\$

▸ ĐỊNH NGHĨA

Bài toán được gọi là

• Không có nghiệm chấp nhận được (infeasible), nếu $\mathcal{X} = \varnothing$. Ngược lại, nó được gọi là có nghiệm chấp nhận được (feasible).
• Không bị chặn (unbounded) nếu nó có nghiệm chấp nhận được, và ta luôn tìm được nghiệm chấp nhận được có giá trị hàm mục tiêu nhỏ hơn một giá trị hữu hạn cho trước bất kì (đối với bài toán cực tiểu hóa), hoặc lớn hơn một giá trị hữu hạn cho trước bất kì (đối với bài toán cực đại hóa).

$x \in \mathcal{X}$ được gọi là một nghiệm chấp nhận được (feasible solution).

$x^* \in \mathcal{X}$ được gọi là một nghiệm tối ưu (optimal solution), nếu:

đối với bài toán cực tiểu hóa, hoặc:

đối với bài toán cực đại hóa.

$\\$

▸ MỘT SỐ DẠNG BÀI TOÁN TỐI ƯU

Bài toán tối ưu không ràng buộc (unconstrained)

Bài toán tối ưu tuyến tính (linear program)

Bài toán tối ưu nguyên (integer program)

Bài toán tối ưu phi tuyến (nonlinear)

Bài toán tối ưu lồi (convex)

• Dạng tổng quát:

  $$\min_{x \in \mathcal{X}} \ \ f(x)$$

  với $f: \mathcal{X} \rightarrow \mathbb{R}$ lồi và $\mathcal{X}$ là một tập lồi.

• Dạng giới hạn bởi các đẳng thức và bất đẳng thức:

  $$\begin{align*} \max_{x} & \ \ f(x) \\ s.t. & \ \ g_i(x) \leq 0, \ i = 1, 2, ..., k \\ & \ \ h_j(x) = 0, \ j = 1, 2, ..., l \\ \end{align*}$$

  trong đó $f, g_i \ (i = 1, 2, ..., k)$ là các hàm lồi, và $h_j \ (j = 1, 2, ..., l)$ là các hàm affine.