Tài liệu Tối ưu hóa

MỤC LỤC
Chương 1. MỞ ĐẦU 3
§1. ĐỐI TƯỢNG NGHIÊN CỨU .3
1.1. Bài toán tối ưu tổng quát .3
1.2. Phân loại bài toán 3
1.3. Một số mô hình thực tế .4
§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 6
2.1. Dạng tổng quát 6
2.2. Dạng chuẩn tắc 7
2.3. Dạng chính tắc .7
§3. MỘT SỐ KIẾN THỨC BỔ TRỢ 9
3.1. Tập hợp lồi và điểm cực biên 9
3.2. Đa diện lồi (polytope) .10
§4. CẤU TRÚC MIỀN RÀNG BUỘC CỦA BÀI TOÁN 11
QUY HOẠCH TUYẾN TÍNH 11
4.1. Phương án cực biên và phương án cực biên tối ưu .11
4.2. Điều kiện cần và đủ để một phương án là cực biên 13
4.3. Cơ sở của một phương án cực biên .15
Chương 2. THUẬT TOÁN ĐƠN HÌNH 17
§1. MỞ ĐẦU .17
1.1. Bài toán .17
1.2. Phương pháp Hình Học .17
§2. THUẬT TOÁN ĐƠN HÌNH .19
2.1. Tư tưởng của thuật toán đơn hình .19
2.2. Công thức số gia hàm mục tiêu - dấu hiệu tối ưu .20
2.3. Tìm phương án cực biên tốt hơn - Công thức đổi cơ sở .21
2.4. Thuật toán đơn hình (Simplex method) 23
2.5. Bảng đơn hình .24
§3. TÍNH HỮU HẠN CỦA THUẬT TOÁN ĐƠN HÌNH .28
3.1. Trường hợp bài toán không suy biến 28
3.2. Trường hợp bài toán suy biến .28
§4. PHƯƠNG PHÁP HAI PHA 31
4.1. Vấn đề .31
4.2. Phương pháp hai pha giải bài toán QHTT 32