Bài giảng: Tài liệu tối ưu hóa

Bài giảng: Tài liệu tối ưu hóa

Mô tả cơ bản về tài liệu:

Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính giá trị của hàm ()fx trên tất cả các phương án của miền ràng buộc sau đó so sánh các giá trị của hàm mục tiêu thu được để tìm ra phương án tối ưu. Tuy nhiên cách làm này là rất khó hoặc đúng hơn là không thể làm được trong trường hợp tổng quát (chẳng hạn tập là không đếm được). Vì vậy chúng ta phải phân tách nhỏ ra bằng cách thêm một số điều kiện nào đó để được......

Nội dung trích xuất từ tài liệu:

Bài giảng: Tài liệu tối ưu hóa ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN -----o0o----- Bài giảng môn TỐI ƯU HÓA THÂN QUANG KHOÁT Thái nguyên - 2007 Thân Quang Khoát 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 Bộ môn Khoa Học Cơ Bản 1 Bài Giảng môn Tối Ưu Hoá 4.3. Một số ví dụ ....................................................................................................34 §5. PHƯƠNG PHÁP ĐÁNH THUẾ.........................................................................36 §6. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ...................................41 6.1. Bài toán đối ngẫu ............................................................................................41 6.2. Các định lý đối ngẫu .......................................................................................42 6.3. Một số ứng dụng của lý thuyết đối ngẫu ........................................................44 6.4. Thuật toán đơn hình đối ngẫu .........................................................................46 Chương 3. TỐI ƯU HOÁ RỜI RẠC .........................................................................56 §1. BÀI TOÁN TỐI ƯU HOÁ RỜI RẠC.................................................................56 1.1. Mở đầu ............................................................................................................56 1.2. Một số bài toán tối ưu hoá rời rạc tiêu biểu....................................................56 §2. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QHTT NGUYÊN ..........58 2.1. Tư tưởng chung của phương pháp cắt ............................................................58 2.2. Phương pháp cắt Gomory cho bài toán QHTT nguyên hoàn toàn .................59 2.3. Phương pháp cắt Gomory cho bài toán QHTT nguyên bộ phận ....................64 §3. PHƯƠNG PHÁP NHÁNH CẬN ........................................................................65 3.1. Sơ đồ tổng quát ...............................................................................................65 3.2. Thuật toán nhánh cận Land-Doig giải bài toán QHTT nguyên ......................66 3.3. Một số ví dụ ........................................................... ...