Chương III Mô hình tối ưu tuyến tính (QHTT)

CHƯƠNG III MÔ HÌNH TỐI ƯU TUYẾN TÍNH (QHTT) I. Thí dụ mở đầu II. Mô hình bài toán QHTT III. Các tính chất chung của bài toán QHTT IV. Phương pháp đơn hình V. Bài toán đối ngẫu I. Thí dụ mở đầu • Thí dụ 1: Bài toán lựa chọn danh mục đầu tư - Nội dung: Một công ty đầu tư dự định dùng khoản quỹ đầu tư 500 tỷ đồng để mua một số cổ phiếu trên thị trường chứng khoán. Để phòng ngừa rủi ro công ty đưa ra các yêu cầu về đa dạng hoá danh mục đầu như sau: + Loại cổ phiếu và giới hạn mua: + Tỷ lệ đầu tư vào cổ phiếu A và C phải chiếm ít nhất 55% và cổ phiếu B phải chiếm ít nhất 15% tổng số vốn đầu tư thực hiện - Bài toán: Với số tiền dự kiến đầu tư, hãy xác định một danh mục đầu tư sao cho đảm bảo về đa dạng hoá danh mục đầu tư và đem lại mức lợi tức lớn nhất. Loại CK Lợi tức Giới hạn mua A 7%/năm 100 tỷ B 8,5%/năm 300 tỷ C 7,8%/năm 250 tỷ D 8,2%/năm 320 tỷ - Mô hình hoá: + Gọi xA, xB, xC, xD là các khoản tiền đầu tư vào các loại chứng khoán A, B, C, D + Các điều kiện về đa dạng hoá danh mục đầu tư: 0  xA  100; 0  xB  300 (1) 0  xC  250, 0  xD  320 (2) xA + xC  0,55(xA + xB+ xC + xD) (3) xB  0,15(xA + xB+ xC + xD) (4) xA + xB+ xC + xD  500 (5) + Mức lợi tức ứng với danh mục đầu tư: Z = 0,07xA + 0,085xB+ 0,078xC + 0,082xD (tỷ đồng) - Xác định x = (xA, xB, xC, xD) sao cho: Z  Max; với các điều kiện (1), (2), (3), (4), (5). - Bài toán này gọi là bài toán QHTT • Thí dụ 2: Bài toán vận tải - Nội dung: Một công ty kinh doanh xăng dầu tại khu vực Z hàng tuần cần cung ứng xăng cho 3 trạm bán lẻ A, B và C. Công ty có thể đưa xăng đến các trạm từ tổng kho I và II. Lượng xăng dự trù cung ứng cho các trạm của kho I là 20 tấn, kho II là 40 tấn. Nhu cầu tiêu thu xăng hàng tuần của các trạm A, B, C lần lượt là 20, 15, 15 (tấn). Chi phí cho việc cung ứng xăng được cho dưới bảng sau: Đơn vị: nghìn đồng/tấn - Bài toán: Cần lập một kế hoạch cung ứng xăng từ các kho đến các trạm để đảm bảo đáp ứng đủ nhu cầu của các trạm với tổng chi phí vận chuyển là nhỏ nhất. Kho\ Trạm A B C I 500 400 700 II 600 500 500 - Mô hình hoá: + Gọi x1A, x1B, x1C, x2A, x2B, x2C (tấn) lần lượt là các lượng xăng vận chuyển từ kho I, kho II đến các trạm A, B, C. + Điều kiện để đáp ứng đầy đủ nhu cầu của các trạm: x1A + x2A = 20 (1) x1B + x2B = 15 (2) x1C + x2C = 15 (3) + Điều kiện về lượng xăng dự trù cung ứng của các kho: x1A + x1B + x1C  20 (4) x2A + x2B + x2C  40 (5) + Tổng chi phí vận chuyển: Y = 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C (nghìn đồng) - Xác định x1A, x1B, x1C, x2A, x2B, x2C  0 sao cho: Y  Min; với các điều kiện (1), (2), (3), (4), (5) Bài toán này gọi là bài toán QHTT II. Mô hình bài toán QHTT 1. Bài toán dạng tổng quát 2. Một số khái niệm và định nghĩa 3. Các dạng đặc biệt 1. Bài toán dạng tổng quát - Là bài toán tìm cực trị (cực đại hoặc cực tiểu) của một hàm tuyến tính xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương và (hoặc) các bất phương trình tuyến tính. - Xác định véc tơ x = (x1, x2, …, xn) sao cho: 1 1 1 2 1 2 3 1 2 3 1 3 1 ( ) ( ) ( ) ( )(*) , ( ) n j j j n ij j i j n ij j i j n ij j i j f x c x Min Max a x b i I a x b i I I I I I I I I a x b i I                             2. Một số khái niệm và định nghĩa - Hàm f(x) cần tìm cực trị gọi là hàm mục tiêu của bài toán - Hệ (*) gọi là hệ điều kiện của bài toán - Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc của bài toán và hệ điều kiện còn gọi là hệ ràng buộc - Véc tơ x thoả mãn mọi ràng buộc của bài toán gọi là một phương án (PA) của bài toán - Tập hợp các PA có thể có của bài toán gọi là tập PA của bài toán, ký hiệu: D = {x: t/m (*)} - Xét bài toán QHTT có f(x)  Min và hai PA xA, xB. Khi đó: + Nếu f(xA)  f(xB) thì PA xA gọi là không xấu hơn PA xB + Nếu f(xA) < f(xB) thì PA xA gọi là tốt hơn PA xB - Một PA mà tại đó hàm mục tiêu đạt cực trị gọi là PA tối ưu (PATƯ), ký hiệu: x* và f* = f(x*) gọi là trị tối ưu, f(x*)  f(x) với mọi PA x của bài toán. - Một bài toán có ít nhất một PATƯ gọi là bài toán giải được - Một bài toán không có PA TƯ gọi là bài toán không giải được + Bài toán không có PA  không có PATƯ + Bài toán có PA nhưng hàm mục tiêu không bị chặn trên tập PA - Xét với PA x: + Nếu ràng buộc i (iI) thoả mãn với dấu “=“ thì PA x gọi là thoả mãn “chặt” ràng buộc i hay ràng buộc i là chặt đối với PA x + Nếu ràng buộc i (iI) thoả mãn với dấu “>” hoặc “<“ thì PA x gọi là thoả mãn “lỏng” ràng buộc i hay ràng buộc i là lỏng đối với PA x - Nếu một ràng buộc có dạng dấu “=“ thì nó là chặt với mọi PA của bài toán - Nếu một ràng buộc có dạng dấu ““ hoặc ““ thì nó có thể là lỏng đối với PA này nhưng lại là chặt đối với PA khác - Với ràng buộc i ta ký kiệu véc tơ A*i = (ai1, ai2,…, ain) và tập hợp các véc tơ A*i (iI) tạo thành một ma trận, ký hiệu: A* và gọi là ma trận hệ ràng buộc của bài toán - Gọi một nhóm các ràng buộc có hệ véc tơ A*i tương ứng độc lập tuyến tính gọi là các ràng buộc độc lập tuyến tính - Một PA thoả mãn chặt n ràng buộc độc lập tuyến tính gọi là PA cực biên (PACB) + PACB thoả mãn đúng n ràng buộc gọi là PACB không suy biến + PACB thoả mãn hơn n ràng buộc gọi là PACB suy biến - Một bài toán có tất cả các PACB đều không suy biến gọi là bài toán không suy biến - Một bài toán có ít nhất một PACB suy biến gọi là bài toán suy biến Ví dụ 1 1 2 1 2 1 2 1 2 ( ) 2 2 6 (1) 3 (2) 0 (3) 0 (4) f x x x M in x x x x x x              3. Các dạng đặc biệt 3.1. Bài toán dạng chính tắc - Xác định véc tơ x = (x1, x2, …, xn) sao cho: - Bài toán dạng chính tắc có một hệ phương trình ràng buộc và các biến số đều không âm + (1) là nhóm các ràng buộc dạng phương trình gọi là các phương trình ràng buộc + (2) là nhóm các ràng buộc dạng bất phương trình gọi là các ràng buộc về dấu đối với các biến 1 1 ( ) ( ) ( 1 ) (1) 0( 1 ) (2) n j j j n ij j i j j f x c x Min Max a x b i m x j n                - Ký hiệu: A = ((aij))mn gọi là ma trận điều kiện của bài toán Aj là véc tơ cột j của ma trận A- gọi là véc tơ điều kiện j c là véc tơ hệ số của các biến trong hàm mục tiêu b là véc tơ vế phải của hệ phương trình ràng buộc - Khi đó bài toán dạng chính tắc có thể viết dưới dạng hoặc 1 1 ( ) ( ) 0( 1 ) n j j j n j j j j f x c x Min Max x A b x j n              ( ) ( , ) ( ) 0 f x c x MinMax Ax b x      Mệnh đề - Mọi bài toán QHTT đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hai bài toán là như nhau và từ PATƯ của bài toán này có thể suy ra PATƯ của bài toán kia. - Các phép biến đổi tương đương như sau: + Nếu xj  0 thì đặt: xj’ = - xj  0 + Nếu xj không có ràng buộc về dấu thì đặt: + Nếu ràng buộc i có dạng thì biến đổi: + Nếu ràng buộc i có dạng thì biến đổi: ' '' ' '', 0 j j j j j x x x x x      1 n ij j i j a x b   1 0 n p ij j i i j p i a x x b x         1 n ij j i j a x b   1 0 n p ij j i i j p i a x x b x         Ví dụ 2 - Cho bài toán QHTT: - Đưa bài toán về dạng chính tắc tương đương 1 2 3 1 2 3 1 2 3 2 3 1 2 ( ) 2 3 2 6 (1) 4 10 (2) 4 (3) 0 (4) 0 (5) f x x x x M in x x x x x x x x x x                 Định lý 1 - PA x của bài toán dạng chính tắc là PACB khi và chỉ khi hệ thống các véc tơ {Aj: xj > 0} là độc lập tuyến tính - Ví dụ 3: Cho bài toán QHTT Chứng tỏ véc tơ x0 = (2, 1, 0) là PACB bằng hai cách 1 2 3 1 2 3 1 2 3 ( ) 2 4 6 3 4 4 10 (1) 4 1 (2) 0( 1 3)j f x x x x M in x x x x x x x j                   Nhận xét - Với bài toán dạng chính tắc, không làm mất tính chất tổng quát ta giả thiết hệ phương trình ràng buộc gồm m phương trình độc lập và m < n, tức là r(A) = m < n - Bởi vì: + Nếu m = n thì hệ phương trình ràng trở thành hệ Cramer, hệ này có tối đa một nghiệm nên việc tìm PATƯ trở thành không cần thiết + Nếu m > n thì bằng phép biến đổi tương đương ta có thể đưa về hệ chỉ có n phương trình và hệ này cũng là hệ Cramer - Từ định lý 1 ta thấy: + Một PACB có tối đa m thành phần dương (?) + Một PACB không suy biến có đúng m thành phần dương (?) + Một PACB suy biến có ít hơn m thành phần dương (?) Định nghĩa cơ sở của PACB - Xét bài toán dạng chính tắc và PACB x - Gọi m véc tơ {Aj} độc lập tuyến tính bao hàm hệ thống các véc tơ {Aj: xj > 0} là cơ sở của PACB x, ký hiệu một cách quy ước là J - Cơ sở J của PACB x bao hàm 3 nội dung: + Số phần tử của J là m + Hệ véc tơ {Aj: j  J} độc lập tuyến tính + {Aj: j  J}  {Aj: xj > 0} - Nếu PACB x không suy biến thì có một cơ sở duy nhất: {Aj: j  J}  {Aj: xj > 0} - Nếu PACB x suy biến thì có thể có nhiều cơ sở khác nhau mà phần chung của chúng là các véc tơ {Aj: xj > 0} - Với PACB x ta gọi: xj (j  J) gọi là thành phần cơ sở của PACB x: xj > 0  j  J xk(k  J) gọi là thành phần phi cơ sở của PACB x: k  J  xk = 0 3.2. Bài toán dạng chuẩn - Là bài toán dạng chính tắc có bi  0 (i) và mỗi phương trình ràng buộc đều có một biến với hệ số bằng 1 và không có mặt ở các phương trình khác. - Xác định véc tơ x = (x1, x2, …, xn) sao cho: - Bài toán dạng chuẩn cho ta PACB x0 = (b1, b2, …, bm, 0, …, 0) với cơ sở {Aj: j  J}  {ej: j = 1m} gọi là cơ sở đơn vị + Nếu bi > 0 (i) thì PACB x0 là PACB không suy biến + Nếu có ít nhất một bi = 0 thì PACB x0 PACB suy biến 1 1 1 1 1 1 2 1 1 2 2 1 1 2 1 ( ) ( ) ... ... ........................................ ............................ ... 0 ( 1 ) n j j j m m n n m m n n mm m mn nm m j f x c x M in M ax a x a x b a x a x b a x a x b x j x n x x                               Ví dụ 4 - Cho bài toán QHTT: - Đưa bài toán về dạng chính tắc và dạng chuẩn - Xác định một PACB của bài toán và cho biết tính chất của PACB 1 2 3 1 3 4 1 2 3 4 1 3 4 ( ) 2 5 3 2 3 12 (1) 2 2 4 (2) 3 4 8 (3) 0( 1 4)j f x x x x Max x x x x x x x x x x x j                       III. Các tính chất chung của bài toán QHTT 1. Sự tồn tại của PACB - Nếu bài toán có PA và hạng của ma trận hệ ràng buộc (A*) bằng n thì bài toán có PACB. - Nếu bài toán dạng chính tắc có PA thì chắc chắn có PACB (vì hạng của ma trận hệ ràng buộc luôn bằng n). 2. Tính hữu hạn của số PACB: Số PACB của mọi bài toán QHTT đều hữu hạn. 3. Sự tồn tại PATƯ - Nếu bài toán có PA và f(x)  M (bị chặn dưới) với bài toán có f(x) Min và f(x)  M (bị chặn trên) với bài toán có f(x)  Max trên tập PA thì bài toán có PATƯ, tức là giải được. - Nếu bài toán có PACB và giải được thì phải có PACB tối ưu. Do đó nếu bài toán dạng chính tắc giải được thì có PACB tối ưu. - Nếu bài toán có hơn một PATƯ thì sẽ có vô số PATƯ (?) IV. Phương pháp đơn hình 1. Nội dung 2. Cơ sở lý thuyết 3. Thuật toán đơn hình 4. Áp dụng thuật toán đơn hình tìm PACB 1. Nội dung - Xét bài toán không suy biến dạng chính tắc và biết một PACB. - Xuất phát từ PACB, tìm cách đánh giá nó, nếu chưa tối ưu thì tìm cách di chuyển sang một PACB khác tốt hơn. Vì số PACB của bài toán QHTT là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu không bị chặn trên tập PA hoặc sẽ tìm được PACB tối ưu. 2. Cơ sở lý thuyết - Xét bài toán dạng chính tắc có PACB x0 và cơ sở J0: x0j (j  J0) là thành phần cơ sở: x0j > 0  (j  J0) x0k (k  J0) là thành phần phi cơ sở: k  J0  x0k = 0 - Với PACB x0, ta có: 1 1 ( ) (1) 0( 1 ) (2) n j j j n j j j j f x c x Min x A b x j n              0 0 0 0 0 0 0 1 (*) n j j j j k k j j j j J k J j J b x A x A x A x A            - Ta có: - Ký hiệu: - Với x là PA bất kỳ của bài toán, ta có: 0 0( )k jk j j J A x A k J    0 0( )k j jk k j J c x c k J      1 0 0 ( ) 0 00 0 0 0 ( ) (**) 0 0 n b x A x A x Aj j j j k kj Jj k J b x A x x Aj j jk jkj J j Jk J b x A A x xj j j k jkj J j J k J b x x x Aj jk jkj J k J                             Định lý 2: Dấu hiệu tối ưu - Nếu đối với PACB x0 có cơ sở J0 của bài toán dạng chính tắc mà thì x0 là PATƯ + Nếu thì x0 là PATƯ duy nhất + Đối với PACB x0, cơ sở J0 thoả mãn định lý 2 mà tồn tại thì x0 có thể không phải là PATƯ duy nhất. 00( )k k J    00( )k k J    00( )k k J   Chứng minh - Từ (*) và (**), ta có 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ( ) ( ) ( ) ( ) ( ) ( ) ( ) j j k jk j j k jk k J k J n j j j j k k j J k Jj j j k jk k k j J k J k J j j j k jk k k j J j J k J k J j j j jk k k j J k J j J x x x x x x c x c x x c x c x c x c x f x c x f x f x x x j J c x x c x f x x c x c x f                                                     0 0( ) ( ) k kk J x f x x     - Như vậy: - Bài toán chính tắc có thể quy về bài toán dạng chuẩn: 0 0 00( ) 0 ( ) ( )k k kk J x f x f x k J           0 0 0 0 0 ( ) ( ) ( ) 0( 1 ) k k k J j k jk j k J j x x x f x f x x Min x j J x j n                 - Định lý 3: Dấu hiệu bài toán không giải được Nếu đối với PACB x0, cơ sở J0 của bài toán dạng chính tắc mà k > 0 (kJ0) mà xjk  0 (jJ0) thì bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA. - Định lý 4: Dấu hiệu cải tiến PA Nếu với mỗi k > 0 (kJ0) đều có ít nhất một xjk > 0 (jJ0) thì ta có thể chuyển sang một PACB mới, ký hiệu: x1 tốt hơn x0, tức là f(x1) < f(x0). Chứng minh + Với PACB x0, cơ sở J0 mà thì theo dấu hiệu tối ưu x0 chưa phải là PATƯ + Với mỗi chỉ số kJ0 xác định một véc tơ Zk = {zjk: j =1m) và gọi là phương Zk theo công thức: + Xuất phát từ PACB x0 di chuyển theo phương Zk với bước di chuyển  > 0 ta có véc tơ x() = x0 + Zk  f(x()) = f(x0) - k + Ảnh hưởng của phương Zk đến giá trị hàm mục tiêu được đánh giá thông qua k như sau: +> Nếu k f(x0)  Zk gọi là phương tăng +> Nếu k = 0 thì f(x()) = f(x0) thì Zk gọi là phương không đổi +> Nếu k > 0 thì f(x()) < f(x0)  Zk gọi là phương giảm 00( )k k J   0 0 0 ( ) 0( & ) 1( & ) jk k j x j J Z j J j k j J j k          +> Nếu k > 0 (kJ0) và xjk  0 (jJ0) thì Zk gọi là phương giảm vô hạn của hàm mục tiêu. +>Nếu với mỗi k > 0 (kJ0) đều xjk > 0 (jJ0) thì Zk gọi là phương giảm hữu hạn của hàm mục tiêu. + Xét Zk là phương giảm hữu hạn: +> Với các xjk > 0 ta xác định +> Với bước di chuyển 0 ta xác định PA x1: x1 = x(0) = x0 + 0k và f(x1) = f(x0) - 0k < f(x0) + PA x1 là PACB mới tốt hơn PACB x0 0 0 0 , 0 0 j jkj J jk x Min x x            3. Thuật toán đơn hình - Áp dụng cho bài toán dạng chính tắc đã biết PACB x0, cơ sở J0 ={1,2,…,m}, tức là cơ sở bao gồm m véc tơ {A1, A2,…,Am}. - Thuật toán bao gồm 5 bước như sau: + Bước 1: Lập bảng đơn hình ứng với PACB x0, cơ sở J0 là bảng ghi các hệ số phân tích của véc tơ b và các véc tơ điều kiện qua cơ sở J0 theo mẫu sau: Bảng đơn hình Hệ số Cơ sở PACB C1 C 2 … Cr … Cm Cm+1 … Ck … Cs … Cn x1 x2 … xr … xm xm+1 … xk … xs … xn C1 x1 x01 1 0 … 0 … 0 x1m+1 … x1k … x1s … x1 n C2 x2 x02 0 1 … 0 … 0 x2m+1 … x2k … x2s … x2 n … … … … … … … … … … … … … … … … Cr xr x0r 0 0 … 1 … 0 xrm+1 … xrk … [xrs] … xrn … … … … … … … … … … … … … … … … Cm xm x0m 0 0 … 0 … 1 xmm+1 … xmk … xms … xm n f(x) f(x0) 0 0 … 0 … 0 m+1 … k … s … n + Bước 2: Kiểm tra dấu hiệu tối ưu +> Nếu k  0 (kJ0) thì PACB x0 là PACB tối ưu -> Nếu k < 0 (kJ0) thì PACB x0 là PACB tối ưu duy nhất -> Nếu k = 0 (kJ0) thì PACB x0 có thể là PACB không duy nhất +> Nếu k > 0 (kJ0) thì chuyển sang bước 3 + Bước 3: Kiểm tra tính không giải được của bài toán +> Nếu k > 0 (kJ0) mà xjk  0 (jJ0) thì bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA +> Nếu với mỗi k > 0 (kJ0) đều có ít nhất một xjk > 0 (jJ0) thì chuyển sang bước 4 + Bước 4: Chọn véc tơ đưa vào cơ sở và xác định véc tơ loại khỏi cơ sở +> Giả sử: khi đó ta đưa véc tơ As vào cơ sở +> Xác định: khi đó loại véc tơ Ar ra khỏi cơ sở 0k k sMax      0 0 0 0 0, 0 ( , 0) j r js rsj J js rs x x Min x r J x x x              + Bước 5: Biến đổi bảng đơn hình +> Trong cột cơ sở thay xr bằng xs và trong cột hệ số thay cr bằng cs; dòng r gọi là dòng xoay, cột s gọi là cột xoay, phần tử [xrs] gọi là phần tử trục xoay. +> Chia lần lượt các phần tử nằm trên dòng xoay cho phần tử trục xoay ta thu được một dòng tương ứng ở bảng đơn hình mới gọi là dòng chuẩn. +> Tìm trên dòng cần biến đổi còn lại phần tử thuộc cột xoay, đổi dấu nó, rồi đem nhân với dòng chuẩn, sau đó cộng với chính dòng đó ở bảng đơn hình cũ ta thu đợc một dòng mới tương ứng ở bảng đơn hình mới. +> Dòng ước lượng cũng được biến đổi như một dòng bình thường hoặc xác định lại theo công thức đã có. + Sau bước 5 quay trở lại bước bước 2 và tiếp tục thuật toán với PACB mới x1, cơ sở J1. Sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA hoặc sẽ tìm được được PACB tối ưu. Chú ý - Khi 0 = 0 ta vẫn thực hiện thuật toán một cách bình thường, khi đó kết quả của việc biến đổi sẽ cho ta chuyển sang một cơ sở khác của cùng một PACB suy biến. - Tại bước 4, nếu khi chọn véc tơ đưa vào cơ sở và xác định véc tơ loại khỏi có sở mà có nhiều véc tơ thuộc diện lựa chọn thì ta chọn ngẫu nhiên một trong các véc tơ đó. - Với bài toán có g(x)  Max ta đưa về bài toán có f(x)  Min bằng cách đổi dấu toàn bộ các hệ số trong hàm mục tiêu. Sau đó áp dụng thuật toán một cách bình thường, tuy nhiên: gmax = - fmin. Ví dụ 5 - Cho bài toán QHTT: - Giải bài toán sau bằng phương pháp đơn hình 1 2 3 4 1 2 3 4 2 3 4 2 3 4 1 ( ) 2 3 2 1 1 8 (1) 2 4 8 8 ( 2 ) 2 2 3 2 0 (3) 0 ( 1 4 )j f x x x x x M in x x x x x x x x x x x j                        Ví dụ 6 - Cho bài toán QHTT: - Giải bài toán sau bằng phương pháp đơn hình 1 2 3 1 2 3 1 3 1 2 3 ( ) 4 3 2 2 16 (1) 4 2 28 (2) 2 12 (3) 0( 1 3)j f x x x x Min x x x x x x x x x j                   Ví dụ 7 - Cho bài toán QHTT: - Giải bài toán sau bằng phương pháp đơn hình 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 2 3 5 4 2 1 2 (1) 1 2 8 ( 2 ) 2 3 2 2 0 (3 ) 2 0 ( 1 3 )j f x x x x M in x x x x x x x x x x j                            4. Áp dụng thuật toán đơn hình tìm PACB - Nội dung: Áp dụng cho bài toán dạng chính tắc chưa biết thông tin về PACB. Để áp dụng thuật toán đơn hình cần tìm một PACB và cơ sở tương ứng của nó. - Xét bài toán dạng chính tắc có bi  0 (i): 1 1 ( ) ( 1 ) (1) ( ) 0( 1 ) (2) n j j j n ij j i j j f x c x Min a x b i m I x j n                - Từ bài toán này xây dựng bài toán phụ (P): Trong đó: xig là các biến giả 1 1 ( 1 ) 1 1 ( , ) 0 ( ) 0 ( ) m g g i i n g ij j i i j j g i a x b i m j n i m P x x x Min x x x                     Nhận xét - Véc tơ x là PA, PACB của bài toán (I) khi và chỉ khi (x, xg = 0) là PA, PACB của bài toán (P). - Bài toán (P) là bài toán chuẩn và P(x, xg)  0 nên luôn giải được. - Ký hiệu PACB tối ưu của bài toán (P) là và trị tối ưu Pmin = P - Có hai trường hợp xảy ra: + bài toán (I) không có PA, tức là không