Chuyên Đề Tối ưu hoá Bài toán vận tải mở rộng

Tên đề tài:
TỐI ƯU HÓA BÀI TOÀN SẬN TẢI MỞ RỘNG​
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 toán vận tải ba chỉ số, bài toán vận tải khoảng, bài toán vận tải đa mục tiêu và rất nhiều bài toán khác, đó là các biến thể của bài toán vận tải kinh điển trên.


Trong khuôn khổ khoá luận này, em xem xét và nghiên cứu một số bài toán mở rộng trong lớp các bài toán vận tải mở rộng đó. Đó là các bài toán: (solid transport problem) không hạn chế và có hạn chế khả năng thông qua, Bài toán vận tải ba chỉ số khoảng (interval solid transport problem) và giới thiệu một số Bài toán vận tải đa mục tiêu.
Cuối cùng, em xin bày tỏ lòng biết ơn sâu sắc nhất đối với thày giáo hướng dẫn Thạc sỹ Vũ Tiến Việt, người đã tận tình chỉ bảo, giúp đỡ em trong quá trình hoàn thành khoá luận này. Em cũng xin chân thành cảm ơn sự giúp đỡ nhiệt tình của các thầy cô trong khoa Toán - Tin, Học viện An ninh Nhân dân.