"Đề cương bài giảng môn Các phép toán tối ưu" được biên soạn với các bài học bài toán tối ưu hóa và các vấn đề cơ sở; bài toán qui hoạch tuyến tính; lý thuyết đối ngẫu; bài toán vận tải; qui hoạch tham số. | ĐỀ CƯƠNG BÀI GIẢNG Học phần CÁC PP TỐI ƯU Đơn vị Bộ môn Toán Khoa CNTT Thời gian Tuần 1 Tiết 1-3 Giáo viên Nguyễn Trọng Toàn GV giảng 3 Bài tập 0 Tự học 3 Vũ Anh Mỹ Chương 1 Bài toán tối ưu hoá và các vấn đề cơ sở Bài toán TUH và phân loại bài toán. Các mục Một số mô hình thực tế Không gian Euclide n-chiều Mục đích - - Nắm được ý nghĩa ứng dụng trong thực tiễn của các bài toán TUH yêu cầu - Nhắc lại và bổ xung một số kiến thức ĐSTT có liên quan NỘI DUNG I. LÝ THUYẾT Chương 1. BÀI TOÁN TỐI ƯU HÓA VÀ CÁC VẤN ĐỀ CƠ SỞ BÀI TOÁN TỐI ƯU HÓA VÀ PHÂN LOẠI BÀI TOÁN Bài toán tối ưu hoá tổng quát Min hoặc Max của hàm f x g i x b i i 1 m với các điều kiện n x X R trong đó - f x Hàm mục tiêu với n biến. - gi x i 1 m Các hàm ràng buộc. Mỗi bất đẳng thức gọi là một ràng buộc. - Tập D x X R n gi x bi i 1 m Miền ràng buộc - x x1 x2 . xn D Phương án hay lời giải chấp nhận được. - Phương án x D làm cực đại cực tiểu hàm mục tiêu gọi là phương án hay lời giải tối ưu. Cụ thể là f x f x x D đối với bài toán max hay f x f x x D đối với bài toán min. Khi đó f f x gọi là giá trị tối ưu của bài toán. Phân loại bài toán Để tìm thuật giải hiệu quả cho các bài toán Tối ưu hoá cần phân loại các bài toán - Quy hạch tuyến tính QHTT - Quy hoach phi tuyến QHPT - Qui hoạch rời rạc QHRR - Qui hoạch đa mục tiêu QHĐMT . MỘT SỐ MÔ HÌNH THỰC TẾ Bài toán lập kế hoạch sản xuất tối ưu Một công ty muốn sản xuất 2 loại sản phẩm A và B bằng các loại nguyên liệu I II và III. Chi phí sản xuất cho một đơn vị sản phẩm được cho trong bảng sau 1 Sản phẩm A B Nguyên liệu I 2 1 II 1 2 III 0 1 I 8 Giả sử công ty có lương dự trữ nguyên liệu II 7 Đơn vị nguyên liệu . Tiền III 3 lãi cho 1 đơn vị sản phẩm loại A và B tương ứng là 4 và 5 đơn vị tiền tệ . Cần lập kế hoạch sản xuất sao cho công ty thu được lãi nhiều nhất với điều kiện hạn chế về nguyên liệu như trên. Kí hiệu x1 và x2 tương ứng là số lượng sản phẩm loại A và B cần sản xuất. Mô hình toán học của bài toán trên có
