Bài giảng Toán rời rạc - Bài toán tối ưu
Bài toán tối ưu
TOÁN RỜI RẠC
NỘI DUNG
Giới thiệu
Kỹ thuật nhánh cận
Kỹ thuật nhánh cận giải bài toán người bán hàng
GIỚI THIỆU
Bài toán tối ưu: Là bài toán tìm ra tổ hợp tốt nhất trong
những tổ hợp có thể tạo ra, thỏa mãn yêu cầu cho trước.
Tối ưu tổ hợp có rất nhiều ứng dụng trong thực tế.
MỘT SỐ BÀI TOÁN TỐI ƯU
Xếp ba lô (1): có 1 chiếc ba lô, mang được không quá
trọng lượng b. Có n đồ vật với trọng lượng: a1, …, an và
giá trị c1, …, cn tương ứng. Hỏi ta xếp vào ba lô những
vật nào để mang được giá trị lớn nhất?
Xếp ba lô (2): tương tự như bài 1 nhưng mỗi loại đồ vật
có thể mang theo từ 0->m lần
MỘT SỐ BÀI TOÁN TỐI ƯU
Bài toán người bán hàng:
1 người bán hàng cần giao hàng đến n điểm: T1, …, Tn.
Đường đi: Xuất phát từ một địa điểm Ti, đi qua tất cả các
điểm còn lại, mỗi nơi đi qua đúng 1 lần rồi quay trở lại vị
trí xuất phát.
Biết Cij là chi phí đi từ địa điểm Ti đến Tj .
Yêu cầu: Hãy tìm một hành trình thỏa mãn yêu cầu có
tổng chi phí nhỏ nhất.
MỘT SỐ BÀI TOÁN TỐI ƯU
Bài toán phân công: Có n công việc và n thợ. Cij là chi
phí để trả cho thợ i làm công việc j. Hãy tìm cách thuê
thợ sao cho tổng chi phí là nhỏ nhất. Lưu ý: mỗi thợ chỉ
làm 1 việc và 1 việc chỉ làm bởi 1 thợ.
MỘT SỐ BÀI TOÁN TỐI ƯU
Bài toán trả tiền ATM: Khách hàng yêu cầu rút số tiền n.
Trong cây ATM có các loại tiền với mệnh giá: a1, …, am.
Tính xem cây phải trả tiền như thế nào để số tờ tiền là ít
nhất?
BÀI TOÁN
Dạng tổng quát của bài toán tối ưu:
Cho tập hữu hạn phần tử D
Hàm mục tiêu f(X) xác định trên D
Mỗi phần tử X ∈ D có dạng X = (x1, x2, …, xn) được gọi
là 1 phương án
Yêu cầu: Tìm phương án X0 sao cho f(X0) đạt cực đại
(cực tiểu) trên D.
Phương án X0 được gọi là phương án tối ưu.
VÍ DỤ
Bài toán xếp ba lô 1 (mỗi đồ vật chọn không quá 1 lần):
Tập phương án (D): Tập các bộ n phần tử (x1, …, xn) trong
đó xi = 0 nếu không chọn vật thứ i và = 1 nếu chọn.
Hàm mục tiêu (f) : Tổng giá trị các đồ vật xếp được:
σ푛
f 푥 = 푖=1 푥푖푐푖
Điều kiện: Tổng khối lượng không quá b:
σ푛푖=1
푥푖푎푖 ≤ 푏
Yêu cầu: Tìm phương án thỏa mãn điều kiện và làm hàm
mục tiêu đạt cực đại
KỸ THUẬT NHÁNH CẬN
KỸ THUẬT NHÁNH CẬN
Kỹ thuật nhánh cận phát triển từ ý tưởng của thuật toán
quay lui.
Thay vì duyệt tất cả các trường hợp, nếu ta đến một vị
trí mà giá trị của hàm mục tiêu tại đó và các điểm về
sau chắc chắn không tốt nhất thì quay lại luôn
TƯ TƯỞNG CỦA KỸ THUẬT NHÁNH CẬN
Xét bài toán:
Tìm min {f(x) | x ∈ D}
D = {x = (x1, …, xn) ∈ A1 … An; x thỏa mãn t/c P}
Một bộ (a1, …, ak) là phương án bộ phận cấp k
Giả sử tồn tại hàm g thỏa mãn:
g(a1, …, ak) ≤ min {f(x) | x ∈ D, xi = ai , i = 1, 푘}
Khi đó giá trị hàm g tại phương án bộ phận ≤ min của hàm
mục tiêu trên nhánh đó.
Hay g là hàm cận dưới, giá trị g(a1, …, ak) là cận dưới của
nhánh chứa phương án bộ phận (a1, …, ak)
TƯ TƯỞNG CỦA KỸ THUẬT NHÁNH CẬN
Giả sử đã có hàm g.
Trong quá trình thực hiện thuật toán quay lui, ta gọi:
푥 là phương án tốt nhất đã tìm được
푓 = 푓(푥) là kỷ lục
Nếu tại bước k, ta có phương án bộ phận (a1, …, ak) mà
g(a1, a2, …, ak) > 푓
=> tập con của D chứa các phương án mở rộng của (a1, …,
ak) sẽ không phải là kết quả tốt nhất => quay lui
KỸ THUẬT NHÁNH CẬN
Ta sửa thuật toán quay lui như sau:
procedure Try(k: integer);
begin
for (mọi giá trị có thể gán cho) do
if <chấp nhận ak> then
begin
xk := ak;
if k = n then <cập nhật kỷ lục>
else
if g(a1, a2, …, ak) ≤ 푓 then Try(k+1)
end;
end;
KỸ THUẬT NHÁNH CẬN
Để bắt đầu, ta sẽ đặt kỷ lục là giá trị rất lớn.
Thuật toán nhánh cận được thực hiện nhờ thủ tục:
procedure nhanh_can;
begin
푓 = +∞;
Try(1);
if 푓 < +∞ then 푓 là giá trị tối ưu, 푥 là phương án tối ưu>
else <bài toán không có kết quả>;
end;
VẤN ĐỀ
Xác định hàm g????
Tính giá trị của g phải đơn giản hơn việc tìm phương án
tối ưu trong nhánh
Kết quả của hàm g phải gần với kết quả tối ưu của nhánh
VÍ DỤ 1 – BÀI TOÁN XẾP BA LÔ 2
Ba lô cỡ b, đồ vật khối lượng: a1, …, an, giá trị c1, …, cn.
Xếp vào ba lô | giá trị max, số lượng mỗi loại tùy ý
Giả sử các đồ vật đã được xếp thứ tự theo “giá trị riêng” giảm dần:
c1/a1 ≥ c2/a2 ≥ … ≥ cn/an
Xét phương án bộ phận (x1, …, xk) (xi là số đồ vật thứ i)
Ký hiệu:
σ푘
Giá trị ba lô hiện tại: 휎푘 = 푖=1 푐푖푥푖
Khối lượng còn chứa được: bk = b – a1x1 - … - akxk
Cận trên cho phương án bộ phận (x1, …, xk) là:
푐푘+1
푔 푥1, … , 푥푘 = 휎푘 + 푏푘. ൗ
푎푘+1
VÍ DỤ 1
Giải bài toán xếp ba lô:
f(x) = 9x1 + 6x2 + 2 x3 + 3x4 → max
2x1 + 3x2 + x3 + 4x4 ≤ 5
xi ∈ Z
푘
휎푘 = 푐푖푥푖
푖=1
bk = b – a1x1 - … - akxk
푐푘+1푏푘
ൗ
푔 푥1, … , 푥푘 = 휎푘 +
푎푘+1
VÍ DỤ 1
Giải bài toán xếp ba lô:
f(x) = 9x1 + 6x2 + 2 x3 + 3x4 → max
2x1 + 3x2 + x3 + 4x4 ≤ 5
xi ∈ Z
푘
휎푘 = 푐푖푥푖
푖=1
bk = b – a1x1 - … - akxk
푐푘+1푏푘
ൗ
푔 푥1, … , 푥푘 = 휎푘 +
푎푘+1
Kết quả: 20 – (2, 0, 1, 0)
VÍ DỤ 2 – BÀI TOÁN NGƯỜI BÁN HÀNG
n địa điểm, chi phí từ i sang j là cij. Bắt đầu từ 1 điểm, đi một vòng
qua tất cả các điểm và quay về vị trí bắt đầu. Tìm đường | chi phí
min
Nhận xét:
Mỗi cách đi ~ 1 hoán vị từ 1 đến n.
Đi vòng tròn => cố định 1 địa điểm làm vị trí xuất phát (T1)
Kí hiệu:
Phương án bộ phận (u1, u2, …, uk) (u1 = 1)
cmin = min {cij, i, j = 1, …, n, i ≠ j}
σ푘−1
Chi phí cho hành trình bộ phận: 휎 =
푐푢 푢
푖 푖+1
푖=1
Hàm cận dưới cho phương án bộ phận:
푔 푢1, 푢2, … , 푢푘 = 휎 + 푛 − 푘 + 1 푐푚푖푛
Tải về để xem bản đầy đủ
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Bài toán tối ưu", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_bai_toan_toi_uu.pdf