1. Bản chất của linear programming

Linear programming xuất phát từ nhu cầu ra quyết định trong các hệ thống có giới hạn rõ ràng. Một doanh nghiệp có thể muốn tối thiểu hóa chi phí vận chuyển. Một nhà máy có thể muốn lập kế hoạch sản xuất sao cho thỏa mãn nhu cầu theo tháng với chi phí thấp nhất. Một đơn vị vận hành hạ tầng có thể muốn chọn vị trí đặt cơ sở sao cho phục vụ được nhiều điểm nhu cầu nhất trong giới hạn ngân sách. Những bài toán này khác nhau về bối cảnh, nhưng cùng chia sẻ một cấu trúc toán học: cần tối ưu một mục tiêu tuyến tính dưới các constraint tuyến tính.

Dạng chuẩn cơ bản của một bài toán linear programming có thể viết như sau:

Ghi chú nhập CKEditor: mỗi dòng công thức được viết ở dạng \( ... \). Không dùng công thức khối và không dùng môi trường aligned.

\(\max Z = c^T x\)

\(\text{s.t. } Ax \le b\)

\(x \ge 0\)

Trong biểu thức này, \(x\) là vector biến quyết định. Vector \(c\) chứa hệ số của objective function. Ma trận \(A\) và vector \(b\) mô tả các constraint. Ký hiệu \(c^T\) là transpose của \(c\). Điều kiện \(x \ge 0\) phản ánh thực tế rằng nhiều đại lượng quyết định như số lượng sản phẩm, số chuyến vận chuyển hoặc mức đầu tư không thể nhận giá trị âm.

Miền nghiệm khả thi (feasible region) là tập tất cả các điểm thỏa mãn constraint. Với hai biến, feasible region có thể biểu diễn bằng một đa giác. Với số biến lớn hơn, feasible region trở thành một đa diện lồi trong không gian nhiều chiều. Đặc điểm quan trọng của linear programming là nghiệm tối ưu, nếu tồn tại và hữu hạn, có thể đạt tại một đỉnh của feasible region. Đây là nền tảng trực giác cho Simplex method.

Hình 1. Feasible region và hướng cải thiện của objective function

Hình 1 minh họa cách một objective function tuyến tính được dịch chuyển theo hướng cải thiện giá trị. Các đường đồng mức của objective function song song với nhau. Khi dịch chuyển đường này trong hướng tối ưu, điểm tiếp xúc cuối cùng với feasible region chính là một nghiệm tối ưu. Trực giác hình học này giải thích vì sao Simplex method không cần khảo sát toàn bộ miền nghiệm mà chỉ cần di chuyển có hệ thống qua các đỉnh liên quan.

2. Mô hình hóa bài toán tối ưu

Mô hình hóa (modeling) là bước chuyển một tình huống thực tế thành ngôn ngữ toán học. Một bài toán chỉ có thể giải bằng linear programming khi người viết mô hình xác định đúng biến, đúng mục tiêu và đúng constraint. Sai sót trong bước modeling thường dẫn đến nghiệm đúng về mặt tính toán nhưng sai về mặt nghiệp vụ.

Quy trình modeling có thể triển khai theo ba bước. Bước 1 là xác định biến quyết định, tức là đại lượng cần tìm. Bước 2 là xây dựng objective function, thể hiện tiêu chí cần tối đa hóa hoặc tối thiểu hóa. Bước 3 là thiết lập constraint dựa trên yêu cầu tài nguyên, nhu cầu, năng lực, ngân sách hoặc điều kiện kỹ thuật. Mỗi constraint cần có ý nghĩa rõ ràng và phải tương thích với đơn vị đo của biến.

Một lưu ý cơ bản là bài toán tối đa hóa và tối thiểu hóa có thể chuyển đổi qua đổi dấu objective function, tức là \(\max Z \equiv \min (-Z)\). Vì vậy, trọng tâm của modeling không nằm ở việc bài toán dùng max hay min, mà nằm ở việc objective function và constraint có biểu diễn đúng quyết định cần ra hay không.

\(\max Z \equiv \min(-Z)\)

3. Bài toán vận tải

Bài toán vận tải là ví dụ điển hình của linear programming. Giả sử có \(n\) kho hàng và \(m\) điểm nhận hàng. Chi phí vận chuyển một đơn vị sản phẩm từ kho \(i\) đến điểm nhận \(j\) là \(c_{ij}\). Năng lực cung ứng của kho \(i\) là \(P_i\). Nhu cầu của điểm nhận \(j\) là \(D_j\). Biến quyết định tự nhiên là \(x_{ij}\), biểu thị lượng hàng được vận chuyển từ kho \(i\) đến điểm nhận \(j\).

Hình 2. Mối quan hệ giữa một kho hàng và nhiều điểm nhận trong bài toán vận tải

Objective function của bài toán vận tải thường là tổng chi phí vận chuyển. Mô hình có thể viết dưới dạng:

\(\min Z = \sum_{i=1}^{n}\sum_{j=1}^{m} c_{ij}x_{ij}\)

\(\sum_{j=1}^{m} x_{ij} \le P_i,\quad i=1,\ldots,n\)

\(\sum_{i=1}^{n} x_{ij} \ge D_j,\quad j=1,\ldots,m\)

\(x_{ij} \ge 0\)

Constraint thứ nhất giới hạn tổng lượng hàng xuất từ mỗi kho theo năng lực cung ứng. Constraint thứ hai bảo đảm mỗi điểm nhận được đáp ứng đủ nhu cầu. Trong trường hợp tổng cung bằng tổng cầu, constraint nhu cầu thường được viết dưới dạng bằng. Nếu tổng cung lớn hơn tổng cầu, dạng lớn hơn hoặc bằng phù hợp khi mục tiêu là bảo đảm đủ nhu cầu và cho phép tồn kho còn lại tại nguồn.

4. Lập kế hoạch sản xuất và lựa chọn cơ sở

Một lớp bài toán khác của linear programming là lập kế hoạch sản xuất (production planning). Doanh nghiệp biết trước nhu cầu \(D_i\) trong từng tháng, có năng lực sản xuất bình thường, có lựa chọn làm thêm giờ và có chi phí lưu kho. Biến quyết định có thể gồm số lượng sản xuất trong giờ bình thường \(x_i\), số lượng sản xuất làm thêm \(o_i\) và lượng tồn kho cuối tháng \(s_i\). Objective function là tổng chi phí sản xuất, chi phí làm thêm và chi phí lưu kho trong toàn bộ kỳ kế hoạch.

\(\min Z = \sum_{i=1}^{12}\left(C_i x_i + CO_i o_i + CS_i s_i\right)\)

\(s_{i-1}+x_i+o_i = D_i+s_i,\quad i=1,\ldots,12\)

\(x_i \le 30000,\quad i=1,\ldots,12\)

\(x_i,o_i,s_i \ge 0\)

Constraint cân bằng tồn kho là phần quan trọng nhất của mô hình. Lượng tồn kho đầu kỳ cộng lượng sản xuất trong kỳ phải bằng nhu cầu kỳ đó cộng lượng tồn kho cuối kỳ. Constraint năng lực sản xuất giới hạn số lượng sản phẩm được tạo ra trong giờ bình thường. Khi mô hình được viết đúng, lời giải cho biết từng tháng nên sản xuất bao nhiêu, có cần làm thêm hay không và nên giữ tồn kho ở mức nào.

Lựa chọn cơ sở (facility location) thường dẫn đến mô hình hỗn hợp nhị phân tuyến tính (mixed binary linear programming). Biến nhị phân \(y_i\) nhận giá trị 1 nếu xây dựng cơ sở tại vị trí \(i\) và nhận giá trị 0 nếu không xây dựng. Biến liên tục \(x_{ij}\) biểu thị lượng hàng hoặc mức phục vụ từ cơ sở \(i\) đến khách hàng \(j\). Objective function kết hợp chi phí xây dựng cố định và chi phí phục vụ biến đổi. Constraint dung lượng bảo đảm mỗi cơ sở không phục vụ vượt quá năng lực, đồng thời constraint nhu cầu bảo đảm khách hàng được đáp ứng.

\(\min Z = \sum_{i=1}^{n} f_i y_i + \sum_{i=1}^{n}\sum_{j=1}^{m} c_{ij}x_{ij}\)

\(\sum_{j=1}^{m} x_{ij} \le P_i y_i,\quad i=1,\ldots,n\)

\(\sum_{i=1}^{n} x_{ij} \ge D_j,\quad j=1,\ldots,m\)

\(x_{ij} \ge 0,\quad y_i \in \{0,1\}\)

Trong bài toán phủ sóng, biến nhị phân có thể biểu thị việc chọn trạm phát và việc một khu vực dân cư có được phủ sóng hay không. Objective function là tổng dân số được phục vụ. Constraint ngân sách giới hạn tổng chi phí xây dựng trạm. Constraint liên kết bảo đảm một khu vực chỉ được tính là được phủ sóng khi có ít nhất một trạm được chọn có khả năng phục vụ khu vực đó. Kiểu modeling này phù hợp với các quyết định đầu tư hạ tầng, đặt điểm dịch vụ, bố trí kho và thiết kế mạng lưới.

\(\max Z = \sum_{j=1}^{m} p_j z_j\)

\(\sum_{i=1}^{n} f_i y_i \le B\)

\(z_j \le \sum_{i\in N(j)} y_i,\quad j=1,\ldots,m\)

\(y_i,z_j \in \{0,1\}\)

5. Nguyên lý của Simplex method

Simplex method là một thủ tục lặp dùng để cải thiện nghiệm qua từng bước. Thay vì quét toàn bộ feasible region, phương pháp này bắt đầu từ một nghiệm cơ sở khả thi ban đầu (initial basic feasible solution), sau đó di chuyển sang một nghiệm cơ sở lân cận nếu sự di chuyển đó làm objective function tốt hơn. Quá trình dừng khi không còn biến nào có thể đưa vào cơ sở để cải thiện giá trị mục tiêu.

Cách nhìn hình học của Simplex method rất rõ ràng. Với hai biến, thuật toán đi qua các cạnh của đa giác feasible region. Với nhiều biến, thuật toán đi qua các cạnh của đa diện lồi. Vì số đỉnh của feasible region là hữu hạn trong các bài toán hữu hạn, thuật toán có cơ sở để dừng sau một số bước nếu không gặp các hiện tượng suy biến đặc biệt.

Trong bảng Simplex, mỗi bước lặp gồm hai quyết định chính. Thứ nhất là chọn biến vào cơ sở (entering variable), thường dựa trên hệ số còn khả năng cải thiện objective function. Thứ hai là chọn biến ra khỏi cơ sở (leaving variable), thường dựa trên phép kiểm tra tỷ số để bảo toàn tính khả thi của nghiệm. Phần tử giao giữa entering variable và leaving variable là pivot. Sau khi chuẩn hóa pivot và cập nhật các hàng còn lại, bảng mới biểu diễn một nghiệm cơ sở mới.

6. Chuẩn hóa mô hình trước khi chạy Simplex

Simplex method cơ bản yêu cầu mô hình ở dạng thuận lợi cho việc lập bảng. Vế phải của các constraint nên không âm. Nếu một constraint có vế phải âm, toàn bộ constraint cần được nhân với hệ số âm để đổi dấu. Sau bước này, tất cả constraint bất đẳng thức cần được chuyển thành đẳng thức bằng cách thêm biến phụ phù hợp.

Với constraint dạng \(\le\), ta thêm slack variable để biến bất đẳng thức thành đẳng thức. Với constraint dạng \(\ge\), ta trừ surplus variable và thường phải thêm artificial variable để tạo được nghiệm cơ sở ban đầu. Với constraint dạng \(=\), artificial variable cũng cần được thêm vào nếu chưa có biến cơ sở tự nhiên. Các phép chuyển đổi có thể viết như sau.

\(a_i^T x \le b_i \Rightarrow a_i^T x+s_i=b_i,\quad s_i\ge 0\)

\(a_i^T x \ge b_i \Rightarrow a_i^T x-s_i+r_i=b_i,\quad s_i\ge 0,\ r_i\ge 0\)

\(a_i^T x = b_i \Rightarrow a_i^T x+r_i=b_i,\quad r_i\ge 0\)

Artificial variable không thuộc bài toán gốc. Nó chỉ được đưa vào để hỗ trợ việc khởi tạo. Nếu sau pha khởi tạo vẫn còn artificial variable mang giá trị dương trong nghiệm, bài toán gốc không có nghiệm khả thi. Vì vậy, xử lý artificial variable là điểm khác biệt chính giữa Simplex một pha và two phase Simplex.

7. Các tình huống cần nhận diện trong quá trình giải

Khi vận hành Simplex method, người giải không chỉ thực hiện biến đổi hàng. Cần nhận diện đúng trạng thái của bài toán để dừng đúng lúc và kết luận đúng. Các tình huống quan trọng gồm nghiệm tối ưu duy nhất, nhiều nghiệm tối ưu, nghiệm không bị chặn, không có nghiệm khả thi và trường hợp hòa khi chọn biến.

Trong thực hành, trường hợp hòa cần được xử lý cẩn thận vì có thể dẫn đến nghiệm suy biến và lặp vòng. Một quy tắc chọn biến nhất quán giúp giảm rủi ro này. Khi đang ở pha một, nếu có hòa ở leaving variable, ưu tiên đưa artificial variable ra khỏi cơ sở là lựa chọn hợp lý vì mục tiêu của pha này là loại bỏ hoàn toàn artificial variable khỏi nghiệm.

8. Simplex một pha

Simplex một pha áp dụng khi mô hình sau chuẩn hóa đã có initial basic feasible solution. Trường hợp phổ biến là bài toán tối đa hóa có tất cả constraint dạng ≤, vế phải không âm và tất cả biến không âm. Khi thêm slack variable, các slack variable tạo thành cột đơn vị trong bảng, nên có thể làm biến cơ sở ban đầu.

Quy trình giải gồm lập bảng Simplex đầu tiên, kiểm tra điều kiện dừng, chọn entering variable, chọn leaving variable, thực hiện pivot và lặp lại. Khi hàng objective function không còn hệ số cải thiện theo quy ước bảng đang dùng, nghiệm cơ sở hiện tại là nghiệm tối ưu. Giá trị của các biến cơ sở đọc từ cột giá trị. Các biến ngoài cơ sở có giá trị bằng 0.

Ví dụ Simplex một pha có thể mô tả bằng hệ công thức sau. Sau khi thêm các slack variable, bài toán có nghiệm cơ sở ban đầu và có thể lập bảng Simplex trực tiếp.

\(\max Z = 4x_1+5x_2\)

\(2x_1+x_2 \le 8\)

\(x_1+2x_2 \le 7\)

\(x_2 \le 3\)

\(x_1,x_2 \ge 0\)

\(2x_1+x_2+x_3 = 8\)

\(x_1+2x_2+x_4 = 7\)

\(x_2+x_5 = 3\)

\((x_1,x_2,x_3,x_4,x_5)=(3,2,0,0,1),\quad Z^*=22\)

Kết quả này có thể hiểu là hai biến quyết định chính đạt mức 3 và 2, trong khi một constraint còn dư một đơn vị tài nguyên.

9. Two phase Simplex

Two phase Simplex được dùng khi bài toán không có initial basic feasible solution rõ ràng. Tình huống này thường xuất hiện khi có constraint dạng ≥ hoặc =. Artificial variable được thêm vào để khởi tạo bảng, nhưng các biến này không được phép tồn tại trong nghiệm cuối cùng của bài toán gốc.

Hình 3. Quy trình tổng quát của two phase Simplex

Pha một xây dựng một bài toán phụ. Objective function của bài toán phụ nhằm đưa tổng artificial variable về 0. Nếu pha một kết thúc với giá trị mục tiêu bằng 0, bài toán gốc có nghiệm khả thi. Khi đó, artificial variable được loại khỏi bảng và thuật toán chuyển sang pha hai. Nếu giá trị mục tiêu của pha một khác 0, hệ constraint của bài toán gốc không thể thỏa mãn đồng thời, nên bài toán gốc không có nghiệm khả thi.

Pha hai sử dụng objective function gốc và bắt đầu từ nghiệm cơ sở khả thi tìm được ở pha một. Từ thời điểm này, quá trình giống Simplex một pha: kiểm tra điều kiện dừng, chọn entering variable, chọn leaving variable, pivot và cập nhật bảng. Ví dụ two phase Simplex có thể viết dưới dạng CKEditor như sau.

\(\max Z = 2x_1+3x_2+x_3\)

\(x_1+x_2+x_3 \le 40\)

\(2x_1+x_2-x_3 \ge 10\)

\(-x_2+x_3 \ge 10\)

\(x_1,x_2,x_3 \ge 0\)

\(\min W=x_7+x_8\)

\((x_1,x_2,x_3,x_4,x_5,x_6)=(10,20,10,0,0,0),\quad Z^*=70\)

Sau pha một, giá trị của bài toán phụ bằng 0 nên bài toán gốc khả thi. Sau khi loại artificial variable và giải tiếp ở pha hai, nghiệm tối ưu đạt giá trị như công thức trên.

10. Ý nghĩa thực tiễn

Linear programming có giá trị lớn vì nó buộc người ra quyết định mô tả rõ mục tiêu và giới hạn. Một mô hình tốt không chỉ đưa ra con số tối ưu, mà còn làm rõ cấu trúc của bài toán: nguồn lực nào đang giới hạn kết quả, constraint nào còn dư, quyết định nào ảnh hưởng mạnh đến chi phí hoặc lợi ích. Với các hệ thống sản xuất, logistics, năng lượng, viễn thông, lập lịch và phân công nguồn lực, cách tiếp cận này giúp chuyển quyết định kinh nghiệm thành quyết định có căn cứ định lượng.

Simplex method giữ vai trò nền tảng trong tối ưu hóa tuyến tính vì nó kết nối được trực giác hình học, biểu diễn đại số và quy trình tính toán bằng bảng. Người học cần nắm đồng thời ba lớp kiến thức: cách modeling bài toán thực tế, cách chuẩn hóa mô hình và cách đọc trạng thái của bảng Simplex. Khi ba lớp này được hiểu thống nhất, linear programming trở thành một công cụ thực hành mạnh cho phân tích quyết định và thiết kế hệ thống.

Kết luận

Quy hoạch tuyến tính cung cấp một khuôn khổ chặt chẽ để giải các bài toán tối ưu có objective function và constraint tuyến tính. Giá trị của phương pháp không nằm riêng ở thuật toán tính toán, mà còn nằm ở năng lực chuyển vấn đề thực tế thành mô hình có thể kiểm chứng. Simplex method khai thác cấu trúc đỉnh của feasible region để tìm nghiệm tối ưu thông qua các phép pivot liên tiếp. Khi mô hình có initial basic feasible solution, Simplex một pha đủ để giải bài toán. Khi mô hình cần artificial variable, two phase Simplex là quy trình phù hợp để kiểm tra tính khả thi và tiếp tục tối ưu hóa objective function gốc. Sự kết hợp giữa modeling chính xác và Simplex method tạo nên nền tảng quan trọng cho các bài toán ra quyết định trong vận hành, sản xuất, logistics và thiết kế hệ thống.