“Giải Mã” Bài Tập Phương Pháp Đơn Hình Có Lời Giải: Từ A đến Z Cho Người Mới Bắt Đầu

Chào bạn, có phải bạn đang “vật lộn” với các bài toán quy hoạch tuyến tính và nghe đâu đó phương pháp đơn hình là “chìa khóa” nhưng khi bắt tay vào giải Bài Tập Phương Pháp đơn Hình Có Lời Giải thì lại thấy như đang “lạc trôi” giữa một “biển” số liệu và công thức? Đừng lo lắng, bạn không đơn độc đâu! Phương pháp đơn hình là một công cụ cực kỳ mạnh mẽ và phổ biến trong lĩnh vực tối ưu, nhưng để nắm vững nó, đặc biệt là khi giải các bài tập có lời giải, đòi hỏi chúng ta phải đi từ từ, chắc chắn qua từng bước. Bài viết này được viết ra với mục tiêu giúp bạn “giải mã” bí ẩn này, cung cấp cho bạn không chỉ lời giải mà còn là cách hiểu sâu sắc, để bạn tự tin đối mặt với bất kỳ bài toán đơn hình nào sau này.

Phương pháp đơn hình là gì?

Phương pháp đơn hình (Simplex Method) là một thuật toán lặp được sử dụng để tìm phương án tối ưu cho các bài toán quy hoạch tuyến tính (Linear Programming – LP). Nó hoạt động bằng cách di chuyển từ một đỉnh của miền ràng buộc (một đa diện lồi) sang một đỉnh “tốt hơn” lân cận cho đến khi đạt đến đỉnh tối ưu nhất.

Nói nôm na, nếu bài toán của bạn là tìm cách phân bổ các nguồn lực khan hiếm (tiền, vật liệu, thời gian…) để đạt được mục tiêu tốt nhất (lợi nhuận cao nhất, chi phí thấp nhất…), thì phương pháp đơn hình giống như việc bạn đang đứng ở một góc nhà và được hướng dẫn đi từng bước qua các phòng (các đỉnh của miền ràng buộc) cho đến khi tìm thấy “kho báu” (phương án tối ưu) ẩn trong một căn phòng nào đó, mà không cần phải lục tung cả ngôi nhà.

Tại sao bài tập phương pháp đơn hình có lời giải lại quan trọng?

Việc thực hành bài tập phương pháp đơn hình có lời giải là cách tốt nhất để bạn biến lý thuyết khô khan thành kiến thức thực tế.

Lý thuyết cung cấp nền tảng, nhưng chỉ khi bạn tự tay giải một bài toán, mắc lỗi, và rồi đối chiếu với lời giải, bạn mới thực sự hiểu được “linh hồn” của phương pháp này. Nó giúp bạn:

• Củng cố kiến thức về các khái niệm như dạng chuẩn, biến cơ sở, phi cơ sở, tiêu chuẩn tối ưu, tỷ số tối thiểu.
• Nắm vững quy trình giải từng bước.
• Nhận diện các trường hợp đặc biệt (bài toán không có phương án tối ưu, bài toán có vô số phương án tối ưu, bài toán suy biến).
• Phát triển kỹ năng phân tích và giải quyết vấn đề, những kỹ năng này cực kỳ hữu ích khi bạn cần nâng cao chất lượng dịch vụ trong công việc hay hoàn thành các báo cáo, luận văn sau này.

Đừng chỉ đọc lời giải một cách thụ động. Hãy coi mỗi bài tập phương pháp đơn hình có lời giải như một thử thách. Tự mình làm trước, sau đó mới xem lời giải để học hỏi từ sai lầm của chính mình. Đó là cách học hiệu quả nhất!

Các bước “giải mã” một bài toán đơn hình có lời giải

Giải một bài toán quy hoạch tuyến tính bằng phương pháp đơn hình đòi hỏi sự tỉ mỉ và tuân thủ đúng trình tự. Dưới đây là các bước chi tiết, giống như một cuốn cẩm nang giúp bạn đi từ bài toán ban đầu đến lời giải cuối cùng.

Bước 1: Đưa bài toán về dạng chuẩn (Standard Form)

Dạng chuẩn là gì?

Dạng chuẩn của bài toán quy hoạch tuyến tính là dạng mà tất cả các ràng buộc đều là phương trình với vế phải không âm, và tất cả các biến đều không âm. Hàm mục tiêu có thể là cực đại hoặc cực tiểu.

Để đưa một bài toán bất kỳ về dạng chuẩn, chúng ta thực hiện các biến đổi sau:

• Nếu hàm mục tiêu là cực tiểu (Minimize Z): Chuyển về cực đại bằng cách Maximze (-Z’). Hàm mục tiêu mới sẽ là Z’ = -Z. Khi tìm được phương án tối ưu X cho Z’, giá trị tối ưu của Z ban đầu sẽ là Z = -Z’*.
• Nếu ràng buộc là bất phương trình:
  • <=: Thêm biến bù (slack variable) không âm vào vế trái để biến thành phương trình. Ví dụ: x1 + x2 <= 5 trở thành x1 + x2 + s1 = 5, với s1 >= 0. Biến bù biểu thị lượng “thừa” còn lại sau khi sử dụng nguồn lực.
  • >=: Trừ đi biến dư (surplus variable) không âm và thêm biến giả (artificial variable) không âm vào vế trái để biến thành phương trình. Biến giả được thêm vào chỉ để có một biến cơ sở ban đầu cho ràng buộc đó. Nó phải bằng 0 ở phương án tối ưu. Ví dụ: x1 - x2 >= 3 trở thành x1 - x2 - s2 + a1 = 3, với s2 >= 0, a1 >= 0. Biến dư s2 biểu thị lượng “vượt quá” mức tối thiểu.
• Nếu ràng buộc là phương trình: Thêm biến giả không âm vào vế trái. Ví dụ: x1 + 2x2 = 7 trở thành x1 + 2x2 + a2 = 7, với a2 >= 0.
• Nếu có biến không bị ràng buộc dấu (free variable): Biến đổi biến đó thành hiệu của hai biến không âm. Ví dụ: biến x_j không bị ràng buộc dấu thì đặt x_j = x_j' - x_j'', với x_j' >= 0, x_j'' >= 0. Thay thế x_j trong toàn bộ bài toán bằng hiệu này.
• Nếu vế phải của ràng buộc là âm: Nhân cả hai vế của phương trình/bất phương trình đó với -1 và đảo chiều bất phương trình (nếu có). Ví dụ: -x1 + x2 <= -2 trở thành x1 - x2 >= 2. Sau đó xử lý bất đẳng thức >= như trên.

Quá trình chuyển đổi này nghe có vẻ rắc rối, nhưng khi làm bài tập phương pháp đơn hình có lời giải, bạn sẽ thấy nó tuân theo một quy luật nhất định. Chìa khóa là xác định đúng loại ràng buộc và loại biến cần thêm/bớt.

Bước 2: Xây dựng bảng đơn hình ban đầu (Initial Simplex Tableau)

Bảng đơn hình là gì và cấu trúc ra sao?

Bảng đơn hình là một cách trình bày ma trận các hệ số của bài toán quy hoạch tuyến tính ở dạng chuẩn, cùng với các thông tin cần thiết để thực hiện thuật toán đơn hình.

Cấu trúc cơ bản của bảng đơn hình (đối với bài toán cực đại, sử dụng phương pháp M hoặc phương pháp hai pha nếu có biến giả):

• Hàng đầu tiên: Chứa các biến (x1, x2, … và các biến bù, dư, giả). Bên dưới mỗi biến là hệ số của nó trong hàm mục tiêu gốc (c_j).
• Cột “Cơ sở”: Liệt kê các biến cơ sở của phương án ban đầu. Thông thường, đây là các biến bù, biến giả hoặc các biến gốc có hệ số ma trận đơn vị tương ứng.
• Cột “cB”: Chứa hệ số của các biến trong cột “Cơ sở” trong hàm mục tiêu.
• Các cột từ x1 đến a_m: Chứa các hệ số của các biến tương ứng trong các phương trình ràng buộc. Dòng tương ứng với biến cơ sở B_i sẽ có hệ số 1 tại cột B_i và 0 tại các cột biến cơ sở khác, tạo thành ma trận đơn vị (hoặc một phần của nó).
• Cột “Vế phải”: Chứa giá trị các vế phải của các phương trình ràng buộc. Đây chính là giá trị của các biến cơ sở trong phương án ban đầu (các biến phi cơ sở bằng 0).
• Hàng “c_j – z_j” (hoặc “z_j – c_j”): Hàng đánh giá, dùng để kiểm tra tính tối ưu và chọn biến vào cơ sở. z_j = Tổng (cB * hệ số của x_j trong ràng buộc tương ứng). c_j - z_j là sự thay đổi của hàm mục tiêu khi tăng biến x_j lên 1 đơn vị (trong khi giữ các biến phi cơ sở khác bằng 0 và điều chỉnh các biến cơ sở).

Phương pháp M và Phương pháp Hai pha (khi có biến giả):

Nếu bài toán có biến giả, chúng ta cần đảm bảo các biến giả này bằng 0 ở phương án tối ưu. Có hai cách xử lý:

1. Phương pháp M (Big M Method): Thêm một khoản phạt rất lớn (M) vào hàm mục tiêu cho mỗi biến giả.
   • Với bài toán cực đại (Max): Z = ... - M*a_i (trừ M*a_i).
   • Với bài toán cực tiểu (Min): Z = ... + M*a_i (cộng M*a_i). M là một số rất lớn.
     Trong bảng đơn hình, hệ số c_j của biến giả sẽ là -M (Max) hoặc +M (Min). Khi tính z_j – c_j, M sẽ xuất hiện. Chúng ta coi M là một số lớn vô cùng so với các hệ số khác.
2. Phương pháp Hai pha: Chia quá trình giải thành hai pha.
   • Pha 1: Giải một bài toán phụ với hàm mục tiêu là cực tiểu tổng các biến giả (Minimize W = sum a_i). Mục tiêu là đưa tất cả các biến giả ra khỏi cơ sở (W=0). Nếu không thể đưa tất cả biến giả ra (W > 0), bài toán gốc không có phương án khả thi.
   • Pha 2: Nếu Pha 1 đạt W=0, loại bỏ cột biến giả ra khỏi bảng đơn hình cuối cùng của Pha 1. Thay hàng đánh giá bằng hàng c_j – z_j của hàm mục tiêu gốc và tiếp tục giải bằng phương pháp đơn hình thông thường từ bảng này.

Việc lựa chọn phương pháp M hay Hai pha tùy thuộc vào sở thích và yêu cầu của bài toán/giảng viên. Trong các bài tập phương pháp đơn hình có lời giải, bạn sẽ thấy cả hai cách tiếp cận này được sử dụng.

Bước 3: Kiểm tra tính tối ưu (Check for Optimality)

Sau khi có bảng đơn hình, bước tiếp theo là kiểm tra xem phương án hiện tại có phải là tối ưu chưa. Chúng ta dựa vào hàng đánh giá (c_j – z_j hoặc z_j – c_j):

• Đối với bài toán cực đại (Max Z): Phương án là tối ưu khi tất cả các giá trị trong hàng c_j – z_j đều nhỏ hơn hoặc bằng 0 (c_j – z_j <= 0). Điều này có nghĩa là không có biến phi cơ sở nào có thể làm tăng giá trị hàm mục tiêu nếu được đưa vào cơ sở.
• Đối với bài toán cực tiểu (Min Z): Phương án là tối ưu khi tất cả các giá trị trong hàng z_j – c_j đều nhỏ hơn hoặc bằng 0 (z_j – c_j <= 0) hoặc, nếu dùng c_j – z_j, thì tất cả phải lớn hơn hoặc bằng 0 (c_j – z_j >= 0).

Nếu điều kiện tối ưu chưa thỏa mãn, chúng ta cần thực hiện một bước lặp để cải thiện phương án.

Bước 4: Chọn biến vào cơ sở (Choose the Entering Variable)

Nếu phương án hiện tại chưa tối ưu, chúng ta cần chọn một biến phi cơ sở để đưa vào cơ sở nhằm tăng giá trị hàm mục tiêu (đối với Max) hoặc giảm giá trị hàm mục tiêu (đối với Min).

• Đối với bài toán cực đại (Max Z): Chọn biến có giá trị (c_j – z_j) dương lớn nhất trong hàng đánh giá. Cột tương ứng với biến này được gọi là cột trục (pivot column). Biến này sẽ là biến vào cơ sở.
• Đối với bài toán cực tiểu (Min Z): Chọn biến có giá trị (c_j – z_j) âm lớn nhất (tức là giá trị dương lớn nhất của z_j – c_j). Cột tương ứng là cột trục.

Việc chọn biến có sự thay đổi hàm mục tiêu lớn nhất giúp thuật toán hội tụ nhanh hơn, mặc dù bất kỳ biến nào có c_j – z_j > 0 (Max) hoặc c_j – z_j < 0 (Min) đều có thể được chọn để vào cơ sở.

Bước 5: Chọn biến ra khỏi cơ sở (Choose the Leaving Variable)

Sau khi đã chọn được biến vào cơ sở, chúng ta cần xác định biến nào trong cơ sở hiện tại sẽ ra khỏi cơ sở để thay thế. Điều này được quyết định bởi phép thử tỷ số tối thiểu (minimum ratio test).

• Cách tính: Chia giá trị ở cột “Vế phải” (RHS) cho hệ số tương ứng ở cột trục (cột của biến vào). Thực hiện phép chia này cho tất cả các hàng mà hệ số ở cột trục là dương (> 0).
• Cách chọn: Biến ra khỏi cơ sở là biến cơ sở ở hàng có tỷ số này là nhỏ nhất và không âm. Hàng tương ứng với biến này được gọi là hàng trục (pivot row).

Lưu ý:

• Nếu hệ số ở cột trục là âm hoặc bằng 0, chúng ta không tính tỷ số cho hàng đó.
• Nếu tất cả các hệ số ở cột trục đều nhỏ hơn hoặc bằng 0, điều này có nghĩa là bài toán không bị chặn (unbounded solution) – giá trị hàm mục tiêu có thể tăng (Max) hoặc giảm (Min) vô hạn mà vẫn thỏa mãn ràng buộc. Đây là một trường hợp đặc biệt cần nhận diện.
• Nếu có nhiều hàng cho cùng tỷ số tối thiểu, bài toán bị suy biến (degeneracy). Bạn có thể chọn bất kỳ biến nào trong số đó để ra khỏi cơ sở, nhưng điều này có thể dẫn đến việc lặp lại các phương án cơ sở và gây ra hiện tượng “chu kỳ” (cycling), mặc dù rất hiếm gặp trong thực tế.

Bước 6: Biến đổi bảng đơn hình mới (Transform the New Simplex Tableau)

Sau khi xác định được biến vào và biến ra (và do đó xác định được phần tử trục – pivot element, là phần tử nằm ở giao điểm của hàng trục và cột trục), chúng ta thực hiện các phép biến đổi hàng sơ cấp để cập nhật bảng đơn hình. Mục tiêu là biến đổi cột trục sao cho phần tử trục trở thành 1, và tất cả các phần tử khác trong cột trục trở thành 0.

Các bước biến đổi:

1. Biến đổi hàng trục: Chia toàn bộ hàng trục hiện tại cho giá trị của phần tử trục. Hàng này sẽ trở thành hàng mới cho biến vừa vào cơ sở.

2. Biến đổi các hàng còn lại (kể cả hàng đánh giá): Đối với mỗi hàng khác hàng trục, tính giá trị mới của từng phần tử theo công thức:
   Giá trị mới = Giá trị cũ - (Hệ số ở cột trục của hàng đó) * (Giá trị mới tương ứng ở hàng trục)

   Nói cách khác, để biến phần tử ở hàng i cột trục j thành 0 (giả sử phần tử trục là p ở hàng r cột j), chúng ta thực hiện phép biến đổi hàng i như sau: Hàng i mới = Hàng i cũ - (Hàng i cũ[j] / Hàng r cũ[j]) * Hàng r mới. (Trong đó Hàng r mới đã được tính ở bước 1).

   Quy tắc này áp dụng cho tất cả các cột, bao gồm cột Vế phải và cột cB (nếu bạn cập nhật cột cB). Hàng đánh giá cũng được biến đổi tương tự.

Sau khi hoàn thành các phép biến đổi, bạn sẽ có một bảng đơn hình mới.

Bước 7: Lặp lại cho đến khi tối ưu (Repeat Until Optimal)

Với bảng đơn hình mới vừa thu được, chúng ta quay lại Bước 3: Kiểm tra tính tối ưu.

• Nếu phương án là tối ưu (hàng đánh giá thỏa mãn điều kiện), dừng thuật toán.
• Nếu phương án chưa tối ưu, tiếp tục các bước 4, 5, 6 để chọn biến vào/ra và biến đổi bảng cho đến khi đạt được phương án tối ưu.

Quá trình này lặp đi lặp lại, mỗi lần lặp sẽ di chuyển từ một đỉnh của miền ràng buộc sang một đỉnh lân cận “tốt hơn”, đảm bảo giá trị hàm mục tiêu không giảm (đối với Max) hoặc không tăng (đối với Min).

Bước 8: Đọc kết quả (Read the Result)

Khi thuật toán dừng lại ở bảng đơn hình tối ưu, chúng ta cần đọc kết quả từ bảng đó:

• Giá trị của các biến cơ sở: Các biến trong cột “Cơ sở” của bảng tối ưu sẽ có giá trị bằng các giá trị tương ứng trong cột “Vế phải”.
• Giá trị của các biến phi cơ sở: Các biến không có trong cột “Cơ sở” là biến phi cơ sở và có giá trị bằng 0.
• Giá trị tối ưu của hàm mục tiêu: Giá trị này thường nằm ở ô cuối cùng bên phải của hàng đánh giá (c_j – z_j hoặc z_j – c_j). Đối với bài toán Max Z, giá trị này là -Z. Đối với bài toán Min Z ban đầu được chuyển thành Max (-Z’), giá trị ở đây là -Z’. Do đó, Z = -(-Z’) = Z’*. Cẩn thận với dấu khi đọc kết quả cuối cùng!

Nếu bạn đã chuyển bài toán Min Z thành Max (-Z’), thì giá trị tối ưu của Z sẽ bằng âm giá trị tối ưu của Z’ đọc từ bảng đơn hình.

Đọc kết quả đúng là bước cuối cùng nhưng cũng rất quan trọng để hoàn thành bài tập phương pháp đơn hình có lời giải.

Ví dụ minh họa: Bài tập phương pháp đơn hình có lời giải chi tiết

Lý thuyết là vậy, nhưng “trăm hay không bằng tay quen”. Cùng nhau đi qua một ví dụ cụ thể để “thực chiến” nào!

Bài toán:

Một công ty sản xuất hai loại sản phẩm A và B. Để sản xuất một đơn vị sản phẩm A cần 2 giờ máy và 1 kg nguyên liệu. Để sản xuất một đơn vị sản phẩm B cần 1 giờ máy và 1 kg nguyên liệu. Công ty có 100 giờ máy và 80 kg nguyên liệu. Lợi nhuận thu được từ mỗi đơn vị sản phẩm A là 3 nghìn đồng, sản phẩm B là 2 nghìn đồng. Công ty muốn xác định số lượng sản phẩm mỗi loại cần sản xuất để tối đa hóa lợi nhuận.

Bước 1: Xây dựng mô hình và đưa về dạng chuẩn

Gọi x1 là số đơn vị sản phẩm A sản xuất, x2 là số đơn vị sản phẩm B sản xuất.
Mục tiêu: Tối đa hóa lợi nhuận Z = 3×1 + 2×2
Ràng buộc về máy: 2×1 + x2 <= 100
Ràng buộc về nguyên liệu: x1 + x2 <= 80
Ràng buộc về dấu: x1 >= 0, x2 >= 0

Bài toán ở dạng chuẩn (thêm biến bù s1, s2):
Max Z = 3×1 + 2×2 + 0s1 + 0s2
Subject to:
2×1 + x2 + s1 = 100
x1 + x2 + s2 = 80
x1, x2, s1, s2 >= 0

Biến gốc: x1, x2. Biến bù: s1, s2. Tất cả đều không âm. Ràng buộc là phương trình. Hàm mục tiêu là Max. Bài toán đã ở dạng chuẩn.

Bước 2: Xây dựng bảng đơn hình ban đầu

Các biến cơ sở ban đầu có thể chọn là s1 và s2 vì chúng tạo thành ma trận đơn vị (cột của s1 là [1, 0], cột của s2 là [0, 1]) và vế phải không âm.

c_j: 3 2 0 0
Biến | x1 | x2 | s1 | s2 | RHS
——–|—-|—-|—-|—-|—-
c_B | Cơ sở | | | | |
——–|——-|—-|—-|—-|—-|—-
0 | s1 | 2 | 1 | 1 | 0 | 100
0 | s2 | 1 | 1 | 0 | 1 | 80
——–|——-|—-|—-|—-|—-|—-
z_j | | 0 | 0 | 0 | 0 | 0 (z_j = Tổng cB * hệ số cột tương ứng)
c_j – z_j| | 3 | 2 | 0 | 0 | (c_j – z_j = c_j – 0 = c_j)

Bảng đơn hình ban đầu (phiên bản gọn hơn):

Phương án ban đầu: x1=0, x2=0 (phi cơ sở), s1=100, s2=80 (cơ sở). Z = 30 + 20 + 0100 + 080 = 0.

Bước 3: Kiểm tra tính tối ưu

Hàng c_j – z_j: [3, 2, 0, 0]. Có các giá trị dương (3 và 2). Phương án chưa tối ưu.

Bước 4: Chọn biến vào cơ sở

Giá trị c_j – z_j dương lớn nhất là 3 (tại cột x1). Chọn x1 làm biến vào cơ sở. Cột trục là cột x1.

Bước 5: Chọn biến ra khỏi cơ sở

Tính tỷ số RHS / hệ số cột trục cho các hàng có hệ số dương ở cột x1:

• Hàng s1: 100 / 2 = 50
• Hàng s2: 80 / 1 = 80

Tỷ số tối thiểu là 50 (tại hàng s1). Chọn s1 làm biến ra khỏi cơ sở. Hàng trục là hàng s1.
Phần tử trục là 2 (ở giao điểm hàng s1 và cột x1).

Bước 6: Biến đổi bảng đơn hình mới (Lặp 1)

• Hàng trục mới (hàng x1 mới): Chia hàng s1 cũ cho 2.
  [2, 1, 1, 0, 100] / 2 = [1, 0.5, 0.5, 0, 50]
• Hàng s2 mới: Hàng s2 cũ – (Hệ số ở cột trục của hàng s2) (Hàng x1 mới)
  [1, 1, 0, 1, 80] – (1) [1, 0.5, 0.5, 0, 50]
  = [1-1, 1-0.5, 0-0.5, 1-0, 80-50]
  = [0, 0.5, -0.5, 1, 30]
• Hàng cj-zj mới: Hàng cj-zj cũ – (Hệ số ở cột trục của hàng cj-zj) (Hàng x1 mới)
  [3, 2, 0, 0, 0] – (3) [1, 0.5, 0.5, 0, 50]
  = [3-3, 2-1.5, 0-1.5, 0-0, 0-150]
  = [0, 0.5, -1.5, 0, -150]

Bảng đơn hình sau lặp 1:

Phương án hiện tại: x1=50, x2=0, s1=0, s2=30. Z = 350 + 20 = 150. (Lưu ý giá trị hàm mục tiêu là -(-150) = 150).

Bước 7: Kiểm tra tính tối ưu (Lặp 1)

Hàng c_j – z_j: [0, 0.5, -1.5, 0]. Có giá trị dương (0.5 tại cột x2). Phương án chưa tối ưu.

Bước 4: Chọn biến vào cơ sở (Lặp 2)

Giá trị c_j – z_j dương lớn nhất là 0.5 (tại cột x2). Chọn x2 làm biến vào cơ sở. Cột trục là cột x2.

Bước 5: Chọn biến ra khỏi cơ sở (Lặp 2)

Tính tỷ số RHS / hệ số cột trục cho các hàng có hệ số dương ở cột x2:

• Hàng x1: 50 / 0.5 = 100
• Hàng s2: 30 / 0.5 = 60

Tỷ số tối thiểu là 60 (tại hàng s2). Chọn s2 làm biến ra khỏi cơ sở. Hàng trục là hàng s2.
Phần tử trục là 0.5 (ở giao điểm hàng s2 và cột x2).

Bước 6: Biến đổi bảng đơn hình mới (Lặp 2)

• Hàng trục mới (hàng x2 mới): Chia hàng s2 cũ cho 0.5.
  [0, 0.5, -0.5, 1, 30] / 0.5 = [0, 1, -1, 2, 60]
• Hàng x1 mới: Hàng x1 cũ – (Hệ số ở cột trục của hàng x1) (Hàng x2 mới)
  [1, 0.5, 0.5, 0, 50] – (0.5) [0, 1, -1, 2, 60]
  = [1-0, 0.5-0.5, 0.5-(-0.5), 0-1, 50-30]
  = [1, 0, 1, -1, 20]
• Hàng cj-zj mới: Hàng cj-zj cũ – (Hệ số ở cột trục của hàng cj-zj) (Hàng x2 mới)
  [0, 0.5, -1.5, 0, -150] – (0.5) [0, 1, -1, 2, 60]
  = [0-0, 0.5-0.5, -1.5-(-0.5), 0-1, -150-30]
  = [0, 0, -1, -1, -180]

Bảng đơn hình sau lặp 2:

Phương án hiện tại: x1=20, x2=60, s1=0, s2=0. Z = 320 + 260 = 60 + 120 = 180. (Lưu ý giá trị hàm mục tiêu là -(-180) = 180).

Bước 7: Kiểm tra tính tối ưu (Lặp 2)

Hàng c_j – z_j: [0, 0, -1, -1]. Tất cả các giá trị đều nhỏ hơn hoặc bằng 0. Phương án là tối ưu.

Bước 8: Đọc kết quả

Từ bảng đơn hình tối ưu:

• Biến cơ sở: x1 và x2. Giá trị: x1 = 20, x2 = 60.
• Biến phi cơ sở: s1 và s2. Giá trị: s1 = 0, s2 = 0.
• Giá trị tối ưu của hàm mục tiêu Z: -(-180) = 180.

Kết luận: Để tối đa hóa lợi nhuận, công ty nên sản xuất 20 đơn vị sản phẩm A và 60 đơn vị sản phẩm B. Lợi nhuận tối đa đạt được là 180 nghìn đồng.

Bạn thấy không? Khi đi đúng từng bước, một bài toán tưởng chừng phức tạp lại trở nên “dễ thở” hơn rất nhiều. Quá trình này đòi hỏi sự cẩn thận trong tính toán, giống như việc chuẩn bị báo cáo thực tập ngân hàng agribank cần độ chính xác cao về số liệu vậy.

Những “lưu ý vàng” khi giải bài tập phương pháp đơn hình

Giải bài tập phương pháp đơn hình có lời giải không chỉ là làm theo các bước, mà còn là rèn luyện khả năng nhận diện các tình huống đặc biệt và tránh những sai lầm phổ biến.

• Sai lầm ở bước chuyển đổi dạng chuẩn: Đây là bước đầu tiên và cũng là nơi dễ mắc lỗi nhất. Chỉ cần sai dấu, sai biến, thêm/bớt nhầm biến bù/dư/giả là cả bài toán đi tong. Hãy kiểm tra lại thật kỹ bước này! Nhớ rằng vế phải luôn không âm ở dạng chuẩn.
• Nhầm lẫn khi tính z_j và c_j – z_j: Công thức z_j = Tổng (cB * hệ số cột tương ứng) là nền tảng. Tính sai z_j sẽ dẫn đến sai hàng đánh giá và sai cả quá trình lặp sau đó.
• Sai trong phép thử tỷ số tối thiểu: Chỉ tính tỷ số với các hàng có hệ số dương ở cột trục. Tính sai tỷ số hoặc chọn nhầm tỷ số (không phải tỷ số nhỏ nhất không âm) sẽ chọn sai biến ra, khiến thuật toán không hội tụ hoặc đi sai hướng.
• Sai sót trong phép biến đổi hàng: Các phép biến đổi hàng cần được thực hiện chính xác cho tất cả các phần tử trong hàng. Chỉ một sai số nhỏ cũng sẽ lan truyền và làm hỏng toàn bộ bảng đơn hình. Cẩn thận với các số âm và phân số.
• Không nhận diện được trường hợp đặc biệt: Bài toán không bị chặn (unbounded), không có phương án khả thi (infeasible), suy biến (degeneracy), hoặc có nhiều phương án tối ưu. Việc nắm vững cách nhận diện các trường hợp này từ bảng đơn hình là rất quan trọng. Ví dụ, bài toán không bị chặn khi cột trục có tất cả các hệ số <= 0. Bài toán không có phương án khả thi (khi dùng phương pháp M) khi ở bảng tối ưu vẫn còn biến giả dương, hoặc (khi dùng phương pháp Hai pha) Pha 1 kết thúc với W > 0.
• Đọc sai kết quả cuối cùng: Nhớ phân biệt biến cơ sở và phi cơ sở. Đặc biệt cẩn thận với dấu của giá trị hàm mục tiêu khi chuyển đổi từ bài toán Min sang Max.

“Sai một ly, đi một dặm” là câu nói rất đúng trong trường hợp này. Tuy nhiên, đừng nản lòng! Mỗi lần mắc lỗi và sửa lỗi chính là một lần bạn học được sâu hơn. Càng làm nhiều bài tập phương pháp đơn hình có lời giải, bạn sẽ càng tinh ý và ít mắc sai lầm hơn.

TS. Trần Thị Mai Phương, một chuyên gia lâu năm trong lĩnh vực Vận trù học, từng chia sẻ:

“Nhiều sinh viên ban đầu thấy phương pháp đơn hình khá ‘khó nuốt’ vì các bước biến đổi liên tục. Nhưng mấu chốt là hiểu được ý nghĩa đằng sau mỗi bước: tại sao lại chọn biến này vào, tại sao biến kia phải ra, phép biến đổi hàng thực chất là gì. Khi hiểu được ‘tâm hồn’ của thuật toán, việc làm bài tập sẽ trở nên logic và thú vị hơn nhiều.”

Lời khuyên của cô Mai Phương nhấn mạnh vào việc hiểu bản chất, không chỉ là học thuộc lòng các bước. Điều này rất đúng, bởi khi bạn hiểu, bạn sẽ ít khi làm sai ngay từ gốc.

Phương pháp đơn hình trong thực tế ứng dụng

Bạn có thể tự hỏi, liệu phương pháp đơn hình chỉ là lý thuyết trên sách vở hay nó thực sự có ích? Câu trả lời là CÓ, rất có ích là đằng khác! Phương pháp đơn hình là xương sống của nhiều mô hình tối ưu trong các ngành công nghiệp khác nhau.

• Sản xuất: Tối ưu hóa kế hoạch sản xuất (sản xuất bao nhiêu mỗi loại sản phẩm?) để tối đa hóa lợi nhuận với các ràng buộc về máy móc, lao động, nguyên liệu. Ví dụ minh họa chúng ta vừa làm là một phiên bản đơn giản của bài toán này.
• Logistics và Vận tải: Tối ưu hóa tuyến đường vận chuyển, phân bổ hàng hóa vào các kho, lên lịch trình giao hàng để giảm chi phí hoặc thời gian.
• Tài chính: Tối ưu hóa danh mục đầu tư để tối đa hóa lợi nhuận kỳ vọng với mức rủi ro chấp nhận được.
• Quản lý nguồn nhân lực: Phân công công việc cho nhân viên, lên lịch làm việc ca kíp để tối ưu hiệu suất hoặc chi phí. Đây là một khía cạnh quan trọng khi nghiên cứu tiểu luận quản trị nguồn nhân lực.
• Nông nghiệp: Lập kế hoạch trồng trọt, chăn nuôi để tối đa hóa năng suất dựa trên diện tích đất, lượng phân bón, nguồn nước…

Các bài tập phương pháp đơn hình có lời giải thường đơn giản hóa các mô hình thực tế để dễ tiếp cận, nhưng nguyên lý đằng sau là hoàn toàn giống nhau. Nắm vững phương pháp này giúp bạn có một công cụ tư duy mạnh mẽ để phân tích và giải quyết các vấn đề tối ưu trong đời sống và công việc.

Nâng cao kỹ năng với bài tập phương pháp đơn hình

Việc làm đi làm lại các bài tập phương pháp đơn hình có lời giải giống như việc rèn kiếm vậy, càng mài dũa càng sắc bén. Mỗi bài tập là một cơ hội để bạn:

• Rèn luyện sự cẩn thận: Tính toán chính xác là yếu tố sống còn.
• Phát triển tư duy logic: Hiểu được luồng suy nghĩ của thuật toán, tại sao lại làm bước này trước bước kia.
• Làm quen với các trường hợp khác nhau: Bài toán chỉ có 2 biến, nhiều biến hơn, có ràng buộc dấu bằng, dấu lớn hơn hoặc bằng, có biến không ràng buộc dấu, bài toán cực tiểu… Mỗi loại bài tập sẽ có những điểm khác biệt nhỏ ở bước chuyển đổi dạng chuẩn và cách đọc hàng đánh giá.

Ngoài các bài tập cơ bản, bạn có thể tìm kiếm các bài tập phương pháp đơn hình có lời giải nâng cao hơn, ví dụ như các bài toán có nhiều phương án tối ưu, bài toán suy biến, hoặc các bài toán thực tế phức tạp hơn.

Nguồn tài liệu để luyện tập rất đa dạng:

• Sách giáo khoa/giáo trình Vận trù học hoặc Quy hoạch tuyến tính.
• Các trang web chuyên ngành về Toán ứng dụng, Vận trù học.
• Các bài giảng online.

Đừng ngần ngại thử sức với nhiều dạng bài khác nhau. Ban đầu có thể chậm, có thể sai, nhưng dần dần bạn sẽ làm quen và tốc độ, độ chính xác sẽ tăng lên đáng kể. Giống như khi bạn mới bắt đầu viết báo cáo thực tập hay tiểu luận quản trị nguồn nhân lực, lần đầu tiên sẽ mất nhiều thời gian và công sức, nhưng càng làm nhiều, bạn càng thành thạo.

Hãy coi việc giải bài tập phương pháp đơn hình có lời giải như một cuộc phiêu lưu khám phá thế giới tối ưu hóa. Mỗi bài tập giải được là một “chiến công” nhỏ, giúp bạn tiến gần hơn đến việc làm chủ công cụ mạnh mẽ này.

Kết bài

Chúng ta đã cùng nhau đi qua một hành trình khá chi tiết để “giải mã” bài tập phương pháp đơn hình có lời giải. Từ việc hiểu bản chất của phương pháp, các bước thực hiện, đến việc thực hành qua một ví dụ cụ thể và điểm qua những lưu ý quan trọng.

Phương pháp đơn hình không phải là một khái niệm quá phức tạp nếu bạn tiếp cận nó một cách có hệ thống và kiên trì. Nó là một kỹ năng nền tảng không chỉ trong Toán ứng dụng, Kinh tế lượng, Vận trù học mà còn hữu ích trong nhiều lĩnh vực khác của đời sống. Việc thành thạo nó thông qua việc luyện tập bài tập phương pháp đơn hình có lời giải sẽ trang bị cho bạn một công cụ mạnh mẽ để tư duy và giải quyết vấn đề một cách logic và hiệu quả.

Hãy bắt đầu ngay hôm nay với những bài tập cơ bản, sau đó dần nâng cao độ khó. Đừng sợ sai, quan trọng là bạn học được gì từ những sai lầm đó. Nếu bạn gặp khó khăn, hãy xem lại các bước, đối chiếu với lời giải, và cố gắng hiểu tại sao cách giải lại đi theo hướng đó.

Chúc bạn thành công trên con đường chinh phục phương pháp đơn hình! Hãy thử sức và chia sẻ trải nghiệm của bạn với chúng tôi nhé.