Chương III: BÀI TOÁN VẬN TẢI. I. ĐỊNH NGHĨA VÀ MỘT SỐ TÍNH . CHẤT . m nghĩa 1 (1) f = � cij xij. � min. i =1 j = TQ có dạng: n. (2). j =1. xij = ai ( i = 1, m ). m. (3). i =1. xij = b j ( j = 1, n ). (4) xij 0Dạng bảng của btvt: T B1 B2 Bj Bn. P. A1 c11 c12 c1j c1n. . Ai ci1 ci2 cij cin. . Am cm1 cm2 Cmj cmn Thu T1 T2 T3. 35 tấn hàng 25 tấn hàng 45 tấn hàngPhát. P1 5 2 tấn hàng. P2 2 1 tấn hàngLưu ý:.+Mỗi hàng Ai đại diện cho một trạm phát+Mỗi cột Bj đại diện cho một trạm thu+Ô(i,j) đại diện cho tuyến đường vận tải .hàng từ trạm phát thứ i đến trạm thu thứ j+Điều kiện cân bằng thu phát là đk:. m n � =�. a. i =1. b i. j =1. j+ PA của btvt viết dưới dạng ma trận:. � 11 . x1n �. x. �. x=�. . . � ( ij ) m. � x. = n. � �. �m1 . xmn �. lý 1: .Btvt cân bằng thu phát luôn có PATƯ. Định nghĩa 2: .• Tập hợp các ô của bảng vận tải mà 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 ô được gọi là một .đường đi. . X X. X X. X X• Một đường đi khép kín được gọi là một .chu trình X X. X X. X lý 2: Một bảng vận tải m dòng, n .cột thì tập hợp các ô không chứa chu trình .có tối đa là (m+n1) nghĩa 3: Trong một PA, .ô có vận tải hàng đi qua ứng với xij>0 .được gọi là ô chọn. Ô có xij=0 gọi là ô .loại. .Chú ý: ta thường dùng x để chỉ ô chọn. .Định lý 3: X là PACB của btvt khi và chỉ .khi X có tập hợp các ô chọn không chứa .chu nghĩa 4: PACB gọi là không suy .biến nếu số ô chọn =m+n1. PACB gọi là .suy biến nếu số ô chọn <(m+n1) X X. X X. X X X X. X X X.* Đưa PACB suy biến về PACB không .suy biến, ta bổ sung thêm các ô loại cho .đủ (m+n1) ô chọn không chứa chu trình. .Các ô loại bổ sung đó được gọi là ô chọn Định lý 3. Cho bảng vận tải có m dòng, n .cột, cho E={(m+n1) ô không chứa chu . (i, j ) }, ô . Khi đó, . oE1 = E { (i , j )} chứa duy nhất một chu . .trình V oE2 = E1 \ { (i*, j*) / (i*, j*) V }. sẽ không .chứa chu trình(Vậy: E là PACB cũ, E2 là PACB mới).II. Phương pháp tìm . Phương pháp “min cước”: . nghĩa là ưu tiên phân phối hàng nhiều . nhất vào ô có cước phí rẻ nhất!.Ví dụ 1. Tìm PACB của bt sau:. 30 40 50 60. 80 1 5 7 2. 45 5 7 4 9. 55 12 2 3 6Bằng “pp min cước” ta nhận được .PACB:. 30 40 50 60. 80 1 x 5 7 2 x. 30 50. 45 5 7 4 x 9 x. 35 10. 55 12 2 x 3 x 6. 40 15 30 0 0 50 �. �. �.x=� �. 0 0 35 10 �. � 40 15 0 �. 0. � �Nghĩa là: .+ Chuyển 30 (đvh) từ 1 đến 1, .+ Chuyển 50 (đvh) từ 1 đến 4 , .+ Chuy
