Giáo trình Toán kinh tế (Phần 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ơ 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ổ