Chương 3: Bài toán vận tải - bài 1

Tài liệu tham khảo về bài toán vận tải...
Nội dung trích xuất từ tài liệu:
Chương 3: Bài toán vận tải - bài 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT1. Thiết lập bài toán n kho hàng (trạm phát): A1 ,..., An ai (i  1, n) m nơi tiêu thụ (trạm thu): B1 ,..., Bm b j ( j  1, m)CPVC 1 đv hàng hoá từ trạm Ai đến trạm B j là cijHãy lập kế hoạch vận chuyển hàng hoá từ các trạm phátđến các trạm thu sao cho CPVC là thấp nhất. 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT1. Thiết lập bài toánGọi xij là lượng hàng cần vận chuyển từ trạm Ai  B j n m+ Tổng CPVC được xác định bằng: f ( x)   cij xij m i 1 j 1+ Tổng lượng hàng phát đi từ trạm Ai :  xij j 1 n+ Tổng lượng hàng thu tại trạm B j :  xij i 1 2 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT1. Thiết lập bài toánVà khi đó, mô hình toán học của BT được viết như sau: n m f ( x)   cij xij  min i 1 j 1 m x j 1 ij  ai n x i 1 ij  bj Đây là mô hình toán của BTVT xij  0, (i  1, n, j  1, m) dạng tổng quát. 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT1. Thiết lập bài toánTrong thực tế, ta thường gặp 3 trường hợp cụ thể sau:a) Cân bằng thu- phát (Tổng thu bằng tổng phát):Hệ ràng buộc của bài toán có thêm điều kiện: n m  a  b i 1 i j 1 jKhi đó, bài toán được gọi là BTVT đóng.b) Không cân bằng thu- phát (tổng thu > tổng phát hoặctổng thu < tổng phát).c) Điều kiện vận tải không cho phép (BTVT có ô cấm). 4 2 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT2. Đặt bài toán dưới dạng bảng@ Dạng bảng của BTVT : Trạm thu Bm Ô (1,2): tuyến A1 qua B2 Thu B1 B2 Bm … Phát b1 b2 bm A1 a1 c11 c12 … c1mTrạm phát A2 a2 c21 c22 … c2m A2 … … … … … Ma trận An cước phí an cn1 cn2 … cnm 5 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT2. Đặt bài toán dưới dạng bảng@ Dạng bảng của mô hình BTVT:Các ẩn số của BT tạo thành ma trận ẩn số X = (xij)mxn.6 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT 3. Các khái niệm + Phương án của BTVT + Ô chọn + Ô loại + Dây chuyền + Vòng + Phương án cơ bản + Phương án không cơ bản + PACB không suy biến & PACB suy biến 7 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT 3. Các khái niệmCác dạng vòng thường gặp như sau: 8 4 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 1: CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BTVT 4. Các tính chất của bài toán vận tải* Tính chất 1: Mọi BTVT đều có PATU.* Tính chất 2: Một PACB có tối đa m+n-1 ô chọn.* Tính chất 3: Một ô loại bất kỳ được bổ sung vàomột PACB không suy biến (có m+n-1 ô chọn) sẽtạo thành một vòng duy nhất; và nếu loại một ôbất kỳ thuộc vòng đó thì ta sẽ có một dây chuyềncác ô chọn. 9 5 ...