Bài giảng quy hoạch tuyến tính Chương 1: Bài toán quy hoạch tuyến tính

Trường Đại học kinh tế kỹ thuật công nghiệp Bộ môn khoa học cơ bản BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH Chương 1: Bài toán quy hoạch tuyến tính TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP  BỘ MÔN KHOA HỌC CƠ BẢN BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH Chương I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương II: BÀI TOÁN VẬN TẢI  Chương III: MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI CHƯƠNG I:  BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1. Bài toán quy hoạch tuyến tính tổng quát 1.2. Bài toán dạng chính tắc 1.3. Bài toán dạng chuẩn 1.4. Các tính chất chung 1.5. Phương pháp đơn hình 1.6. Phương pháp đơn hình đối ngẫu 1.1. Bài toán quy hoạch tuyến tính tổng quát Hàm f(x) gọi là hàm mục tiêu 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. ■ Một số khái niệm : Phương án: Vectơ x = (x1, x2,..., xn) thoả mãn mọi điều kiện ràng buộc của bài toán gọi là một phương án. -Nếu thì ràng buộc i gọi là “chặt” đối với phương án x, hoặc phương án x thoả mãn chặt ràng buộc i. -Nếu thì ràng buộc i gọi là “lỏng” đối với phương án x, hoặc phương án x thoả mãn lỏng ràng buộc i. Phương án tối ưu: Một phương án mà tại đó trị số hàm mục tiêu đạt cực tiểu (hoặc cực đại) gọi là phương án tối ưu. Phương án cực biên: Một phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính gọi là phương án cực biên. 1.2. Bài toán dạng chính tắc: Mọi bài toán quy hoạch tuyến tính đề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 hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia ●Cách đưa bài toán về dạng chính tắc -Nếu xj ≤ 0 thì đổi biến xj’= −xj ≥ 0. -Nếu một ràng buộc có dạng thì có thể thay bằng với và hệ số của trong f(x) bằng 0. Các biến gọi là biến phụ. -Nếu một ràng buộc có dạng thì thay bằng , -Nếu xj không có ràng buộc dấu thì đặt xj = xj’− xj’’, với xj’, xj’’≥ 0. Ví dụ: Đưa bài toán sau về dạng chính tắc:f(x) = –2x1 + x2 + 3x3 + 5x4  min  x1 – 3x2 + 5x3 – x4  16  2x1 – x2 – 2x3 + 2x4 ≥ – 4  4x1 + 3x2 + x3 + x4 = 9  x1, x2 ≥ 0, x3  0 Các biến phụ sẽ được đánh số tiếp là x5, x6.Đặt x3’= – x3 ≥ 0, x4 = x4’ – x4’’, x4’, x4’’ ≥ 0.Ta được bài toán chính tắc tương đương sau:f(x) = –2x1 + x2 – 3x3’ + 5x4’ – 5x4’’  min   x1 – 3x2 – 5x3’ – x4’ + x4’’ + x5 = 16  2x1 – x2 + 2x3’ + 2x4’ – 2x4’’ – x6 = –4  4x1 + 3x2 – x3’ + x4’ – x4’’ = 9  x1, x2 , x3’, x4’, x4’’, x5, x6 ≥ 0 1.3. Bài toán dạng chuẩn Trong đó: Bài toán dạng chuẩn là bài toán dạng chính tắc có vế phải không âm và mỗi phương trình đều có một biến số với hệ số bằng 1 đồng thời không có trong các phương trình khác (gọi là biến cô lập với hệ số bằng 1). Từ hệ phương trình ràng buộc của bài toán dễ dàng suy ra một phương án đầu tiên: x0 = (b1, b2, …,bm, 0, 0,…, 0), với cơ sở là {A1, A2,…Am} = E, đó là phương án cực biên. 1.4. Các tính chất chung 1. Tính chất 1: Sự tồn tại phương án cực biên: Nếu bài toán có phương án và hạng của ma trận hệ ràng buộc bằng n thì bài toán có phương án cực biên. Hạng của ma trận hệ ràng buộc của bài toán dạng chính tắc luôn luôn bằng n nên nếu bài toán chính tắc có phương án thì phải có phương án cực biên. 2. Tính chất 2: Sự tồn tại phương án tối ưu: Nếu bài toán có phương án và trị số hàm mục tiêu bị chặn trên tập phương án thì bài toán có phương án tối ưu. 3. Tính chất 3: Tính hữu hạn của số phương án cực biên: Số phương án cực biên của mọi bài toán quy hoạch tuyến tính đều hữu hạn. 1.5. Phương pháp đơn hình 1. Nội dung của phương pháp: Xuất phát từ một phương án cực biên đầu tiên, tìm cách đánh giá phương án cực biên ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang một phương án cực biên mới tốt hơn, quá trình được lặp lại vì số phương án cực biên 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ì hàm mục tiêu không bị chặn hoặc sẽ tìm được phương án tối ưu. Phương pháp này chỉ áp dụng được cho những bài toán có phương án cực biên, tuy nhiên mọi bài toán QHTTT đều có thể đưa về bài toán dạng chính tắc, và khi nó đã có phương án thì sẽ có phương án cực biên. Do đó không làm mất tính chất tổng quát từ đây ta sẽ chỉ xét bài toán dạng chính tắc. 2. Cơ sở của phương án cực biên: Định nghĩa: Một hệ vectơ {Aj } độc lập tuyến tính bao hàm hệ thống các vectơ tương ứng với các thành phần dương của phương án cực biên x gọi là cơ sở của phương án cực biên ấy Ký hiệu: J, trong đó: J = {j, Aj nằm trong cơ sở}. Một phương án cực biên không suy biến có đúng m thành phần dương, có một cơ sở duy nhất, đó chính là các vectơ tương ứng với các thành phần dương, còn phương án cực biên suy biến thì có nhiều cơ sở khác nhau, phần chung của chúng là các vectơ tương ứng với các thành phần dương. 3. Thuật toán của phương pháp đơn hình Giả sử đã biết phương án cực biên x0, cơ sở J0. Lập bảng đơn hình tương ứng: Bước 1: Kiểm tra dấu hiệu tối ưu:Tính các ước lượng ∆k theo công thức:  -Nếu ∆k ≤ 0, (k  J0) thì x0 là phương án tối ưu. -Nếu ∆k > 0 thì x0 không phải là phương án tối ưu, chuyển sang bước 2. Bước 2: Kiểm tra tính không giải được của bài toán: -Nếu tồn tại một ∆k > 0 mà xjk ≤ 0 (j  J0) thì bài toán không có phương án tối ưu. -Nếu với mỗi ∆k > 0 đều có ít nhất một xjk > 0 thì chuyển sang bước 3. Bước 3: Chọn vectơ đưa vào cơ sở và xác định vectơ loại khỏi cơ sở: -Giả sử , vectơ As được đưa vào cơ sở,  tính -Giả sử Vectơ Ar bị loại khỏi cơ sở Phần tử xrs gọi là phần tử xoay của phép biến đổi.  Lập bảng đơn hình mới, thay xs vào vị trí xr, và cs vào  vị trí cr. Chuyển sang bước 4. Bước 4: Biến đổi bảng: Thực hiện phép biến đổi cơ sở tổng quát cho toàn bộ bảng (bao gồm cả hàng ước lượng k). -Để tính hàng vectơ đưa vào (xs) trong bảng mới ta lấy hàng vectơ loại ra (xr) trong bảng cũ chia cho phần tử xoay. -Để tính hàng xj trong bảng mới, ta lấy hàng xj trong bảng cũ trừ đi hàng xs vừa mới tính được sau khi nhân nó với xjs.  Kết quả của quá trình biến đổi sẽ cho ta bảng đơn hình ứng với phương án cực biên mới x1, tốt hơn x0.  Đối với x1 quay trở lại bước 1 và quá trình lặp lại sau một số hữu hạn bước sẽ tìm được phương án cực biên tối ưu hoặc kết luận bài toán không giải được vì hàm mục tiêu không bị chặn. Ví dụ 1: Giải bài toán sau bằng phương pháp đơn hình: f(x) = 2x1 + 3x2 – x3 – 1/2x4  min  x1 – x2 + x3 + 1/2x4 = 18  x2 – 4x3 + 8x4  8  –2x2 + 2x3 – 3x4  20  xj ≥ 0 (j =1…4) Trước hết đưa bài toán về dạng chính tắc bằng cách cộng vào ràng buộc hai và ba hai biến phụ x5 và x6. Ta có: f(x) = 2x1 + 3x2 – x3 – 1/2x4  min x1 – x2 + x3 + 1/2x4 = 18 x2 – 4x3 + 8x4 + x5 = 8 –2x2 + 2x3 – 3x4 + x6 = 20 xj ≥ 0 (j = 1…6) Bài toán có dạng chuẩn, các biến cô lập là x1, x5, x6 nên phương án cực biên tương ứng x0 = (18, 0, 0, 0, 8, 20), cơ sở là {A1, A5, A6}, do đó ta có thể lập ngay được bảng đơn hình ứng với phương án cực biên x0: f(x) 36 0 0 0 −5 3/2 3 Ở bước 1 ta thấy phương án tương ứng chưa tối ưu. Vectơ đưa vào cơ sở là A3 ứng với 3 = 3, θ0 = 20/2 nên vectơ A6 bị loại khỏi cơ sở, phần tử xoay là [2]. −1 10 0 −1 1 −3/2 0 1/2 1 0 0 0 0 1 8 0 2 −1/2 48 −3 2 2 f(x) 6 0 0 0 −2 6 −3/2 −1/2 4 1/2 0 0 1 0 −1/4 0 1 0 0 1 0 40 −1 −3 5/2 16 3/4 −1 1/8 f(x) −18 0 0 0 −3 −2 0 Ở bước thứ ba ta thấy k  0 (k  J) Phương án tương ứng là tối ưu: x* = (0, 0, 16, 4, 40, 0) Giá trị tối ưu của hàm mục tiêu là: f* = –18. 4. Các chú ý khi áp dụng thuật toán: 1) Đối với bài toán có hàm f(x)  max thì có thể chuyển về giải bài toán với hàm g(x) = −f(x)  min chú ý là fmax = −gmin hoặc cũng có thể giải trực tiếp với dấu hiệu tối ưu là k ≥ 0, dấu hiệu để điều chỉnh phương án là k 0 vào cơ sở cũng cải tiến được phương án. 3) Trường hợp bài toán suy biến thì θ0 có thể bằng 0, khi θ0 = 0 vẫn thực hiện thuật toán một cách bình thường, nghĩa là vectơ ứng với θ0 vẫn bị loại khỏi cơ sở.  Dấu hiệu xuất hiện phương án cực biên suy biến là θ0 đạt tại nhiều chỉ số, khi đó vectơ loại khỏi cơ sở được chọn trong số những vectơ ứng với θ0 theo quy tắc ngẫu nhiên. Khi áp dụng thuật toán cần lưu ý hai trường hợp:  -Phương án cực biên x0 có cơ sở J0 là cơ sở đơn vị, lúc đó ma trận hệ số phân tích của [ A | b] theo cơ sở đơn vị là chính nó nên ta có thể lập ngay được bảng đơn hình.  Bài toán dạng chuẩn là bài toán cho ngay một phương án cực biên với cơ sở là đơn vị, nên từ bài toán ta có thể lập được bảng đơn hình ứng với phương án cực biên ấy. -Nếu J0 không phải là cơ sở đơn vị thì để lập bảng đơn hình trước hết cần phải tìm ma trận hệ số phân tích theo J0. Để làm điều này ta viết ma trận mở rộng [A | b] sau đó thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận, biến đổi sao cho các vectơ cơ sở trở thành các vectơ đơn vị khác nhau. Khi đó ma trận mở rộng sẽ trở thành ma trận hệ số phân tích. Ví dụ 2: Cho bài toán:  f(x) = −2x1 − 6x2 + 8x3 – 5x4  min  x1 + 2x2 − 3x3 + x4 = 8  −2x1 + x2 + x3 − 5x4  2  4x1 + 7x2 − 8x3 + 2x4 ≥ 20  xj ≥ 0 (j = 1…4) và vectơ x0 = (8, 0, 0, 0).  Chứng tỏ x0 là phương án cực biên, lợi dụng x0 giải bài toán bằng phương pháp đơn hình.  Dễ thấy rằng x0 thỏa mãn mọi ràng buộc của bài toán, các ràng buộc là độc lập tuyến tính, vậy x0 là phương án cực biên không suy biến. Để giải bài toán bằng phương pháp đơn hình trước hết phải đưa bài toán về dạng chính tắc. f(x) = −2x1 − 6x2 + 8x3 – 5x4  min x1 + 2x2 − 3x3 + x4 = 8 −2x1 + x2 + x3 − 5x4 + x5 = 2 4x1 + 7x2 − 8x3 + 2x4 – x6 = 20 xj ≥ 0 (j = 1…6) Từ x0 suy ra phương án cực biên không suy biến của bài toán dạng chính tắc: = (8, 0, 0, 0, 18, 12) với cơ sở là J0 = {A1, A5, A6} không phải là cơ sở đơn vị. Vì vậy để lập được bảng đơn hình ứng với phương án cực biên ta phải tìm ma trận hệ số phân tích của ma trận điều kiện của bài toán dạng chính tắc qua cơ sở J0 . Chú ý rằng vế phải của ma trận hệ số phân tích phải trùng với các thành phần cơ sở của phương án cực biên. Quá trình biến đổi thực hiện trên các ma trận sau: Trên cơ sở ma trận hệ số phân tích, lập bảng đơn hình Sau bước 2 ta có 3 = 4 > 0, nhưng xj3 0, khi đó bài toán xuất phát không có phương án b) Pmin = 0, khi đó , = 0, phương án tối ưu có dạng: suy ra là phương án cực biên của bài toán xuất phát. Để áp dụng được thuật toán cho phương án cực biên cần phải biết cơ sở của nó. Hai trường hợp có thể xảy ra: -Trong cơ sở của phương án cực biên tối ưu không có các vectơ tương ứng với các biến giả, khi đó cơ sở của phương án cực biên này cũng là cơ sở của phương án cực biên , để có bảng đơn hình tương ứng chỉ cần tính lại hàng ước lượng k theo hàm f và tiếp tục thuật toán. -Trong cơ sở của phương án cực biên tối ưu có ít nhất một vectơ biến giả, thành phần tương ứng , phương án cực biên là suy biến. Trường hợp này để tiếp tục tính toán, trước hết ta loại các cột ứng với k(P) < 0 (và các cột xgi phi cơ sở), sau đó tính lại các ước lượng k theo hàm f và tiếp tục thuật toán. Khi giải bài toán P cần chú ý một số đặc điểm sau: - Khi xây dựng bài toán phụ chỉ cộng thêm biến giả vào những phương trình cần thiết (nhằm tạo ma trận điều kiện của bài toán phụ có đủ m vectơ đơn vị). - Một biến giả đã bị loại khỏi cơ sở thì cột tương ứng không cần tính ở các bước tiếp sau. - Chỉ được áp dụng công thức đổi cơ sở cho hàng ước lượng khi hai bảng kế tiếp có cùng tên hàm mục tiêu. Ví dụ 3: Giải bài toán sau bằng phương pháp đơn hình:  f(x) = 3x1 + 4x2 + 2x3 + 2x4  min  2x1 + 2x2 + x4 = 28  x1 + 5x2 + 3x3 − 2x4  31 2x1 – 2x2 + 2x3 + x4 = 16  xj ≥ 0 (j =1…4) Đưa bài toán về dạng chính tắc: f(x) = 3x1 + 4x2 + 2x3 + 2x4  min  2x1 + 2x2 + x4 = 28  x1 + 5x2 + 3x3 − 2x4 + x5 = 31 2x1 – 2x2 + 2x3 + x4 = 16  xj ≥ 0 (j =1…5) Ta thấy bài toán không phải dạng chuẩn nên thành lập bài toán phụ P(x, xg) = xg1 + xg3  min 2x1 + 2x2 + x4 + xg1 = 28 x1 + 5x2 + 3x3 – 2x4 + x5 = 31 2x1 – 2x2 + 2x3 + x4 + xg3 = 16 xj ≥ 0 (j =1…5), xg ≥ 0 Bài toán phụ: 44 4 0 2 2 0 0 0 0 8 1 −1 1 1/2 0 0 0 0 0 1 1 0 12 4 –2 0 23 6 2 –5/2 0 0 0 12 4 0 –2 4 3 5 3 0 1 −1/2 0 0 0 0 1 0 0 1 0 5 11 −5/2 1/2 1/2 45 −5/2 −1/2 0 0 0 3 4 2 2 0 f(x) k  0 (kJ), phương án tương ứng là tối ưu: x* = (11, 3, 0, 0, 5) và f* = 45. 1.6. Phương pháp đơn hình đối ngẫu 1. Cách thành lập bài toán đối ngẫu: Xét bài toán dạng chính tắc: (I) Bài toán đối ngẫu của bài toán (I) có dạng sau: Quy tắc thành lập bài toán đối ngẫu: - Nếu f(x)  min thì và hệ ràng buộc của bài toán đối ngẫu có dạng “  ”. - Nếu f(x)  max thì và hệ ràng buộc của bài toán đối ngẫu có dạng “ ≥ ”. - Số ràng buộc (không kể ràng buộc dấu) trong bài toán này bằng số biến số trong bài toán kia, nghĩa là tương ứng với một ràng buộc của bài toán này là một biến số của bài toán kia. - Hệ số trong hàm mục tiêu của bài toán này là vế phải của hệ ràng buộc trong bài toán kia. - Ma trận điều kiện trong hai bài toán là chuyển vị của nhau. - Các biến số trong bài toán đối ngẫu không có ràng buộc về dấu. Định nghĩa: Cặp ràng buộc đối ngẫu: 2 ràng buộc bất đẳng thức (kể cả ràng buộc dấu) trong hai bài toán cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu. Trong bài toán (I) và có n cặp ràng buộc đối ngẫu: Cách viết bài toán đối ngẫu: Trừ các ràng buộc về dấu, ta cho tương ứng với mỗi phương trình ràng buộc i của bài toán gốc một biến của bài toán đối ngẫu , thực hiện phép nhân vô hướng vectơ y lần lượt với vectơ b và các vectơ ta sẽ được hàm mục tiêu và toàn bộ hệ ràng buộc của bài toán đối ngẫu. Ví dụ 1: Viết bài toán đối ngẫu của bài toán sau: f(x) = −3x1 + 5x2 + 4x3 – 2x4 + x5  max 2x1 − 3x2 − x3 + 6x4 – 2x5 + 2x6 = –14 −x1 + 2x2 + 5x3 + 3x5 − 4x6 = 8 6x1 − 3x2 + 2x3 − x4 + x5 + 3x6 = 12 xj ≥ 0 (j =1…6) Bài toán đối ngẫu có 3 biến số y1, y2, y3. Theo cách viết trên ta có: = – 14y1 + 8y2 + 12y3  min 2y1 − y2 + 6y3 ≥ –3 −3y1 + 2y2 − 3y3 ≥ 5 − y1 + 5y2 + 2y3 ≥ 4 6y1 − y3 ≥ –2 −2y1 + 3y2 + y3 ≥ 1 2y1 − 4y2 + 3y3 ≥ 0 Đối với bài toán bất kỳ thì đưa bài toán về dạng chính tắc, xây dựng bài toán đối ngẫu của bài toán này và gọi nó là bài toán đối ngẫu của bài toán đã cho. Xét bài toán sau gọi là bài toán (II): (II) Đưa bài toán về dạng chính tắc, ký hiệu là (II’): (II’) Bài toán đối ngẫu của (II’) và cũng là bài toán đối ngẫu của (II) có dạng: Hai bài toán này có n + m cặp ràng buộc đối ngẫu sau: và Lược đồ tổng quát xây dựng bài toán đối ngẫu: Ví dụ 2: Viết bài toán đối ngẫu của bài toán sau: f(x) = −4x1 + x2 + 5x3 + 3x5  min 3x1 − 6x2 − x3 + 2x4 + 4x5 ≥ –15 −2x1 + 3x2 + 4x3 − 5x4 + x5  8 − 6x2 + 3x3 + 8x4 − 4x5 = 9 3x1 + 2x2 − 3x4 + x5 ≥ 24 x1, x3, x5 ≥ 0 Quy về bài toán chính tắc: f(x) = −4x1 + x2 + 5x3 + 3x5  min 3x1 − 6x2 − x3 + 2x4 + 4x5 − x6 = –15 −2x1 + 3x2 + 4x3 − 5x4 + x5 + x7 = 8 − 6x2 + 3x3 + 8x4 − 4x5 = 9 3x1 + 2x2 − 3x4 + x5 − x8 = 24 x1, x3, x5, x6, x7, x8 ≥ 0 Bài toán đối ngẫu: = –15y1 + 8y2 + 9y3 + 24y4  max 3y1 − 2y2 + 3y4  –4 −6y1 + 3y2 − 6y3 + 2y4 = 1 − y1 + 4y2 + 3y3  5 2y1 − 5y2 + 8y3 – 3y4 = 0 4y1 + y2 − 4y3 + y4  3 −y1  0 y2  0 −y4  0 2. Thuật toán của phương pháp đơn hình đối ngẫu: Xét bài toán dạng chính tắc với hàm f(x)  min Giả sử đã biết phương án cực biên y, cơ sở J của bài toán đối ngẫu. Thành lập bảng đơn hình ứng với cơ sở J: -Ở cột cơ sở ghi các thành phần cơ sở của giả phương án x vì đó là các hệ số phân tích của vectơ b qua cơ sở J. -Thay cho f(x) ghi . -Trị số của f(x) ứng với giả phương án x ghi trong bảng đơn hình xác định bởi: đó cũng chính là trị số của hàm mục tiêu ứng với phương án cực biên y. Bước 1: Kiểm tra dấu hiệu tối ưu: -Nếu xj ≥ 0 (j J) thì giả phương án trở thành phương án tối ưu của bài toán gốc, đồng thời phương án cực biên y tương ứng cũng tối ưu. -Nếu tồn tại một xj < 0 thì y không phải phương án tối ưu, chuyển sang bước 2. Bước 2: Kiểm tra tính không giải được của bài toán: -Nếu tồn tại một xj < 0 mà xjk ≥ 0 (k  J) thì bài toán đối ngẫu không giải được vì hàm mục tiêu không bị chặn, bài toán gốc không có phương án. -Nếu với mỗi xj < 0 đều có ít nhất một xjk < 0 thì chuyển sang bước 3. Bước 3: Đổi cơ sở: -Giả sử vectơ Ar bị loại khỏi cơ sở. -Tính θ0 theo công thức: giả sử , vectơ As được đưa vào cơ sở. Phần tử xoay của phép biến đổi cơ sở là xrs < 0. Lập bảng đơn hình mới và chuyển sang bước 4. Bước 4: Biến đổi bảng: Thực hiện phép biến đổi cơ sở cho toàn bộ bảng, kết quả sẽ cho ta bảng đơn hình ứng với phương án cực biên mới y’ của bài toán đối ngẫu tốt hơn y với cơ sở là J’ = [J \ {r}]{s}. Đối với y’ quay trở lại bước 1, và vì số phương án cực biên 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 gốc không có phương án hoặc sẽ tìm được phương án cực biên tối ưu. Khi giải bài toán cụ thể cần chú ý hai trường hợp: - Bài toán dạng chính tắc có một cơ sở gồm các vectơ { ei}, dễ dàng lập bảng đơn hình ứng với cơ sở này, nếu k  0, k  J thì đó là cơ sở đối ngẫu và áp dụng được thuật toán. - Biết phương án cực biên y của bài toán đối ngẫu của bài toán dạng chính tắc. Khi đó xác định cơ sở của y, tìm ma trận hệ số phân tích theo cơ sở này và lập bảng đơn hình tương ứng, trong bảng phải có k  0, k  J. Ví dụ 1: Giải bài toán bằng phương pháp đơn hình đối ngẫu: f(x) = x1 + 3x2 + 2x3 + 3x4 + 5x5  min x1 + 2x2 − x3 + x4 − x5 = −3 − x2 − x3 + 2x4 + 4x5 ≥ 18 − x2 − 3x3 + 2x5  10 xj ≥ 0 (j = 1…5) Đưa bài toán về dạng chính tắc: f(x) = x1 + 3x2 + 2x3 + 3x4 + 5x5  min x1 + 2x2 − x3 + x4 − x5 = −3 − x2 − x3 + 2x4 + 4x5 − x6 = 18 − x2 − 3x3 + 2x5 + x7 = 10 xj ≥ 0 (j = 1…7) Cơ sở {A1, A6, A7} = {e1, − e2, e3 }. Dễ dàng tính được ma trận hệ số phân tích theo cơ sở này bằng cách đổi dấu phương trình ràng buộc 2. Lập bảng đơn hình tương ứng: 0 −3 −1 0 0 −3 −2 −6 Ta thấy k  0 (k  J), đó là cơ sở đối ngẫu nên áp dụng được thuật toán. 9 0 −1/2 −1/2 1 2 −1/2 0 3 0 1 0 0 0 1 −12 5/2 −1/2 −3 1/2 10 −1 −3 2 0 15 0 0 0 −2 −4 −2 −1 4 −1/3 −5/6 1/6 0 1 −1/6 0 1 0 0 0 0 1 1 2/3 7/6 5/6 −1/6 2 2/3 2/3 −10/3 1/3 23 0 0 0 −2/3 −11/3 −11/3 −4/3 Phương án tối ưu của bài toán gốc: x* = (0, 0, 0, 1, 4, 0, 2) và f* = 23. Phương án tối ưu của bài toán đối ngẫu xác định bởi hệ phương trình: với J là cơ sở ứng với bảng đơn hình cuối cùng. − y1 + 4y2 + 2y3 = 5 y1 + 2y2 = 3 y3 = 0 Giải hệ phương trình này được y* = (1/3, 4/3, 0). Ví dụ 2: Cho bài toán: f(x) = −2x1 + 3x2 − 4x3 + 3x4 + x5  min −x1 + x2 − 2x3 − x5 ≥ −6 x1 + 3x2 + x3 − 2x4 + 2x5  21 2x1 − x2 + 3x3 + x4 = 6 xj ≥ 0 (j = 1…5) Viết bài toán đối ngẫu, chứng tỏ y0 = (3, −1, 1) là phương án cực biên của nó, xuất phát từ y0 giải bài toán bằng phương pháp đơn hình đối ngẫu. Xác định phương án tối ưu của bài toán đối ngẫu. Bài toán dạng chính tắc: f(x) = −2x1 + 3x2 − 4x3 + 3x4 + x5  min −x1 + x2 − 2x3 − x5 − x6 = −6 x1 + 3x2 + x3 − 2x4 + 2x5 + x7 = 21 2x1 − x2 + 3x3 + x4 = 6 xj ≥ 0 (j = 1…7) Bài toán đối ngẫu: = –6y1 + 21y2 + 6y3  max −y1 + y2 + 2y3  –2 y1 + 3y2 − y3  3 −2y1 + y2 + 3y3  −4 − 2y2 + y3  3 −y1 + 2y2  1 −y1  0 y2  0 Thử y0 vào các ràng buộc, chúng đều thoả mãn nên y0 là phương án. Phương án y0 thoả mãn chặt các ràng buộc 1, 3, 4, dễ thấy chúng độc lập tuyến tính nên y0 là phương án cực biên không suy biến. Cơ sở của phương án cực biên y0 là J0 = {A1, A3, A4}. Tìm ma trận hệ số phân tích của bài toán chính tắc theo J0: Phương án tối ưu của bài toán đối ngẫu là nghiệm của hệ phương trình: − y1 = 0 −2y1 + y2 + 3y3 = 3 y2 = 0 Suy ra y* = (0, 0, −4/3).