LỜI MỞ ĐẦU

Cùng với sự phát triển mạnh mẽ của khoa học kỹ thuật, các bài toán tối ưu xuất hiện ngày càng nhiều và tính phức tạp của chúng ngày càng lớn. Phạm vi và khả năng ứng dụng của các bài toán tối ưu cũng ngày càng đa dạng và phong phó.

Lớp bài toán tối ưu quan trọng được nghiên cứu đầu tiên và được ứng dụng nhiều nhất là bài toán quy hoạch tuyến tính (linear programming). Đó là mô hình toán học của một lớp rộng lớn các bài toán ứng dụng trong kinh tế và kỹ thuật. Do đó cấu trúc của lớp bài toán quy hoạch tuyến tính có nhiều tính chất rất tốt về mặt toán học, người ta đã tìm được các thuật giải rất hữu hiệu cho bài toán này. Năm 1947 nhà toán học Mỹ G.B. Dantzig đã nghiên cứu và đề xuất ra thuật toán đơn hình (simplex method) để giải bài toán quy hoạch tuyến tính. Thuật toán đơn hình được phát triển mạnh mẽ trong những năm sau đó và được xem là một phương pháp kinh điển để giải các bài toán quy hoạch tuyến tính. Đây là một phương pháp được sử dụng có thể nói là rộng rãi nhất. Có ba lý do chính:

Một là: Rất nhiều vấn đề thực tế, trong nhiều lĩnh vực khác nhau có thể đưa về bài toán quy hoạch tuyến tính.

Hai là: Trong nhiều phương pháp giải các bài toán phi tuyến, bài toán tuyến tính xuất hiện nh­ là một bài toán phụ cần phải giải trong nhiều bước lặp.

Ba là: Phương pháp đơn hình là phương pháp hiệu quả để giải bài toán quy hoạch tuyến tính.

Ngày nay, bằng thuật toán đơn hình và các dạng cải biên của chúng, người ta có thể giải rất nhanh các bài toán QHTT cỡ lớn.

Lớp các bài toán vận tải là trường hợp đặc biệt của quy hoạch tuyến tính, bởi vậy có thể dùng các phương pháp của quy hoạch tuyến tính để giải. Tuy nhiên, do tính chất đặc thù riêng của nó, người ta xây dựng các phương pháp giải riêng.

Thông thường khi nói đến bài toán vận tải ta thường liên hệ ngay đến bài toán vận tải hai chỉ số, bởi đây là bài toán vận tải kinh điển có những phương pháp giải hay. Bên cạnh đó, người ta còn xét mét sè các bài toán vận tải mở rộng như bài

Trang: 79