tailieunhanh - Bài giảng toán tin 6

Tìm một phương án đối ngẫu khả thi x = B-1b tương ứng với ma trận cơ sở B trong một phân rã nào đó A = [N B]: điều kiện xj ≥ 0, ∀j có thể không được thoả mãn nhưng luôn có Δj ≥ 0, ∀j. – Tính Δj = cj – zj, ∀j = 1,n , trong đó n là số biến của bài toán đang xét. | và tập A2 x - x y x e S y 0 . Dễ dàng kiểm tra được A1 và A2 là các tập lồi. Ngoài ra A1 n A2 0 vì nếu trái lại thì tồn tại x y sao cho x e S và 0 y f x -f x mâu thuẫn với giả thiết x là phương án tối ưu. Theo định lý 8 sẽ có một siêu phẳng phân tách A1và A2 tức là tồn tại véc tơ ệ0 p 0 và một số vô hướng a sao cho 0 x - x py a ứng với x e Rn y f x - f x và o x - x py a ứng với x e S y 0 . Trong cho x x và y 0 thì có a 0. Trong cho x x và y s 0 thì có ps a. Do s có thể chọn tùy ý nên p 0 a. Tóm lại ta có p 0 và a 0. Giả sử p 0 thì từ có Ị x - x 0 Vx. Đặt x x ệ0 thì suy ra 0 qrT x - x 01 2 hay ệ0 0. Do ệo p 0 0 nên p 0. Chia cả hai vế của và cho - p và đặt - ệo p ệ chúng ta có y ệT x - x ứng với x e Rn y f x - f x và ệT x - x - y 0 ứng với x e S y 0. Trong cho y 0 thì ta có ệT x - x 0 V x e S. Từ suy ra ngay f x f x T x - x Vx e Rn. Vậy ệ là dưới vi phân của hàm f tại x sao cho ệT x - x 0 V x e S đpcm . Hệ quả 24a. Trong điều kiện của định lý trên nếu S là tập mở và x là phương án tối ưu thì tồn tại dưới vi phân 0 tại x . Hệ quả 24b. Trong điều kiện của định lý trên nếu f khả vi thì x là phương án tối ưu khi và chỉ khi Vf x T x - x 0 Vx e S. Ngoài ra nếu S là tập mở thì x là phương án tối ưu khi và chỉ khi Vf x 0 . Việc chứng minh hai hệ quả này khá dễ dàng được dành cho bạn đọc. Ví dụ 8. Xét bài toán tối ưu Min f x1 x2 x1 - 3 2 2 x2 - 5 2 với miền ràng buộc -xi x2 2 2x1 3x2 11 -x1 0 -x2 0. Đây là BTQHL xem minh họa hình . 160 Điểm B 1 3 là phương án tối ưu vì Vf 1 3 ổf Ổx1 -Õĩ dx J 1 3 2 x1 - 3 2 -1 _2 x2 - 5 _ 1 3 _-4 _ Trên hình ta thấy tại x 1 3 V x thuộc miền ràng buộc S luôn có Vf 1 3 T x - x 0 . Do đó x 1 3 là phương án tối ưu toàn cục. Xét điểm x 0 0 có Vf 0 0 -3 -10 . Do đó tồn tại xe S sao cho x - x hợp với Vf 0 0 góc tù hay Vf 0 0 T x - x 0 . Vậy x 0 0 không là điểm tối ưu. Định lý 25 cực đại hóa hàm lồi . Cho f S c Rn Rlà hàm lồi xét bài toán cực đại hóa Maxf x . Nếu x e S là phương án .