Chương 6
Bài toán tối ưu
GV: Nguyễn Thị Thùy Liên Email: lien.nguyenthithuy@phenikaa-uni.edu.vn
2
Bài toán tối ưu
❖Trong toán học, thuật ngữ tối ưu hóa chỉ việc nghiên cứu
cá bài toán có dạng:
Cho trước một hàm f: A->R từ tập hợp A tới tập số thực.
Tìm: một phần từ x0thuộc A:
sao cho f(x0)≤f(x) với mọi x thuộc A(“cực tiểu hóa”)
hoặc sao cho f(x0)≥f(x) với mọi x thuộc A(“cực đại hóa”)
❖Một phát biểu bài toán như vậy đôi khi được gọi là một
quy hoạch toán học. Nhiều bài toán thực tế và lý thuyết có
thể được mô hình theo cách tổng quát trên.
Tin hc ng dng
3
Bài toán tối ưu
❖Miền xác định A của hàm f được gọi là không gian tìm
kiếm. Thông thường là tập con của Rn, thường được xác
định bởi một tập các ràng buộc, các đẳng thức, bất đẳng
thức mà các thành viên của A phải thỏa mãn.
❖Các phần tử của A được gọi là các lời giải khả thi.
❖Hàm f được gọi là hàm mục tiêu hoặc hàm chi phí cực tiểu
hóa(hoặc cực đại hóa) hàm mục tiêu được gọi là lời giải
tối ưu.
❖Các lĩnh vực con chính:
▪Quy hoạch tuyến tính
▪Quy hoạch phi tuyến
Tin hc ng dng
4
Bài toán quy hoạch tuyến tính
❖Mô hình bài toán quy hoạch tuyến tính (QHTT)
❖Hàm mục tiêu:
f(x1,.. xn) =
Hệ ràng buộc
: ràng buộc quản lý (=, >=, <=)
Xi là các số thực
=
→
n
1j
max(min)CjXj
=
n
1j
BiAijXj
Tin hc ng dng
5
Bài toán quy hoạch tuyến tính
❖Phương án: Một véc tơ x=(x1, x2,….xn) thỏa mãn hệ
ràng buộc phương án của bài toán
❖Phương án tối ưu: Một phương án mà tai đó hàm mục
tiêu đạt giá trị cực tiểu (hoặc cực đại)
=> Giải bài toán tối ưu chính là đi tìm phương án tối ưu
Tin hc ng dng