Sử dụng bộ giải trong Excel để tìm luồng lớn nhất 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.).

Hình thành mô hình

Mô hình chúng ta sẽ giải quyết trông như sau trong Excel.

Maximum Flow Problem in Excel

  1. Để hình thành bài toán lưu lượng cực đại này, hãy trả lời ba câu hỏi sau.

\ a. Các quyết định đượ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 luồ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ì? 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.

\ c. 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 lượng này. Lưu lượng tối đa bằng Lưu lượng ra khỏi nút S.

  1. Để làm cho mô hình dễ hiểu hơn, hãy đặt tên cho các phạm vi sau.

Range Name

Cells

From

B4:B15

To

C4:C15

Flow

D4:D15

Capacity

F4:F15

SupplyDemand

K5:K9

MaximumFlow

D17

  1. Chèn các chức năng sau.

Insert Functions

Thử và Lỗi

Với công thức này, việc phân tích bất kỳ dung dịch thử nào trở nên dễ dàng.

  1. Ví dụ, đường dẫn SADT với lưu lượng 2. Đường dẫn SCT với lưu lượng 4. Đường dẫn SBET với lưu lượng 2. Các đường dẫn này cho tổng lưu lượng là 8.

Trial Solution

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 sử dụng Excel Solver để 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.

Click Solver

Lưu ý: không tìm thấy nút Solver? Nhấp vào đây để tải phần bổ trợ Solver.

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.

Solver Parameters

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.

  1. Nhập MaximumFlow cho Mục tiêu.

  2. Nhấp vào Max.

  3. Nhập Luồng cho các ô có thể thay đổi.

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

Net Flow Constraint

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

Capacity Constraint

  1. 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’.

  2. Cuối cùng, nhấp vào Giải quyết.

Kết quả:

Solver Results

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

Maximum Flow Problem Result

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. Những đường dẫn này cho lưu lượng tối đa là 12.