Giáo trình Toán kinh tế - Trần Ngọc Minh

ương án tối ưu y vào các ràng buộc của bài toán đối ngẫu ta thấy ràng buộc (5) thỏa lỏng, chứng tỏ với phương pháp sản xuất thứ hai mọi hao phí bỏ ra không được chuyển hoá hết vào giá trị sản phẩm nên không sử dụng phương pháp sản xuất này (x2 = 0). Trong phương án tối ưu y ta có y2 = 2 > 0, điều này nói lên sản phẩm hàng loại hai được đánh giá là có giá trị và chính nó có vai trò làm tăng tổng giá trị sản phẩm. Tương ứng trong phương án tối ưu x ràng buộc (2) thỏa chặt, nghĩa là sản phẩm hàng loại hai sản xuất vừa đủ nhu cầu tối thiểu, sản xuất đến đâu tiêu thụ hết đến đấy. Vì vậy trong phương án sản xuất tiếp theo nên mở rộng sản xuất theo hướng sản phẩm hàng loại hai phải tăng thêm số lượng. PT IT PT IT Bài giảng Toán kinh tế Chương 2: Mô hình quy hoạch tuyến tính 89 Ở đây ràng buộc (6) của bài toán đối ngẫu thỏa chặt, điều này nói lên có thể sử dụng cách sản xuất thứ ba thay thế cho cách sản xuất thứ nhất trong trường hợp cách sản xuất thứ nhất gặp khó khăn về trang thiết bị, nhiên liệu,Ràng buộc (3) của bài toán gốc thỏa lỏng nên trong phương án đánh giá tối ưu y sản phẩm này được xem là không có giá trị, nghĩa là trong phương án sản xuất tiếp theo không nên chú trọng sản phẩm này. Câu hỏi và bài tập ôn chương 2 I. Lý thuyết 1.Trình bày mô hình bài toán quy hoạch tuyến tính dạng tổng quát, dạng chuẩn tắc và dạng chính tắc ? Cho thí dụ ? 2. Thế nào là miền ràng buộc, phương án, phương án tối ưu ? 3. Định nghĩa phương án cực biên ? 4. Các phép biến đổi bài toán quy hoạch tuyến tính ? 5. Trình bày phương pháp đơn hình giải bài toán quy hoạch tuyến tính ? 6. Trình bày các phương pháp tìm phương án cực biên ban đầu ? 7. Trình bày lược đồ tổng quát khi xây dựng bài toán đối ngẫu ? Cho thí dụ ? 8. Các định lý đối ngẫu và ứng dụng khi tìm nghiệm ? 9. Phương pháp đơn hình đối ngẫu ? 10. Ý nghĩa kinh tế của cặp bài toán đối ngẫu ? II. Bài tập 1. Tìm các phương án cực biên không suy biến của bài toán quy hoạch tuyến tính sau : f(x) = 2x1 + x2 – 3x3 + 5x4 + x5 → Min 3x1 + 4x2 - x3 + x4 = 10 x1 - 3x2 - x4 + x5 = 0 -2x1 + x3 + 3x4 = 9 xj ≥ 0 (j =1,4 ) 2. Cho bài toán quy hoạch tuyến tính : f(x) = -3x1 + x2 + 7x3 + 5x4 → Min0 x1 + 2x2 – 3x3 + x4 ≤ 37 -x1 - x2 + x3 + 3x4 = -5 2x1 + 3x2 – x3 - x4 ≥ 25 xj ≥ 0 (j =1,4 ) a) Chứng tỏ x0 = (14, 0, 0, 3) là phương án cực biên. Lợi dụng x0 giải bài toán bằng phương pháp đơn hình ? b) Viết bài toán đối ngẫu và tìm nghiệm đối ngẫu ? 3. Cho bài toán quy hoạch tuyến tính: f(x) = -x1 + x2 - 2x3 + 2x4 + x5 -3x2 + 3x3 + 7x4 + 13x5 + 20x6 = 32 -x2 + x3 + 2x4 + 4x5 + 6x6 = 6 2x1 + 2x2 – 8x3 – 6x4 – 8x5 - 13x6 = -24 xj ≥ 0 (j =1,6 ) PT IT PT IT Bài giảng Toán kinh tế Chương 2: Mô hình quy hoạch tuyến tính 90 a) Xét tính chất của véc tơ x0 = (0, 38, 0, 6, 8, 0) ? Xuất phát từ x0 dùng phương pháp đơn hình tìm lời giải của bài toán trong 2 trường hợp : f(x) → Min và f(x)→ Max. b) Khi f(x) → Min hãy tìm phương án tối ưu có x1= 23 ? 4. Cho bài toán quy hoạch tuyến tính: f(x) = x1 + 5x2 - 3x3 + 6x4 → Min -x1 + 3x2 - x3 + x4 = -2 3x1 - x2 + 2x3 - x4 ≥ 14 2x1 + x2 + x3 – 3x4 ≤ 30 xj ≥ 0 (j =1,4 ) a) Chứng tỏ x0 = (0, 2, 8, 0) là phương án cực biên ? Lợi dụng x0 giải bài toán bằng phương pháp đơn hình ? b) Có kết luận gì khi f(x) → Max, khi đó xác định một phương án có thành phần x4 > 0 và f(x) = 0 ? 5. Cho bài toán quy hoạch tuyến tính: f(x) = x1 - 3x2 - 4x3 - 2x4 + 3x5 → Min 2x1 - 22x3 + x4 + 14x5 ≥ 26 x1 + 2x2 + x3 - 3x4 + 2x5 = -12 -x1 - x2 + 2x3 + 2x4 – 4x5 = 4 4x1 + 7x2 – 4x3 – 9x4 + 15x5 ≤ -4 xj ≥ 0 (j =1,5 ) a) Xét tính chất của véc tơ x0 = (12, 0, 0, 8, 0) ? Lợi dụng x0 giải bài toán bằng phương pháp đơn hình ? Xác định tập phương án tối ưu, chỉ ra các phương án cực biên tối ưu, phương án tối ưu có x4 = 33 ? b) Xác định phương án cực biên tối ưu của bài toán đối ngẫu ? 6. Cho bài toán quy hoạch tuyến tính : f(x) = c1x1 + c2x2 + c3x3 + c4x4 + x5 + x6 → Min x1 - x2 + 3x3 - 7x4 - 2x5 + x6 = 14 -4x1 + 6x2 - 9x3 +21x4 + 5x5 - 2x6 = -45 -2x1 + 4x2 – x3 + 2x4 – x5 + x6 = -15 xj ≥ 0 (j =1,6 ) và phương án cực biên x0 = (12, 0, 0, 0, 7, 16) a) Biết c1 = 0 xác định những thành phần còn lại của véc tơ c để x 0 là phương án tối ưu ? Tìm phương án tối ưu tương ứng của bài toán đối ngẫu ? b) Tìm điều kiện đối với véc tơ c để x0 là phương án tối ưu duy nhất ? 7. Giải bài toán sau bằng phương pháp đơn hình đối ngẫu : f(x) = 3x1 + 5x2 + x3 – 2x4 → Min - 7 2 x2 + x3 + x4 ≤ 8 x1 + x2 - x3 - 2x4 = -6 -3x2 + 2x3 + x4 ≥ 20 5 2 x2 – 5x3 ≥ -30 PT IT PT IT Bài giảng Toán kinh tế Chương 2: Mô hình quy hoạch tuyến tính 91 xj ≥ 0 (1,4 ) Sử dụng kết quả tính toán tìm lời giải của bài toán khi thay dấu « ≤ « ở ràng buộc (1) bằng dấu « ≥ « ? 8. Cho bài toán quy hoạch tuyến tính : f(x) = -4x1 - 5x2 + 2x3 x1 + 3x2 – 3x3 = 17 -x1 - x2 + 2x3 ≤ 2 4x1 + 5x2 - 2x3 ≤ 43 2x1 - x2 + 8x3 = -1 xj ≥ 0 (j =1,3 ) a) Xác định tập phương án cực biên của bài toán. Chứng tỏ bài toán giải được và chỉ ra phương án cực biên tối ưu trong hai trường hợp f(x) → Min và f(x) → Max ? b) Viết bài toán đối ngẫu tìm phương án tối ưu của nó khi f(x) → Min ? 9. Cho bài toán quy hoạch tuyến tính: f(x) = 4x1 + 7x2 + 2x4 – 6x5 - x6 → Min -2x1 - x3 + 5x4 + x6 ≤ 9 x1 + 2x2 - 2x4 + 3x6 ≥ -8 3x1 - 4x4 + 3x5 + 6x6 ≤ 15 x1, x4, x6 ≥ 0 a) Viết bài toán đối ngẫu. Chứng tỏ bài toán có phương án cực biên và giải được. Tìm phương án cực biên tối ưu của cặp bài toán đối ngẫu. Từ đó suy ra bài toán giải được với mọi véc tơ b, xác định trị tối ưu của hàm mục tiêu trong trường hợp này ? b) Với c6 = -5/2 chứng tỏ bài toán không giải được. Xác định một dãy phương án trên đó trị số hàm mục tiêu giảm vô hạn ? 10. Một công ty kinh doanh thương mại chuẩn bị cho một đợt khuyến mại nhằm thu hút khách hàng bằng cách tiến hành quảng cáo trên hệ thống phát thanh và truyền hình. Chi phí cho một phút quảng cáo trên truyền hình là 400.000đ, trên hệ thống phát thanh là 80.000đ. Đài phát thanh chỉ nhận các chương trình quảng cáo dài ít nhất 5 phút. Do nhu cầu quảng cáo trên truyền hình rất lớn nên đài truyền hình chỉ nhận phát các chương trình quảng cáo tối đa là 4 phút. Theo các phân tích xã hội học, cùng thời lượng một phút quảng cáo, trên truyền hình sẽ hiệu quả gấp 6 lần trên sóng phát thanh. Công ty dự định chi tối đa là 1.600.000đ cho đợt quảng cáo. Công ty nên đạt thời lượng quảng cáo trên phát thanh và truyền hình như thế nào để đạt hiệu quả cao nhất ? 11. Doanh nhân A có 2 tỷ đồng muốn đầu tư vào các danh mục sau đây : - Gửi tiết kiệm không kỳ hạn với lãi suất 4%/năm - Mua trái phiếu chính phủ với lãi suất 8%/năm. - Cho doanh nghiệp tư nhân vay với lãi suất 15%/năm. - Mua đất phân lô bán nền với lãi suất kỳ vọng 20%/năm. Thời gian đáo hạn giả thiết là như nhau. Các hình thức đầu tư đều có rủi ro. Để hạn chế rủi ro doanh nhân A được các nhà tư vấn hướng dẫn như sau : - Không cho doanh nghiệp tư nhân vay quá 30% vốn. - Số tiền mua trái phiếu chính phủ không vượt quá số tiền đầu tư trong 4 lĩnh vực kia. - Ít nhất 20% số tiền đầu tư phải thuộc lĩnh vực tiết kiệm có kỳ hạn và trái phiếu. PT IT PT IT Bài giảng Toán kinh tế Chương 2: Mô hình quy hoạch tuyến tính 92 - Tỷ lệ tiết kiệm không kỳ hạn trên tiết kiệm có kỳ hạn không vượt quá 1/3. - Số tiền mua đất không vượt quá 40% số vốn. Doanh nhân A muốn đầu tư toàn bộ vốn. Hãy lập mô hình bài toán tìm phương án đầu tư sao cho thu được lợi nhuận tối đa. Giải bài toán bằng thuật toán đơn hình. PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 92 CHƯƠNG 3 MÔ HÌNH BÀI TOÁN VẬN TẢI Trong chương 3 ta sẽ xét bài toán quy hoạch tuyến tính dạng đặc biệt - Bài toán vận tải - với các số liệu cụ thể. Trong chương này, ta đưa ra mô hình tổng quát của bài toán vận tải đồng thời làm quen với phương pháp giải phù hợp với đặc điểm cấu trúc của bài toán. 3.1 Nội dung và đặc điểm a) Nội dung kinh tế và mô hình toán học Đặt vấn đề: Như đã nêu ở mục 2.1 chương 2, mô hình toán học của bài toán vận tải có dạng như sau: f(x) = m n ij ij i=1 j=1 c x Min (Cực tiểu tổng chi phí vận chuyển) (3.1) Với các điều kiện ràng buộc: n ij i j=1 x = a , i = 1,m (mọi điểm phát giao hết hàng). (3.2) m ij j i=1 x = b , j = 1,n (mọi điểm thu nhận đủ hàng) (3.3) xij > 0 với i = 1,m , j = 1,n (lượng hàng vận chuyển không âm) (3.4) Ở đây m là điểm phát hàng, n là điểm tiêu thụ hàng. ai: là lượng hàng có (cung) ở điểm phát i ( i = 1,m ). bj: là lượng hàng yêu cầu ở điểm thu j ( j = 1,n ) . cij: là chi phí vận chuyển một đơn vị hàng từ điểm phát i tới điểm thu j. xij: biểu thị lượng hàng vận chuyển cần tìm từ điểm phát i tới điểm thu j. Điều kiện cần và đủ để bài toán (3.1)-(3.4) giải được là phải có điều kiện cân bằng thu phát, nghĩa là tổng cung bằng tổng cầu: n n i j j=1 j=1 a = b , (i = 1,m, j = 1,n)  (3.5) Bài toán vận tải (3.1) – (3.4) là một dạng đặc biệt của quy hoạch tuyến tính. Để thấy rõ điều này ta sắp xếp các biến số theo thứ tự x11, x12,.x1n, x21, x22,....., x2n,.., xm1, xm2,.., xmn và viết lại hệ ràng buộc. Ràng buộc chính (3.2) – (3.3) dưới dạng hệ m + n phương trình của m x n biến số xij như sau: x11 + x12 +. x1n = a1 x21 + x22 +. + x2n = a2 . xm1 + xm2 +...xmn = am x11 + x21 +.xm1 = b1 x12 ++ x22 +..+ xm2 = b2 ... x1n + x2n +..+ xmn = bn (3.6) PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 93 Ký hiệu ma trận A là ma trận hệ số của hệ phương trình trên (gồm m + n hàng và m x n cột), x = (x11, x12,., x1n, x21, x22,., x2n,.., xm1, xm2,, xmn) T là véc tơ cột m x n thành phần, c =( c11, c12,., c1n, c21, c22,., c2n,.., cm1, cm2,,cmn) T là véc tơ cột m x n thành phần. b = (a1, a2,., am, b1, b2,., bn) T là véc tơ cột vế phải (m + n thành phần). Bài toán vận tải (3.1) – (3.4) được viết lại thành bài toán quy hoạch tuyến tính dạng chính tắc: f = Min (3.7) Ax = b, x ≥ 0 (3.8) Ta gọi Aij là véc tơ cột của ma trận A ứng với biến xij. Dễ thấy rằng véc tơ này có hai thành phần bằng 1 tại dòng i và dòng m + j, còn các thành phần khác bằng 0. (3.1) gọi là hàm mục tiêu của bài toán vận tải. Véc tơ x thỏa mãn (3.2) – (3.4) gọi là một phương án của bài toán vận tải. Một phương án làm cho hàm mục tiêu đạt cực tiểu gọi là phương án tối ưu hay lời giải. Phương án x là phương án cực biên khi và chỉ khi các véc tơ cột Aij của ma trận A ứng với các thành phần xij > 0 là độc lập tuyến tính. Ta giả thiết là có điều kiện (3.5). Do bài toán vận tải có m + n ràng buộc chính, nên ta nghĩ rằng mỗi phương án cực biên cũng có m + n thành phần dương, nhưng thực tế nó chỉ có nhiều nhất m + n – 1 thành phần dương, vì trong số các ràng buộc này có một ràng buộc thừa (có thể bỏ đi mà không làm ảnh hưởng đến lời giải của bài toán). Một phương án cực biên của bài toán gọi là không suy biến nếu số phần tử của tập hợp G = {(i, j) : xij > 0} bằng m + n – 1, gọi là suy biến nếu G < m + n -1. Để cho gọn, ta ghi lại dữ liệu của bài toán dưới dạng bảng chữ nhật, gọi là bảng vận tải (bảng 3.1). Bảng gồm m + 1 hàng và n + 1 cột, cột 1 ghi khối lượng của các điểm phát hàng, dòng 1 ghi khối lượng yêu cầu của các điểm thu. Phần bảng còn lại gồm m x n ô. Nơi giao nhau ở hàng i, cột j ký hiệu là ô (i, j). Chi phí vận chuyển một đơn vị hàng cij được ghi góc trên bên trái của ô (i, j), lượng hàng vận chuyển xij ghi ở góc dưới bên phải của ô. Ô (i, j) biểu thị tuyến đường vận chuyển từ trạm phát i đến trạm thu j. Đặt cij = ∞ nếu không thể vận chuyển hàng từ i đến j. Đối với những ô có xij = 0 gọi là các ô phi cơ sở và trên bảng vận tải để trống (trường hợp ô chọn 0 được coi như ô cơ sở). Bảng 3.1: Bảng vận tải Thu Phát b1 .. bj .. bn a1 c11 x11 .. c1j x1j .. c1n x1n : : .. : .. : ai ci1 xi1 .. cij xij .. cin xin : : .. : .. : PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 94 am c1m x1m .. cmj xmj .. cmn x1n Với điều kiện (3.5) bài toán vận tải (3.1)- (3.4) có các tính chất quan trọng sau đây: Định lý 3.1: a) Bài toán vận tải luôn có phương án tối ưu. Vì: - Trị số hàm mục tiêu bị chặn dưới: cij ≥ 0 ( i, j), nên với mọi phương án x = {xij} ta có: m n ij ij i=1 j=1 c x 0 - Bài toán luôn có phương án: ký hiệu d = n n i j j=1 j=1 a = b  , xác định tập hợp {xij} như sau: xij = aibj /d ( i=1,m; j = 1,n ). Rõ ràng xij > 0 ( (i, j)), ngoài ra: n n j ij i i j=1 j=1 m m i ij j j i=1 i=1 b x = a = a (i =1,m) d a x = b = b (j =1,n) d     Như vậy {xij = aibj/d} với i=1,m; j = 1,n là một phương án của bài toán. b) Hạng của hệ phương trình (3.2) – (3.5) của bài toán bằng m + n – 1. Hệ phương trình (3.2) – (3.3) được viết lại thành hệ (3.6). Do có điều kiện (3.5) nên từ hệ này ta dễ dàng nhận thấy: Tổng của m phương trình đầu (vế phải là ai) bằng tổng của n phương trình sau (vế phải là bj). Điều này cho thấy mỗi phương trình (3.2), (3.3) có thể biểu diễn dưới dạng tổ hợp tuyến tính (với hệ số +1 hoặc - 1) của m + n – 1 phương trình còn lại và ma trận A của hệ có hạng nhỏ hơn hay bằng m + n – 1. Bây giờ ta chứng minh rằng bất kỳ m + n – 1 véc tơ hàng nào của A cũng độc lập tuyến tính. Thật vậy, xét chẳng hạn các hàng 2, 3,.., m + n của A. Ta nhân lần lượt các hàng 2, ., m, m + 1, ., m + n với số α2,, αm, β1, , βn; rồi cộng tất cả lại và cho bằng véc tơ không (gồm m x n thành phần bằng 0). Từ n toạ độ đầu tiên của đẳng thức véc tơ này ta nhận được: β1 = β2 = = βn = 0 Đối với toạ độ n + 1+, 2n + 1+,., (m - 1)x n + 1 ta nhận được: α2 + β1 = α3 + β1 = = αm + β1 = 0 Từ đó suy ra: α2 = α3 = .= αm = 0. Vậy hạng của ma trận A bằng m + n – 1. c) Nếu lượng cung, cầu ai, bj là nguyên thì lời giải của bài toán là số nguyên. Có thể dùng các phương pháp của quy hoạch tuyến tính để giải bài toán vận tải. Tuy nhiên do bài toán này có dạng đặc biệt nên người ta đã đề ra nhiều thuật toán giải hiệu quả hơn. Trong số đó có thuật toán thế vị sẽ được xét ở phần sau. Định nghĩa: Ta gọi dây chuyền là tập hợp các ô có dạng: (i1, j1), (i1, j2), (i2, j2), (i2, j3),, (is, js), (is, js + 1) hoặc (i1, j1), (i2, j1), (i2, j2), (i3, j3),, (is, js), (is + 1, js). PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 95 Một dây chuyền khép kín (js + 1  j1 hoặc is + 1 i1) gọi là một chu trình. Như vậy, mỗi cặp ô liền nhau trong dây chuyền ở trên cùng một hàng hay một cột và số ô trên mỗi dây chuyền có thể chẵn hay lẻ. Một chu trình bao giờ cũng gồm một số chẵn các ô. Thí dụ: Dãy ô đánh dấu “•” trong hình (3.1) a) và b) lập thành các dây chuyền, còn các ô với dấu “•” trong hình (3.1) c) – e) lập thành các chu trình: Hình 3.1: Dây chuyền: a), b). Chu trình: c), d), e). Cho G là một tập hợp ô bất kỳ của bảng vận tải. Mỗi ô thuộc G gọi là ô treo nếu nó là ô duy nhất của G trên hàng hay trên cột của ô đó. Với tập ô cho ở hình 3.1 a) thì ô (1, 1) và ô (4, 3) là các ô treo. Nếu loại khỏi G ô treo (1, 1) thì ô (1, 2) sẽ trở thành ô treo của tập hợp ô còn lại. Ta có mối liên hệ quan trọng sau đây: Định lý 3.2. Hệ véc tơ {Aij: (i, j)G} của bài toán vận tải là độc lập tuyến tính khi và chỉ khi tập hợp các ô thuộc G không tạo thành chu trình. Hệ quả 3.1. Véc tơ x = {xij} là một phương án cực biên của bài toán khi và chỉ khi tập hợp các ô (i, j) mà xij > 0 không lập thành chu trình. Hệ quả 3.2. Giả sử T là một tập hợp gồm m + n – 1 ô của bảng vận tải, không tạo thành chu trình. Khi đó, mỗi ô (p, q) T sẽ tạo với các ô T một chu trình duy nhất. 3.2. Tìm phương án cực biên ban đầu Để giải bài toán vận tải (3.1) – (3.4) với điều kiện (3. 5) theo phương pháp thế vị, trước hết cần biết một phương án cực biên của bài toán. Có nhiều cách để tìm một phương án như thế. Sau đây là ba phương pháp thông dụng và có hiệu quả nhất. a) Phương pháp min cước Trong bảng vận tải 3.1, ta chọn ô (p, q) sao cho cpq = min{cij,  (i, j)}. Nếu cực tiểu đạt tại nhiều ô thì chọn một ô bất kỳ trong số các ô đó. Sau đó phân phối hàng tối đa có thể theo tuyến p q, nghĩa là đạt: xpq = Min{ap; bq} Trừ lượng hàng vừa phân phối vào khả năng thu, phát của hàng p và cột q. Tiếp đó, ta “xoá” hàng p nếu điểm phát p đã phát hết hàng, hoặc cột q nếu điểm thu q đã nhận đủ hàng. Khi cả hàng, cột đều phát hết, thu đủ thì “xoá” cả hàng và cột đó. Trong phần bảng còn lại ta chọn ô có cước phí nhỏ nhất và phân phối tối đa lượng hàng còn lại vào ô này. Như vậy mỗi lần phân phối cho một ô, quy mô của bài toán giảm dần. Tiếp tục quá trình cho tới khi yêu cầu của mọi trạm thu và phát đều thỏa mãn. Nếu kết quả quá trình phân phối cho tổng số ô được phân phối là m + n – 1 thì phương án cực biên không suy biến, tập ô được phân phối hàng gọi là tập ô cơ sở, nếu ít hơn m + n – 1 thì đó là phương án suy biến, trong trường hợp này cần bổ sung ô chọn 0, có vai trò như ô cơ sở để đảm bảo có đúng m + n – 1 ô. Việc bổ sung ô chọn 0 không được tạo với các ô cơ sở đã có bất kỳ một chu trình nào. • • • • • • • • • • • • • • • • • • • • • • • • • • • • a) b) c) d) e) PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 96 Thí dụ 3.1: Tìm phương án cực biên của bài toán vận tải cho ở bảng 3.2 theo tiêu chuẩn min cước. Bảng 3.2 Giải:Trước hết cần kiểm tra điều kiện (3.5). Ta thấy bài toán đã ở dạng cân bằng thu – phát. Cước phí nhỏ nhất trong bảng là 15 đạt tại hai ô (2.1) và (2.4). Ta chọn từ trên xuống từ trái quá phải, vậy ô (2.1) được chọn và phân lượng hàng là x21 = min{200,130} = 130. Cột 1 đã nhận đủ hàng nên bị loại. Hàng 2 lượng phát còn lại là 200 – 130 = 70. Trong bảng còn lại (3 cột cuối), ta chọn ô (2,4) có cước phí nhỏ nhất (bằng 15) và phân vào ô này lượng hàng x24 = Min{70, 140} = 70. Lúc này hàng 2 đã phát hết hàng nên bị loại. Cột 4 còn thiếu lượng hàng là 140 – 70 = 70. Trong bảng còn lại , ta chọn ô (1,2) có cước phí nhỏ nhất và phân vào ô này lượng hàng x12 = Min{170,160} = 160. Lúc này cột 2 đã nhận đủ hàng nên bị loại. Hàng 1 chỉ còn lại lượng phát là 170 – 160 = 10. Tiếp đó ta phân vào ô (1,3) lượng hàng x13 = Min{10,120} = 10. Hàng 1 đã phân hết hàng, chỉ còn hàng 3 là còn hàng. Cuối cùng, ta phân vào 2 ô cuối cùng của hàng này lượng hàng x33 = 120 – 10 = 110 và x34 = 180 – 110 = 140 – 70 = 70. Đến đây mọi hàng (cột) đã phát hết (nhận đủ) hàng, ta đặt xij = 0 đối với mọi ô (i,j) còn lại. Kết quả ta được phương án cực biên không suy biến cho ở bảng (3.2). Giá trị hàm mục tiêu tương ứng bằng 12950. b) Phương pháp góc Tây – Bắc. Luôn ưu tiên phân phối cho ô nằm ở góc tây – bắc của bảng. Phương pháp này không quan tâm tới chi phí mà thực hiện máy móc theo sự bố trí các trạm trên bảng vận tải. Về mặt ý nghĩa kinh tế thì phương án thu được rất bất hợp lý, tuy nhiên nhờ tính chất máy móc nó lại rất thuận tiện khi lập trình để giải bài toán trên máy tính. Trước hết chọn ô (1,1) là ô góc tây – bắc đầu tiên của bảng để phân tối đa lượng hàng, x11 = Min{a1,b1}, loại hàng 1 hoặc cột 1 nếu đã thoả mẫn phát hết hoặc thu đủ. Xác định ô góc tây – bắc trong phần bảng còn lại và phân lượng hàng tối đa cho ô đó. Qúa trình tiếp tục cho đến khi ta nhận được phương án cực biên không suy biến hoặc suy biến. Nếu suy biến cần bổ sung ô chọn 0 để đưa về dạng không suy biến như đã nói ở trên. Thí dụ 3.2. Tìm phương án cực biên với số liệu cho ở thí dụ 3.1. Thu Phát 130 160 120 140 170 20 18 160 22 10 25 200 15 130 25 30 15 70 180 45 30 40 110 35 70 PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 97 c) Phương pháp Fôghen. Phương pháp này cho phương án cực biên khá tốt, theo nghĩa là nó khá gần với phương án tối ưu về giá trị mục tiêu và chỉ cần một số ít bước lặp của thuật toán thế vị là có thể tìm được phương án tối ưu. Nó chỉ khác phương pháp min cước ở cách chọn các ô để phân phối hàng. Giả sử, ma trận cước phí là C = (cij)mxn, phương pháp được tiến hành như sau: Đối với mỗi hàng, mỗi cột của C ta tính hiệu số giữa hai giá trị cước phí nhỏ nhất trên hàng (cột) đó. Hiệu số này biểu thị lượng phạt tối thiểu phải chịu nếu ta phân sai lượng hàng vào ô có cước phí nhỏ nhất trên hàng (cột) đó. Chọn hàng hay cột có hiệu số này lớn nhất. Nếu có nhiều hàng (cột) như thế thì chọn hàng (cột) tuỳ ý trong số đó. Phân lượng hàng tối đa có thể vào ô cước phí nhỏ nhất trên hàng cột đã chọn. Giả sử ô đó là ô (r,s). Giảm lượng cung ở hàng r và lượng cầu ở cột s một số bằng lượng hàng đã phân phối. Sự phân phối này sẽ làm thoả mãn một ràng buộc cung hay một ràng buộc cầu hoặc có thể cả hai. Loại bỏ (không cần xét ở bước tiếp theo) ràng buộc đã thỏa mãn bằng cách đánh dấu chéo vào hàng hay cột tương ứng của ma trận cước phí. Nếu cả hai ràng buộc cung và cầu cùng đồng thời thỏa mãn thì chỉ loại bỏ một hàng (cột) mà thôi. Trong trường hợp này cả lượng cung và cầu còn lại của hàng (cột) đó đều trở thành bằng 0. Lặp lại các thao tác trên cho tới khi chỉ còn lại một hàng hay cột duy nhât. Khi thực hiện thao tác 1, không cần tính hiệu số đối với hàng (cột) có lượng cung (lượng cầu) còn lại bằng 0. Khi chỉ còn đúng một hàng (cột), lượng hàng phân vào các ô thuộc hàng (cột) này hoàn toàn được xác định bởi các lượng hàng đã phân phối trước đó. Thí dụ 3.3. Xét lại thí dụ 3.1. Tính hiệu số của các hàng và cột của ma trận cước phí và khoanh tròn hiệu số lớn nhất. Thu Phát 130 160 120 140 170 20 130 18 40 22 25 200 15 25 120 30 80 15 180 45 30 40 40 35 140 Bảng 3.3 PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 98 Bảng 3.4: Phương án cực biên xây dựng theo phương pháp Fôghen Kết quả ta nhận được phương án cực biên ở bảng 3.4. giá trị hàm mục tiêu tương ứng bằng 12290. Rõ ràng phương pháp này tìm phương án cực biên tốt hơn hai phương pháp trên. 3.3 Phương pháp thế vị giải bài toán vận tải Chúng ta đề cập tới một phương pháp khá đơn giản nhưng rất hiệu quả giải bài toán vận tải trên cơ sở phân tích quan hệ của cặp bài toán đối ngẫu. Về bản chất thì đây là một hình thức thể hiện độc đáo của phương pháp đơn hình áp dụng cho bài toán vận tải có cấu trúc hết sức đặc biệt. a) Bài toán đối ngẫu và tiêu chuẩn tối ưu: Xét bài toán vận tải: m n ij ij i=1 j=1 c x Min (1) Với các điều kiện ràng buộc: n ij i j=1 x = a , i = 1,m (2) m ij j i=1 x = b , j = 1,n (3) xij > 0 với i = 1,m , j = 1,n (4) Ký hiệu ui, vj là những biến đối ngẫu ứng với hệ ràng buộc (2), (3); u = {ui}, v = {vi}; g(u,v) là hàm mục tiêu của bài toán đối ngẫu, đồng thời để tiện cho việc giải thích ý nghĩa kinh tế , ta đổi dấu hệ ràng buộc (2). Khi đó bài toán đối ngẫu có dạng: g(u, v) = n m j j i i j=1 i=1 b v - a u Max  vj – ui ≤ cij  (i, j) Trong cặp bài toán đối ngẫu này có m x n cặp ràng buộc đối ngẫu: xij ≥ 0 và vj – ui ≤ cij  (i, j) Thu Phát 130 160 120 140 170 20 18 50 22 120 25 200 15 130 25 30 15 70 180 45 30 110 40 35 70 10; 10 5; 5;5 5 7;7;12;12 8;8;18 10 PT IT PT IT Bài giảngToán kinh tế Chương3: Mô hình bài toán vận tải 99 Từ định lý 2 của đối ngẫu suy ra: Định lý 3.1. Điều kiện cần và đủ để phương án x = {xij} của bài toán vận tải tối ưu là tồn tại hệ thống số {ui, vj} thoả mãn: vj – ui ≤ cij  (i, j) (*) vj – ui = cij nếu xij > 0 (**) Định lý trên gọi là tiêu chuẩn tối ưu đối với phương án của bài toán vận tải. Trị số của các ui và vj trong tiêu chuẩn gọi là các thế vị hàng và cột. Ta có thể giải thích ý nghĩa kinh tế của các thế vị như sau: có thể xem các thế vị hàng ui là giá trị một đơn vị hàng hóa từ nơi sản xuất Ai, còn vj là giá trị của nó tại điểm tiêu thụ Bj. Điều kiện (**) có nghĩa là trong một phương án vận chuyển tối ưu nếu hàng hóa được đưa từ trạm phát Ai đến trạm thu Bj thì giá trị của nó tại điểm tiêu thụ Bj phải bằng giá trị tại nơi sản xuất Ai cộng thêm chi phí vận chuyển cij. Điều kiện (*) có nghĩa là chênh lệch của giá trị hàng hóa giữa nơi tiêu thụ và nơi sản xuất bất kỳ không vượt quá chi phí vận chuyển trực tiếp giữa hai nơi ấy, điều này là hiển nhiên trong thực tiễn kinh tế. b) Thuật toán thế vị. Dựa trên tiêu chuẩn tối ưu, ta xây dựng thuật toán giải bài toán vận tải, thực hiện một cách đơn giản ngay trên bảng vận tải. Giống như phương pháp đơn hình, ở đây cũng xuất phát từ một phương án cực biên, kiểm tra nó nếu chưa thỏa mãn tiêu chuẩn tối ưu thì tìm cách chuyển sang một phương án cực biên khác tốt hơn. Quá trình lặp lại, và vì bài toán luôn giải được nên sau một số hữu hạn bước sẽ