Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (134.15 KB, 25 trang )
gi ( x ) ,i =1, m được gọi là các hàm ràng buộc, mỗi
Các hàm:
đẳng thức hoặc bất đẳng thức trong hệ (1.2) được gọi là một
ràng buộc.
Tập hợp:
{
}
D = x ∈ X | g i ( x ) ( ≤, =, ≥ ) bi , i = 1, m
(1.4)
Được gọi là miền ràng buộc (hay miền chấp nhận được).
Mỗi điểm:
x = ( x1 , x2 ,…, xn ) ∈ D được gọi là một phương án
hay một lời giải chấp nhận được.
Một phương án: x
mục tiêu, cụ thể là:
∗
∈D
đạt cực đại (hay cực tiểu) của hàm
f ( x∗ ) ≥ f ( x),∀x ∈ D (đối với bài toán max)
f ( x∗ ) ≤ f ( x),∀x ∈ D (đối với bài toán min)
được gọi là phương án tối ưu (hay lời giải tối
ưu). Khi đó giá trị f(x*) được gọi là giá trị tối ưu
của bài toán
2. Phân loại các bài toán tối ưu
Một trong những phương pháp hiển nhiên nhất để giải bài
toán tối ưu là phương pháp điểm diện: Tính giá trị hàm mục
tiêu f(x) trên tất cả các phương án, sau đó so sánh các giá
trị tính được để tìm ra giá trị tối ưu và phương án tối ưu của
bài toán.
Thực hiện theo phương pháp trên gặp rất nhiều khó khăn
ngay cả khi kích thước của bài toán(số biến n và số ràng
buộc m) là không lớn, bởi vì tập D thông thường gồm một số
rất lớn các phần tử, trong nhiều trường hợp còn là không
đếm được.
Vì vậy,người ta đã nghiên cứu về mặt lý thuyết
để có thể tách ra từ bài toán tổng quát thành các
lớp bài toán dễ giải. Các nghiên cứu lý thuyết đó
thường là:
– Nghiên cứu các tính chất của các thành
phần bài toán(hàm mục tiêu, các hàm ràng
buộc, các biến số, các hệ số…);
– Các điều kiện tồn tại lời giải chấp nhận
được;
– Các điều kiện cần và đủ của cực trị;
– Tính chất của các đối tượng nghiên cứu.
Dựa vào tính chất của các thành phần bài toán và
đối tượng nghiên cứu để người ta phân loại các
lớp bài toán tối ưu(hay bài toán quy hoạch) như
sau:
