Toán học - Thuật toán quy không cước phí giải bài toán vận tải

Nội dung text: Toán học - Thuật toán quy không cước phí giải bài toán vận tải

1. 7.4. Thuật toán quy không cước phí giải bài toán vận tải: Bước 1: Thành lập một phương án ban đầu, số ô chọn là m+n-1, cũng có thể có ô chọn không. Bước 2: Quy không cước phí các ô chọn . Nếu các ô loại có cước phí không âm thì phương án đang xét là phương án tối ưu. Kết thúc thuật toán . Ngược lại có ô loại có cước phí âm ta qua bước 3.
2. Bước 3: Xây dựng phương án mới như định lý 7. Bước 4: Quay về bước 2. Sau đây là các ví dụ và bài tập.
3. Ví dụ 1: Giải bài toán vận tải cho bởi bảng vận tải sau: j 30 40 50 60 i 80 1 5 7 2 45 5 7 4 9 55 12 2 3 6
4. Bước 1: Thành lập một phương án ban đầu. j 30 40 50 60 i 80 1 5 7 2 30 45 5 7 4 9 55 12 2 3 6 Với bảng vận tải như trên ta thấy ô có cước phí thấp nhất là ô (1,1), ô này có cước phí là 1. Vậy lượng hàng có thể phân nhiều nhất vào ô này là 30. Lượng hàng này là từ nơi phát 1 chở đến nơi nhận 1. Ta xóa cột 1 đi. Lúc này nơi nhận 1 đã đủ hàng và nơi phát 1 chỉ còn 50 đơn vị hàng.
5. 30 40 50 60 30 40 50 60 j j i i 80 1 5 7 2 80 1 5 7 2 30 30 50 45 5 7 4 9 45 5 7 4 9 55 12 2 3 6 55 12 2 3 6
6. 30 40 50 60 j 30 40 50 60 j i i 80 1 5 7 2 80 1 5 7 2 30 50 30 50 45 5 7 4 9 45 5 7 4 9 55 12 2 3 6 55 12 2 3 6 40
7. j 30 40 50 60 j 30 40 50 60 i i 80 1 5 7 2 80 1 5 7 2 30 50 30 50 45 5 7 4 9 45 5 7 4 9 35 10 55 12 2 3 6 55 12 2 3 6 40 15 40 15 Đây là một phương án mà số ô chọn là 6=3+4-1=m+n-1. Và đây là một phương án cực biên.
8. Bước 2: Quy không cước phí các ô chọn. 1 5 7 2 Các ô chọn là x x các ô có đánh 5 7 4 9 dấu x . x x 12 2 3 6 x x Ta cộng vào dòng i số ri và cột j số sj sao cho các ô chọn có cước phí bằng 0. Khi đó ta có hệ phương trình
9. 1 5 7 2 x x 5 7 4 9 x x 12 2 3 6 x x Hệ này có vô số nghiệm, tuy nhiên ta có thể chọn một bộ nghiệm là:
10. 1 5 7 2 x x r1=0 5 7 4 9 x x r2=-7 12 2 3 6 r =-6 x x 3 0 9 10 0 x x s1=-1 s2=4 s3=3 s4=-2 -3 4 0 0 x x 5 0 0 -2 x x
11. Chứng tỏ phương án này chưa tối ưu, vì còn ô có cước phí âm. Bước 3: Xây dựng phương án mới. Bổ sung ô (2,1) có cước phí âm nhỏ nhất vào tập các ô chọn E, ta được một chu trình V duy nhất (2,1); (2,4); (1,4); (1,1). (Đánh dấu * ô (2,1)) 0 x 9 10 x -3 4 0 * x x 5 0 0 -2 x x
12. Đánh số thứ tự các ô thuộc chu trình V, bắt đầu từ ô (2,1). (Số thứ tự trong mgoặc) 0 9 10 (3) (4) x x -3 4 0 * x x Lượng hàng ở các (1) (2) 5 0 0 -2 ô lẻ là x x ở các ô chẵn là Lượng hàng ở các ô không thuộc chu trình là
13. P. Án mới theo công thức ( Vì hai ô này có số thứ tự lẻ) ( Vì hai ô này có số thứ tự chẵn) ( Vì các ô này không thuộc chu trình).
14. 0 9 10 (3) 0 9 10 (3) (4) x X (4) x x 30 50 20 60 -3 4 0 -3 4 0 * 35 10 * x (1) x x 10 35 x (2) 5 0 0 -2 5 0 0 -2 x x x x 40 15 40 15 Các ô có thứ tự chẵn thì trừ đi lượng hàng điều chỉnh. Các ô có thứ tự lẻ thì cộng thêm lượng hàng điều chỉnh. Các ô không thuộc chu trình thì giữ nguyên.
15. Phương án mới là các số in đậm trong bảng sau (các số nhỏ ở trên là cước phí). 1 5 7 2 2 6 0 0 5 7 4 9 1 3 0 5 1 2 3 6 2 4 1 Bước 4:0 Xem5 đây là một phương án ban đầu, ta quay lại bước 2, quy không cước phí các ô chọn.
16. 1 5 7 2 x x r1 =0 5 7 4 9 x x r2 =-4 12 2 3 6 x x r3 =-3 s1 s2 s3 s4 -1 1 0 -2
17. 1 5 7 2 r x x 1 =0 5 7 4 9 r2=-4 x x 12 2 3 6 r3=-3 x x 0 6 7 0 s1 s2 s3 s4 x x -1 1 0 -2 0 4 0 3 Đến đây ta thấy tất cả x x các ô đều có cước phí 8 0 0 1 không âm. Vậy có x x phương án tối ưu
18. Nghĩa là từ nơi phát 1 phân đến nơi nhận 1 20 đơn vị hàng, từ nơi phát 1 phân đến nơi nhận 4 60 đơn vị hàng, từ nơi phát 2 phân đến nơi nhận 1 10 đơn vị hàng, từ nơi phát 2 phân đến nơi nhận 3 35 đơn vị hàng, từ nơi phát 3 phân đến nơi nhận 2 40 đơn vị hàng, từ nơi phát 2 phân đến nơi nhận 3 15 đơn vị hàng. Cước phí phải trả là f=1.20+2.60+5.10+4.35+2.40+3.15=455. Đây là cước phí nhỏ nhất.
19. Ví dụ 2: Giải bài toán vận tải cho bởi bảng vận tải sau: 50 40 70 j i 80 5 5 12 20 7 9 11 60 4 2 3
20. j 50 40 70 i 80 5 5 12 50 30 20 7 9 11 j 50 40 70 i 20 80 5 5 12 60 4 2 3 40 20 20 7 9 11 60 4 2 3
21. Phương án này có 5=3+3-1 ô chọn. Bước 2: Quy không cước phí các ô chọn. Các ô chọn là các ô có đánh dấu x 5 5 12 x x r1 =0 7 9 11 x r2 =1 4 2 3 x x r3 =9 s1 s2 s3 -5 -11 -12
22. 0 -6 0 Chứng tỏ phương x x án này chưa tối 3 -1 0 ưu, vì còn ô có x cước phí âm. 8 0 0 x x Bước 3: Xây dựng phương án mới. Bổ sung ô (1,2) có cước phí âm nhỏ nhất vào tập các ô chọn E, ta được một chu trình V duy nhất (1,2); (1,3); (3,3); (3,2). (Đánh dấu * ô (1,2))
23. 0 (1) x x * 3 -1 0 x 8 (4) 0 (3) x x