Giáo trình Toán kinh tế (Dùng cho hệ Đại học và Cao đẳng): Phần 2

(NB) Giáo trình Toán kinh tế (Dùng cho hệ Đại học và Cao đẳng): Phần 2 sẽ tiếp tục giới thiệu tới các bạn về bài toán vận tải; một số bài toán ứng dụng bài toán quy hoạch tuyến tính. Mời các bạn cùng tìm hiểu và tham khảo nội dung thông tin tài liệu.
Nội dung trích xuất từ tài liệu:
Giáo trình Toán kinh tế (Dùng cho hệ Đại học và Cao đẳng): Phần 2 Chƣơng 3 BÀI TOÁN VẬN TẢI 1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI 1.1. Nội dung kinh tế và các dạng toán học của bài toán vận tải 1.1.1. Nội dung kinh tế của bài toán Giả sử cần vận chuyển một loại hàng hóa từ m trạm phát, ký hiệu là A i (i = 1, m ). Lƣợng hàng cần chuyển đi ở mỗi trạm A i tƣơng ứng là ai (đơn vị hàng), tới n trạm cần thu hàng, ký hiệu B j (j = 1, n ), lƣợng hàng cần thu về ở mỗi trạm B j tƣơng ứng bj (đơn vị hàng). Giả sử cƣớc phí vận chuyển từ trạm phát hàng A i tới trạm thu B j là cij (đơn vị tùy theo qui ƣớc). m n Giả thiết ai > 0, bj > 0, cij 0 ( i 1, m, j 1, n ) và ai bj Q (bài toán i 1 j 1 cân bằng thu phát). Hãy lập kế hoạch vận chuyển hàng hoá sao cho tổng chi phí vận chuyển nhỏ nhất đồng thời thoả mãn nhu cầu thu phát hàng (các trạm phát, phát hết hàng và các trạm thu, thu đủ hàng). 1.1.2. Mô hình toán học của bài toán Xác định kế hoạch vận chuyển hàng nghĩa là xác định lƣợng hàng cần chuyển đi từ các trạm phát tới các trạm thu tƣơng ứng. Gọi xij là lƣợng hàng hoá vận chuyển từ trạm phát A i tới trạm thu B j (xij 0, i = 1, m , j = 1, n ). n Mọi trạm phát, phát hết hàng nên ta có: x ij a i , i 1, m . j 1 m Mọi trạm thu, thu đủ hàng nên ta có: x ij b j , j 1, n. i 1 m n Nhƣ vậy tổng chi phí vận chuyển là: cij x ij , và đòi hỏi phải cực tiểu. i 1j 1 Khi đó mô hình toán học của bài toán sẽ là: - 56 - m n f (X) cijx ij min (3.1) i 1 j 1 n x ij a i , (i 1, m) (3.2) j 1 m x ij b j , ( j 1, n ) (3.3) i 1 xij 0 (i = 1, m , j = 1, n ). (3.4) Trong đó ma trận X = (xij)m.n đƣợc gọi là ma trận phân phối hàng cần phải tìm. Hàm f(X) đƣợc gọi là hàm mục tiêu và là tổng chi phí vận chuyển. Hiển nhiên (3.1) (3.2) (3.3) (3.4) là mô hình toán học của một bài toán qui hoạch tuyến tính dạng chính tắc. Chú ý: Bài toán vận tải (3.1) (3.2) (3.3) (3.4) đƣợc viết dƣới dạng tƣờng minh nhƣ sau: c11x11 + c12x 12 + … + c1nx 1n + c 21x 21 + c22x22 + … + c2nx2n + … + cm1x m1 + cm2xm2 + … +c mnx mn min. x11 + x 12 + … + x 1n = a1 x 21 + x22 + … + x2n = a2 ………………………………………………………………… x m1 + xm2 + … +x mn = am x11 + x21 + ………… …... + xm1 = b1 x12 + x22 + ……………….. + xm2 = b2 …………………………………………………………… + x1n + x2n + ………………. + xmn = bn Theo đó, ma trận ràng buộc A của bài toán (3.1) (3.2) (3.3) (3.4) là: - 57 - 11...1 00...0 ... 00...0 00...0 11...1 ... 00...0 m ... ... ... ... 00...0 00...0 ... 11...1 A 10...0 10...0 ... 10...0 01...0 01...0 ... 01...0 n ... ... ... ... 00...1 00...1 ... 00...1 n n n Nhận thấy ma trận A đƣợc chia làm 2m khối: m khối của m dòng đầu thì ở mỗi khối là một ma trận cấp m.n có một dòng có các phần tử là 1, còn các dòng khác các phần tử đều là 0; khối thứ k có dòng thứ k là 1 với k = 1, m . Còn m khối của n dòng sau thì mỗi khối là một ma trận đơn vị cấp n. Gọi Aij là cột hệ số của ẩn xij , ta có Aij là véc tơ cột thứ j trong nhóm cột thứ i của ma trận A, khi đó ta luôn có Aij = Ei + E m + j, i = 1, m, j 1, n , trong đó Ek là ma trận cấp (m.n, 1) có phần tử ở hàng thứ k là 1, các phần tử khác là 0. Định nghĩa 3.1. Mọi bài toán qui hoạch tuyến tính có dạng toán học (3.1) (3.2) m n (3.3) (3.4) với giả thiết ai > 0, bj > 0, cij 0 ( i 1, m, j 1, n ); ai bj Q đƣợc i 1 j 1 gọi là bài toán vận tải cân bằng thu phát. Ngoài bài toán vận tải cân bằng thu phát hay bài toán dạng đóng ta có hai bài toán vận tải không cân bằng thu phát hay bài toán dạng mở nhƣ sau: m n +) ai bj : i 1 ...