Wiki › Thuật toán › Toán học › Quy hoạch tuyến tính (Simplex)

Quy hoạch tuyến tính (Simplex)

Giải bài toán cực đại hàm tuyến tính dưới hệ bất đẳng thức tuyến tính bằng thuật toán đơn hình hai pha, và dùng đối ngẫu LP để đổi bài toán tối ưu lạ thành luồng hoặc hình học.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 19 phút 4 lượt xem

Quy hoạch tuyến tính (Linear Programming, LP) là bài toán tìm vector số thực x làm cực đại một hàm tuyến tính cTx dưới một hệ bất đẳng thức tuyến tính Ax≤b, x≥0. Rất nhiều bài toán tối ưu quen thuộc là LP trá hình: luồng cực đại, luồng chi phí nhỏ nhất, đường đi ngắn nhất, ghép cặp có trọng số, pha trộn nguyên liệu, phân bổ thời gian giữa các công việc. Thuật toán đơn hình (Simplex) của Dantzig giải LP bằng cách đi từ đỉnh này sang đỉnh kề tốt hơn của miền khả thi cho tới khi không cải thiện được nữa.

Trong competitive programming, Simplex dùng được khi số biến và số ràng buộc nhỏ (cỡ n,m≤100 đến vài trăm). Thời gian xấu nhất là mũ, nhưng trên thực tế số bước xoay thường chỉ cỡ O(m+n), mỗi bước O(mn). Quan trọng hơn cả cài đặt là đối ngẫu LP: nhiều bài khó (kể cả ICPC) không cần chạy Simplex, mà dùng đối ngẫu để biến một LP lạ thành bài luồng hoặc bài hình học có thuật toán tổ hợp nhanh.

Ý tưởng / Trực giác

Dạng chuẩn. Ta luôn đưa bài về dạng

max cTxvới Ax≤b, x≥0,

với A cỡ m×n. Mọi LP khác đều đổi được về dạng này: cực tiểu cTx thì cực đại −cTx; ràng buộc ≥ thì nhân −1; ràng buộc = thì tách thành hai bất đẳng thức ≤ và ≥; biến tự do xj (được âm) thì viết xj=xj+−xj− với xj+,xj−≥0.

Miền khả thi là một đa diện lồi, nghiệm tối ưu nằm ở một đỉnh. Mỗi bất đẳng thức cắt không gian thành nửa không gian; giao của chúng là một đa diện lồi P. Hàm mục tiêu tuyến tính nên các mặt mức cTx=t là các siêu phẳng song song. Đẩy t tăng dần, lần cuối siêu phẳng còn chạm P là tại một đỉnh (hoặc cả một cạnh, một mặt chứa đỉnh). Chứng minh ngắn: nếu điểm tối ưu x* không phải đỉnh, nó nằm giữa hai điểm x*±d của P; do cT(x*+d)+cT(x*−d)=2cTx* nên cả hai cũng tối ưu, và ta trượt theo d tới khi chạm thêm một ràng buộc chặt. Lặp lại tới khi có n ràng buộc chặt độc lập, tức một đỉnh. Vậy chỉ cần tìm trong các đỉnh, nhưng số đỉnh có thể là (m+nn), quá nhiều để duyệt hết.

Biến bù và bảng đơn hình. Thêm biến bù si=bi−Aix≥0 cho mỗi ràng buộc. Khi b≥0, điểm x=0, s=b là một đỉnh khả thi: các si là biến cơ sở (được biểu diễn qua các biến còn lại), các xj là biến ngoài cơ sở (bằng 0). Mỗi đỉnh ứng với một cách chọn m biến cơ sở trong m+n biến.

Bước xoay (pivot). Từ đỉnh hiện tại, viết mục tiêu theo các biến ngoài cơ sở: z=z0+∑jc¯jxj.

  • Nếu mọi c¯j≤0: tăng bất kỳ biến ngoài cơ sở nào cũng không làm z tăng, nên đỉnh hiện tại tối ưu (vì P lồi, tối ưu cục bộ là tối ưu toàn cục).
  • Ngược lại, chọn một cột s có c¯s>0 (biến vào). Tăng xs từ 0 trong khi giữ các biến ngoài cơ sở khác bằng 0; mỗi biến cơ sở giảm tuyến tính. Biến chạm 0 đầu tiên (kiểm tra tỉ số nhỏ nhất bi/ais trên các hàng ais>0) là biến ra. Hoán đổi vai trò hai biến: đó là đi dọc một cạnh của P sang đỉnh kề, z không giảm.
  • Nếu không hàng nào có ais>0, ta tăng xs mãi được: LP không bị chặn.

Pha 1: khi gốc toạ độ không khả thi. Nếu có bi<0 thì x=0 vi phạm ràng buộc. Ta thêm một biến phụ x0≥0 vào mọi ràng buộc: Aix−x0≤bi, rồi giải LP phụ "cực đại −x0". Một lần xoay đưa x0 vào cơ sở tại hàng có bi nhỏ nhất là đã có đỉnh khả thi của LP phụ. Nếu tối ưu của LP phụ có x0>0 thì bài gốc vô nghiệm; ngược lại đẩy x0 ra khỏi cơ sở và chạy Simplex bình thường (pha 2).

Đối ngẫu. Với mỗi LP dạng chuẩn (bài gốc, primal) có một LP đối ngẫu (dual):

(P) max cTx, Ax≤b, x≥0(D) min bTy, ATy≥c, y≥0.

  • Đối ngẫu yếu: mọi x khả thi của (P) và y khả thi của (D) thoả cTx≤(ATy)Tx=yT(Ax)≤yTb. Trực giác: yi là "hệ số nhân" cho ràng buộc i; cộng các ràng buộc theo hệ số y mà trội hơn c thì ra một cận trên cho mục tiêu.
  • Đối ngẫu mạnh: nếu (P) có tối ưu hữu hạn thì (D) cũng vậy và hai giá trị bằng nhau. Simplex chứng minh điều này một cách xây dựng: khi dừng, các hệ số ở hàng mục tiêu ứng với biến bù chính là một nghiệm tối ưu y của (D).
  • Lỏng bù (complementary slackness): tại cặp tối ưu, yi>0 thì ràng buộc i của (P) chặt, và xj>0 thì ràng buộc j của (D) chặt.

Ví dụ quen thuộc: đối ngẫu của luồng cực đại là lát cắt nhỏ nhất; đối ngẫu của ghép cặp lớn nhất trên đồ thị hai phía là phủ đỉnh nhỏ nhất (định lý König). Ma trận ràng buộc của các bài luồng là unimodular hoàn toàn (mọi định thức con thuộc {−1,0,1}), nên mọi đỉnh của đa diện đều nguyên: LP thực và bài nguyên cho cùng đáp án.

Ví dụ chạy tay

Giải

max z=3x+2yvớix+y≤4,x+3y≤6,x≤3,x,y≥0.

Miền khả thi là ngũ giác với các đỉnh (0,0),(3,0),(3,1),(1.5,1.5),(0,2):

  y
  2 *
    |  ' .        x + 3y = 6
1.5 |      * (1.5, 1.5)
    |        ' .  x + y = 4
  1 |           * (3, 1)
    |           |  x = 3
  0 *-----------*-------> x
    0           3

Thêm biến bù s1,s2,s3. Bảng ban đầu (cơ sở là các biến bù, hàng z lưu −c):

cơ sở x y s1 s2 s3 vế phải
s1 1 1 1 0 0 4
s2 1 3 0 1 0 6
s3 1 0 0 0 1 3
z -3 -2 0 0 0 0

Bước 1. Hệ số âm nhất ở hàng z là −3 (cột x): x vào. Tỉ số: 4/1,6/1,3/1, nhỏ nhất là 3 ở hàng s3: s3 ra. Xoay quanh ô (s3,x):

cơ sở x y s1 s2 s3 vế phải
s1 0 1 1 0 -1 1
s2 0 3 0 1 -1 3
x 1 0 0 0 1 3
z 0 -2 0 0 3 9

Ta đang ở đỉnh (3,0) với z=9.

Bước 2. Còn hệ số −2 ở cột y: y vào. Tỉ số: 1/1=1 (hàng s1) và 3/3=1 (hàng s2), hoà; chọn hàng có chỉ số biến nhỏ hơn là s1. Xoay quanh ô (s1,y):

cơ sở x y s1 s2 s3 vế phải
y 0 1 1 0 -1 1
s2 0 0 -3 1 2 0
x 1 0 0 0 1 3
z 0 0 2 0 1 11

Hàng z không còn hệ số âm: tối ưu z=11 tại (x,y)=(3,1). Lưu ý s2=0 dù là biến cơ sở: đỉnh (3,1) là suy biến (ba ràng buộc cùng chặt tại đó), chính là chỗ xảy ra hoà tỉ số ở bước 2.

Đọc nghiệm đối ngẫu. Hệ số ở hàng z dưới các cột s1,s2,s3 là y=(2,0,1). Kiểm tra: đối ngẫu là min 4y1+6y2+3y3 với y1+y2+y3≥3, y1+3y2≥2, y≥0. Với y=(2,0,1): hai ràng buộc thành 3≥3, 2≥2, và 4·2+6·0+3·1=11, đúng bằng giá trị bài gốc. Nghĩa là: lấy 2×(x+y≤4) cộng 1×(x≤3) được 3x+2y≤11, một chứng chỉ rằng không thể vượt 11.

Cài đặt

Cài đặt dưới đây dùng bảng (m+2)×(n+2): m hàng ràng buộc, hàng m là mục tiêu, hàng m+1 là mục tiêu của pha 1; cột n là biến phụ x0, cột n+1 là vế phải. Quy tắc chọn: cột vào có hệ số âm nhất, hàng ra theo tỉ số nhỏ nhất, hoà thì ưu tiên chỉ số biến nhỏ. Chương trình đọc m,n, ma trận A, vector b, vector c, in giá trị tối ưu và nghiệm, hoặc INFEASIBLE / UNBOUNDED.

C++
#include <bits/stdc++.h>
using namespace std;

// Giải: max c^T x  với  A x <= b,  x >= 0  (m ràng buộc, n biến)
// Trả về: giá trị tối ưu, -INF nếu vô nghiệm, +INF nếu không bị chặn.
typedef double T;
typedef vector<T> vd;
const T EPS = 1e-9, INF = 1 / .0;

struct LPSolver {
    int m, n;
    vector<int> N, B;       // N: biến ngoài cơ sở (cột), B: biến cơ sở (hàng)
    vector<vd> D;           // bảng đơn hình (m+2) x (n+2)

    LPSolver(const vector<vd>& A, const vd& b, const vd& c)
        : m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, vd(n + 2)) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) D[i][j] = A[i][j];
        for (int i = 0; i < m; i++) {
            B[i] = n + i;           // biến bù s_i = b_i - A_i x
            D[i][n] = -1;           // cột biến phụ x0 (chỉ dùng ở pha 1)
            D[i][n + 1] = b[i];     // vế phải
        }
        for (int j = 0; j < n; j++) {
            N[j] = j;
            D[m][j] = -c[j];        // hàng mục tiêu (lưu -c)
        }
        N[n] = -1;
        D[m + 1][n] = 1;            // hàng mục tiêu pha 1: max -x0
    }

    // Xoay quanh phần tử D[r][s]: biến N[s] vào cơ sở, biến B[r] ra
    void pivot(int r, int s) {
        T inv = 1 / D[r][s];
        for (int i = 0; i < m + 2; i++)
            if (i != r && fabs(D[i][s]) > EPS) {
                T inv2 = D[i][s] * inv;
                for (int j = 0; j < n + 2; j++) D[i][j] -= D[r][j] * inv2;
                D[i][s] = D[r][s] * inv2;
            }
        for (int j = 0; j < n + 2; j++)
            if (j != s) D[r][j] *= inv;
        for (int i = 0; i < m + 2; i++)
            if (i != r) D[i][s] *= -inv;
        D[r][s] = inv;
        swap(B[r], N[s]);
    }

    // Lặp đơn hình trên hàng mục tiêu x = m + phase - 1
    bool simplex(int phase) {
        int x = m + phase - 1;
        while (true) {
            int s = -1;   // cột vào: hệ số âm nhất, hoà thì chỉ số biến nhỏ hơn
            for (int j = 0; j <= n; j++) {
                if (N[j] == -phase) continue;
                if (s == -1 || make_pair(D[x][j], N[j]) < make_pair(D[x][s], N[s])) s = j;
            }
            if (D[x][s] >= -EPS) return true;   // không còn cải thiện: tối ưu
            int r = -1;   // hàng ra: kiểm tra tỉ số nhỏ nhất
            for (int i = 0; i < m; i++) {
                if (D[i][s] <= EPS) continue;
                if (r == -1 || make_pair(D[i][n + 1] / D[i][s], B[i]) <
                                   make_pair(D[r][n + 1] / D[r][s], B[r]))
                    r = i;
            }
            if (r == -1) return false;          // tăng mãi được: không bị chặn
            pivot(r, s);
        }
    }

    T solve(vd& x) {
        int r = 0;
        for (int i = 1; i < m; i++)
            if (D[i][n + 1] < D[r][n + 1]) r = i;
        if (D[r][n + 1] < -EPS) {               // gốc toạ độ không khả thi: chạy pha 1
            pivot(r, n);
            if (!simplex(2) || D[m + 1][n + 1] < -EPS) return -INF;   // vô nghiệm
            for (int i = 0; i < m; i++)
                if (B[i] == -1) {               // đẩy x0 ra khỏi cơ sở
                    int s = 0;
                    for (int j = 1; j <= n; j++)
                        if (s == -1 || make_pair(D[i][j], N[j]) < make_pair(D[i][s], N[s])) s = j;
                    pivot(i, s);
                }
        }
        bool ok = simplex(1);
        x = vd(n);
        for (int i = 0; i < m; i++)
            if (B[i] < n) x[B[i]] = D[i][n + 1];
        return ok ? D[m][n + 1] : INF;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<vd> A(m, vd(n));
    vd b(m), c(n);
    for (auto& row : A)
        for (auto& v : row) cin >> v;
    for (auto& v : b) cin >> v;
    for (auto& v : c) cin >> v;
    LPSolver lp(A, b, c);
    vd x;
    T val = lp.solve(x);
    if (val == -INF) cout << "INFEASIBLE\n";
    else if (val == INF) cout << "UNBOUNDED\n";
    else {
        cout << fixed << setprecision(6) << val << "\n";
        for (int j = 0; j < n; j++) cout << x[j] << (j + 1 < n ? ' ' : '\n');
    }
}
Python
import sys

EPS = 1e-9
INF = float("inf")


# Giải: max c^T x  với  A x <= b,  x >= 0  (m ràng buộc, n biến)
# Trả về (giá trị, x): giá trị -INF nếu vô nghiệm, +INF nếu không bị chặn.
def lp_solve(A, b, c):
    m, n = len(b), len(c)
    D = [[0.0] * (n + 2) for _ in range(m + 2)]  # bảng đơn hình
    for i in range(m):
        for j in range(n):
            D[i][j] = float(A[i][j])
        D[i][n] = -1.0  # cột biến phụ x0 (pha 1)
        D[i][n + 1] = float(b[i])  # vế phải
    for j in range(n):
        D[m][j] = -float(c[j])  # hàng mục tiêu (lưu -c)
    D[m + 1][n] = 1.0  # hàng mục tiêu pha 1
    B = [n + i for i in range(m)]  # biến cơ sở (biến bù)
    N = list(range(n)) + [-1]  # biến ngoài cơ sở

    def pivot(r, s):  # biến N[s] vào cơ sở, biến B[r] ra
        Dr = D[r]
        inv = 1.0 / Dr[s]
        for i in range(m + 2):
            if i != r and abs(D[i][s]) > EPS:
                Di = D[i]
                inv2 = Di[s] * inv
                for j in range(n + 2):
                    Di[j] -= Dr[j] * inv2
                Di[s] = Dr[s] * inv2
        for j in range(n + 2):
            if j != s:
                Dr[j] *= inv
        for i in range(m + 2):
            if i != r:
                D[i][s] *= -inv
        Dr[s] = inv
        B[r], N[s] = N[s], B[r]

    def simplex(phase):
        x = m + phase - 1
        while True:
            s = -1  # cột vào: hệ số âm nhất, hoà thì chỉ số biến nhỏ hơn
            for j in range(n + 1):
                if N[j] == -phase:
                    continue
                if s == -1 or (D[x][j], N[j]) < (D[x][s], N[s]):
                    s = j
            if D[x][s] >= -EPS:
                return True  # tối ưu
            r = -1  # hàng ra: tỉ số nhỏ nhất
            for i in range(m):
                if D[i][s] <= EPS:
                    continue
                if r == -1 or (D[i][n + 1] / D[i][s], B[i]) < (D[r][n + 1] / D[r][s], B[r]):
                    r = i
            if r == -1:
                return False  # không bị chặn
            pivot(r, s)

    r = 0
    for i in range(1, m):
        if D[i][n + 1] < D[r][n + 1]:
            r = i
    if m > 0 and D[r][n + 1] < -EPS:  # gốc toạ độ không khả thi: pha 1
        pivot(r, n)
        if not simplex(2) or D[m + 1][n + 1] < -EPS:
            return -INF, None  # vô nghiệm
        for i in range(m):
            if B[i] == -1:  # đẩy x0 ra khỏi cơ sở
                s = 0
                for j in range(1, n + 1):
                    if (D[i][j], N[j]) < (D[i][s], N[s]):
                        s = j
                pivot(i, s)
    ok = simplex(1)
    x = [0.0] * n
    for i in range(m):
        if B[i] < n:
            x[B[i]] = D[i][n + 1]
    return (D[m][n + 1] if ok else INF), x


def main():
    data = sys.stdin.read().split()
    m, n = int(data[0]), int(data[1])
    p = 2
    A = []
    for _ in range(m):
        A.append([float(v) for v in data[p : p + n]])
        p += n
    b = [float(v) for v in data[p : p + m]]
    p += m
    c = [float(v) for v in data[p : p + n]]
    val, x = lp_solve(A, b, c)
    if val == -INF:
        print("INFEASIBLE")
    elif val == INF:
        print("UNBOUNDED")
    else:
        print("%.6f" % val)
        print(" ".join("%.6f" % v for v in x))


main()

Thứ tự hoà theo chỉ số biến giúp giảm nguy cơ lặp vòng (cycling) trên đỉnh suy biến; quy tắc Bland thuần (luôn chọn cột vào có chỉ số nhỏ nhất trong các cột âm) chứng minh được là không bao giờ lặp vòng nhưng chậm hơn. Với dữ liệu thực nguyên, có thể dùng long double cho T để an toàn số học hơn.

Độ phức tạp

Thao tác Thời gian Bộ nhớ
Một bước xoay O(mn) O(mn)
Toàn bộ Simplex (thực tế) thường O(m+n) bước, tức khoảng O(mn(m+n)) O(mn)
Toàn bộ Simplex (xấu nhất) mũ (ví dụ khối Klee-Minty) O(mn)

Vì sao mỗi bước O(mn)? Bước xoay cập nhật toàn bộ bảng (m+2)×(n+2), mỗi ô một phép nhân trừ. Tìm cột vào O(n), tìm hàng ra O(m).

Vì sao số bước khó đoán? Mỗi bước đi sang một đỉnh kề có z không nhỏ hơn, và không lặp lại đỉnh nếu không suy biến, nên số bước không quá số đỉnh. Có những đa diện được dựng riêng (Klee-Minty) khiến quy tắc "hệ số âm nhất" đi qua 2n đỉnh, nhưng trên dữ liệu thông thường Simplex chạy rất nhanh. Nếu cần bảo đảm đa thức, có thuật toán điểm trong (interior point) hoặc ellipsoid, hiếm khi cần trong CP.

⚠️ Lỗi thường gặp

  • So sánh số thực không có EPS: D[x][s] >= 0 thay vì >= -EPS khiến Simplex xoay mãi vì những hệ số cỡ −10−16 do sai số làm tròn. Mọi phép so sánh với 0 trong bảng phải có ngưỡng.
  • Quên pha 1 khi có bi<0: bắt đầu từ x=0 khi gốc toạ độ không khả thi sẽ trả ra một "tối ưu" vi phạm ràng buộc. Ràng buộc dạng ≥ sau khi nhân −1 thường cho bi<0, nên trường hợp này rất hay gặp.
  • Đổi sai dạng chuẩn: quên rằng mọi biến phải ≥0. Biến được phép âm mà không tách x=x+−x− thì Simplex ngầm chặn nó ở 0 và trả đáp án sai. Ràng buộc đẳng thức phải tách thành hai bất đẳng thức.
  • Chọn hàng ra sai: chỉ xét các hàng có ais>0 (lớn hơn EPS). Lấy cả hàng ais≤0 làm tỉ số âm hoặc chia cho 0, đưa bảng tới đỉnh không khả thi.
  • Nhầm không bị chặn với vô nghiệm: không tìm được hàng ra nghĩa là mục tiêu tăng vô hạn (UNBOUNDED), còn vô nghiệm chỉ được phát hiện ở pha 1 khi tối ưu của LP phụ âm. Hai trường hợp cần in khác nhau.
  • Mong đợi nghiệm nguyên: Simplex trả nghiệm thực. Nếu bài yêu cầu x nguyên (quy hoạch nguyên) thì nói chung là NP-khó; chỉ khi ma trận unimodular hoàn toàn (luồng, ghép cặp hai phía) đỉnh tối ưu mới tự động nguyên.

Biến thể / Mở rộng

  • Đối ngẫu để đổi sang bài tổ hợp: đây là cách dùng LP thường gặp nhất trong đề thi. Viết bài toán thành LP, lấy đối ngẫu, rồi nhận ra đối ngẫu là luồng, lát cắt hay đường đi ngắn nhất. Xem Max Flow (Dinic) và Min Cost Flow.
  • LP ít biến: khi chỉ có 2 biến, miền khả thi là đa giác lồi và tối ưu là một đỉnh của nó; có thể giải bằng bao lồi, hoặc nhận xét hàm maxxmini(…) là lồi/lõm rồi dùng Ternary Search. Thuật toán Megiddo / Seidel giải LP số chiều cố định trong O(m) kỳ vọng.
  • Ghép cặp và König: LP của ghép cặp hai phía có ma trận unimodular hoàn toàn, đối ngẫu của nó là phủ đỉnh. Xem Bipartite Matching (Ghép cặp hai phía).
  • Tối ưu phân thức maxcTxdTx: đổi biến Charnes-Cooper đưa về LP, hoặc tìm kiếm nhị phân đáp án như Tối ưu phân thức (Dinkelbach).

Bài tập luyện

  • Giấc mơ freelancer (freedream): (Expert) Chia thời gian (số thực) cho các dự án để tích luỹ đủ p điểm kinh nghiệm và q đô-la với tổng số ngày nhỏ nhất. Đây là LP với n biến và 2 ràng buộc; đối ngẫu chỉ có 2 biến nên giải được bằng hình học hoặc tìm kiếm tam phân.
  • Lợi nhuận của nhà vua (icpc23regk): (Expert) Xây trạm thu phí và công viên trên các cạnh sao cho mọi đường đi từ 1 đến n không vượt mức chịu đựng, cực đại lợi nhuận. Viết thành LP theo thế đỉnh rồi lấy đối ngẫu, bài trở thành luồng nhỏ nhất có cận dưới.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0