Đề 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

TT

Họ và tên

Địa chỉ liên hệ

Điện thoại

Chức danh, học vị

1 Phạm Trọng Quát

PGS. TS. ĐHQGHN

0913247974

2 Nguyễn Ngọc Thắng

GVC

0913005223

Khoa Toán-Cơ-Tin học, trường ĐHKHTN

3 Nguyễn Hữu Điển

PGS. TS.

0989061951

Khoa Toán-Cơ-Tin học, trường ĐHKHTN

4 Nguyễn Đình Hóa

PGS. TS.

0193281197

Viện Công nghệ thông tin, ĐHQGHN

5 Hoàng Xuân Huấn

PGS. TS

Trường ĐH Công nghệ

6 Lê Công Lợi

TS.

0904183257

Khoa Toán-Cơ-Tin học, 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

Bậc 1 (Nhớ)

Bậc 2 (Hiểu)

Bậc 3 (Áp dụng)

Mục tiêu Nội dung

Biết chuyển một số mô hình thực tế về bài toán tối ưu.

Chương 1 Mở đầu

- Hiểu cách phân loại các bài toán tối ưu.

- Các dạng của bài toán quy hoạch tuyến tính. - Cách thiết lập bài toán đối ngẫu.

- Thuật toán đơn hình, hai pha, đối ngẫu. - Sử dụng được các phần mềm đã có để giải các bài toán quy hoạch tuyến tính.

Chương 2 Bài toán quy hoạch tuyến tính

- Cách phân loại các bài toán tối ưu. - Một số khái niệm cơ bản trong giải tích lồi. - Các dạng của bài toán quy hoạch tuyến tính. - Thuật toán đơn hình, hai pha. - Cách thiết lập bài toán đối ngẫu, các định lý đối ngẫu, thuật toán đối ngẫu. - 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.

Các điều kiện tối ưu cho bài toán quy hoạch phi tuyến không ràng buộc và có ràng buộc.

- Điều kiện tối ưu của bài toán không ràng buộc và có ràng buộc. - Phương pháp Gradient, phương pháp Newton, hàm phạt, hàm chắn.

Chương 3 Mở đầu về bài toán quy hoạch phi tuyến

- Áp dụng được các phương pháp Gradient, Newton, hàm phạt và hàm chắn để giải các bài toán quy hoạch phi tuyến cụ thể. - Biết sử dụng một số 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

Tổng Nội dung Tự học, tự nghiên cứu Kiểm tra, đánh giá Lý thuyết

Chương 1 Chương 2 Chương 3 Kiểm tra Tổng cộng Lên lớp Bài tập 4 2 6 3 12 8 23 1 1 3 16 10 1 30 Thảo luận

4

7.2 Lịch trình tổ chức giảng dạy cụ thể

Nội dung chính

Yêu cầu SV chuẩn bị

Hình thức tổ chức dạy học

Đọc tài liệu 1, tr. 1-7

Chương 1: 1.1, 1.2, 1.3 - Chương 1: 1.4, 1.5 - Chương 2 : 2.1, 2.2 Chương 2: 2.3.1, 2.3.2

Đọc tài liệu 1, tr. 7-24 Đọc tài liệu 1, tr. 23-34

Chương 2: 2.3.2, 2.3.3 Đọc tài liệu 1, tr. 40-46

Chương 2: 2.3.3, 2.4

Đọc tài liệu 1, tr. 136-140

Đọc tài liệu 1, tr. 63-83

Thời gian, địa điểm Tuần 1 Giảng đường Tuần 2 Giảng đường Tuần 3 Giảng đường Tuần 4 Giảng đường Tuần 5 Giảng đường Tuần 6 Giảng đường

Chương 2: 2.5.1, 2.5.2 - Chương 2: 2.5.3 - Chữa bài tập Chương 2

- Đọc tài liệu 1, tr. 84-92 - Làm bài tập 1-5, tr. 61-62 tài liệu 1

Tuần 7 Giảng đường

Làm bài tập chương III tr. 92-93 tài liệu 1

Chữa bài tập Chương 2

Tuần 8 Giảng đường

Chương 2: 2.6

Đọc tài liệu 1, tr. 94-102, 105-114

Tuần 9 Giảng đường

- Chương 2 : 2.7 - Chữa bài tập Chương 2

Tuần 10 Giảng đường

- Đọc tài liệu 2, tr. 134-136 - Đọc tài liệu 4, tr. 315-323 - Làm bài tập 1-2, tr. 128, tài liệu 1

Đọc tài liệu 2, tr. 184-186, 190-192

Đọc tài liệu 2, tr. 233-241, 246-252

Chương 3: 3.1.1, 3.1.2 Chương 3: 3.1.3 Chương 3: 3.2.1, 3.2.2

Đọc tài liệu 2, tr. 326-327, 333-334, 341-345

Chương 3: 3.2.3

Chữa bài tập Chương 3

Đọc tài liệu 2, tr. 402-415 Đọc tài liệu 7, tr. 490-504 Làm bài tập 3, 9 tr. 213- 214, 12, 13 tr. 356 tài liệu 2

Tuần 11 Giảng đường Tuần 12 Giảng đường Tuần 13 Giảng đường Tuần 14 Giảng đường Tuần 15 Giảng đường

Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ - Lý thuyết 1 giờ tín chỉ -Bài tập 1 giờ tín chỉ (2 tiết thực học) Bài tập 2 giờ tín chỉ (4 tiết thực học) - Kiểm tra giữa kỳ 1 giờ tín chỉ - Lý thuyết 1 giờ tín chỉ - Lý thuyết 1 giờ tín chỉ - Bài tập 1 giờ tín chỉ (2 tiết thực học) Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Lý thuyết 2 giờ tín chỉ Bài tập 2 giờ tín chỉ (4 tiết thực học)

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á

Phương pháp

Mục đích

Trọng số

Hình thức

10%

Kiểm tra đánh giá thường xuyên

Đánh giá khả năng nhớ, hiểu và kỹ năng giải bài tập của từng nội dung các chương riêng lẻ

- Kiểm tra việc chuẩn bị bài ở nhà: lí thuyết, bài tập. - Kết quả giải bài tập trên lớp. Kiểm tra viết 1 lần trong 1 tiết Kiểm tra giữa kỳ

30%

Đánh giá khả năng giải các bài tập có liên quan tới các nội dung đã được học

Thi kết thúc môn học

60%

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 để 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 7-9 5-6 Dưới 5 Đạt cả 3 tiêu chí trên Đạt tiêu chí 1 và 2 Đạt tiêu chí 1, tiêu chí 2 chưa giải quyết trọn vẹn 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