Bài toán quy hoạch tuyến tính: Thuật toán không tính cước phí

Trong toán học, Bài toán vận tải là một dạng của bài toán quy hoạch tuyến tính. Bài toán vận tải có thể biểu diễn như một đồ thị hai phía, có hướng. Nó có thể ứng dụng vào nhiều vấn đề khác nhau. Giải thuật đơn hình trên bài toán vận tải cũng đơn giản hơn.Một chu trình trong bảng vận tải là một dãy các ô trong đó ô đầu tiên và ô thứ hai nằm trên cùng một dòng, hai ô liên tiếp hoặc nằm trên cùng một dòng, hoặc cùng nằm trên một cột, ba ô...
Nội dung trích xuất từ tài liệu:
Bài toán quy hoạch tuyến tính: Thuật toán không tính cước phí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ạicó cước phí âm ta qua bước 3.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.Ví dụ 1: Giải bài toán vận tải cho bởibả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 6Bướ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 6Vớ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ânnhiều nhất vào ô này là 30. Lượng hàng này là từ nơi phát 1chở đến nơi nhận 1. Ta xóa cột 1 đi. Lúc này nơi nhận 1 đã 30 40 50 60 30 40 50 60 j ji i80 1 5 7 2 80 1 5 7 2 30 30 50 5 7 4 945 45 5 7 4 9 55 12 2 3 655 12 2 3 6 j 30 40 50 60 j 30 40 50 60i i 80 1 5 7 280 1 5 7 2 30 50 30 50 45 5 7 4 945 5 7 4 9 55 12 2 3 6 4055 12 2 3 6 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 45 5 7 4 9 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.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 xTa cộng vào dòng i số ri và cột j số sj saocho các ô chọn có cước phí bằng 0. Khi đó ta có hệ phương trình 1 + r1 + s1 = 0 1 5 7 2 x x 2 + r1 + s4 = 0 4 + r2 + s3 = 0 5 7 4 9 x x 9 + r2 + s4 = 0 12 2 3 6 2 + r3 + s2 = 0 x x 3 + r3 + s3 = 0 Hệ này có vô số nghiệm, tuy nhiên ta có thể chọn một bộ nghiệm là:r1 = 0, s1 = − 1, s4 = − 2, r2 = − 7, s3 = 3, r3 = − 6, s2 = 41 5 7 2 r1=0 x x5 7 4 9 r2=-7 x x12 2 3 6 r3=-6 x x 0 9 10 0 x xs1=-1 s2=4 s3=3 s4=-2 -3 4 0 0 x x 5 0 0 -2 x xChứ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ấtvào tập các ô chọn E, ta được một chutrình V duy nhất (2,1); (2,4); (1,4); (1,1).(Đánh dấu * ô (2,1)) 0 x9 10 x -3 ...