Quy hoạch tuyến tính (Linear Programming) là một phương pháp toán học nhằm tìm phương án tốt nhất (tối ưu), ví dụ như lợi nhuận cao nhất hay chi phí thấp nhất từ một tập hợp các quyết định có giới hạn. Nó yêu cầu cả hàm mục tiêu và các điều kiện ràng buộc đều phải là các phương trình hoặc bất phương trình bậc nhất (tuyến tính).

CƠ SỞ TOÁN HỌC VÀ PHƯƠNG PHÁP TÍNH

1. Cơ sở Toán học (Mathematical Foundations)

1.1. Dạng Chính tắc (Canonical Form)

Mọi bài toán quy hoạch tuyến tính (LP) có thể được chuyển đổi về dạng chuẩn tắc để xử lý bằng thuật toán máy tính:

\begin{aligned} \text{Minimize } & Z = \mathbf{c}^T \mathbf{x} \\ \text{Subject to } & A\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq 0 \end{aligned}

Trong đó:

$\mathbf{x} \in \mathbb{R}^n$ : Vector biến quyết định (decision variables).
$\mathbf{c} \in \mathbb{R}^n$ : Vector hệ số hàm mục tiêu (cost vector).
$A \in \mathbb{R}^{m \times n}$ : Ma trận hệ số ràng buộc (constraint matrix) với hạng đầy đủ $m < n$ .
$\mathbf{b} \in \mathbb{R}^m$ : Vector vế phải (right-hand side vector).

1.2. Lý thuyết Đa diện (Polyhedral Theory)

Tập hợp các giải pháp chấp nhận được (Feasible Set) $P$ được định nghĩa hình học là giao của các nửa không gian:

$P = \{ \mathbf{x} \in \mathbb{R}^n \mid A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0 \}$

$P$ là một đa diện lồi (Convex Polyhedron).
Định lý Cơ bản (Fundamental Theorem of LP): Nếu bài toán có nghiệm tối ưu hữu hạn, thì nghiệm đó phải nằm tại ít nhất một đỉnh (vertex) hoặc điểm cực biên (extreme point) của đa diện $P$ .

1.3. Lý thuyết Đối ngẫu (Duality Theory)

Mỗi bài toán gốc (Primal - P) luôn đi kèm một bài toán đối ngẫu (Dual - D):

(P): Min $\mathbf{c}^T \mathbf{x}$ s.t. $A\mathbf{x} \geq \mathbf{b}, \mathbf{x} \geq 0$
(D): Max $\mathbf{b}^T \mathbf{y}$ s.t. $A^T \mathbf{y} \leq \mathbf{c}, \mathbf{y} \geq 0$

Các định lý cốt lõi:

Đối ngẫu Yếu (Weak Duality): $\mathbf{b}^T \mathbf{y} \leq \mathbf{c}^T \mathbf{x}$ với mọi cặp nghiệm khả thi $(\mathbf{x}, \mathbf{y})$ .
Đối ngẫu Mạnh (Strong Duality): Tại điểm tối ưu $(\mathbf{x}^*, \mathbf{y}^*)$ , ta có $\mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}^*$ .
Độ lệch bù (Complementary Slackness): $x_j (c_j - \mathbf{y}^T A_j) = 0, \quad \forall j$ $y_i (A_i \mathbf{x} - b_i) = 0, \quad \forall i$

2. Phân loại Phương pháp Giải quyết (Methodology Hierarchy)

flowchart LR
    Root[Linear Programming Solving Methods]
    
    Root --> Simplex[Simplex Methods]
    Simplex --> PSimplex[Primal Simplex]
    Simplex --> DSimplex[Dual Simplex]
    Simplex --> RSimplex[Revised Simplex]
    
    Root --> IPM[Interior Point Methods]
    IPM --> Affine[Affine Scaling]
    IPM --> Path[Primal-Dual Path Following]
    IPM --> Barrier[Barrier Methods]
    
    Root --> Special[Specialized Algorithms]
    Special --> Ellipsoid[Ellipsoid Method]
    Special --> ColGen[Column Generation]
    Special --> Dantzig[Dantzig-Wolfe Decomposition]

3. Bảng So sánh Kỹ thuật (Comparative Analysis)

Tiêu chí	Phương pháp Đơn hình (Simplex)	Phương pháp Điểm trong (Interior Point)	Phương pháp Ellipsoid
Cơ chế Hình học	Di chuyển dọc theo cạnh của đa diện (Vertex-to-Vertex).	Di chuyển xuyên qua phần trong của vùng chấp nhận (Through Interior).	Bao nghiệm bằng chuỗi các hình Ellipsoid có thể tích giảm dần.
Độ phức tạp (Lý thuyết)	Mũ (Exponential): . (Kém nhất trong lý thuyết).	Đa thức (Polynomial): .	Đa thức (Polynomial): .
Hiệu năng (Thực tế)	Rất nhanh, số bước lặp .	Ổn định với bài toán quy mô lớn (Large-scale).	Chậm, ít dùng trong thực tế công nghiệp.
Warm Start	Xuất sắc: Tận dụng tốt nghiệm cũ (Cốt lõi của Branch & Bound).	Kém: Khó tái sử dụng nghiệm khi thay đổi bài toán.	Không áp dụng.
Độ chính xác	Tuyệt đối (Exact Basic Solution).	Xấp xỉ (-optimal). Cần bước Crossover để chính xác hóa.	Kém hơn Simplex.
Ứng dụng chính	General LP, MILP, Small-Medium size.	Very Large LP, Sparse Matrices.	Lý thuyết độ phức tạp.

4. Phương pháp Tính toán Chi tiết (Computational Methods)

4.1. Phương pháp Đơn hình (Simplex Algorithm)

Chiến lược: Iterative improvement.
Bước lặp:

Chọn biến vào (Entering variable): Dựa trên Reduced Cost âm nhất ().
Chọn biến ra (Leaving variable): Dựa trên phép thử tỷ số (Minimum Ratio Test) để đảm bảo tính khả thi.
Xoay trục (Pivot): Sử dụng phép khử Gaussian để cập nhật ma trận cơ sở.

Revised Simplex: Tối ưu hóa việc tính toán bằng cách chỉ lưu trữ và cập nhật phân rã của ma trận cơ sở , giúp xử lý ma trận thưa hiệu quả.

4.2. Phương pháp Điểm trong (Primal-Dual Interior Point)

Chiến lược: Giải hệ phương trình KKT bị nhiễu bởi tham số rào cản .
Hệ phương trình Newton (Newton Step): Tại mỗi bước lặp, giải hệ tuyến tính sau để tìm hướng di chuyển :
: Ma trận đường chéo của và (biến bù).
: Phần dư (residuals) của bài toán gốc và đối ngẫu.
: Tham số trung tâm hóa (centering parameter).

5. Tài liệu Nguồn (References)

Danh mục tài liệu gốc được trích dẫn (Primary Literature):

Dantzig, G. B. (1947). Maximization of a linear function of variables subject to linear inequalities. (Publication of the Simplex Method).
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4, 373–395. (Seminal paper on Interior Point Methods).
Khachiyan, L. G. (1979). A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR, 244: 1093–1096. (The Ellipsoid Method).
Mehrotra, S. (1992). On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 2(4), 575-601. (Predictor-Corrector algorithm used in modern solvers).
Wright, S. J. (1997). Primal-Dual Interior-Point Methods. SIAM.

Quy hoạch Tuyến tính