Xây dựng mô hình | Phep thử va lôi sai | Giải quyết mô hình
Sử dụng bộ giải trong Excel để tìm lưu lượng cực đại từ nút S đến nút T trong một mạng có hướng. Các điểm trong mạng được gọi là các nút (S, A, B, C, D, E và T). Các đường trong mạng đượ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. Để hình thành điều này vấn đề dòng chảy tối đa , hãy trả lời ba câu hỏi sau.
Một. 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.
NS. Những ràng buộc đối với những quyết định này là gì? Lưu lượng ròng (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. Ngoài ra, mỗi hồ quang có một công suất cố định. Lưu lượng trên mỗi hồ quang nên nhỏ hơn công suất này.
NS. Thước đo tổng thể về hiệu suất cho những quyết định này là gì? Thước đo tổng thể của hiệu suất là lưu lượng tối đa, vì vậy mục tiêu là tối đa hóa số lượng này. Lưu lượng tối đa bằng Lưu lượng ra khỏi nút S.
2. Để làm cho mô hình dễ hiểu hơn, hãy tạo như sau phạm vi được đặt tên .
Tên phạm vi | Tế bào |
---|---|
Từ | B4: B15 |
Đến | C4: C15 |
Chảy | D4: D15 |
Sức chứa | F4: F15 |
Nguồn cung cấp | K5: K9 |
Lưu lượng cực đại | D17 |
3. Chèn các chức năng sau.
Giải thích: SUMIF các hàm tính toán Lưu lượng ròng của mỗi nút. Đối với nút A, hàm SUMIF đầu tiên tính tổng các giá trị trong cột Luồng với dấu 'A' trong cột Từ (Luồng ra). Hàm SUMIF thứ hai tính tổng các giá trị trong cột Luồng với dấu 'A' trong cột Tới (Luồng Vào). Luồng tối đa bằng giá trị trong ô I4, là luồng ra khỏi nút S. Vì nút A, B, C, D và E có Luồng thực bằng 0 nên Luồng ra từ nút S sẽ bằng Luồng vào của nút T.
Phep thử va lôi sai
Với công thức này, việc phân tích bất kỳ giải pháp thử nào trở nên dễ dàng.
1. Ví dụ: đường dẫn SADT với lưu lượng là 2. Đường dẫn SCT với lưu lượng là 4. Đường dẫn SBET với lưu lượng là 2. Các đường dẫn này cho tổng lưu lượng là 8.
làm cách nào để tạo một biểu đồ
Không nhất thiết phải sử dụng thử và sai. Tiếp theo chúng tôi sẽ mô tả cách Trình giải quyết Excel có thể được sử dụng để nhanh chóng tìm ra giải pháp tối ưu.
Giải quyết mô hình
Để tìm ra giải pháp tối ưu, hãy thực hiện các bước sau.
1. Trên tab Dữ liệu, trong nhóm Phân tích, hãy bấm Bộ giải.
Lưu ý: không tìm thấy nút Solver? Bấm vào đây để tải Giải pháp bổ trợ .
Nhập các thông số của bộ giải (đọc tiếp). Kết quả phải phù hợp với hình dưới đây.
Bạn có thể chọn nhập tên phạm vi hoặc nhấp vào các ô trong bảng tính.
2. Nhập MaximumFlow cho Mục tiêu.
3. Nhấp vào Max.
4. Nhập Luồng cho các ô có thể thay đổi.
5. Nhấp vào Thêm để nhập ràng buộc sau.
6. Nhấp vào Thêm để nhập ràng buộc sau.
7. Chọn 'Làm cho các biến không bị ràng buộc thành không phủ định' và chọn 'Simplex LP'.
8. Cuối cùng, nhấp vào Giải quyết.
Kết quả:
Giải pháp tối ưu:
Kết luận: đường đi SADT với lưu lượng 2. Đường đi SCT với lưu lượng 4. Đường dẫn SBET với lưu lượng 2. Đường dẫn SCET với lưu lượng 2. Đường đi SACET với lưu lượng 1. Đường dẫn SACDT với lưu lượng 1. Các đường dẫn này cho lưu lượng tối đa là 12.
Đi tới Chương tiếp theo: