Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 57
(Sở Kiên Giang 2025) Một công ty vận tải cần giao hàng đến tất cả các địa điểm $ A,B,C,D,E $ (tham khảo hình vẽ). Chi phí di chuyển giữa các địa điểm này được mô tả trên hình (tính theo đơn vị nghìn đồng). Xe giao hàng của công ty xuất phát từ $ E $, đi qua tất cả các địa điểm còn lại đúng một lần sau đó trở lại $ E. $ Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng).
Xem lời giải
Lời giải
Đáp án: 2650.
Ta liệt kê các đường đi xuất phát từ $ E $ đi qua tất cả các trạm còn lại và trở về $ E $.
1. $ E\to B\to A\to C\to D\to E $
Tổng: $ 400+450+600+650+550=2650 $
2. $ E\to B\to D\to C\to A\to E $
Tổng: $ 400+650+650+600+500=2800 $
3. $ E\to A\to B\to D\to C\to E $
Tổng: $ 500+450+650+650+600=2850 $
4. $ E\to C\to D\to B\to A\to E $
Tổng: $ 600+650+650+450+500=2850 $
5. $ E\to A\to C\to D\to B\to E $
Tổng: $ 500+600+650+650+400=2800 $
Vậy đường đi tối ưu nhất là$ E\to B\to A\to C\to D\to E $
Tổng: $ 400+450+600+650+550=2650 $
