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: a₁, …, a_nvà

giá trị c₁, …, c_ntươ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: T₁, …, T_n.

 Đường đi: Xuất phát từ một địa điểm T_i, đ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 C_ijlà chi phí đi từ địa điểm T_iđến T_j.

 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ợ. C_ijlà 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á: a₁, …, a_m.

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 = (x₁, x₂, …, x_n) được gọi

là 1 phương án

 Yêu cầu: Tìm phương án X₀sao cho f(X₀) đạt cực đại

(cực tiểu) trên D.

Phương án X₀đượ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ử (x₁, …, x_n) trong

đó x_i= 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 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 = (x₁, …, x_n) ∈ A₁ …  A_n; x thỏa mãn t/c P}

 Một bộ (a₁, …, a_k) là phương án bộ phận cấp k

 Giả sử tồn tại hàm g thỏa mãn:

g(a₁, …, a_k) ≤ min {f(x) | x ∈ D, x_i= a_i, 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(a₁, …, a_k) là cận dưới của

nhánh chứa phương án bộ phận (a₁, …, a_k)

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 (a₁, …, a_k) mà

g(a₁, a₂, …, a_k) > 푓

=> tập con của D chứa các phương án mở rộng của (a₁, …,

a_k) 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 a_k> then

begin

x_k:= a_k;

if k = n then <cập nhật kỷ lục>

else

if g(a₁, a₂, …, a_k) ≤ 푓 then Try(k+1)

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: a₁, …, a_n, giá trị c₁, …, c_n.

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:

c₁/a₁≥ c₂/a₂≥ … ≥ c_n/a_n

 Xét phương án bộ phận (x₁, …, x_k) (x_ilà 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: b_k= b – a₁x₁- … - a_kx_k

 Cận trên cho phương án bộ phận (x₁, …, x_k) là:

푐_푘+1

푔 푥₁, … , 푥_푘= 휎_푘+ 푏_푘. ൗ

푎_푘+1

VÍ DỤ 1

 Giải bài toán xếp ba lô:

f(x) = 9x₁+ 6x₂+ 2 x₃+ 3x₄→ max

2x₁+ 3x₂+ x₃+ 4x₄≤ 5

x_i∈ Z

푘

휎_푘= ෍ 푐_푖푥_푖

푖=1

b_k= b – a₁x₁- … - a_kx_k

푐_푘+1푏_푘

ൗ

푔 푥₁, … , 푥_푘= 휎_푘+

푎_푘+1

VÍ DỤ 1

 Giải bài toán xếp ba lô:

f(x) = 9x₁+ 6x₂+ 2 x₃+ 3x₄→ max

2x₁+ 3x₂+ x₃+ 4x₄≤ 5

x_i∈ Z

푘

휎_푘= ෍ 푐_푖푥_푖

푖=1

b_k= b – a₁x₁- … - a_kx_k

푐_푘+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à c_ij. 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 (T₁)

 Kí hiệu:

 Phương án bộ phận (u₁, u₂, …, u_k) (u₁= 1)

 c_min= min {c_ij,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 푐_푚푖푛