›
›

Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 4: Bài toán tối ưu tổ hợp - Nguyễn Đức Nghĩa

Download
Chương 4  
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  
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  
3
➢ Trong rất nhiều vấn đề ứng dụng thực tế của  
tổ hợp, các cấu hình tổ hợp được gán cho  
một giá trị bằng số đánh giá giá trị sử dụng  
của cấu hình đối với mục đích sử dụng cụ  
thể nào đó. Khi đó xuất hiện bài toán: Hãy  
lựa chọn trong số các cấu hình tổ hợp chấp  
nhận được cấu hình có giá trị sử dụng tốt  
nhất. Các bài toán như vậy chúng ta sẽ gọi là  
bài toán tối ưu tổ hợp.  
4
Phát biểu bài toán  
➢ Díi d¹ng tæng qu¸t bµi to¸n tèi u tæ hîp cã  
thÓ ph¸t biÓu nh sau:  
T×m cùc tiÓu (hay cùc ®¹i) cña phiÕm hµm  
f(x) → min (max),  
víi ®iÒu kiÖn  
x D,  
trong ®ã D lµ tËp h÷u h¹n phÇn tö.  
5
Các thuật ngữ  
➢ 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  
7
Bµi to¸n ngêi du lÞch  
(Traveling Salesman Problem – TSP)  
➢ Mét ngêi du lÞch muèn ®i tham quan n thµnh  
phè T1, T2, ..., Tn.  
➢ Hành trình là cách đi xuÊt ph¸t tõ mét thµnh  
phè nµo ®ã ®i qua tÊt c¶ c¸c thµnh phè cßn  
l¹i, mçi thµnh phè ®óng mét lÇn, råi quay trë  
l¹i thµnh phè xuÊt ph¸t.  
➢ BiÕt cij lµ chi phÝ ®i tõ thµnh phè Ti ®Õn thµnh  
phè Tj (i, j = 1, 2,..., n),  
➢ T×m hµnh tr×nh víi tæng chi phÝ lµ nhá nhÊt.  
8
Sơ lược về lịch sử  
➢ The origins of the TSP are obscure. In the 1920's, the  
mathematician and economist Karl Menger publicized it  
among his colleagues in Vienna.  
➢ In the 1930's, the problem reappeared in the mathematical  
circles of Princeton.  
➢ In the 1940's, it was studied by statisticians (Mahalanobis  
(1940), Jessen (1942), Gosh (1948), Marks (1948)) in  
connection with an agricultural application and the  
mathematician Merill Flood popularized it among his  
colleagues at the RAND Corporation. Eventually, the  
TSP gained notoriety as the prototype of a hard problem  
in combinatorial optimization: examining the tours one by  
one is out of the question because of their large number,  
and no other idea was on the horizon for a long time.  
➢ New history with George Dantzig, Ray Fulkerson, and  
Selmer Johnson's 1954 breakthrough.  
9
➢ Ta cã t¬ng øng 1-1 gi÷a một hµnh tr×nh  
T(1) → T(2) →... → T(n) → T(1)  
víi mét ho¸n vÞ = ((1), (2),..., (n)) cña n  
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.  
10  
➢ 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:  
min { f() :   }.  
➢ Có 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).  
11  
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  
12  
Bài toán cái túi  
(Knapsack Problem)  
➢ Một nhà thám hiểm cần đem theo một cái túi  
có trọng lượng không quá b.  
➢ Có n đồ vật có thể đem theo. Đồ vật thứ j có  
▪ trọng lượng là aj và  
▪ giá trị sử dụng là cj (j = 1, 2,..., n).  
➢ Hỏi rằng nhà thám hiểm cần đem theo các đồ  
vật nào để cho tổng giá trị sử dụng của các đồ  
vật đem theo là lớn nhất?  
13  
Phát biểu bài 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µ  
n
f (x) = c x ,  
j j  
j=1  
tæng träng lîng ®å vËt ®em theo lµ  
n
g(x) = a x  
j j  
j=1  
14  
Bài toán cái túi  
➢ Bµi to¸n c¸i tói cã thÓ ph¸t biÓu díi d¹ng bµi  
to¸n tèi u tæ hîp sau:  
Trong sè c¸c vect¬ nhÞ ph©n ®é dµi n tho¶  
m·n ®iÒu kiÖn g(x) b, h·y t×m vect¬ x* cho  
gi¸ trÞ lín nhÊt cña hµm môc tiªu f(x):  
max { f(x): xBn, g(x) b }.  
15  
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  
16  
Bµi to n ng th ng  
(Bin Packing)  
➢ Có 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.  
17  
Phát biểu bài toán  
➢ 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.  
18  
Bài toán đóng thùng  
➢ Đưa vào biến Bun  
xij = 1, nếu đồ vật i được xếp vào thùng j,  
0, nếu trái lại.  
Khi đó bài toán đóng thùng có thể phát biểu dưới dạng:  
n
n
sign( x ) → min,  
   
ij  
j=1  
i=1  
n
x =1, i =1,2,...,n  
ij  
j=1  
n
w x b, j =1,2,...,n;  
i ij  
i=1  
xij {0,1}, i, j =1,2,...,n.  
19  
2. DUYỆT TOÀN BỘ  
20  
Tải về để xem bản đầy đủ
ppt 93 trang Thùy Anh 26360 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 4: Bài toán tối ưu tổ hợp - Nguyễn Đức Nghĩa", để 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:

  • pptbai_giang_toan_roi_rac_phan_1_ly_thuyet_to_hop_chuong_4_bai.ppt