TAILIEUCHUNG - Chương III BÀI TOÁN VẬN TẢI
1. Định nghĩa 1: Ta gọi một đường đi là tập hợp các ô của bảng sao cho cứ hai ô liên tiếp thì nằm trên cùng một dòng hay một cột, và một dòng hay một cột không chứa quá hai ô. | Chương III BÀI TOÁN VẬN TẢI §1. ĐỊNH NGHĨA VÀ MỘT SỐ TÍNH CHẤT nghĩa 1: Trong §1, chương 1 ta đã giới thiệu về bài toán vận tải. Dạng tổng quát có thể định nghĩa như sau: Đây chính là bài toán Quy hoạch tuyến tính dạng chính tắc ẩn và m+n ràng buộc. 3. Định lý 2: Điều kiện cân bằng thu phát là điều kiện cần và đủ để bài toán vận tải có tập phương án khác rỗng. Hơn nữa, nếu bài toán vận tải có điều kiện cân bằng thu phát thì có phương án tối ưu. Tổng lượng hàng thu bằng tổng lượng hàng phát. Ví dụ: Xét lại bài toán vận tải đã biết ở chương 1. Đây là bài toán vận tải cân bằng thu phát. §2. DẠNG BẢNG CỦA BÀI TOÁN VẬN TẢI VÀ ĐIỀU KIỆN TỐI ƯU Thu Phát b1 b2 bj . bn c1 c11 c12 c1j c1n c2 c21 c22 c2j c2n ci ci1 ci2 cij cin cm cm1 cm2 Cmj cmn Thu Phát T1 35 tấn hàng T2 25 tấn hàng T3 45 tấn hàng P1 30 tấn hàng 5 2 3 P2 75 tấn hàng 2 1 1 1. Định nghĩa 1: Ta gọi một đường đi là tập hợp các ô của bảng sao cho cứ hai ô liên tiếp thì nằm trên cùng một dòng hay một cột, và một dòng hay một cột không chứa quá hai ô. Một đường đi khép kín được gọi là một chu trình. X X X X X X ( Đường đi) X X X X X X ( Chu trình ) 3. Hệ qủa: Một bảng vận tải có m dòng, n cột thì tập ô không chứa chu trình có tối đa là m+n-1 ô. 4. Định lý 2: Một bảng vận tải có m dòng, n cột . Cho E là tập gồm m+n-1 ô không chứa chu trình, ô . Khi đó tập hợp có chứa duy nhất một chu trình đi qua ô . Ví dụ: Xét bảng gồm 3 dòng, 4 cột và tập hợp các ô (1,1); (1,3); (2,3); (2,4); (3,4); (3,2). Tập hợp này có 6 ô. 6=3+4-1=m+n-1 và các ô này không chứa chu trình. Khi đó xét bất kỳ một ô thuộc bảng vận tải ta đều có duy nhất một chu trình đi qua ô này. X X X X X X Chẳng hạn, xét ô (2,1) ta có chu trình là các ô (2,1); (2,3); (1,3); (1,1), và đây là chu trình duy nhất. Chú ý, ta không quan tâm đến ô (2,4), và ta nói ô (2,4) không thuộc chu trình. Xét ô (3,1) ta có chu trình là các ô (3,1); (3,4); (2,4); (2,3); (1,3); (1,1) , và đây là chu trình duy nhất đi qua ô (3,1). Và ta cũng không quan tâm đến ô .
đang nạp các trang xem trước
