Bài này này sẽ hướng dẫn các bạn tính toán đường đi ngắn nhấn trong Excel.
Tìm đường đi ngắn nhất
Sử dụng solveri trong Excel để tìm đường đi ngắn nhất từ nút S đến nút T trong đồ thị vô 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 về con đường ngắn nhất này, chúng ta phải 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 xem một cung có nằm trên đường ngắn nhất hay không (Yes= 1, No= 0). Ví dụ: nếu SB là một phần của đường đi ngắn nhất, ô F5 bằng 1. Nếu không, ô F5 bằng 0.
b. Những ràng buộc đối với những quyết định này là gì?Net Flow (Net Flow) của mỗi nút phải bằng Supply/Demand. Nút S chỉ nên có một cung đi ra (Net Flow = 1). Nút T chỉ nên có một cung đang chạy (Net Flow = -1). Tất cả các nút khác phải có một cung đi ra và một cung đi vào nếu nút nằm trên đường ngắn nhất (Net Flow= 0) hoặc không có luồng nào (Net Flow = 0).
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à tổng khoảng cách của đường đi ngắn nhất, vì vậy mục tiêu là giảm thiểu đại 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 SBET có tổng khoảng cách là 16.
Giải quyết mô hình
1. Trên bảng Data chọn 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 TotalDistance cho Objective.
3. Nhấp vào Min.
4. Nhập Go cho Changing Variable Cells.
5. Nhấn Add
6. Chọn ‘Make Unconstrained Variables Non-Negative’ và chọn ‘Simplex LP’.
7. Cuối cùng nhấn Solve.
Kết quả
Giải pháp tối ưu:
Kết luận: SADCT là đường đi ngắn nhất có tổng quãng đường là 11.
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 để sử dụng Solver trong Excel để tìm đường đi ngắn nhất?
Bạn cần thiết lập một mô hình trong Excel, bao gồm các biến thể hiện các cung trên đồ thị (1 nếu nằm trên đường đi ngắn nhất, 0 nếu không), các ràng buộc về dòng chảy tại mỗi nút, và hàm mục tiêu là tổng khoảng cách. Sau đó, sử dụng Solver để tối thiểu hàm mục tiêu, tuân thủ các ràng buộc.
Solver trong Excel có hỗ trợ loại bài toán tìm đường đi ngắn nhất nào?
Bài viết hướng dẫn giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng sử dụng Solver. Phương pháp này phù hợp với các đồ thị có kích thước vừa phải.
Tôi có thể tìm thấy thêm thông tin về các bài toán Excel khác ở đâu?
Bạn có thể tham khảo thêm nhiều bài viết về Excel khác tại đây: https://anonyviet.com/category/tin-hoc-van-phong/excel/
