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

Chia sẻ: Nguyễn Văn Quân | Ngày: | Loại File: PPT | Số trang:23

Thêm vào BST

Báo xấu

883
lượt xem 234
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 ô...

Chủ đề:

Bình luận(1) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ạ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 30 40 50 60 i 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 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 đã
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 5 7 4 9 45 45 5 7 4 9 55 12 2 3 6 55 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 5 7 4 9 45 5 7 4 9 55 12 2 3 6 40 55 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 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 + 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 = 4
1 5 7 2 r1=0 x x 5 7 4 9 r2=-7 x x 12 2 3 6 r3=-6 x x 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
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 x9 10 x -3 4 0 * x x 5 0 0 -2 x x
Đánh số thứ tự các ô thuộc chu trình V, bắt đầu từ ô (2,1). (Số thứ tự trong 10 mgoặc) V = { (2,1); (1, 4)} , L 0 9 (3) (4) x x V = { (2, 4); (1,1)} C -3 4 0 * x x Lượng hàng ở (1) (2) các ô lẻ là 5 0 0 -2 { x21 = 0, x14 = 50} x x ở các ô chẵn là { x24 = 10, x11 = 30} Lượng hàng ở các ô không thuộc chu trình là x32 = 40, x33 = 15, x23 = 35
xi* j* = min { xij : (i, j ) � } = min { 10,30} = 10 C V xij theo công thức P. Án mới x21 = 0 + 10 = 10 ( Vì hai ô này có số thứ tự lẻ) x14 = 50 + 10 = 60 x24 = x24 − xi* j* = 10 − 10 = 0, ( Vì hai ô này có số x11 = x11 − xi* j* = 30 − 10 = 20, thứ tự chẵn) x23 = x23 = 35, ( Vì các ô này không thuộc x32 = x32 = 40, chu trình). x33 = x33 = 15,
0 9 10 (3) 0 9 10 (3) (4) x X (4) x x 30 50 20 60 -3 4 0 -3 4 0 * x * 35 10 10 35 x (1) x 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.
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 60 20 5 10 7 4 35 9 12 2 40 3 15 6 Bước 4: Xem đâ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.
1 5 7 2 r1 =0 x x r2 =-4 5 7 4 9 x x 12 2 3 6 r3 =-3 x x s1 s2 s3 s4 1 0 -2 -1
1 5 7 2 r1 =0 x x r2=-4 5 7 4 9 r3=-3 x x 0 6 7 0 s1 s s s4 12 22 3 36 x x x x 1 -2 1 0 0 4 0 3 Đến đây ta thấy tất x x cả các ô đều có 8 0 0 1 cước phí không âm. x x Vậy có phương án
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.
Ví dụ 2: Giải bài toán vận tải cho bởi bảng vận tải sau: j 50 40 70 i 80 5 5 12 20 7 9 11 60 4 2 3
j 50 40 70 i 80 5 5 12 50 30 j 50 40 70 20 7 9 11 i 20 80 5 5 12 60 4 2 3 40 20 20 7 9 11 60 4 2 3