Hướng Dẫn Giải Bài Toán Đơn Hình Chi Tiết Chuẩn KaTeX

Giới thiệu về hướng dẫn giải bài toán đơn hình, nhiều sinh viên thường cảm thấy bối rối trước bảng đơn hình với các ký hiệu và chỉ số phức tạp, dễ dẫn đến nhầm lẫn. Tuy nhiên, bản chất của thuật toán là đưa ra các tình huống rất cụ thể. Để nắm vững, điều quan trọng là phải hiểu các khái niệm cơ bản như độc lập tuyến tính của hệ véc-tơ và cơ sở của không gian véc-tơ, thay vì chỉ cố gắng áp dụng thuật toán một cách máy móc. Bài viết này tập trung phân tích sâu hơn các bước thực hiện, minh họa bằng các ví dụ và bài tập điển hình, giúp sinh viên tự học và nghiên cứu hiệu quả hơn.

Đề Bài

Tối đa hóa hàm mục tiêu:
Z = 3x_1 + 2x_2

Với các ràng buộc:

1. x_1 + x_2 \le 4
2. 2x_1 + x_2 \le 5
3. x_1 \ge 0, x_2 \ge 0

(Đây là một bài toán quy hoạch tuyến tính dạng chuẩn gốc, thường được giải bằng thuật toán đơn hình để tìm phương án tối ưu.)

Phân Tích Yêu Cầu

Bài toán yêu cầu tìm giá trị lớn nhất có thể của hàm mục tiêu Z = 3x_1 + 2x_2, với điều kiện các biến x_1, x_2 phải thỏa mãn đồng thời ba ràng buộc đã cho. Các ràng buộc này giới hạn không gian các phương án khả thi cho x_1 và x_2. Thuật toán đơn hình sẽ giúp chúng ta đi từ một phương án khả thi ban đầu đến phương án tối ưu bằng cách cải tiến dần giá trị của hàm mục tiêu.

Các dữ kiện quan trọng:

• Hàm mục tiêu: Z = 3x_1 + 2x_2
• Ràng buộc 1: x_1 + x_2 \le 4
• Ràng buộc 2: 2x_1 + x_2 \le 5
• Ràng buộc phi âm: x_1 \ge 0, x_2 \ge 0

Hướng giải tổng quát là chuyển bài toán về dạng chuẩn, thiết lập bảng đơn hình ban đầu và thực hiện các bước lặp theo thuật toán để tìm nghiệm tối ưu.

Kiến Thức/Nền Tảng Cần Dùng

Để giải bài toán quy hoạch tuyến tính bằng thuật toán đơn hình, chúng ta cần nắm vững các khái niệm sau:

1. Dạng Chuẩn của Bài Toán Quy Hoạch Tuyến Tính:
   Một bài toán quy hoạch tuyến tính được coi là ở dạng chuẩn nếu nó có dạng:
   Tối đa hóa Z = c^T x
   Với các ràng buộc Ax \le b và x \ge 0.
   Trong đó, $x$ là vector biến, $c$ là vector hệ số của hàm mục tiêu, $A$ là ma trận các hệ số ràng buộc, và $b$ là vector vế phải.

2. Biến Dư (Slack Variables):
   Để chuyển các bất đẳng thức dạng \le thành phương trình, ta thêm biến dư. Ví dụ, ràng buộc x_1 + x_2 \le 4 sẽ trở thành x_1 + x_2 + s_1 = 4, với s_1 \ge 0 là biến dư thứ nhất. Biến dư này đại diện cho “phần còn lại” hoặc “không gian chưa sử dụng” trong ràng buộc.

3. Phương Án Khả Thi Cơ Bản (Basic Feasible Solution – BFS):
   Trong thuật toán đơn hình, chúng ta làm việc với các phương án khả thi cơ bản. Một phương án khả thi là cơ bản nếu số lượng biến khác không (biến cơ sở) bằng số lượng ràng buộc (sau khi đã chuyển về dạng phương trình). Các biến còn lại gọi là biến không cơ sở, và chúng có giá trị bằng 0.

4. Bảng Đơn Hình (Simplex Tableau):
   Đây là một bảng ma trận dùng để biểu diễn bài toán quy hoạch tuyến tính ở dạng chuẩn, bao gồm hệ số hàm mục tiêu, hệ số các biến cơ sở và biến không cơ sở, cùng với vế phải của các ràng buộc. Các phép toán trong thuật toán đơn hình được thực hiện trên bảng này.

5. Nguyên Tắc Cải Tiến Nghiệm:
   Thuật toán đơn hình tìm kiếm phương án tối ưu bằng cách:

   • Bắt đầu từ một phương án khả thi cơ bản (thường là gốc tọa độ với các biến dư).
   • Kiểm tra xem có thể cải thiện giá trị hàm mục tiêu bằng cách chuyển sang một phương án khả thi cơ bản khác hay không. Việc này được thực hiện bằng cách đưa một biến không cơ sở vào cơ sở (tăng giá trị của nó lên) và loại bỏ một biến cơ sở ra khỏi cơ sở (giảm giá trị của nó về 0).
   • Lặp lại quá trình này cho đến khi đạt được phương án tối ưu, tức là không còn biến không cơ sở nào có thể làm tăng giá trị hàm mục tiêu.

Áp dụng cho bài toán trên:
Trước tiên, ta chuyển bài toán về dạng chuẩn với các phương trình bằng cách thêm biến dư s_1, s_2:
Hàm mục tiêu: Z - 3x_1 - 2x_2 = 0
Ràng buộc 1: x_1 + x_2 + s_1 = 4
Ràng buộc 2: 2x_1 + x_2 + s_2 = 5
Với x_1, x_2, s_1, s_2 \ge 0.

Trong phương án khả thi ban đầu, ta thường chọn các biến dư làm biến cơ sở. Đặt x_1 = 0, x_2 = 0, ta có s_1 = 4, s_2 = 5. Giá trị hàm mục tiêu lúc này là Z = 0.

Hướng Dẫn Giải Chi Tiết

Chúng ta sẽ thiết lập bảng đơn hình ban đầu và tiến hành các bước lặp.

Bước 1: Thiết lập Bảng Đơn Hình Ban Đầu

Giải thích: Hàng $Z$ biểu diễn phương trình -3x_1 - 2x_2 + Z = 0. Các hệ số của biến cơ sở trong hàng $Z$ luôn bằng 0.

Bước 2: Kiểm tra tính tối ưu và Chọn Biến Vào Cơ Sở

Xem xét hàng $Z$. Nếu tất cả các hệ số của biến không cơ sở (x_1, x_2) đều không âm, thì phương án hiện tại là tối ưu. Trong bảng này, có các hệ số âm (-3 và -2), nên phương án chưa tối ưu.
Ta chọn biến có hệ số âm nhất trong hàng $Z$ để đưa vào cơ sở, nhằm cải thiện giá trị $Z$ nhanh nhất. Ở đây, hệ số của x_1 là -3, nhỏ hơn -2. Do đó, x_1 sẽ là biến vào cơ sở.

Bước 3: Chọn Biến Ra Khỏi Cơ Sở (Tìm Tỷ Lệ)

Để xác định biến nào sẽ ra khỏi cơ sở, ta tính tỷ lệ giữa Vế Phải và hệ số tương ứng của biến vào cơ sở (x_1) trong các hàng ràng buộc. Chỉ xét các hệ số dương.

• Hàng s_1: \frac{4}{1} = 4
• Hàng s_2: \frac{5}{2} = 2.5

Ta chọn hàng có tỷ lệ nhỏ nhất. Tỷ lệ nhỏ nhất là 2.5, tương ứng với hàng s_2. Do đó, s_2 sẽ là biến ra khỏi cơ sở.

Bước 4: Thực hiện Phép Biến Đổi Gauss-Jordan để Cập Nhật Bảng

Biến vào cơ sở là x_1, biến ra khỏi cơ sở là s_2. Phần tử trục (pivot element) là hệ số của x_1 trong hàng s_2, tức là số 2.

• Mục tiêu: Biến phần tử trục thành 1 và các phần tử khác trong cột trục thành 0.

1. Chuẩn hóa hàng trục (hàng s_2): Chia toàn bộ hàng s_2 cho 2.
   Hàng s_2 mới (sẽ là hàng x_1):
   \frac{1}{2} [2, 1, 0, 1, 5] = [1, 0.5, 0, 0.5, 2.5]

2. Cập nhật các hàng khác:

   • Hàng s_1 mới = Hàng s_1 cũ – (hệ số x_1 của hàng s_1 cũ) (Hàng s_2 mới)
     Hàng s_1 cũ có hệ số x_1 là 1.
     Hàng s_1 mới = `[1, 1, 1, 0, 4] – 1 [1, 0.5, 0, 0.5, 2.5] =[1-1, 1-0.5, 1-0, 0-0.5, 4-2.5] =[0, 0.5, 1, -0.5, 1.5]`

   • Hàng $Z$ mới = Hàng $Z$ cũ – (hệ số x_1 của hàng $Z$ cũ) (Hàng s_2 mới)
     Hàng $Z$ cũ có hệ số x_1 là -3.
     Hàng $Z$ mới = `[-3, -2, 0, 0, 0] – (-3) [1, 0.5, 0, 0.5, 2.5] =[-3, -2, 0, 0, 0] + 3 [1, 0.5, 0, 0.5, 2.5] =[-3+3, -2+1.5, 0+0, 0+1.5, 0+7.5] =[0, -0.5, 0, 1.5, 7.5]`

Bảng Đơn Hình Sau Lần Lặp 1:

Giải thích: Phương án khả thi hiện tại là x_1 = 2.5, x_2 = 0, với s_1 = 1.5, s_2 = 0. Giá trị hàm mục tiêu là Z = 7.5.

Bước 5: Lặp lại Kiểm tra và Chọn Biến

Xem xét hàng $Z$. Vẫn còn hệ số âm (-0.5 cho x_2). Do đó, bài toán chưa tối ưu.
x_2 là biến vào cơ sở.

Tính tỷ lệ cho x_2:

• Hàng s_1: \frac{1.5}{0.5} = 3
• Hàng x_1: \frac{2.5}{0.5} = 5

Tỷ lệ nhỏ nhất là 3, tương ứng với hàng s_1. Do đó, s_1 sẽ là biến ra khỏi cơ sở.

Phần tử trục là 0.5 (hệ số của x_2 trong hàng s_1).

Bước 6: Thực hiện Biến Đổi Gauss-Jordan Lần 2

Biến vào cơ sở là x_2, biến ra khỏi cơ sở là s_1. Phần tử trục là 0.5.

1. Chuẩn hóa hàng trục (hàng s_1): Chia toàn bộ hàng s_1 cho 0.5.
   Hàng s_1 mới (sẽ là hàng x_2):
   \frac{1}{0.5} [0, 0.5, 1, -0.5, 1.5] = [0, 1, 2, -1, 3]

2. Cập nhật các hàng khác:

   • Hàng x_1 mới = Hàng x_1 cũ – (hệ số x_2 của hàng x_1 cũ) (Hàng s_1 mới)
     Hàng x_1 cũ có hệ số x_2 là 0.5.
     Hàng x_1 mới = `[1, 0.5, 0, 0.5, 2.5] – 0.5 [0, 1, 2, -1, 3] =[1-0, 0.5-0.5, 0-1, 0.5-(-0.5), 2.5-1.5] =[1, 0, -1, 1, 1]`

   • Hàng $Z$ mới = Hàng $Z$ cũ – (hệ số x_2 của hàng $Z$ cũ) (Hàng s_1 mới)
     Hàng $Z$ cũ có hệ số x_2 là -0.5.
     Hàng $Z$ mới = `[0, -0.5, 0, 1.5, 7.5] – (-0.5) [0, 1, 2, -1, 3] =[0, -0.5, 0, 1.5, 7.5] + 0.5 [0, 1, 2, -1, 3] =[0+0, -0.5+0.5, 0+1, 1.5+(-0.5), 7.5+1.5] =[0, 0, 1, 0.5, 9]`

Bảng Đơn Hình Sau Lần Lặp 2:

Giải thích: Phương án khả thi hiện tại là x_1 = 1, x_2 = 3. Giá trị hàm mục tiêu là Z = 9.

Bước 7: Kiểm tra lại Tính Tối ưu

Xem xét hàng $Z$. Tất cả các hệ số của biến không cơ sở (s_1, s_2) đều không âm (1 và 0.5). Điều này chứng tỏ phương án hiện tại là tối ưu.

Mẹo kiểm tra:

• Tính hợp lệ của phương án: Kiểm tra xem các biến cơ sở có giá trị không âm hay không. Trong bảng cuối cùng, x_1 = 1 và x_2 = 3 đều không âm.
• Thế vào hàm mục tiêu: Z = 3(1) + 2(3) = 3 + 6 = 9. Khớp với giá trị trong bảng.
• Kiểm tra ràng buộc:
  • x_1 + x_2 \le 4 implies 1 + 3 = 4 \le 4 (Thỏa mãn, s_1=0 sau khi thế biến gốc vào)
  • 2x_1 + x_2 \le 5 implies 2(1) + 3 = 2 + 3 = 5 \le 5 (Thỏa mãn, s_2=0 sau khi thế biến gốc vào)

Lỗi hay gặp:

• Nhầm lẫn hệ số âm/dương: Khi chọn biến vào cơ sở hoặc kiểm tra tính tối ưu.
• Sai sót trong phép biến đổi Gauss-Jordan: Đặc biệt là phép cộng/trừ vector hoặc phép nhân với số âm.
• Chọn sai tỷ lệ nhỏ nhất: Dẫn đến việc chọn sai biến ra khỏi cơ sở.
• Sử dụng biến dư làm biến không cơ sở khi chúng có giá trị dương: Trong bảng cuối cùng, các biến không cơ sở (s_1, s_2) đều có giá trị hệ số âm trong hàng $Z$, nghĩa là chúng có thể làm giảm giá trị Z nếu được đưa vào cơ sở. Khi không còn hệ số âm nào trong hàng $Z$, bài toán đã tối ưu.

Đáp Án/Kết Quả

Phương án tối ưu cho bài toán quy hoạch tuyến tính đã cho là:

• x_1 = 1
• x_2 = 3
• Giá trị lớn nhất của hàm mục tiêu Z = 9.

Điều này có nghĩa là để đạt được lợi nhuận/hiệu quả cao nhất, doanh nghiệp nên sản xuất 1 đơn vị sản phẩm loại 1 và 3 đơn vị sản phẩm loại 2.

Kết Luận

Giải bài toán đơn hình đòi hỏi sự cẩn trọng trong từng bước, từ việc chuyển đổi bài toán, thiết lập bảng, chọn biến vào/ra cơ sở, cho đến thực hiện các phép biến đổi Gauss-Jordan. Việc nắm vững lý thuyết nền tảng về biến dư và phương án khả thi cơ bản là yếu tố then chốt. Thực hành với nhiều ví dụ khác nhau sẽ giúp bạn làm quen với các tình huống có thể xảy ra và nâng cao kỹ năng giải quyết bài toán một cách hiệu quả.

Ngày chỉnh sửa nội dung mới nhất January 8, 2026 by Thầy Đông

Thầy Đông

Thầy Đông – Giảng viên Đại học Công nghiệp Hà Nội, giáo viên luyện thi THPT
Thầy Đông bắt đầu sự nghiệp tại một trường THPT ở quê nhà, sau đó trúng tuyển giảng viên Đại học Công nghiệp Hà Nội nhờ chuyên môn vững và kinh nghiệm giảng dạy thực tế. Với nhiều năm đồng hành cùng học sinh, thầy được biết đến bởi phong cách giảng dạy rõ ràng, dễ hiểu và gần gũi. Hiện thầy giảng dạy tại dehocsinhgioi, tiếp tục truyền cảm hứng học tập cho học sinh cấp 3 thông qua các bài giảng súc tích, thực tiễn và giàu nhiệt huyết.