Chương 4 trình bày những kiên thức cơ bản liên qua đến bài toán tối ưu tổ hợp như: Phát biểu bài toán, duyệt toàn bộ, thuật toán nhánh cận. . | Chương 4 BÀI TOÁN TỐI ƯU TỔ HỢP 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 1. Phát biểu bài toán . Bài toán tổng quát . Bài toán người du lịch . Bài toán cái túi . Bài toán đóng thùng 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. 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ö. 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. 1. Phát biểu bài toán . Bài toán tổng quát . Bài toán người du lịch . Bài toán cái túi . Bài toán đóng thùng 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. Sơ lược về lịch sử The origins of the TSP are obscure. In the 1920s, the mathematician and economist Karl Menger publicized it among his colleagues in Vienna. In the 1930s, the problem reappeared in the mathematical circles of Princeton. In the 1940s, it was studied by . | Chương 4 BÀI TOÁN TỐI ƯU TỔ HỢP 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 1. Phát biểu bài toán . Bài toán tổng quát . Bài toán người du lịch . Bài toán cái túi . Bài toán đóng thùng 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. 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ö. 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
