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.
Quy hoạch tuyến tính (Linear Programming, LP) là bài toán tìm vector số thực làm cực đại một hàm tuyến tính dưới một hệ bất đẳng thức tuyến tính , . 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 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ỡ , mỗi bước . 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
với cỡ . Mọi LP khác đều đổi được về dạng này: cực tiểu thì cực đại ; ràng buộc thì nhân ; ràng buộc thì tách thành hai bất đẳng thức và ; biến tự do (được âm) thì viết với .
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 . Hàm mục tiêu tuyến tính nên các mặt mức là các siêu phẳng song song. Đẩy tăng dần, lần cuối siêu phẳng còn chạm 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 không phải đỉnh, nó nằm giữa hai điểm của ; do nên cả hai cũng tối ưu, và ta trượt theo tới khi chạm thêm một ràng buộc chặt. Lặp lại tới khi có 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à , quá nhiều để duyệt hết.
Biến bù và bảng đơn hình. Thêm biến bù cho mỗi ràng buộc. Khi , điểm , là một đỉnh khả thi: các là biến cơ sở (được biểu diễn qua các biến còn lại), các là biến ngoài cơ sở (bằng ). Mỗi đỉnh ứng với một cách chọn biến cơ sở trong 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ở: .
- Nếu mọi : tăng bất kỳ biến ngoài cơ sở nào cũng không làm tăng, nên đỉnh hiện tại tối ưu (vì 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 có (biến vào). Tăng từ trong khi giữ các biến ngoài cơ sở khác bằng ; mỗi biến cơ sở giảm tuyến tính. Biến chạm đầu tiên (kiểm tra tỉ số nhỏ nhất trên các hàng ) là biến ra. Hoán đổi vai trò hai biến: đó là đi dọc một cạnh của sang đỉnh kề, không giảm.
- Nếu không hàng nào có , ta tăng mãi được: LP không bị chặn.
Pha 1: khi gốc toạ độ không khả thi. Nếu có thì vi phạm ràng buộc. Ta thêm một biến phụ vào mọi ràng buộc: , rồi giải LP phụ "cực đại ". Một lần xoay đưa vào cơ sở tại hàng có nhỏ nhất là đã có đỉnh khả thi của LP phụ. Nếu tối ưu của LP phụ có thì bài gốc vô nghiệm; ngược lại đẩy 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):
- Đối ngẫu yếu: mọi khả thi của (P) và khả thi của (D) thoả . Trực giác: là "hệ số nhân" cho ràng buộc ; cộng các ràng buộc theo hệ số mà trội hơn 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 của (D).
- Lỏng bù (complementary slackness): tại cặp tối ưu, thì ràng buộc của (P) chặt, và thì ràng buộc 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 ), 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
Miền khả thi là ngũ giác với các đỉnh :
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ù . Bảng ban đầu (cơ sở là các biến bù, hàng lưu ):
| cơ sở | vế phải | |||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 4 | |
| 1 | 3 | 0 | 1 | 0 | 6 | |
| 1 | 0 | 0 | 0 | 1 | 3 | |
| -3 | -2 | 0 | 0 | 0 | 0 |
Bước 1. Hệ số âm nhất ở hàng là (cột ): vào. Tỉ số: , nhỏ nhất là ở hàng : ra. Xoay quanh ô :
| cơ sở | vế phải | |||||
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | -1 | 1 | |
| 0 | 3 | 0 | 1 | -1 | 3 | |
| 1 | 0 | 0 | 0 | 1 | 3 | |
| 0 | -2 | 0 | 0 | 3 | 9 |
Ta đang ở đỉnh với .
Bước 2. Còn hệ số ở cột : vào. Tỉ số: (hàng ) và (hàng ), hoà; chọn hàng có chỉ số biến nhỏ hơn là . Xoay quanh ô :
| cơ sở | vế phải | |||||
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | -1 | 1 | |
| 0 | 0 | -3 | 1 | 2 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 3 | |
| 0 | 0 | 2 | 0 | 1 | 11 |
Hàng không còn hệ số âm: tối ưu tại . Lưu ý dù là biến cơ sở: đỉnh 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 dưới các cột là . Kiểm tra: đối ngẫu là với , , . Với : hai ràng buộc thành , , và , đúng bằng giá trị bài gốc. Nghĩa là: lấy cộng được , một chứng chỉ rằng không thể vượt .
Cài đặt
Cài đặt dưới đây dùng bảng : hàng ràng buộc, hàng là mục tiêu, hàng là mục tiêu của pha 1; cột là biến phụ , cột 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 , ma trận , vector , vector , in giá trị tối ưu và nghiệm, hoặc INFEASIBLE / UNBOUNDED.
#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');
}
}
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 | ||
| Toàn bộ Simplex (thực tế) | thường bước, tức khoảng | |
| Toàn bộ Simplex (xấu nhất) | mũ (ví dụ khối Klee-Minty) |
Vì sao mỗi bước ? Bước xoay cập nhật toàn bộ bảng , mỗi ô một phép nhân trừ. Tìm cột vào , tìm hàng ra .
Vì sao số bước khó đoán? Mỗi bước đi sang một đỉnh kề có 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 đỉ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] >= 0thay vì>= -EPSkhiến Simplex xoay mãi vì những hệ số cỡ do sai số làm tròn. Mọi phép so sánh với trong bảng phải có ngưỡng. - Quên pha 1 khi có : bắt đầu từ 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 thường cho , 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 . Biến được phép âm mà không tách thì Simplex ngầm chặn nó ở 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ó (lớn hơn EPS). Lấy cả hàng làm tỉ số âm hoặc chia cho , đư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 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ó 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 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 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 : đổ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ỹ đủ điểm kinh nghiệm và đô-la với tổng số ngày nhỏ nhất. Đây là LP với biến và ràng buộc; đối ngẫu chỉ có 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ừ đế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.
Bình luận