›
›

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

pdf 58 trang hapham 60
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải thuật nâng cao - Quy hoạch tuyến tính - Ngô Quốc Việt", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_giai_thuat_nang_cao_quy_hoach_tuyen_tinh_ngo_quoc.pdf

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

  1. QUY HOẠCH TUYẾN TÍNH TS. NGÔ QUỐC VIỆT 2015
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  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 Đồ thị ràng buộc giờ công Giải thuật nâng cao-Quy hoạch tuyến tính 14
  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 giờ công Giải thuật nâng cao-Quy hoạch tuyến tính 15
  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 Vùng ràng buộc đất sét Giải thuật nâng cao-Quy hoạch tuyến tính 16
  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 Hai ràng buộc Giải thuật nâng cao-Quy hoạch tuyến tính 17
  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 Vùng nghiệm Giải thuật nâng cao-Quy hoạch tuyến tính 18
  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 Đườ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
  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 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
  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 Điểm tối ưu Giải thuật nâng cao-Quy hoạch tuyến tính 21
  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 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. Đị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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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 - 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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
  50. 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
  51. 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
  52. Đị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
  53. Đị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
  54. Đị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
  55. Đị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
  56. 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
  57. 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
  58. 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