300 Ví Dụ

Vấn đề dòng chảy tối đa

Maximum Flow Problem

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.





Sự cố dòng tối đa 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.

Chèn hàm

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.

Giải pháp thử nghiệm

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.

Nhấp vào Trình giải quyết

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.

Tham số bộ giải

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.

Ràng buộc dòng chảy ròng

6. Nhấp vào Thêm để nhập ràng buộc sau.

Giới hạn năng lực

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 kết quả

Giải pháp tối ưu:

Kết quả vấn đề về luồng tối đa

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.

5/7 Hoàn thành! Tìm hiểu thêm về trình giải quyết>
Đi tới Chương tiếp theo: Phân tích ToolPak



^