Đề cương môn học Tối ưu hóa

Chia sẻ: Nhung Nhung | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

412
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề cương môn học Tối ưu hóa được ban hành kèm theo Quyết định số 783/QĐ-ĐT ngày 22 tháng 3 năm 2011 của Giám đốc Đại học Quốc gia Hà Nội. Tài liệu giới thiệu về bài toán tối ưu và các dạng bài toán tối ưu; lý thuyết cơ bản của bài toán quy hoạch tuyến tính và bài toán đối ngẫu; phương pháp đơn hình và phương pháp đơn hình đối ngẫu; một số bài toán điển hình trong kinh tế và kỹ thuật dẫn về bài toán quy hoạch tuyến tính; các điều kiện tối ưu cho bài toán quy hoạch phi tuyến; một số phương pháp cơ bản để giải bài toán quy hoạch phi tuyến.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề cương môn học Tối ưu hóa

ĐỀ CƯƠNG MÔN HỌC TỐI ƯU HÓA MÃ SỐ: MAT 1100 (Ban hành kèm theo Quyết định số 783 /QĐ-ĐT ngày 22 tháng 3 năm 2011 của Giám đốc Đại học Quốc gia Hà Nội) Dành cho sinh viên các chương trình: Nhóm 7a Công nghệ thông tin Công nghệ thông tin CLC Khoa học máy tính Hệ thống thông tin 1. Thông tin về giảng viên Chức danh, TT Họ và tên Địa chỉ liên hệ Điện thoại học vị 1 Phạm Trọng Quát PGS. TS. ĐHQGHN 0913247974 Khoa Toán-Cơ-Tin học, 2 Nguyễn Ngọc Thắng GVC 0913005223 trường ĐHKHTN Khoa Toán-Cơ-Tin học, 3 Nguyễn Hữu Điển PGS. TS. 0989061951 trường ĐHKHTN Viện Công nghệ thông tin, 4 Nguyễn Đình Hóa PGS. TS. 0193281197 ĐHQGHN 5 Hoàng Xuân Huấn PGS. TS Trường ĐH Công nghệ Khoa Toán-Cơ-Tin học, 6 Lê Công Lợi TS. 0904183257 trường ĐHKHTN 2. Thông tin chung về môn học - Tên môn học: TỐI ƯU HÓA - Mã số môn học: MAT 1100 - Số tín chỉ: 02 - Môn học tiên quyết: Đại số tuyến tính (MAT1093), Giải tích 2 (MAT1095). - Giờ tín chỉ đối với các hoạt động học tập: + Nghe giảng lý thuyết: 23 + Làm bài tập trên lớp: 06 + Kiểm tra đánh giá: 01 - Địa chỉ khoa phụ trách môn học: Khoa Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên 1
3. Mục tiêu của môn học 3.1. Mục tiêu chung 3.1.1. Mục tiêu về kiến thức Trang bị cho sinh viên một số kiến thức cơ bản về tối ưu hoá để phục vụ cho việc học tập và nghiên cứu các bài toán trong kinh tế và kỹ thuật. 3.1.2. Mục tiêu về kỹ năng - Sinh viên cần hiểu một số thuật toán cơ bản và sử dụng được phần mềm đã có để giải những bài toán tối ưu đơn giản. Đặc biệt, sinh viên hiểu được một số thuật toán, không nhất thiết phải biết viết chương trình mà chỉ cần sử dụng được phần mềm đã có như Matlab, GAMS, ... để giải một số bài toán cụ thể. Ngoài ra, bước đầu hình thành kỹ năng phân tích những bài toán thực tế, đưa bài toán này về các bài toán quy hoạch tuyến tính hoặc phi tuyến, biết cách áp dụng các phương pháp của quy hoạch tuyến tính và những phương pháp cơ bản của quy hoạch phi tuyến để giải các bài toán này. - Góp phần rèn luyện phương pháp tư duy khoa học, tư duy logic. 3.1.3. Mục tiêu về thái độ Giúp cho sinh viên hiểu thêm về vai trò của Toán học trong các ngành khoa học khác cũng như những ứng dụng của nó trong cuộc sống. 3.2. Mục tiêu chi tiết Mục tiêu Bậc 1 Bậc 2 Bậc 3 (Nhớ) (Hiểu) (Áp dụng) Nội dung - Cách phân loại các bài toán - Hiểu cách phân loại Biết chuyển một số mô Chương 1 tối ưu. các bài toán tối ưu. hình thực tế về bài toán Mở đầu - Một số khái niệm cơ bản tối ưu. trong giải tích lồi. - Các dạng của bài toán quy - Các dạng của bài toán - Thuật toán đơn hình, hoạch tuyến tính. quy hoạch tuyến tính. hai pha, đối ngẫu. - Thuật toán đơn hình, hai pha. - Cách thiết lập bài toán - Sử dụng được các Chương 2 đối ngẫu. phần mềm đã có để giải - Cách thiết lập bài toán đối Bài toán quy ngẫu, các định lý đối ngẫu, các bài toán quy hoạch hoạch tuyến thuật toán đối ngẫu. tuyến tính. tính - Phương pháp đơn hình giải bài toán vận tải. - Bài toán luồng mạng. - Điều kiện tối ưu của bài toán Các điều kiện tối ưu cho - Áp dụng được các không ràng buộc và có ràng bài toán quy hoạch phi phương pháp Gradient, buộc. tuyến không ràng buộc Newton, hàm phạt và Chương 3 - Phương pháp Gradient, và có ràng buộc. hàm chắn để giải các bài Mở đầu về toán quy hoạch phi phương pháp Newton, hàm bài toán quy phạt, hàm chắn. tuyến cụ thể. hoạch phi - Biết sử dụng một số tuyến phần mềm đã có để giải các bài toán quy hoạch phi tuyến cụ thể. 2
4. Tóm tắt nội dung môn học Giới thiệu về bài toán tối ưu và các dạng bài toán tối ưu; lý thuyết cơ bản của bài toán quy hoạch tuyến tính và bài toán đối ngẫu; phương pháp đơn hình và phương pháp đơn hình đối ngẫu; một số bài toán điển hình trong kinh tế và kỹ thuật dẫn về bài toán quy hoạch tuyến tính; các điều kiện tối ưu cho bài toán quy hoạch phi tuyến; một số phương pháp cơ bản để giải bài toán quy hoạch phi tuyến. 5. Nội dung chi tiết môn học Chương 1. Mở đầu (giờ tín chỉ lý thuyết: 3) 1.1. Bài toán tối ưu 1.1. Phân loại các bài toán tối ưu 1.2. Một số mô hình thực tế dẫn tới bài toán tối ưu 1.3. Kích thước của bài toán tối ưu 1.4. Một số khái niệm và kết quả cơ bản trong giải tích Chương 2. Bài toán quy hoạch tuyến tính (giờ tín chỉ lý thuyết: 12, bài tập:4) 2.1. Các dạng của bài toán quy hoạch tuyến tính 2.2. Phương án cực biên và phương án cực biên tối ưu 2.3. Phương pháp đơn hình 2.3.1. Cơ sở của thuật toán 2.3.2. Thuật toán đơn hình 2.3.3. Phương pháp hai pha 2.4. Phương pháp điểm trong 2.4.1. Các khái niệm cơ bản 2.4.2. Phương pháp căn chỉnh affine (Dikin) 2.4.3. Tìm cơ sở xuất phát 2.5. Bài toán quy hoạch tuyến tính đối ngẫu 2.5.1. Thiết lập bài toán đối ngẫu 2.5.2. Quan hệ giữa cặp bài toán đối ngẫu. Các định lý đối ngẫu 2.5.3. Phương pháp đơn hình đối ngẫu 2.6. Bài toán vận tải 2.6.1. Thiết lập bài toán 2.6.2. Tìm phương án cơ sở xuất phát 2.6.3. Phương pháp đơn hình giải bài toán vận tải 2.7. Bài toán luồng mạng 2.7.1. Các khái niệm cơ bản 2.7.2. Luồng chi phí nhỏ nhất 2.7.3. Luồng lớn nhất 3
Chương 3. Mở đầu về bài toán quy hoạch phi tuyến (giờ tín chỉ lý thuyết: 8, bài tập:2) 3.1. Bài toán tối ưu không ràng buộc 3.1.1. Một số khái niệm cơ bản 3.1.2. Điều kiện tối ưu: điều kiện cần; bài toán tối ưu lồi; điều kiện đủ; bài toán tối ưu toàn phương 3.1.3. Phương pháp Gradient; phương pháp đường dốc nhất; phương pháp Newton; cách lựa chọn bước lưới; sự hội tụ 3.2. Bài toán tối ưu có ràng buộc 3.2.1. Một số khái niệm cơ bản 3.2.2. Điều kiện tối ưu: điều kiện cần, điều kiện đủ 3.2.3. Phương pháp hàm phạt; phương pháp hàm chắn; tính chất của các hàm phạt và hàm chắn 6. Học liệu 6.1. Học liệu bắt buộc 1. Nguyễn Ngọc Thắng, Nguyễn Đình Hóa, Quy hoạch tuyến tính, NXB Đại học Quốc gia Hà Nội, 2004. 2. D. G. Luenberger, Linear and Nonlinear Programming, 3ed, Springer, 2008. 3. Phan Quốc Khánh, Trần Huệ Nương, Quy hoạch tuyến tính, NXB Giáo dục, 2003. 6.2. Học liệu tham khảo 4. Bùi Thế Tâm, Trần Vũ Thiệu, Các phương pháp tối ưu hóa, NXB Giao thông vận tải, 1998. 5. G. B. Dantzig, M. N. Thapa, Linear Programming 1: Introduction, Springer, 1997. 6. D. P. Bertsekas, Nonlinear Programming, 2ed, Athena Scientific, Massachusetts, 1999. 7. J. Nocedal, S. L. Wright, Numerical Optimizations, Springer, 1999. 8. Phí Văn Ban, Quy hoạch tuyến tính, NXB Đại học Sư phạm Hà Nội, 2009. 9. E.K.P. Chong, S.H. Zak, An Introduction to Optimization, John Wiley & Son, 2001. 7. Hình thức tổ chức dạy học 7.1. Lịch trình chung Hình thức tổ chức dạy học môn Nội dung Lên lớp Tự học, tự Kiểm tra, Tổng Bài Thảo Lý thuyết nghiên cứu đánh giá tập luận Chương 1 3 3 Chương 2 12 4 16 Chương 3 8 2 10 Kiểm tra 1 1 Tổng cộng 23 6 1 30 4
7.2 Lịch trình tổ chức giảng dạy cụ thể Hình thức tổ Thời gian, Nội dung chính Yêu cầu SV chuẩn bị chức dạy học địa điểm Lý thuyết Tuần 1 Chương 1: 1.1, 1.2, 1.3 Đọc tài liệu 1, tr. 1-7 2 giờ tín chỉ Giảng đường Lý thuyết Tuần 2 - Chương 1: 1.4, 1.5 Đọc tài liệu 1, tr. 7-24 2 giờ tín chỉ Giảng đường - Chương 2 : 2.1, 2.2 Lý thuyết Tuần 3 Chương 2: 2.3.1, 2.3.2 Đọc tài liệu 1, tr. 23-34 2 giờ tín chỉ Giảng đường Lý thuyết Tuần 4 Chương 2: 2.3.2, 2.3.3 Đọc tài liệu 1, tr. 40-46 2 giờ tín chỉ Giảng đường Lý thuyết Tuần 5 Chương 2: 2.3.3, 2.4 Đọc tài liệu 1, tr. 136-140 2 giờ tín chỉ Giảng đường Lý thuyết Tuần 6 Chương 2: 2.5.1, 2.5.2 Đọc tài liệu 1, tr. 63-83 2 giờ tín chỉ Giảng đường - Lý thuyết - Chương 2: 2.5.3 - Đọc tài liệu 1, tr. 84-92 1 giờ tín chỉ - Chữa bài tập Chương 2 - Làm bài tập 1-5, tr. 61-62 Tuần 7 tài liệu 1 -Bài tập Giảng đường 1 giờ tín chỉ (2 tiết thực học) Bài tập Chữa bài tập Chương 2 Làm bài tập chương III tr. Tuần 8 92-93 tài liệu 1 2 giờ tín chỉ Giảng đường (4 tiết thực học) - Kiểm tra giữa kỳ Chương 2: 2.6 Đọc tài liệu 1, tr. 94-102, 1 giờ tín chỉ Tuần 9 105-114 - Lý thuyết Giảng đường 1 giờ tín chỉ - Lý thuyết - Chương 2 : 2.7 - Đọc tài liệu 2, tr. 134-136 1 giờ tín chỉ - Chữa bài tập Chương 2 - Đọc tài liệu 4, tr. 315-323 Tuần 10 - Bài tập - Làm bài tập 1-2, tr. 128, Giảng đường tài liệu 1 1 giờ tín chỉ (2 tiết thực học) Lý thuyết Tuần 11 Chương 3: 3.1.1, 3.1.2 Đọc tài liệu 2, tr. 184-186, 2 giờ tín chỉ Giảng đường 190-192 Lý thuyết Tuần 12 Chương 3: 3.1.3 Đọc tài liệu 2, tr. 233-241, 2 giờ tín chỉ Giảng đường 246-252 Lý thuyết Tuần 13 Chương 3: 3.2.1, 3.2.2 Đọc tài liệu 2, tr. 326-327, 2 giờ tín chỉ Giảng đường 333-334, 341-345 Lý thuyết Tuần 14 Chương 3: 3.2.3 Đọc tài liệu 2, tr. 402-415 2 giờ tín chỉ Giảng đường Đọc tài liệu 7, tr. 490-504 Bài tập Tuần 15 Chữa bài tập Chương 3 Làm bài tập 3, 9 tr. 213- 2 giờ tín chỉ Giảng đường 214, 12, 13 tr. 356 tài liệu (4 tiết thực học) 2 5
8. Chính sách đối với môn học và yêu cầu khác của giảng viên - Với thời gian hạn chế trong 2 tín chỉ, khi giảng dạy giảng viên nên giảm bớt các chứng minh toán học chặt chẽ; tăng cường nhiều ví dụ; nêu ý tưởng của thuật toán; nêu những ưu, khuyết điểm chính của thuật toán; giới thiệu cách áp dụng một số phần mềm thông dụng như Matlab, GAMS cho các thuật toán. - Sinh viên được dự thi kết thúc môn học khi có đủ các điều kiện sau: + Có mặt trên lớp không dưới 80% số giờ lí thuyết của môn học; + Có đủ điểm thành phần của môn học. 9. Phương pháp và hình thức kiểm tra, đánh giá kết quả học tập môn học 9.1. Mục đích và trọng số kiểm tra, đánh giá Hình thức Phương pháp Mục đích Trọng số - Kiểm tra việc chuẩn bị Đánh giá khả năng nhớ, bài ở nhà: lí thuyết, bài hiểu và kỹ năng giải bài Kiểm tra đánh giá tập. tập của từng nội dung 10% thường xuyên các chương riêng lẻ - Kết quả giải bài tập trên lớp. Kiểm tra viết 1 lần trong Đánh giá khả năng giải 1 tiết các bài tập có liên quan Kiểm tra giữa kỳ 30% tới các nội dung đã được học Làm bài thi viết 90 phút Đánh giá khả năng hiểu, nhớ và vận dụng lí thuyết Thi kết thúc môn học 60% để giải các bài toán cụ thể Tổng 100% 9.2. Tiêu chí đánh giá các loại bài tập và kiểm tra đánh giá Tiêu chí đánh giá các loại bài tập này gồm: 1) Nắm được nội dung của mỗi chương, giải được các bài tập đơn giản của từng chương; 2) Áp dụng được các thuật toán đã học để giải các bài toán tối ưu cụ thể không quá phức tạp. 3) Biết cách sử dụng các phần mềm để giải được các bài toán tối ưu cụ thể. Điểm Tiêu chí 10 Đạt cả 3 tiêu chí trên 7-9 Đạt tiêu chí 1 và 2 5-6 Đạt tiêu chí 1, tiêu chí 2 chưa giải quyết trọn vẹn Dưới 5 Không đạt được 1 tiêu chí nào trong 3 tiêu chí 9.3. Lịch thi và kiểm tra - Thi giữa kỳ: Tuần thứ 9 - Thi cuối kỳ: Sau tuần 15- Theo lịch thi của trường. ________________________________________________ 6