Giáo trình Toán kinh tế (Phần 2)

Nội dung text: Giáo trình Toán kinh tế (Phần 2)

1. Bảng 3.3 T 30 20 25 35 40 P 30 13 7 6 2 12 20 5 1 10 5 11 40 10 5 3 7 14 60 6 3 2 11 10 Giải: Trên bảng vận tải 3.3, ta thấy ô (2, 2) có cƣớc phí nhỏ nhất c22 = 5. Phân vào ô đó lƣợng hàng lớn nhất có thể đƣợc là x22 = 20. Khi đó trạm phát A2 hết hàng và trạm thu B2 nhận đủ hàng, trạm phát A1 còn 80 đơn vị hàng. Xóa bỏ hàng 2, cột 2, lặp lại công việc trên sau một số hữu hạn bƣớc, ta thu đƣợc phƣơng án cực biên của bài toán nhƣ bảng (3.4). Bảng 3.4 T P 30 20 25 35 40 13 7 6 2 12 30 30 5 1 10 5 11 20 20 10 5 3 7 14 40 5 35 6 3 2 11 10 60 30 25 5 0 0 0 30 0 0 20 0 0 0 Nhƣ vậy, phƣơng án cực biên thu đƣợc là: X . 0 0 0 0 5 35 30 0 25 0 5 - 66 -
2. Phƣơng án X0 có 7 ô chọn, thiếu một ô so với hạng của bài toán cân bằng thu phát. Ta lấy thêm một ô loại bổ sung thêm vào tập hợp 7 ô chọn để đủ 8 ô không chứa vòng. Chẳng hạn ô (1, 2), ta đƣợc tập ô cơ sở J0 = {(1, 2), (1, 4), (2,2), (3, 4), (3, 5), (4, 1), (4, 3), (4, 5)}. 2.1.2. Phương pháp Fogels Nội dung phƣơng pháp: Trên bảng vận tải, ta tính chênh lệch cƣớc phí giữa hai ô có cƣớc phí nhỏ nhất của mỗi dòng và mỗi cột. Xét dòng hay cột có chênh lệch lớn nhất và phân vào ô có cƣớc phí nhỏ nhất của dòng hay cột đó một lƣợng hàng lớn nhất có thể đƣợc, bỏ đi các ô nằm trên các trạm đã đƣợc thỏa mãn. Sau đó tính lại chênh lệch cƣớc phí của các cột hay dòng còn lại, lặp lại công việc trên sau một số hữu hạn lần, ta thu đƣợc ma trận X = (xij)m.n là một phƣơng án cực biên của bài toán vận tải cân bằng thu phát. Ví dụ 3.2: Tìm phƣơng án cực biên theo phƣơng pháp Fogels của bài toán vận tải ở ví dụ 3.1. Giải: Bằng phƣơng pháp Fogels ta tìm đƣợc phƣơng án cực biên nhƣ bảng 3.5. Bảng 3.5 T P 30 20 25 35 40 13 7 6 2 12 30 4,4x 30 5 1 10 5 11 20 4x 20 10 5 3 7 14 40 2,4,3,7 5 35 6 3 2 11 10 60 1,4,4,1 30 25 5 1,4,4x 2x 1,1,1x 3,5,4,7x 1,2,4,4 Phƣơng án cực biên tìm đƣợc theo phƣơng pháp Fogels: - 67 -
3. 0 0 0 30 0 0 20 0 0 0 X 0 0 0 25 5 10 30 0 0 0 30 2.2. Tiêu chuẩn tối ƣu cho một phƣơng án của bài toán vận tải cân bằng thu phát 2.2.1. Bài toán đối ngẫu của bài toán vận tải Xét bài toán vận tải : mn f (X) cij x ij min (3.1) i 1 j 1 n xij ai ,(i 1,m) (3.2) j 1 m xij b j,(j 1,n) (3.3) i 1 xij 0 (i = 1,m , j = 1, n ). (3.4) K hiệu ui là các biến đối ngẫu ứng với hệ ràng buộc (3.2), vj là các biến đối ngẫu ứng với hệ ràng buộc (3.3). Khi đó bài toán đối ngẫu của bài toán vận tải có dạng: m n aiui b jv j max (3.9) i 1 j 1 ui + vj cij (i 1,m, j 1,n). (3.10) Các cặp điều kiện đối ngẫu: xij 0 ui + vj cij (i 1,m, j 1,n) (3.11) 2.2.2. Tiêu chuẩn tối ưu cho một phương án của bài toán vận tải Định lý 3.5. Giả sử X = (xij)m.n là phương án của bài toán vận tải cân bằng thu phát (3.1) (3.2) (3.3) (3.4). Khi đó điều kiện cần và đủ để phương án X là phương án tối ưu là tồn tại một hệ thống gồm m + n thế vị (u1, u2, , um, v1, v2, , vn) = (U, V) sao cho: - 68 -
4. ui + vj cij (i 1,m,j 1,n), (3.12) ui + vj = cij nếu xij > 0. (3.13) Chứng minh. Cần: Giả sử X = (xij)m.n là phƣơng án tối ƣu của bài toán vận tải cân bằng thu phát (3.1) (3.2) (3.3) (3.4). Theo định lý đối ngẫu thứ nhất, bài toán đối ngẫu (3.9) (3.10) cũng có phƣơng án tối ƣu. Giả sử phƣơng án tối ƣu đó là (U, V) = (ui, vj), i 1,m, j 1,n . Khi đó điều kiện (3.12) đƣợc thỏa mãn. Mặt khác theo định l đối ngẫu thứ hai giữa (U, V) và X thì điều kiện (3.13) đƣợc thỏa mãn. Vậy phƣơng án tối ƣu của bài toán đối ngẫu (U, V) chính là hệ thống thế vị phải tìm. Đủ: Giả sử tìm đƣợc hệ thống thế vị (U, V) = {(ui, vj): } thỏa mãn (3.12) (3.13). Vì thỏa mãn (3.12) nên (U, V) là phƣơng án của bài toán đối ngẫu. Vì thỏa mãn (3.13) nên cặp phƣơng án X, (U, V) thỏa mãn giả thiết của định l đối ngẫu thứ hai. Vậy X là phƣơng án tối ƣu của bài toán vận tải và hệ thống thế vị (U, V) là phƣơng án tối ƣu của bài toán đối ngẫu. 2.2.3. Phương pháp xây hệ thống toán thế vị 0 Giả sử X0 (x ij ) m.n là một phƣơng án cực biên và J0 là một hệ thống ô chọn cơ sở của X0. Ta sẽ xây dựng hệ thống thế vị (U, V) = (ui, vj), . Lấy (3.13) làm điều kiện xuất phát để tìm hệ thống thế vị sau đó sẽ kiểm tra điều kiện (3.12). Xét hệ phƣơng trình tuyến tính: ui + vj = cij (i, j) J0. (3.14) Vì J0 gồm m + n – 1 ô không chứa vòng nên hệ (3.14) gồm m + n – 1 phƣơng trình độc lập tuyến tính, xác định m + n ẩn. Do vậy hệ (3.14) có vô số nghiệm phụ thuộc một tham số. Lấy bất kỳ một ẩn làm tham số, và cho tham số nhận một giá trị cụ thể, chẳng hạn là số 0, ta đƣợc một nghiệm riêng của hệ phƣơng trình. Đó chính là hệ thống thế vị đối với tập ô cơ sở J0. Định lý 2. Giả sử (U, V) và (U’, V’) là hai nghiệm riêng của hệ (3.14) khi đó ta có: ui + vj = ui’ + vj’ , i 1,m, j 1,n . - 69 -
5. Từ kết quả của định l ta nhận thấy việc phƣơng án X0 có tối ƣu hay không nghĩa là hệ thống thế vị (U, V) tìm đƣợc có thỏa mãn điều kiện (3.12) hay không, nó hoàn toàn không phụ thuộc vào việc ta chọn ẩn tự do và cho nó giá trị là bao nhiêu khi đi tìm nghiệm riêng của hệ phƣơng trình (3.14). Tóm lại, để tìm hệ thống thế vị ứng với một phương án cực biên X0 cho trước và kiểm tra X0 đã tối ưu chưa ta thực hiện các bước sau: - Xác định hệ ô chọn cơ sở của X0. Nếu X0 không suy biến thì J0 = C(X0). Nếu X0 suy biến thì ta cần bổ sung thêm một số ô loại (làm ô chọn giả) để cùng với tập C(X0) tạo thành m + n – 1 ô không chứa vòng. Lƣợng hàng tại các ô chọn giả là 0. - Tìm một hệ thống thế vị, hay là tìm một nghiệm riêng của hệ (3.14). Đặt ij = ui + vj – cij, ij đƣợc gọi là số kiểm tra hay ƣớc lƣợng của ô (i, j). Rõ ràng ij = 0 (i, j) J và - nếu ij 0 (i, j) thì X0 là phƣơng án tối ƣu, - nếu tồn tại ij > 0 thì X0 chƣa phải là phƣơng án tối ƣu. 2.3. Phƣơng pháp cải tiến phƣơng án Bổ đề 3.1. Xét phƣơng án cực biên X0 với hệ ô chọn cơ sở J0. Giả sử (i0, j0) là một ô bất kỳ không thuộc J0, khi đó tập hợp {J0 + (i0, j0)} sẽ chứa một vòng duy nhất. Chứng minh: Do {J + (i0, j0)} gồm m + n ô nên nó chứa một vòng V nào đó và hiển nhiên V đi qua (i0, j0), Giả sử vòng V có dạng: V = {(i0, j0), (i0, j1), (i1, j1), , (ik, jk), (ik, j0)}. Giả sử tồn tại vòng V’ V, dĩ nhiên V’ cũng đi qua (i0, j0) và giả sử V’ có dạng: V’ = {(i0, j0), (i0, q1), (p1, q1), , (pk, qk), (pk, j0)}. Từ V và V’ ta lập vòng mới: V’’ = {(i0, j1), (i1, j1), , (ik, jk), (ik, j0), (pk, jo), (pk, qk), , (i0, q1)}. Vòng này không đi qua (i0, j0), trái với giả thiết J0 không chứa vòng. Vậy ta có điều phải chứng minh. - 70 -
6. Bổ đề 3.2. Gọi V là vòng duy nhất tạo bởi (i0, j0) và một số ô của J0. Đánh số thứ tự 1, 2, 3, các ô trên V bắt đầu từ (i0, j0). K hiệu: Vc = {(i, j) V có số thứ tự chẵn}, Vl = {(i, j) V có số thứ tự lẻ}. Ta có công thức c c . ij ij i 0 j0 (i, j) Vc (i, j) Vl Chứng minh: Giả sử V = {(i0, j0), (i0, j1), (i1, j1), , (ik, jk), (ik, j0)}. Khi đó: c c c c c c c ij ij i 0 j0 i 0 j1 i1 j1 i k jk i k j0 (i, j) Vc (i, j) Vl c u v u v u v u v i 0 j0 i 0 i1 i1 j1 i k jk i k j0 c u v . i 0 j0 i 0 j0 i 0 j0 Ta có điều phải chứng minh. Dựa vào hai kết quả trên ta đưa ra thuật toán cải tiến phương án như sau: Giả sử phƣơng án cực biên X0 với hệ ô chọn cơ sở J0 chƣa thỏa mãn tiêu chuẩn tối ƣu, nghĩa là còn tồn tại số kiểm tra ij > 0. - Chọn ô điều chỉnh (thƣờng chọn ô có số kiểm tra dƣơng lớn nhất). Giả sử max{ 0}, khi đó ô (i0, j0) là ô điều chỉnh. i 0 j0 ij - Lập vòng điều chỉnh V tạo bởi (i0, j0) và một số ô chọn khác của J0. Sau đó đánh số thứ tự và chia V thành Vc , Vl. - Xác định phƣơng án mới X1 theo công thức: 0 xij (ij) V 1 0 xij xij q (ij) Vc (3.15) 0 xij q (ij) Vl với q là lƣợng điều chỉnh đƣợc xác định theo công thức: q min x0 : (ij) V x0 . (3.16) ij c i r jr Định l 3.7. Giả sử X0 là phương án cực biên không suy biến, ma trận X1 được xác định theo công thức (3.15) (3.16) là một phương án cực biên với hệ ô chọn cơ sở J0 = J {i0, j0}\{ir, jr}, và tốt hơn hẳn X0. - 71 -
7. Chứng minh: Vì số ô của vòng V nằm trên một dòng hay một cột bằng 0 hoặc là một số chẵn nên từ công thức (3.15) ta có: n n m m 1 0 1 0 xij xij ai , i 1,m , xij xij b j, j 1,m. j 1 j 1 i 1 i 1 0 Vì X0 là phƣơng án cực biên không suy biến nên x ij > 0 với mọi (i, j) J0. 1 Do vậy q > 0, mặt khác theo (3.15) và (3.16) thì x ij 0, (i, j). Nhƣ vậy chứng tỏ X1 là phƣơng án của bài toán. Tập hợp J1 vẫn đảm bảo m + n - 1 ô chọn và không chứa vòng. Vậy phƣơng án X1 thu đƣợc là phƣơng án cực biên với cơ sở J1, đồng thời f(X0) – f(X1) = q > 0, chứng tỏ phƣơng án X1 tốt hơn phƣơng án X0. i 0 j0 Thuật toán thế vị giải bài toán vận tải cân bằng thu phát (bài toán không suy biến)gồm các bước sau: Bƣớc 1: Tìm phƣơng án cực biên xuất phát X0 và hệ ô chọn cơ sở J0. Bƣớc 2: Xây dựng hệ thống thế vị, kiểm tra tiêu chuẩn tối ƣu. + Nếu thỏa mãn tiêu chuẩn tối ƣu, kết luận bài toán; + Nếu chƣa thỏa mãn tiêu chuẩn tối ƣu, chuyển sang bƣớc 3. Bƣớc 3: Cải tiến phƣơng án: - Chọn ô điều chỉnh, lập vòng điều chỉnh, xác định lƣợng điều chỉnh q. - Xác định phƣơng án cực biên mới X1: Giữ nguyên lƣợng hàng tại các ô không nằm trên vòng điều chỉnh V. Trên vòng điều chỉnh V ta thêm lƣợng hàng q ở các ô lẻ, bớt đi lƣợng hàng q ở các ô chẵn đồng thời xác định hệ ô chọn cơ sở mới J1. Gán X1: = X0, quay về bƣớc 2. Chú rằng, do số phƣơng án cực biên là hữu hạn nên thuật toán thế vị cũng sẽ kết thúc sau một số hữu hạn bƣớc. Ví dụ 3.3: Tìm phƣơng án tối ƣu của bài toán vận tải cân bằng thu phát cho ở bảng 3.6. - 72 -
8. Bảng 3.6 T 30 25 40 25 P 20 4 2 10 6 45 1 3 8 12 55 5 3 9 7 Giải: - Bằng phƣơng pháp cƣớc phí bé nhất, ta tìm đƣợc phƣơng án cực biên xuất phát X0 nhƣ bảng 3.7. Bảng 3.7 T 30 25 40 25 P 4 2 10 6 20 20 1 3 8 12 45 30 5 10 5 3 9 7 55 30 25 0 20 0 0 X0 30 5 10 0 0 0 30 25 Phƣơng án cực biên X0 có cơ sở J0 là tập các ô chọn. - 73 -
9. Bảng 3.8 4 2 10 6 u1 = 0 - 20 - - 1 3 8 12 u2 = 1 30 5 10 - 5 3 9 7 u3 = 2 - (1) 30 25 v1 = 0 V2 = 2 v3 = 7 v4 = 5 - Xây dựng hệ thống thế vị: từ công thức ui + vj = cij (i, j) J0, cho u1 = 0, ta đƣợc hệ thống thế vị nhƣ ở bảng 3.8. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij đối với các ô loại, thấy ô (3.2) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: lấy ô (3.2) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(3, 2), (2, 2), (2, 3), (3, 3)}. q = min{5, 30} = 5. Điều chỉnh 5 đơn vị hàng từ ô thuộc Vc sang ô thuộc Vl, ta đƣợc phƣơng án cực biên X1 nhƣ bảng 3.9: khi đó ô (2, 2) hết hàng trở thành ô loại, ô (3, 2) có hàng trở thành ô chọn. Ta có cơ sở mới J1 là tập các ô chọn nhƣ bảng 3.9. Bảng 3.9 4 2 10 6 u1 = - 1 - 20 - (0) 1 3 8 12 u2 = - 1 30 - 15 - 5 3 9 7 u3 = 0 - 5 25 25 v1 = 2 v2 = 3 V3 = 9 v4 = 7 - 74 -
10. - Xây dựng hệ thống thế vị: từ công thức ui + vj = cij (i, j) J1, cho u3 = 0, ta đƣợc hệ thống thế vị nhƣ ở bảng 3.9. Tính ij, ta thấy ij 0, (i, j). Vậy phƣơng án cực biên X1 là phƣơng án tối ƣu của bài toán. 0 20 0 0 X1 30 0 15 0 , 0 5 25 25 tổng cƣớc phí vận chuyển nhỏ nhất là: f(x) = 2.20 + 1.30 + 8.15 + 3.5 + 9.25 + 7.25 = 605. Chú : Nếu gặp trƣờng hợp phƣơng án cực biên suy biến thì q có thể bằng 0. Khi q = 0, ta vẫn tiến hành thuật toán bình thƣờng. Thực chất của quá trình này là thay đổi một ô cơ sở thành một ô không thuộc cơ sở, còn ô điều chỉnh sẽ trở thành ô cơ sở. Kết quả của quá trình là chuyển từ tập ô cơ sở này sang tập ô cơ sở khác mà không làm thay đổi phƣơng án cực biên. Nếu q = min xij đạt tại nhiều ô khác nhau, đó là dấu hiệu của phƣong án (i, j) Vc cực biên suy biến. Ta loại một ô bất kỳ một cách ngẫu nhiên trong các ô đó, các ô khác giữ nguyên trong tập cơ sở mới (chúng có vai trò nhƣ ô bổ sung). Ví dụ 3.4: Cho bài toán vận tải nhƣ bảng 3.10. Bảng 3.10 T 51 54 60 45 80 P 50 10 11 10 9 8 90 12 12 5 13 11 70 19 18 6 14 15 80 18 17 7 15 12 - 75 -
11. Tìm phƣơng án vận chuyển tối ƣu. Giải: - Tìm phƣơng án cực biên xuất phát: Dùng phƣơng pháp Fogels, ta thu đƣợc phƣơng án cực biên X0 nhƣ bảng 3.11. Bảng 3.11 T 51 54 60 45 80 P 10 11 10 9 8 50 1,1,2,1x 5 45 12 12 5 13 11 90 6,1,1,0 46 44 19 18 6 14 15 70 10 60 0 8,1,3,1 18 17 7 15 12 80 5,3,5x 80 2,2,7x 1,1,6 1x 4x 3x - Xác định tập ô cơ sở: phƣơng án cực biên xuất phát có 7 ô chọn, thiếu một ô so với hạng của bài toán. Ta bổ sung thêm ô (3.5) để đủ 8 ô không chứa vòng. Khi đó ta có tập ô cơ sở J0 = {(1, 1), (1, 4), (2,1), (2,2), (3,2), (3,3), (3,5), (4, 5)}. Bảng 3.12 10 11 10 9 8 u1 =-8 5 - - 45 - 12 12 5 13 11 u2 = -6 46 44 - - - 19 18 6 14 15 u3 = 0 - 10 60 (3) 0 18 17 7 15 12 u4 = -3 - - - - 80 v1 = 18 V2 = 18 v3 = 6 v4 =17 v5 =15 - 76 -
12. - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J0, ta đƣợc hệ thống thế vị nhƣ bảng 3.12. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij , ta thấy ô (3, 4) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (3.4) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(3, 4), (1, 4), (1, 1), (2, 1), (2, 2), (2, 3)}. q = min{45, 46, 10} = 10. Điều chỉnh 10 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X1: Khi đó ô (3, 2) hết hàng trở thành ô loại, ô (3, 4) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J1. Bảng 3.13 10 11 10 9 8 u1 =-5 15 - - 35 (2) 12 12 5 13 11 u2 = -3 36 54 - - (1) 19 18 6 14 15 u3 = 0 - - 60 10 0 18 17 7 15 12 u4 = -3 - - - - 80 v1 = 15 V2 = 15 v3 = 6 v4 =14 v5 =15 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J1, ta đƣợc hệ thống thế vị nhƣ bảng 3.13. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij, ta thấy ô (1, 5) và ô (2, 5) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (1, 5) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(1,5), (3, 5), (3, 4), (1, 4)}. q = min{35, 0} = 0. - 77 -
13. Điều chỉnh 0 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X2: khi đó ô (3, 5) trở thành ô loại, ô (1, 5) trở thành ô chọn, ta có hệ ô chọn cơ sở J2. Bảng 3.14 10 11 10 9 8 u1 =-5 15 - - 35 0 12 12 5 13 11 u2 = -3 36 54 - - - 19 18 6 14 15 u3 = 0 - - 60 10 - 18 17 7 15 12 u4 = -1 - - - - 80 v1 = 15 v2 = 15 v3 = 6 v4 =14 v5 =13 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J2, ta đƣợc hệ thống thế vị nhƣ bảng 3.14. - Kiểm tra tiêu chuẩn tối ƣu: ij 0, (i, j) . Vậy phƣơng án cực biên X2 là phƣơng án tối ƣu: 15 0 0 35 0 36 54 0 0 0 X 2 0 0 60 10 0 0 0 0 0 80 Khi đó tổng cƣớc phi vận chuyển nhỏ nhất là: f(X2) = 10.15 + 9.35 + 12.36 + 12.54 + 6.60 + 14.10 + 12.80 = 3005. 3. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT m n 3.1. Phát lớn hơn thu: ( ai b j ) i 1 j 1 - 78 -
14. Khi vận chuyển xong cho các trạm thu thì các trạm phát còn tồn kho một m n lƣợng hàng tổng cộng là ai b j . Bài toán đặt ra nên để trạm phát nào phải i 1 j 1 chịu tồn kho và tồn bao nhiêu thì tổng chi phí vận chuyển sẽ thấp nhất. Để giải quyết bài toán này, ta lập thêm trạm thu thứ n + 1 (gọi là trạm thu m n giả) với nhu cầu nhận về là bn 1 ai b j , cƣớc phí từ các trạm phát đến các i 1 j 1 trạm thu giả là ci n+1 = 0, i = 1, m . Khi đó ta đƣợc bài toán vận tải cân bằng thu phát, tìm phƣơng án tối ƣu cho bài toán cân bằng này, từ đó suy ra phƣơng án tối ƣu của bài toán gốc: trạm phát nào phân hàng cho trạm thu giả thì trạm phát đó phải chịu tồn hàng. Chú ý rằng, khi giải bài toán trên nếu dùng phƣơng pháp cƣớc phí bé nhất để tìm phƣơng án cực biên xuất phát ta ƣu tiên phân phối hàng tối đa vào các ô có cƣớc phí dƣơng bé nhất trƣớc, rồi cuối cùng mới đến các ô có cƣớc phí bằng 0. Ví dụ 3.5: Tìm phƣơng án vận chuyển tối ƣu của bài toán vận tải (Bảng 3.15). Bảng 3.15 T 25 35 42 53 P 45 4 8 7 6 38 10 12 3 9 57 7 5 4 12 20 11 1 5 8 m n Giải: - Kiểm tra điều kiện cân bằng thu phát: ai 160, b j 155, nhƣ vậy i 1 j 1 phát lớn hơn thu. Ta lập thêm trạm thu giả B4 với nhu cầu nhận về tƣợng trƣng là: - 79 -
15. 4 4 b5 ai bj = 160 – 155 = 5 đơn vị hàng, cƣớc phí ci5 = 0, i = 1,4. Khi đó i 1 j 1 ta đƣợc bài toán vận tải cân bằng thu phát nhƣ bảng 3.16. Bảng 3.16 T 25 35 42 53 5 P 45 4 8 7 6 0 38 10 12 3 9 0 57 7 5 4 12 0 20 11 1 5 8 0 - Tìm phƣơng án cực biên xuất phát: Dùng phƣơng pháp cƣớc phí bé nhất, ta thu đƣợc phƣơng án cực biên X0 nhƣ bảng 3.17. Bảng 3.17 T 25 35 42 53 5 P 4 8 7 6 0 45 25 20 10 12 3 9 0 38 38 7 5 4 12 0 57 15 4 33 5 11 1 5 8 0 20 20 Tập ô cơ sở J0 là tập các ô chọn nhƣ bảng trên. - 80 -
16. Bảng 3.18 4 8 7 6 0 u1 = -6 25 - - 20 - 10 12 3 9 0 u2 = -1 - - 38 (2) - 7 5 4 12 0 u3 = 0 (3) 15 4 33 5 11 1 5 8 0 u4 = -4 - 20 - (0) - v1=10 v2 = 5 V3 = 4 V4=12 v5 = 0 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J0, ta đƣợc hệ thống thế vị nhƣ bảng 3.18. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij, ta thấy ô (3, 1) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (3.1) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(3, 1), (1, 1), (1, 4), (3, 4)}. q = min{25, 33} = 25. Điều chỉnh 25 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X1: Khi đó ô (1, 1) hết hàng trở thành ô loại, ô (3, 1) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J1. Bảng 3.19 4 8 7 6 0 u1 = -6 - - - 45 - 10 12 3 9 0 u2 = -1 - - 38 (2) - 7 5 4 12 0 u3 = 0 25 15 4 8 5 11 1 5 8 0 u4 = -4 - 20 - (0) - V1=7 v2 = 5 V3 = 4 V4=12 v5 = 0 - 81 -
17. - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J1, ta đƣợc hệ thống thế vị nhƣ bảng 3.19. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij, ta thấy ô (2, 4) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (2, 4) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(2, 4), (3, 4), (3, 3), (2, 3)}. q = min{8, 38} = 8. Điều chỉnh 8 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X2: Khi đó ô (3, 4) hết hàng trở thành ô loại, ô (2, 4) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J2. Bảng 3.20 4 8 7 6 0 u1 = -4 4 - - - 45 - 10 12 3 9 0 u2 = -1 - - 30 8 - 7 5 4 12 0 u3 = 0 25 15 12 - 5 11 1 5 8 0 u4 = -4 - 20 - - - V1=7 v2 = 5 V3 = 4 v4=10 v5 = 0 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J2, ta đƣợc hệ thống thế vị nhƣ bảng 3.20. - Kiểm tra tiêu chuẩn tối ƣu: ij 0, (i, j). Vậy phƣơng án cực biên X2 là phƣơng án tối ƣu: 0 0 0 45 0 0 0 30 8 0 X . 2 25 15 12 0 5 0 20 0 0 0 Phƣơng án tối ƣu của bài toán gốc là: - 82 -
18. 0 0 0 45 0 0 30 8 X , 25 15 12 0 0 20 0 0 theo phƣơng án này trạm phát A3 phải chịu tồn kho 5 đơn vị hàng. khi đó chi phí vận chuyển nhỏ nhất là:f(X) = 6.45 + 3.30 + 9.8 + 7.25 + 5.15 + 4.12 + 1.20 = 750. m n 3.2. Phát ít hơn thu: ( ai b j ) i 1 j 1 Khi vận chuyển hết hàng từ các trạm phát đến các trạm thu theo nhu cầu của các trạm thu, thì các trạm thu còn thiếu so với nhu cầu một lƣợng hàng tổng cộng n m là b j ai . Bài toán đặt ra nên để trạm thu nào phải chịu thiếu hàng và thiếu j 1 i 1 bao nhiêu thì tổng chi phí vận chuyển sẽ thấp nhất. Để giải quyết bài toán này, ta lập thêm trạm phát Am + 1 thứ m + 1 (gọi là n m trạm phát giả) với lƣợng hàng cần chuyển đi là am 1 b j ai , cƣớc phí từ j 1 i 1 các trạm phát giả đến các trạm thu là cm+1 j = 0, j = 1, n . Khi đó ta đƣợc bài toán vận tải cân bằng thu phát, tìm phƣơng án tối ƣu cho bài toán cân bằng này, từ đó suy ra phƣơng án tối ƣu của bài toán gốc: trạm thu nào nhận hàng của trạm phát giả thì trạm thu đó phải chịu thiếu hàng. Ví dụ 3.6: Cho bài toán vận tải Bảng 3.21 110 90 110 15 17 14 80 60 12 10 11 100 20 16 21 - 83 -
19. a. Viết dạng toán học của bài toán. b. Tìm phƣơng án vận chuyển tối ƣu. m n Giải: a. Kiểm tra điều kiện cân bằng thu phát: ai 240, b j 310, nhƣ vậy i 1 j 1 phát ít hơn thu, do đó các trạm phát tiêu thụ hết hàng, các trạm thu phải chịu thiếu hàng. Gọi xij là lƣợng hàng từ trạm phát Ai, đến trạm thu Bj (i 1,3, j 1,3). Khi đó ta có mô hình toán học nhƣ sau: Tìm ma trận X = (xij)3x3 sao cho: f(X) = 15x11 + 17x12 + 14x13 + 12x21 + 10x22 + 11x23 + 20x31 + 16x32 + 21x11 min. x11 + x12 + x13 = 80 x21 + x22 + x24 = 60 x31 + x32 + x33 = 100 x11 + x21 + x31 110 x21 + x22 + x32 90 x13 + x23 + x33 110 xij 0, i 1,3, j 1,3 b. Ta lập thêm trạm phát giả A4 với luợng hàng tƣợng trƣng cần chuyển đi là: 3 3 a4 b j ai = 310 - 270 = 70 đơn vị hàng, cƣớc phí c4j = 0, j = 1,3 . Khi đó j 1 i 1 ta đƣợc bài toán vận tải cân bằng thu phát trong bảng 3.22. - 84 -