GIÁO TRÌNH - Tối ưu hoá (PGS.TS. Nguyễn Hải Thanh)

Giáo trình Tối ưu hóa được biên soạn với mục đích cung cấp cho sinh viên năm thứ hai ngành Tin học của Khoa Công nghệ thông tin, Trường Đại học Nông nghiệp Hà Nội một số kiến thức cơ bản về các lĩnh vực quan trọng của Tối ưu hóa. Qua giáo trình này, sinh viên cần nắm được cơ sở lý thuyết ở một mức độ nhất định, nắm chắc các thuật toán tối ưu cơ bản để áp dụng trong việc xây dựng các phần mềm tối ưu tính toán giải các bài toán kinh tế, công nghệ, kỹ thuật và quản lý. Trọng tâm của giáo trình nằm trong việc trình bày các thuật toán tối ưu cơ bản, tuyến tính cũng như phi tuyến. Đây cũng là một vấn đề mới trong giảng dạy môn học này ở bậc đại học, vì hiện nay môn học Tối ưu hóa trong hầu hết các trường đại học trong nước mới chỉ đề cập tới Quy hoạch tuyến tính.
Việc trình bày các phương pháp tối ưu đề cập tới trong giáo trình nhằm tới đích sinh viên phải hiểu được và làm được. Chính vì vậy, các phương pháp luôn được trình bày một cách cụ thể thông qua các ví dụ mẫu từ dễ tới khó, mà những ví dụ này có thể được sử dụng nhiều lần để tiết kiệm thời gian. Trong chừng mực cho phép, các ký hiệu tổng quát sẽ được sử dụng ở mức độ tối thiểu, nhưng không làm giảm tính tổng quát của vấn đề đặt ra cần giải quyết. Các quy trình tính toán, các thuật toán cần luôn được trình bày rõ ràng, có minh họa thông qua việc giải các ví dụ cụ thể, tính toán cho từng bước cụ thể. Phần bài tập, vì vậy, bao gồm cả các bài tập tính tay và các bài tập lập trình bằng ngôn ngữ Pascal hay C. Những sinh viên đã học Matlab cũng có thể lập trình các thuật toán trong Matlab.
Giáo trình gồm sáu chương với thời lượng 3 tới 4 tín chỉ của học chế tín chỉ (tương đương 60 tiết tới 75 tiết của học chế niên chế) và bài tập kèm theo từng chương.


CHƯƠNG I. BÀI TOÁN TỐI ƯU TỔNG QUÁT VÀ ỨNG DỤNG 7
1. BÀI TOÁN TỐI ƯU TỔNG QUÁT VÀ PHÂN LOẠI 7
1.1. Bài toán tối ưu tổng quát 7
1.2. Phân loại các bài toán tối ưu 8
2. ỨNG DỤNG BÀI TOÁN TỐI ƯU GIẢI QUYẾT CÁC VẤN ĐỀ THỰC TẾ 9
2.1. Phương pháp mô hình hóa toán học 9
2.2. Một số ứng dụng của bài toán tối ưu 10
CHƯƠNG II. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 16
1. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH 16
1.1. Phát biểu mô hình 16
1.2. Phương pháp đồ thị 17
2. PHƯƠNG PHÁP ĐƠN HÌNH 19
2.1. Tìm hiểu quy trình tính toán 19
2.2. Khung thuật toán đơn hình 23
3. CƠ SỞ TOÁN HỌC CỦA PHƯƠNG PHÁP ĐƠN HÌNH 23
3.1. Phát biểu bài toán quy hoạch tuyến tính dạng chính tắc 23
3.2. Công thức số gia hàm mục tiêu 25
3.3. Tiêu chuẩn tối ưu 26
3.4. Thuật toán đơn hình cho bài toán quy hoạch tuyến tính dạng chính tắc 27
4. BỔ SUNG THÊM VỀ PHƯƠNG PHÁP ĐƠN HÌNH 29
4.1. Đưa bài toán quy hoạch tuyến tính về dạng chính tắc 29
4.2. Phương pháp đơn hình mở rộng 31
4.3. Phương pháp đơn hình hai pha 33
4.4. Phương pháp đơn hình cải biên 35
BÀI TẬP CHƯƠNG II 41
CHƯƠNG III. BÀI TOÁN ĐỐI NGẪU VÀ MỘT SỐ ỨNG DỤNG 44
1. PHÁT BIỂU BÀI TOÁN ĐỐI NGẪU 44
1.1. Phát biểu bài toán 44
1.2. Ý nghĩa của bài toán đối ngẫu 45
1.3. Quy tắc viết bài toán đối ngẫu 46
1.4. Các tính chất và ý nghĩa kinh tế của cặp bài toán đối ngẫu 48
2. CHỨNG MINH MỘT SỐ TÍNH CHẤT CỦA CẶP BÀI TOÁN ĐỐI NGẪU 53
2.1. Định lý đối ngẫu yếu 54
2.2. Định lý đối ngẫu mạnh 54
2.3. Định lý độ lệch bù 56
3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU 57
3.1. Quy trình tính toán và phát biểu thuật toán 57
3.2. Cơ sở của phương pháp đơn hình đối ngẫu 61
4. BÀI TOÁN VẬN TẢI 62
4.1. Phát biểu bài toán vận tải 62
4.2. Các tính chất của bài toán vận tải 66
4.3. Phương pháp phân phối giải bài toán vận tải 68
4.4. Phương pháp thế vị giải bài toán vận tải 72
4.5. Cơ sở của phương pháp phân phối và phương pháp thế vị 74
BÀI TẬP CHƯƠNG III 78
CHƯƠNG IV. QUY HOẠCH NGUYÊN 81
1. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN 81
1.1. Phát biểu bài toán quy hoạch tuyến tính nguyên 81
1.2. Minh họa phương pháp Gomory bằng đồ thị 82
1.3. Giải bài toán quy hoạch tuyến tính nguyên bằng bảng 84
1.4. Khung thuật toán cắt Gomory 86
2. PHƯƠNG PHÁP NHÁNH CẬN LAND – DOIG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN 87
2.1. Minh họa phương pháp nhánh cận bằng đồ thị 87
2.2. Nội dung cơ bản của phương pháp nhánh cận 88
2.3. Khung thuật toán nhánh cận Land – Doig 88
3. GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN BẰNG QUY HOẠCH ĐỘNG 90
3.1. Bài toán người du lịch 90
3.2. Quy trình tính toán tổng quát 91
3.3. Áp dụng quy hoạch động giải bài toán quy hoạch tuyến tính nguyên 93
3.4. Bài toán cái túi 95
3.5. Hợp nhất hóa các ràng buộc của bài toán quy hoạch tuyến tính nguyên 100
BÀI TẬP CHƯƠNG IV 103
CHƯƠNG V. MỘT SỐ PHƯƠNG PHÁP QUY HOẠCH PHI TUYẾN 105
1. CÁC KHÁI NIỆM CƠ BẢN CỦA BÀI TOÁN TỐI ƯU PHI TUYẾN 105
1.1. Phát biểu bài toán tối ưu phi tuyến 105
1.2. Phân loại các bài toán tối ưu phi tuyến toàn cục 106
1.3. Bài toán quy hoạch lồi 107
1.4. Hàm nhiều biến khả vi cấp một và cấp hai 108
2. MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN KHÔNG RÀNG BUỘC 109
2.1. Phương pháp đường dốc nhất 109
2.2. Phương pháp Newton 111
2.3. Phương pháp hướng liên hợp 113
3. THIẾT LẬP ĐIỀU KIỆN TỐI ƯU KUHN – TUCKER CHO CÁC BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC 116
3.1. Hàm Lagrange 116
3.2. Thiết lập điều kiện Kuhn – Tucker 117
4. MỘT SỐ PHƯƠNG PHÁP GIẢI QUY HOẠCH TOÀN PHƯƠNG 120
4.1. Bài toán quy hoạch toàn phương 120
4.2. Phát biểu điều kiện Kuhn – Tucker cho bài toán quy hoạch toàn phương 121
4.3. Phương pháp Wolfe giải bài toán quy hoạch toàn phương 121
4.4. Giải bài toán quy hoạch toàn phương bằng bài toán bù 123
5. QUY HOẠCH TÁCH VÀ QUY HOẠCH HÌNH HỌC 126
5.1. Quy hoạch tách 126
5.2. Quy hoạch hình học 129
BÀI TẬP CHƯƠNG V 133
CHƯƠNG VI. MỘT SỐ VẤN ĐỀ CƠ SỞ CỦA LÝ THUYẾT QUY HOẠCH LỒI VÀ QUY HOẠCH PHI TUYẾN 136
1. TẬP HỢP LỒI 136
1.1. Bao lồi 136
1.2. Bao đóng và miền trong của tập lồi 138
1.3. Siêu phẳng tách và siêu phẳng tựa của tập lồi 139
1.4. Nón lồi và nón đối cực 144
2. ỨNG DỤNG GIẢI TÍCH LỒI VÀO BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 145
2.1. Điểm cực biên và hướng cực biên 145
2.2. Biểu diễn tập lồi đa diện qua điểm cực biên và hướng cực biên 148
2.3. Điều kiện tối ưu trong phương pháp đơn hình giải bài toán quy hoạch tuyến tính
3. CÁC TÍNH CHẤT CỦA HÀM LỒI 152
3.1. Các định nghĩa và tính chất cơ bản 152
3.2. Dưới vi phân của hàm lồi 153
3.3. Hàm lồi khả vi 155
3.4. Cực đại và cực tiểu của hàm lồi 158
4. CÁC ĐIỀU KIỆN TỐI ƯU FRITZ – JOHN VÀ KUHN – TUCKER 162
4.1. Bài toán tối ưu không ràng buộc 162
4.2. Bài toán tối ưu có ràng buộc 164
4.3. Điều kiện tối ưu Fritz – John 166
4.4. Điều kiện tối ưu Kuhn – Tucker 166
5. MỘT SỐ PHƯƠNG PHÁP HƯỚNG CHẤP NHẬN GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN 170
5.1. Phương pháp hướng chấp nhận 170
5.2. Thuật toán Frank – Wolfe giải bài toán quy hoạch lồi có miền ràng buộc là tập lồi đa diện 172
5.3. Phương pháp gradient rút gọn 172
5.4. Phương pháp đơn hình lồi Zangwill 174
6. GIỚI THIỆU PHƯƠNG PHÁP ĐIỂM TRONG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
6.1. Bài toán ellipsoid xấp xỉ 177
6.2. Một số thuật toán điểm trong 181
BÀI TẬP CHƯƠNG VI 183
TÀI LIỆU THAM KHẢO 186

LINK DOWNLOAD

Giáo trình Tối ưu hóa được biên soạn với mục đích cung cấp cho sinh viên năm thứ hai ngành Tin học của Khoa Công nghệ thông tin, Trường Đại học Nông nghiệp Hà Nội một số kiến thức cơ bản về các lĩnh vực quan trọng của Tối ưu hóa. Qua giáo trình này, sinh viên cần nắm được cơ sở lý thuyết ở một mức độ nhất định, nắm chắc các thuật toán tối ưu cơ bản để áp dụng trong việc xây dựng các phần mềm tối ưu tính toán giải các bài toán kinh tế, công nghệ, kỹ thuật và quản lý. Trọng tâm của giáo trình nằm trong việc trình bày các thuật toán tối ưu cơ bản, tuyến tính cũng như phi tuyến. Đây cũng là một vấn đề mới trong giảng dạy môn học này ở bậc đại học, vì hiện nay môn học Tối ưu hóa trong hầu hết các trường đại học trong nước mới chỉ đề cập tới Quy hoạch tuyến tính.
Việc trình bày các phương pháp tối ưu đề cập tới trong giáo trình nhằm tới đích sinh viên phải hiểu được và làm được. Chính vì vậy, các phương pháp luôn được trình bày một cách cụ thể thông qua các ví dụ mẫu từ dễ tới khó, mà những ví dụ này có thể được sử dụng nhiều lần để tiết kiệm thời gian. Trong chừng mực cho phép, các ký hiệu tổng quát sẽ được sử dụng ở mức độ tối thiểu, nhưng không làm giảm tính tổng quát của vấn đề đặt ra cần giải quyết. Các quy trình tính toán, các thuật toán cần luôn được trình bày rõ ràng, có minh họa thông qua việc giải các ví dụ cụ thể, tính toán cho từng bước cụ thể. Phần bài tập, vì vậy, bao gồm cả các bài tập tính tay và các bài tập lập trình bằng ngôn ngữ Pascal hay C. Những sinh viên đã học Matlab cũng có thể lập trình các thuật toán trong Matlab.
Giáo trình gồm sáu chương với thời lượng 3 tới 4 tín chỉ của học chế tín chỉ (tương đương 60 tiết tới 75 tiết của học chế niên chế) và bài tập kèm theo từng chương.


CHƯƠNG I. BÀI TOÁN TỐI ƯU TỔNG QUÁT VÀ ỨNG DỤNG 7
1. BÀI TOÁN TỐI ƯU TỔNG QUÁT VÀ PHÂN LOẠI 7
1.1. Bài toán tối ưu tổng quát 7
1.2. Phân loại các bài toán tối ưu 8
2. ỨNG DỤNG BÀI TOÁN TỐI ƯU GIẢI QUYẾT CÁC VẤN ĐỀ THỰC TẾ 9
2.1. Phương pháp mô hình hóa toán học 9
2.2. Một số ứng dụng của bài toán tối ưu 10
CHƯƠNG II. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 16
1. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH 16
1.1. Phát biểu mô hình 16
1.2. Phương pháp đồ thị 17
2. PHƯƠNG PHÁP ĐƠN HÌNH 19
2.1. Tìm hiểu quy trình tính toán 19
2.2. Khung thuật toán đơn hình 23
3. CƠ SỞ TOÁN HỌC CỦA PHƯƠNG PHÁP ĐƠN HÌNH 23
3.1. Phát biểu bài toán quy hoạch tuyến tính dạng chính tắc 23
3.2. Công thức số gia hàm mục tiêu 25
3.3. Tiêu chuẩn tối ưu 26
3.4. Thuật toán đơn hình cho bài toán quy hoạch tuyến tính dạng chính tắc 27
4. BỔ SUNG THÊM VỀ PHƯƠNG PHÁP ĐƠN HÌNH 29
4.1. Đưa bài toán quy hoạch tuyến tính về dạng chính tắc 29
4.2. Phương pháp đơn hình mở rộng 31
4.3. Phương pháp đơn hình hai pha 33
4.4. Phương pháp đơn hình cải biên 35
BÀI TẬP CHƯƠNG II 41
CHƯƠNG III. BÀI TOÁN ĐỐI NGẪU VÀ MỘT SỐ ỨNG DỤNG 44
1. PHÁT BIỂU BÀI TOÁN ĐỐI NGẪU 44
1.1. Phát biểu bài toán 44
1.2. Ý nghĩa của bài toán đối ngẫu 45
1.3. Quy tắc viết bài toán đối ngẫu 46
1.4. Các tính chất và ý nghĩa kinh tế của cặp bài toán đối ngẫu 48
2. CHỨNG MINH MỘT SỐ TÍNH CHẤT CỦA CẶP BÀI TOÁN ĐỐI NGẪU 53
2.1. Định lý đối ngẫu yếu 54
2.2. Định lý đối ngẫu mạnh 54
2.3. Định lý độ lệch bù 56
3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU 57
3.1. Quy trình tính toán và phát biểu thuật toán 57
3.2. Cơ sở của phương pháp đơn hình đối ngẫu 61
4. BÀI TOÁN VẬN TẢI 62
4.1. Phát biểu bài toán vận tải 62
4.2. Các tính chất của bài toán vận tải 66
4.3. Phương pháp phân phối giải bài toán vận tải 68
4.4. Phương pháp thế vị giải bài toán vận tải 72
4.5. Cơ sở của phương pháp phân phối và phương pháp thế vị 74
BÀI TẬP CHƯƠNG III 78
CHƯƠNG IV. QUY HOẠCH NGUYÊN 81
1. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN 81
1.1. Phát biểu bài toán quy hoạch tuyến tính nguyên 81
1.2. Minh họa phương pháp Gomory bằng đồ thị 82
1.3. Giải bài toán quy hoạch tuyến tính nguyên bằng bảng 84
1.4. Khung thuật toán cắt Gomory 86
2. PHƯƠNG PHÁP NHÁNH CẬN LAND – DOIG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN 87
2.1. Minh họa phương pháp nhánh cận bằng đồ thị 87
2.2. Nội dung cơ bản của phương pháp nhánh cận 88
2.3. Khung thuật toán nhánh cận Land – Doig 88
3. GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN BẰNG QUY HOẠCH ĐỘNG 90
3.1. Bài toán người du lịch 90
3.2. Quy trình tính toán tổng quát 91
3.3. Áp dụng quy hoạch động giải bài toán quy hoạch tuyến tính nguyên 93
3.4. Bài toán cái túi 95
3.5. Hợp nhất hóa các ràng buộc của bài toán quy hoạch tuyến tính nguyên 100
BÀI TẬP CHƯƠNG IV 103
CHƯƠNG V. MỘT SỐ PHƯƠNG PHÁP QUY HOẠCH PHI TUYẾN 105
1. CÁC KHÁI NIỆM CƠ BẢN CỦA BÀI TOÁN TỐI ƯU PHI TUYẾN 105
1.1. Phát biểu bài toán tối ưu phi tuyến 105
1.2. Phân loại các bài toán tối ưu phi tuyến toàn cục 106
1.3. Bài toán quy hoạch lồi 107
1.4. Hàm nhiều biến khả vi cấp một và cấp hai 108
2. MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN KHÔNG RÀNG BUỘC 109
2.1. Phương pháp đường dốc nhất 109
2.2. Phương pháp Newton 111
2.3. Phương pháp hướng liên hợp 113
3. THIẾT LẬP ĐIỀU KIỆN TỐI ƯU KUHN – TUCKER CHO CÁC BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC 116
3.1. Hàm Lagrange 116
3.2. Thiết lập điều kiện Kuhn – Tucker 117
4. MỘT SỐ PHƯƠNG PHÁP GIẢI QUY HOẠCH TOÀN PHƯƠNG 120
4.1. Bài toán quy hoạch toàn phương 120
4.2. Phát biểu điều kiện Kuhn – Tucker cho bài toán quy hoạch toàn phương 121
4.3. Phương pháp Wolfe giải bài toán quy hoạch toàn phương 121
4.4. Giải bài toán quy hoạch toàn phương bằng bài toán bù 123
5. QUY HOẠCH TÁCH VÀ QUY HOẠCH HÌNH HỌC 126
5.1. Quy hoạch tách 126
5.2. Quy hoạch hình học 129
BÀI TẬP CHƯƠNG V 133
CHƯƠNG VI. MỘT SỐ VẤN ĐỀ CƠ SỞ CỦA LÝ THUYẾT QUY HOẠCH LỒI VÀ QUY HOẠCH PHI TUYẾN 136
1. TẬP HỢP LỒI 136
1.1. Bao lồi 136
1.2. Bao đóng và miền trong của tập lồi 138
1.3. Siêu phẳng tách và siêu phẳng tựa của tập lồi 139
1.4. Nón lồi và nón đối cực 144
2. ỨNG DỤNG GIẢI TÍCH LỒI VÀO BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 145
2.1. Điểm cực biên và hướng cực biên 145
2.2. Biểu diễn tập lồi đa diện qua điểm cực biên và hướng cực biên 148
2.3. Điều kiện tối ưu trong phương pháp đơn hình giải bài toán quy hoạch tuyến tính
3. CÁC TÍNH CHẤT CỦA HÀM LỒI 152
3.1. Các định nghĩa và tính chất cơ bản 152
3.2. Dưới vi phân của hàm lồi 153
3.3. Hàm lồi khả vi 155
3.4. Cực đại và cực tiểu của hàm lồi 158
4. CÁC ĐIỀU KIỆN TỐI ƯU FRITZ – JOHN VÀ KUHN – TUCKER 162
4.1. Bài toán tối ưu không ràng buộc 162
4.2. Bài toán tối ưu có ràng buộc 164
4.3. Điều kiện tối ưu Fritz – John 166
4.4. Điều kiện tối ưu Kuhn – Tucker 166
5. MỘT SỐ PHƯƠNG PHÁP HƯỚNG CHẤP NHẬN GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN 170
5.1. Phương pháp hướng chấp nhận 170
5.2. Thuật toán Frank – Wolfe giải bài toán quy hoạch lồi có miền ràng buộc là tập lồi đa diện 172
5.3. Phương pháp gradient rút gọn 172
5.4. Phương pháp đơn hình lồi Zangwill 174
6. GIỚI THIỆU PHƯƠNG PHÁP ĐIỂM TRONG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
6.1. Bài toán ellipsoid xấp xỉ 177
6.2. Một số thuật toán điểm trong 181
BÀI TẬP CHƯƠNG VI 183
TÀI LIỆU THAM KHẢO 186

LINK DOWNLOAD

Chuyên mục: C. Bài giảng C. Bài giảng kinh tế C. Bài giảng kinh tế khác (Others)