Chương 4

Nguyễn Đức Nghĩa

BÀI TOÁN TỐI ƯU TỔ HỢP

1


Nội dung

1. Phát biểu bài toán
 2. Duyệt toàn bộ
 3. Thuật toán nhánh cận
Nguyễn Đức Nghĩa



2


1. Phát biểu bài toán
1.1. Bài toán tổng quát
 1.2. Bài toán người du lịch
 1.3. Bài toán cái túi
 1.4. Bài toán đóng thùng
Nguyễn Đức Nghĩa



3

Dới

5


Cỏc thut ng

Nguyn c Ngha

f(x)

- hàm mục tiêu của bài toán,
x D - phơng án
D - tập các phơng án của bài toán.
Thông thờng tập D đợc mô tả nh là tập các
cấu hình tổ hợp thoả mãn một số tính chất
cho trớc nào đó.
Phơng án x* D đem lại giá trị nhỏ nhất
(lớn nhất) cho hàm mục tiêu đợc gọi là phơng án tối u, khi đó giá trị f* = f(x*) đợc gọi là giá trị tối u của bài toán.
6


1. Phát biểu bài toán
1.1. Bài toán tổng quát
 1.2. Bài toán người du lịch
 1.3. Bài toán cái túi
 1.4. Bài toán đóng thùng
Nguyễn Đức Nghĩa



số tự nhiên 1, 2,..., n.
Đặt
f() = c(1),(2) +... + c(n-1),(n) + c(n),(1).
Ký hiệu:
- tập tất cả các hoán vị của n số tự nhiên 1,
2,..., n.
9


 Khi

®ã bµi to¸n ngưêi du lÞch cã thÓ ph¸t
biÓu dưíi d¹ng bµi to¸n tèi ưu tæ hîp
sau:

Nguyễn Đức Nghĩa

min { f() :    }.
thể thấy rằng tổng số hành trình của người
du lịch là n!, trong đó chỉ có (n-1)! hành trình
thực sự khác nhau (bởi vì có thể xuất phát từ
một thành phố bất kỳ, nên có thể cố định một
thành phố nào đó là thành phố xuất phát).

 Có

10


1. Phát biểu bài toán

vật đem theo là lớn nhất?

12


Phỏt biu bi toỏn


Một phơng án đem đồ của nhà thám hiểm có thể
biểu diễn bởi vectơ nhị phân độ dài n: x = (x1, x2,...,
xn), trong đó xj = 1 nếu đồ vật thứ j đợc đem theo
và xj = 0 nếu trái lại.
Với phơng án x, giá trị đồ vật đem theo là
Nguyn c Ngha

n

f ( x) c j x j ,
j 1

tổng trọng lợng đồ vật đem theo là
n

g ( x) a j x j
j 1

13


Bi toỏn cỏi tỳi

n đồ vật với trọng lượng là w1, w2, ..., wn.
Cần tìm cách xếp các đồ vật này vào các cái
thùng có cùng dung lượng là b sao cho số
thùng cần sử dụng là nhỏ nhất có thể được.

Nguyễn Đức Nghĩa

 Có

16


Phỏt biu bi toỏn

Nguyn c Ngha

Ta

có thể giả thiết là
wi b, i = 1, 2,.., n.
Do đó số thùng cần sử dụng để chứa tất cả
các đồ vật là không quá n. Vấn đề là cần số
thùng ít nhất. Ta sẽ mở sẵn n cái thùng. Bài
toán đặt ra là hãy xác định xem mỗi một
trong số n đồ vật cần đợc xếp vào cái thùng
nào trong số n cái thùng đã mở để cho số
thùng chứa đồ là ít nhất.
17



i 1

ij

i ij

 b,

j  1, 2,..., n;

xij  {0,1}, i, j  1, 2,..., n.
18


Nguyễn Đức Nghĩa

2. DUYỆT TOÀN BỘ

19


NỘI DUNG

Nguyễn Đức Nghĩa

2.1. Mô tả phương pháp
2.2. Ví dụ áp dụng: Bài toán cái túi

20


Vớ d: Gii bi toỏn cỏi tỳi
Xét

bài toán cái túi:
n

m ax{ f ( x) c j x j : x D},
j 1

n

trong đó D {x ( x1 , x2 ,..., xn ) B n : w j x j b}
Nguyn c Ngha

j 1

cj ,

wj, b l cỏc s nguyờn dng, j=1,2,, n.

Cần
23

có thuật toán liệt kê các phần tử của D


Thuật toán quay lui
liệt kê các phương án chất đồ



procedure Nhapdl;
var i: integer;
begin
{Nhập vào n, c, w, b}
end;

25

procedure Inkq;
var j;
begin
{Phương án tối ưu: xopt;
Giá trị tối ưu: fopt }
end;