Bài giảng Giải thuật nâng cao - Quy hoạch tuyến tính - Ngô Quốc Việt

QUY HOẠCH TUYẾN TÍNH 
TS. NGÔ QUỐC VIỆT 
2015 
Nội dung 
1. Giới thiệu 
2. Giải quy hoạch tuyến tính dựa trên đồ thị 
3. Bài toán đối ngẫu 
4. Giải thuật Simplex 
5. Max-Flow dựa trên LP 
Giải thuật nâng cao-Quy hoạch tuyến tính 2 
Giới thiệu 
 Mục tiêu kinh doanh thường: maximizing profit 
hoặc minimizing costs. 
 Quy hoạch tuyến tính (Linear programming) sử 
dụng các quan hệ tuyến tính để biểu diễn các quyết 
định, với business objective, và các constraints. 
 Linear Programming model tìm maximize hoặc 
minimize linear function, thỏa mãn linear 
constraints. 
Giải thuật nâng cao-Quy hoạch tuyến tính 3 
Quy hoạch tuyến tính 
• Nhiều vấn đề thực tế có dạng linear 
programming. 
• Các vấn đề thực khác có thể xấp xỉ theo linear 
models. 
• Có nhiều ứng dụng trong : 
• Manufacturing, Marketing, Finance (investment), 
Advertising, Agriculture, Energy, etc. 
• Có nhiều kỹ thuật hiệu quả nhằm tìm nghiệm 
của linear programming models. 
Giải thuật nâng cao-Quy hoạch tuyến tính 4 
Giới thiệu 
Chuyển vấn đề sang LP 
1. Xác định vấn đề có thể giải bằng linear 
programming. 
2. Lập mô hình toán của unstructured 
problem theo các bước 
a. Xác định hàm mục tiêu 
b. Xác định các biến quyết định 
c. Xác định ràng buộc 
3. Giải mô hình dựa trên một số kỹ thuật. 
Giải thuật nâng cao-Quy hoạch tuyến tính 5 
Quy hoạch tuyến tính-ví dụ 1 
MAX 4X1 + 7X3 - 6X4 
 2X1 + 3X2 - 2X4 = 20 
 -2X2 + 9X3 + 7X4  10 
 -2X1 + 3X2 + 4X3 + 8X4  35 
 X2  5 
 Mọi X  0 
Giải thuật nâng cao-Quy hoạch tuyến tính 6 
Ràng buộc 
X1  0, X2  0, X3  0, X4  0 
Quy hoạch tuyến tính-ví dụ 2 
• Resource 40 giờ công mỗi ngày 
 Availability: 120 lbs đất sét 
• Decision x1 = số chén (bowl) sản xuất mỗi ngày 
 Variables: x2 = số ca (mug) sản xuất mỗi ngày 
• Objective Maximize Z = $40x1 + $50x2 
 Function: với Z = lợi nhuận mỗi ngày 
• Resource 1x1 + 2x2  40 (giờ công) 
 Constraints: 4x1 + 3x2  120 lbs đất sét 
• Non-Negativity x1  0; x2  0 
 Constraints: 
Giải thuật nâng cao-Quy hoạch tuyến tính 7 
Quy hoạch tuyến tính-ví dụ 2 (tt) 
Mô hình tuyến tính 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Giải thuật nâng cao-Quy hoạch tuyến tính 8 
Quy hoạch tuyến tính-ví dụ 3 
• Post office cần số nhân viên theo từng ngày trong 
tuần, được xác định trong bảng cụ thể. 
• Quy định: mỗi nhân viên phải làm 5 ngày liên tục, 
rồi nghỉ hai ngày. 
• Yêu cầu: lập LP sao cho post office có thể sử dụng ít 
nhân viên nhất. 
Giải thuật nâng cao-Quy hoạch tuyến tính 9 
Quy hoạch tuyến tính-ví dụ 3 
• Đặt: x1, x2,, x7 là số nhân viên làm việc bắt đầu tương 
ứng vào Monday, Tue, , Sun (x1 làm từ Mon đến Fri) 
• Hàm mục tiêu: 
z=Min (x1+x2++x7) 
• Ràng buộc: 
 x1+ +x4+x5+x6+x7 >=17 
 x1+ x2+ +x5+x6+x7 >=13 
 x1+x2+x3+ +x6+x7 >=15 
 x1+x2+x3+ x4+ +x7 >=19 
 x1+x2+x3+x4+x5 >=14 
 x2+x3+x4+x5+x6 >=16 
 x3+x4+x5+x6+x7 >=11 
 Giải thuật nâng cao-Quy hoạch tuyến tính 10 
Các thành phần của mô hình 
• Các biến quyết định – ký hiệu toán biểu diễn các 
trạng thái/mức độ của một vấn đề cụ thể. Các biến 
quyết định là độc lập 
• Hàm mục tiêu – quan hệ tuyến tính mô tả mục tiêu, 
theo các decision variable – yêu cầu là cần cực 
đại/tiểu hàm này. 
• Ràng buộc – các yêu cầu hay hạn chế ràng buộc bài 
toán, thể hiện quan hệ tuyến tính giữa các decision 
variable. 
• Tham số - các hệ số và hằng của hàm mục tiêu và 
ràng buộc. 
 Giải thuật nâng cao-Quy hoạch tuyến tính 11 
Phương pháp đồ thị cho LP 
• Phương pháp graphical phù hợp cho các mô 
hình linear programming chỉ có hai decision 
variables 
• Phương pháp graphical thể hiện trực quan 
lời giải của linear programming problem. 
Giải thuật nâng cao-Quy hoạch tuyến tính 12 
Phương pháp đồ thị cho LP 
• Xét ví dụ 2 
Giải thuật nâng cao-Quy hoạch tuyến tính 13 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
X1: số bowl 
X2: số mug 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 14 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Đồ thị ràng buộc giờ công 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 15 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Vùng ràng buộc giờ công 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 16 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Vùng ràng buộc đất sét 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 17 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Hai ràng buộc 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 18 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Vùng nghiệm 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 19 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Đường giá trị hàm mục tiêu với Z =800 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 20 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Các đường khác của hàm mục tiêu 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 21 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Điểm tối ưu 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 22 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Các tọa độ của lời giải tối ưu 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 23 
Maximize Z = $40x1 + $50x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Nghiệm tại các đỉnh 
Phương pháp đồ thị cho LP (tt) 
Giải thuật nâng cao-Quy hoạch tuyến tính 24 
Maximize Z = $70x1 + $20x2 
Thỏa mãn: 1x1 + 2x2  40 
 4x1 + 3x2  120 
 x1, x2  0 
Nghiệm tối ưu với Z = 70x1 + 20x2 
Các biến hỗ trợ 
 Dạng chuẩn: mọi ràng buộc có dạng phương trình. 
 Biến slack được thêm vào ràng buộc bất phương 
trình để chuyển thành phương trình. 
 Biến hỗ trợ slack thường biểu diễn tài nguyên 
không sử dụng. 
 Biến slack không đóng góp vào giá trị hàm mục 
tiêu. 
Giải thuật nâng cao-Quy hoạch tuyến tính 25 
Mô hình LP: dạng chuẩn 
• Xét ví dụ 2 
Giải thuật nâng cao-Quy hoạch tuyến tính 26 
Max Z = 40x1 + 50x2 + 0s1 + 0s2 
Thỏa :1x1 + 2x2 + s1 = 40 
 4x1 + 3x2 + s2 = 120 
 x1, x2, s1, s2  0 
 x1 = số bowl 
 x2 = số mug 
 s1, s2: các biến slack 
Dạng chuẩn 
Mọi biến không âm 
Các ràng buộc là bất phương trình 
Hệ quy hoạch tuyến tính chuẩn tổng quát 
• Cho 𝑏 = 𝑏1,  , 𝑏𝑚
𝑇 , và 𝑐 = 𝑐1,  , 𝑐𝑛
𝑇, và ma trận 
𝐴 =
𝑎11 ⋯ 𝑎1𝑛
⋮
𝑎𝑚1 ⋯ 𝑎𝑚𝑛
Vấn đề Max chuẩn: tìm 𝑥 = 𝑥1,  , 𝑥𝑛
𝑇 sao cho 𝑀𝑎𝑥 𝑐𝑇𝑥 = 𝑐1𝑥1 +
⋯+ 𝑐𝑛𝑥𝑛, thỏa các ràng buộc 
𝑎11𝑥1 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 
⋮ 
𝑎𝑚1𝑥1 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 
𝑥1 ≥ 0, , 𝑥𝑚 ≥ 0 
Vấn đề Min chuẩn: 𝑀𝑖𝑛 𝑐𝑇𝑥 = 𝑐1𝑥1 +⋯+ 𝑐𝑛𝑥𝑛, thỏa các ràng buộc 
𝑎11𝑥1 +⋯+ 𝑎1𝑛𝑥𝑛 ≥ 𝑏1 
⋮ 
𝑎𝑚1𝑥1 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≥ 𝑏𝑚 
𝑥1 ≥ 0, , 𝑥𝑚 ≥ 0 
Giải thuật nâng cao-Quy hoạch tuyến tính 27 
Có thể chuyển từ MIN sang MAX & ngược lại (duality) 
Quy hoạch tuyến tính-ví dụ 4 
• Cho m loại thực phẩm 𝐹1,  , 𝐹𝑚 cung cấp n chất dinh 
dưỡng 𝑁1,  , 𝑁𝑛. Đặt cj, là yêu cầu tối thiểu chất dinh 
dưỡng Nj hàng ngày, bj là giá mỗi đơn vị thực phẩm Fi. 
Đặt aij là lượng dinh dưỡng Nj có trong thực phẩm Fi, yi 
là số lượng thực phẩm Fi cần mua mỗi ngày. 
• Yêu cầu: cung cấp đủ chất với chi phí tối thiểu. 
• Hàm mục tiêu 
𝑍 = 𝑏1𝑦1 +⋯+ 𝑏𝑚𝑦𝑚 
• Dinh dưỡng Nj có trong thực phẩm mua mỗi ngày 
𝑎1𝑗𝑦1 +⋯+ 𝑎𝑚𝑗𝑦𝑚, 𝑗 = 1𝑛 
• Ràng buộc 
𝑎1𝑗𝑦1 +⋯+ 𝑎𝑚𝑗𝑦𝑚 ≥ 𝑐𝑗 , 𝑗 = 1𝑛 
𝑦1 ≥ 0, , 𝑦𝑚 ≥ 0 
Giải thuật nâng cao-Quy hoạch tuyến tính 28 
Định lý cơ bản 
• Định lý cơ bản: Cho 𝛺 = 𝑥 | 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 . Nếu 
min(cx) với 𝑥 ∈ 𝛺 có nghiệm tối ưu, thì nghiệm nằm 
trên các đỉnh của 𝛺. 
• 
ntalTheoremOfLinearProgramming/ hoặc 
• 
remofLinearAlgebra.html 
• Điểm cực trị (đỉnh) của convex không thể viết 
dạng 𝑎 + 𝑏 /2 
Giải thuật nâng cao-Quy hoạch tuyến tính 29 
Nghiệm cơ sở 
• Một đỉnh được gọi là nghiệm cơ sở (basis feasible 
solution) 
• Tập chỉ mục các tập con độc lập tuyến tính của những 
vector cột được gọi là cơ sở 
• Cơ sở là feasible nếu tồn tại nghiệm cơ sở x sao cho 
𝑗 | 𝑥𝑗 > 0 ⊂ 𝐼 
• Ký hiệu: 𝐴𝐼 = 𝑎𝑗 , 𝑖 ∈ 𝐼 . Tập chỉ mục I là feasible basis 
nếu và chỉ nếu 𝑟𝑎𝑛𝑘 𝐴𝐼 = 𝑚 = 𝐼 và 𝐴𝐼
−1𝑏 ≥ 0 
Có thể giải LP bằng cách duyệt qua mọi đỉnh và chọn đỉnh 
tốt nhất  độ phức tạp? 
Xét mọi ràng buộc dạng: 0 ≤ 𝑥𝑖 ≤ 1  sẽ có 2
𝑛 điểm góc. 
Giải thuật nâng cao-Quy hoạch tuyến tính 30 
Bài tập 
1. Giải các bài tập sau 
2. Tìm hiểu & trình bày quy hoạch tuyến tính trên MATLAB 
Giải thuật nâng cao-Quy hoạch tuyến tính 31 
Duality 
• Mọi mô hình tuyến tính đều có mô hình tuyến tính đối ngẫu. 
• Ví dụ: tìm Max (x1+x2) thỏa 
Chuyển thành dạng tìm 𝑀𝑖𝑛(4𝑦1 + 12𝑦2 + 𝑦3) thỏa 
Giải thuật nâng cao-Quy hoạch tuyến tính 32 
Duality-tổng quát 
• Vấn đề Max chuẩn, và Min chuẩn có thể biểu diễn 
tổng quát như sau 
• Ví dụ 
Giải thuật nâng cao-Quy hoạch tuyến tính 33 
Các phương pháp trong LP 
• Giải thuật Simplex 
• Cài đặt đơn giản, tuy nhiên trong một số trường 
hợp giải thuật có độ phức tạp lũy thừa 
• Các phương pháp Polynomial 
• Phương pháp Ellipsoid (Leonid Khachiyan 1979): 
mang tính lý thuyết 
• Phương pháp Narendra Karmarkar (1984 ), có 
tính thực tế. 
• Các phương pháp xấp xỉ (bài giảng kế) 
Giải thuật nâng cao-Quy hoạch tuyến tính 34 
Giải thuật Simplex cho LP 
• Giải các vấn đề LP có nhiều hơn 2 biến quyết định 
(George Dantzig, 1949). 
• Dạng giải thuật leo đồi, tối ưu cục bộ. 
• Giải thuật có độ phức tạp đa thức 
• Bắt đầu tại điểm góc bất kỳ. “Di chuyển” đến từng 
điểm góc, và xác định giá trị hàm mục tiêu. Giữ lại 
điểm góc có giá trị hàm mục tiêu tốt hơn 
• Lặp đến khi không còn điểm góc kề có giá trị hàm 
mục tiêu tốt hơn. 
• Cài đặt: sử dụng cấu trúc bảng/mảng 2 chiều 
Giải thuật nâng cao-Quy hoạch tuyến tính 35 
Giải thuật Simplex cho LP 
• Phát sinh chuỗi các nghiệm dạng bảng. Xem 
xét hàng cuối của bảng, để xác định là nghiệm 
tối ưu. Mỗi bảng ứng với một điểm góc của 
không gian nghiệm. Bảng đầu tiên ứng với 
origin. Các bảng sau có được bằng cách dời 
tới điểm góc kề theo hướng sinh ra highest 
(smallest) rate of profit (cost). Quá trình tiếp 
tục khi positive (negative) rate of profit 
(cost) vẫn còn. 
Giải thuật nâng cao-Quy hoạch tuyến tính 36 
Giải thuật Simplex cho LP 
1. Đổi mọi ràng buộc của LP sang dạng chuẩn 
(phương trình, có bổ sung thêm biến hỗ trợ) 
2. Tạo bảng simplex 
 Chuyển mọi giá trị của bước 1 vào bảng. 
3. Xác định nghiệm tối ưu của bảng simplex bằng 
cách thực hiện simplex method algorithm 
Giải thuật nâng cao-Quy hoạch tuyến tính 37 
Giải thuật Simplex cho LP 
Giải thuật nâng cao-Quy hoạch tuyến tính 38 
 Khởi tạo vòng lặp: bao gồm tìm nghiệm đầu tiên 
 Optimality test: kiểm tra nghiệm tối ưu ? 
 if no if yes stop 
 Iteration: Lặp để xác định nghiệm tốt hơn 
Giải thuật Simplex: bước 1 
• Chuyển LP sang dạng chuẩn (mọi ràng buộc có dạng 
phương trình) 
• Ví dụ: 
• Dạng <=: x1 + x2 ≤ 3  x1 + x2 + s1 = 3 
• Dạng >=: x1 + x2 ≥ 3  x1 + x2 - s2 + A2= 3 
• Dạng =: x1 + x2 = 3  x1 + x2 + A3 = 3 
Giải thuật nâng cao-Quy hoạch tuyến tính 39 
Giải thuật Simplex: bước 1 
• Đổi các bất phương trình ràng buộc sang dạng 
phương trình bằng cách thêm các biến hỗ trợ. 
Giải thuật nâng cao-Quy hoạch tuyến tính 40 
Dạng LP gốc Dạng chuẩn (hay 
Augmented) 
Max 𝑍 = 3𝑥1+ 5𝑥2, 
Ràng buộc 
𝑥1 ≤ 4 
2𝑥2 ≤ 12 
3𝑥1 + 2𝑥2 ≤ 18 
𝑍 − 3𝑥1− 5𝑥2 = 0 
Ràng buộc 
𝑥1 + 𝑠1 = 4 
2𝑥2 + 𝑠2 = 12 
3𝑥1 + 2𝑥2 + 𝑠3 = 18 
Giải thuật Simplex: bước 2 
Giải thuật nâng cao-Quy hoạch tuyến tính 41 
2. Initial tableau 
Pivot column 
Pivot row 
Pivot 
number 
Entering 
variable 
Leaving 
variable 
Giải thuật Simplex: bước 2 
• Nghiệm ban đầu ứng với giá trị của các biến quyết 
định (x1, x2 trong ví dụ đang xét) có giá trị zero. 
X1 = 0, X2 = 0, S1 = 4, S2 = 12, S3 = 18, Z=0. 
• X1, X2: các nonbasic variables; S1, S2, S3: các basic 
variables (trong giải thuật Simplex). 
Giải thuật nâng cao-Quy hoạch tuyến tính 42 
Giải thuật Simplex: bước 3 
3. Kiểm tra tối ưu 
Trường hợp 1: Max 
• Nghiệm là tối ưu nếu mọi hệ số của hàng hàm mục 
tiêu (hàng cuối cùng) là nonnegative 
Trường hợp 2: Min 
• Nghiệm là tối ưu nếu mọi hệ số của hàng hàm mục 
tiêu (hàng cuối cùng) là nonpositive 
Hàng cuối trong vd đang xét còn giá trị âm (-3 và -5), 
vì vậy (0, 0, 4, 12, 18) không là nghiệm tối ưu. 
Giải thuật nâng cao-Quy hoạch tuyến tính 43 
Giải thuật Simplex: bước 4 
1. Chọn biến entering 
• Vấn đề Max: biến có giá trị âm nhất 
• Vấn đề Min: biến có giá trị dương nhất 
Chọn -5 (biến X2) trong ví dụ đang xét. 
2. Chọn biến leaving (dựa trên kiểm tra tỉ lệ nhỏ 
nhất) 
Giải thuật nâng cao-Quy hoạch tuyến tính 44 
Basic 
variable 
Entering 
variable X2 
(1) 
RHS 
(2) 
Ratio 
(2)(1) 
S1 0 4 None 
S2 
Leaving 
2 12 6 
Smallest ratio 
S3 2 18 9 
Giải thuật Simplex: bước 4 
3. Tìm nghiệm, bằng các loại trừ dòng theo cách sau 
1. New pivot row = old pivot row  pivot number 
Giải thuật nâng cao-Quy hoạch tuyến tính 45 
Basic 
variable 
X1 X2 S1 S2 S3 RHS 
S1 
X2 0 1 0 1/2 0 6 
S3 
Z 
X2 trở thành basic variables list 
thay cho S2 
Giải thuật Simplex: bước 4 
2. Cập nhật các hàng còn lại trong bảng theo nguyên tắc 
 New row = old row – the coefficient of this row in the pivot 
 column (new pivot row) 
Hàng S1 
 1 0 1 0 0 4 
 - 
 0 (0 1 0 1/2 0 6) 
 1 0 1 0 0 4 
Hàng S3 
 3 2 0 0 1 18 
 - 
 2 (0 1 0 1/2 0 6) 
 3 0 0 -1 1 6 
 Hàng Z 
 -3 -5 0 0 0 0 
- 
 -5(0 1 0 1/2 0 6) 
 -3 0 0 5/2 0 30 
Giải thuật nâng cao-Quy hoạch tuyến tính 46 
Giải thuật Simplex: bước 4 
• Nghiệm chưa tối ưu (còn giá trị -3 ở hàng Z) 
• Tiếp tục lặp 
Giải thuật nâng cao-Quy hoạch tuyến tính 47 
Basic 
variable 
X1 X2 S1 S2 S3 RHS 
S1 1 0 1 0 0 4 
X2 0 1 0 1/2 0 6 
S3 3 0 0 -1 1 6 
Z -3 0 0 5/2 0 30 
-3: giá trị âm nhất 
X1: trở thành entering 
Ratio: 6/3=2, nhỏ nhất 
S3: trở thành leaving 
Giải thuật Simplex: bước 4 
• Thực hiện tương tự 
• Nghiệm tối ưu: X1 = 2, X2 = 6 and S1 = 2; non-basic 
variables are S2 = S3 = 0, Z = 36. 
Giải thuật nâng cao-Quy hoạch tuyến tính 48 
Basic 
variable 
X1 X2 S1 S2 S3 RHS 
S1 0 0 1 1/3 -1/3 2 
X2 0 1 0 1/2 0 6 
X1 1 0 0 -1/3 1/3 2 
Z 0 0 0 3/2 1 36 
Giải thuật Simplex: nhận xét 
1. Giao của basic variable với nó luôn bằng 1 và các giá trị 
còn lại của cột là zero. 
2. Hàng Z: chứa các biến non-basic. Các biến basic có hệ số 
zero trong hàng này. 
3. Nếu non-basic variables có hệ số zero trong bảng sau 
cùng (bảng nghiệm tối ưu), thì có nhiều nghiệm tối ưu. 
4. Khi xác định ”biến ra” của bảng, nếu không có positive 
ratio (mọi giá trị trong pivot column là <= zero), thì 
nghiệm là unbounded. 
5. Nếu có nhiều hơn một “biến vào” (có cùng âm nhất hay 
dương nhất), thì chọn ngẫu nhiên một biết trong số đó. 
6. Nếu có nhiều hơn một “biến ra” (cùng tỉ lệ), chọn bất kỳ 
biến nào. 
7. Nghiệm bao gồm biến basic có giá trị zero được gọi là 
nghiệm suy biến (degenerate solution). 
Giải thuật nâng cao-Quy hoạch tuyến tính 49 
Giải thuật Simplex: mã nguồn 
• Hãy thực nghiệm giải thuật Simplex với các ngôn 
ngữ JAVA, C# hoặc MATLAB. 
• Giải bài toán luồng cực đại dựa trên LP 
Giải thuật nâng cao-Quy hoạch tuyến tính 50 
Giới thiệu 
Phân tích & Thiết kế giải thuật - Luồng cực đại 
• Luồng cực đại là một trong những bài toán tối ưu 
trên đồ thị có hướng 𝐺 = (𝑉, 𝐸) 
• Ứng dụng nhiều trên các mạng (đồ thị có hướng): 
internet, điện thoại, giao thông, điện, nước, gas, v.v. 
• Được giới thiệu vào 1956 bởi Lester Randolph 
Ford và Delbert Ray Fulkerson. 
• Bài toán tương đương: tìm lát cắt tối tiểu (min cut 
problem) trên đồ thị (định lý Max-flow Min-cut). 
51 
Định nghĩa bài toán luồng cực đại 
Phân tích & Thiết kế giải thuật - Luồng cực đại 
• Cho mạng 𝐺 = (𝑉, 𝐸, 𝑐, 𝑠, 𝑡) 
• Mỗi cạnh e = (𝑢, 𝑣) ∈ 𝐸 có trọng số biểu diễn sức chứa/độ 
tải tối đa 𝑐(𝑢, 𝑣). 
• Có duy nhất một đỉnh s (đỉnh nguồn) không có cung vào, và 
một đỉnh t không có cung ra (đỉnh đích) 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 10 
 10 
 10 15 4 
 4 
Capacity 
52 
Định nghĩa bài toán luồng cực đại 
Phân tích & Thiết kế giải thuật - Luồng cực đại 
• Ký hiệu: 
• 𝑊− 𝑣 = 𝑢, 𝑣 ∈ 𝐸 ∶ 𝑢 ∈ 𝑉 . Tập các cung đi vào đỉnh v. 
• 𝑊+ 𝑣 = 𝑣, 𝑢 ∈ 𝐸 ∶ 𝑢 ∈ 𝑉 . Tập các cung đi ra đỉnh v. 
• Luồng f trong mạng 𝐺 là ánh xạ 𝑓: 𝐸 → 𝑅 thỏa 
• Capacity constraint: 0 𝑓(𝑒)  𝑐(𝑒) 
• Flow conversion (tổng luồng vào bằng tổng luồng ra): 
∀𝑣 ≠ 𝑠, 𝑡 𝑓 𝑒 =𝑒∈𝑊− 𝑣 𝑓 𝑒𝑒∈𝑊+ 𝑣 ; 
 𝑓 𝑢, 𝑣 = 0𝑣∈𝑉,𝑢≠𝑠,𝑣≠𝑡 
• Skew Symmetry: ∀𝑢, 𝑣 ∈ 𝑉, 𝑓 𝑢, 𝑣 = −𝑓 𝑣, 𝑢 
• Ký hiệu: used/capacity cho mạng luồng 
53 
Định nghĩa bài toán luồng cực đại 
Phân tích & Thiết kế giải thuật - Luồng cực đại 
• Giá trị luồng xác định bởi 
𝑓 = 𝑓 𝑠, 𝑣 =
𝑣∈𝑉
 𝑓 𝑣, 𝑡
𝑣∈𝑉
• Bài toán luồng cực đại nhằm xác định luồng sao cho 
max 𝑓 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 10 
 10 
 10 15 4 
 4 
10 
9 
9 
14 
14 
4 10 
4 8 9 
1 
0 0 
Value = 28 
0 0 
Capacity 
Flow 
54 
Định nghĩa bài toán luồng cực đại 
Phân tích & Thiết kế giải thuật - Luồng cực đại 
𝑓 = 𝑓 𝑠, 2 + 𝑓 𝑠, 3 + 𝑓 𝑠, 4 + 𝑓 𝑠, 5 + 𝑓 𝑠, 6
+ 𝑓 𝑠, 7 + 𝑓 𝑠, 𝑡
= 10 + 4 + 14 + 0 + 0 + 0 + 0 = 28 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 10 
 10 
 10 15 4 
 4 
10 9 
14 
14 
4 10 
4 8 9 
1 
0 0 
Value = 28 
0 0 
Capacity 
Flow 
55 
MAX-FLOW và LP 
• Đặt 𝑥𝑢𝑣 thể hiện luồng cho cạnh nối đỉnh u và v. 
• Hàm mục tiêu: 
𝑀𝑎𝑥 𝑥𝑢𝑡
𝑢
− 𝑥𝑡𝑢
𝑢
• Ràng buộc: 
• Giá trị các biến 
0 ≤ 𝑥𝑢𝑣 ≤ 𝑐 𝑢, 𝑣 
• Luồng vào = luồng ra. 
∀𝑣 ∉ 𝑠, 𝑡 , 𝑥𝑢𝑣
𝑢
= 𝑥𝑣𝑢
𝑢
Giải thuật nâng cao-Quy hoạch tuyến tính 56 
MAX-FLOW và LP 
• Hàm mục tiêu: 𝑀𝑎𝑥 𝑥𝑑𝑡 + 𝑥𝑐𝑡 
• Ràng buộc: 
0 ≤ 𝑥𝑠𝑎 ≤ 4, 0 ≤ 𝑥𝑎𝑐 ≤ 3, 
𝑥𝑠𝑎 = 𝑥𝑎𝑐 , 𝑥𝑠𝑏 + 𝑥𝑐𝑏 = 𝑥𝑏𝑐 + 𝑥𝑏𝑑 , 𝑥𝑎𝑐 + 𝑥𝑏𝑐
= 𝑥𝑐𝑏 + 𝑥𝑐𝑡 , 𝑥𝑏𝑑 = 𝑥𝑑𝑡 
Giải thuật nâng cao-Quy hoạch tuyến tính 57 
Tóm tắt 
• LP Tìm maximize hoặc minimize linear function, 
thỏa mãn linear constraints. 
• Một số giải thuật tiêu biểu 
• Simplex (1940s): không luôn thời gian đa thức 
• Ellipsoid (1980s): thời gian đa thức, nhưng chậm. 
• Karmarkar: thời gian đa thức. Tốt hơn Ellipsoid nhiều. 
• Một số gói thương mại: LINDO, CPLEX, Solver (Excel). 
Giải thuật nâng cao-Quy hoạch tuyến tính 58