Chương 2
TỐI ƯU HÓA RỜI RẠC
TỐI ƯU HÓA RỜI RẠC
10/6/2012 1MaMH: C02012 Chương 2: Tối ưu hóa rời rạc
NỘI DUNG
1. Bài toán tốiưu hóa rời rạc (tốiưu tổhợp)
2. Bài toán ba lô (bài toán cái túi)
3. Bài toán Quy hoạch (QH) nguyên tuyến tính
4. Thuật toán Gomory
5. Phương pháp nhánh cận Land – Doig
10/6/2012 2MaMH: C02012 Chương 2: Tối ưu hóa rời rạc
BÀI TOÁN TỐI ƯU HÓA RỜI RẠC
Định nghĩaBài toán tốiưu hóa rời rạc xác định
trên tập hữu hạnS, và
: .
f S
→
ℝ
*
:
s S
∈
*
( ) min{ ( )}
.
s S
∈
=
10/6/2012 3MaMH: C02012 Chương 2: Tối ưu hóa rời rạc
BÀI TOÁN TỐI ƯU HÓA RỜI RẠC
Tốiưu hóa rời rạc dựa vào:
•Quy hoạch tuyến tính
•Lý thuyếtđồ thị
•Lý thuyết về độ phức tạp tính toán
10/6/2012 4MaMH: C02012 Chương 2: Tối ưu hóa rời rạc
BÀI TOÁN TỐI ƯU HÓA RỜI RẠC
Một sốví dụvềbài toán tốiưu rời rạc:
•Bài toán tìm đường đi ngắn nhất
•Bài toán ba lô
•Bài toán người du lịch
10/6/2012 5MaMH: C02012 Chương 2: Tối ưu hóa rời rạc