CHƯƠNG IV BÀI TỐN VÂN TẢI 4.1 MƠ HÌNH TỐN HỌC CỦA BÀI TOÁN VẬN TẢI 4.1.1 Nội dung Cần vận chuyển loại hàng hoá từ m trạm phát (các kho, xí nghiệp sản xuất, ) ký hiệu Ax, A2, Am vởi khả cung cấp tương ứng ax, a2, ,am đơn vị hàng tới n trạm thu (các trung tâm tiêu thụ), ký hiệu Bx, B2, ,Bn vởi nhu cầu tiêu thụ tương ứng bx, b2, , bn đơn vị hàng Biết cước phí vận chuyển áơn vị hàng hố từ trạm phát Aj đến trạm thu Bj Cy (i = 1, 2, ,m; j = 1, 2, ,n) Giả thiết cước phí vận chuyển sô không phụ thuộc vào lượng hàng vận chuyển, nghĩa chi phí vận chuyển cung đường định tỷ lệ thuận với lượng hàng vận chuyển Tuy nhiên thực tế giả thiết thực Để đơn giản giả thiết rằng: 1=1 j=i nghĩa tổng khả cung cấp trạm phát tổng nhu cầu trạm thu 145 Nhiệm vụ đặt xây dựng phương án vận chuyển hợp lý nhất, tức xác định lượng hàng cần vận chuyển từ trạm phát đến trạm thu cho: a Mỗi trạm phát phát hết hàng, trạm thu nhận đủ hàng yêu cầu b Tổng chi phí vận chuỵển nhỏ Chúng ta ký hiệu Cjj cước phí vận chuyển đơn vị hàng hoá từ trạm phát Aj đến trạm thu Bj (i = 1, 2, ,m; j= 1, 2, , n) Ký hiệu Xjj (i = 1, 2, , m; j = 1, 2, , n) lượng hàng chưa biết phải vận chuyển từ Ai đến Bj Như sơ biến tốn vận tải m.n Từ giả thiết cho ta thấy: a Từng trạm phát phải phát hết khả cung cấp có trạm thu phải nhận đủ theo yêu cầu Nói cách khác biến Xý- cần phải thoả mãn m + n phương trình (ràng buộc)X11 + x12 + •••• + xln = al X21 + x22 + •••■ + x2n xml + X21 + X11 = a2 xm2 +•••+ xmn n + xml = bl + x22 + + xm2 = b2 x12 x2n +••■+ xmn xln (4.1) (4.2) bn b Tổng chi phí vận chuyển (hàm mục tiêu) (4.3) i=i j=l cần đạt giá trị cực tiểu 146 c Các biến Xjj không âm (suy từ thực tế, vận chuyển lượng hàng hoá âm), tức là: Xjj > (i=l, 2, , m ; j = 1,2, , n) (4.4) d ỉ ai=ỉ bj (điểu kiện cân thu phát) (4.5) i=i j=i Tởi ta phát biểu mơ hình tốn học tốn vận tải sau: 4.1.2 Mơ hình tốn học Tìm mxn số thực {Xjj} thoả mãn điều kiện sau: Ề CjjXjj -> i=l j=l ỉ Xij = Si (i=l,2, ,m) (4.1a) bj 0=1,2, .,n) (4.2a) j=l Ề Xụ = i=l Xjj > (i=l, 2, , m ; j=l, 2, , n) (4.4a) Vối giả thiết: ¿ bj (cân thu phát) (4.5) i=i j=i Nhận xét: Bài toán vận tải toán q hoạch tuyến tính dạng tắc Vì định nghĩa (phương án, phương án cực biên, phương án tối ưu, sở phương án cực biên, véctơ biến sở, véctơ biến phi sỏ, ) 147 định lý qui hoạch tuyến tính áp dụng cho tốn vận tải đương nhiên giải phương pháp đơn hình Nhưng cấu tạo đặc biệt tốn vận tải, người ta xây dựng sơ phương pháp khác giải đơn giản tiện lợi mà duới trình bày phương pháp thơng dụng để giải tốn vận tải - phương pháp vị 4.3 MƠ TẢ BÀI TỐN DƯỚI DẠNG BẢNG Trước nghiên cứu tính chất riêng phương pháp giải toán vận tải, ta chuyển thành dạng bảng sau: Ta xây dựng bảng gồm m hàng, n cột Mỗi hàng đặc trưng cho trạm phát, cột đặc trưng cho trạm thu - Hàng ghi tên trạm thu Bj nhu cầu bj tương ứng (j = 1, 2, ,n) - Cột đầu ghi tên trạm phát Aj khả cung cấp aj tương ứng (i = 1, 2, ,m) - Trong bảng giao hàng i cột j gọi ô (ij), đặc trưng cho đoạn đưòng nôi trạm phát Aị với trạm thu Bj nên ô ta ghi Cjj Mỗi (ij) cịn tương ứng với biến Xịj, đồng thời tương ứng với véctơ Ajj (hệ sô biến Xịj hệ ràng buộc la 4.2a) Như liệu toán vận tải thể bảng 4.1 gọi bảng vận tải 148 Bảng 4.1 Thu Phát\ Aựa-i) B1 b2 Bn (bi) (b2) (bn) C11 C12 X11 A2(a2) X12 C22 C21 Cm1 Xm1 Xin C2n X22 X21 Mam) cin Cm2 Xm2 X2n Cmn Xmn Nếu bảng thay cho cước phí vận chuyển ta ghi khoảng cách tính theo km trạm, thay cho tổng chi phí vận chuyến tổng số km cần vận chuyển 4.2 CÁC TÍNH CHẤT BẢN CỦA BÀI TỐN VẬN TẢI Ngồi tính chất chung tốn qui hoạch tuyến tính, tốn vận tải cịn có tính chất riêng phát biểu 149 Định lý 4.1 Bài tốn vận tải cân thu phát có phương án cực biên ưu Chứng minh Đặt d = ỉa.-ỉ bj , xác định hệ thống sô {Xjj} 1=1 sau* j=l aịbj Xjj = d (1=1, 2, m J J —1, 2, , n), Rõ ràng Xịj > (Vij), : s = bjS^ = «ij = i=l f 0-1,2, ,n) i=l a i=l Như |Xjj : Xÿ = bj (i=l,2, ,m) ai°i (i = 1, 2, , m ; j = 1, 2, , n) j phương án tốn Hơn Cịì > (Vij), Xjj > V(ij) nên: CÿXjj > nghĩa hàm mục tiêu bị chặn dưởi i=i j=l khơng Do đó, theo tính chất tốn qui hoạch tuyến tính, tốn vận tải có phương án hàm mục tiêu bị chặn chắn có phương án tốt có phương án cực biên tơt Nhìn vào hệ ràng buộc (4.1) (4.2) ta thấy ma trận hệ sô ẩn có dạng 150 1 A Véctơ Ajj hệ số ẩn Xjj có thành phần thứ i (m+j) (m + n - 2) thành phần khác 0 Aii - thứ tự i - thứ tự m+j = O J - thú tự m+n Véctơ cột Ajj viết: Ajj = Ej + Ej+m (4.6) Trong Ej Ej+m hai véctơ đơn vị (m + n) chiều tương ứng có thành phần thứ i thứ j + m Khơng khó khăn ta chứng minh ma trận A có hạng m + n -1 Nói cách khác hệ (4.1) (4.2) có 151 (m + n -1) ràng buộc độc lập, tức phương trình hệ (4.1) (4.2) hệ (m 4- n -1) phương trình cịn lại (hiển nhiên với giả thiết cân thu phát) chẳng hạn ta cộng phương trình (4.1) trừ vào tổng (n-1) phương trình đầu (4.2) ta nhận phương trình cuối (4.2) Như ta phát biểu tính chất hai tốn vận tải: Ma trận hệ số A hệ ràng buộc (4.1) (4.2) có hạng (m +n -1) Từ liên hệ với định nghĩa phương án cực biên tốn quy hoạch tuyến tính ta suy ra: - Phương án cực biên tốn vận tải có khơng m + n - thành phần dương - Phương án cực biên toán vận tải gọi khơng suy biến có m + n -1 thành phần dương gọi suy biến có m + n -1 thành phần dương - Mỗi phương áñ cực biên ứng với sở gồm m + n -1 véctơ Ajj độc lập tuyến tính Trong trường hợp phương án cực biên không suy biến Xo = {Xij(0)} có sở hệ (A¡j : x¡j > 0} gồm m + n -1 véctơ độc lập tuyến tính Trở lại bảng vận tải ta thấy ô (ij) véctơ Ajj ẩn Xjj có tương ứng -1 (ĩj) gọi chọn có lượng hàng phân phối Xjj > gọi ô loại Xÿ = Như phương án cực biên có khơng q (m +n -1) chọn 152 Phương án cực biên gọi không suy biến có m + n -1 chọn suy biến có m + n -1 ô chọn Đê thấy rõ tính độc lập hay phụ thuộc hệ véctơ (Ajj} gắn với phân bố ô tương ứng vởi chúng bảng vận tải ta xét hệ véctơ sau: Ah Ajz ’ • • • ’ \jk Ají tất số thứ (chỉ số hàng) sô thứ hai (chỉ sô cột) xuất hai lần Nếu ta cho tương ứng véctơ với ô bảng vận tải ta thấy hàng bảng có khơng có tương ứng với véctơ Tương tự cột bảng Nếu nối Ô tương ứng bảng với hệ véctơ (4.7) đoạn nằm ngang thảng đứng nhận chu Hình 4.1 Như vịng tập hợp bảng vận tải mà nằm hàng (cùng cột) với đứng trưốc nó, đồng thời nằm cột (cùng hàng) với ô đứng sau 153 Tứ định nghĩa ta thấy hàng cột mà vòng qua có hai thuộc vịng, tổng số vịng sơ chẵn bốn Có thể mơ tả vịng dạng bảng sau: (iiJi); (Í1J2); Ơ2jạ);-(ifcjfc); (ikJi) Định lý 4.2 Điều kiện cần đủ để tập hợp cho có chứa vịng hệ véctơ {Ajj} tương ứng phụ thuộc tuyến tính Chứng minh Điêu kiện càn ■ ■ • > AkjJ phụ thuộc tuyến tính đủ (vì hệ chứa hệ phụ thuộc tuyến tính hệ phụ thuộc tuyến tính) Theo (4.6) ta có: A:u-h: — Aị j + A¿ ;+ + Aj~kJkj — Aị j = (Ej*1 + E Jl+rn j ) — ”2^2 ~kh (E:h + EjJ2-1H) + (E;*2 + EjJ2-m/) + + (EjK + E:Jk-in ) — (E; + EjJl-m') = v ‘k Chứng tỏ hệ véctơ: { i, A1 j2 A2j2 • • •, \jk AkJ1 phụ thuộc tuyến tính Điêu kiện đủ Giả sử tập hợp ô cho tương ứng với hệ véctơ {Aý-} phụ thuộc tuyến tính, ta phải chứng minh tập hợp cho có chứa vịng 154