Tối ưu hoá PGS.TS Nguyễn Hải Thanh - Giáo trình cho chuyên ngành tin học và công nghệ thông tin

MỞ ĐẦU 6
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
4.2. Phương pháp đơn hình mở rộng
4.3. Phương pháp đơn hình hai pha
4.4. Phương pháp đơn hình cải biên
29
31
33
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 4
3.1. Quy trình tính toán và phát biểu thuật toán
3.2. Cơ sở của phương pháp đơn hình đối ngẫu
57
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
4.2. Các tính chất của bài toán vận tải
4.3. Phương pháp phân phối giải bài toán vận tải
62
66
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
2.3. Khung thuật toán nhánh cận Land – Doig
88
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
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
95
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
1.4. Hàm nhiều biến khả vi cấp một và cấp hai
107
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
2.3. Phương pháp hướng liên hợp
111
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 5
4.3. Phương pháp Wolfe giải bài toán quy hoạch toàn phương
4.4. Giải bài toán quy hoạch toàn phương bằng bài toán bù
121
123
5. QUY HOẠCH TÁCH VÀ QUY HOẠCH HÌNH HỌC 126
5.1. Quy hoạch tách
5.2. Quy hoạch hình học
126
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
1.4. Nón lồi và nón đối cực
139
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
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
148

150
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
4.4. Điều kiện tối ưu Kuhn – Tucker
166
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
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
170

172
5.3. Phương pháp gradient rút gọn
5.4. Phương pháp đơn hình lồi Zangwill
172
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

177
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