Bài giảng Toán tài chính - Chương 5b: Quy hoạch tuyến tính hai biến

QUY HOẠCH TUYẾN TÍNH HAI BIẾN + CHƯƠNG 5B VÍ DỤ 1 Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền lãi cho một bánh mỗi loại được cho trong bảng sau: Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho không bị động về nguyên liệu mà lãi đạt được cao nhất. VÍ DỤ 1 Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập cẩm, bánh dẻo cần phải sản xuất. Điều kiện: xj ≥ 0 = 1,2,3 Tiền lãi thu được (ngàn đồng) Lượng đường sử dụng và điều kiện: Lượng đậu sử dụng và điều kiện:    1 2 3 1 2 3, , 3 2 2,5f x f x x x x x x    1 2 30,04 0,06 0,05 500x x x   1 30,07 0,02 300x x  VÍ DỤ 1 Vậy ta có mô hình bài toán: Đây là bài toán quy hoạch tuyến tính 3 biến, tìm giá trị lớn nhất của hàm mục tiêu.       1 2 3 1 2 3 1 2 3 1 3 , , 3 2 2,5 max 0,04 0,06 0,05 500 0,07 0,02 300 0 1,2,3j f x f x x x x x x x x x x x x j                VÍ DỤ 2 Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng đạm, đường, khoáng cho một loại gia súc tương ứng là 90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại được cho trong bảng sau: Hãy lập mô hình toán học của bài toán xác định khối lượng thức ăn mỗi loại phải mua để tổng số tiền chi cho mua thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi ngày. VÍ DỤ 3 Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau: Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao động tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6. VÍ DỤ 4 Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả sử, đối với: Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m ván Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất. BÀI TOÁN QHTT TỔNG QUÁT (1) Hàm f(x) gọi là hàm mục tiêu (2) là hệ ràng buộc chính (3) là hệ ràng buộc dấu (2) Và (3) gọi chung là hệ ràng buộc của bài toán           1 1 2 2 1 1 2 2 1 ... 2 ... 1,2,.., 0 3 0 1,2,..., min (max)n n i i in n i j f x c x c x c x a x a x a x b i m x j n tuy y                           DẠNG MA TRẬN CỦA BÀI TOÁN QHTT Xét bài toán QHTT dạng:   1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 ... ... ... .......................................... ... 0 min (max)n n n n n n m m mn n m j f x c x c x c x a x a x a x b a x a x a x b a x a x a x b x                       DẠNG MA TRẬN CỦA BÀI TOÁN QHTT Đặt: Ta có dạng ma trận của bài toán QHTT: 11 12 1 1 1 1 21 22 2 2 2 2 1 2 ... ... ... ... ....................... ... n n m n nm m mn a a a b x c a a a b x c A b x c b x ca a a                                                     min max 0 Tf c x Ax b x      BÀI TOÁN DẠNG CHÍNH TẮC:   n j j j 1 n ij j j 1 j f x c x min (max) a x b (i 1,m) x 0 (j 1,n) i              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ác ràng buộc chính đều là phương trình • Các ẩn đều không âm BÀI TOÁN DẠNG CHUẨN TẮC 1 2 1 0 0 0 1 0 ... ... ... 0 0 1 me e e                                         n j j j 1 n ij j j 1 j f x c x min (max) a x b (i 1,m) x 0 (j 1,n) i              • Các hệ số tự do bi không âm (bi ≥ 0) • Trong ma trận hệ số có đủ m vecto cột đơn vị: e1, e2,,em VÍ DỤ 5 Bài toán sau có dạng chính tắc: 1 2 3 1 2 3 1 2 3 1 2 1 2 3 260 120 600 max 2 3 500 100 40 250 40000 6 , , 0 x x x x x x x x x x x x x x               VÍ DỤ 6 Xét bài toán QHTT sau: Bài toán trên có dạng chính tắc hay chuẩn tắc     1 2 3 4 1 4 5 1 3 6 1 2 3 4 2 4 6 max 12 12 3 6 0 1,2,...,6j f x x x x x x x x x x x x x x x x j                     VÍ DỤ 6 Ma trận hệ số tự do: 12 3 6 b            • Ma trận hệ số A: 1 0 0 1 1 0 12 0 1 0 0 1 1 1 1 1 0 0 A            1e 2e3e • Ẩn cơ bản thứ nhất là x5. • Ẩn cơ bản thứ 2 là x6. • Ẩn cơ bản thứ 3 là x2. CÁC LOẠI PHƯƠNG ÁN Định nghĩa. Vec tơ ∈ thỏa tất cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được. Định nghĩa. Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ nhất (nếu là bài toán min) thì được gọi là phương án tối ưu (PATU). VÍ DỤ 7 Cho bài toán QHTT: Trong các phương án sau phương án nào là phương án chấp nhận được.   1 2 1 2 1 2 1 2 120 100 max 2 3 8 5 3 15 0, 0 f x x x x x x x x x            1 2 3 4 1 2 1 2 2 2 3 1 u u u u                            PHƯƠNG ÁN CƠ BẢN Trong bài toán chính tắc. Xét phương án Hệ vectơ liên kết với phương án Trong đó Aj là vec tơ cột thứ j trong ma trận hệ số Amn Định nghĩa. Phương án cơ bản nếu hệ vecto liên kết với phương án độc lập tuyến tính Ẩn xj gọi là cơ bản nếu > 0  1 2, ,..., nx x x x  | 0j jA A x  PACB TRONG BÀI TOÁN CHUẨN TẮC Cho ẩn cơ bản thứ k bằng hệ số tự do thứ k, còn các ẩn không cơ bản bằng 0, nghĩa là: Ta được một phương án cơ bản x = (0,6,0,0,12,3) . Phương án này không suy biến vì có đủ 3 thành phần dương. Đây là phương án cơ bản ban đầu của bài toán. Tổng quát, trong bài toán QHTT dạng chuẩn bất kì, khi cho ẩn cơ bản thứ k bằng hệ số tự do thứ k ( k = 1,2,,m ), còn các ẩn không cơ bản bằng 0, ta được phương án cơ bản ban đầu của bài toán. Nếu sắp xếp lại ta có dạng sau. 1 2 3 4 5 60; 6; 0; 0; 12; 3x x x x x x       0 1 2, ,..., ,0,0,...,0mx b b b ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC Bước 1. Kiểm tra ràng buộc chính 1 1 2 2 ...i i in n ia x a x a x b    • Ràng buộc dạng nhỏ hơn: • • Ta cộng thêm ẩn phụ: • Ràng buộc dạng lớn hơn: • Ta trừ đi ẩn phụ: 1 1 2 2 ...i i in n n k ia x a x a x x b     1 1 2 2 ...i i in n ia x a x a x b    1 1 2 2 ...i i in n n k ia x a x a x x b     ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC Bước 2. Kiểm tra điều kiện dấu các ẩn số Nếu có ẩn dạng: ta đổi biến: Nếu ẩn xi có dấu tùy ý ta đổi biến: Chú ý: Các ẩn mới và các ẩn phụ đều không âm. Hệ số của các ẩn phụ trong hàm mục tiêu là 0. Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ được PATU của bài toán dạng tổng quát đã cho. 0ix  i i ix x x   i ix x   VÍ DỤ 8 Đưa bài toán sau về dạng chính tắc:   1 2 3 1 2 3 1 3 1 2 3 1 2 2 4 min 4 6 3 12 7 3 2 3 5 6 0, 0 f x x x x x x x x x x x x x x                   VÍ DỤ 8 Đáp án:           1 2 3 3 1 2 3 3 4 1 3 3 5 1 2 3 3 1 2 3 3 4 5 2 4 min 4 6 3 12 7 3 2 3 5 6 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                                         PHƯƠNG PHÁP HÌNH HỌC (ĐỒ THỊ) Sinh viên tham khảo thêm lý thuyết sách College Mathematics for Busines – Raymond A. Barnett Chương 5 phần Linear Programing Chỉ dùng cho bài toán quy hoạch tuyến tính 2 biến PHƯƠNG PHÁP ĐỒ THỊ Xét bài toán quy hoach tuyến tính :     2 1 2 1 min maxj j j ij j i j f x c x a x b        PHƯƠNG PHÁP ĐỒ THỊ Biểu diễn các ràng buộc lên đồ thị Oxy. Xác định phần được giới hạn bởi các ràng buộc là tập phương án. Xác định các điểm cực biên (đỉnh) của tập phương án thỏa mãn các ràng buộc. Xác định giá trị của hàm mục tiêu tại các điểm cực biên. So sánh và suy ra phương án tối ưu VÍ DỤ 9. BÀI TOÁN KẾ HOẠCH SẢN XUẤT Một nhà sản xuất lều sử dụng trên các vùng núi có 2 dòng sản phẩm: tiêu chuẩn và thám hiểm. Mỗi lều tiêu chuẩn yêu cầu 1 giờ công lao động từ bộ phận cắt và 3 giờ công từ bộ phận lắp ráp. Mỗi lều thám hiểm đòi hỏi 2 giờ công lao động từ bộ phận cắt và 4 giờ làm việc từ bộ phận lắp ráp. Số giờ lao động tối đa có sẵn mỗi ngày trong các phòng cắt và lắp ráp lần lượt là 32 và 84. Nếu công ty thu được mức lợi nhuận $50 cho mỗi lều tiêu chuẩn và 80$ cho mỗi lều thám hiểm, thì mỗi ngày nên sản xuất bao nhiêu lều mỗi loại để tối đa hóa tổng lợi nhuận hàng ngày (giả sử rằng tất cả các lều có thể được bán)? MÔ HÌNH BÀI TOÁN Gọi x, y lần lượt là số lều tiêu chuẩn và thám hiểm  , 50 80 max 0, 32 0 2 3 4 84 x f x y y x x y P x y y                TẬP PHƯƠNG ÁN •Ta có thể tính toán được lợi nhuận tại từng điểm nằm trong miền khả thi (feasible region) hay tập phương án •Tại (x,y)=(12,10) ta có P=1400 •Tại (x,y)=(23,2) ta có P=1310 2 32 3 4 8 0, 0 4 x x y x y y            ĐƯỜNG ĐẲNG LỢI Gán cho P một giá trị cố định và vẽ đồ thị P=50x+80y trên hệ trục tọa độ Oxy ta có được một đường thẳng. Đường này có tên là constant profit line hay đường đẳng lợi. Mọi điểm thuộc tập phương án và nằm trên đường này đều cho ta một kế hoạch sản xuất và có cùng lợi ích P như nhau. Với mỗi giá trị khác nhau của P ta có một đường đẳng lợi khác song song với đường đẳng lợi còn lại, vì có chung hệ số góc. Để thuận tiện ta đưa phương trình đường đẳng lợi về dạng: 5 50 80 8 80 P P x y y x       ĐƯỜNG ĐẲNG LỢI Lợi nhuận lớn nhất sẽ nằm tại điểm mà đường đẳng lợi xa nhất so với gốc tọa độ nhưng vẫn còn nằm trong miền khả năng. Trong ví dụ này thì nó chính là điểm (20,6) Profit max: P=20.50+6.80=1480 Nhận xét. PATU nằm tại các điểm góc (corner points) của tập phương án max max 5 8 80 P y x P y     VÍ DỤ 10 Đối với tập phương án như hình vẽ (A) Cho P = x + y. Vẽ đồ thị các đường đẳng lợi thông qua các điểm (5, 5) và (10, 10). Đặt đường thẳng dọc theo đường có lợi nhuận nhỏ hơn và trượt theo hướng tăng lợi nhuận, mà không làm thay đổi độ dốc của nó. Giá trị tối đa của P là bao nhiêu? Giá trị tối đa này xảy ra ở đâu? (B) Lặp câu (A) cho P = x + 10y. (C) Lặp câu (A) cho P = 10x + y CÁC ĐỊNH LÝ Định lý 1. Nếu bài toán quy hoạch tuyến tính có PATU thì PATU là một trong các PACB của tập phương án. Định lý 2. (Về sự tồn tại phương án tối ưu) A) Nếu tập phương án của bài toán QHTT bị chặn thì cả bài toán min và max đều có PATU B) Nếu tập phương án không bị chặn và các hệ số của hàm mục tiêu đều dương thì bài toán min có PATU nhưng bài toán max không có PATU C) Nếu tập phương án của bài toán rỗng thì cả bài toán min và max đều không có PATU TÌM PATU BẰNG PP ĐỒ THỊ VÍ DỤ 11A Z max = 28 Z min = 15 VÍ DỤ 11B Z min = 160 Không có max VÍ DỤ 12 Giải bài toán QHTT sau:         1 2 1 2 1 2 1 2 1 2 1 2 , min 2 2 1 2 2 5 3 0, 0 f x x x x x x x x x x x x                 VÍ DỤ 13 Biểu diễn đồ thị các bất đẳng thức lên hệ trục tọa độ ta được miền các phương án là hình ngũ giác ABCDE. Các điểm có tọa độ như sau A(0,0); B(0,2); C(1,4); D(4,1); E(2,0) là các điểm cực biên. lần lượt thay các cực biên vào hàm mục tiêu ta có f(A) = 0; f(B) = 2; f(C) = 3; f(D) = -3; f(E) = -2. Vậy phương án tối ưu x*=(4,1) tại đó hàm mục tiêu đạt giá trị Min D C A B E VÍ DỤ 14 Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu 100 mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ chính quyết định sản lượng kế hoạch. Thợ rèn có 2000 công, thợ sắt có 3000 công, thợ mộc có 1500 công. Định mức lao động của mỗi loại tàu được cho trong bản: Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt tổng số mã lực cao nhất? 100 mã lực 50 mã lực Thợ sắt (3000) Thợ rèn (2000) Thợ mộc (1500) 150 120 80 70 50 40 VÍ DỤ 14 Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã lực cần đóng Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2max Điều kiện:            0x,0x 1500x40x80 2000x50x120 3000x70x150 21 21 21 21 VÍ DỤ 15 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, 150 giờ máy mài để chế tạo 3 loại sản phẩm A, B, C. Để chế tạo một đơn vị sản phẩm A cần 9 giờ máy cán, 5 giờ máy tiện, 3 giờ máy mài; 1 đơn vị sản phẩm B cần 3 giờ máy cán, 4 giờ máy tiện; 1 đơn vị sản phẩm C cần 5 giờ máy cán. 3 giờ máy tiện, 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, mỗi sản phẩm C trị giá 27 ngàn đồng. Vấn đề đặt ra là xí nghiệp cấn chế tạo bao nhiêu đơn vị sản phẩm mỗi loại để tổng giá trị sản phẩm xí nghiệp thu được là lớn nhất, với điều kiện không dùng quá số giờ hiện có của mỗi loại máy. VÍ DỤ 16 Một xí nghiệp điện cơ sản xuất quạt điện các loại. Cần cắt từ một tấm tôn các cánh quạt điện theo 3 kiểu A, B, C. Có 6 mẫu cắt khác nhau theo bảng sau: Kiểu cánh quạt Mẫu cắt 1 2 3 4 5 6 A B C 2 0 0 1 1 0 1 0 1 0 2 0 0 1 2 0 0 3 PHƯƠNG PHÁP ĐƠN HÌNH Simplex method Xuất phát từ một PACB đầu tiên, tìm cách đánh giá PACB ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang một PACB mới tốt hơn. Quá trình được lặp lại vì số PACB 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. Do nhà toán học George Benard Danzig đưa ra năm 1947 PHƯƠNG PHÁP ĐƠN HÌNH 1) Tìm một phương án cực biên (phương án cơ bản) 2) Xét xem PACB này đã là PATU hay chưa. Nếu đã tối ưu thì kết thúc. Ngược lại chuyển sang bước 3. 3) Tìm phương án cực biên liền kề tốt hơn PACB đang xét 4) Quay về bước 2. VÍ DỤ 17 Xét bài toán dạng chuẩn tắc Ta có:            0 5 432 min232 421 321 4321 jx xxx xxx xxxxxf               5 4 1011 0132 BA VÍ DỤ 17 Ẩn cơ bản: x3, x4 Phương án cơ bản: x1=x2=0; x3=4; x4=5 Ta có:               5 4 1011 0132 BA     25,4,0,0 00  xfx   4321 232 xxxxxf                   0 5 324 0 5 432 214 213 421 321 jj x xxx xxx x xxx xxx VÍ DỤ 17 Ta đánh giá f(x) như sau: Bài toán min nên với Ta chưa đánh giá được giá trị nhỏ nhất của f             2211021 212121 4321 932 5232432 232 xxxfxxxf xxxxxxxf xxxxxf      21 932 xxxf    Axxxf  21 932 VÍ DỤ 17 Thử chọn x1, x4 làm ẩn cơ bản. Cho x2, x3=0 ta có Phương án cơ bản: Ta có:            3 2 5 42 4 1 41 1 x x xx x  3,0,0,20 x                      0 2 1 2 5 3 2 1 2 3 2 0 5 432 324 321 421 321 j j x xxx xxx x xxx xxx VÍ DỤ 17 Ta đánh giá f(x) như sau: Dễ thấy: Vậy phương án tối ưu:     32 4321 2 3 2 9 4 232 xxxf xxxxxf     4xf  3,0,0,2* x CHÚ Ý Tổng quát ta có: Với x0 là phương án cơ bản + Nếu bài toán min thì ta cần Delta dương + Nếu bài toán max thì ta cần Delta âm Trong PP đơn hình phía sau thì Delta trong bảng đơn hình ngược dấu với Delta ở đây.      kk xxfxf 0 Ẩn không cơ bản 0kx PHƯƠNG PHÁP ĐƠN HÌNH BẢNG ĐƠN HÌNH    n 1 jijij cacΔ i  Cách tính Delta một cột:  Lấy hệ số cột ngoài cùng bên trái bảng  Nhân với hệ số cột cần tính  Trừ đi giá trị trên đầu cột cần tính  Cách tính giá trị f(x):  Lấy cột hệ số nhân cột P. Án      n 1 iibcf i x DẤU HIỆU VỀ PHƯƠNG ÁN TỐI ƯU 1. Nếu ∆k ≤ 0 thì x 0 là phương án tối ưu. 2. Nếu tồn tại một ∆k > 0 mà ajk ≤ 0 thì bài toán không có phương án tối ưu. 3. Nếu tất cả ∆k > 0 và tồn tại ajk > 0 thì ta có thể tìm được phương án tốt hơn trong trường hợp bài toán không suy biến. CÁC BƯỚC THỰC HIỆN CÁC BƯỚC THỰC HIỆN Nhớ phép biến đổi sơ cấp trên dòng đối với ma trận. Tương tự như khi đi tìm hạng của ma trận khi biến đổi về dạng bậc thang. VÍ DỤ 18                       36 60 52 100103 010324 001342 bA VÍ DỤ 18 Hệ số Ẩn cơ bản PA X1 5 X2 4 X3 5 X4 2 X5 1 X6 3                       36 60 52 100103 010324 001342 bA   654321 32545 xxxxxxxf  VÍ DỤ 18 Hệ số Ẩn cơ bản PA x1 x2 x3 x4 x5 x6 5 4 5 2 1 3 2 x4 52 2 4 3 1 1 0 1 x5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1                       36 60 52 100103 010324 001342 bA   654321 32545 xxxxxxxf  VÍ DỤ 18 Hệ số Ẩn cơ bản PA X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 2 X4 52 2 4 3 1 1 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0   654321 32545 xxxxxxxf  64 0 2 4 3 1 2 2                        272 36 60 52 3 1 2 0                      xf VÍ DỤ 18 Hệ số Ẩn cơ bản PA X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 2 X4 52 2 4 3 1 1 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0                       36 60 52 100103 010324 001342 bA   654321 32545 xxxxxxxf  125 3 4 2 3 1 2 1                       64 0 2 4 3 1 2 1                       ĐÁNH GIÁ Hệ số Ẩn cơ bản PA X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 2 X4 52 2 4 3 1 1 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0 Giá trị lớn nhất nằm ở cột x1 123:36 154:60 162:52    Giá trị nhỏ nhất nằm ở hàng x6 Vậy đưa biến x1 vào thay cho biến x6 BẢNG MỚI Hệ số Ẩn cơ bản PA X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 2 X4 52 2 4 3 1 0 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0 2 X4 28 0 4 7/3 1 0 -2/3 1 X5 12 0 2 5/3 0 1 -4/3 5 x1 12 1 0 1/3 0 0 1/3 128 0 6 3 0 0 -4 Chia hàng mới để có hệ số 1 tại vị trí xoay Biến đổi trên dòng để các hàng còn lại là 0 Tính lại các giá trị Delta và giá trị f(x0) BẢNG MỚI Hệ số Ẩn cơ bản PA X1 5 X2 4 X3 5 X4 2 X5 1 X6 3 2 X4 28 0 4 7/3 1 0 -2/3 1 X5 12 0 2 5/3 0 1 -4/3 5 x1 12 1 0 1/3 0 0 1/3 128 0 6 3 0 0 -4 2 X4 4 0 0 -1 1 -2 2 4 X2 6 0 1 5/6 0 1/2 -2/3 5 x1 12 1 0 1/3 0 0 1/3 92 0 0 -2 0 -3 0 Đưa biến x2 vào thay biến x5 PATU: x0=(12,6,0,4,0,0) f min = 92 PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý 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, còn các yếu tố khác của thuật toán không đổi. 2) Chọn vectơ đưa vào cơ sở ứng với max là với hy vọng làm trị số hàm mục tiêu giảm nhiều nhất sau mỗi bước biến đổi, tuy nhiên vectơ đưa vào cơ sở thực sự làm trị số hàm mục tiêu giảm nhiều nhất phải ứng với max .   nhưng trên nguyên tắc thì đưa bất kỳ vectơ nào ứng với k > 0 vào cơ sở cũng cải tiến được phương án. PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý 3