2. Thuật toán đơn hình 2 pha dạng chuẩn tắc

Thuật toán đơn hình 2 pha sẽ được áp dụng trong các bài toán LP mà ta không dễ dàng tìm được một cơ sở chấp nhận được xuất phát.

Nội dung chính của 2 pha:

• Pha 1: Giải bài toán phụ trợ để tìm một cơ sở chấp nhận được xuất phát.
• Pha 2: Sử dụng cơ sở tìm được, áp dụng thuật toán đơn hình để tìm nghiệm tối ưu.

$\\$

▸ DẠNG CHUẨN TẮC

Trong nhiều trường hợp các ràng buộc có vế phải âm hoặc không thể tạo được cơ sở chấp nhận được xuất phát một cách trực tiếp, ta sẽ sử dụng phương pháp đơn hình 2 pha.

Các bước thực hiện đối với dạng chuẩn tắc cực đại hóa:

• Pha 1: Giải bài toán phụ trợ sau

  $$\begin{align*} \max & \quad -x_0 \\ \text{s.t.} & \quad -x_0\mathbf{1} + Ax \le b, \quad x_0, x \ge 0 \end{align*}$$

  Sử dụng bảng đơn hình có cả hàm mục tiêu gốc $z$, hàm mục tiêu $w$ của bài toán phụ trợ và thêm cột $x_0$.

  Nếu giá trị tối ưu của $w = 0$ thì bài toán gốc có nghiệm chấp nhận được. Nếu giá trị tối ưu của $w > 0$ thì bài toán gốc vô nghiệm.

• Pha 2: Trích ra một bảng mới gồm phần hàm mục tiêu và các cột (biến) của bài toán gốc từ bảng đơn hình thu được sau khi thực hiện pha 1. Sau đó áp dụng thuật toán đơn hình để giải bài toán LP.

▸ VÍ DỤ

Bài toán gốc:

Pha 1: Viết bài toán phụ trợ như sau

Lần xoay đầu tiên, ta chọn cột xoay là cột $x_0$ với hàng xoay $i$ là hàng có chỉ số $b_i < 0$ (thông thường chọn hàng có chỉ số âm nhất).

Sau đó tiến hành thuật toán đơn hình với hàm mục tiêu $w$ như bình thường.

Như vậy $w$ có giá trị tối ưu là 0. Ta thu được cơ sở xuất phát ban đầu là $\{s_1, x_3, x_2\}$, cơ sở này không chứa $x_0$.

Pha 2: Trích xuất bảng đơn hình của bài toán gốc từ phần bảng đơn hình của bài toán phụ trợ, bỏ đi cột $x_0$ và hàng $w$. Sau đó, áp dụng thuật toán đơn hình với bảng đơn hình mới.

Vậy nghiệm tối ưu là $(x_1, x_2, x_3)^\top = (0, \frac{14}{5}, \frac{17}{5})^\top$ với giá trị tối ưu là $z = \frac{3}{5}$.