tailieunhanh - Một số thuật toán giải bài toán tối ưu phân thức và ứng dụng - ThS. Nguyễn Mạnh Hùng

nội dung bài viết "Một số thuật toán giải bài toán tối ưu phân thức và ứng dụng" dưới đây để nắm bắt được nội dung bài toán tìm đường đi có tỷ số lớn nhất trong đồ thị không có chu trình, phương pháp Newton,. Với các bạn chuyên ngành Toán học thì đây là tài liệu tham khảo hữu ích. | MỘT số THUẬT TOÁN GIẢI BẢI TOÁN Tối Uu PHÂN THỨC VẢ ÚNG DỤNG . NGUYỄN MẠNH HÙNG Trường Đại học Thuỷ lợi Email hungmath1976@ Tóm tắt Hệ thống nguồn nước tạo ra nhiều vấn đề đặc biệt ví dụ trong sử dụng tối ưu nguồn nước việc cực đại hiệu quá kinh tế chất lượng môi trường khá năng điều tiết khi ứng dụng các phương pháp tối ưu hoá và các mô hình Toán học gặp khá nhiều khó khăn vì các đặc trưng khác nhau của hệ thống liên quan đến bài toán qui hoạch rời rạc. Đặc điểm khác biệt của tối ưu rời rạc tối ưu tổ hợp là các biến thuộc miền rời rạc và nó đã phát triển nhanh chóng vì việc sử dụng rộng khắp về máy tính và công nghệ thông tin. Một số kỹ thuật của tối ưu rời rạc dưới đây là lời giái về các thuật toán các định lý hội tụ cho bài toán tối ưu phân tuyến .Sử dụng phương pháp Newton liên hệ với độ phức tạp tính toán của thuật toán trong đó nghiệm tối ưu được xấp xĩ và thuật toán đa thức dừng sau một số hữu hạn bước lặp. 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 tối ưu phân tuyến. Bài toán tối ưu phân tuyến tìm được nhiều ứng dụng trong thực tế chẳng hạn để đo hiệu quả của một số hệ thống được thể hiện như là tỷ số giữa lợi nhuận thời gian phí tổn thời gian . . Một trong những lớp bài toán tối ưu phân tuyến thường gặp trong thực tế là bài toán tối ưu phân tuyến rời rạc. Bài toán tối ưu rời rạc phân tuyến có thể phát biểu như sau F max f x g x xeX 1 trong đó g x 0 VxeX f x 0 với một số x eX Các phẩn tử của tập rời rạc X được gọi là các cấu trúc f x thường được gọi là hàm chi phí cost g x thường được gọi là hàm trọng lượng weight . Một ví dụ về bài toán qui hoạch rời rạc phân tuyến là tìm Max f x g x x eX trong đó X 0 1 p. Cùng với bài toán F ta xét bài toán sau G Min ỗeR vớif x -ỗg x 0 VxeX Cặp S x eR X X là nghiệm tối ưu của bài toán G nếu và chỉ nếu f x -S g x 0 f x -S g x với mỗi xeX. Điều này tương đương với f x g x s f x g x với mỗi xeX có nghĩa là s là giá trị mục .