tailieunhanh - Thuật toán gần đúng cho bài toán tối ưu tổ hợp - ThS. Nguyễn Mạnh Hùng

Nhằm giúp các bạn chuyên ngành Toán học có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu, nội dung bài viết "Thuật toán gần đúng cho bài toán tối ưu tổ hợp" dưới đây. Nội dung bài viết trình bày về thuật toán gần đúng, ứng dụng thuật toán gần đúng,. | THUẬT TOÁN e-GẦN ĐÚNG CHO BÀI TOÁN Tối ưu Tổ HỢP Ths. Nguyễn Mạnh Hùng - Khoa CNTT - ĐH Thuỷ Lọi I. Giới THIỆU. Bài toán tìm cực đại hoặc cực tiểu của thương hai hàm thực trên tập D của không gian Rn được gọi là bài toán quy hoạch phân tuyến. Bài toán quy hoạch phân tuyến có nhiều ứng dụng trong thực tế nhưng rất khó tìm nghiệm chính xác vì thế người ta quan tâm đến việc xây dựng các thuật giải gần đúng. Một thuật toán được gọi là -gần đúng nếu nó luôn cho lời giải -tối ưu tức là lời giải cố sai số tương đối so với giá trị tối ưu bị chặn trên bởi một hằng sô dương . Xét bài toán quy hoạch rời rạc phân tuyến sau a0 ax . P Max R x 7 xeD b0 bx trong đó a0 b0 thuộc R a a1 . an eR b b1 . bn eR x x1 x2 . xn gR D là tập con hữu hạn khác rỗng của Rn. Ta có các giả thiết sau đây 1 bx 0 V xeD. 2 b0 0 và a0 0 3 R x a0 b0 với một x eD nào đó. Giả thiết 1 và 2 đảm bảo rằng mẫu số của R x là dương trên D và giả thiết 3 chỉ ra rằng giá trị tối ưu Ầ của bài toán P là lớn hơn a0 b0. Xét bài toán phụ Q Ầ với tham số A Q Ầ max a-Ầb x xeD . Khi đó bài toán P là tương đương với việc tìm Ầ Ầ sao cho Q V có giá trị tối ưu Ầ b0 - a0 trong trường hợp này Ầ chính là giá trị tối ưu của bài toán P và 3 đã giới thiệu thuật toán giải Q V mà không cần biết trước Ầ . Sau đây ta sẽ nêu ra một thuật toán gọi là Frac s cho P khi đã biết một thuật toán PARA Ầ s tìm nghiệm 8-gần đúng cho bài toán Q Ầ . Gọi v và v Ầ là giá trị giá trị tối ưu của P và Q Ầ tương ứng. Các tính chất của bài toán bổ trợ Tính chất 1. v Ầ là liên tục tuyến tính từng khúc không tâng và lồi. Tính chất 2. v Ầ Ầb0-a0 nếu và chỉ nếu A V v Ầ Ầb0-a0 nếu và chỉ nếu Ầ Ầ v Ầ Ầb0-a0 nếu và chỉ nếu Ầ Ầ . Đinh lý 1. Tồn tại một khoảng e f sao cho Ầ e e f và v Ầ 0 VXe e f . Chứng minh. Vì tính liên tục của v Ầ nên chỉ cần chứng minh v Ầ 0 Vì b0 0 và bx 0 nên từ giả thiết 3 suy ra a- a0 b0 b x 0 với một x nào đó thuộc D v a0 b0 0. 1 Vì vậy ta có a0 b0 b0 -a0 0 v a0 b0 theo tính chất 2 thì a0 b0 X . Điều này dẫn đến v X X b0-a0 0. Tiếp theo