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 Ràng buộc X2  5 Mọi X  0 X1  0, X2  0, X3  0, X4  0 Giải thuật nâng cao-Quy hoạch tuyến tính 6 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 X2: số mug Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 X1: số bowl Giải thuật nâng cao-Quy hoạch tuyến tính 13 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 14 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 15 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 16 Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Hai ràng buộc Giải thuật nâng cao-Quy hoạch tuyến tính 17 Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Vùng nghiệm Giải thuật nâng cao-Quy hoạch tuyến tính 18 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 19 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 20 Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Điểm tối ưu Giải thuật nâng cao-Quy hoạch tuyến tính 21 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 22 Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Nghiệm tại các đỉnh Giải thuật nâng cao-Quy hoạch tuyến tính 23 Phương pháp đồ thị cho LP (tt) 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 Giải thuật nâng cao-Quy hoạch tuyến tính 24 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 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 Giải thuật nâng cao-Quy hoạch tuyến tính 26 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 Có thể chuyển từ MIN sang MAX & ngược lại (duality) Giải thuật nâng cao-Quy hoạch tuyến tính 27 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 −1 nếu và chỉ nếu 푟푎푛푘 퐴퐼 = 푚 = 퐼 và 퐴퐼 푏 ≥ 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 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 nâng cao-Quy hoạch tuyến tính 38 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ợ. Dạng LP gốc Dạng chuẩn (hay Augmented) Max 푍 = 3푥1 + 5푥2, 푍 − 3푥1 − 5푥2 = 0 Ràng buộc Ràng buộc 푥1 ≤ 4 푥1 + 푠1 = 4 2푥2 ≤ 12 2푥2 + 푠2 = 12 3푥 + 2푥 ≤ 18 3푥 + 2푥 + 푠 = 18 1 2 1 2 3 Giải thuật nâng cao-Quy hoạch tuyến tính 40 Giải thuật Simplex: bước 2 Entering 2. Initial tableau variable Pivot row Leaving Pivot column variable Pivot number Giải thuật nâng cao-Quy hoạch tuyến tính 41 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) Basic Entering RHS Ratio variable variable X2 (1) (2) (2)(1) S1 0 4 None S2 2 12 6 Leaving Smallest ratio S3 2 18 9 Giải thuật nâng cao-Quy hoạch tuyến tính 44 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 Basic X1 X2 S1 S2 S3 RHS variable 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 nâng cao-Quy hoạch tuyến tính 45 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) Basic X1 X2 S1 S2 S3 RHS variable S 1 0 1 0 0 4 1 X 0 1 0 1/2 0 6 2 S 3 0 0 -1 1 6 3 Z -3 0 0 5/2 0 30 • Tiếp tục lặp -3: giá trị âm nhất Ratio: 6/3=2, nhỏ nhất X1: trở thành entering S3: trở thành leaving Giải thuật nâng cao-Quy hoạch tuyến tính 47 Giải thuật Simplex: bước 4 • Thực hiện tương tự Basic X1 X2 S1 S2 S3 RHS variable 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 • 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 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 • 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). Phân tích & Thiết kế giải thuật - Luồng cực đại 51 Định nghĩa bài toán 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) 2 9 5 10 4 15 15 10 s 5 3 8 6 10 t 4 6 15 Capacity 15 10 4 30 7 Phân tích & Thiết kế giải thuật - Luồng cực đại 52 Định nghĩa bài toán 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 Phân tích & Thiết kế giải thuật - Luồng cực đại 53 Định nghĩa bài toán9 luồng cực đại 2 9 5 10 1 9 10 15 4 0 15 0 10 4 8 9 s 5 3 8 6 10 t 4 10 4 0 6 15 0 10 Capacity 15 14 Value = 28 Flow 4 30 7 • Giá trị luồng xác định bởi 14 푓 = 푓 푠, 푣 = 푓 푣, 푡 푣∈푉 푣∈푉 • Bài toán luồng cực đại nhằm xác định luồng sao cho max 푓 Phân tích & Thiết kế giải thuật - Luồng cực đại 54 Định nghĩa bài toán luồng cực đại 2 9 5 10 1 9 10 15 15 0 4 0 10 4 8 9 s 5 3 8 6 10 t 4 10 4 0 6 15 0 10 Capacity 15 14 Value = 28 Flow 4 30 7 14 푓 = 푓 푠, 2 + 푓 푠, 3 + 푓 푠, 4 + 푓 푠, 5 + 푓 푠, 6 + 푓 푠, 7 + 푓 푠, 푡 = 10 + 4 + 14 + 0 + 0 + 0 + 0 = 28 Phân tích & Thiết kế giải thuật - Luồng cực đại 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