Nếu mà ta đã biết được x là phương án tối ưu nhờ một cách nào đó thì mục đích của ta đã xong. Nếu x không phải là phương án tối ưu thì ta tìm phương án cực biên khác tốt hơn tức là phương án làm cho giá trị hàm mục tiêu nhỏ hơn. | Chương I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Bài 4. PHƯƠNG PHÁP ĐƠN HÌNH 1. Giới thiệu chung: Ta xét bài toán QHTT dạng chính tắc: Hoặc viết dưới dạng: Trong đó: Giả sử bài toán đang xét ta đã biết một phương án cực biên dạng : trong đó cơ sở liên kết của x là Giá trị hàm mục tiêu là: Với mỗi j = 1, 2, , n Ký hiệu : Nếu mà ta đã biết được x là phương án tối ưu nhờ một cách nào đó thì mục đích của ta đã xong. Nếu x không phải là phương án tối ưu thì ta tìm phương án cực biên khác tốt hơn tức là phương án làm cho giá trị hàm mục tiêu nhỏ hơn. Muốn vậy ta phải xây dựng một cơ sở mới, đơn giản nhất là thay thế một véctơ trong cơ sở cũ bằng một véctơ nằm ngoài cơ sở cũ. Đặt: Từ hai véctơ: 2. Định lý 1.( Dấu hiệu tối ưu) Nếu là một 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 sao cho : thì x là phương án tối ưu, và ngược lại. 3. Định lý 2: Nếu tồn tại véctơ ngoài cơ sở liên kết của phương án cực biên sao cho và thì bài toán Quy hoạch tuyến tính dạng chính tắc không có phương án tối ưu. Rõ hơn là hàm mục tiêu không bị chặn dưới trên tập phương án. Ví dụ 1: Xét bài toán QHTT với phương án cực biên x=(6,8,0). Xét xem x có phải là phương án tối ưu hay không ? Giải: Véctơ x có cơ sở liên kết là: Ta xác định các véctơ xj : Lần lượt thay j=1,2,3 ta có : Ta thấy tất cả các với mọi j. Vậy x là phương án tối ưu và giá trị tối ưu là: f(x)=. Để dễ thấy ta sắp xếp các phép toán lên bảng sau: Cơ sở Hệ số P. án 1 x1 6 x2 9 x3 A1 A2 1 6 6 8 1 0 0 1 2 1 f(x) 54 Bảng gồm 3 dòng, 6 cột. Cột một ghi cơ liên kết của p. án x, cột hai ghi hệ số liên kết của x, cột 3 ghi p. án x, cột 4; 5; 6 ở dòng hai ghi toàn bộ ma trận A Ví dụ 2: Xét bài toán QHTT với phương án cực biên x=(5,0,7). Xét xem x có phải là phương án tối ưu hay không ? Giải: Véctơ x có cơ sở liên kết là: Ta xác định các véctơ xj : Lần lượt thay j=1,2,3 ta có : Ta thấy và .Vậy bài toán không có phương án tối ưu. Rõ hơn là hàm mục tiêu không bị chặn dưới trên tập phương án. Cơ sở Hệ số P. án 7 x1 | Chương I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Bài 4. PHƯƠNG PHÁP ĐƠN HÌNH 1. Giới thiệu chung: Ta xét bài toán QHTT dạng chính tắc: Hoặc viết dưới dạng: Trong đó: Giả sử bài toán đang xét ta đã biết một phương án cực biên dạng : trong đó cơ sở liên kết của x là Giá trị hàm mục tiêu là: Với mỗi j = 1, 2, , n Ký hiệu : Nếu mà ta đã biết được x là phương án tối ưu nhờ một cách nào đó thì mục đích của ta đã xong. Nếu x không phải là phương án tối ưu thì ta tìm phương án cực biên khác tốt hơn tức là phương án làm cho giá trị hàm mục tiêu nhỏ hơn. Muốn vậy ta phải xây dựng một cơ sở mới, đơn giản nhất là thay thế một véctơ trong cơ sở cũ bằng một véctơ nằm ngoài cơ sở cũ. Đặt: Từ hai véctơ: 2. Định lý 1.( Dấu hiệu tối ưu) Nếu là một 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 sao cho : thì x là phương án tối ưu, và ngược lại. 3. Định lý 2: Nếu tồn tại véctơ ngoài cơ sở liên kết của phương án cực biên sao cho và thì bài toán Quy hoạch tuyến tính dạng chính tắc không có .
