Bài 267: Bài toán tìm đường đi ngắn nhất trong Excel

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.