Page 3
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
Contenu du document
Page 4
➢ 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. Nguyễn Đức Nghĩa 4
Page 5
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ö. Nguyễn Đức Nghĩa 5
Page 6
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. Nguyễn Đức Nghĩa 6
Page 7
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 7
Page 8
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á Nguyễn Đức NghĩanhÊt. 8
Page 9
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. Nguyễn Đức Nghĩa 9
Page 10
➢ Ta cã t¬ng øng 1-1 gi÷a một hμnh tr×nh T → T →... → T → T (1) (2) (n) (1) víi mét ho¸n vÞ = ((1), (2),..., (n)) cña n sè tù nhiªn 1, 2,..., n. §Æt f() = c +... + c + c (1), (2) (n-1), (n) (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. Nguyễn Đức Nghĩa 10
Page 11
➢ 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). Nguyễn Đức Nghĩa 11
Page 12
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 12
Page 13
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? Nguyễn Đức Nghĩa 13
Page 14
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 Nguyễn Đức Nghĩa 14
Page 15
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 }. Nguyễn Đức Nghĩa 15
Page 16
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 16
Page 17
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. Nguyễn Đức Nghĩa 17
Page 18
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. Nguyễn Đức Nghĩa 18
Page 19
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 x {0,1}, i j, =1, 2,..., .n Nguyễn Đức Nghĩa ij 19
Affichage des 19 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !