Tham khảo tài liệu 'bài giảng toán tin 7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | T4x1 4x2 - 6 6x2 4x1 - 3 U1 1 1 2 u2 2 3 -1 U 3 0 0 U4 - I 0 U1 x1 x2 - 1 0 U2 2x1 3x2 -4 0 U3x1 0 u4x 2 0 U 0 Vi Ĩ74. Xét x 1 0 Từ hệ điều kiện trên ta có u2 u3 0 nên -2 U ì U4 0 -1 1 _1_ _-1_ 0. Do đó u1 2 và u4 1. Vậy x 1 0 là phương án tối ưu toàn cục. 5. Một số phương pháp hướng chấp nhận giải bài toán quy hoạch phi tuyến Trong mục này chúng ta trình bày vắn tắt một số phương pháp hướng chấp nhận giải BTQHTT thông qua một vài ví dụ đơn giản. Các phương pháp này đều hội tụ tới các điểm thỏa mãn điều kiện Kuhn - Tucker. Vì vậy nếu các giả thiết của định lý 34 hay 35 được thỏa mãn thì đây chính là các điểm tối ưu toàn cục. . Phương pháp hướng chấp nhận Trước hết cần nhắc lại một số khái niệm sau đây. Xét bài toán tối ưu Min f x với x e S trong đó f Rn R và S là tập lồi khác rỗng S c Rn. Một véc tơ d 0 được gọi là một hướng chấp nhận tại x e S nếu 3 ỗ 0 sao cho x Âd e S đúng VÀ. e 0 ỗ . Ngoài ra d được gọi là hướng cải thiện tại x e S nếu 3 ỗ 0 sao cho x Âd e S và f x Âd f x đúng VÀ. e 0 ỗ . Nội dung của phương pháp hướng chấp nhận hay còn được gọi là phương pháp hướng khả thi method of feasible directions như sau Tại mỗi bước lặp ứng với phương án xk hiện có phải xây dựng được một hướng cải thiện dk. Sau đó cần xác định độ dài bước dịch chuyển À. 0 để dịch chuyển từ xk sang phương án mới xk 1 trên hướng dk căn cứ bài toán tối ưu với một biến À. được gọi là bài toán tìm kiếm trên hướng Min f xk Âdk sao cho xk Ầdk e S. Từ đó tìm được giá trị tối ưu của À. và nhận được phương án xk 1 xk Ầdk tốt hơn hoặc ít nhất tốt bằng phương án xk. Ví dụ 13. Xét BTQHPT Min f x 8x2 10x2 12x1 x2 50x1 - 80x2 với các ràng buộc g1 x x1 x2 -1 0 g2 x x1 -1 2 0 x1 x2 0. 170 Ta thấy H X1 X2 ổ2f dx2 ổ2f 0X10X2 ổ2f ÕX1ÕX2 ổ2f ổx2 16 12 12 20 xác định dương nên đây là BTQHL. Bước lặp 1 Xét x1 0 0 ta có - 16x1 12x2 50 ỔX1 1 2 20X2 12X -80 K 2 1 50 -80 Dễ dàng kiểm tra được Vx x1 x2 e S trong đó S là miền ràng buộc đã cho ta có . Minh họa phương pháp hướng chấp nhận Từ đó có 0 0 0 .
