Giáo trình Toán kinh tế - Chương 3: Quy hoạch tuyến tính

60 trang huongle 8190

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán kinh tế - Chương 3: Quy hoạch tuyến tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_kinh_te_chuong_3_quy_hoach_tuyen_tinh.pdf

Nội dung text: Giáo trình Toán kinh tế - Chương 3: Quy hoạch tuyến tính

Giáo trình toán kinh tế 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 g (x) 0, i 1,2, ,m (2) i 1 hj (x) 0, j 1,2, ,m 2 (3) n x X  R (4) n Trong đó f , gi , hj : R R ( i 1,2, ,m1 ; j 1,2, m 2 ) 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ơ x X  Rn 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à XR n , 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 m n điểm phát ít nhất phải bằng tổng yêu cầu ở các điểm thu: ai  b j i 1 j 1 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í. 51 Tổ môn kế toán
Giáo trình toán kinh tế 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 ). n Tổng lượng hàng chuyển từ Ai đến mọi Bj là xij (i = 1,m ) j 1 m Tổng lượng hàng điểm Bj nhận được từ mọi Ai là xij (j = 1,n ) i 1 m n Tổng cước phí phải trả là cij x ij . Bài toán đặt ra là: i 1 j 1 Tìm véc tơ x = (xij) (i = 1,m, j 1,n ) sao cho: m n f(x) = cij x ij min i 1 j 1 và thoả mãn các điều kiện n xij a i (i 1,m) j 1 m xij b i (j 1,n) i 1 x 0 (i 1,m;j 1,n) ij 3. Bài toán quy hoạch tuyến tính a, Dạng tổng quát : T n Tìm vec tơ x = (x1, x2, , xn ) R sao cho : n f(x)  cj x j min (max) j 1 Với các điều kiện : 52 Tổ môn kế toán
Giáo trình toán kinh tế n aij x j b i j 1 n aij x j b i (j 1,m) j 1 n aij x j b i j 1 với các ràng buộc về dấu: x 0 (j 1,n ) j 1 xj 0 (j n 1 1,n 2 ) xj dấu tự do (j n 2 1,n) Dễ thấy rằng : 1) f(x*) = min { f(x) , x D } - f(x*) = max {- f(x) , x D } n n 2) aij x j b j  ( a ij )x j b j j 1 j 1 n aij x j b j n j 1 a x b 3)  ij j j n j 1 aij x j b j j 1 n n 4) aij x j b j  a ij x j x n i b j ; x n i 0 j 1 j 1 n n 5) aij x j b j  a ij x j x n i b j ; x n i 0 j 1 j 1 Các biến xn 1 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 53 Tổ môn kế toán
Giáo trình toán kinh tế n f(x)  cj x j min j 1 n aij x j b i (i 1,m) j 1 xj 0 (j 1,n) hay dưới dạng ma trận: f(x) ct 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 f(x)  cj x j min j 1 n aij x j b i (j 1,m) j 1 xj 0 (j 1,n) hay dưới dạng ma trận: f(x) ct 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 x1 x2 x4 6 2x2 9x3 3x4 4 5x1 x2 7x3 2 x1, x2 , x3, x4 0 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 54 Tổ môn kế toán
Giáo trình toán kinh tế x1 x2 x4 6 2x2 9x3 3x4 x5 4 5x1 x2 7x3 x6 2 x1, x2 , x3, x4 , x5 , x6 0 - Dạng chuẩn tắc: f(x) = - 2x1 + 3x2 - 4x3 + 5x4 -> min x1 x2 x4 6 x1 x2 x4 6 2x2 9x3 3x4 4 5x x 7x 2 1 2 3 x1, x2 , x3, x4 0 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: a11 a 12 a 1n a a a A = 21 22 2n am1 a m2 a mn 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. 55 Tổ môn kế toán
Giáo trình toán kinh tế Để đơ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 k ạ tính, suy ra tồn tại các số z1, z2, , zk không đồng thời bằng 0 để  zj a 0. Đặt aj 1 t z = (z1, z2, , zk, 0, 0) 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 - 1 1 z => x = x' x'' suy ra trái với giả thiết x là phương án cực biên. 2 2 Đ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 x' x'' biên, suy ra x’, x’’ D, x’ x’’ sao cho x = . Ta có (n-k) thành phần của 2 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. k k k j ' j '' j Vậy xj a  x j a  x j a aj 1 aj 1 aj 1 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 56 Tổ môn kế toán
Giáo trình toán kinh tế 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 x0 với cơ sở J (tức là hệ véctơ cột độc lập j tuyến tính a,jJ;J   J x j,xj 0. Ta có: n 0 0 j 0 j Ax b hay b  xj a  x j a 1 j 1 j J 0 k ( vì xj 0;  j J). Với mỗi k J, ta biểu diễn véctơ a qua các véctơ cơ sở aj , j J . k j a  zjk a  k J j J Giả xử x D là một phương án bất kỳ. Ta có. k j j k j k j b = xj a  x j a  x k a  x j a  x  z jk a (2) j1 jJ kJ jJ kJjJ Vì {aj, j J} là độc lập tuyến tính nên từ (1) và (2) ta có: 0 x j = xj +  zjk x k (j J) k J hay 0 xj = x j -  zjk x k (j J) (3) k J 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 f x c x  cj x j  c j x j  c k x k j 1 j J k J Thay (3) vào ta được: 57 Tổ môn kế toán
Giáo trình toán kinh tế 0 f x  xj  z jk x k c j  c k x k j J k J k J 0 cj x j   z jk c j c k x k j J k J j J Ký hiệu: k = zjk c j c k (k J) j J Gọi là ước lượng của véc tơ cột ak theo cơ sở J và: 0 f(x) = f(x ) -  kx k j J 0 Nhận xét: do x ≥ 0 nên nếu k J, 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: 0 Nếu j J, j s 1 x j =  Nếu j s (*) 0 xj  z js 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 0 x j - zjs 0 j J mà zjs > 0. x0 Giả sử cực tiểu trên đạt tại j = r. Lấy  = r , thay vào (*) ta được: zrs 58 Tổ môn kế toán
Giáo trình toán kinh tế 0 Nếu j J, j s x0 1 r x j = Nếu j s ( ) zrs 0 0 xr xj Nếu j J zrs 0 1 0 xr f(x ) = f(x ) - s. ( ) zrs x0 Phương án x1 nhận được ở ( ) thực sự tốt hơn x0 nếu r > 0. Điều này thấy zrs 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. 1 + 1 1 Chứng minh: Theo ( ) suy ra x r = 0 nên J (x )  J . Ta cần chứng minh j j 1 hệ véc tơ {a , j J } độc lập tuyến tính. Thật vậy, giả sử aj x = 0 ta cần chứng j J1 1 minh j = 0  j J . Ta có: j j s j j 0 = aj x =  ja s a  j a s  z js a j J1 j J,j r j J,j r j J j r =  ( j s z js )a s z rs a j J,j r Vì hệ véc tơ {aj, j J} là độc lập tuyến tính, nên suy ra: j sz js 0  j J,j r sz rs 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. 59 Tổ môn kế toán
Giáo trình toán kinh tế 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 x1 cùng với giá trị hàm mục tiêu f(x1 ) thông qua các hệ số khai triển z jk và các ước lượng k trong cơ sở J. Để có thể tiến hành các bước tiếp 1 1 1 theo ta cần xác định các đại lương tương ứng z jk và k trong cơ sở mới J . 1 k Theo định nghĩa z jk và z jk là các hệ số khai triển của véctơ a tương ứng với cơ sở J, J1. k j 1 j 1 a  zajk  za jk J J\r  s (1) j J j J1 j j r zjk a  z jk a z jk a (2) j J j J1 ,j r s j j r Từ a  zajs  zazavi`z js rs rs 0 j J j J1 ,j r r1 s j Ta có a a  zjs a thay vào (2) ta được : zrs j J,j r j jzrk s j zjk a  z jk a a  z js a jJ jJ,jr zrs jJ,jr zrk j z rk s  zjk z js a a j J,j r zrs z rs Vì {aj, j J1} độc lập tuyến tính nên từ (1) và (2) suy ra: zrk nếu j=s 1 zrs z jk z z rk z nếu j J, j r jk js zrs 1 1 zrk z rk k z jk c j c k  z jk z js c j c s c k 1 j J j J,j r zrs z rs zrk z rk  zjk z js c j c s c k 1 j J zrs z rs zrk ( Vì với j=r thì zjk z js 0 ) zrs 60 Tổ môn kế toán
Giáo trình toán kinh tế 1 zrk z rk zjk c j c k  z js c j c s k s 1 j J zrs j J z rs 1 zrk Vậy k k s zrs 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: 0 a. Nếu k 0  k J thì x 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 k J mà k > 0 thì kiểm tra các hệ số khai triển zjk của cột a 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 s Chọn a đư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 0  xr x j  = min , z js 0 xrs z js  1 1 1 1 1 + Bước 4: Tính các x j, f(x ), k, z jk trong cơ sở mới J = (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: 61 Tổ môn kế toán
Giáo trình toán kinh tế Phương 1 2 k n Cơ sở J cj án xj c1 c2 ck 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 phương án x đ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 0  xr x j  = min , z js 0 zrs z js  Ví dụ 1: f(x) = x1 - x2 - 2x4 + 2x5 - 3x6 min x1 x4 x5 x6 2 x2 x4 x6 12 x 2x 4x 3x 9 3 4 5 6 x j 0 ( j 1,6) 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: 62 Tổ môn kế toán
Giáo trình toán kinh tế 1 2 3 4 5 6 J c x j j 1 -1 0 -2 2 -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ở: 4 Chọn chỉ số s: 4 = max { 4 = 2; 6 = 1}. Chọn cột 4 làm cột xoay (đưa a vào cơ sở). 2 12 9  2 x Chọn chỉ số r:  = min ,,  1 => r = 1 chọn hàng 1 làm hàng 1 1 1  1 z14 1 xoay (đưa a 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: 1 2 3 4 5 6 J c x j j 1 -1 0 -2 2 -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 63 Tổ môn kế toán
Giáo trình toán kinh tế x1 x 2 x 4 x 6 15 2x1 x 3 2x 6 9 (1) 4x1 2x 4 x 5 3x 6 2 xj 0(j 1, 6) Đổi dấu để có vec tơ đơn vị : Xét bài toán : g(x) = 6x1 + x2 + x3 + 3x4 +x5 -7x6 min. x1 x 2 x 4 x 6 15 2x1 + x 3 2x 6 9 (2) 4x1 2x 4 x 5 3x 6 2 xj 0(j 1, 6) 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 1 15 -1 1 0 -1 0 01 3 1 9 -2 0 1 0 0 -2 5 1 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 -7 15 -1 1 0 -1 0 1 3 1 39 -4 2 1 -2 0 0 5 1 47 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 64 Tổ môn kế toán
Giáo trình toán kinh tế 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 f(x)  cj x j min j 1 n (I) aij x j b i (i 1,2, ,m) D: j 1 xj 0(j 1,2, ,n) 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 : f(x) un 1 u n 2 u n 3 u n m min n aij x j u n i b i (i 1,2, ,m) j 1 (P) D' : xj 0(j 1,2, ,n) un i 0(i 1,2, ,m) Các biến un i 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 . 65 Tổ môn kế toán
Giáo trình toán kinh tế ( 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 . 66 Tổ môn kế toán
Giáo trình toán kinh tế 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 : f(x) 3x1 x 2 3x 3 x 4 min x1 2x 2 x 3 x 4 2 2x1 6x 2 3x 3 3x 4 9 (I) x x x x 6 1 2 3 4 xj 0(j 1,2,3,4) 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 67 Tổ môn kế toán
Giáo trình toán kinh tế 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 68 Tổ môn kế toán
Giáo trình toán kinh tế 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 . f(x) 2x1 4x 2 2x 3 min x1 2x 2 x 3 27 2x1 x 2 2x 3 50 (I) x x x x 18 1 2 3 4 xj 0(j 1,2,3,4) Xét bài toán quy hoạch tuyến tính phụ sau : f(x) u5 u 6 min x1 2x 2 x 3 u 5 27 2x1 x 2 2x 3 u 6 50 x x x x 18 1 2 3 4 xj 0(j 1,2,3,4);u 6 ,u 5 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 69 Tổ môn kế toán
Giáo trình toán kinh tế 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 f(x) 3x1 x 2 3x 3 max x1 2x 2 x 3 2 10x2 5x 3 5 3x 2x 4 2 3 xj 0 (j = 1,3) Lời giải Chuyển về bài toán dạng chính tắc : g(x) 3x1 x 2 3x 3 min x1 2x 2 x 3 2 10x2 5x 3 5 3x 2x 4 2 3 xj 0 (j = 1,3) Xét bài toán phụ : g(x,u) u4 u 5 min x1 2x 2 x 3 2 10x2 5x 3 u 4 5 3x 2x u 4 2 3 5 xj 0 (j = 1,3)u 4 ,u 5 0 70 Tổ môn kế toán
Giáo trình toán kinh tế 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 71 Tổ môn kế toán
Giáo trình toán kinh tế 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 f(x)  cj x j min j 1 Với các điều kiện : n aij x j b i : i=1, ,m 1 j 1 n aij x j b i : i m 1 1, ,m j 1 với các ràng buộc về dấu: xj 0 (j 1,n1 ) xj dấu tự do (j n 1 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) ct x min bt y max n i=1, ,m1 yi 0( i=1, ,m1 ) aij x j b i j 1 n i m1 1, ,m yi có dấu tự do aij x j b i j 1 i m1 1, ,m m xj 0 j 1,n1 aij y i c j với j 1,n1 i 1 x dấu tự do m j j n1 1,n aij yj c j với j n1 1,n i 1 72 Tổ môn kế toán
Giáo trình toán kinh tế Ví dụ 1 : Tìm bài toán đối ngẫu với bài toán gốc sau : f(x) 5x1 x 2 2x 3 3x 4 6x 5 min 3x1 x 2 2x 3 3x 4 4x 5 80 x1 x 2 x 3 x 4 x 5 10 3x1 2x 2 2x 3 x 4 x 5 30 x x 6 1 3 x1 0;x 2 ,x 3 0;x 4 ,x 5 dấu tự do Lời giải: Theo bảng ta có bài toán đối ngẫu như sau : g(y) 80y1 10y 2 30y 3 6y 4 max 3y1 y 2 3y 3 y 4 5(do x 1 0) y1 y 2 2y 3 1( do x 2 0) 2y y 2y y 2( do x 0) 1 2 3 4 3 3y1 y 2 y 3 3(do x 4 tự do) 4y1 y 2 y 3 6(do x 5 tự do) y tự do (do ràng buộc 1 ở bài toán gốc là :’ ’) 1 y2 0 (do ràng buộc 2 ở bài toán gốc là :’ ’) y3 ,y 4 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: f(x) 2x1 3x 2 x 3 x 4 max 2x1 x 2 x 3 x 4 5 x1 x 2 2x 3 x 4 7 5x1 x 2 3x 3 x 4 20 x1 ,x 2 0,x 3 0,x 4 tự do. Ta có bài toán đối ngẫu : 73 Tổ môn kế toán
Giáo trình toán kinh tế g(y) 5y1 7y 2 20y 3 min 2y1 y 2 y 3 2( do x 1 0) y1 y 2 y 3 3( do x 2 0) y 2y 3y 1( do x 0) 1 2 3 3 y1 y 2 y 3 1( do x 4 tự do ) y 0(do ràng buộc 1 trong bài toán gốc là" ") 1 y2 tự do (do ràng buộc 2 trong bài toán gốc là" ") y3 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. Bài toán gốc Bài toán đối ngẫu f(x) ct x min g(y) bt y max Ax b (P) At y c (Q) x 0 y tự do Đị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 : 74 Tổ môn kế toán
Giáo trình toán kinh tế +, 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: f(x) x2 x 3 2x 5 min 1 x x x 2x 7 12 2 3 5 2x 4x x 12 2 3 4 4x2 3x 3 8x 5 x 6 10 x 0 j 1,6 j Đá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: f(x) 2x1 5x 2 4x 3 x 4 5x 5 min x1 6x 2 2x 4 9x 5 32 1 3 2x2 x 3 x 4 x 5 30 2 4 3x2 x 5 36 x 0 j 1,5 j Đáp số: x 32,0,30,0,0 ; f x 184 75 Tổ môn kế toán
Giáo trình toán kinh tế 3) Giải bài toán quy hoạch tuyến tính sau: f(x) 2x1 6x 2 4x 3 2x 4 3x 5 max x1 2x 2 4x 3 52 4x 2x x 60 2 3 4 3x x 36 2 5 x 0 j 1,5 j 34 22 400 Đáp số: x 0, , ,0 ; f x 3 3 3 4) Giải bài toán quy hoạch tuyến tính sau: f(x) x1 2x 2 x 3 min x1 x 2 2x 3 2 x x x 1 1 2 3 x2 x 3 5 2x x 2 1 2 xj 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: f(x) 16x1 7x 2 9x 3 min 2 1 1 x x x 31 3 2 3 3 5x 5x 7 1 2 x 0 j 1,2,3 j 7 22 Đáp số: x 0, , ; f x 23 5 15 76 Tổ môn kế toán
Giáo trình toán kinh tế 6) Giải bài toán quy hoạch tuyến tính sau: f(x) 3x1 2x 2 max 2x1 x 2 5 x1 x 2 1 x1 x 2 3 xj 0 j 1,2 7) Giải bài toán quy hoạch tuyến tính sau: f(x) 5x1 x 2 6x 3 2x 4 max 4x1 4x 2 4x 3 x 4 44 8x1 6x 2 4x 3 3x 4 36 xj 0 j 1,2,3,4 8) Giải bài toán quy hoạch tuyến tính sau: f(x) 2x1 x 2 x 3 x 4 min x1 x 2 2x 3 x 4 2 2x1 x 2 3x 3 x 4 6 x1 x 2 x 3 x 4 7 xj 0 j 1,2,3,4 9) Giải bài toán quy hoạch tuyến tính sau: f(x) x1 x 2 x 3 x 4 x 5 x 6 min x1 x 4 6x 6 9 3x1 x 2 4x 3 2x 6 2 x1 2x 3 x 5 2x 6 6 xj 0 j 1,2,3,4,5,6 77 Tổ môn kế toán
Giáo trình toán kinh tế 10) Giải bài toán quy hoạch tuyến tính sau: 1 f(x) 2x 3x x x min 1 2 32 4 1 x x x x 9 1 2 32 4 x 4x 8x 4 2 3 4 2x2 2x 3 3x 4 10 x 0 j 1,4 j Đá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: 9 f(x) 2x 7x 5x x min 1 2 32 4 x1 x 2 x 3 3x 4 14 x 4x x 8 2 3 4 x 2x 3x 20 2 3 4 x 0 j 1,4 j Đá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: f(x) x1 x 2 2x 3 3x 4 4x 5 x 6 min 3 x x 2x x x 40 12 2 5 6 7 2x x x 3x x 10 2 3 5 6 7 1 x2 x 4 x 5 2x 6 x 7 60 2 x 0 j 1,7 j Đáp số: Bài toán không có lời giải 78 Tổ môn kế toán
Giáo trình toán kinh tế 11) Giải bài toán quy hoạch tuyến tính sau: f(x) 2x1 x 2 x 3 6x 4 max x1 2x 2 4x 3 x 4 9 3x1 2x 2 x 3 4 5x1 3x 2 x 4 1 xj 0 ;  j 3;x 3 0 Đáp số: x 0,0,2,1,0,6 ; f x 8 o0o 79 Tổ môn kế toán
Giáo trình toán kinh tế 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 B j (j=1,2 n ) tiêu thụ loại hàng đó với khối lượng tương ứng là: bj ( 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 ai  b j i 1 j 1 đượ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 B j là cij đơ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 xij là số đơn vị hàng chuyển từ điểm phát Ai đến điểm thu B j Tổng lượng hàng xuất phát từ điểm phát Ai tới mọi điểm thu B j là ai khi đó : n xij a i i = 1,2 m j 1 Tổng lượng hàng thu về điểm thu B j từ mọi điểm phát Ai là bj khi đó : 80 Tổ môn kế toán
Giáo trình toán kinh tế n xij b j j = 1,2 n. i 1 Tổng cước phí phải trả là : m n cij x ij i 1 j 1 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 cij x ij min i 1 j 1 n xij a i i = 1,2 m (1) j 1 n xij b j j = 1,2 n. (2) i 1 xij ≥ 0 (i = 1,2 m ; j = 1,2 n ) (3) Ma trận X = (xij ) m x n thoả mãn (1) , (2) , (3), được gọi là một phương án m n của bài toán vận tảI và nếu nó làm cho cij x ij đạt giá trị nhỏ nhất thì gọi là i 1 j 1 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 xij 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 : m n Điều kiện cân bằng thu phát ( ai  b j ) là điều kiện cần và đủ để bài i 1 j 1 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 = (xij ) khi đó : n * xij a i i = 1,2 m j 1 81 Tổ môn kế toán
Giáo trình toán kinh tế n * xij b j j = 1,2 n. i 1 Vì vậy : m m n n m n ai  x ij  x ij  b j i1 i1j1 j1i1 j1 m n Ngược lại , giả sử ta có ai  b j , ta cần chứng minh bài toán vận tảI có i 1 j 1 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 . m n ai b j Thật vậy : ta đặt Q = ai  b j > 0 , xét vec tơ X ( ) i = 1,m;j 1,n i 1 j 1 Q a b có thành phần x i j . ij Q Ta có n n n ai b j b j xij  a i  a i i = 1, . . .m. j 1 j 1QQ j 1 m ma b m i j ai xij  b j  b j j = 1, n . i 1 i 1QQ i 1 Và rõ ràng xij ≥ 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 n cij x ij 0 với c ij 0 và xij a i suy ra 0 xij a i vì vậy j 1 cij x ij c ij a i với c ij 0 suy ra cij x ij min {0 , cij ai } i= 1.2 m ; j = 1,2, n . m n m n Do đó f(x) = cij x ij ≥ min{0,cij a i } = const . Vậy hàm mục tiêu bị i 1 j 1 i 1 j 1 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 : 82 Tổ môn kế toán
Giáo trình toán kinh tế B j b1 b1 bj bn Ai c11 c12 c c1n a1 2 j x11 x12 x1n x2j c21 c22 c c2n a2 2 j x21 x22 x2n x2j ci1 ci2 c cin ai ij xi1 x11 xin xij cm1 cm2 c cmn am mj xm1 xm2 xmn xmj 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 b j ( j = 1 n ) , cột đầu tiên ghi các ai (i = 1 m) . 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 B j 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 cij vào góc trên phía trái và lượng vận chuyển xij 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 xij > 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 . 83 Tổ môn kế toán
Giáo trình toán kinh tế Ví dụ 1 : Trong bảng : B j b1 b2 b3 Ai 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 : B j b1 b2 b3 b4 Ai 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 . 84 Tổ môn kế toán
Giáo trình toán kinh tế 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 : cij  c ij (4) (i,j)V (i,j)V Xây dựng vec tơ X = (xij ) theo công thức : 85 Tổ môn kế toán
Giáo trình toán kinh tế x  nếu (i, j) V ij xij x ij  nếu (i, j) V (5) x nếu (i, j) V ij - Trong đó  = min { xij , (i,j) V Rõ ràng xij ≥ 0  (i,j) , ngoài ra do V là vòng nên từ (5) ta có : n n xij  xij a i (i = 1,m) j 1 j 1 m m xij  xij b j (j = 1,n) i 1 i 1 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 f(X)  cxij ij  cx ij ij  (  c ij  c) ij i 1 j 1 i 1 j 1 (i,j) V (i,j) V m n cij x ij f(X) i 1 j 1 Từ (5) và cách xác định  nên sẽ có ít nhất một ô (i , j ) V để  = x , 0 0 i0 j 0 do đó x =0 , và ô (i , j ) V sẽ không là ô chọn nữa . i0 j 0 0 0 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 . 86 Tổ môn kế toán
Giáo trình toán kinh tế 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 87 Tổ môn kế toán
Giáo trình toán kinh tế 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 88 Tổ môn kế toán
Giáo trình toán kinh tế 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 ai , b j , c ij ( 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à : ,,,, ai a i (i 1) , a 1 a 1 x 11 , b j b j (j 1), b 1 b 1 x 11 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à ai (i 2,m);b(j 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 : 89 Tổ môn kế toán
Giáo trình toán kinh tế B j B1:20 B2:40 B3:30 Ai A1: 30 1 3 5 20 10 A2: 25 5 4 2 25 A3: 35 8 5 4 5 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 = ( cij ) mxn 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à : ar nếu a r b s (*) xij bs nếu a r >b s ( ) 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ụ : 90 Tổ môn kế toán
Giáo trình toán kinh tế 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 : B j B1:20 B2:40 B3:30 Ai A1: 30 1 3 5 20 10 A2: 25 5 4 2 25 A3: 35 8 5 4 5 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 = (cij ) mxn một số ri tuỳ ý (i = 1 m) và cộng vào cột j củ nó mọt số tuỳ ý sj ( j = 1 n) thì ta có bài toán vận tảI mới với ma trận cước phí C (cij ) mxn trong đó (cij ) (c ij ) r i s j 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à : 91 Tổ môn kế toán
Giáo trình toán kinh tế m n m n f (X)  cij x ij  (c ij r i s j )x ij i 1 j 1 i 1 j 1 m n m n n m cij x ij  r i  x ij  s j  x ij i1j1 i1j1 j1i1 m n f(X)  ri a i  s j b j i 1 j 1 f(X) C m n Trong đó C = ri a i  s j b j là một hằng số . i 1 j 1 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í (cij ) mxn một số ri i=1 m và cộng vào cột j của nó số sj ( 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 cij = 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 + . 92 Tổ môn kế toán
Giáo trình toán kinh tế V - : các ô được đánh dấu - . 4. Tìm các ô đưa ra và lượng điều chỉnh : Giả sử min { xij : (i, j) V } = xi0 j 0 0 0 khi đó ( i j ) là ô đưa ra và xi0 j 0 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 X (xij ) mxn được tiính như sau : + x x0 0 nếu (i,j) V ij i j - xij x ij xi0 j 0 nếu (i,j) V xij (i,j) nếu V Nhận xét : 0 0 x x +) Ô ( i j ) trước có i0 j 0 đơn vị hàng và ở ô đánh dấu trừ nên bị trừ đI i0 j 0 đơ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 xi0 j 0 đơn vị hàng thành ô chọn . +) X (xij ) mxn 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 n  x i j và  x i j i 1 j 1 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 : 93 Tổ môn kế toán
Giáo trình toán kinh tế B j B1:20 B2:40 B3:30 Ai 1 3 5 A1: 30 20 10 5 4 2 A2: 25 25 8 5 4 A3: 35 5 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ố sj ( 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à sj đó ta cần giải hệ phương trình : 1 r1 s 1 0 2 r s 0 1 2 3 r2 s 3 0 5 r s 0 3 2 4 r3 s 3 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à : B j B1:20 B2:40 B3:30 Ai 0 0 3 A : 30 1 20 10 4 1 0 A2: 25 25 5 0 0 A3: 35 5 30 94 Tổ môn kế toán
Giáo trình toán kinh tế 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. B j B1:80 B2:20 B3:60 Ai 5 4 1 A1: 50 50 3 2 6 A2: 40 20 20 7 9 11 A3: 70 60 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ố sj (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 r1 s 3 0 3 r s 0 2 1 2 r2 s 2 0 7 r s 0 3 1 11 r3 s 3 0 95 Tổ môn kế toán
Giáo trình toán kinh tế Đâ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 : x23 x23 10 0 10 10 x31 x 10 60 10 70 31 x33 x33 10 10 10 0 x21 x21 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 : 0 r1 s 3 0 0 r s 0 2 1 0 r2 s 2 0 1 r s 0 3 1 0 r3 s 3 0 96 Tổ môn kế toán
Giáo trình toán kinh tế Cho r2 0 ta được s1 = 0,s2 = 0, s3 = 1, r1 =-1 , r3 = 0 7 7 0 Ta có ma trận cước phí mới là : 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. n m Đó là bài toán vận tải mà điều kiện cân bằng thu phát ai  b j không được i 1 j 1 n m thoả mãn. Khi đó có 2 khả năng xảy ra: hoặc ai  b j (tức là tổng lượng i 1 j 1 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 ai  b j . Ta xét từng trường hợp: i 1 j 1 n m a. Nếu ai  b j : i 1 j 1 Ta đưa thêm vào điểm thu giả Bn 1 với lượng hàng thu tương ứng n m bn 1  a i  b j 0 và xét bài toán vận tải với m điểm phát và n+1 điểm i 1 j 1 thu: 97 Tổ môn kế toán
Giáo trình toán kinh tế m n 1  cij x ij min i 1 j 1 n 1  xij a i j 1 m xij b j i 1 x 0i 1,m;j 1,n 1 ij c 0; i 1,m in 1 n 1 n n m n m Rõ ràng bj  b j b n 1  b j  a i  b j  a i j1 j1 j1 i1 j1 i1 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 X xij i 1,m; j 1,n 1 . Nếu xin 1 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à xin 1 . n m b. Nếu ai  b j : i 1 j 1 Ta đưa them biến phát giả Am 1 với lượng phát tương ứng là: m n am 1  b j  ai 0 j 1 i 1 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  cij x ij min i 1 j 1 n xij a i i 1,m 1 j 1 m 1  xij b j j 1,n i 1 x 0 i 1,m 1;j 1,n ij c 0; j 1,n m 1j 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 98 Tổ môn kế toán
Giáo trình toán kinh tế X xij i 1,m 1;j 1,n . Nếu xm 1j 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à xm 1j . 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: B j B1:20 B2:40 B3:60 Ai 3 4 1 A1: 80 4 2 3 A2: 30 1 5 6 A3: 50 3 3 Vì ai 80 30 50 160,  b j 20 40 60 120 ta có trường hợp thứ j 1 j 1 nhất. Đưa thêm điểm thu giả B4 với lượng hàng cần thu b4 160 120 40. Ta có bảng vận tải: B j B1:20 B2:40 B3:60 B4 : 40 Ai 3 4 1 0 A1: 80 X . X -7 -4 0  0  40 4 2 3  0  A2: 30 X   -6 0 30 0  2  1 5 6  0  A3: 50 X X X X 0 20 0 10 0 20 5 99 Tổ môn kế toán
Giáo trình toán kinh tế 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ị ui i 1,2,3 ;v j j 1,2,3,4 bằng cách giải hệ phương trình: u1 v 3 1 u v 0 2 4 u2 v 2 2 u3 v 1 1 u v 5 3 2 u3 v 3 6 Cho u1 0 ta được u2 2 , u3 5, v1 4, v2 0, v3 1, v 4 0 + Tính các ij u i v j c ij ta co : 7 4 0 0 11 12 13 14 21 6 22 0 23 0 24 2 31 0 32 0 33 1 34 5 Ô đưa vào là ô (3,4) vì 34 max ij , ij 0. + Có vòng V 3,4 ,3,3 ,1,3 ,1,4  V 3,4 ,1,3  ;V 3,3 ,1,4  min x33 ,x 13 min 20,40 20 x 33 Ô đưa ra là ô (3,3). + Phương án mới: X xij co x ij  i, j V. x33 x 33 20 20 20 0 ; x 14 40 20 20 x34 0 20 20 Ta có bảng tương ứng với phương án X 100 Tổ môn kế toán
Giáo trình toán kinh tế B j B1:20 B2:40 B3:60 B4 : 40 Ai 3 4 1 0 A1: 80 X . . X . X -2 1  0 60 0  20 4 2  3 0  A2: 30 X  -6 0  30 -5 -3  1 5  6 0  A3: 50 X X . . . X 0 20 0 10 -6 0 Lặp lại quá trình trên với X= X +Tìm các thế vị ui i 1,3;v j j 1,4 bằng cách giải hệ phương trình: u1 v 3 1 u v 0 1 4 u2 v 2 2 u3 v 1 1 u v 5 3 2 u3 v 4 0 Cho u1 0 ta được u2 3, u3 0, v1 1, v2 5, v3 1, v 4 0 + Tính các ij u i v j c ij ta co : 2 1 0 0 11 12 13 14 216 22 0 23 5 24 3 31 0 32 0 33 6 34 0 Ô đưa vào là ô (1,2) vì 12 1 0. 101 Tổ môn kế toán
Giáo trình toán kinh tế + Có vòng V 1,2 ,1,4 ,3,4 ,3,2  V 1,2 ,3,4  ;V 1,4 ,3,2  min x14 ,x 32 min 20,10 10 x 32 +Phương án mới: X xij co x ij  i, j V. x12 0 10 10 ; x 14 20 10 10 x32 10 10 0 ; x 34 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à: B j B1:20 B2:40 B3:60 B4 : 40 Ai 3 4 1 0 A1: 80 X X X 10 60 10 4 2 3 0 A2: 30 X 30 1 5 6 0 A3: 50 X X 0 20 30 Xác định các thế vị bàng cách giải hệ phương trình: 102 Tổ môn kế toán
Giáo trình toán kinh tế u1 v 2 4 u v 1 1 3 u1 v 4 0 u2 v 2 2 u v 1 3 1 u3 v 4 0 Cho u1 0 ta được u2 2 , u3 0 , v1 1, v2 4 , v3 1, v 4 0 + Tính các ij u i v j c ij ta co : 2 0 0 0 11 12 13 14 215 22 0 23 4 24 2 31 0 32 1 33 5 34 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. 103 Tổ môn kế toán
Giáo trình toán kinh tế 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 B1 : 60 B2 : 70 B3 : 40 B4 : 30 Ai 2 1 4 3 A1 :100 5 3 2 6 A2 :80 6 2 1 5 A3 : 20 60 10 0 30 Đáp số: 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: 1 5 6 2 t a) a 50,80,30 ; b 20,40,60,30 ; C 3 4 1 7 4 2 3 5 20 0 50 0 0 Đáp số: x 0 40 0 30 10 20 0 10 0 0 7 6 5 t b) a 25,10,45 ; b 10,30,50 ; C 2 1 4 3 5 2 0 20 5 Đáp số: x 0 10 0 10 0 35 104 Tổ môn kế toán
Giáo trình toán kinh tế 3.Trong vụ bão lụt vừa qua có 5 điểm B,B,B,B,B1 2 3 4 5 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 A,A,A,A1 2 3 4 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 B1 :10 B2 :10 B3 :10 B4 : 20 B5 : 20 Ai 5 1 4 6 7 A1 : 5 3 4 2 7 8 A2 :15 4 3 1 7 9 A3 : 20 6 5 4 9 11 A4 : 30 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. 0 5 0 0 0 10 0 0 0 5 Đáp số: 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 B,B,B,B,B1 2 3 4 5 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 A,A,A,A1 2 3 4 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 B1 : 20 B2 :100 B3 :145 B4 : 30 B5 :150 Ai 6 3 1 4 5 A1 :120 1 2 5 4 3 A2 :150 2 4 3 1 6 A3 :150 3 1 4 2 7 A4 : 25 105 Tổ môn kế toán
Giáo trình toán kinh tế 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. 0 0 120 0 0 0 0 0 0 150 Đáp số: 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 B1 : 70 B2 : 20 B3 : 60 B4 : 80 Ai 15 12 6 3 A1 : 40 12 9 6 8 A2 : 70 12 9 9 18 A3 :120 6.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj B1 : 30 B2 :15 B3 : 20 B4 :15 Ai 3 4 2 6 A1 : 25 5 1 6 2 A2 :15 2 1 5 3 A3 : 40 7.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj B1 :180 B2 : 200 B3 : 230 B4 : 280 Ai 4 2 10 6 A1 : 280 1 3 8 12 A2 : 320 5 3 9 7 A3 : 290 106 Tổ môn kế toán
Giáo trình toán kinh tế 9.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj B1 : 5 B2 :15 B3 : 20 B4 :10 Ai 2 1 4 3 A1 :10 6 0 5 2 A2 : 25 1 4 8 2 A3 :15 8.Giải bài toán vận tải với các dữ liệu cho trong bảng sau: Bj B1 : 30 B2 : 25 B3 : 40 B4 : 25 Ai 3 4 2 6 A1 : 20 5 1 6 2 A2 : 45 2 1 5 3 A3 : 55 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 B1 : 60 B2 : 30 B3 : 30 Ai 1 4 5 A1 : 80 4 6 4 A2 : 50 6 4 3 A3 : 40 107 Tổ môn kế toán
Giáo trình toán kinh tế 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 B1 : 60 B2 : 85 B3 : 45 Ai 12 5 7 A1 : 55 4 9 11 A2 :80 8 13 2 A3 : 75 108 Tổ môn kế toán
Giáo trình toán kinh tế Mục lục Lời nói đầu Trang Chương I : Đại số tuyến tính. 4 Bài 1. Vectơ n chiều 4 Bài 2. Hệ vectơ độc lập tuyến tính, phụ thuộc tuyến tính 5 Bài 3. Ma trận 6 Bài 4. Định thức của ma trận 12 Bài 5. Ma trận nghịch đảo 15 Bài 6. Hệ phương trình tuyến tính 16 Bài tập ôn tập chương I 20 Chương II: Xác suất. Bài 1. Giải tích tổ hợp 23 Bài 2. Biến cos ngẫu nhiên và xác suất 25 Bài 3. Các định nghĩa xác suất 28 Bài 4. Xác suất có điều kiện, công thức nhân, xác suất 32 toàn phần, công thức Bayes Bài 5. Công thức Becnulli 38 Bài tập ôn tập chương II 44 Chương III: Quy hoạch tuyến tính. Bài 1. Mở đầu 51 Bài 2. Phương pháp đơn hình 57 Bài 3. Bài toán quy hoạch tuyến tính đối ngẫu 71 Bài tập ôn tập chương III 75 Chương IV: Bài toán vận tải. Bài 1. Thiết lập BTVT 79 Bài 2. Tìm phương án cơ sở xuất phất 87 90 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 96 Bài tập ôn tập chương IV 101 109 Tổ môn kế toán
Giáo trình toán kinh tế 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 110 Tổ môn kế toán