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.
| Tham gia kênh Telegram của AnonyViet 👉 Link 👈 |
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.
