Giáo trình: Tối ưu hóa – Nguyễn Hải Thanh

Giáo trình trình bày những chủ đề cơ bản nhất trong lí thuyết tối ưu. Các bạn SV trường Đại học Thương mại có thể tham khảo chương I, II và III để hiểu thêm về học phần Các phương pháp Toán kinh tế.

Mục lục:

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 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 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 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 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

Link tài tiệu: http://www.vcef.edu.vn/Resources/file/68719614-toi-uuhoa.pdf

or http://www.scribd.com/doc/53763634/toi-uuhoa

————&&————

3 phản hồi

  1. Thưa thầy em đã đọc bài Giới thiệu phần mềm giải bài toán QHTT của thầy trên trang scribd.com, em hiện đang làm đồ án về đề tài này, thầy cho em hỏi phần mềm này được viết bằng java hay c ah? Thầy có thể gửi cho em phần code của bài toán vận tải được không ah?
    Em xin cảm ơn.

    • 1. Tôi không gửi code được đâu.
      2. Nếu bạn đã đọc bài giới thiệu thì sẽ thấy ý tưởng: Chúng tôi dùng mã nguồn mở của java commons math http://commons.apache.org/math/ để giải bài toán QHTT, còn bài toán vận tải thì đưa về bài toán QHTT (cách đưa thuẩn túy toán học – nói chính xác thì bài toán vận tải là trường hợp riêng of bài toán QHTT, các tài liệu toán đều có giải thích điều này). Phần mềm viết hoàn toàn bằng java.

  2. Cảm ơn thầy đã giới thiệu tài liệu Tối ưu hóa của PGS.TS Nguyễn Hải Thanh.
    Tiện thể thông báo link http://elib.dtu.edu.vn/file/Ebook/872.pdf bị lỗi rồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: