Giải tích 1 - Bài toán quy hoạch tuyến tính

ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 1 Ths. Nguyễn Công Trí Copyright 2001 Ths. Nguyễn Công Trí Copyright 2001 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. THIẾT LẬP MÔ HÌNH BÀI TOÁN (Xem) 2. CÁC DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (Xem) 3. CÁC KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (Xem) 4. CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (Xem) 5. BÀI TẬP (Xem) CHƯƠNG 1 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Ví dụ 1.1. BÀI TOÁN LẬP KẾ HOẠCH SẢN XUẤT Một xí nghiệp dùng 3 loại nguyên liệu: N1; N2; N3 để sản xuất ra một loại sản phẩm theo 3 phương pháp khác nhau: PP1; PP2; PP3. Định mức nguyên liệu và số lượng sản phẩm sản xuất ra trong 1 giờ được cho ở bảng sau: Hãy lập mô hình bài toán sao cho xí nghiệp sản xuất ra nhiều sản phẩm nhất? Nguyên Liệu Số lượng hiện có (đv) Định mức nguyên liệu PP1 PP2 PP3 N1 250 4 5 3 N2 350 2 4 1 N3 450 3 6 4 Số sản phẩm (sp/giờ) 10 12 9 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Gọi x1, x2, x3 lần lượt là thời gian sản xuất ra sản phẩm theo 3 phương pháp PP1, PP2, PP3. Tổng sản phẩm sản xuất (cần làm cực đại) f(x) = 10x1 + 12x2 + 9x3  max Do xí nghiệp chỉ có 250 nguyên liệu N1 nên x1, x2, x3 phải thỏa mãn 4x1 + 5x2 + 3x3 ≤ 250 Tương tự cho các nguyên liệu N2, N3 ta có 2x1 + 4x2 + x3 ≤ 350 và 3x1 + 6x2 + 4x3 ≤ 450 Dĩ nhiên ta phải có x1, x2, x3 không âm Vậy mô hình bài toán được phát biểu như sau: Tìm các biến x1, x2, x3 sao cho f(x)= 10x1 + 12x2 + 9x3  max, thỏa các điều kiện 4x1 + 5x2 + 3x3 ≤ 250 2x1 + 4x2 + x3 ≤ 350 3x1 + 6x2 + 4x3 ≤ 450 x1  0 x2  0 x3  0 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Ví dụ 1.2. BÀI TOÁN PHA CẮT VẬT LIỆU Một xí nghiệp may mặc cần sản xuất đúng 2.000 quần và ít nhất 1.000 áo. Mỗi tấm vải có 6 cách cắt như sau: Hãy tìm phương án cắt quần áo sao cho tổng số tấm vải là ít nhất? Cách cắt Quần Áo 1 90 35 2 80 55 3 70 70 4 60 90 5 120 0 6 0 100 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 2 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Gọi xj (j = 1, 2, ..., 6) là số tấm vải được cắt theo cách thứ j. Tổng số tấm vải dùng để sản xuất (cần làm cực tiểu) là f(x) = x1 + x2 + x3 + x4 + x5 + x6  min Do xí nghiệp cần sản xuất đúng 2.000 quần nên các xj phải thỏa mãn 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 Tương tự cho điều kiện về sản xuất áo, ta có 35x1 + 55x2 + 70x3 + 90x4 + 100x6  1000 Dĩ nhiên ta phải có xj (j = 1, 2, ..., 6) không âm Vậy mô hình bài toán được phát biểu như sau: Tìm các biến xj (j = 1, 2, ..., 6) sao cho f(x)= xj  min, thỏa các điều kiện 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 35x1 + 55x2 + 70x3 + 90x4 + 100x6  1000 xj  0, (j = 1, 2, ..., 6). MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Ví dụ 1.3. BÀI TOÁN XÁC ĐỊNH KHẨU PHẦN Để nuôi một loại gia súc có hiệu quả, mỗi ngày cần phải có khối lượng tối thiểu các chất protit, glucit, khoáng tương ứng là 90 gram, 130 gram, 10 gram. Tỷ lệ (%) theo khối lượng các chất trên có trong các loại thức ăn A, B, C như sau: Giá 1 kg thức ăn A, B, C tương ứng là 3.000 đồng, 4.000 đồng, 5.000 đồng. Hãy lập mô hình bài toán xác định khối lượng thức ăn cần thiết sao cho chi phí nuôi gia súc là thấp nhất? Thức ăn Chất dinh dưỡng (%) Protit Glucit Khoáng A 10 30 2 B 20 40 1 C 30 20 3 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Gọi xj (j = 1, 2, 3) là số gram thức ăn A, B, C cần mua mỗi ngày. Tổng chi phí dùng để mua thức ăn (cần làm cực tiểu) là f(x) = 3x1 + 4x2 + 5x3  min (đồng) Do các tỷ lệ các chất protit, glucit và khoáng có trong thức ăn A nên các xj phải thỏa mãn 0,1x1 + 0,2x2 + 0,3x3  90 Tương tự cho điều kiện của thức ăn B và C, ta có 0,3x1+0,4x2+0,2x3 130 và 0,02x1+0,01x2+0,03x310 Vậy mô hình bài toán được phát biểu như sau: Tìm các biến xj (j = 1, 2, 3) sao cho f(x) = 3x1 + 4x2 + 5x3  min, thỏa các điều kiện 0,1x1 + 0,2x2 + 0,3x3  90 0,3x1 + 0,4x2 + 0,2x3  130 0,02x1 + 0,01x2 + 0,03x3  10 xj  0, (j = 1, 2, 3). MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Ví dụ 1.4. BÀI TOÁN VẬN TẢI Cần vận chuyển xi măng từ 3 kho K1, K2, K3 đến 4 công trường xây dựng T1, T2, T3, T4. Cho biết lượng xi măng có ở mỗi kho, lượng xi măng cần ở mỗi công trường và cước phí vận chuyển (ngàn đồng/ tấn) từ mỗi kho đến công trường như sau: Lập mô hình bài toán vận chuyển sao cho các kho phát hết xi măng có, công trường nhận đủ xi măng cần và chi phí vận chuyển thấp nhất? Công trường Kho T1: 130 t T2: 160 t T3: 120 t T4: 140 t K1: 170 tấn 20 18 22 25 K2: 200 tấn 15 25 30 15 K3: 180 tấn 45 30 40 35 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 3 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTT Gọi xij (i = 1, 2, 3, j = 1, 2, 3, 4) là lượng xi măng cần vận chuyển từ kho Ki đến công trường Tj. Tổng chi phí vận chuyển (cần làm cực tiểu) là f(x) = 20x11 + 18x12 + 22x13 + 25x14 15x21 + 25x22 + 30x23 + 15x24 45x31 + 30x32 + 40x33 + 35x34  min Điều kiện của các kho x11 + x12 + x13 + x14 = 170 x21 + x22 + x23 + x24 = 200 x31 + x32 + x33 + x34 = 180 Điều kiện của các công trường x11 + x21 + x31 = 130 x12 + x22 + x32 = 160 x13 + x23 + x33 = 120 x14 + x24 + x34 = 140 xij  0, i = 1, 2, 3, j = 1, 2, 3, 4. CÁC DẠNG CỦA BÀI TOÁN QHTT 2.1. DẠNG TỔNG QUÁT Tìm x = (x1, x2,..., xn) sao cho: (2.1) gọi là hàm mục tiêu. (2.2) gọi là hệ ràng buộc. (2.3) gọi là ràng buộc về dấu của ẩn số. Ví dụ 1.1, Ví dụ 1.2 và Ví dụ 1.3 là các bài toán QHTT có dạng tổng quát. 1 ( ) min ( max) (2.1) n j j j f x c x hay        1 1, 2.2 0, 0, 2.3 n ij j i j j k a x b i m x x j k n                     CÁC DẠNG CỦA BÀI TOÁN QHTT  Một vectơ x = (x1, x2,..., xn) thỏa mãn điều kiện (2) và (3) được gọi là một phương án (P.A) của bài toán quy hoạch tuyến tính (QHTT).  Tập các P.A của bài toán được gọi là miền ràng buộc hay miền xác định. Ký hiệu là D.  Phương án tối ưu (P.A.T.Ư) hay nghiệm của bài toán, ký hiệu là Xopt (optimality), nếu vectơ X là một P.A và hàm mục tiêu (2.1) bị chặn.  Bài toán được gọi là giải được hay có lời giải hay có nghiệm nếu nó có ít nhất một P.A.T.Ư.  Bài toán không giải được hay vô nghiệm nếu D =  hay nó có P.A nhưng không có PA.T.Ư. CÁC DẠNG CỦA BÀI TOÁN QHTT 2.2. DẠNG CHÍNH TẮC Tìm x = (x1, x2,..., xn) sao cho: Nhận xét: Hệ ràng buộc của bài toán dạng chính tắc đều là các đẳng thức và mọi biến của bài toán đều không âm. Ví dụ 1.4 BÀI TOÁN VẬN TẢI có dạng chính tắc. 1 ( ) min ( max) n j j j f x c x hay    1 1, 0, 1, n ij j i j j a x b i m x j n          ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 4 CÁC DẠNG CỦA BÀI TOÁN QHTT 2.3. DẠNG CHUẨN Tìm x = (x1, x2,..., xn) sao cho: Nhận xét: Bài toán dạng chuẩn là bài toán ở dạng chính tắc với hệ ràng buộc chứa ma trận con Im là ma trận đơn vị cấp m. Trong đó các xi (i = 1, 2,..., m) được gọi là ẩn cơ bản (A.C.B), còn các ẩn xi,m+k, (k = 0, 1,..., n – m) được gọi là ẩn không cơ bản. 1 ( ) min ( max) n j j j f x c x hay    , 1 , 1, 0 1, 0 n m i i m k m k i k j i x a x b i m x j n b               CÁC DẠNG CỦA BÀI TOÁN QHTT 2.4. CHUYỂN ĐỔI DẠNG BÀI TOÁN QHTT Khi xét bài toán QHTT, người ta thường sử dụng dạng chính tắc, có thể đưa bài toán dạng tổng quát về dạng chính tắc bằng các biến đổi sau: 1) Nếu ràng buộc thứ i có dạng aijxj ≤ bi thì thêm vào một ẩn phụ xn+1  0, sao cho aijxj + xn+1 = bi. 2) Nếu ràng buộc thứ i có dạng aijxj  bi thì thêm vào một ẩn phụ xn+1  0, sao cho aijxj – xn+1 = bi. 3) Nếu ẩn xj ≤ 0 thì được thay bằng x / j = – xj  0. 4) Nếu ẩn xj không ràng buộc về dấu thì thay xj bằng hai ẩn phụ x/j và x // j sao cho xj = x / j – x // j, với x/j  0, x // j  0. CÁC DẠNG CỦA BÀI TOÁN QHTT Để bài toán gọn hơn, chúng ta dùng các ký hiệu Trong đó A là ma trận mn gồm các hệ số ở vế trái của hệ ràng buộc; Aj là vectơ cột thứ j của ma trận A; b là vectơ hệ số ở vế phải của hệ ràng buộc; c là vectơ hệ số ở hàm mục tiêu; x là vectơ ẩn số; 0 là vectơ không. Khi đó bài toán QHTT ở dạng chính tắc có dạng f(x) = cTx  min (hay max) Ax = b, x  0 11 12 1 21 22 2 1 2 , n n m m mn a a a a a a A a a a                    1 2 , m b b b b              1 2 , n c c c c              1 2 , n x x x x              0 0 0 0              1 2 , j j j mj a a A a              CÁC DẠNG CỦA BÀI TOÁN QHTT Ví dụ 1.5. Đưa bài toán QHTT sau đây về dạng chính tắc và viết bài toán chính tắc dưới dạng ma trận Thêm 2 ẩn phụ x4, x5  0 vào ràng buộc thứ nhất và ràng buộc thứ ba. Thay x/3 = –x3  0 Thay x2 = x / 2 –x // 2  0, với x / 2, x // 2  0 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 3 2 min 3 2 7 2 4 12 4 3 8 10 0 0 f x x x x x x x x x x x x x x x                   ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 5 CÁC DẠNG CỦA BÀI TOÁN QHTT Bài toán QHTT có dạng chính tắc như sau Bài toán QHTT dưới dạng ma trận như sau f(x) = (1, 3, – 2, 0, 0, 0)T(x1, x / 2, x // 2, x / 3, x4, x5)  min (x1, x / 2, x // 2, x / 3, x4, x5)  (0, 0, 0, 0, 0, 0) 1 2 2 3 1 2 2 3 4 1 2 2 3 1 2 2 3 5 1 2 2 3 4 5 ( ) 3 3 2 min 3 2 7 2 4 4 12 4 3 3 8 10 0, 0, 0, 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x x x x x x                                        1 2 2 3 4 5 3 1 1 2 1 0 7 2 4 4 1 0 0 12 4 3 3 8 0 1 10 x x x x x x                                  CÁC DẠNG CỦA BÀI TOÁN QHTT Ví dụ 1.6. Cho bài toán QHTT: Ta có ma trận hệ số của hệ ràng buộc: chứa I3 nên bài toán quy hoạch tuyến tính trên có dạng chuẩn. 2 5 1 2 5 2 3 5 2 4 5 ( ) min 2 1 3 3 2 2 0 1,5j f x x x x x x x x x x x x x j                             11020 10130 20011 A Một phương án x* = (x1*, x2*,..., xn*) của bài toán QHTT dạng tổng quát là phương án cực biên (P.A.C.B) nếu x* = (x1*, x2*,..., xn*) thỏa mãn chặt n ràng buộc độc lập tuyến tính. Tức là: Trong đó A là ma trận con cấp n của hpt (*).  Một P.A.C.B không suy biến là một P.A.C.B thỏa mãn đúng n ràng buộc chặt.  Một P.A.C.B suy biến là một P.A.C.B thỏa mãn hơn n ràng buộc chặt. P.A.C.B còn được gọi là phương án cơ bản. ĐỊNH NGHĨA PHƯƠNG ÁN CỰC BIÊN             *X la P.A.C.B j n * ij i j=1 * j a x = b ,i=1,k,k m * k+l n,det A 0 x =0, j=1,l, l n Ví dụ 1.7. Cho bài toán QHTT Các vectơ nào sau đây là phương án cực biên? ĐỊNH NGHĨA PHƯƠNG ÁN CỰC BIÊN 1 2 3 1 2 3 1 1 2 3 1 2 3 2 3 ( ) 50 16 23 min 5 3 4 2 2 3 1 6 2 4 0 0 f x x x x x x x x x x x x x x x x                      0, 1, 3X   3, 0, 0Y  23 6 2, , 5 5 Z        ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 6 º Dễ dàng kiểm tra X không phải là phương án. Y, Z là phương án của bài toán. º Y thỏa 2 ràng buộc chặt (2 ràng buộc về dấu) nên Y chỉ là P.A. º Z thỏa 3 ràng buộc chặt (ràng buộc 2, ràng buộc 3, ràng buộc 4) và Vậy Z là phương án cực biên của bài toán. ĐỊNH NGHĨA PHƯƠNG ÁN CỰC BIÊN   1 0 0 det 1 1 3 1 6 5 0 6 2 1               ĐỊNH LÝ 1. (TÍNH ĐẶC TRƯNG CỦA P.A.C.B) Một phương án X* = (x1*, x2*,, xn*) của bài toán QHTT dạng chính tắc là phương án cực biên nếu và chỉ nếu hệ vectơ cột Aj ứng với thành phần xj* > 0 là độc lập tuyến tính. Ví dụ 1.8. Cho bài toán QHTT Các vectơ nào sau đây X = (2, 2, 0), Y = (0, 0, 4), Z = (1, 1, 2), là P.A.C.B của bài toán. CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT 1 2 3 1 2 3 1 2 ( ) 2 3 min 4 0 0, 1,3j f x x x x x x x x x x j                 X, Y, Z thỏa các ràng buộc nên chúng là P.A.  Mặt khác ta có  Với X = (2, 2, 0), nên X là P.A.C.B.  Với Y = (0, 0, 4), hệ chỉ gồm một vectơ A3 nên Y cũng là P.A.C.B.  Với Z=(1, 1, 2), ta thấy hệ {A1, A2, A3} phụ thuộc tuyến tính vì A1+A2–2A3=0 nên Z không là P.A.C.B. HỆ QUẢ 1. (tính hữu hạn của P.A.C.B). Sốù phương án cực biên của bài toán QHTT dạng chính tắc là hữu hạn. CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT 1 1 1 A        2 1 1 A       3 1 0 A        1 1 det 2 1 1        HỆ QUẢ 2. Sốù thành phần dương trong mỗi phương án cực biên của bài toán quy hoạch tuyến tính dạng chính tắc tối đa bằng m (m là số dòng của ma tận A). ĐỊNH LÝ 2. (SỰ TỒN TẠI CỦA PHƯƠNG ÁN TỐI ƯU) Nếu bài toán quy hoạch tuyến tính có phương án và hàm mục tiêu bị chặn dưới (đối với f(x) min) hoặc hàm mục tiêu bị chặn trên (đối với f(x) max) trên tập các phương án thì bài toán có phương án tối ưu. ĐỊNH LÝ 3. (SỰ TỒN TẠI CỦA P.A.C.B. TỐI ƯU) Nếu bài toán QHTT dạng chính tắc có P.A.T.Ư thì bài toán có P.A.C.B tối ưu (P.A.C.B.T.Ư). CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 7 ĐỊNH LÝ 4. (SỰ TỒN TẠI NHIỀU P.A.C.B.T.Ư) Nếu bài toán có P.A.T.Ư là Xopt và X (1), X(2) là 2 phương án khác nhau của bài toán thoả Xopt = X(1) + (1–)X(2), 0    1 thì X(1), X(2) là P.A.T.Ư. NHẬN XÉT 1. Ta có thể tìm P.A.T.Ư của bài toán QHTT trong số các P.A.C.B của bài toán và có thể xác định ngay P.A.C.B của bài toán dạng chuẩn bằng cách cho các ẩn không cơ bản bằng không (xem Ví dụ 1.9). 2. Trong bài toán QHTT dạng chính tắc. Nếu hạng của ma trận hệ số A là m thì P.A.C.B được gọi là không suy biến nếu nó có đúng m thành phần dương. Nếu P.A.C.B có ít hơn m thành phần dương thì được gọi là P.A.C.B suy biến (xem Ví dụ 1.10). CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT Ví dụ 1.9 . Với bài toán quy hoạch tuyến tính Ta có phương án X = (1, 0, 3, 2, 0) là phương án cực biên của bài toán vì các ẩn x1, x3, x4 là các ẩn cơ bản của bài toán dạng chuẩn. CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT 5,10 22 33 12 min)( 542 532 521 52      jx xxx xxx xxx xxxf j Ví dụ 1.10 . Với bài toán quy hoạch tuyến tính Kiểm tra vectơ X = (11, 3, 0, 0) có phải là P.A.C.B?  Kiểm tra trực tiếp, ta có X là P.A của bài toán.  Hạng của ma trận hệ số của hệ ràng buộc tuyến tính bằng 3 và X có 2 thành phần dương là x1 =11, x2 = 3 nên X là P.A.C.B suy biến. CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT 1 2 3 4 1 2 4 1 2 3 4 1 2 3 4 ( ) 3 4 2 2 min 2 2 28 5 3 2 26 2 2 2 16 0 1,4j f x x x x x x x x x x x x x x x x x j                   Ths. Nguyễn Công Trí Copyright 2001 CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 4.1. PHƯƠNG PHÁP HÌNH HỌC (Xem) 4.2. PHƯƠNG PHÁP ĐƠN HÌNH (Xem) 4.3.PHƯƠNG PHÁP ĐƠN HÌNH MỞ RỘNG (BÀI TOÁN M) (Xem) ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 8 ax+by=c PHƯƠNG PHÁP HÌNH HỌC Xét bài toán QHTT có 2 biến. ax+by>c ax+by<c O =m (đường mức) a b tăng giảm N(a,b) Ví dụ 1.11. Một công ty có 2 phân xưởng: PX1 và PX2 cùng sản xuất 2 loại sản phẩm A và B. Năng suất và chi phí sản xuất của mỗi PX trong 1 giờ: Đơn đặt hàng: ít nhất 5.000 SpA, 3.000 SpB. Hãy phân phối thời gian hoạt động của 2 phân xưởng sao cho thoả yêu cầu đơn đặt hàng và chi phí sản xuất thấp nhất. Phân xưởng Năng suất PX1 PX2 Sản phẩm A 250 250 Sản phẩm B 100 200 Chi phí (triệu đồng/ giờ) 0,6 1 PHƯƠNG PHÁP HÌNH HỌC Gọi x1, x2 lần lượt là số giờ hoạt động của phân xưởng thứ nhất và phân xưởng thứ hai. Ta có mô hình bài toán Dùng phương pháp hình học để giải bài toán trên như sau PHƯƠNG PHÁP HÌNH HỌC   1 2 1 2 1 2 1 2 0,6 min 250 250 5000 100 200 3000 0 0 f x x x x x x x x x            10 20 30 10 15 20 250x1+250x2=5000 100x1+200x2=3000 0,6x1+x2=m tăng giảm Miền ràng buộc D A1(0,20) A2(30,0) A3 (10,10) PHƯƠNG PHÁP HÌNH HỌC Vậy P.A.T.Ư: xopt(10,10) và f(xopt)=16 triệu đồng. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 9 Ví dụ 1.12. Giải bài toán quy hoạch tuyến tính bằng phương pháp hình học   1 2 1 2 1 2 1 2 2 min 2 2 2 0 0 f x x x x x x x x x                  PHƯƠNG PHÁP HÌNH HỌC Hàm mục tiêu không bị chặn. Bài toán không có phương án tối ưu. -2 2 2 x1-x2= -2 tăng giảm Miền ràng buộc D -1 -x1+2x2= -2 A1(0,2) A2(2,0)O -1 -2x1+x2= m PHƯƠNG PHÁP HÌNH HỌC Ví dụ 13: giải bài toán Đưa bài toán về dạng chính tắc 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 3 2 min 2 4 3 10 3 4 5 2 2 8 0 1,3j f x x x x x x x x x x x x x x j                     CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 1 2 3 1 2 3 1 1 2 3 2 1 2 3 3 ( ) 3 2 min 2 4 3 10 3 4 5 2 2 8 0, 1,3, 0, 1,3j i f x x x x x x x w x x x w x x x w x j w i                          Ta có P.A.C.B là x = (0, 0, 0, 10, 5, 8) Bài toán tương đương có P.A.C.B là x = (0, 0, 0, 10, 5, 8) và f(x) = 0. Nhận xét: có thể đổi P.A bằng cách tăng x1 bằng một giá trị dương và giử x2 = x3 = 0 thỏa điều kiện wi ≥ 0. CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 ( ) 3 2 min 10 2 4 3 5 3 4 8 2 2 0 1,3, 0, 1,3j i f x x x x w x x x w x x x w x x x x j w i                          ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 10 Ta có Chọn x1 = 5/3, ta được P.A mới là x1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3. Và f(x) = - 5. Bài toán tương đương: tại ràng buộc thứ hai tính x1 theo các biến còn lại, rồi thế giá trị x1 vừa tính được vào các ràng buộc và hàm mục tiêu. CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 1 1 1 2 1 1 1 3 1 1 5 10 2 0 5 5 5 3 0 3 3 8 0 8 x w x w x x x w x x                     (Chọn dòng 2) Ta có kết quả Nhận xét: có thể đổi P.A bằng cách tăng x2 bằng một giá trị dương và giử x3 = w2 = 0 thỏa điều kiện wi ≥ 0. CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 2 2 3 1 2 2 3 1 2 2 3 3 2 2 3 ( ) 5 3 min 20 2 10 1 3 3 3 3 5 1 1 4 3 3 3 3 19 1 5 2 3 3 3 3 0 1,3, 0, 1,3j i f x w x x w w x x x w x x w w x x x j w i                              Ta có Chọn x2 = 2, ta được P.A mới là x1 = 1, x3 = w1 = w2 = 0, w3 = 3 và f(x) = - 7. Bài toán tương đương: tại ràng buộc thứ nhất tính x2 theo các biến còn lại, rồi thế giá trị x2 vừa tính được vào các ràng buộc và hàm mục tiêu. CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 1 1 2 1 2 2 2 2 3 2 20 10 0 3 3 2 5 1 0 5 2 3 3 19 19 5 0 5 3 3 w x x x x x x x w x                           (Chọn dòng 1) Ta có kết quả Bài toán có P.A.T.U là xopt = (1, 2, 0) và f(xopt) = - 7 CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 1 2 3 2 1 2 3 1 1 2 3 3 1 3 3 4 31 ( ) 7 min 10 5 10 3 1 1 2 10 5 10 1 6 39 1 10 15 30 1 2 3 2 3 0 1,3, 0, 1,3j i f x w w x x w w x x w w x w w x x j w i                             ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 11        1 , 1 ( ) min max 1 2 0 1, 0 3 n j j j n m i i m k m k i k j i f x c x hay x a x b x j n b                  CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH 0 0 1 2 1 ( , , ; ,.0 ,0) ( ) m m i i i x b b b f x c b      1 1 1 ( ) n m n m j j i i m k m k j i k f x c x c x c x            1 2, ( , , , )nx D x x x x   Dựa trên cơ sở bài toán có dạng chuẩn  Dấu hiệu tối ưu của bài toán Phương án cực biên đầu tiên là: Chọn một P.A bất kỳ của bài toán CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH   , 1 1 1 m n m m i i i m k i m k m k i k i f x c x a c c x                    , 1 2 , n m i i i m k m k k x b a x        , 1        m m k i m k i m k i a c c    0 1 n m m k m k k f x f x x        0 m k    0 ,f x f x 0m kx   0 m k    0 ,f x f x 0m kx   1    m j ij i j i a c c ( ) f x Min 0;  j j ( ) f x Max 0;  j j Đặt thì  Nếu thì vì  Nếu thì vì Ký hiệu lại: (1) Khi thì (2) Khi thì  Dấu hiệu bài toán không có P.A.T.Ư Định lý. Với một phương án cực biên, nếu tồn tại j > 0 mà aij ≤ 0, i thì bài toán không có P.A.T.Ư. (xem Ví dụ 1.13) CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH Hệä sốá Aåån C.B PA CB C1 C2 ... Ci ... Cm Cm+1 ... Cj ... Cn x1 x2 ... xi ... xm xm+1 ... xj ... xn C1 x1 b1 1 0 ... ... ... 0 a1,m+1 ... a1j ... a1n C2 x2 b2 0 1 ... ... ... 0 a2,m+1 ... a2j ... a2n ... ... ... ... ... ... ... ... ... ... ... ... ... ... Ci xi bi 0 0 ... ... ... 0 ai,m+1 ... aij ... ain ... ... ... ... ... ... ... ... ... ... ... ... ... ... Cm xm bm 0 0 ... ... ... 1 am,m+1 ... amj ... amn f(x) f(x0) 0 0 ... ... ... 0 m+1 ... j ... n Hệä sốá Aåån C.B PA CB C1 C2 ... Ci ... Cm Cm+1 ... Cj ... Cn x1 x2 ... xi ... xm xm+1 ... xj ... xn C1 x1 b1 1 0 ... ... ... 0 a1,m+1 ... a1j ... a1n C2 x2 b2 0 1 ... ... ... 0 a2,m+1 ... a2j ... a2n ... ... ... ... ... ... ... ... ... ... ... ... ... ... Ci xi bi 0 0 ... ... ... 0 ai,m+1 ... aij ... ain ... ... ... ... ... ... ... ... ... ... ... ... ... ... Cm xm bm 0 0 ... ... ... 1 am,m+1 ... amj ... amn f(x) f(x0) 0 0 ... ... ... 0 m+1 ... j ... n  Dấu hiệu bài toán có P.A.C.B. khác tốt hơn Định lý. Với một P.A.C.B, nếu j>0, i: aij > 0 thì bài toán có P.A.C.B khác tốt hơn P.A.C.B đang xét. CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 12 BẢNG ĐƠN HÌNH Hệä sốá Aåån C.B PA CB C1 C2 ... Ci ... Cm Cm+1 ... Cj ... Cn x1 x2 ... xi ... xm xm+1 ... xj ... xn C1 x1 b1 1 0 ... ... ... 0 a1,m+1 ... a1j ... a1n C2 x2 b2 0 1 ... ... ... 0 a2,m+1 ... a2j ... a2n ... ... ... ... ... ... ... ... ... ... ... ... ... ... Ci xi bi 0 0 ... ... ... 0 ai,m+1 ... aij ... ain ... ... ... ... ... ... ... ... ... ... ... ... ... ... Cm xm bm 0 0 ... ... ... 1 am,m+1 ... amj ... amn f(x) f(x0) 0 0 ... ... ... 0 m+1 ... j ... n j ≤ 0,j? THUẬT GIẢI ĐƠN HÌNH Sai Đúng Sai Đúng LẬP BẢNG ĐƠN HÌNH XÁC ĐỊNH PHƯƠNG ÁN MỚI Aån vào: Aån ra: P.A.T.Ư KẾT THÚC THUẬT GIẢI aij ≤ 0,i? BÀI TOÁN KHÔNG CÓ P.A.T.Ư BIẾN ĐỔI BẢNG ĐƠN HÌNH 0j j jMax x     0ij i i a ij b Min x a     SỐ BƯỚC LẶP LÀ HỮU HẠN THUẬT GIẢI ĐƠN HÌNH Thuật giải gồm 4 bước: Bước 1: Lập bảng đơn hình Bài toán phải ở dạng chuẩn, đưa các số liệu vào bảng đơn hình. Bước 2: Kiểm tra tính tối ưu của bài toán Tính j = ∑aijci – cj  Nếu j ≤ 0: bài toán có P.A.T.U.  Nếu j > 0: chuyển sang bước 3. Bước 3: Kiểm tra tính giải được của bài toán  Nếu aij ≤ 0, i: bài toán không có P.A.T.U.  Nếu aij > 0: chuyển sang bước 4. THUẬT GIẢI ĐƠN HÌNH Bước 4: Tìm P.A.C.B mới của bài toán  Chọn ẩn vào: Chọn Maxj (j > 0), ẩn xj sẽ được chọn đưa vào hệ ẩn cơ bản ứng với j đã được chọn.  Chọn ẩn ra: Chọn  = Min{bi/aij} (aij > 0), ẩn xi sẽ được chọn đưa ra khỏi hệ ẩn cơ bản ứng với  nhỏ nhất. Phần tử aij (ứng với ẩn vào xi và ẩn ra xj) được gọi là phần tử trục.  Dùng phương pháp biến đổi sơ cấp dòng trên ma trận hệ số để biến đổi ẩn mới đưa vào trở thành ẩn cơ bản. Sau đó quay về bước 2. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 13 THUẬT GIẢI ĐƠN HÌNH NHẬN XÉT. Dấu hiệu bài toán có nhiều P.A.T.Ư. Với P.A.C.B.T.Ư Xopt tìm được, nếu j = 0, mà xj không là P.A.C.B thì bài toán có P.A.C.B.T.Ư khác X/opt (xem Ví dụ 1.15). Tập phương án tối ưu:  Trường hợp có hai P.A.C.B.T.Ư là Xopt và X / opt Topt = {Xopt + (1 – )X / opt, [0, 1]}  Trường hợp có 3 P.A.C.B.T.Ư X(1)opt, X (2) opt, X (3) opt Topt = { X (1) opt + X (2) opt + X (3) opt, }, với , ,   0 và  +  +  = 1. 1 2 3 4 5 6 7 1 2 4 6 7 1 3 4 6 7 1 4 5 6 ( ) 6 3 7 6 min 3 2 4 2 9 4 2 3 2 0 1,7j f x x x x x x x x x x x x x x x x x x x x x x x j                           Ví dụ 1.14. Giải bài toán quy hoạch tuyến tính THUẬT GIẢI ĐƠN HÌNH BT không có P.A.T.Ư vì 4= 1 > 0 mà ai4 < 0, i. HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 6x 7x 6 1 1 3 1 7 6 2x 3x 5x 1 1 1 3 9 2 1 2 4 1 0 0 1 1 4 2 2 3 1  f x 14 5 0 0 6 0 7 6 0 0 0 0 0 1 1 1 6x 3x 5x 7 1 1 3 1 1 0 1 0 1 1 3 0 2 1 2 0 30 11 1 3 0 1 0 31  f x 7 2 7 0 1 0 0 13 THUẬT GIẢI ĐƠN HÌNH Ví dụ 1.15. Giải bài toán quy hoạch tuyến tính Bài toán có phương án tối ưu khác hay không? Nếu có tìm tập phương án tối ưu và chỉ ra 3 phương án tối ưu. 1 2 3 4 5 6 1 2 3 4 1 2 3 5 1 3 6 ( ) 5 4 5 2 3 min 2 4 3 152 4 2 3 60 3 36 0 1,6j f x x x x x x x x x x x x x x x x x x x j                     THUẬT GIẢI ĐƠN HÌNH ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 14 HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 5x 6x 2 1 3 152 60 36 2 4 3 4 2 0 1 3 3 1 0 0  f x 472 12 6 7 0 0 0 0 0 0 01 1 4x 5x 1x 2 1 5 128 0 4 7 3 1 0 2 3 12 0 2 53 0 4 31 12 1 0 13 0 130  f x 328 0 6 3 0 0 4 THUẬT GIẢI ĐƠN HÌNH Bài toán có P.A.T.Ư xopt=(12, 6, 0, 104, 0, 0) và f(xopt)= 292. Bài toán còn P.A.C.B.T.Ư khác vì 6 = 0, nhưng x6 không phải là A.C.B. Ta có P.A.C.B.T.Ư thứ hai bằng cách chọn ẩn x6 là ẩn đưa vào. HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 2x 1x 2 4 5 104 0 0 1 1 2 2 6 0 1 5 6 0 2 312 12 1 0 13 0 130  f x 292 0 0 2 0 3 0 THUẬT GIẢI ĐƠN HÌNH Bài toán có phương án cực biên tối ưu khác là x/opt = (0, 30, 0, 32, 0, 36) và f(x / opt) = 292. Tập phương án tối ưu Topt={xopt + (1 - )x / opt, 0, 1} HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 2x 6x 2 4 3 32 6 0 3 1 2 0 30 2 1 3 2 0 012 36 3 0 1 0 10  f x 292 0 0 2 0 3 0 THUẬT GIẢI ĐƠN HÌNH Với tập phương án tối ưu, ta có : xopt + (1 - )x / opt = (12, 6, 0, 104, 0, 0) + (1-)(0, 30, 0, 32, 0, 36) = (12 , 30–24, 0, 32 + 72, 0, 36 - 36) 3 phương án tối ưu là  Với  = 0, ta có P.A.T.Ư: x/opt = (0, 30, 0, 32, 0, 36) và f(x / opt) = 292.  Với  = 1, ta có P.A.T.Ư: xopt = (12, 6, 0, 104, 0, 0) và f(x / opt) = 292.  Với  = ½, ta có P.A.T.Ư: Zopt = (6, 18, 0, 68, 0, 18) và f(zopt) = 292. THUẬT GIẢI ĐƠN HÌNH ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 15 NHẬN XÉT. Nếu bài toán có hàm mục tiêu Có hai cách giải:  Giải trực tiếp bài toán (xem Ví dụ 1.16), với:  Tiêu chuẩn tối ưu là •  Ẩn vào là •  Ẩn ra là  Chuyển hàm mục tiêu của bài toán về min 1 ( )    n j j j f x c x Max ( ) ( )  g x f x Min 0,  j j 0   j jMin THUẬT GIẢI ĐƠN HÌNH 0ij i a ij b Min a Ví dụ 1.16. Giải bài toán quy hoạch tuyến tính Bài toán có phương án tối ưu khác hay không? Nếu có, hãy chỉ ra phương án tối ưu khác. 1 2 3 4 1 2 3 4 2 3 4 3 4 ( ) 2 max 2 2 7 3 2 3 2 5 0 1,4j f x x x x x x x x x x x x x x x j                    THUẬT GIẢI ĐƠN HÌNH Đưa bài toán về dạng chính tắc bằng cách thêm ẩn phụ x5 ≥ 0 vào ràng buộc thứ hai và ẩn phụ x6 ≥ 0 vào ràng buộc thứ ba. Ta có bài toán ở dạng chuẩn Lập bảng đơn hình 1 2 3 4 1 2 3 4 2 3 4 5 3 4 6 ( ) 2 max 2 2 7 3 2 3 2 5 0 1,6j f x x x x x x x x x x x x x x x x x j                     THUẬT GIẢI ĐƠN HÌNH HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 6x 2 1 1 1 0 0 1x 5x 6x 2 0 0 2 2 5 1 0 0 1 1 0 1 2 7 3 3 2  f x 4 0 1 5 1 0 0 0 0 0 01 1 3x 5x 6x 1 0 0 1 12 12 1 12 0 0 9 7 2 5 2 0 12 01 8 3 2 3 2 0 12 10  f x 1 5 2 3 2 0 3 2 0 0 THUẬT GIẢI ĐƠN HÌNH ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 16 Vì các j  0, j nên bài toán có P.A.T.Ư là Xopt = (0, 0, 9, 16) và f(Xopt) = 25. Bài toán trên không còn phương án tối ưu nào khác vì không có j = 0 nào với xj là ẩn không cơ bản. HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 6x 2 1 1 1 0 0 3x 5x 4x 1 0 1 9 2 2 1 0 0 1 17 5 4 0 0 11 16 3 3 0 1 20  f x 25 7 6 0 0 0 3 THUẬT GIẢI ĐƠN HÌNH Xuất phát từ bài toán dạng chính tắc Không làm mất tính tổng quát của bài toán, ta giả sử các bi  0 và ma trận hệ số của hệ ràng buộc không chứa vectơ (cột) đơn vị nào. Cộng vào mỗi ràng buộc với một ẩn giả tương ứng xi (g) ≥ 0 thì ta được bài toán có dạng: CƠ SỞ THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG   1 1 ( ) , 1, 0 1, 0               n j j j n ij j i j j i f x c x Min a x b i m I x j n b Bài toán (I) được gọi là bài toán gốc, bài toán (II) gọi là bài toán mở rộng hay bài toán M. Một phương án của bài toán M có dạng trong đó xj gồm n ẩn thật và xi (g) gồm m ẩn giả. CƠ SỞ THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG   1 1 1 ( ) , 1, 0, 1, ; 0, 1, , 0 vo âcùng lớn.                     n m g j j i j i n g ij j i i j g j i f x c x M x Min a x x b i m II x j n x i m M  , gj ix x x Trong đó các xn+i (i = 1, 2, ..., m) là các ẩn giả. Hệä Sốá ẨÅn C.B PA CB C1 C2 Cm Cm+1 Cj Cn x1 x2 xm xm+1 xj xn M xn+1 b1 a11 a12 a1m a1,m+1 a1j a1,n M x n+2 b2 a21 a22 a2m a2,m+1 a2j a2,n M x n+i bi ai1 ai2 aim ai,m+1 aij ai,n M xn+m bm am1 am2 amm am,m+1 amj am,n f(x) f(x0) 1 2 m m+1 j n BẢNG ĐƠN HÌNH MỞ RỘNG ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 17 NHẬN XÉT. Khi thuật giải của bài toán M kết thúc thì có hai trường hợp sau đây có thể xảy ra: [1] Nếu bài toán M (Bài toán II) không có phương án tối ưu thì bài toán gốc (Bài toán I) cũng không có phương án tối ưu. [2] Nếu bài toán M (Bài toán II) có phương án tối ưu thì có 3 trường hợp xảy ra sau đây: a) Trong hệ A.C.B không chứa ẩn giả nào thì P.A.T.Ư của bài toán M cũng chính là P.A.T.Ư của bài toán gốc (xem Ví dụ 1.17). CƠ SỞ THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG b) Nếu trong hệ ẩn cơ bản của bài toán M có chứa ẩn giả nhưng giá trị của chúng đều bằng không thì P.A.T.Ư của bài toán gốc là P.A.T.Ư. của bài toán M loại bỏ các ẩn giả bằng không (xem Ví dụ 1.18). c) Nếu trong hệ ẩn cơ bản của bài toán M có một ẩn giả mà giá trị của chúng khác không thì bài toán gốc không có P.A.T.Ư. Chú ý. Nếu hàm mục tiêu là f(x)  Max thì hệ số các ẩn giả trong hàm mục tiêu của bài toán M là (– M), với M > 0 vô cùng lớn (xem Ví dụ 1.19). CƠ SỞ THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG Đúng Sai aij ≤ 0? Sai Đúng Không CóĐúng j ≤ 0? THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG Sai LẬP BẢNG ĐƠN HÌNH Xác định phương án mới Aån vào: Aån ra: CÓ P.A.T.Ư ĐƯA BÀI TOÁN VỀ DẠNG CHUẨN KHÔNG CÓ P.A.T.Ư KẾT THÚC THUẬT GIẢI CÓ P.A.T.Ư BIẾN ĐỔI BẢNG ĐƠN HÌNH ?gix 0? g ix KHÔNG CÓ P.A.T.Ư 0j jMax    0ij i a ij b Min a    SỐ BƯỚC LẶP LÀ HỮU HẠN Ví dụ 1.17. (trường hợp a). Giải bài toán QHTT Nhân (– 1) vào ràng buộc thứ nhất, bài toán có dạng chính tắc như sau 1 2 3 1 2 3 1 2 3 ( ) 8 6 2 min 4 4 3 18 4 3 4 16 0 1,3j f x x x x x x x x x x x j                THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG 1 2 3 1 2 3 1 2 3 ( ) 8 6 2 min 4 4 3 18 4 3 4 16 0 1,3j f x x x x x x x x x x x j              ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 18 Đưa bài toán về dạng chuẩn: Thêm hai ẩn giả x4 ≥ 0 và x5 ≥ 0 vào lần lượt vào ràng buộc thứ nhất và thứ hai của bài toán Bài toán có dạng chuẩn như sau: Ta có bảng đơn hình mở rộng 1 2 3 4 5 1 2 3 4 1 2 3 5 ( ) 8 6 2 ( ) 4 4 3 18 4 3 4 16 0 1,5 M 0 vo â cùng lớn.                 j f x x x x M x x Min x x x x x x x x x j THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG Bài toán có P.A.T.Ư Xopt=(5/2, 2, 0), f(Xopt)= –8. HỆ SỐ ẨN C.B P.A 1x 2x 3x 8 6 2 4x 5x M M 18 16 4 4 4 3 3 4  f x 34M 8 8M  7 6M  2M  4x 1x M 8 2 0 1 7 4 1 3 4 1  f x 2 32M  0 12M  7 10M  THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG 2x 1x 6 8 2 5 2 0 1 1 0 7 25 4  f x 8 0 0 94 Ví dụ 1.18. (trường hợp b). Giải bài toán QHTT Thêm ẩn phụ x4  0 vào ràng buộc thứ nhất 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 6 3 min 2 5 10 4 3 2 16 2 4 8 0 1,3j f x x x x x x x x x x x x x x j                    THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG 1 2 3 1 2 3 4 1 2 3 1 2 3 ( ) 6 3 min 2 5 10 4 3 2 16 2 4 8 0 1,4j f x x x x x x x x x x x x x x x j                     Thêm hai ẩn giả x5 ≥ 0, x6 ≥ 0 lần lượt vào ràng buộc thứ hai và ràng buộc thứ ba. Ta có bài toán dạng chuẩn như sau Ta có bảng đơn hình mở rộng 1 2 3 5 6 1 2 3 4 1 2 3 5 1 2 3 6 ( ) 6 3 ( ) min 2 5 4 3 2 2 4 0 1 1 6 , 0 8 6 1 j f x x x x M x x x x x x x x x x x x x x x j                     M 0 THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 19 HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 6 3 1 0 4x 5x 6x 0 M M 10 16 8 2 4 2 5 3 1 2 1 0 0  f x 24M 6 6M  3M  3 1M  0 4 1 4x 5x 1x 0 M 6 2 0 1 0 1 0 0 11 0 0 4 1 2 12 0  f x 24 0 11 9M  2 0 THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG P.A.T.Ư của BTM là với ẩn giả x5 = 0 P.A.T.Ư của BT gốc là xopt = (0, 0, 8) và f(xopt) = 8. HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 6 3 1 0 4x 5x 3x 0 M 1 2 0 1 0 1 0 0 11 0 0 8 2 4 1 0  f x 8 4 11 1M  0 0  0, 0, 8, 2, 0, 0x  THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG Ví dụ 1.19. (trường hợp c). Giải bài toán QHTT Thêm 2 ẩn phụ x4, x5 ≥ 0 vào ràng buộc (1) & (2) 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 2 max 4 2 12 2 2 10 2 1 2 10 0 1,3j f x x x x x x x x x x x x x x j                       THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG 1 2 3 1 2 3 4 1 2 3 5 1 2 3 ( ) 2 max 4 2 12 2 2 10 2 1 2 10 0 1,5j f x x x x x x x x x x x x x x x x j                         Thêm 2 ẩn giả vào x6, x7  0 lần lượt vào ràng buộc (1) & (3). Ta có bài toán dạng chuẩn như sau Ta có bảng đơn hình mở rộng  1 2 3 6 7 1 2 3 4 6 1 2 3 5 1 2 3 7 ( ) 2 max 4 2 12 2 2 10 1 2 10 2 0 1,7j f x x x x M x x x x x x x x x x x x x x x x j                        M 0 THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 20 P.A.T.Ư Xopt = (0, 0, 6, 0, 16, 0, 13), với x7 = 13  0 nên bài toán gốc không có P.A.T.Ư. 1 1 2 4M  HỆ SỐ ẨN C.B P.A 1x 2x 3x 4x 5x 2 1 1 0 0 6x 5x 7x M 0 M 12 10 10 4 2 1 1 2 0 1 2 1 1 2  0 0  f x 22M 3 2M  3 1M  3 2 1M  M 0 2 0 1 3x 5x 7x 1 0 M 6 2 12 1 12 0 16 4 3 2 0 12 1 13 0 9 4 0 14 0  f x 6 13M 0 912 4M 0 0 THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG BÀI TẬP CHƯƠNG 1 LẬP MÔ HÌNH BÀI TOÁN [1] [2] [3] [4] BÀI TOÁN QHTT DẠNG CHÍNH TẮC [5a] [5b] XÁC ĐỊNH P.A – P.A.C.B VÀ P.A.T.Ư. [6] [7a] [7b] [7c] GIẢI BÀI TOÁN QHTT BẰNG PP HÌNH HỌC [8a] [8b] [8c] GIẢI BÀI TOÁN QHTT BẰNG PP ĐƠN HÌNH [9] [10] [11] [12] [13] [14] [15] [16] [17] 1. Một xí nghiệp chế biến đồ gỗ hiện có 3.000 đơn vị gỗ nguyên liệu nhóm I, 5.000 đơn vị gỗ nguyên liệu nhóm II và 2.000 đơn vị gỗ nguyên liệu nhóm III. Theo kế hoạch xí nghiệp phải sản xuất bốn loại hàng hoá với định mức nguyên liệu và lợi nhuận được thể hiện trong bảng sau Hãy lập mô hình bài toán sao cho xí nghiệp đạt lợi nhuận nhiều nhất? BÀI TẬP CHƯƠNG 1 Sảûn phẩåm Định mứùc Nguyêân liệäu Bộä tủû Bộä cửûa Bộä sa-lôâng Bộä giườøng ngủû Gỗã nhóùm I 30 40 0 10 Gỗã nhóùm II 10 20 50 60 Gỗã nhóùm III 10 50 80 20 Lợïi nhuậän (triệäu đồàng) 0,5 0,8 0,4 0,6 1.Gọi xj (j=1, 2, 3, 4) lần lượt là số lượng bộ tủ, bộ cửa, bộ sa–lông và bộ giường ngủ do xí nghiệp sản xuất. Mô hình của bài toán f(x) = 0,5x1 + 0,8x2 + 0,4x3 + 0,6x4  Max Với các ràng buộc về nguyên liệu 30x1 + 40x2 + +10x4 ≤ 3000, 10x1 + 20x2 + 50x3 + 60x4 ≤ 5000, 10x1 + 50x2 + 80x3 + 20x4 ≤ 2000, Ràng buộc các ẩn số xj ≥ 0 , j = 1, 2, 3, 4 BÀI TẬP CHƯƠNG 1 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 21 2. Một công ty có kế hoạch quảng cáo một loại sản phẩm do công ty sản xuất trong thời gian một tháng với tổng chi phí là 100 triệu đồng. Các phương tiện được chọn để quảng cáo sản phẩm với số liệu được dự kiến như sau: Công ty yêu cầu phải có ít nhất 30 lần quảng cáo trên truyền hình trong tháng. Hãy lập mô hình bài toán sao cho phương án quảng cáo sản phẩm của công ty là tối ưu. BÀI TẬP CHƯƠNG 1 Phương tiện quảng cáo Chi phí mỗi lần quảng cáo (triệu Đ) Số lần quảng cáo tối đa trong tháng Dự đoán số người xem quảng cáo Truyền hình (1 phút) 1,5 60 15.000 Báo (1/2 trang) 1 26 30.000 Phát thanh (1 phút) 0,5 90 9.000 3. Một xí nghiệp có thể sử dụng tối đa 510 giờ máy cán, 360 giờ máy tiện và 150 giờ máy mài để chế tạo 3 sản phẩm A, B và C. Để chế tạo một sản phẩm A cần 9 giờ máy cán, 5 giờ máy tiện và 3 giờ máy mài; một sản phẩm B cần 3 giờ máy cán, 4 giờ máy tiện; một sản phẩm C cần 5 giờ máy cán, 3 giờ máy tiện và 2 giờ máy mài. Mỗi sản phẩm A trị giá 48 ngàn đồng, mỗi sản phẩm B trị giá 16 ngàn đồng và mỗi sản phẩm C trị giá 27 ngàn đồng. Hãy lập mô hình bài toán xí nghiệp cần chế tạo mỗi loại bao nhiêu sản phẩm để có tổng giá trị sản phẩm lớn nhất. BÀI TẬP CHƯƠNG 1 4. Một xí nghiệp vận tải cần chuyển một loại hàng hóa từ ba kho hàng A1, A2 và A3 đến bốn cửa hàng B1, B2, B3 và B4. Chi phí vận chuyển một đơn vị hàng hóa từ kho Ai (i = 1, 2, 3) đến cửa hàng Bj (j = 1, 2, 3, 4) được cho ở bảng sau Hãy lập mô hình bài toán vận tải hàng hóa sao cho tổng chi phí vận tải bé nhất? BÀI TẬP CHƯƠNG 1 Cửûa hàøng Chi phí vậän chuyểån Kho B1 B2 B3 B4 Lượïng hàøng hiệän cóù (tấán) A1 3 4 0 1 40 A2 1 2 5 6 30 A3 1 5 8 2 30 Nhu cầàu củûa cửûa hàøng (tấán) 20 25 30 15 5. a) Đưa bài toán quy hoạch tuyến tính sau đây về dạng chính tắc Thêm 2 ẩn phụ x4, x5  0 vào ràng buộc thứ hai, thứ ba và x3 = x / 3 – x // 3, với x/3  0, x // 3  0, ta có bài toán dạng chính tắc BÀI TẬP CHƯƠNG 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ( ) 4 3 2 min 4 6 2 3 8 3 4 2 3 0, 0 f x x x x x x x x x x x x x x x                    1 2 3 3 1 2 3 3 1 2 3 3 4 1 2 3 3 5 1 2 3 3 4 5 ( ) 4 3 2 2 min 4 4 6 2 3 3 8 3 4 2 2 3 0, 0 0, 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x x x x x x                                   ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 22 5. b) Đưa bài toán quy hoạch tuyến tính sau đây về dạng chính tắc Thêm 2 ẩn phụ x4, x5  0 vào ràng buộc thứ nhất, thứ ba và x2 = x / 2 – x // 2, với x/2  0, x // 2  0, ta có bài toán dạng chính tắc BÀI TẬP CHƯƠNG 1 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 2 3 max 4 2 15 5 2 10 3 6 2 25 0, 0 f x x x x x x x x x x x x x x x                    1 2 2 3 1 2 2 3 4 1 2 2 3 1 2 2 3 5 1 2 2 3 4 5 ( ) 2 3 3 min 4 2 2 15 5 2 2 10 3 6 6 2 25 0, 0 0, 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x x x x x x                                   6. Cho bài toán QHTT sau đây Xét các véctơ X = (0, 0, 0, 8), Y = (14, 0, 0, 1), Z = (7, 0, 0, 9/2) và T = (16, 1, 0, ½) (a) Vectơ nào là P.A; vectơ nào là P.A.C.B? (b) Cho biết Y là P.A.T.Ư. Trong các vectơ còn lại, vectơ nào là P.A.T.Ư của bài toán trên? BÀI TẬP CHƯƠNG 1 2 3 4 2 3 4 2 3 2 3 4 j 3 7 2 max 3 2 30 2 2 3 60 2 2 3 + 4 32 x 0 (j 1,4) x x x x x x x x x x x                  1 1 1 1 f(x) x 2x x x (a) Các vectơ X, Y, Z và T là P.A của bài toán vì chúng thỏa hệ ràng buộc.  Với X = (0, 0, 0, 8) thỏa 4 ràng buộc chặt, ta có Vậy X là P.A.C.B không suy biến.  Tương tự, Y = (14, 0, 0, 1) là P.A.C.B không suy biến. Z và T không phải là P.A.C.B. (b) Với Y là P.A.T.Ư, ta có f(Y) = 40, ta có f(X) = – 16  f(Y), f(Z) = 12  f(Y) và f(T) = 40 = f(Y). Vậy T là P.A.T.Ư. BÀI TẬP CHƯƠNG 1 2 2 3 4 1 0 0 1 0 0 0 det 4det 0 1 0 4 0 1 0 0 0 0 1 0 0 1 0                       7. a) Tìm P.A.C.B không suy biến của bài toán  cho x1 = 0, ta có hệ phương trình vô nghiệm.  cho x2 = 0, giải hpt, ta có x1 = 2, x3 = 1. Kiểm tra trực tiếp phương án X = (2, 0, 1) là P.A.C.B không suy biến.  cho x3 = 0, ta có Y = (2, 1, 0). Kiểm tra trực tiếp phương án Y là P.A.C.B không suy biến. BÀI TẬP CHƯƠNG 1 1 2 3 1 2 3 1 2 3 ( ) 4 3 2 min 1 3 0, 1,2,3j f x x x x x x x x x x x j                ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 23 7. b) Tìm P.A.C.B không suy biến của bài toán BÀI TẬP CHƯƠNG 1 1 2 3 1 2 3 1 2 3 ( ) 4 3 2 min 10 2 3 14 0, 1, 2,3j f x x x x x x x x x x x j                7. c) Tìm P.A.C.B không suy biến của bài toán BÀI TẬP CHƯƠNG 1 1 2 3 1 2 3 1 2 ( ) 4 3 2 min 4 0 0, 1,2,3j f x x x x x x x x x x j               8. a) Giải bài toán bằng phương pháp hình học BÀI TẬP CHƯƠNG 1 1 2 1 2 1 2 1 2 ( ) max 1 3 2 6 3 9 0, 1,2j f x x x x x x x x x x j                8. b) Giải bài toán bằng phương pháp hình học BÀI TẬP CHƯƠNG 1 1 2 1 2 1 2 1 2 ( ) 5 4 max 2 8 2 4 3 2 12 0, 1, 2j f x x x x x x x x x x j               ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 24 8. c) Giải bài toán bằng phương pháp hình học BÀI TẬP CHƯƠNG 1 1 2 1 2 1 2 1 2 ( ) 5 3 min 2 6 0 2 0 0, 1,2j f x x x x x x x x x x j               9. Giải bài toán QHTT sau đây BÀI TẬP CHƯƠNG 1 1 2 4 5 6 1 4 5 6 2 4 6 3 4 5 6 ( ) 2 2 3 min 2 12 2 4 3 9 0 1,6j f x x x x x x x x x x x x x x x x x x j                     10. Giải bài toán QHTT sau đây BÀI TẬP CHƯƠNG 1 7,10 2021711 1 2 1 4 1 3 3 4 1 2 2 1 max343)( 76541 65431 5421 4321      jx xxxxx xxxxx xxxx xxxxxf j 11. Giải bài toán QHTT sau đây BÀI TẬP CHƯƠNG 1 6,10 10824 1242 723 min22)( 6532 432 5321 532      jx xxxx xxx xxxx xxxxf j ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 25 12. Giải bài toán QHTT sau đây Thêm 3 ẩn phụ x4, x5, x6  0 vào 3 ràng buộc, ta có bài toán dạng chuẩn như sau BÀI TẬP CHƯƠNG 1 1 2 3 1 2 3 1 2 3 1 3 ( ) 3 min 2 1 4 2 2 3 5 0 1,3j f x x x x x x x x x x x x x j                                  1 2 3 1 2 3 4 1 2 3 5 1 3 6 ( ) 3 min 2 1 4 2 2 3 5 0 1,6j f x x x x x x x x x x x x x x x x j 13. Giải bài toán QHTT sau đây Đưa bài toán về dạng chính tắc BÀI TẬP CHƯƠNG 1 4,10 16222 31235 2822 min2243)( 4321 4321 421 4321      jx xxxx xxxx xxx xxxxxf j 1 2 3 4 1 2 4 1 2 3 4 5 1 2 3 4 ( ) 3 4 2 2 min 2 2 28 5 3 2 31 2 2 2 16 0 1,5j f x x x x x x x x x x x x x x x x x x j                    14. Giải bài toán QHTT sau đây BÀI TẬP CHƯƠNG 1 4,10 102 2052 1532 min32)( 4321 321 321 4321      jx xxxx xxx xxx xxxxxf j 15. Giải bài toán QHTT sau đây BÀI TẬP CHƯƠNG 1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 ( ) 3 2 2 min 2 4 10 3 2 2 8 4 2 4 0 1,4j f x x x x x x x x x x x x x x x x x j                    ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 1 26 16. Giải bài toán QHTT sau đây BÀI TẬP CHƯƠNG 1 6,10 2 2 1 423 3 2 1 3 1 2 4226 min52)( 654321 54321 654321 65421      jx xxxxxx xxxxx xxxxxx xxxxxxf j 17. Dùng phương pháp đơn hình giải các bài toán từ bài tập [1] đến bài tập [8]. BÀI TẬP CHƯƠNG 1