tailieunhanh - 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 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 ô. | . 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. 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ởi bảng vận tải sau: j i 30 40 50 60 80 1 5 7 2 45 5 7 4 9 55 12 2 3 6 Bước 1: Thành lập một phương án ban đầu. j i 30 40 50 60 80 1 30 5 7 2 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. j i 30 40 50 60 80 1 30 5 7 2 45 5 7 4 9 55 12 2 3 6 j i 30 40 50 60 80 1 30 5 7 2 50 45 5 7 4 9 55 12 2 3 6 j i 30 40 50 60 80 1 30 5 7 2 50 45 5 7 4 9 55 12 2 3 6 j i 30 40 50 60 80 1 30 5 7 2 50 45 5 7 4 9 55 12 2 40 3 6 j i 30 40 50 60 80 1 30 5 7 2 50 45 5 7 4 9 55 12 2 40 3 15 6 j i 30 40 50 60 80 1 30 5 7 2 50 45 5 7 4 35 9 10 55 12 2 40 3 15 6 Đâ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 x 5 7 2 x 5 7 4 x 9 x 12 2 x 3 x 6 Các ô chọn là các ô có đánh dấu 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 1 x 5 7 2 x 5 7 4 x 9 x 12 2 x 3 x 6 Hệ này có vô số nghiệm, tuy nhiên ta có thể chọn một bộ nghiệm là: 1 x 5 7 2 x 5 7 4 x 9 x 12 2 x 3 x 6 0 x 9 10 0 x -3 4 0 x 0 x 5 0 x 0 x -2 r1=0 r2=-7 s4=-2 s1=-1 r3=-6 s2=4 s3=3 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 . | . 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. 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ởi bảng vận tải sau: j i 30 40 50 60 80 1 5 7 2 45 5 7 4 9 55 12 2 3 6 Bước 1: Thành lập một phương án ban đầu. j i 30 40 50 60 80 1 30 5 7 2 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. j i 30 40 50 60 80 1 30 5 7 2 45 5 7 4 9 55 12 2 3 6 j i 30 40 50 60