Luận văn Thạc sĩ Toán học: Bài toán vận tải dạng chi phí - nút thắt với nhiều mục tiêu

Luận văn có mục đích tìm hiểu và trình bày một số mô hình bài toán vận tải nhiều hàm mục tiêu và các thuật toán tìm nghiệm hữu hiệu của bài toán. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Bài toán vận tải dạng chi phí - nút thắt với nhiều mục tiêu ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THU HUỆBÀI TOÁN VẬN TẢI DẠNG CHI PHÍNÚT THẮT VỚI NHIỀU MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 iMục lụcDanh sách ký hiệu iiiDanh sách bảng ivMở đầu 11 Bài toán vận tải theo mục tiêu cước phí 4 1.1 Nội dung bài toán và tính chất . . . . . . . . . . . . . . . . . . . 4 1.2 Phương án cực biên ban đầu . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Phương pháp min cước. . . . . . . . . . . . . . . . . . . 7 1.2.2 Phương pháp góc tây bắc. . . . . . . . . . . . . . . . . . 8 1.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Bài toán vận tải với hai mục tiêu 14 2.1 Bài toán vận tải theo mục tiêu thời gian . . . . . . . . . . . . . . 14 2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Thuật toán chắn (Blocking Method). . . . . . . . . . . . 16 2.2 Bài toán vận tải với hai mục tiêu . . . . . . . . . . . . . . . . . . 19 2.2.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.2 Tìm các nghiệm cơ sở hữu hiệu của (MP) . . . . . . . . . 20 ii3 Bài toán vận tải với ba mục tiêu 25 3.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Tìm tập nghiệm cơ sở hữu hiệu . . . . . . . . . . . . . . . . . . 29 3.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 31Kết luận 36Tài liệu tham khảo 37 iiiDanh sách ký hiệu Trong luận văn này ta dùng những ký hiệu với các ý nghĩa xác định trong bảngdưới đây: x∈D x thuộc tập D x 6∈ D x không thuộc tập D |G(X)| số phần tử của tập G ∪ phép hợp các tập hợp +∞ dương vô cùng P hàm tổng ∆ij được gọi là ước lượng của biến xij τ chỉ thời hạn về thời gian L danh sách ghi nghiệm hữu hiệu tìm được ivDanh sách bảng Bảng 1.1. Bảng vận tải T Bảng 2.1. Dữ liệu bài toán trong ví dụ 2.2 Bảng 2.2. Bảng vận tải theo mục tiêu thời gian Bảng 2.3. Bảng vận tải theo mục tiêu cước phí Bảng 2.4. Bảng vận tải theo mục tiêu cước phí với τ = 73 Bảng 2.5. Bảng vận tải theo mục tiêu cước phí với τ = 68 Bảng 2.6. Bảng vận tải theo mục tiêu cước phí với τ = 66 Bảng 2.7. Các nghiệm cơ sở hữu hiệu của bài toán vận tải hai mục tiêu Bảng 3.1. Bảng vận tải theo mục tiêu cước phí với τ = 63 Bảng 3.2. Nghiệm cơ sở hữu hiệu S2 kề S1 Bảng 3.3. Bảng vận tải theo mục tiêu cước phí với τ = 66 Bảng 3.4. Tập nghiệm cơ sở hữu hiệu của bài toán trong Ví dụ 3.1 1Mở đầu Bài toán vận tải theo mục tiêu cước phí (Cost Transportation Problem) là bài .toán cổ điển, quen thuộc trong lý thuyết tối ưu và trong các ứng dụng. Đó là bàitoán tìm phương án vận chuyển hàng từ các nơi cung cấp (gọi là điểm phát) đếncác nơi tiêu thụ (gọi là điểm thu) sao cho tổng chi phí vận chuyển là nhỏ nhất. Bàitoán này đã được nghiên cứu khá chi tiết và đầy đủ, cả về lý thuyết lẫn phươngpháp giải. Bài toán vận tải theo mục tiêu thời gian hay còn gọi bài toán vận tải dạng nútthắt (Bottleneck Transportation Problem) là một dạng khác của bài toán vận tải,trong đó có tính đến thời gian đi trên các tuyến đường có vận chuyển hàng. Thayvì tìm cực tiểu tổng chi phí, mục tiêu bây giờ là hoàn thành vận chuyển hàng trongthời gian sớm nhất có thể. Trong bài toán này hàm mục tiêu là phi tuyến. Nhiềudạng khác nhau của bài toán vận tải theo mục tiêu thời gian đã được đặt ra vànhiều thuật toán giải đã được đề xuất. Trong các ứng dụng thực tiễn, để đánh giá hiệu quả hoạt động kinh tế vận tảivà đề ra các quyết định quản lý có căn cứ khoa học, người ta còn gặp các mô hìnhbài toán vận tải với hai hay nhiều hàm mục tiêu. Chẳng hạn, bài toán vận tải cựctiểu cả chi phí lẫn thời gian vận chuyển, gọi là bài toán vận tải dạng chi phí - nútthắt (Bottleneck - Cost Tr ...