Bài giảng Giải thuật nâng cao - Quy hoạch tuyến tính

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