3. Thuật toán đơn hình 2 pha dạng chính 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 CHÍNH TẮC

Ta cần đưa bài toán về dạng chính tắc cực đại hóa, với các hệ số ở cột $b$ đều không âm để tiến hành áp dụng thuật toán đơn hình 2 pha.

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

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

  $$\begin{align*} \max & \quad \mathbf{1}^\top Ax \\ \text{s.t.} & \quad Ax + y = b, \quad x, y \ge 0 \end{align*}$$

  $x = 0$ và $y = b$ là một nghiệm cơ sở chấp nhận được của LP này.

  Dễ thấy rằng bài toán gốc có nghiệm chấp nhận được khi bài toán phụ trợ có giá trị tối ưu bằng $\mathbf{1}^\top b$ và nghiệm tối ưu thỏa mãn $y = 0$, do với $Ax + y = b$ và $y \ge 0$ thì

  $$1^\top Ax = 1^\top b - 1^\top y \le 1^\top b$$

  Trong trường hợp trên, ta cần phải tìm một cơ sở xuất phát. Giả sử bài toán phụ trợ kết thúc với một cơ sở $B$.

  • TH1: Nếu cơ sở này không chứa biến nhân tạo $y$ thì nó chính là một cơ sở cho bài toán gốc.

  • TH2: Nếu còn một số biến $y$ nằm trong cơ sở (trường hợp cơ sở suy biến), thì ta phải đẩy chúng ra khỏi cơ sở.

    Để đẩy các biến nhân tạo khỏi cơ sở:

    • Nếu một biến $y_i$ là biến cơ sở và hàng tương ứng có tất cả hệ số của các biến ở bài toán ban đầu đều bằng 0, ta có thể bỏ nó đi.
    • Nếu tồn tại ít nhất một hệ số khác 0 ở biến ban đầu, ta thực hiện phép xoay để đưa một biến gốc vào cơ sở thay cho biến $y_i$.

• Pha 2: Thực hiện thuật toán đơn hình với bảng đơn hình thu được ở pha 1, ta thu được nghiệm tối ưu của bài toán.

▸ VÍ DỤ

• Pha 1: Xét bài toán phụ trợ sau

Hàm mục tiêu của bài toán phụ trợ là $\mathbf{1}^\top Ax$ nên hệ số của $x_i$ chính là tổng hệ số của biến đó ở các ràng buộc. Từ bài toán trên, ta kẻ bảng đơn hình như sau:

Nghiệm tối ưu có $y = 0$ nên bài toán gốc có nghiệm chấp nhận được.

Khi này, ta thấy hàng $y_3$ có hệ số của $x_1, x_2, x_3, x_4$ đều là 0, do đó đây là điều kiện phụ thuộc tuyến tính, vậy ta có thể loại bỏ điều kiện này đi.

Bỏ phần bảng đơn hình tương ứng với biến $y$ và hàm mục tiêu $w$, ta thu được bảng đơn hình với cơ sở chấp nhận được xuất phát cho bài toán gốc.

Pha 2: Áp dụng thuật toán đơn hình với bảng đơn hình đã rút ra ở trên

Vậy nghiệm tối ưu của bài toán là $(x_1, x_2, x_3, x_4)^\top = (\frac{1}{2}, \frac{5}{4}, 0, 1)^\top$ với giá trị tối ưu là $z = -\frac{7}{4}$.