Tối ưu hóa phần 1

MỞ ĐẦU CHƯƠNG I. BÀI TOÁN TỐI ƯU TỔNG QUÁT VÀ ỨNG DỤNG 1. BÀI TOÁN TỐI ƯU TỔNG QUÁT VÀ PHÂN LOẠI 1.1. Bài toán tối ưu tổng quát 1.2. Phân loại các bài toán tối ưu 2. ỨNG DỤNG BÀI TOÁN TỐI ƯU GIẢI QUYẾT CÁC VẤN ĐỀ THỰC TẾ 2.1. Phương pháp mô hình hóa toán học 2.2. Một số ứng dụng của bài toán tối ưu CHƯƠNG II. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH 1.1. Phát biểu mô hình 1.2. Phương pháp đồ thị...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa phần 1 Trường Đại học Nông nghiệp I PGS. TS. NGUYỄN HẢI THANH Tối ưu hóa Giáo trình cho ngành Tin học và Công nghệ thông tin Nhà xuất bản Bách khoa – Hà Nội 1 Mã số: 920 − 2006 / CBX / 01 − 130 / BKHN 2 MỤC LỤC 6 MỞ ĐẦU 7 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 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 9 2. ỨNG DỤNG BÀI TOÁN TỐI ƯU GIẢI QUYẾT CÁC VẤN ĐỀ THỰC TẾ 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 16 QUY HOẠCH TUYẾN TÍNH 16 1. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH 1.1. Phát biểu mô hình 16 1.2. Phương pháp đồ thị 17 19 2. PHƯƠNG PHÁP ĐƠN HÌNH 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 23 3. CƠ SỞ TOÁN HỌC CỦA PHƯƠNG PHÁP ĐƠN HÌNH 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 29 4. BỔ SUNG THÊM VỀ PHƯƠNG PHÁP ĐƠN HÌNH 4.1. Đưa bài toán quy hoạch tuyến tính về dạng chính tắc 29 31 4.2. Phương pháp đơn hình mở rộng 33 4.3. Phương pháp đơn hình hai pha 35 4.4. Phương pháp đơn hình cải biên 41 BÀI TẬP CHƯƠNG II 44 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 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 53 2. CHỨNG MINH MỘT SỐ TÍNH CHẤT CỦA CẶP BÀI TOÁN ĐỐI NGẪU 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 57 3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU 3 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 62 4. BÀI TOÁN VẬN TẢI 62 4.1. Phát biểu bài toán vận tải 66 4.2. Các tính chất của bài toán vận tải 68 4.3. Phương pháp phân phối giải bài toán vận tải 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 78 BÀI TẬP CHƯƠNG III 81 CHƯƠNG IV. QUY HOẠCH NGUYÊN 1. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN 81 QUY HOẠCH TUYẾN TÍNH NGUYÊN 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ị ...