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