Linear Programming: tối ưu dưới các ràng buộc tuyến tính

Không phải bài toán tối ưu nào cũng cần heuristic.

Nếu ta mô tả được bài toán bằng hàm mục tiêu tuyến tính và các ràng buộc tuyến tính, Linear Programming (LP) cho phép dùng các thuật toán rất mạnh để tìm nghiệm tối ưu.

1. Ví dụ: phân bổ thời gian cho hackathon

Một nhóm sinh viên còn 10 giờ lập trình và 8 giờ kiểm thử trước vòng demo. Nhóm có hai hạng mục:

$x$ : số đơn vị công việc cho tính năng A.
$y$ : số đơn vị công việc cho tính năng B.

Điểm kỳ vọng:

\max \; 5x + 4y

Nhưng nhóm có giới hạn:

Mỗi đơn vị A cần 2 giờ lập trình và 1 giờ kiểm thử.
Mỗi đơn vị B cần 1 giờ lập trình và 2 giờ kiểm thử.
Tổng giờ lập trình: $2x + y \le 10$ .
Tổng giờ kiểm thử: $x + 2y \le 8$ .
Không thể dùng thời gian âm: $x \ge 0$ , $y \ge 0$ .

Ta có một bài toán LP hoàn chỉnh:

\max \; 5x + 4y

subject to:

2x + y \le 10

x + 2y \le 8

x, y \ge 0

2. Ba thành phần cần nhận ra

Biến quyết định

Các đại lượng ta được phép lựa chọn:

x, y

Hàm mục tiêu

Thứ ta muốn tối đa hoặc tối thiểu:

5x + 4y

Ràng buộc

Giới hạn tài nguyên hoặc luật nghiệp vụ:

2x + y \le 10

x + 2y \le 8

3. Feasible region - vùng nghiệm hợp lệ

Mỗi ràng buộc loại bỏ một phần không gian nghiệm.

Giao của tất cả các vùng còn lại tạo thành vùng khả thi.

Với ví dụ hai biến, vùng khả thi là một đa giác — ta có thể kiểm tra từng đỉnh để tìm nghiệm tối ưu. Bốn đỉnh của bài toán hackathon trên là:

Đỉnh	x (giờ A)	y (giờ B)	Điểm = 5x + 4y
O	0	0	0
P1	5	0	25
P2	4	2	28 ← tối ưu
P3	0	4	16

Nghiệm tối ưu là $x=4, y=2$ với điểm 28. Ta không cần thử vô số điểm — chỉ cần kiểm tra các đỉnh của đa giác khả thi.

Cách tính đỉnh $P2$ :

2x + y = 10

x + 2y = 8

Lấy phương trình đầu trừ nửa phương trình sau, hoặc giải hệ trực tiếp, ta được $x=4, y=2$ . Kiểm tra lại:

Giờ lập trình: $2 \cdot 4 + 2 = 10$ .
Giờ kiểm thử: $4 + 2 \cdot 2 = 8$ .
Điểm: $5 \cdot 4 + 4 \cdot 2 = 28$ .

P2 (x=4, y=2) cho điểm cao nhất là 28 — đây là nghiệm tối ưu của bài toán.

Ý tưởng này giải thích tại sao phương pháp Simplex di chuyển giữa các đỉnh của miền khả thi. Ở số chiều cao hơn, miền khả thi trở thành một đa diện.

Điều gì xảy ra nếu ràng buộc thay đổi?

Nếu đội có thêm 2 giờ lập trình (tăng từ 10 lên 12 giờ), ràng buộc mới là $2x + y \le 12$ . Feasible region giãn ra, đỉnh tối ưu dịch chuyển:

Kịch bản	Ràng buộc thay đổi	Nghiệm tối ưu	Điểm
Gốc	LP=10, QA=8	x=4, y=2	28
+2 giờ lập trình	LP=12, QA=8	x=5.3, y=1.3	32
+2 giờ kiểm thử	LP=10, QA=10	x=3.3, y=3.3	30
+2 giờ cả hai	LP=12, QA=10	x=4.7, y=2.7	34

Trong nghiệm gốc, thêm 2 giờ lập trình tăng điểm từ 28 lên 32, tức +4 điểm. Thêm 2 giờ kiểm thử tăng điểm từ 28 lên 30, tức +2 điểm. Đây là trực giác của shadow price — giá trị biên của mỗi đơn vị tài nguyên thêm. LP solver thường tính sẵn thông tin này để giúp quyết định tài nguyên nào đáng đầu tư thêm.

4. Dạng ma trận tổng quát

Một dạng chuẩn thường gặp:

\min_x \; c^T x

subject to:

A_{ub}x \le b_{ub}

A_{eq}x = b_{eq}

l \le x \le u

Trong đó:

$x$ : vector biến quyết định.
$c$ : hệ số của hàm mục tiêu.
$A_{ub}, b_{ub}$ : các bất đẳng thức.
$A_{eq}, b_{eq}$ : các đẳng thức.
$l, u$ : cận dưới và cận trên của biến.

5. Tại sao gọi là “linear”?

Các biểu thức phải tuyến tính theo biến.

Hợp lệ:

3x + 2y

4x - y \le 7

Không còn là LP thuần túy:

x^2 + y

xy \le 10

\sin(x) + y

Điểm quan trọng không phải là bài toán “dễ”, mà là cấu trúc tuyến tính cho phép các thuật toán chuyên biệt khai thác rất hiệu quả.

6. Simplex và Interior-Point

Simplex

George Dantzig phát triển phương pháp Simplex năm 1947.

Ý tưởng hình học đơn giản:

Bắt đầu ở một đỉnh khả thi.
Di chuyển qua các đỉnh kề.
Chọn hướng cải thiện hàm mục tiêu.
Dừng khi không còn đỉnh kề tốt hơn.

Interior-Point

Các phương pháp interior-point đi qua bên trong vùng khả thi thay vì chỉ di chuyển trên biên.

Trong khóa nhập môn, không cần tự cài Simplex hay interior-point. Điều quan trọng là biết khi nào bài toán có thể mô hình hóa thành LP.

7. Dùng SciPy

SciPy hỗ trợ LP bằng scipy.optimize.linprog.

Ví dụ cực đại hóa $5x + 4y$ có thể đổi thành cực tiểu hóa $-5x - 4y$ :

from scipy.optimize import linprog

result = linprog(
    c=[-5, -4],          # cực tiểu hóa -5x - 4y ≡ cực đại hóa 5x + 4y
    A_ub=[
        [2, 1],          # 2x + y <= 10
        [1, 2],          # x + 2y <= 8
    ],
    b_ub=[10, 8],
    bounds=[(0, None), (0, None)],  # x >= 0, y >= 0
    method="highs",
)

print(f"x = {result.x[0]:.2f}, y = {result.x[1]:.2f}")
print(f"Điểm tối đa = {-result.fun:.2f}")

# Shadow prices (dual variables): giá trị của mỗi đơn vị tài nguyên thêm
shadow = result.ineqlin.marginals
print(f"Shadow price lập trình: {-shadow[0]:.2f} điểm/giờ")
print(f"Shadow price kiểm thử:  {-shadow[1]:.2f} điểm/giờ")

x = 4.00, y = 2.00
Điểm tối đa = 28.00
Shadow price lập trình: 2.00 điểm/giờ
Shadow price kiểm thử:  1.00 điểm/giờ

Shadow price 2.00 > 1.00 xác nhận: trong nghiệm hiện tại, mỗi giờ lập trình thêm mang lại 2 điểm, còn mỗi giờ kiểm thử thêm mang 1 điểm. Đây là thông tin để quyết định phân bổ tài nguyên.

Theo tài liệu SciPy hiện tại, method="highs" dùng các solver HiGHS và là lựa chọn mặc định cho linprog.

8. Khi biến phải là số nguyên thì sao?

Giả sử $x$ là số laptop cần mua. Nghiệm $x=3.7$ không có ý nghĩa.

Khi một số hoặc toàn bộ biến bắt buộc là số nguyên, ta chuyển sang:

Integer Programming.
Mixed-Integer Linear Programming (MILP).

Đây là họ bài toán khác và thường khó hơn LP liên tục.

9. LP dùng ở đâu?

Các dạng ứng dụng điển hình:

Phân bổ tài nguyên.
Lập kế hoạch sản xuất.
Tối ưu chi phí vận tải.
Phân bổ ngân sách.
Network flow.
Một số bài toán năng lượng và viễn thông.

Trong AI, LP cũng xuất hiện bên trong nhiều phương pháp tối ưu, inference và relaxation của bài toán rời rạc.

10. Khi không nên ép bài toán thành LP

Nếu mô hình thực tế có:

Quan hệ phi tuyến mạnh.
Điều kiện logic phức tạp.
Nhiều biến Boolean / integer.
Ràng buộc kiểu lịch biểu khó biểu diễn tuyến tính.

thì CSP, CP-SAT, MIP hoặc các phương pháp tối ưu khác có thể phù hợp hơn.

Chọn đúng mô hình quan trọng hơn chọn solver thật mạnh.

11. Câu hỏi tự kiểm tra

Vì sao bài toán có $xy$ trong ràng buộc không còn là LP thuần túy?
Nghiệm khả thi khác nghiệm tối ưu thế nào?
Nếu biến là “số phòng học được mở”, tại sao LP liên tục có thể chưa đủ?
Trong một bài toán mới, phần khó hơn thường là viết solver hay mô hình hóa?

Tài liệu tham khảo

Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004: https://web.stanford.edu/~boyd/cvxbook/
George B. Dantzig. “Linear Programming.” Operations Research, 50(1), 2002. https://doi.org/10.1287/opre.50.1.42.17798
SciPy documentation, scipy.optimize.linprog: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html
SciPy documentation, linprog(method="highs"): https://docs.scipy.org/doc/scipy/reference/optimize.linprog-highs.html
CS50 AI, Lecture 3 - Optimization: https://cs50.harvard.edu/ai/notes/3/

Bản tiếng Anh đang soạn.