Phương Pháp Đơn Hình: Cơ Sở và Thuật Toán Trong Quy Hoạch Tuyến Tính

Trong lĩnh vực vận trù học và kinh tế, quy hoạch tuyến tính (Linear Programming) đóng vai trò nền tảng để giải quyết các bài toán tối ưu hóa phức… 54 trang.

• Đề tài: Phương Pháp Đơn Hình Trong Quy Hoạch Tuyến Tính

Mục lục chi tiết

• 2. CHƯƠNG 2: PHƯƠNG PHÁP ĐƠN HÌNH
• 2.1. Cơ sở của phương pháp
• 2.1.1. Tính chất
• 2.1.2. Tiêu chuẩn tối ưu
• 2.2. Thuật toán đơn hình
• 2.3. Thuật toán đơn hình mở rộng

Tóm tắt

I. Khám Phá Phương Pháp Đơn Hình Chìa Khóa Tối Ưu Hóa Vận Hành

Trong lĩnh vực vận trù học và kinh tế, quy hoạch tuyến tính (Linear Programming) đóng vai trò nền tảng để giải quyết các bài toán tối ưu hóa phức tạp. Từ việc phân bổ nguồn lực, lập kế hoạch sản xuất đến quản lý chuỗi cung ứng, mục tiêu chung là tối đa hóa lợi nhuận hoặc tối thiểu hóa chi phí dưới một hệ ràng buộc nhất định. Tuy nhiên, khi số lượng biến và ràng buộc tăng lên, việc tìm kiếm phương án tối ưu trở nên vô cùng thách thức. Đây là lúc Phương pháp Đơn hình (Simplex Method), một công cụ thuật toán mạnh mẽ, thể hiện giá trị vượt trội. Được phát triển bởi George Dantzig vào năm 1947, phương pháp này cung cấp một quy trình lặp đi lặp lại có hệ thống để di chuyển dọc theo các đỉnh của miền chấp nhận được (feasible region) và hội tụ về nghiệm tối ưu. Cốt lõi của phương pháp nằm ở việc xây dựng và biến đổi bảng đơn hình, một ma trận chứa đựng toàn bộ thông tin của bài toán. Bằng cách kiểm tra các tiêu chuẩn tối ưu ở mỗi bước, thuật toán đơn hình đảm bảo rằng giá trị của hàm mục tiêu luôn được cải thiện cho đến khi không thể tốt hơn được nữa. Bài viết này sẽ phân tích sâu về cơ sở lý thuyết, các bước triển khai chi tiết và những ứng dụng thực tiễn của phương pháp mang tính cách mạng này, giúp người đọc nắm vững một trong những công cụ quan trọng nhất của toán học ứng dụng.

1.1. Giới thiệu tổng quan về bài toán quy hoạch tuyến tính

Một bài toán quy hoạch tuyến tính là bài toán tìm giá trị lớn nhất hoặc nhỏ nhất của một hàm tuyến tính, gọi là hàm mục tiêu, với các biến số phải thỏa mãn một hệ các phương trình hoặc bất phương trình tuyến tính, gọi là hệ ràng buộc. Mọi bài toán trong lĩnh vực này đều có ba thành phần cơ bản: các biến quyết định (decision variables), hàm mục tiêu, và các ràng buộc. Ví dụ, trong sản xuất, biến quyết định có thể là số lượng sản phẩm cần sản xuất, hàm mục tiêu là tổng lợi nhuận, và ràng buộc là giới hạn về nguyên vật liệu, nhân công và thời gian. Điều kiện quan trọng là tất cả các biến quyết định phải không âm. Mục tiêu của việc giải bài toán là tìm ra một bộ giá trị cho các biến này sao cho hàm mục tiêu đạt giá trị tối ưu (lớn nhất hoặc nhỏ nhất) mà không vi phạm bất kỳ ràng buộc nào. Tập hợp tất cả các phương án thỏa mãn hệ ràng buộc được gọi là miền chấp nhận được. Theo lý thuyết, nếu một phương án tối ưu tồn tại, nó phải nằm ở một trong các đỉnh của miền này.

1.2. Vai trò và tầm quan trọng của Simplex Method trong tối ưu hóa

Trước khi Simplex Method ra đời, việc giải các bài toán quy hoạch tuyến tính quy mô lớn gần như là bất khả thi. Phương pháp đồ thị chỉ hiệu quả với hai biến, trong khi các phương pháp đại số khác trở nên cồng kềnh và thiếu hiệu quả. Thuật toán đơn hình đã tạo ra một cuộc cách mạng bằng cách cung cấp một quy trình lặp có cấu trúc, hiệu quả và đảm bảo tìm ra lời giải tối ưu (nếu có tồn tại) sau một số hữu hạn bước. Tầm quan trọng của nó không chỉ nằm ở khía cạnh học thuật mà còn ở khả năng ứng dụng rộng rãi trong thực tế. Các ngành công nghiệp từ vận tải, tài chính, sản xuất đến viễn thông đều sử dụng các biến thể của thuật toán này để tối ưu hóa hoạt động, tiết kiệm hàng tỷ đô la chi phí và nâng cao hiệu quả cạnh tranh. Nó là nền tảng cho nhiều phần mềm tối ưu hóa thương mại và là công cụ không thể thiếu cho các nhà phân tích, kỹ sư và nhà quản lý trong việc ra quyết định dựa trên dữ liệu.

II. Thách Thức Khi Tìm Phương Án Tối Ưu Trong Quy Hoạch Tuyến Tính

Việc giải một bài toán tối ưu hóa không đơn giản là tìm một lời giải bất kỳ, mà là tìm lời giải tốt nhất trong số vô số các khả năng. Thách thức lớn nhất trong quy hoạch tuyến tính nằm ở việc xác định và đánh giá các phương án một cách có hệ thống. Khi bài toán có nhiều biến, không gian lời giải trở thành một khối đa diện đa chiều phức tạp, và miền chấp nhận được có thể chứa vô số điểm. Lý thuyết nền tảng cho biết "nếu bài toán có phương án tối ưu thì cũng có phương án cơ bản tối ưu", và "số phương án cơ bản là hữu hạn". Điều này cho phép chúng ta giới hạn việc tìm kiếm trong một tập hợp hữu hạn các điểm đỉnh của miền chấp nhận. Tuy nhiên, việc liệt kê và kiểm tra tất cả các phương án cơ bản là không khả thi đối với các bài toán lớn. Do đó, cần một thuật toán thông minh có thể di chuyển từ một phương án cơ bản này đến một phương án cơ bản khác tốt hơn mà không cần phải duyệt qua toàn bộ không gian. Phương pháp Đơn hình giải quyết chính xác thách thức này bằng cách cung cấp một "tiêu chuẩn tối ưu" để đánh giá phương án hiện tại và một quy tắc để chuyển sang phương án kề cận có khả năng cải thiện hàm mục tiêu tốt hơn.

2.1. Phân biệt các dạng bài toán Dạng tổng quát dạng chính tắc và dạng chuẩn

Để áp dụng thuật toán đơn hình, trước hết cần đưa bài toán về một dạng cấu trúc cụ thể. Một bài toán quy hoạch tuyến tính có thể tồn tại ở ba dạng chính. Dạng tổng quát là dạng tự nhiên nhất, có thể bao gồm các ràng buộc bất phương trình (≤, ≥) và phương trình (=), cùng các biến có thể âm hoặc không âm. Dạng chính tắc yêu cầu tất cả các ràng buộc phải là phương trình và tất cả các biến phải không âm. Để chuyển từ dạng tổng quát sang dạng chính tắc, người ta thường sử dụng biến bù (slack variable) hoặc biến thặng dư (surplus variable). Cuối cùng, dạng chuẩn là một trường hợp đặc biệt của dạng chính tắc, trong đó hệ phương trình ràng buộc đã có sẵn một hệ cơ sở đơn vị. Đây là dạng xuất phát lý tưởng cho Simplex Method. Việc hiểu rõ cách chuyển đổi giữa các dạng này là bước đầu tiên và cơ bản để chuẩn bị dữ liệu đầu vào cho quá trình giải toán.

2.2. Khái niệm về biến cơ sở và biến không cơ sở trong không gian nghiệm

Trong một hệ phương trình tuyến tính có nhiều biến hơn số phương trình, ta có thể chọn ra một tập hợp các biến và biểu diễn chúng thông qua các biến còn lại. Trong quy hoạch tuyến tính, các biến được chọn này được gọi là biến cơ sở (basic variables), và các biến còn lại được gọi là biến không cơ sở (non-basic variables). Tại một phương án cơ bản, các biến không cơ sở được gán giá trị bằng 0, và giá trị của các biến cơ sở được xác định duy nhất từ hệ phương trình ràng buộc. Mỗi phương án cơ bản tương ứng với một đỉnh của miền chấp nhận được. Thuật toán đơn hình hoạt động bằng cách hoán đổi vai trò giữa một biến cơ sở và một biến không cơ sở ở mỗi bước lặp. Việc lựa chọn biến nào từ tập không cơ sở để "đưa vào" cơ sở và biến nào từ cơ sở để "đưa ra" là quyết định cốt lõi của thuật toán, dựa trên các tiêu chí tính toán từ bảng đơn hình.

III. Hướng Dẫn Thuật Toán Đơn Hình Tối Ưu Hóa Từng Bước Một

Cốt lõi của Phương pháp Đơn hình là một quy trình lặp gồm các bước được xác định rõ ràng, bắt đầu từ một phương án cơ bản ban đầu và liên tục cải thiện nó cho đến khi đạt được phương án tối ưu. Quá trình này được thực hiện trên một công cụ gọi là bảng đơn hình. Bảng này tóm tắt tất cả thông tin cần thiết: các biến cơ sở, hệ số của các biến trong hệ ràng buộc, giá trị của phương án hiện tại và giá trị của hàm mục tiêu. Bước quan trọng nhất là tính toán các giá trị ước lượng, ký hiệu là ∆j (delta j). Các giá trị này cho biết mức độ thay đổi của hàm mục tiêu nếu một biến không cơ sở tương ứng được đưa vào cơ sở. Dựa trên dấu của các ∆j, thuật toán sẽ quyết định: (1) Phương án hiện tại đã là tối ưu hay chưa; (2) Bài toán có lời giải vô hạn hay không; hoặc (3) Cần thực hiện một bước lặp nữa để cải thiện lời giải. Tài liệu nghiên cứu chỉ rõ: "Nếu △j ≤ 0 (với bài toán min) hoặc △j ≥ 0 (với bài toán max) với mọi j, thì phương án cơ bản đang xét là phương án tối ưu". Nếu điều kiện này chưa thỏa mãn, thuật toán sẽ tiến hành chọn biến vào, biến ra và cập nhật lại bảng.

3.1. Quy trình 5 bước cốt lõi của thuật toán đơn hình cơ bản

Thuật toán đơn hình có thể được tóm gọn trong 5 bước lặp đi lặp lại. Bước 1: Lập bảng đơn hình ban đầu từ bài toán đã được đưa về dạng chuẩn. Bước 2: Kiểm tra tính tối ưu. Tính các ước lượng ∆j. Nếu tất cả các ∆j thỏa mãn điều kiện tối ưu (ví dụ, ≤ 0 cho bài toán min), dừng lại, phương án hiện tại là tối ưu. Ngược lại, chuyển sang bước 3. Bước 3: Tìm ẩn đưa vào. Chọn biến không cơ sở có ∆j vi phạm điều kiện tối ưu nhiều nhất (ví dụ, ∆j > 0 lớn nhất cho bài toán min) để đưa vào cơ sở. Bước 4: Tìm ẩn đưa ra. Tính tỷ số λ giữa vế phải và các hệ số dương trong cột của biến đưa vào. Chọn biến cơ sở ứng với tỷ số λ nhỏ nhất để đưa ra khỏi cơ sở. Phần tử nằm ở giao của cột đưa vào và hàng đưa ra được gọi là phần tử trục xoay. Bước 5: Biến đổi bảng. Sử dụng các phép biến đổi hàng sơ cấp (tương tự phép khử Gauss) để tạo bảng đơn hình mới, với cơ sở mới. Sau đó, quay trở lại Bước 2.

3.2. Cách xác định phần tử trục xoay và biến đổi bảng đơn hình

Việc biến đổi bảng đơn hình là trái tim của mỗi bước lặp. Sau khi xác định được biến đưa vào (cột chủ yếu) và biến đưa ra (hàng chủ yếu), phần tử trục xoay sẽ là phần tử nằm ở giao điểm của chúng. Quá trình biến đổi bảng, hay còn gọi là phép xoay, nhằm mục đích đưa biến mới vào cơ sở và loại biến cũ ra. Đầu tiên, hàng chủ yếu mới được tính bằng cách chia hàng chủ yếu cũ cho phần tử trục xoay. Tiếp theo, các hàng còn lại (bao gồm cả hàng hàm mục tiêu) được cập nhật. Hàng mới được tính bằng cách lấy hàng cũ trừ đi tích của hệ số tương ứng trong cột chủ yếu với hàng chủ yếu mới. Mục tiêu của phép biến đổi này là làm cho cột chủ yếu trong bảng mới trở thành một vector đơn vị, tương ứng với việc biến được chọn đã trở thành một biến cơ sở. Quá trình này đảm bảo rằng các ràng buộc vẫn được thỏa mãn và phương án mới vẫn là một phương án cơ bản.

IV. Bí Quyết Xử Lý Bài Toán Phức Tạp Phương Pháp M Lớn Hai Pha

Không phải lúc nào một bài toán quy hoạch tuyến tính cũng ở dạng chuẩn với một hệ cơ sở đơn vị sẵn có. Nhiều bài toán thực tế có các ràng buộc dạng '≥' hoặc '=', dẫn đến việc không thể tìm thấy một phương án cơ bản ban đầu một cách dễ dàng. Để giải quyết vấn đề này, các kỹ thuật mở rộng của thuật toán đơn hình đã được phát triển, tiêu biểu là phương pháp M lớn (Big M Method) và phương pháp hai pha (Two-Phase Method). Cả hai phương pháp này đều dựa trên ý tưởng thêm vào bài toán các biến nhân tạo, gọi là biến giả (artificial variables). Các biến này tạm thời đóng vai trò như các biến cơ sở ban đầu, giúp khởi tạo bảng đơn hình đầu tiên. Mục tiêu sau đó là loại bỏ tất cả các biến giả này ra khỏi cơ sở để tìm được một phương án cơ bản khả thi cho bài toán gốc. Theo tài liệu, "nếu bài toán mở rộng có phương án tối ưu mà trong đó, còn ít nhất một ẩn giả dương, thì bài toán xuất phát không có phương án". Ngược lại, nếu tất cả các biến giả đều bằng 0 trong nghiệm tối ưu, ta đã tìm được lời giải cho bài toán ban đầu.

4.1. Kỹ thuật sử dụng biến giả để khởi tạo thuật toán đơn hình

Khi một ràng buộc có dạng '≥' hoặc '=', ta không thể dùng biến bù để tạo thành một vector đơn vị trong ma trận. Thay vào đó, một biến giả được cộng vào vế trái của các phương trình này. Các biến giả này không có ý nghĩa thực tế, chúng chỉ là công cụ toán học để tạo ra một ma trận đơn vị ban đầu, cho phép thuật toán đơn hình bắt đầu. Tuy nhiên, sự tồn tại của các biến giả trong phương án cuối cùng sẽ vi phạm các ràng buộc gốc. Do đó, cần phải tìm cách loại bỏ chúng. Cả phương pháp M lớn và phương pháp hai pha đều được thiết kế để thực hiện nhiệm vụ này một cách hiệu quả, đảm bảo rằng lời giải cuối cùng là một phương án khả thi cho bài toán gốc.

4.2. So sánh phương pháp M lớn và phương pháp hai pha trong thực tế

Phương pháp M lớn hoạt động bằng cách đưa các biến giả vào hàm mục tiêu với một hệ số phạt rất lớn, ký hiệu là M. Đối với bài toán tối thiểu hóa, ta cộng 'M' lần tổng các biến giả vào hàm mục tiêu; đối với bài toán tối đa hóa, ta trừ đi. Do M là một số rất lớn, thuật toán sẽ tự động ưu tiên loại bỏ các biến giả ra khỏi cơ sở để giảm thiểu (hoặc tối đa hóa) hàm mục tiêu. Ưu điểm của phương pháp này là chỉ cần giải một bài toán duy nhất. Nhược điểm là có thể gây ra lỗi số học do M quá lớn. Ngược lại, phương pháp hai pha chia bài toán thành hai giai đoạn. Pha 1 tập trung hoàn toàn vào việc tối thiểu hóa tổng các biến giả. Nếu giá trị tối thiểu này bằng 0, nghĩa là đã tìm được một phương án cơ bản khả thi cho bài toán gốc và ta chuyển sang Pha 2. Ở Pha 2, ta loại bỏ các biến giả và giải bài toán gốc bằng hàm mục tiêu ban đầu. Phương pháp này ổn định hơn về mặt số học nhưng đòi hỏi phải thực hiện hai quy trình tối ưu hóa riêng biệt.

V. Ứng Dụng Phương Pháp Đơn Hình Từ Lý Thuyết Đến Giải Pháp Kinh Tế

Phương pháp Đơn hình không chỉ là một công cụ lý thuyết mà còn là nền tảng cho vô số ứng dụng thực tiễn nhằm giải quyết các bài toán tối ưu hóa trong kinh doanh và kỹ thuật. Khả năng tìm kiếm phương án tối ưu một cách hiệu quả giúp các tổ chức đưa ra quyết định thông minh hơn, dẫn đến tối đa hóa lợi nhuận và tối thiểu hóa chi phí. Ví dụ, trong ngành sản xuất, một công ty có thể sử dụng quy hoạch tuyến tính để xác định số lượng mỗi loại sản phẩm cần sản xuất để đạt lợi nhuận cao nhất, với các ràng buộc về nguồn nguyên liệu, giờ công lao động và công suất máy móc. Trong lĩnh vực tài chính, các nhà đầu tư có thể xây dựng một danh mục đầu tư tối ưu, cân bằng giữa rủi ro và lợi nhuận kỳ vọng. Một khái niệm quan trọng liên quan đến ứng dụng là bài toán đối ngẫu (dual problem). Mỗi bài toán quy hoạch tuyến tính (bài toán gốc) đều có một bài toán đối ngẫu tương ứng. Lời giải của bài toán đối ngẫu cung cấp những thông tin kinh tế vô cùng giá trị, chẳng hạn như giá trị bóng (shadow price) của mỗi nguồn lực, cho biết lợi nhuận sẽ tăng thêm bao nhiêu nếu có thêm một đơn vị nguồn lực đó.

5.1. Case study Tối ưu hóa sản xuất và phân bổ nguồn lực

Xét một nhà máy sản xuất hai loại sản phẩm A và B. Mỗi sản phẩm đòi hỏi thời gian xử lý trên ba máy khác nhau và mang lại một mức lợi nhuận nhất định. Nhà máy có giới hạn về tổng thời gian hoạt động của mỗi máy. Bài toán tối ưu hóa ở đây là: cần sản xuất bao nhiêu sản phẩm A và bao nhiêu sản phẩm B để tổng lợi nhuận là lớn nhất? Bằng cách thiết lập hàm mục tiêu là hàm tổng lợi nhuận và hệ ràng buộc là các bất phương trình về thời gian máy, ta có thể áp dụng thuật toán đơn hình. Bảng đơn hình sẽ giúp tìm ra phương án tối ưu, ví dụ: sản xuất 50 sản phẩm A và 70 sản phẩm B. Lời giải này không chỉ cho biết con số cụ thể mà còn chỉ ra máy nào đang được sử dụng hết công suất, là nút thắt cổ chai của quy trình sản xuất.

5.2. Giải quyết bài toán vận tải và logistics với Simplex Method

Bài toán vận tải là một ứng dụng kinh điển của quy hoạch tuyến tính. Một công ty có nhiều nhà máy và nhiều kho hàng. Chi phí vận chuyển một đơn vị sản phẩm từ mỗi nhà máy đến mỗi kho hàng là khác nhau. Mỗi nhà máy có một năng lực sản xuất nhất định và mỗi kho hàng có một nhu cầu cụ thể. Mục tiêu là xác định kế hoạch vận chuyển (số lượng sản phẩm chuyển từ nhà máy i đến kho j) sao cho tổng chi phí vận chuyển là nhỏ nhất mà vẫn đáp ứng đủ nhu cầu của tất cả các kho hàng. Phương pháp Đơn hình và các biến thể chuyên dụng của nó (như thuật toán vận tải) có thể giải quyết hiệu quả bài toán này, giúp các công ty logistics tiết kiệm chi phí đáng kể, tối ưu hóa lộ trình và đảm bảo hàng hóa được phân phối kịp thời, góp phần vào việc tối thiểu hóa chi phí hoạt động tổng thể.

Nội dung chính

Báo Cáo Phân Loại Và Tổng Quan Học Thuật: Giáo Trình Phương Pháp Đơn Hình Trong Quy Hoạch Tuyến Tính

---

Tổng quan về giáo trình

Tài liệu "Chương 2: Phương pháp đơn hình" là một phần trong hệ thống học liệu thuộc Chương trình đào tạo trực tuyến, phục vụ cho học phần Quy hoạch tuyến tính hoặc Tối ưu hóa tại bậc đại học. Trong cấu trúc chương trình đào tạo của các khối ngành Toán ứng dụng, Khoa học máy tính, Hệ thống thông tin quản lý, Kinh tế học và Quản lý công nghiệp, Quy hoạch tuyến tính giữ vị trí nền tảng, cung cấp cơ sở toán học để giải quyết các bài toán phân bổ nguồn lực và tối ưu hóa hệ thống.

Mục tiêu học tập của tài liệu tập trung vào việc trang bị cho người học:

• Cơ sở lý thuyết về không gian nghiệm của bài toán quy hoạch tuyến tính dạng chuẩn.
• Năng lực giải thích và vận dụng các điều kiện tối ưu thông qua hệ thống ước lượng $\Delta_j$.
• Kỹ năng thực hiện quy trình lặp của thuật toán đơn hình tiêu chuẩn và thuật toán đơn hình mở rộng (phương pháp Big-M) trên bảng tính toán ma trận.
• Khả năng biện luận các trường hợp nghiệm của bài toán: phương án tối ưu duy nhất, hàm mục tiêu không bị chặn, hoặc bài toán không có phương án khả thi.

Tài liệu được biên soạn theo cấu trúc tuyến tính chặt chẽ, đi từ việc thiết lập các tiền đề toán học, phân tích cấu trúc của phương án cơ bản, xác lập tiêu chuẩn tối ưu, đến việc mô hình hóa các bước lặp và minh họa cụ thể qua các ví dụ tính toán số học chi tiết.

---

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung tài liệu được cấu trúc thành ba phần chính, tiếp nối các kiến thức thiết lập bài toán từ Chương 1:

1. Cơ sở của phương pháp (Mục I)

• Tính chất của tập nghiệm: Tài liệu xác lập các nguyên lý cơ bản: nếu bài toán có phương án tối ưu (PATƯ) thì cũng có phương án cơ bản (PACB) tối ưu; số lượng PACB của bài toán là hữu hạn; điều kiện cần và đủ để bài toán có PATƯ là hàm mục tiêu bị chặn dưới đối với bài toán tìm giá trị nhỏ nhất ($f(x) \to \min$) hoặc bị chặn trên đối với bài toán tìm giá trị lớn nhất ($f(x) \to \max$).
• Xác lập ước lượng và tiêu chuẩn tối ưu: Từ một PACB ban đầu $x^0 = (b_1, \dots, b_m, 0, \dots, 0)$ với giá trị hàm mục tiêu $f_0 = \sum_{i=1}^m c_i b_i$, hệ số ước lượng cho mỗi ẩn $x_j$ được xác định theo công thức: $$\Delta_j = \sum_{i=1}^m c_i a_{ij} - c_j$$ Mối liên hệ giữa giá trị hàm mục tiêu của một phương án bất kỳ $x$ và phương án $x^0$ được thiết lập qua đẳng thức: $$f(x) = f_0 - \sum_{j=m+1}^n \Delta_j x_j$$
• Nguyên tắc chuyển cơ sở: Nếu tồn tại $\Delta_j > 0$ (với bài toán Min), việc đưa biến $x_j$ vào cơ sở sẽ làm giảm giá trị hàm mục tiêu một lượng tỷ lệ với $\Delta_j$. Việc chuyển từ PACB này sang PACB khác được thực hiện bằng phép biến đổi khử Gauss.

2. Thuật toán đơn hình tiêu chuẩn (Mục II)

Quy trình thuật toán đơn hình cho bài toán dạng chuẩn $f(x) \to \min$ được chuẩn hóa thành 5 bước:

• Bước 1 (Lập bảng ban đầu): Thiết lập ma trận bảng đơn hình gồm các hàng hệ số hàm mục tiêu $c_j$, cột hệ số cơ bản $c_i$, cột ẩn cơ bản, cột phương án $b_i$, ma trận hệ số ràng buộc $a_{ij}$, cột tỷ số $\lambda_i$, và hàng cuối chứa giá trị hàm mục tiêu $f_0$ cùng các ước lượng $\Delta_j$.
• Bước 2 (Kiểm tra tính tối ưu):
  • Nếu $\Delta_j \le 0, \forall j$: Phương án đang xét là PATƯ.
  • Nếu tồn tại $\Delta_j > 0$ mà hệ số $a_{ij} \le 0, \forall i = 1, \dots, m$: Hàm mục tiêu không bị chặn, bài toán không có PATƯ.
• Bước 3 (Tìm ẩn đưa vào): Chọn ẩn $x_v$ ứng với $\Delta_v = \max {\Delta_j > 0}$ để làm cột chủ yếu (cột xoay).
• Bước 4 (Tìm ẩn đưa ra): Tính tỷ số $\lambda_i = \frac{b_i}{a_{iv}}$ với các điều kiện $a_{iv} > 0$. Ẩn $x_r$ tương ứng với $\lambda_r = \min {\lambda_i}$ được chọn đưa ra khỏi cơ sở. Hàng $r$ là hàng chủ yếu và phần tử $a_{rv}$ là phần tử trục xoay.
• Bước 5 (Biến đổi bảng): Cập nhật hệ ẩn cơ bản và ma trận theo phép biến đổi dòng:
  • Hàng $r$ mới (hàng chuẩn): $\text{Hàng } r \text{ mới} = \frac{\text{Hàng } r \text{ cũ}}{a_{rv}}$.
  • Các hàng $i$ khác ($i \neq r$): $\text{Hàng } i \text{ mới} = \text{Hàng } i \text{ cũ} - a_{iv} \times (\text{Hàng chuẩn})$.
  • Hàng ước lượng cuối: $\text{Hàng cuối mới} = \text{Hàng cuối cũ} - \Delta_v \times (\text{Hàng chuẩn})$.
• Điều chỉnh cho bài toán tìm cực đại ($f(x) \to \max$): Điều kiện tối ưu đổi thành $\Delta_j \ge 0, \forall j$; bài toán không có PATƯ khi tồn tại $\Delta_j < 0$ với mọi $a_{ij} \le 0$; biến đưa vào được chọn theo $\Delta_v = \min {\Delta_j < 0}$.

3. Thuật toán đơn hình mở rộng (Mục III)

Áp dụng cho các bài toán dạng chính tắc chưa có sẵn ma trận đơn vị để thiết lập PACB ban đầu:

• Kỹ thuật thêm ẩn giả: Đưa các ẩn giả $x_{n+k} \ge 0$ vào hệ ràng buộc và gán hệ số phạt $M$ (với $M$ là đại lượng dương vô cùng lớn) vào hàm mục tiêu: $+M x_{n+k}$ đối với bài toán Min.
• Tách dòng ước lượng: Dòng cuối của bảng đơn hình được phân tách thành 2 dòng nhỏ: dòng trên ghi phần giá trị không phụ thuộc vào $M$, dòng dưới ghi hệ số của $M$. Khi xét dấu và so sánh các $\Delta_j$, thứ tự ưu tiên được thực hiện trên dòng hệ số của $M$; chỉ khi hệ số của $M$ triệt tiêu (bằng 0) mới xét đến dòng không phụ thuộc $M$.
• Biện luận nghiệm bài toán gốc:
  1. Nếu bài toán mở rộng không có PATƯ thì bài toán gốc không có PATƯ.
  2. Nếu bài toán mở rộng có PATƯ với tất cả ẩn giả đều bằng 0, việc loại bỏ các ẩn giả cho ra PATƯ của bài toán gốc.
  3. Nếu bài toán mở rộng có PATƯ nhưng vẫn còn ít nhất một ẩn giả mang giá trị dương, bài toán xuất phát vô nghiệm (không có phương án khả thi).

---

Kiến thức nền tảng được xây dựng

Tài liệu củng cố và vận dụng các mảng lý thuyết đại số tuyến tính:

• Không gian vectơ và hệ vectơ trực giao/đơn vị trong việc biểu diễn cơ sở $\mathbb{R}^m$.
• Kỹ thuật biến đổi sơ cấp trên dòng của ma trận tương đương với phép khử Gauss-Jordan.
• Tính lồi của tập phương án và nguyên lý nghiệm tối ưu luôn đạt tại các điểm cực biên (đỉnh của đa diện lồi).

---

Kỹ năng phát triển

Thông qua việc nghiên cứu giáo trình, người học xây dựng các kỹ năng cụ thể:

• Kỹ năng đại số hóa và chuẩn hóa: Chuyển đổi các hệ bất phương trình ràng buộc sang dạng phương trình bằng việc thêm ẩn phụ, ẩn bù hoặc ẩn giả.
• Kỹ năng thao tác bảng tính ma trận: Thực hiện chuẩn xác các phép tính số học trên phân số trong quá trình xoay bảng đơn hình.
• Kỹ năng phân tích và chẩn đoán trạng thái bài toán: Nhận diện sớm dấu hiệu không bị chặn của hàm mục tiêu hoặc tính vô nghiệm của hệ ràng buộc thông qua cấu trúc dấu của các vectơ cột trong bảng đơn hình.

---

Phương pháp giảng dạy và học tập

Tài liệu áp dụng phương pháp sư phạm tiếp cận theo quy trình thuật toán tuần tự (Algorithmic Approach), kết hợp lý giải cơ sở toán học với các bước thực thi dạng bảng:

Hệ thống ví dụ minh họa trong tài liệu

Tài liệu tích hợp hệ thống bài tập mẫu tương ứng với các tình huống toán học khác nhau:

1. Ví dụ dạng chuẩn đạt tối ưu tại bảng 1: Bài toán $f(x) = 2x_1 + 5x_2 + 4x_3 + x_4 - 5x_5 \to \min$ với việc bổ sung ẩn phụ $x_6$, qua đó kiểm tra nhanh điều kiện $\Delta_j \le 0, \forall j$ để kết luận nghiệm $x = (32, 0, 30, 0, 0)$ và $f(x) = 184$.
2. Ví dụ bài toán không có PATƯ: Bài toán tìm Min có $b_2 = -9 < 0$, thực hiện nhân đổi dấu để đưa về dạng chuẩn, sau một bước lặp phát hiện $\Delta_4 = 1 > 0$ nhưng $a_{i4} \le 0, \forall i$, kết luận hàm mục tiêu không bị chặn dưới.
3. Ví dụ bài toán Max qua nhiều bước lặp: Bài toán $f(x) = -2x_1 + 6x_2 + 4x_3 - 2x_4 + 3x_5 \to \max$, trải qua 2 vòng đổi cơ sở (thay $x_1$ bằng $x_3$, sau đó thay $x_4$ bằng $x_2$) để đạt PATƯ $x = (0, 34/3, 22/3, 0, 2)$ với $f(x) = 310/3$.
4. Hệ thống ví dụ thuật toán mở rộng (Big-M):
   • Trường hợp bài toán mở rộng không có PATƯ do cột âm ($\Delta_5 = 2/3 > 0, a_{i5} < 0, \forall i$).
   • Trường hợp bài toán mở rộng tìm được nghiệm và các biến giả bị loại hoàn toàn ($x_4 = 0$), thu được nghiệm của bài toán xuất phát $x = (0, 7/5, 4/5)$ với $f(x) = 17$.
   • Trường hợp bài toán hỗn hợp ràng buộc gồm phương trình và bất phương trình, yêu cầu kết hợp cả ẩn phụ ($x_4$) và hai ẩn giả ($x_5, x_6$).

Hướng dẫn tự học và đánh giá

Người học được khuyến nghị thực hiện việc tính toán bảng đơn hình thủ công từng bước, so sánh hệ số dòng cuối $\Delta_j$ với công thức độc lập để kiểm tra sai số tính toán, đồng thời nắm vững nguyên tắc lựa chọn phần tử trục xoay qua quy tắc tìm $\min \lambda_i$.

---

Điểm nổi bật và cập nhật

• Quy chuẩn hóa cấu trúc bảng đơn hình: Bảng tính được thiết kế rõ ràng với đầy đủ các cột hệ số $c_j$, ẩn cơ bản, cột phương án $b_i$ và cột kiểm tra $\lambda_i$, giúp giảm thiểu việc nhầm lẫn chỉ số trong quá trình biến đổi ma trận.
• Kỹ thuật tách hai dòng cho tham số $M$: Thay vì gán cho $M$ một giá trị số thực lớn cụ thể (dễ gây lỗi làm tròn số), giáo trình hướng dẫn tách dòng cuối thành hai thành phần đại số riêng biệt: dòng độc lập và dòng hệ số chứa $M$. Kỹ thuật này giúp việc kiểm tra tính tối ưu và chọn cột xoay đạt độ chính xác giải tích tuyệt đối.
• Quy tắc loại bỏ ẩn giả: Hướng dẫn chi tiết việc không cần ghi lại các cột ứng với ẩn giả sau khi chúng đã bị đưa ra khỏi hệ ẩn cơ bản, giúp tinh giản kích thước của bảng đơn hình ở các bước lặp sau.

---

Đối tượng sử dụng giáo trình

• Sinh viên đại học: Thuộc các ngành Toán học, Toán tin ứng dụng, Khoa học dữ liệu, Kỹ thuật công nghiệp, Quản trị kinh doanh, Kinh tế đầu tư và Thương mại điện tử đang theo học học phần Quy hoạch tuyến tính hoặc Vận trù học (Operations Research).
• Kiến thức tiên quyết: Người học cần có kiến thức nền tảng về Đại số tuyến tính, bao gồm: giải hệ phương trình đại số tuyến tính, phép biến đổi ma trận sơ cấp, tính định thức và hạng của ma trận.
• Giảng viên và nhà nghiên cứu: Tài liệu cung cấp cấu trúc nội dung chuẩn xác để biên soạn bài giảng trực tuyến (E-learning), xây dựng đề thi và bài tập đánh giá quá trình.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu phục vụ sinh viên và người học ở bậc đại học đang theo học các chương trình đào tạo chính quy hoặc từ xa trong các ngành kỹ thuật, kinh tế và công nghệ thông tin cần nắm vững phương pháp giải thuật toán tối ưu hóa tuyến tính.

2. Cần kiến thức nền nào để học?

Người học cần hoàn thành môn Đại số tuyến tính, nắm vững phép toán trên ma trận, kỹ thuật khử Gauss-Jordan và các khái niệm cơ bản về hình học giải tích đa chiều.

3. Điểm khác biệt của tài liệu so với các bài giảng khác?

Tài liệu cung cấp quy tắc xử lý bảng toán học chi tiết đối với phương pháp Big-M bằng cách phân tách rõ ràng dòng tham số $M$, đồng thời bao quát đầy đủ các tình huống suy biến và kết thúc thuật toán (tối ưu, không bị chặn, vô nghiệm) thông qua các bài tập số học cụ thể.

4. Làm sao để tự học nội dung này hiệu quả?

Người học nên tự vẽ lại bảng đơn hình, thực hiện các phép biến đổi dòng độc lập trước khi đối chiếu kết quả từng bảng trong tài liệu; chú ý kiểm tra điều kiện của phần tử trục xoay $a_{rv} > 0$ khi tính tỷ số $\lambda_i$.

5. Có tài liệu bổ trợ nào kèm theo?

Tài liệu là phần tiếp nối của "Chương 1: Bài toán quy hoạch tuyến tính tổng quát và cách đưa về dạng chuẩn", và là tiền đề cho các nội dung tiếp theo về "Bài toán quy hoạch tuyến tính đối ngẫu" và "Phương pháp đơn hình đối ngẫu".

---

Kết luận

Tài liệu "Chương 2: Phương pháp đơn hình" cung cấp hệ thống lý thuyết chuẩn xác và các quy trình tính toán tường minh của thuật toán đơn hình và thuật toán đơn hình mở rộng. Nội dung văn bản xây dựng nền tảng vững chắc cho người học trong việc phân tích định lượng, giải quyết các bài toán tối ưu hóa trong mô hình hóa kinh tế và quản lý kỹ thuật. Lộ trình tiếp theo sau chương này là nghiên cứu lý thuyết đối ngẫu và phân tích độ nhạy của nghiệm tối ưu.