Để giải bài toán vận tải có ô cấm ta sẽ xem ô cấm như ô bình thường nhưng cước phí vận chuyển là M rất lớn rồi giải như trường hợp không có ô cấm. | 1) Giải bài toán vận tải cho bởi bảng vận tải sau: j i 40 50 80 30 90 2 4 4 2 40 5 7 1 1 70 4 8 3 6 Bước 1: Thành lập một phương án ban đầu. j i 40 50 80 30 90 2 40 4 20 4 2 30 40 5 7 1 40 1 70 4 8 30 3 40 6 2 x 4 x 4 2 x 5 7 1 x 1 4 8 x 3 x 6 R1= s1= R2= R3= s2= s3= s4= 0 -2 -2 -4 -4 1 -2 0 x 0 x 5 0 x 1 1 0 x -3 -2 0 x 0 x 0 0 x 0 x 5 0 x 1 1 0 x -3 * -2 0 x 0 x 0 0 x 0 x (3) 5 0 x (2) 1 1 0 (6) x -3 * (1) -2 0 x (4) 0 x (5) 0 0 x 0 x (3) 5 0 x (2) 1 1 0 (6) x -3 * (1) -2 0 x (4) 0 x (5) 0 0 40 0 20 (3) 5 0 30 (2) 1 1 0 (6) 40 -3 * (1) -2 0 30 (4) 0 40 (5) 0 0 40 0 20 (3) 5 0 30 (2) 1 1 0 (6) 40 -3 * (1) -2 0 30 (4) 0 40 (5) 0 0 40 0 50 5 0 1 1 0 10 -3 * 30 -2 0 0 70 0 2 40 4 50 4 2 5 7 1 10 1 30 4 8 3 70 6 2 x 4 x 4 2 5 7 1 x 1 x 4 X* 8 3 x 6 R1= s1= R2= R3= s2= s3= s4= 0 -2 0 -4 -2 -1 -1 0 x 0 x 3 1 x 3 3 0 x 0 0 x 2 0 x 3 2) Giải bài toán vận tải có ô cấm cho bởi bảng vận tải sau: j i 65 75 100 80 4 2 1 90 3 5 70 6 7 8 Để giải bài toán vận tải có ô cấm ta sẽ xem ô cấm như ô bình thường nhưng cước phí vận chuyển là M rất lớn rồi giải như trường hợp không có ô cấm. j i 65 75 100 80 4 2 1 90 3 M 5 70 6 7 8 j i 65 75 100 80 4 2 1 90 3 M 5 70 6 7 8 j i 65 75 100 80 4 2 1 80 90 3 65 M 5 5 20 70 6 7 70 8 Đây là phương án cực biên ban đầu. 4 2 1 x 3 x M x 5 x 6 7 x 8 r1= r2= r3= s3 s2 s1 5 -M+6 0 x 0 x 0 x 0 x M-4 0 x M-4 0 -3 -M -5 4 M-7 5 -M+6 0 x 0 x 0 x 0 x M-4 0 x M-4 5 -M+6 * 0 x 0 x 0 x 0 x M-4 0 x M-4 5 -M+6 (1) * 0 x (4) 0 x 0 (2) x 0 x (3) M-4 0 x M-4 5 -M+6 * 0 80 x 0 x 0 x 5 0 x M-4 0 x M-4 (1) * 80 x (4) x 65 (2) x 5 x (3) 20 x 70 5 75 65 25 70 4 2 x 1 x 3 x M 5 x 6 7 x 8 r1= r2= r3= s3 s2 s1 5 0 x 0 x 0 x M-6 0 x 2 0 x 2 0 -3 -6 -5 4 -1 Vì M là số dương rất lớn nên ma trận cước phí mới này không âm. Vậy phương án vừa có là tối ưu. 3) Giải bài toán vận tải không cân bằng thu phát cho bởi bảng vận tải sau: j i 40 50 80 90 6 1 1 40 5 7 4 70 4 11 3 Để giải quyết vấn đề này ta thêm vào một trạm thu giả mà cước phí vận chuyển đến đều bằng 0. j i 40 50 80 30 90 | 1) Giải bài toán vận tải cho bởi bảng vận tải sau: j i 40 50 80 30 90 2 4 4 2 40 5 7 1 1 70 4 8 3 6 Bước 1: Thành lập một phương án ban đầu. j i 40 50 80 30 90 2 40 4 20 4 2 30 40 5 7 1 40 1 70 4 8 30 3 40 6 2 x 4 x 4 2 x 5 7 1 x 1 4 8 x 3 x 6 R1= s1= R2= R3= s2= s3= s4= 0 -2 -2 -4 -4 1 -2 0 x 0 x 5 0 x 1 1 0 x -3 -2 0 x 0 x 0 0 x 0 x 5 0 x 1 1 0 x -3 * -2 0 x 0 x 0 0 x 0 x (3) 5 0 x (2) 1 1 0 (6) x -3 * (1) -2 0 x (4) 0 x (5) 0 0 x 0 x (3) 5 0 x (2) 1 1 0 (6) x -3 * (1) -2 0 x (4) 0 x (5) 0 0 40 0 20 (3) 5 0 30 (2) 1 1 0 (6) 40 -3 * (1) -2 0 30 (4) 0 40 (5) 0 0 40 0 20 (3) 5 0 30 (2) 1 1 0 (6) 40 -3 * (1) -2 0 30 (4) 0 40 (5) 0 0 40 0 50 5 0 1 1 0 10 -3 * 30 -2 0 0 70 0 2 40 4 50 4 2 5 7 1 10 1 30 4 8 3 70 6 2 x 4 x 4 2 5 7 1 x 1 x 4 X* 8 3 x 6 R1= s1= R2= R3= s2= s3= s4= 0 -2 0 -4 -2 -1 -1 0 x 0 x 3 1 x 3 3 0 x 0 0 x 2 0 x 3 2) Giải bài toán vận tải có ô cấm cho bởi bảng vận tải sau: j i 65 75 100 80 4 2 1 90 3 5 70 6 7 8 Để giải bài toán vận tải có ô cấm ta sẽ xem ô cấm như ô bình