Vấn đề đường đi ngắn nhất - Shortest Path

Sử dụng giải quyết trong Excel để tìm đường đi ngắn nhất từ nút tới nút S T trong một mạng vô hướng. Điểm trong một mạng được gọi là các nút (S, A, B, C, D, E và T). Dòng trong một mạng được gọi là vòng cung (SA, SB, SC, AC, vv).

Xây dựng các mô hình

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

1. Xây dựng vấn đề này con đường ngắn nhất, trả lời ba câu hỏi sau đây.

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 ra nếu một hồ quang là trên con đường ngắn nhất hay không (Có = 1, Không = 0). Ví dụ, nếu SB là một phần của con đường ngắn nhất, ô F5 bằng 1. Nếu không, ô F5 bằng 0.

những hạn chế về các quyết định 

b. là gì? Net Flow (chảy ra - Lưu lượng In) của mỗi nút nên bằng cấp / Demand. Node S chỉ nên có một vòng cung đi (Net dòng = 1). Node T chỉ nên có một vòng cung thoi vàng (Net dòng = -1). Tất cả các nút khác nên có một vòng cung đi và một vòng cung thoi vàng nếu nút là trên con đường ngắn nhất (Net Lưu lượng = 0) hoặc không có dòng (Net Lưu lượng = 0).

c. các biện pháp tổng thể về hiệu suất cho những quyết định này là gì? Các biện pháp tổng thể về hiệu suất là khoảng cách tổng cộng con đường ngắn nhất, do đó mục tiêu là để giảm thiểu số lượng này.

2. Để thực hiện các mô hình dễ hiểu, đặt tên cho các dãy sau đây.

Range Name	Cells
From	B4:B21
To	C4:C21
Distance	D4:D21
Go	F4:F21
NetFlow	I4:I10
SupplyDemand	K4:K10
TotalDistance	F23

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

Giải thích: SUMIF chức năng tính toán dòng chảy ròng của mỗi nút. Đối với nút S, hàm SUMIF tính tổng của các giá trị trong cột Go với một "S" trong từ cột. Kết quả là, chỉ có tế bào F4, F5 hay F6 có thể là 1 (một vòng cung đi).Đối với nút T, hàm SUMIF tính tổng của các giá trị trong cột Đi với một "T" trong cột Để. Kết quả là, chỉ có tế bào F15, F18 hay F21 có thể là 1 (một vòng cung thoi vàng). Đối với tất cả các nút khác, Excel trông vào From và To cột. Tổng số cách bằng với SUMPRODUCT Từ xa và Go.

Thử và Sai

Với công thức này, nó trở nên dễ dàng để phân tích bất kỳ giải pháp thử nghiệm.

1. Ví dụ, con đường SBET có một khoảng cách tổng cộng 16.

Nó không phải là cần thiết để sử dụng thử và sai. Chúng ta sẽ mô tả tiếp theo như thế nào Solver Excel có thể được sử dụng để nhanh chóng tìm ra giải pháp tối ưu.

Giải quyết các Model

Để tìm ra giải pháp tối ưu, thực hiện các bước sau đây.

1. Trên tab Data, nhấn Solver.

Lưu ý: không thể tìm thấy nút Solver? Nhấn vào đây để tải các Solver Add-in .

Nhập các thông số giải (đọc tiếp). Kết quả phải nhất quán với hình ảnh dưới đây.

Bạn có thể lựa chọn cách gõ tên dãy hoặc nhấp vào các tế bào trong bảng tính.

2. Nhập TotalDistance cho các Mục tiêu.

3. Nhấn vào Min.

4. Nhập Đi cho các tế bào biến đổi.

5. Nhấn Add để nhập các ràng buộc sau.

6. Kiểm tra 'Hãy biến Unconstrained Non-Negative "và chọn" Simplex LP'.

7. 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: SADCT là con đường ngắn nhất với một khoảng cách tổng cộng 11.