Bài này này sẽ hướng dẫn các bạn tính toán luồng cực đại trong Excel.
Luồng cực đại
Sử dụng solver trong Excel để tìm luồng lớn nhất từ nút S đến nút T trong một đồ thị có hướng. Các điểm trong đồ thị được gọi là các nút (S, A, B, C, D, E và T). Các đường trong độ thị được gọi là cung (SA, SB, SC, AC, v.v.).
Xây dựng mô hình
Mô hình chúng ta sẽ giải quyết trông như sau trong Excel.
1. Để xây dựng bài toán này, chúng ta cần trả lời ba câu hỏi sau.
a. Các quyết định sẽ được thực hiện là gì? Đối với vấn đề này, chúng ta cần Excel để tìm luồng trên mỗi cung. Ví dụ, nếu lưu lượng trên SB là 2, ô D5 bằng 2.
b. Những ràng buộc đối với những quyết định này là gì? Net Flow (Flow Out – Flow In) của nút A, B, C, D và E phải bằng 0. Nói cách khác, Flow Out = Flow In.
c. Số liệu tổng thể về hiệu suất cho những quyết định này là gì? Số liệu tổng thể của hiệu suất là maximum flow, vì vậy mục tiêu là tối đa hóa số lượng này.
2. Để làm cho mô hình dễ hiểu hơn,
3. Thêm hàm
Phép thử và lỗi sai
1. Ví dụ: đường dẫn SADT với flow là 2. Đường dẫn SCT với flow là 4. Đường dẫn SBET với flow là 2. Các đường dẫn này cho total flow là 8.
Giải quyết mô hình
1. Trên tab Data, Solver
Nhập các thông số . Kết quả phải phù hợp với hình dưới đây.
2. Nhập MaximumFlow cho Objective.
3. Nhấp vào Max.
4. Nhập Flow vào Changing Variable Cells.
5. Nhấn Add .
6. Nhấn Add
7. Nhấn ‘Make Unconstrained Variables Non-Negative’ và chọn ‘Simplex LP’.
8. Nhấn Solve
Giải pháp tối ưu:
Kết luận: đường đi SADT với flow 2. Đường đi SCT với flow 4. Đường dẫn SBET với flow 2. Đường dẫn SCET với flow 2. Đường đi SACET với flow 1. Đường dẫn SACDT với flow 1. Các đường dẫn này cho total flow là 12.
Ngoài ra, bạn cũng có thể xem nhiều bài excel khác tại đây.
Câu hỏi thường gặp
Làm thế nào để xác định luồng cực đại trong Excel?
Bài viết hướng dẫn sử dụng Solver trong Excel để tìm luồng cực đại. Bạn cần thiết lập một mô hình thể hiện đồ thị luồng, sau đó sử dụng Solver để tối đa hóa tổng luồng.
Solver trong Excel hoạt động như thế nào trong bài toán này?
Solver được sử dụng để tìm các giá trị luồng trên mỗi cung sao cho tổng luồng tối đa, đồng thời thỏa mãn điều kiện ràng buộc: tổng luồng vào bằng tổng luồng ra tại mỗi nút (trừ nguồn và đích).
Tôi cần chuẩn bị dữ liệu gì trước khi sử dụng Solver?
Bạn cần chuẩn bị một bảng dữ liệu trong Excel thể hiện đồ thị luồng với các nút, cung và dung lượng của mỗi cung. Mô hình cần xác định rõ biến quyết định (luồng trên mỗi cung), hàm mục tiêu (tối đa hóa tổng luồng) và các ràng buộc (điều kiện cân bằng luồng tại mỗi nút).
