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

Giáo trình toán kinh tế Tổ môn kế toán 51 Chương 3: Quy hoạch tuyến tính Bài 1: mở đầu 1. Bài toán tối ưu. Tối ưu hóa là một lĩnh vực toán học nghiên cứu lý thuyết và các thuật toán giải bài toán cực trị . Nhiều vấn đè thực tế khác nhau dẫn đến việc giải bài toán cực trị sau : f(x) min (1) Với các điều kiện i 1 j 2 n g (x) 0, i 1,2,...,m (2) h (x) 0, j 1,2,...,m (3) x X R (4)          Trong đó f , gi , hj : ( n 1 2R R i 1,2,...,m ; j 1,2,...m )   Bài toán (1) ... (4) được gọi là bài toán quy hoạch toán học . Hàm f(x) được gọi là hàm mục tiêu , còn các hàm gi , hj gọi là các hàm ràng buộc . Tập hợp các véc tơ nx X R  thoả mãn các ràng buộc (2), (3) gọi là tập phương án hay miền chấp nhận được của bài toán trên . Phương án x* thoả mãn f(x*)  f(x) với phương án x gọi là phương án tối ưu hay lời giải của bài toán f(x*) gọi là phương án tối ưu . Nếu hàm mục tiêu f(x) và các hàm ràng buộc gi , hj đều là các hàm tuyến tính và nX R  , ta có bài toán quy hoạch tuyến tính , ngược lại ta có bài toán quy hoạch phi tuyến tính . Chuyên đề của chúng ta chỉ xét bài toán quy hoạch tuyến tính 2. Bài toán vận tải Giả sử có m kho kí hiệu là A1, A2, ...., Am (các điểm phát) cung cấp cùng một loại mặt hàng nào đó với khối lượng tương ứng a1, a2, ... , am và n cửa hàng tiêu thụ (các điểm thu) ký hiệu là B1, B2, ... , Bn với khối lượng nhu cầu tương ứng b1, b2, ... , bn. Để thoả mãn nhu cầu của các điểm thu thì tổng số lượng hàng ở các điểm phát ít nhất phải bằng tổng yêu cầu ở các điểm thu: m n i j i 1 j 1 a b     Biết rằng cước phí vận chuyển một đơn vị hàng (chiếc, tấn ...) từ điểm phát Ai đến điểm thu Bj là cị đơn vị tiền. Ma trận C = (cij)mxn gọi là ma trận cước phí. Giáo trình toán kinh tế Tổ môn kế toán 52 Hãy lập phương án vận chuyển sao cho các điểm thu đều nhận đủ hàng và cước phí vận chuyển là ít nhất. Lập bài toán: Gọi xị là số đơn vị hàng chuyển từ Ai đến Bj. Tất nhiên xij ≥ 0 (i = 1,m, j 1,n ). Tổng lượng hàng chuyển từ Ai đến mọi Bj là n ij j 1 x   (i = m,1 ) Tổng lượng hàng điểm Bj nhận được từ mọi Ai là m ij i 1 x   (j = n,1 ) Tổng cước phí phải trả là m n ij ij i 1 j 1 c x    . Bài toán đặt ra là: Tìm véc tơ x = (xij) (i = 1,m, j 1,n ) sao cho: f(x) = m n ij ij i 1 j 1 c x    min và thoả mãn các điều kiện n ij i j 1 m ij i i 1 ij x a (i 1,m) x b (j 1,n) x 0 (i 1,m; j 1,n)                   3. Bài toán quy hoạch tuyến tính a, Dạng tổng quát : Tìm vec tơ x = (x1, x2, ... , xn ) T nR sao cho : n j j j 1 f(x) c x min (max)    Với các điều kiện : Giáo trình toán kinh tế Tổ môn kế toán 53                                  n ij j i j 1 n ij j i j 1 n ij j i j 1 1j j 1 2 j 2 a x b a x b (j 1,m) a x b với các ràng buộc về dấu: x 0 (j 1,n ) x 0 (j n 1,n ) x dấu tự do (j n 1,n) Dễ thấy rằng : 1) f(x*) = min { f(x) , x  D }  - f(x*) = max {- f(x) , x  D } 2)        n n ij j j ij j j j 1 j 1 a x b ( a )x b 3)                n ij j j n j 1 ij j j n j 1 ij j j j 1 a x b a x b a x b 4) n n ij j j ij j n i j n i j 1 j 1 a x b a x x b ; x 0           5) n n ij j j ij j n i j n i j 1 j 1 a x b a x x b ; x 0           Các biến n 1x 0  gọi là các biến bù . Từ các nhận xét trên ta thấy bất kỳ bài toán quy hoạch tuyến tính nào cũng có thể đưa về một trong hai dạng sau đây: b. Bài toán quy hoạch tuyến tính dạng chính tắc Giáo trình toán kinh tế Tổ môn kế toán 54                  n j j j 1 n ij j i j 1 j f(x) c x min a x b (i 1,m) x 0 (j 1,n) hay dưới dạng ma trận: tf(x) c x min Ax b x 0        Trong đó: c, x Rn, b Rm, A là ma trận cấp m x n. c. Bài toán quy hoạch tuyến tính dạng chuẩn tắc.                  n j j j 1 n ij j i j 1 j f(x) c x min a x b (j 1,m) x 0 (j 1,n) hay dưới dạng ma trận: tf(x) c x min Ax b x 0        Ví dụ: Có bài toán quy hoạch tuyến tính: f(x) = 2x1 – 3x2 + 4x3 – 5x4  max            0,,, 275 4392 6 4321 321 432 421 xxxx xxx xxx xxx Hãy viết bài toán trên dưới dạng chính tắc và chuẩn tắc. - Dạng chính tắc: f(x) = - 2x1 + 3x2 - 4x3 + 5x4  min Giáo trình toán kinh tế Tổ môn kế toán 55            0,,,,, 275 4392 6 654321 6321 5432 421 xxxxxx xxxx xxxx xxx - Dạng chuẩn tắc: f(x) = - 2x1 + 3x2 - 4x3 + 5x4 -> min              0,,, 275 4392 6 6 4321 321 432 421 421 xxxx xxx xxx xxx xxx 4. Điều kiện cần và đủ để một phương án là cực biên Xét bài toán quy hoạch tuyến tính dạng chính tắc (I) f(x) = ctx -> min Ax b x 0    Ký hiệu a1, a2, ... an là các cột của: A = 11 12 1n 21 22 2n m1 m2 mn a a ... a a a ... a ... ... ... ... a a ... a             Không mất tính tổng quát, luôn có thể giả thiết : R(A)=R (a1, a2, ..., an) = m Vì nếu có phương trình nào trong hệ Ax = b biểu diễn được dưới dạng tổ hợp tuyến tính của các phương trình khác thì có thể bỏ nó đi. Định lý: Điều kiện cần và đủ để x  D là một phương án cực biên là hệ các véc tơ cột ứng với các thành phần dương của x độc lập tuyến tính. Tức là: Ký hiệu J+(x) = {j : xj > 0} thì x  D là cực biên  {aj, j  J+ (x)} độc lập tuyến tính. Chứng minh: Điều kiện cần x  D là điểm cực biên. Cần chứng minh hệ véc tơ {aj, j  J+ (x)} độc lập tuyến tính. Giáo trình toán kinh tế Tổ môn kế toán 56 Để đơn giản, giả sử J+(x) = {1, 2, ..., k} Ta chứng minh bằng phản chứng. Giả sử hệ {a1, a2, ..., ak} phụ thuộc tuyến tính, suy ra tồn tại các số z1, z2, ..., zk không đồng thời bằng 0 để k ạ j aj 1 z a 0   . Đặt z = (z1, z2, ..., zk, 0, ..0) t thì Az = 0. Lập các véc tơ: x’ = x + z; x’’ = x - z => Ax’ = Ax’’ = Ax = b (vì Az = 0) Lấy  > 0 đủ bé sao cho x’ ≥ 0 thì x’, x’’ D mà từ x’ = x + z; x’’ = x - z => x = '' 2 1 ' 2 1 xx  suy ra trái với giả thiết x là phương án cực biên. Điều kiện đủ: Giả sử hệ véc tơ {aj, j  J+ (x)} độc lập tuyến tính. Cần chứng minh rằng x là một phương án cực biên. Ta chứng minh bằng phản chứng. Giả sử x không phải là phương án cực biên, suy ra x’, x’’D, x’  x’’ sao cho x = 2 ''' xx  . Ta có (n-k) thành phần của chúng đều không âm, không xảy ra tình huống n - k thành phần cuối của x’, x’’ đối nhau. Vậy k k k j ' j '' j j j j aj 1 aj 1 aj 1 x a x a x a        Vì Ax’ = Ax’’ = Ax = b Nhưng hệ {aj, j  J+ (x)} độc lập tuyến tính nên suy ra: xj = x’j = x’’j (j = 1, 2, ... k) xj = x’j= x’’j = 0 (j = k+1 , ... , n) hay x = x’ = x’’. Điều này mâu thuẫn với giải thiết x’  x’’. --------------------o0o------------------------ Giáo trình toán kinh tế Tổ môn kế toán 57 Bài 2: Phương pháp đơn hình I. Tư tưởng của phương án đơn hình 1.Biểu diễn qua cơ sở. Dấu hiệu tối ưu. Giả sử có phương án cực biên 0x với cơ sở J (tức là hệ véctơ cột độc lập tuyến tính      j ja , j J ; J J x j,x 0    . Ta có:   n 0 0 j 0 j j j j 1 j J Ax b hay b x a x a 1       ( vì 0jx 0; j J)   . Với mỗi k J , ta biểu diễn véctơ ka qua các véctơ cơ sở  ja , j J .  k jjk j J a z a k J     Giả xử x  D là một phương án bất kỳ. Ta có. b = k j j k j k j j j k j jk j 1 j J k J j J k J j J x a x a x a x a x z a (2)                Vì {aj, jJ} là độc lập tuyến tính nên từ (1) và (2) ta có: x0j = xj + jk k k J z x   (j J) hay xj = x 0 j - jk k k J z x   (j J) (3) Ta gọi (3) là khai triển của một phương án bất kỳ qua cơ sở J. Lại có :   n t j j j j k k j 1 j J k J f x c x c x c x c x          Thay (3) vào ta được: Giáo trình toán kinh tế Tổ môn kế toán 58   0j jk k j k k j J k J k J 0 j j jk j k k j J k J j J f x x z x c c x c x z c c x                             Ký hiệu: k = jk j k j J z c c   (k J) Gọi là ước lượng của véc tơ cột ak theo cơ sở J và: f(x) = f(x0) - k k j J x   Nhận xét: do x ≥ 0 nên nếu k J, k< 0 thì f(x) ≥ f(x 0), x  D do đó ta có dấu hiệu tối ưu sau đây: Phương án cực biên x0 với cơ sở J là phương án tối ưu thì k  0, kJ. 2. Tìm phương án cực biên mới tốt hơn - Công thức đổi cơ sở. Giả xử x0 với cơ sở J là một phương án cực biên nhưng chưa phải là phương án tối ưu, khi đó k J sao cho k> 0. Giả sử s là một chỉ số trong các chỉ số nói trên: s J, s > 0. Theo thuật toán đơn hình ta cần cải tiến x0 để nhận được một phương án cực biên mới x1 tốt hơn. Nhằm mục đích kế thừa tận dụng những kết quả ở bước trước ta sẽ tìm phương án cực biên mới x1 với cơ sở J1 chỉ khác J một véc tơ: J1 = (J \ r) U s, nghĩa là ta sẽ đưa véc tơ as vào cơ sở thay thế cho véc tơ ar khác bị loại khỏi cơ sở J. Các véc tơ ar và as được lựa chọn sao cho x1 tốt hơn x0. Tóm lại: x1j = 0 j js 0 Nếu j J, j s Nếu j s x z Nếu j J           (*) Nếu k  J, k > 0 mà zjs  0 j  J thì f(x) -> -  Nếu j  J để zjs > 0, khi đó số  không thể lớn tuỳ ý, nó phải thoả mãn x0j - zjs  0 j  J mà zjs > 0. Giả sử cực tiểu trên đạt tại j = r. Lấy  = rs r z x0 , thay vào (*) ta được: Giáo trình toán kinh tế Tổ môn kế toán 59 x1j = 0 r rs 0 0 r j rs 0 Nếu j J, j s x Nếu j s z x x Nếu j J z             (**) f(x1) = f(x0) - s. 0 r rs x z (***) Phương án x1 nhận được ở (**) thực sự tốt hơn x0 nếu 0 r rs x z > 0. Điều này thấy rõ từ (***). Định lý: Phương án x1 được xác định theo công thức (**) là phương án cực biên với cơ sở J1 = (J \ r) U s. Chứng minh: Theo (**) suy ra x1r = 0 nên J +(x1)  J1. Ta cần chứng minh hệ véc tơ {aj, j  J1} độc lập tuyến tính. Thật vậy, giả sử 1 j j j J a x   = 0 ta cần chứng minh j = 0  j  J 1. Ta có: 0 = 1 j j j J a x   = j s j jj s j s js j J,j r j J,j r j J a a a z a             = j r j s js s rs j J,j r ( z )a z a      Vì hệ véc tơ {aj, j  J} là độc lập tuyến tính, nên suy ra: j s js s rs z 0 j J,j r z 0         Vì zr s > 0 nên suy ra s = 0, do đó j = 0 (j  J, j r). Vậy j = 0 j J1 = {J\r}  {s}. Vì J+(x1)  J1 nên hệ véc tơ {aj, j  J+(x1)} độc lập tuyến tính, do đó x1 là phương án cực biên và J1là cơ sở của phương án cực biên x1. Định lý được chứng minh. Giáo trình toán kinh tế Tổ môn kế toán 60 Các công thức (**) và (***) cho ta cách tìm các thành phần của phương án cực biên mới 1x cùng với giá trị hàm mục tiêu f( 1x ) thông qua các hệ số khai triển jkz và các ước lượng k trong cơ sở J. Để có thể tiến hành các bước tiếp theo ta cần xác định các đại lương tương ứng 1jkz và 1 k trong cơ sở mới 1J . Theo định nghĩa jkz và 1 jkz là các hệ số khai triển của véctơ ka tương ứng với cơ sở J, 1J .      1 1 k j 1 j 1 jk jk j J j J j j r jk jk jk j J j J ,j r a z a z a J J \ r s (1) z a z a z a (2)                Từ 1 s j j r js js rs rs j J j J ,j r a z a z a z a vi` z 0         Ta có r s j js j J,j rrs 1 a a z a z           thay vào (2) ta được : j j s jrk jk jk js j J j J,j r j J,j rrs j srk rk jk js j J,j r rs rs z z a z a a z a z z z z z a a z z                            Vì {aj, j  J1} độc lập tuyến tính nên từ (1) và (2) suy ra: rk rs1 jk rk jk js rs z nếu j=s z z z z z nếu j J, j r z           1 1 1 1 rk rk k jk j k jk js j s k j J j J,j r rs rs rk rk jk js j s k j J rs rs z z z c c z z c c c z z z z z z c c c z z                             ( Vì với j=r thì rkjk js rs z z z 0 z        ) Giáo trình toán kinh tế Tổ môn kế toán 61   1 1 rk rk jk j k js j s k s j J j Jrs rs z z z c c z c c z z                Vậy 1 rkk k s rs z z      II. Thủ tục đơn hình - Bảng đơn hình. 1. Các bước của thủ tục đơn hình. + Bước xuất phát: Tìm một phương án cực biên x0 và cơ sở J tương ứng. Tính các hệ số khai triển zjk và các ước lượng k. + Bước 1: Kiểm tra dấu hiệu tối ưu: a. Nếu k  0  k  J thì x 0 là phương án tối ưu. Thuật toán kết thúc. b. Nếu k > 0 thì chuyển sang bước hai. Phương án cực biên mới tốt hơn với cơ sở J1 = (J\r) U s theo quy tắc sau: + Bước 3: + Bước 2: Kiểm tra dấu hiệu hàm mục tiêu giảm vô hạn: Với mỗi k  J mà k > 0 thì kiểm tra các hệ số khai triển zjk của cột a k tương ứng. a. Nêu có một k> 0 mà tất cả zjk  0  j  J thì kết luận hàm mục tiêu giảm vô hạn trên miền ràng buộc. Bài toán không có lời giải hữu hạn. Thuật toán kết thúc. b. Trái lại nếu với mọi k  J mà k> 0 đều tồn tại ít ất một hệ số zjk>0 thì tiến hà tìm phương Chọn as đưa vào cơ sở: có thể chọn bất kỳ s  J mà ước lượng s > 0. Thông thường chọn s  J theo quy tắc: s = max {k > 0, k  J} (vì khi đó hàm số giảm nhanh nhất) Chọn véc tơ ar đưa ra khỏi cơ sở theo quy tắc:  =          0,min 00 js js j rs r z z x x x + Bước 4: Tính các x1j, f(x 1), 1k, z 1 jk trong cơ sở mới J 1 = (J \ r) U s các công thức trên. Quay trở lại bước 1. 2. Bảng đơn hình Để thuận tiện cho việc tính toán theo thủ tục đơn hình người ta sắp xếp các số liệu thành 1 bảng đơn hình như dưới đây: Giáo trình toán kinh tế Tổ môn kế toán 62 Cơ sở J cj Phương án xj 1 c1 2 c2 k ck n cn J1 cj 1 xj 1 zj 11 zj 12 zj 1k zj 1n J2 cj 2 xj 2 zj 21 zj 22 zj 2k zj 2n Jm cj m xj m zj m1 zj m2 zj mk zj mn f(x) 1 2 k n 3. Thủ tục đơn hình trên bảng. + Bước 1: Kiểm tra điều kiện tối ưu: k < 0  k - Nếu k  0  k => phương án x 0 đang xét là phương án tối ưu. - Nếu k > 0 thì chuyển sang bước 2. + Bước 2: (Kiểm tra dấu hiệu hàm mục tiêu giảm vô hạn: có k > 0 và cột tương ứng gồm toàn các phần tử không dương zjk  0  j  J) - Nếu có k > 0 và zjk  0  j  J thì bài toán không có phương án tối ưu (hữu hạn) vì hàm mục tiêu giảm vô hạn trên miền ràng buộc. - Nếu k > 0,  j  J để zjk > 0 thì chuyển sang bước 3. + Bước 3: (Xác định cột xoay, dòng xoay, phần tử trục) - Chọn chỉ số s: s = max {k, k> 0}, đánh dấu cột s là cột xoay. - Tìm chỉ số r đạt min.  =          0,min 00 js js j rs r z z x z x Ví dụ 1: f(x) = x1 - x2 - 2x4 + 2x5 - 3x6  min            )6,1(0 9342 12 2 6543 642 6541 jx xxxx xxx xxxx j Chọn cơ sở xuất phát J = {1,2,3}. Aj là ma trận đơn vị, do đó ta có ngay bảng đơn hình xuất phát sau: Giáo trình toán kinh tế Tổ môn kế toán 63 J cj xj 1 1 2 -1 3 0 4 -2 5 2 6 -3 1 1 2 1 0 0 01 1 -1 2 -1 12 0 1 0 1 0 1 3 0 9 0 0 1 2 4 3 -10 0 0 0 2 -1 1 Các bước của thủ tục đơn hình: + Có 4 > 0, 6 > 0. Dấu hiệu tối ưu chưa thỏa mãn, chuyển sang bước 2. Trên các cột 4 và cột 6 (có k > 0) không phải tất cả zjk ≤ 0 (j J) trường hợp 2a) không xảy ra. + Tiến hành đổi cơ sở: Chọn chỉ số s: 4 = max {4 = 2; 6 = 1}. Chọn cột 4 làm cột xoay (đưa a 4 vào cơ sở). Chọn chỉ số r:  = min 1 14 x2 12 9 2 , , 1 1 1 1 z        => r = 1 chọn hàng 1 làm hàng xoay (đưa a1 ra khỏi cơ sở). Phần tử trục là z14 = 1 (được đánh dấu "o" bên cạnh). Tiến hành tính toán theo các công thức đổi cơ sở ta được bảng đơn hình sau: J cj xj 1 1 2 -1 3 0 4 -2 5 2 6 -3 4 -2 2 1 0 0 1 1 -1 2 -1 10 -1 1 0 0 -1 2 3 0 5 -2 0 1 0 2 5 -14 -2 0 0 0 -3 3 Cột xoay: 6, dòng xoay: 3, phần tử trục z36 = 5 4 -2 3 3/5 0 1/5 1 7/5 0 2 -1 8 -1/5 1 -2/5 0 -9/5 0 6 -3 1 -2/5 0 1-5 0 2/5 1 -17 -4/5 0 -3/5 0 -21/5 0 Tất cả k <0 ( k = 1,2 6) . Phương án tối ưu là : x* =(0,8,0,3,0,1) và giá trị tối ưu f(x* ) = - 17 Ví dụ 2: f(x) = 6x1 + x2 + x3 + 3x4 +x5 -7x6 + 7  min Giáo trình toán kinh tế Tổ môn kế toán 64 1 2 4 6 1 3 6 1 4 5 6 j x x x x 15 2x x 2x 9 4x 2x x 3x 2 x 0(j 1,...6)                   (1) Đổi dấu để có vec tơ đơn vị : Xét bài toán : g(x) = 6x1 + x2 + x3 + 3x4 +x5 -7x6 min. 1 2 4 6 1 3 6 1 4 5 6 j x x x x 15 2x + x 2x 9 4x 2x x 3x 2 x 0(j 1,...6)                  (2) Nghiệm x* của (2) cũng là nghiệm của (1) và f(x*) = g(x*) + 7 Nếu (2) không có phương án tối ưu thì (1) cũng không có phương án tối ưu . Bài toán (2) có J = {2,3,5} là cơ sở . Ta có bảng đơn hình : J Cj xj 1 2 3 4 5 6 6 1 1 3 1 -7 2 3 5 1 1 1 15 9 2 -1 1 0 -1 0 01 -2 0 1 0 0 -2 4 0 0 2 1 -3 26 -5 0 0 -2 0 3 J Cj xj 1 2 3 4 5 6 6 1 1 3 1 -7 6 3 5 -7 1 1 15 39 47 -1 1 0 -1 0 1 -4 2 1 -2 0 0 1 3 0 -1 1 0 -19 -2 -3 0 1 0 0 Tồn tại 4 > 0 và mọi phần tử trên cột 4 đều nhỏ hơn 0 . Bài toán không có phương án tối ưu hữu hạn . Nên (1) không có phương án tối ưu . III. Tìm cơ sở xuất phát Để có thể bắt đầu thủ tục đơn hình , ta giả thiết có sẵn một phương án xuất phát và có cơ sở tương ứng của nó là J . Hơn nữa , ta luôn giả thiết hạng của ma Giáo trình toán kinh tế Tổ môn kế toán 65 trận A là m , nghĩa là các dòng của ma trận A là độc lập tuyến tính . Trong thực tế không có gì đảm bảo điều này cả , thậm chí miền ràng buộc có thể rỗng , tức là bài toán đã cho không có phương án chấp nhận được . Phần này nhằm giải quyết hai vấn đề còn gác lại ở trên . Cho bài toán quy hoạch tuyến tính bất kì , cần chỉ ra cách tìm một phương án cực biên và cơ sở tương ứng hoặc chứn tỏ bài toán không có phương án . 1. Phương pháp hai pha. Xét bài toán quy hoạch tuyến tính dạng chính tắc : n j j j 1 n ij j i j 1 j f(x) c x min a x b (i 1,2,...,m) D : x 0(j 1,2,..., n)              (I) Không giảm tổng quát coi bi  0 , i = 1,2,,m . Nếu trái lại thì ta có bi < 0 , ta nhân hai vế ràng bộc thứ i với -1. Xét bài toán phụ sau : n 1 n 2 n 3 n m n ij j n i i j 1 j n i f(x) u u u ... u min a x u b (i 1,2,...,m) D' : x 0(j 1,2,..., n) u 0(i 1,2,...,m)                           (P) Các biến n iu  gọi là các biến giả . Bài toán (P) cũng là một bài toán quy hoạch tuyến tính dạng chính tắc với n+m biến . Đối với bài toán (P) ta có ngay phương án cực biên xuất phát (x,u) = (0,b) tức là ta có xj=0 (j= 1,2 ,n.) , un+i = bj (i = 1,2, ,m) và cơ sở tương ứng là m cột cuối và ma trận cơ sở Aj = I ( là ma trận đơn vị ) nghĩa là rất thuận lợi để bắt đàu thủ tục đơn hình . Bài toán phụ (P) giúp ta giải quyêt vấn đề phương án cực biên và cơ sở xuất phát của bài toán ban đầu (I) như sẽ thấy dưới đây: Định lí : Bài toán ban đầu (I) có phương án chấp nhận được khi và chỉ khi bài toán phụ (P) có phương án tối ưu với tất cả các biến giả un+i đều bằng 0 (i= 1,2, ,m). Chứng minh . Giáo trình toán kinh tế Tổ môn kế toán 66 ( Thuận ) Giả sử (I) có phương án x = (x1, x2, x3, , xn) thì rõ ràng (P) có phương án (x,0) = (x1, x2, x3, , xn, 0 ,0 , ,0)và với mọi (x,u)  D’ có f(x,u) 0 f(x,0)  mọi phương án dạng (x,0) (xD) đều là phương án tối ưu của bài toán (P). (Nghịch ) Ngược lại nếu (P) có phương án tối ưu (x*,u*) với u*= 0 thì x* là phương án của (I) . Ta còn cần chứng minh nếu (P) có phương án tối ưu (x*,u*) với u* 0 thì (I) không có phương án .Thật vậy , giả sử ngược lại , bài toán (I) có phương án x =(x1, x2, x3, , xn) . Khi đó (x,0) là phương án của bài toán (P) , nhưng vì u*  0 nên f(x*,u*) = et . u > 0 = f(x,0) với (e = (1,1,1, .,1)). Mâu thẫn với giả thiết (x*,u*) là phương án tối ưu của bài toán (P). Quá trình giải bài toán (P) gọi là pha thứ nhất trong trong phương pháp hai pha . Giả sử sau pha thứ nhất này ta nhận được phương án tối ưu (x*,u*) của bài toán phụ (P) . Có 3 khả năng : a, Nếu u*  0 thì kết luận bài toán đầu (I) không có phương án . b, Nếu u* = 0 và cơ sở tương ứng gồm các cột tương ứng với xj , không chứa các cột nào của biến giả un+i . Dây chính là phương án cực biên và cơ sở xuất phát để bắt đầu pha thứ hai , tức là bắt đầu thủ tục đơn hình với bài toán ban đầu (I). c, Nếu u* = 0 nhưng cơ sơ tương ứng có chứa một số cột ứng với các biến giả un+i . ta cần xét kĩ trường hợp này . Kí hiệu Jx là tập các chỉ số trong cơ sở ứng với các biến xj , Ju là tập các chỉ số ứng với biến giả un+i , khi đó J = Jx  Ju . Trường hợp 1 : Nếu trên dòng có chỉ số (n+i) của bảng dơn hình cuối cùng của bài toán (P) ta tìm được một chỉ số k ngoài cơ sở (1k n ) sao cho zn+i, k  0 thì ta thực hiện phép dổi cơ sở với phần tử trục là zn+i, k để đưa (n+i) ra ngoài và đưa k vào cơ sở , ta sẽ nhận được một cơ sở mới trong đó đã được bớt đi một cột ứng với các biến giả u và sẽ nhận được một cơ sở xuất phát cho bài toán ban đầu (I) gồm toàn các cột của ma trận A . Trường hợp 2 : Trên dòng chỉ số (n+i) của bảng đơn hình cuối cùng của bài toán (P) không tìm được chỉ số k ngoài cơ sở (1 k n ) mà zn+i, k  0 thì ta kết luận rằng dòng i của ma trận A là tổ hợp tuyến tính của các dòng còn lại . Thật vậy , vì ma trận xuất phát để giải bài toán (P) là ma trận E , nên phần hệ số zjk trong bảng đơn hình là (A,E). Các tính toán trên bảng đơn hình gồm việc nhân một dòng với một số hoặc nhân một dòng với một số rồi cộng vào dòng trước . Trường hợp 2 nghĩa là trên dòng chỉ số (n+i) của bảng đơn hình phần tử tương ứng với x hoàn toàn bằng 0 sau các phép biến đổi trên . Điều này nói lên rằng dòng i của ma trận A là tổ hợp tuyến tính của các dòng còn lại . Ta có thể xoá đi dòng này và có thể loại bỏ luôn biến giả tương ứng . Giáo trình toán kinh tế Tổ môn kế toán 67 Tóm lại , cả hai trường hợp ta đều loại được các cột ứng với biến giả u ra khỏi cơ sở để nhận được một cơ sở chỉ gồm các cột ứng với biến x . Đây là cơ sở xuất phát để giải quyết bài toán ban đầu (I). Chú ý : Nếu trong số các cột của ma trận A có một cột là một véc tơ của ma tận đơn vị với phần tử bằng 1 tại dòng i thì ta không cần thêm biến giả un+i tương ứng với dòng thứ i , số biến giả chỉ là m - 1 và cơ sở để xuất phát bài toán (P) sẽ gồm cột này và m - 1 cột úng với các biến giả . Có bao nhiêu cột của A là véc tơ của ma trận đơn vị thì ta bớt được bấy nhiêu biến giả . Ví dụ 1: Giải bài toán quy hoạch tuyến tính : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 j f(x) 3x x 3x x min x 2x x x 2 2x 6x 3x 3x 9 x x x x 6 x 0(j 1,2,3,4)                        (I) Ta thêm các biến giả u5 , u6 , u7 , Pha 1 : Giải bài toán quy hoạch tuyến tính phụ J CJ (x,u)j 1 2 3 4 5 6 7 0 0 0 0 1 1 1 5 1 2 01 2 -1 1 1 0 0 6 1 9 2 -6 3 3 0 1 0 7 1 6 1 -1 1 -1 0 0 1 17 4 -5 3 3 0 0 0 (P) (x,u)j 1 2 3 4 5 6 7 0 0 0 0 1 1 1 1 2 -1 1 1 0 0 0 -10 05 1 -2 1 0 0 -3 2 -2 -1 0 1 0 -13 7 -1 -4 0 0 Giáo trình toán kinh tế Tổ môn kế toán 68 J CJ (x,u)j 1 2 3 4 5 6 7 0 0 0 0 1 1 1 1 0 3 1 0 0 6/5 3/5 1/5 0 3 0 1 0 -2 1 1/5 -2/5 1/5 0 7 1 2 0 1 0 -12/5 -1/5 -2/5 1 2 0 1 0 -12/5 -6/5 -7/5 0 J CJ (x,u)j 1 2 3 4 5 6 7 0 0 0 0 1 1 1 1 0 3 1 0 0 6/5 3/5 1/5 0 3 0 5 0 0 1 -23/5 -4/5 -3/5 2 3 0 2 0 1 0 -12/5 -1/5 -2/5 1 0 0 0 0 0 -1 -1 -1 Kết thúc pha thư nhất ta nhận được phương án tối ưu của bài toán (P) là: (x*,u*) = (3,2,5,0,0,0,0) với cơ sở tương ứng là : J = {1,3,2 }= {a1, a3, a5}. Ta có trường hợp b) vì trong phương án tối ưu của bài toán (P) có u* = 0 và cơ sở tương ứng chỉ gồm các cột tương ứng với x . Lấy x* = (3,2,5,0) với cơ sở {1,3,2} xuất phát để giải bài toán ban đầu . Suy ra pha thứ hai có bảng đơn hình là : J CJ xj 1 2 3 4 -3 1 3 -1 1 -3 3 1 0 0 6/5 3 3 5 0 0 1 -23/5 2 1 2 0 1 0 -12/5 8 0 0 0 -94/5 Giáo trình toán kinh tế Tổ môn kế toán 69 Bảng trên nhận được từ bảng đơn hình cuối cùng của bài toán (P) bằng cách bỏ các cột tương ứng với các biến giả , thay cột CJ bằng các hệ số tương ứng của bài toán ban đầu và tính lài(x) và k theo bài toan xuất phát . Bảng đơn hình này đã cho ta thấy đã thoả mãn điều kiện tối ưu. Vậy nghiệm cần tìm là : x* = ( 3,2,5,0) và f(x*) = 8 Ví dụ 2: Giải bài toán quy hoạch tuyến tính . 1 2 3 1 2 3 1 2 3 1 2 3 4 j f(x) 2x 4x 2x min x 2x x 27 2x x 2x 50 x x x x 18 x 0(j 1,2,3,4)                    (I) Xét bài toán quy hoạch tuyến tính phụ sau : 5 6 1 2 3 5 1 2 3 6 1 2 3 4 j 6 5 f(x) u u min x 2x x u 27 2x x 2x u 50 x x x x 18 x 0(j 1,2,3,4);u ,u 0.                      Ta có bảng đơn hình sau : J CJ xj 1 2 3 4 5 6 0 0 0 0 1 1 5 1 27 1 -2 1 0 1 0 6 1 50 2 1 02 0 0 1 4 0 18 1 -1 -1 1 0 0 77 3 -1 3 0 0 0 Giáo trình toán kinh tế Tổ môn kế toán 70 J CJ xj 1 2 3 4 5 6 5 1 2 1 0 25 4 0 -5 0 -5/2 0 0 0 -3/2 Điều kiện tối ưu đã thoả mãn . Phương án tối ưu của (P) là (x*, u*) = (25,0,0,-5,2,0) có u*5 = 2 khác 0 Vậy bài toán ban đầu (I) không có phương án cực biên . Ví dụ 3: Giải bài toán quy hoạch toán sau 1 2 3 1 2 3 2 3 2 3 j f(x) 3x x 3x max x 2x x 2 10x 5x 5 3x 2x 4 x 0 (j = 1,3)                   Lời giải Chuyển về bài toán dạng chính tắc : 1 2 3 1 2 3 2 3 2 3 j g(x) 3x x 3x min x 2x x 2 10x 5x 5 3x 2x 4 x 0 (j = 1,3)                    Xét bài toán phụ : 4 5 1 2 3 2 3 4 2 3 5 j 4 5 g(x,u) u u min x 2x x 2 10x 5x u 5 3x 2x u 4 x 0 (j = 1,3)u ,u 0                     Giáo trình toán kinh tế Tổ môn kế toán 71 J CJ (x,u)j 1 2 3 4 5 0 0 0 1 1 1 0 2 1 2 -1 0 0 4 1 5 0 -10 05 1 0 5 1 4 0 -3 2 0 1 9 0 -13 7 0 0 1 0 3 1 0 0 1/5 0 3 0 1 0 -2 1 1/5 0 5 1 2 0 01 0 -2/5 1 2 0 1 0 -7/5 0 1 0 3 1 0 0 1/5 0 2 0 5 0 0 1 -3/5 2 3 0 2 0 1 0 -2/5 1 0 0 0 0 -1 -1 Sau pha thứ nhất nghiệm của (P) là : (x0,u0) = (3,2,5,0,0) với cơ sở J = {1,2,3} gồm toàn các cột tương ứng với x . Dùng x0 = (3,2,5) với cơ sở J= {1,2,3} làm cơ sở xuất phát để giải bài toán (I). J CJ xJ 1 2 3 -3 -1 3 1 -3 3 1 0 0 2 -1 5 0 0 1 3 3 2 0 1 0 4 0 0 0 Điều kiện tối ưu đã thoả mãn. Suy ra nghiệm của (I) là x* = (3,2,5) và g(x*) = 4 . Suy ra f(x*) = -4. --------------------o0o------------------------ Giáo trình toán kinh tế Tổ môn kế toán 72 Bài 3: Bài toán quy hoạch tuyến tính đối ngẫu. 1. Thành lập bài toán đối ngẫu. Cho bài toán quy hoạch tuyến tính: Dạng tổng quát : n j j j 1 f(x) c x min    Với các điều kiện : n ij j i 1 j 1 n ij j i 1 j 1 1j j 1 a x b : i=1,...,m a x b : i m 1,...,m với các ràng buộc về dấu: x 0 (j 1,n ) x dấu tự do (j n 1,n)                       Thì ta có bài toán đối ngẫu được thành lập như sau : Bài toán gốc (P) Bài toán đối ngẫu (Q) tc x min  tb y max n ij j i j 1 a x b   1 i=1,...,m iy 0 ( 1 i=1,...,m ) n ij j i j 1 a x b   1 i m 1,...,m  yi có dấu tự do 1i m 1,...,m  jx 0 1j 1,n m ij i j i 1 a y c   với 1j 1,n jx dấu tự do 1j n 1,n  m ij j i 1 a yj c   với 1j n 1,n  Giáo trình toán kinh tế Tổ môn kế toán 73 Ví dụ 1 : Tìm bài toán đối ngẫu với bài toán gốc sau : 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 3 1 2 3 4 5 f(x) 5x x 2x 3x 6x min 3x x 2x 3x 4x 80 x x x x x 10 3x 2x 2x x x 30 x x 6 x 0;x ,x 0;x ,x dấu tự do                                Lời giải: Theo bảng ta có bài toán đối ngẫu như sau : 1 2 3 4 1 2 3 4 1 1 2 3 2 1 2 3 4 3 1 2 3 4 1 2 3 5 1 2 g(y) 80y 10y 30y 6y max 3y y 3y y 5(do x 0) y y 2y 1( do x 0) 2y y 2y y 2( do x 0) 3y y y 3(do x tự do) 4y y y 6(do x tự do) y tự do (do ràng buộc 1 ở bài toán gốc là :’ ’) y 0 (                              3 4 do ràng buộc 2 ở bài toán gốc là :’ ’) y ,y 0 (do ràng buộc 3,4 ở bài toán gốc là :’ ’)               Ví dụ 2 : Tìm bài toán đối ngẫu của bài toán sau: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 f(x) 2x 3x x x max 2x x x x 5 x x 2x x 7 5x x 3x x 20 x ,x 0,x 0,x tự do.                       Ta có bài toán đối ngẫu : Giáo trình toán kinh tế Tổ môn kế toán 74 1 2 3 1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 4 1 2 g(y) 5y 7y 20y min 2y y y 2( do x 0) y y y 3( do x 0) y 2y 3y 1( do x 0) y y y 1( do x tự do ) y 0(do ràng buộc 1 trong bài toán gốc là" ") y tự do (do ràng buộc 2 trong bài toán gốc                         3 là" ") y 0 (do ràng buộc 3 trong bài toán gốc là" ")              2. Quan hệ giữa cặp bài toán đối ngẫu. Vì bài toán quy hoạch tuyến tính bất kì đều có thể đưa về bài toán quy hoạch tuyến tính dạng chính tắc và có bài toán đối ngẫu tương ứng, nên không mất tính tổng quát ta xét cặp bài toán đối ngẫu với bài toán gốc cho dưới dạng chính tắc và không suy biến. Định lý 1 . Giả sử bài toán gốc (P) có phương án x bất kỳ , y là phương án bất kỳ của bài toán đối ngẫu (Q) thì f(x)  g(y). Chứng minh g(y) = bty = (Ax,y) = (x,Aty)  (x,c) = ctx = f(x). Định lý 2. Nếu x* là phương án của bài toán gốc (P) , y* là phương án của bài toán đối ngẫu (Q) và có f(x*) = g(y*) thì hai phương án này là phương án tối ưu của bài toán tương ứng. Chứng minh Giả sử x là phương án bất kỳ của P theo định lý trên thì f(x)  g(y*). Theo giả thiết f(x*) = g(y*) nên f(x)  f(x*). Nên x* là phương án tối ưu của bài toán (P). Hoàn toàn tương tự ta cũng chứng minh được y* là phương án tối ưu của (Q). Ta công nhận định lý sau : Bài toán gốc tf(x) c x min Ax b x 0      (P) Bài toán đối ngẫu t t g(y) b y max A y c y tự do       (Q) Giáo trình toán kinh tế Tổ môn kế toán 75 +, Nếu bài toán (P) có phương án tối ưu x* thì bài toán đối ngẫu (Q) cũng có phương án tối ưu y* và ngược lại , Đồng thời f(x*) = g(y*). +, Nếu hàm mục tiêu f(x) của bài toán gốc (P) không bị chặn dưới thì bài toán đối ngẫu (Q) không có phương án . Nếu hàm mục tiêu g(y) của bài toán đối ngẫu (Q) không bị chặn trên thì bài toán (P) không có phương án . BàI tập chương 3 1) Giải bài toán quy hoạch tuyến tính sau:   2 3 5 1 2 3 5 2 3 4 2 3 5 6 j f(x) x x 2x min 1 x x x 2x 7 2 2x 4x x 12 4x 3x 8x x 10 x 0 j 1,6                         Đáp số: x*=( 10,0,3,0,0,1); f(x*)=-3 2) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 5 1 2 4 5 2 3 4 5 2 5 j f(x) 2x 5x 4x x 5x min x 6x 2x 9x 32 1 3 2x x x x 30 2 4 3x x 36 x 0 j 1,5                       Đáp số:    x 32,0,30,0,0 ; f x 184   Giáo trình toán kinh tế Tổ môn kế toán 76 3) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 5 1 2 3 2 3 4 2 5 j f(x) 2x 6x 4x 2x 3x max x 2x 4x 52 4x 2x x 60 3x x 36 x 0 j 1,5                       Đáp số:  34 22 400x 0, , ,0 ; f x 3 3 3        4) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 1 2 3 1 2 3 2 3 1 2 j f(x) x 2x x min x x 2x 2 x x x 1 x x 5 2x x 2 x 0 j 1,2,3                     Đáp số:    x 0,4,1 ; f x 9    5) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 1 2 3 1 2 j f(x) 16x 7x 9x min 2 1 1 x x x 3 3 3 5x 5x 7 x 0 j 1,2,3                    Đáp số:  7 22x 0, , ; f x 23 5 15        Giáo trình toán kinh tế Tổ môn kế toán 77 6) Giải bài toán quy hoạch tuyến tính sau:   1 2 1 2 1 2 1 2 j f(x) 3x 2x max 2x x 5 x x 1 x x 3 x 0 j 1,2               7) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 1 2 3 4 1 2 3 4 j f(x) 5x x 6x 2x max 4x 4x 4x x 44 8x 6x 4x 3x 36 x 0 j 1,2,3,4                    8) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 j f(x) 2x x x x min x x 2x x 2 2x x 3x x 6 x x x x 7 x 0 j 1,2,3,4                       9) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 5 6 1 4 6 1 2 3 6 1 3 5 6 j f(x) x x x x x x min x x 6x 9 3x x 4x 2x 2 x 2x x 2x 6 x 0 j 1,2,3,4,5,6                        Giáo trình toán kinh tế Tổ môn kế toán 78 10) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 1 2 3 4 2 3 4 2 3 4 j 1 f(x) 2x 3x x x min 2 1 x x x x 9 2 x 4x 8x 4 2x 2x 3x 10 x 0 j 1,4                        Đáp số:    x 0,0,8,2,20,0 ; f x 9    11) Giải bài toán quy hoạch tuyến tính sau:   1 2 3 4 1 2 3 4 2 3 4 2 3 4 j 9 f(x) 2x 7x 5x x min 2 x x x 3x 14 x 4x x 8 x 2x 3x 20 x 0 j 1,4                        Đáp số:    x 0,0,034,16,128,0 ; f x 98    12) Chứng minh rằng bài toán sau không có lời giải:   1 2 3 4 5 6 1 2 5 6 7 2 3 5 6 7 2 4 5 6 7 j f(x) x x 2x 3x 4x x min 3 x x 2x x x 40 2 2x x x 3x x 10 1 x x x 2x x 60 2 x 0 j 1,7                                Đáp số: Bài toán không có lời giải Giáo trình toán kinh tế Tổ môn kế toán 79 11) Giải bài toán quy hoạch tuyến tính sau: 1 2 3 4 1 2 3 4 1 2 3 1 2 4 j 3 f(x) 2x x x 6x max x 2x 4x x 9 3x 2x x 4 5x 3x x 1 x 0 ; j 3;x 0                        Đáp số:    x 0,0,2,1,0,6 ; f x 8   ------------------------o0o----------------------- Giáo trình toán kinh tế Tổ môn kế toán 80 Chương 4: bài toán vận tải Bài 1: thiết lập bài toán vận tải . 1. Bài toán vận tải là một trong những mô hình có nhiều ứng dụng trong thực tế . Trước hết ta xét bài toán vận tảI cân bằng thu phát . Bài toán được phát biểu như sau : Có m điểm Ai i=1,2,... m . cung cấp một loại mặt hàng nào đó có khối lượng tương ứng là ai i=1,2... m ( ai ≥ 0 i=1,2, ... m) và n điểm jB (j=1,2... n ) tiêu thụ loại hàng đó với khối lượng tương ứng là: jb ( bj ≥ 0 j =1,2,..n) . Ta gọi Ai là điểm phát thứ i và Bj là điểm thu thứ j ( i=1,2, ... m. j=1,2, ... n). Giả sử rằng tổng lượng hàng ở mọi điểm phát bằng tổng lượng hàng ở mọi điểm thu . Khi đó ta có : m n i j i 1 j 1 a b     được gọi là điều kiện cân bằng thu phát . Giả sử chi phí vận chuyển một đơn vị hàng ( Ví dụ đơn vị là tấn ) từ điểm phát Ai tới điểm thu jB là ijc đơn vị tiền (Ví dụ đơn vị là đồng) . Khi đó C =(cij)m x n được gọi là ma trận cước phí . Hãy lập kế hoạch vận chuyển từ mỗi điểm phát đến mỗi điểm thu bao nhiêu đơn vị hàng sao cho : - Các điểm phát đều phát hết hàng . - Các điểm thu đều nhận đủ hàng . - Chi phí vận chuyển là nhỏ nhất . Ta sẽ xây dựng mô hình toàn học cho bài toán trên . Gọi ijx là số đơn vị hàng chuyển từ điểm phát Ai đến điểm thu jB Tổng lượng hàng xuất phát từ điểm phát Ai tới mọi điểm thu jB là ai khi đó : n ij i j 1 x a   i = 1,2 ... m Tổng lượng hàng thu về điểm thu jB từ mọi điểm phát Ai là bj khi đó : Giáo trình toán kinh tế Tổ môn kế toán 81 n ij j i 1 x b   j = 1,2... n. Tổng cước phí phải trả là : m n ij ij i 1 j 1 c x    Tổng này càng nhỏ càng tốt . Mô hình toàn học của bài toán vận tải có dạng : m n ij ij i 1 j 1 c x min    n ij i j 1 x a   i = 1,2 ... m (1) n ij j i 1 x b   j = 1,2... n. (2) ijx ≥ 0 (i = 1,2 ... m ; j = 1,2... n ) (3) Ma trận X = ( ijx ) m x n thoả mãn (1) , (2) , (3), được gọi là một phương án của bài toán vận tảI và nếu nó làm cho m n ij ij i 1 j 1 c x    đạt giá trị nhỏ nhất thì gọi là phương án tối ưu của bài toán vận tải . Rõ ràng bài toán vận tảI là một bài toán quy hoạch tuyến tính dạng chính tắc , vì thế có thể giảI nó bằng thuật toán quy hoạch tuyến tính . Nhưng khi đó số ẩn thường khá lớn (m.n ijx và m+n ẩn phụ ) . Số ràng buộc cũng nhiều ( m+ n ràng buộc) .và việc đó thường dẫn đến những chi phí tính toán không cần thiết .Tuy nhiên lợi dụng cấu trúc đặc biệt của bài toán vận tảI ta có thể cụ thể hơn thuật toán đơn hình và thu được thuật toán đơn giản và hiệu quả đẻ giảI nó . 2. Định lí 1 : Điều kiện cân bằng thu phát ( m n i j i 1 j 1 a b     ) là điều kiện cần và đủ để bài toán vận tải có phương án tối ưu . Chứng minh : Giả sử bài toán vận tải có phương án tối ưu X* = *ij(x ) khi đó : n * ij i j 1 x a   i = 1,2 ... m Giáo trình toán kinh tế Tổ môn kế toán 82 n * ij j i 1 x b   j = 1,2... n. Vì vậy : m m n n m n * * i ij ij j i 1 i 1 j 1 j 1 i 1 j 1 a x x b             Ngược lại , giả sử ta có m n i j i 1 j 1 a b     , ta cần chứng minh bài toán vận tảI có phương án tối ưu , tức là cần chứng minh tập các phương án của bài toán khác rỗng và hàm mục tiêu bị chặn dưới . Thật vậy : ta đặt Q = m n i j i 1 j 1 a b     > 0 , xét vec tơ i ja b X ( ) i = 1,m;j 1,n Q   có thành phần i j ij a b x Q  . Ta có n n n i j j ij i i j 1 j 1 j 1 a b b x a a Q Q        i = 1, . . .m. m m m i j i ij j j i 1 i 1 i 1 a b a x b b Q Q        j = 1, ... n . Và rõ ràng ijx ≥ 0 với mọi i , j . Vậy X là một phương án của bài toán vận tải , tức là bài toán vận tải có tập phương án khác rỗng. Xét phương án bất kỳ của bài toán vận tải X = (xij ) từ điều kiện các (xij) ≥ 0 và n ij i j 1 x a   suy ra ij i0 x a  vì vậy ij ij ij ij ij ij i ij c x 0 với c 0 c x c a với c 0      suy ra ij ijc x  min {0 , cij ai } i= 1.2m ; j = 1,2,n . Do đó f(x) = m n ij ij i 1 j 1 c x    ≥ m n ij i i 1 j 1 min{0, c a }    = const . Vậy hàm mục tiêu bị chặn dưới trên miền chấp nhận được , suy ra bài toán vận tải có phương án tối ưu. 3. Bảng vận tải. Để ghi các số liệu của bài toán vận tải và để giảI nó bằng các thuật toán trình bày trong mục tiếp theo , ta xây dựng một bảng gồm m + 1 dòng và n+1 cột như sau : Giáo trình toán kinh tế Tổ môn kế toán 83 jB Ai b1 b1 jb bn a1 c11 x11 c12 x12 2 jc 2jx c1n x1n a2 c21 x21 c22 x22 2 jc 2 jx c2n x2n ai ci1 xi1 ci2 x11 ijc ijx cin xin am cm1 xm1 cm2 xm2 mjc mjx cmn xmn Trong bảng mỗi hàng đặc trưng cho một điểm phát , mỗi cột đặc trưng cho một điểm thu : hàng trên cùng ghi các jb ( j = 1..n ) , cột đầu tiên ghi các ai (i = 1m) . Trừ hàng đầu tiên và cột đầu tiên , phần còn lại của bảng gọi là phần chính . Ô nằm trên hàng i và cột j đặc trưng cho tuyến đường từ Ai tới jB gọi là ô (i,j) . Phần chính U của bảng vận tải là : U={(i,j ) : i=1..m ; j = 1 n } . ở mỗi ô (i,j) ta ghi cước phí vận chuyển ijc vào góc trên phía trái và lượng vận chuyển ijx trong phương án X vào góc dưới bên phải. Định nghĩa 1 : Những ô ( i,j)  U với ijx > 0 được gọi là nhưng ô chọn ứng với phương án X . Nhưng ô còn lại được gọi là những ô loại. Ô chọn đặc trưng cho tuyến đường có vận tảI hàng hoá qua . Định nghĩa 2 : Một dãy các ô (i,j)  U mà hai ô liên tiếp ( và không quá hai ô ) của dãy luôn nằm trên cùng một hàng hoặc một cột được gọi là một dây chuyền . Giáo trình toán kinh tế Tổ môn kế toán 84 Ví dụ 1 : Trong bảng : jB Ai b1 b2 b3 a1 X .. . X  a2 X .  . X a3 X Dãy các ô (1,2) , (1,3), (2,3),(2,1),(3,1) lập thành một dây chuyền . Định nghĩa 3 . Một dây chuyền khép kín được gọi là một vòng hay một chu trình . Ví dụ 2 : Trong bảng sau : jB Ai b1 b2 b3 b4 a1 X .  . . X  a2 X .  .  . X a3  X  X Dãy các ô (1,2) , (1,4 ) , (2,4), (2,1), (3,1), (3,2) lập thành một chu trình. Như vậy , một tập hợp được sắp thứ tự các ô của phần chính bảng đơn hình tạo thành một vòng nếu thoả mãn các điều kiện sau : a, Hai ô cạnh nhau nằm trên cùng một hàng hoặc một cột . Giáo trình toán kinh tế Tổ môn kế toán 85 b, Không có ba ô nào nằm trên cùng một hàng hoặc một cột. c, Ô đầu tiên nằm trên cùng một hàng hay một cột với ô cuối cùng. Giả sử L  U là một tập hợp các ô nào đó của bảng vận tải . Định nghĩa 4 : Ta nói rằng L chứa vòng nếu từ các ô của L ta có thể xây dựng được ít nhất một vòng , ngược lại ta nói rằng L không chứa vòng. Định lí 2 : Nếu trong mỗi dòng và cột của bảng vận tải hoặc không có ô nào của L , hoặc có ít nhất hai ô của L thì L chứa vòng. Chứng minh : Bắt đầu từ ô nào đó (i1, j1 )  L. Vì trên dòng i1 còn ít nhất một ô khác của L, chẳng hạn (i1 , j2 ) , nên ta di chuyển theo dòng i1 tới ô đó . Vì (i1 , j2 ) không phảI là ô duy nhất trên cột j 2 nên ta di chuyển theo cột này tới ô (i2 , j 2 )  L nằm trên cột này . Tiếp tục như vậy từ ô (i2, j 2 ) của L ta di chuyển đến ô khác của L thuộc cột khác của bẳng vận tải Quá trình này không thể kéo dài vô tận vì số ô của L là hữu hạn . Vì vậy đến một bước nào đó ta sẽ quay lại ô mà ta đã đi qua , tức là ta đã thực hiện được một vòng. 4. Cách phá vỡ và xây dựng vòng. Cho X là một phương án của bài toán vận tải . Lập bảng vận tải tương ứng với X đó . Gọi G(X) là tập các ô chọn, nếu G(X) không chứa vòng thì X là phương án cơ sở chấp nhận được . Nếu G(X) chứa vòng thì ta phảI tìm cách phá vỡ các vòng trong nó tức là tìm cách xây dựng từ phương án X phương án không chứa vòng , nói cách khác là tìm phương án mới là phương án cơ sở chấp nhận được . Định lí 1 : Giả sử X là phương án của bài toán vận tải và G(X) chứa vòng . Khi đó , từ phương án X ta luôn có thể chuyển sang một phương án mới X không tồi hơn X ( tức là f( X ) ≤ f(X) ) với tập các ô chọn G( X ) không chứa vòng . Chứng minh : Giả sử G(X) chứa vòng V . Đánh dấu các ô trong V bởi các dấu + và - sao cho không có hai ô nào nằm cạnh nhau trong V được đánh cùng một dấu . Gọi V+ là tập các ô trong V được đánh dấu + , và V- là tập các ô trong V được đánh dấu . Không giảm tổng quát có thể coi : ij ij (i, j) V (i, j) V c c      (4) Xây dựng vec tơ X = ( ijx ) theo công thức : Giáo trình toán kinh tế Tổ môn kế toán 86 ij ij ij ij x nếu (i, j) V x x nếu (i, j) V x nếu (i, j) V              (5) Trong đó  = min { ijx , (i,j)  V - Rõ ràng ijx ≥ 0  (i,j) , ngoài ra do V là vòng nên từ (5) ta có : n n ij ij i j 1 j 1 m m ij ij j i 1 i 1 x x a (i = 1,m) x x b (j = 1,n)             Vật X là một phương án của bài toán vận tải. Ta lại có : m n m n ij ij ij ij ij ij i 1 j 1 i 1 j 1 (i, j) V (i,j) V m n ij ij i 1 j 1 f(X) c x c x ( c c ) c x f(X)                     Từ (5) và cách xác định nên sẽ có ít nhất một ô (i0 , j0 ) V  để  = 0 0i j x , do đó 0 0i j x =0 , và ô (i0 , j0 ) V  sẽ không là ô chọn nữa . Do đó G( X ) không còn có mặt trong vòng V nữa . Nếu G( X ) vẫn còn trong vòng V thì ta thay X bằng X và lặp lại thủ tục vừa nêu trên thì sau một số hữu hạn các bước lặp ta phảI đến một phương án không tồi howwn phương án đã qua , và tập hợp các ô chọn tương ứng không chứa vòng. Định lí được chứng minh . Định lí 2 : Giả sử m , n > 1 . Khi đó tập L gồm m + n ô bất kì của bảng vận tải luôn chứa vòng duy nhất . Và tập L gồm m + n - ô bất kì của bảng vận tải không chứa vòng . Chứng minh : Khi m = n =2 thì rõ ràng m + n =4 khi đó L có chứa vòng . Khi m > 2 ; n > 2 ta chúng minh định lí bằng quy nạp theo tổng số dòng và cột k = m + n . Giáo trình toán kinh tế Tổ môn kế toán 87 Giả sử định lí đúng với k = m + n – 1 , ta cần chứng minh nó đúng khi k = m + n Có hai trường hợp xảy ra : Trường hợp 1 : Trong số m + n ô của L có một ô nào đó nằm một mình trong một dòng hay một cột . Khi đó , loại bỏ dòng hay cột chứa ô đó , trong phần còn lại có m + n – 1 ô của L , theo giả thiết quy nạp thì L có chứa vòng , định lí được chứng minh . Trường hợp 2 : Trong mỗi dòng và cột của bảng hoặc không có ô nào của L hoặc có ít nhất 2 ô của L thì theo định lí trên tập L chứa vòng , định lí được chứng minh. Từ định lí này ta có thủ tục xây dựng vòng từ m + n ô của L trong bảng vận tảI như sau : 1) Xoá bỏ khỏi bảng vận tải tất cả các dòng và cột chứa không quá một ô của L . Việc này được lặp lại cho tới khi được bảng vận tải mà mỗi dòng và cột của nó chứa ít nhất 2 ô của L . 2) Từ bảng thu được vòng có thể được xây dựng theo định lí 2. Ví dụ 4 . Xây dựng vòng từ các ô được đánh dấu X trong bảng sau : 1 2 3 4 5 6 7 8 9 10 1 X X X X 2 X X X X 3 X X X X 4 X X Bỏ các cột 1,2,4,5,6,7,vì chỉ chứa 1 ô đánh dấu x 3 8 9 10 1 X X X 2 X 3 X X Giáo trình toán kinh tế Tổ môn kế toán 88 4 X X Bỏ hàng 2 ta được bảng . 3 8 9 10 1 X X X 3 X X 4 X X Bỏ cột 3 được bảng 8 9 10 1 X  ...X  3 X .  ....X 4  X...  ....X Ta thu được vòng V = { (1,8)+, (1,9)- , (4,9)+ , (4,10)- , (3,10)+, (3,8)- } -------------------o0o------------------- Giáo trình toán kinh tế Tổ môn kế toán 89 Bài 2: Tìm phương án cơ sở xuất phát . Đối với bài toán quy hoạch tuyến tính tổng quát , việc tìm phương án cơ sở xuất phát đòi hởi phảI giảI một bài toán quy hoạch tuyến tính phụ . Công việc này đòi hỏi một khối lượng tính toán không nhỏ . Tuy nhiên do đặc thù riêng của mình đối với bài toán vận tảI hiện nay có khá nhiều phương pháp rất hiệu quả để tìm một phương án cơ sở chấp nhận được cho nó . Trong mục này ta giới thiệu một số phương pháp phổ biến nhất. 1. Phương pháp góc tây bắc . Lập bảng vận tải , các số liệu i j ija , b , c ( i = 1..m ; j = 1..n ) được ghi vào bảng vận tải như đã được mô tả trong mục trước . Bắt đầu từ ô (1,1) nằm ở góc trên bên tráI của bảng này ( ô này nằm ở vị trí góc tây bắc của bảng , và tên gọi xuất phát từ đây) ta tiến hành phân phối lượng hàng vào ô này: x11 = min { a1 , b1 } Các lượng thu phát còn lại là : , , , , i i 1 1 11 j j 1 1 11a a (i 1) , a a x , b b (j 1), b b x        Nếu x11 = a1 = min { a1 , b1 } thì a’1 = 0 khi đó xoá dòng thứ nhất của bảng vận tải và thu được bảng mới gồm m - 1 dòng và n cột với lượng pất và thu tương ứng là , ,i ja (i 2, m ); b ( j 1, n )  Lặp lại cách phân phối như vậy đối với bảng mới , tuác là bắt đầu với ô ở góc tây bắc và phân phối lượng hàng vận chuyển vào ô này sao cho hoặc chở hết hàng ở điểm phát , hoặc nhận đủ hàng ở điểm thu tương ứng với nó . Như vậy sau mỗi lần phân phối ta lại xoá đi được một dòng hoặc một cột của bảng nên sau đúng m + n - 1 lần phân phối thủ tục trên sẽ phảI kết thúc . Do đó phương án xây dựng theo phương pháp góc tây bắc sẽ có không quá m + n - 1 thàng phần khác không . Ví dụ : Xây dựng phương án vận tải tcho bài toán vận tảI theo phương pháp góc tây bắc với số liệu cho trong bảng sau : Giáo trình toán kinh tế Tổ môn kế toán 90 jB Ai B1:20 B2:40 B3:30 A1: 30 1 20 3 10 5 A2: 25 5 4 25 2 A3: 35 8 5 5 4 30 Phân tích : Phân cho ô (1,1) : 20 , xoá cột 1 , ở A1 còn 10 . Phân cho ô (1,2) : 10 , xoá hàng 1 , ở B2 còn 30 . Phân cho ô (2,2) : 25 , xoá hàng 2, ở B2 còn 5. Phân cho ô (3,2) : 5 , xoá cột 2 , ở A3 còn 30 . Phân cho ô (3,3) : 30 . Ta được phương án cơ sở xuất phát là : X = ( 20,10,0,0,25,0,0,5,30). Và giá trị hàm mục tiêu tương ứng là : f (x) = 1.20 + 3.10 + 4.25 + 505 + 4.30 = 295. 2. Phương pháp cực tiểu cước phí. Theo phương pháp này ta ưu tiên phân phối nhiều nhất vào ô có cước phí nhỏ nhất trên toàn bảng . Giả sử trong ma trận cước phí C = ( ij mxnc ) có cr s là nhỏ nhất trong các cij . Khi đó ta phân phối tối đa vào ô (r,s) cụ thể là : r r s ij s r s a nếu a b (*) x b nếu a >b (**)     Trong trường hợp (*) điểm Ar đã phất hết hàng nên có thể xoá hàng r của bảng , ở điểm thu Bs chỉ còn cần bs – ar đơn vị hàng . Trong trường hợp (**) điểm thu Bs dã nhận đủ hàng nên có thể xoá đi cột s của bảng , và ở điểm phát Ar chỉ còn lại ar – bs đợn vị hàng . Trong bảng còn lại có số hàng hoặc cột ít hơn , ta lặp lại cách phân phối trên cho tới khi hết hàng hoặc đáp ứng đủ yêu cầu của các điểm thu . Các ô chon còn lại sẽ không chứa vòng và là phương án cơ sở chấp nhận được . Nếu chưa đủ m + n – 1 ô thì ta có thể bổ sung thêm một số ô “ ô chọn không “ cho đủ m + n – 1 ô chọn không tạo thành vòng . Các ô chọn không tức là phân phối lượng hàng bằng 0 vào ô đó. Ví dụ : Giáo trình toán kinh tế Tổ môn kế toán 91 Xây dựng phương án vận tải theo phương pháp cực tiểu cước phí với số liệu như trong ví dụ trước : jB Ai B1:20 B2:40 B3:30 A1: 30 1 20 3 10 5 A2: 25 5 4 2 25 A3: 35 8 5 5 4 30 Phân tích : * phân cho ô (1,1) là ô có cước phí nhỏ nhất , 20 đơn vị hàng , xoá cột 1 . * phân cho ô (2,3) : 25 đơn vị hàng .Xoá dòng 2. * phân cho ô (1,2) :10 đơn vịhàng xoá dòng 1. * phân cho ô (3,3) : 5 đơn vị hàng , xoá cột 3. * phân cho ô (3,2) : 30 đơn vị hàng . Ta được phương án cơ sở xuất phát là : X = (20,10,0,0,0,25,0,0,30,5) Và giá trị hàm mục tiêu f(x) = 1.20+3.10+2.25+5.30+4.5 = 270. ---------------------o0o--------------------- Bài 3: Các thuật toán giảI bài toán vận tảI . 1. Thuật toán quy 0 cước phí các ô chọn Ta có nhận xét sau đây : Nếu cộng vào hàng i của ma trận cước phí C = ( ij mxnc ) một số ri tuỳ ý (i = 1m) và cộng vào cột j củ nó mọt số tuỳ ý js ( j = 1n) thì ta có bài toán vận tảI mới với ma trận cước phí ij mxnC (c ) trong đó ij ij i j(c ) (c ) r s   tương đương với bài toán ban đầu ( tức là phương án tối ưu của bài toán ban đầu là phương án của bài toán kia và ngược lại .) Thật vậy giá trị hàm mục tiêu trong bài toán mới là : Giáo trình toán kinh tế Tổ môn kế toán 92 m n m n ij ij ij i j ij i 1 j 1 i 1 j 1 m n m n n m ij ij i ij j ij i 1 j 1 i 1 j 1 j 1 i 1 m n i i j j i 1 j 1 f (X) c x (c r s )x c x r x s x f(X) r a s b f(X) C                                  Trong đó C = m n i i j j i 1 j 1 r a s b     là một hằng số . Giá trị của hai hàm mục tiêu chỉ khác nhau một hằng số nên điểm cức trị của chúng trùng nhau. Từ những điều trên ta có thuật toán quy không cước phí như sau : + Bước 1 : Giả sử ta đã có một phương án cơ sở chấp nhận được ban đầu với m + n -1 ô chọn ( trong đó có thể có một số ô chọn không ) . Ta cộng vào hàng I của ma trận cước phí ( ij mxnc ) một số ri i=1..m và cộng vào cột j của nó số js ( j = 1..n) và chọn các số ri và sj sao cho ma trận cước phí mới C mà ở đó các ô chọn ijc = 0 . + Bước 2:( Kiểm tra tiêu chuẩn tối ưu ) 1. Nếu sau khi quy không cước phí các ô chọn mà các ô loại đều có cước phí lớn hơn không thì phương án đang xét là phương án tối ưu vì khi đó bất kì ô loại nào thay cho bất kì ô chọn nào cước phí cũng tăng lên và phương án mới là tồi hơn . 2. Nếu sau khi quy không cước phí các ô chọn mà có ít nhất mội ô loại có cước phí âm , thì phương án đang xét không phảI là tối ưu vì khi đó ta thay ô có cước phí âm vào thay cho ô chọn có cước phí không thì cước phí giảm đI .Khi đó ta chuyển bước 3 . + Bước 3: Xây dựng phương án mới tốt hơn. 1.Tìm ô đưa vào: giả sử ô (i*, j *) có cước phí âm nhỏ nhất thì chọn ô (i* j *) làm ô đưa vào . 2. Tìm vòng điều chỉnh : Bổ sung thêm ô (i*, j * ) vào m + n -1 ô chọn ban đầu thì se xuất hiện vòng V duy nhất . 3. Đánh dấu các ô của vòng V : Ta đánh dấu các ô của vòng V bắt đầu từ ô (i*, j * ) ta đánh + , ô tiếp theo ta đánh dấu - sao cho hai ô cạnh nhau của V không đánh cùng một dấu . Khi đó các ô của V chia thành hai lớp : V+ : các ô được đánh dấu + . Giáo trình toán kinh tế Tổ môn kế toán 93 V - : các ô được đánh dấu - . 4. Tìm các ô đưa ra và lượng điều chỉnh : Giả sử min { ijx : (i, j) V  } = 0 0i jx khi đó ( i0 j 0 ) là ô đưa ra và 0 0i jx là lượng điều chỉnh , nói cách khác tìm xem trong các ô đánh dấu trừ ,ô nào được phân hàng ít nhất thì đó là ô đưa ra và lượng hàng ở ô đó chính là lượng điều chỉnh . 5. Phương án mới ij mxnX (x ) được tiính như sau : 0 0 0 0 + ij i j - ij ij i j ij x x nếu (i,j) V x x x nếu (i,j) V x (i,j) nếu V          Nhận xét : +) Ô ( i0 j 0 ) trước có 0 0i jx đơn vị hàng và ở ô đánh dấu trừ nên bị trừ đI 0 0i jx đơn vị hàng thành ô loại . +) Ô (i*, j * ) trước là ô loại và là ô đánh dấu + nên được cộng vào 0 0i jx đơn vị hàng thành ô chọn . +) ij mxnX (x ) là phương án vì x 0 và mỗi hàng hoặc cột của vòng V đI qua đều có một ô đánh dấu + và một ô đánh dấu – nên tổng m i j i 1 x   và n i j j 1 x   Vẫn không đổi . +) Phương án X là phương án cơ sở chấp nhận được vì các ô chọn không tạo thành vòng . Phương án này tốt hơn vì đã loại ra một ô có cước phí không và thay vào đó ô có cước phí nhỏ hơn 0 . Sau khi có phương án cơ sở chấp nhận được mới ta quay lại từ bước một và sau một số hữu hạn lần lặp ta sẽ tìm được phương án tối ưu của bài toán vận tảI vì bài toán vận tảI cân bằng thu phát luôn có phương án tối ưu , và số phương án cơ sở chấp nhận được là hữu hạn. 2. Các ví dụ. Ví dụ 1 : Giải bài toán vận tải với số liệu cho trong bảng sau : Giáo trình toán kinh tế Tổ môn kế toán 94 jB Ai B1:20 B2:40 B3:30 A1: 30 1 20 3 10 5 A2: 25 5 4 2 25 A3: 35 8 5 5 4 30 Dùng phương pháp cực tiểu cước phí ta tìm được phương án cơ sở xuất phát X = {20,10,0,0,0,25,0,30,5} và có f(X) = 270. Quy không cước phí các ô chọn : Ta cộng vào hàng i số ri ( i= 1,2,3) vào cột j số js ( j = 1,2,3 ) sao cho cước phí các ô chon bằng 0. Ta có tập các ô chọn G(X) = { (1,1) , (1,2) , (2,3), (3,2), (3,3) }. để tìm các số ri và js đó ta cần giải hệ phương trình : 1 1 1 2 2 3 3 2 3 3 1 r s 0 2 r s 0 3 r s 0 5 r s 0 4 r s 0                     đây là hệ phương trình gồm 5 phương trình tuyến tính và có 6 ẩn : Cho r1 = 0 ta tìm được r2 = 0 , r3 = -2 , s1 = -1 , s2 = -3 , s3 = -2 . Ma trận cước phí mới là : jB Ai B1:20 B2:40 B3:30 A1: 30 0 20 0 10 3 A2: 25 4 1 0 25 A3: 35 5 0 5 0 30 Giáo trình toán kinh tế Tổ môn kế toán 95 Ta thấy các ô loại đều có cước phí dương . Vậy phương án X = {20,10,0,0,0,25,0,30,5} chính là phương án tối ưu . Ví dụ 2 : Giải bài toán vận tải sau đây bằng phương pháp quy không cước phí các ô chọn. jB Ai B1:80 B2:20 B3:60 A1: 50 5 4 1 50 A2: 40 3 20 2 20 6 A3: 70 7 60 9 11 10 Tìm phương án cơ sở xuất phát ( bằng phương pháp cực tiểu cước phí ). * Phân cho ô (1,3) là ô có cước phí nhỏ nhất , 50 đơn vị hàng , xoá hàng 1. B3 còn cần 10. * Phân cho ô (2,2) : 20 đơn vị hàng .Xoá cột 2. A2 còn lại 20. * Phân cho ô (2,1) : 20 đơn vị hàng xoá dòng 2. B1 còn cần 10 . * Phân cho ô (3,1) : 60 đơn vị hàng , xoá cột 1. * Phân cho ô (3,3) : 10 đơn vị hàng . Ta được phương án cơ sở xuất phát là : X = (0,0,50,20,0,60,0,10) ; và giá trị hàm mục tiêu là : f(X) = 680. + Bước 1 : quy không cước phí các ô chọn : Tập các ô chọn là : G(X) = { (1,3), (2,1), (2,2), (3,1), (3,3) }. Cộng vào hàng i số ri (i=1,2,3) và cột j số js (j = 1,2,3) sao cho cước phí các ô chọn trong G(X) bằng 0 , tức là ta có hệ phương trình : 1 3 2 1 2 2 3 1 3 3 1 r s 0 3 r s 0 2 r s 0 7 r s 0 11 r s 0                     Giáo trình toán kinh tế Tổ môn kế toán 96 Đây là hệ gồm 5 phương trình , 6 ẩn số . Để giải ta cho một ẩn bằng một giá trị xác định . Chẳng hạn r2 = 0 . Ta được : r1 = 6 r3 = - 4 , s1 = -3 , s2 = -2 , s3 = -7. Ma trận cước phí mới la: 8 8 0 0 0 1 0 3 0          + Bước 2 : kiểm tra điều kiện tối ưu . Phương án này chưa tối ưu vì có ô loại (2;3) có cước phí âm là -1 . + Bước 3 : Lập phương án mới : 1. Tìm ô đưa vào : Vì ô (2;3) là ô loại duy nhất có cước phí âm nên ô này là ô đưa vào. 2. Tìm vòng điều chỉnh : bổ sung thêm ô (2;3) vào tập cá ô chọn nên ta tìm được vòng V = { (2;3)+, (3;3)- , (3;1)+ , (2;1)- }. 3. Đánh dấu các ô của vòng V: V+ = {(2;3) , (3;1) } và V- = {(3;3) , (2;1) }. 4. Tìm ô đưa ra : min { x33 , x21} = min (10;20) = 10 = x33 , nên ta có ô đưa ra là (3;3) , lượng điều chỉnh là x33 =10. 5. Lập phương án mới : 23 23 31 31 33 33 21 21 x x 10 0 10 10 x x 10 60 10 70 x x 10 10 10 0 x x 10 20 10 10                     Lượng hàng ở các ô khác được giữ nguyên . Ta có phương án mới là : x (0,0,50,10,20,10,70,0,0) f(x) 670   Ta có phương án cơ sở chấp nhận được x . Quay lại bước 1 ta có : + Bước 1 : Quy 0 các ô chọn : 1 3 2 1 2 2 3 1 3 3 0 r s 0 0 r s 0 0 r s 0 1 r s 0 0 r s 0                     Giáo trình toán kinh tế Tổ môn kế toán 97 Cho r2 0 ta được s1 = 0,s2 = 0, s3 = 1, r1 =-1 , r3 = 0 Ta có ma trận cước phí mới là : 7 7 0 0 0 0 0 3 1           Ta thấy các ô loại đếu có cước phí dương . Vậy phương án tối ưu và giá trị tối ưu là : x (0,0,50,10,20,10,70,0,0) f(x) 670   ---------------------o0o------------------------- Bài 4: Bài toán vận tải không cân bằng thu phát. 1. Khái niệm. Đó là bài toán vận tải mà điều kiện cân bằng thu phát n m i j i 1 j 1 a b           không được thoả mãn. Khi đó có 2 khả năng xảy ra: hoặc n m i j i 1 j 1 a b           (tức là tổng lượng hàng phát của các điểm phát lớn hơn tổng lượng hàng thu ở các điểm thu) hoặc n m i j i 1 j 1 a b           . Ta xét từng trường hợp: a. Nếu n m i j i 1 j 1 a b           : Ta đưa thêm vào điểm thu giả n 1B  với lượng hàng thu tương ứng n m n 1 i j i 1 j 1 b a b 0             và xét bài toán vận tải với m điểm phát và n+1 điểm thu: Giáo trình toán kinh tế Tổ môn kế toán 98      m n 1 ij ij i 1 j 1 n 1 ij i j 1 m ij j i 1 ij in 1 c x min x a x b x 0 i 1,m; j 1,n 1 c 0; i 1,m                             Rõ ràng n 1 n n m n m j j n 1 j i j i j 1 j 1 j 1 i 1 j 1 i 1 b b b b a b a                    Nên bài toán trên là bài toán vận tải cân bằng thu phát, vì vậy ta có thể dùng các thuật toán đã biết để giải ta thu được phương án tối ưu    ijX x i 1,m; j 1,n 1     . Nếu in 1x 0   thì điều đó có nghĩa là ta không vận chuyển hết hàng từ các điểm phát Ai ở đó tồn đọng một lượng hàng là in 1x   . b. Nếu n m i j i 1 j 1 a b           : Ta đưa them biến phát giả m 1A  với lượng phát tương ứng là: m n m 1 j j 1 i 1 a b ai 0             Và xét bài toán vận tải vơi m+1 điểm phát và n điểm thu:          m 1 n ij ij i 1 j 1 n ij i j 1 m 1 ij j i 1 ij m 1j c x min x a i 1,m 1 x b j 1,n x 0 i 1,m 1; j 1,n c 0; j 1,n                                 Bài toán này cũng là bài toán vận tải cân bằng thu phát, vì vậy ta có thể dùng các thuật toán đã biết để giải ta thu được phương án tối ưu Giáo trình toán kinh tế Tổ môn kế toán 99    ijX x i 1,m 1; j 1,n     . Nếu m 1jx 0   thì điều đó có nghĩa là ta không đáp ứng đủ nhu cầu tiêu thụ ở điểm Bj , ở đó đòi hỏi một lượng hàng là m 1jx   . 2. Ví dụ. Giải bài toán vận tải với các số liệu cho trong bảng sau: jB Ai B1:20 B2:40 B3:60 A1: 80 3 4 1 A2: 30 4 2 3 A3: 50 1 5 6 Vì 3 3 i j j 1 j 1 a 80 30 50 160, b 20 40 60 120            ta có trường hợp thứ nhất. Đưa thêm điểm thu giả 4B với lượng hàng cần thu 4b 160 120 40   . Ta có bảng vận tải: jB Ai B1:20 B2:40 B3:60 4B : 40 A1: 80 3 -7 4 -4 1 X 0  0 . X 0  40 A2: 30 4 -6 2 X 0 30 3   0  0   2  A3: 50 1 X 0 20 5 X 0 10 6  X 0 20 0  X 5 Giáo trình toán kinh tế Tổ môn kế toán 100 Bằng phương pháp cực tiểu cước phí ta tìm được phương án cơ sở xuất phát: X=(0,0,40,40,0,30,0,0,20,10,20,0) với f(x)=290 + Tìm các thế vị    i ju i 1,2,3 ;v j 1,2,3,4   bằng cách giải hệ phương trình: 1 3 2 4 2 2 3 1 3 2 3 3 u v 1 u v 0 u v 2 u v 1 u v 5 u v 6                  Cho 1u 0 ta được 2u 2 , 3u 5 , 1v 4  , 2v 0 , 3 4v 1, v 0  + Tính các ij i j ij 11 12 13 14 21 22 23 24 31 32 33 34 u v c ta co : 7 4 0 0 6 0 0 2 0 0 1 5                                Ô đưa vào là ô (3,4) vì  34 ij ijmax , 0     . + Có vòng                       33 13 33 V 3,4 , 3,3 , 1,3 , 1,4 V 3,4 , 1,3 ; V 3,3 , 1,4 min x ,x min 20,40 20 x                Ô đưa ra là ô (3,3). + Phương án mới:    ij ij 33 33 14 34 X x co x i, j V. x x 20 20 20 0 ; x 40 20 20 x 0 20 20               Ta có bảng tương ứng với phương án X Giáo trình toán kinh tế Tổ môn kế toán 101 jB Ai B1:20 B2:40 B3:60 4B : 40 A1: 80 3 -2 4 X . 1  1 . X 0 60 0 . X 0  20 A2: 30 4 -6 2  X 0  30 3 -5 0   -3  A3: 50 1 X 0 20 5  X. 0 10 6 . . -6 0  X 0 Lặp lại quá trình trên với X= X +Tìm các thế vị    i ju i 1,3 ;v j 1,4   bằng cách giải hệ phương trình: 1 3 1 4 2 2 3 1 3 2 3 4 u v 1 u v 0 u v 2 u v 1 u v 5 u v 0                  Cho 1u 0 ta được 2u 3  , 3u 0 , 1v 1 , 2v 5 , 3 4v 1, v 0  + Tính các ij i j ij 11 12 13 14 21 22 23 24 31 32 33 34 u v c ta co : 2 1 0 0 6 0 5 3 0 0 6 0                                  Ô đưa vào là ô (1,2) vì 12 1 0   . Giáo trình toán kinh tế Tổ môn kế toán 102 + Có vòng                       14 32 32 V 1,2 , 1,4 , 3,4 , 3,2 V 1,2 , 3,4 ; V 1,4 , 3,2 min x ,x min 20,10 10 x                +Phương án mới:    ij ij 12 14 32 34 X x co x i, j V. x 0 10 10 ; x 20 10 10 x 10 10 0 ; x 10 20 30                X=(0,10,60,10,0,30,0,0,20,0,0,30) với f(x)=180 Ta có bảng tương ứng với phương án là: jB Ai B1:20 B2:40 B3:60 4B : 40 A1: 80 3 4 X 10 1 X 60 0 X 10 A2: 30 4 2 X 30 3 0 A3: 50 1 X 0 20 5 6 0 X 30 Xác định các thế vị bàng cách giải hệ phương trình: Giáo trình toán kinh tế Tổ môn kế toán 103 1 2 1 3 1 4 2 2 3 1 3 4 u v 4 u v 1 u v 0 u v 2 u v 1 u v 0                  Cho 1u 0 ta được 2u 2  , 3u 0 , 1v 1 , 2v 4 , 3 4v 1, v 0  + Tính các ij i j ij 11 12 13 14 21 22 23 24 31 32 33 34 u v c ta co : 2 0 0 0 5 0 4 2 0 1 5 0                                   Ta thấy tất cả  ij 0, i, j   . Nên phương án cuối cùng tìm được ở trên chính là phương án tối ưu. Vởy ta có phương án tối ưu là:  X 0,10,60,10,0,30,0,0,20,0,0,30  và  f X 180  Tức là theo phương án tối ưu này thì: 80 đợn vị của điểm phát thứ nhất được phát cho điểm thu thứ hai 10 đơn vị hàng điểm thu thứ ba 60 đơn vị hàng còn dư lại 10 đơn vị hàng. 30 đơn vị hàng của điểm phát thứ hai được phát hết cho điểm thu thứ hai. 50 đơn vị hàng của điểm phát thư ba được phát cho điểm phát thứ nhất 20 đơn vị hàng còn dư lại 30 đơn vị hàng. Với phương án tối ưu này cước phí phải trả là 180 đơn vị tiền. Giáo trình toán kinh tế Tổ môn kế toán 104 Bài tập chương 4 1.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj Ai 1B : 60 2B : 70 3B : 40 4B : 30 1A :100 2 1 4 3 2A :80 5 3 2 6 3A : 20 6 2 1 5 Đáp số:   60 10 0 30 x 0 60 20 0 ; f x 460 0 0 20 0              2. Giải bài toán vận tải với các dữ liệu sau: a)     t 1 5 6 2 a 50,80,30  ;  b 20,40,60,30 ; C 3 4 1 7 4 2 3 5              Đáp số: 20 0 50 0 0 x 0 40 0 30 10 20 0 10 0 0             b)     t 7 6 5 a 25,10,45  ;  b 10,30,50 ; C 2 1 4 3 5 2              Đáp số: 0 20 5 x 0 10 0 10 0 35             Giáo trình toán kinh tế Tổ môn kế toán 105 3.Trong vụ bão lụt vừa qua có 5 điểm 1 2 3 4 5B ,B ,B ,B ,B bị ngập nặng, cần tiếp tế lương thực với yêu cầu tương ứng là 10,10,10,20,20 ( tấn). Nhà nước đã bố trí lương thực cứu trợ ở 4 kho 1 2 3 4A ,A ,A ,A với trữ lượng tương ứng là 5,15,20,30 (tấn). Quãng đường (km) từ các kho đến các điểm cần cứu trợ được cho trong bảng sau: Bj Ai 1B :10 2B :10 3B :10 4B : 20 5B : 20 1A : 5 5 1 4 6 7 2A :15 3 4 2 7 8 3A : 20 4 3 1 7 9 4A : 30 6 5 4 9 11 Lập kế hoạch vận chuyển tối ưu, sao cho các điểm cần cứu trợ nhận đủ số lương thực và tổng số tấn/km là nhỏ nhất. Đáp số:   0 5 0 0 0 10 0 0 0 5 x ; f x 435 0 5 10 5 0 0 0 0 15 15                4.Trong vụ bão lụt vừa qua có 5 điểm 1 2 3 4 5B ,B ,B ,B ,B bị ngập nặng, cần tiếp tế lương thực với yêu cầu tương ứng là 10,10,10,20,20 ( tấn). Nhà nước đã bố trí lương thực cứu trợ ở 4 kho 1 2 3 4A ,A ,A ,A với trữ lượng tương ứng là 5,15,20,30 (tấn). Quãng đường (km) từ các kho đến các điểm cần cứu trợ được cho trong bảng sau: Bj Ai 1B : 20 2B :100 3B :145 4B : 30 5B :150 1A :120 6 3 1 4 5 2A :150 1 2 5 4 3 3A :150 2 4 3 1 6 4A : 25 3 1 4 2 7 Giáo trình toán kinh tế Tổ môn kế toán 106 Lập kế hoạch vận chuyển tối ưu, sao cho các điểm cần cứu trợ nhận đủ số lương thực và tổng số tấn/km là nhỏ nhất. Đáp số:   0 0 120 0 0 0 0 0 0 150 x ; f x 940 20 75 25 30 0 0 25 0 0 0                5.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj Ai 1B : 70 2B : 20 3B : 60 4B : 80 1A : 40 15 12 6 3 2A : 70 12 9 6 8 3A :120 12 9 9 18 6.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj Ai 1B : 30 2B :15 3B : 20 4B :15 1A : 25 3 4 2 6 2A :15 5 1 6 2 3A : 40 2 1 5 3 7.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj Ai 1B :180 2B : 200 3B : 230 4B : 280 1A : 280 4 2 10 6 2A : 320 1 3 8 12 3A : 290 5 3 9 7 Giáo trình toán kinh tế Tổ môn kế toán 107 9.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj Ai 1B : 5 2B :15 3B : 20 4B :10 1A :10 2 1 4 3 2A : 25 6 0 5 2 3A :15 1 4 8 2 8.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj Ai 1B : 30 2B : 25 3B : 40 4B : 25 1A : 20 3 4 2 6 2A : 45 5 1 6 2 3A : 55 2 1 5 3 8.Giải bài toán vận tải không cân bằng thu phát với các dữ liệu cho trong bảng sau: Bj Ai 1B : 60 2B : 30 3B : 30 1A : 80 1 4 5 2A : 50 4 6 4 3A : 40 6 4 3 Giáo trình toán kinh tế Tổ môn kế toán 108 9.Giải bài toán vận tải không cân bằng thu phát với các dữ liệu cho trong bảng sau: Bj Ai 1B : 60 2B : 85 3B : 45 1A : 55 12 5 7 2A :80 4 9 11 3A : 75 8 13 2 Giáo trình toán kinh tế Tổ môn kế toán 109 Mục lục Lời nói đầu Chương I : Đại số tuyến tính. Bài 1. Vectơ n chiều Bài 2. Hệ vectơ độc lập tuyến tính, phụ thuộc tuyến tính Bài 3. Ma trận Bài 4. Định thức của ma trận Bài 5. Ma trận nghịch đảo Bài 6. Hệ phương trình tuyến tính Bài tập ôn tập chương I Chương II: Xác suất. Bài 1. Giải tích tổ hợp Bài 2. Biến cos ngẫu nhiên và xác suất Bài 3. Các định nghĩa xác suất Bài 4. Xác suất có điều kiện, công thức nhân, xác suất toàn phần, công thức Bayes Bài 5. Công thức Becnulli Bài tập ôn tập chương II Chương III: Quy hoạch tuyến tính. Bài 1. Mở đầu Bài 2. Phương pháp đơn hình Bài 3. Bài toán quy hoạch tuyến tính đối ngẫu Bài tập ôn tập chương III Chương IV: Bài toán vận tải. Bài 1. Thiết lập BTVT Bài 2. Tìm phương án cơ sở xuất phất Bài 3. Các thuật toán giải BTVT Bài 4.BTVT không cân bằng thu phát Bài tập ôn tập chương IV Trang 4 4 5 6 12 15 16 20 23 25 28 32 38 44 51 57 71 75 79 87 90 96 101 Giáo trình toán kinh tế Tổ môn kế toán 110 Tài liệu tham khảo: 1, PGS.TS Phạm Văn Kiều Giáo trình xác suất thống kê. NXB Giáo dục. 2, Nguyễn Văn Hộ Xác suất thống kê. NXB Giáo dục 3, Đặng Hùng Thắng Bài tập xác suất. NXB Giáo dục 4, TS. Phạm Đình Phùng Bài tập toán kinh tế. NXB Tài chính 5, Bùi Minh Trí Toán kinh tế. NXB Bách khoa – Hà Nội 6, Nguyễn Ngọc Thắng – Nguyễn Đình Hoá Quy hoạch tuyến tính . NXB Đại học quốc gia Hà Nội