CHƯƠNG 1 CƠ SỞ LÝ THUYẾT Chương này trình bày các kiến thức tổng quan về bài toán tối ưu tổ hợp và phân loại lớp các bài toán tối ưu tổ hợp; trình bày tổng quan về mạng xã hội (MXH), các mô hình phát tán thông tin thường được sử dụng để giải quyết các bài toán về lan truyền thông tin. Bài toán tối ưu tổ hợp Tối ưu hóa tổ hợp (TUTH) là một trường con của tối ưu hóa toán học có liên quan đến nghiên cứu hoạt động, lý thuyết thuật toán và lý thuyết độ phức tạp tính toán. Nó có các ứng dụng quan trọng trong một số lĩnh vực, bao gồm trí tuệ nhân tạo, máy học, lý thuyết đánh giá, kỹ thuật phần mềm, toán học ứng dụng và khoa học máy tính lý thuyết TUTH là một chủ đề bao gồm việc tìm kiếm một đối tượng tối ưu từ một tập hợp hữu hạn các đối tượng. Trong nhiều vấn đề như vậy, tìm kiếm toàn diện là không thể tìm được.
Nó hoạt động trên phạm vi của những vấn đề tối ưu hóa, trong đó tập hợp các giải pháp khả thi là rời rạc hoặc có thể được rút gọn thành rời rạc, và trong đó mục tiêu là tìm ra giải pháp tốt nhất. Các bài toán điển hình là bài toán người bán hàng lưu động (travelling salesman problem "(TSP)), bài toán cây bao trùm tối thiểu (minimum spanning tree problem (MST)) và bài toán cái túi. [8] Một cách tổng quát, mỗi bài toán TUTH có thể phát biểu như sau: Cho một bộ ba (𝑆𝑆, 𝑓𝑓, Ω), trong đó S là tập hữu hạn trạng thái (lời giải tiềm năng hay phương án), f là hàm mục tiêu xác định trên S, còn Ω là tập các ràng buộc. Mỗi phương án s ∈ S thỏa mãn các ràng buộc Ω gọi là phương án (hay lời giải) chấp nhận được.
Mục đích của ta là tìm phương án chấp nhận được s∗ tối ưu hóa toàn cục hàm mục tiêu f. Chẳng hạn với bài toán cực tiểu thì f(s∗) ≤ f(s) với mọi phương án chấp nhận được s. 4 Trong thực tế đời sống và trong các hệ thống thông tin, ta thường gặp nhiều bài toán tối ưu quan trọng có dạng như một số bài toán tối ưu kinh điển như sau: Bài toán Người bán hàng (TSP): cho vị trí của N thành phố khác nhau, hãy tìm con đường ngắn nhất có thể để đến thăm mỗi thành phố đúng một lần. Thùng - Đóng gói: cho một bộ N đối tượng, mỗi đối tượng có một kích thước si xác định, tìm cách xếp chúng vào càng ít thùng (mỗi thùng cỡ B) càng tốt.
Lập lịch trình thực hiện công việc: đưa ra một tập hợp các công việc phải thực hiện và một bộ công cụ hạn chế mà các công việc này có thể được thực hiện, tìm lịch trình cho những công việc nên được thực hiện khi nào và bằng những công cụ nào giúp giảm thiểu tổng thời gian cho đến khi tất cả các công việc đã được hoàn thành. Boolean Satisfiability: tìm cách gán giá trị cho một tập hợp các biến boolean để thỏa mãn một biểu thức boolean đã cho. (Một hàm mục tiêu phù hợp có thể là số mệnh đề thỏa mãn nếu biểu thức có dạng CNF) Việc giải các bài toán tối ưu tổ hợp được thực hiện thông qua việc tìm kiếm tập các phương án, tuy nhiên không gian của các phương án khả thi thường quá lớn dẫn đến sư bùng nổ tổ hợp, vì vậy rất khó để tìm kiếm một cách toàn diện bằng các thuật toán tối ưu thuần túy. Trong một số trường hợp, các vấn đề có thể được giải quyết chính xác bằng cách sử dụng kỹ thuật nhánh cận.
Tuy nhiên, trong các trường hợp khác, không có thuật toán chính xác nào khả thi và thường phải sử dụng các thuật toán Heuristic. Do vậy các phương pháp giải gần đúng thường dược các nhà nghiên cứu áp dụng để giải các bài toán loại này. Phân loại các bài toán tối ưu tổ hợp Một trong những phương pháp hiển nhiên nhất để giải bài toán tối ưu là phương pháp vét cạn: Tính giá trị hàm mục tiêu f(x) trên tất cả các phương án, sau đó so sánh các giá trị tính được để tìm ra giá trị tối ưu và phương án tối ưu của bài toán. Thực hiện theo phương pháp trên gặp rất nhiều khó khăn ngay cả 5 khi kích thước của bài toán (số biến n và số ràng buộc m) là không lớn, bởi vì tập D thông thường gồm một số rất lớn các phần tử, trong nhiều trường hợp còn là không đếm được.
Vì vậy, người ta đã nghiên cứu về mặt lý thuyết để có thể tách ra từ bài toán tổng quát thành các lớp bài toán dễ giải. Các nghiên cứu lý thuyết đó thường là: - Nghiên cứu các tính chất của các thành phần bài toán (hàm mục tiêu, các hàm ràng buộc, các biến số, các hệ số .); - Các điều kiện tồn tại lời giải chấp nhận được; Các điều kiện cần và đủ của cực trị; - Tính chất của các đối tượng nghiên cứu. Dựa vào tính chất của các thành phần bài toán và đối tượng nghiên cứu để người ta phân loại các bài toán tối ưu (hay bài toán quy hoạch) như sau: 1. Quy hoạch tuyến tính Quy hoạch tuyến tính (QHTT, còn được gọi là tối ưu hóa tuyến tính) là một phương pháp để đạt được kết quả tốt nhất (chẳng hạn như lợi nhuận tối đa hoặc chi phí thấp nhất) trong một mô hình toán học mà các đối tượng của nó được biểu diễn bằng các mối quan hệ tuyến tính.
Qui hoạch tuyến tính là một trường hợp đặc biệt của qui hoạch toán học (hay còn gọi là tối ưu hóa toán học). QHTT là một kỹ thuật để tối ưu hóa hàm mục tiêu tuyến tính, tuân theo các ràng buộc về bình đẳng tuyến tính và bất bình đẳng tuyến tính. Vùng khả thi của nó là một đa giác lồi, là một tập được định nghĩa là giao của nhiều nửa không gian, mỗi nửa không gian được xác định bởi một bất đẳng thức tuyến tính. Hàm mục tiêu của nó là một hàm affine (tuyến tính) có giá trị thực được xác định trên khối đa diện này.
Giải bài toán qui hoạch tuyến tính là tìm một điểm trong đa giác mà hàm này có giá trị nhỏ nhất (hoặc lớn nhất) nếu một điểm như vậy tồn tại. )𝑇 là ma trận chuyển vị. Biểu thức có giá trị cực đại hoặc cực tiểu được gọi là hàm mục tiêu (trong trường hợp này là 𝑓𝑓(𝑥) = 𝑐 𝑇 𝑥). Các bất đẳng thức 𝑔(𝑥) = 𝐴𝑥 ≤ 𝑏 và 𝑥 ≥ 0 là các ràng buộc xác định một đa giác lồi mà trên đó hàm mục tiêu được tối ưu hóa.
Trong bối cảnh này, hai vectơ có thể so sánh được khi chúng có cùng kích thước. Nếu hàm mục tiêu 𝑓𝑓(𝑥) và tất cả các hàm ràng buộc 𝑔(𝑥), 𝑖 = 1, m là tuyến tính thì bài toán là QHTT. Quy hoạch tham số Quy hoạch tham số (QHTS) là một kiểu tối ưu hóa toán học, trong đó vấn đề tối ưu hóa được biểu diễn dưới dạng một hàm của một hoặc nhiều tham số. Đã có những phát triển đáng kể đối với các trường hợp nhiều tham số, sự hiện diện của các biến nguyên cũng như phi tuyến tính.
Đặc biệt, mối liên hệ giữa qui hoạch tham số và điều khiển dự đoán mô hình được thiết lập vào năm 2000 đã góp phần làm tăng sự quan tâm đến chủ đề này. 𝜃 ∈ Θ ⊂ ℝ𝑚 Trong đó 𝑥 là biến tối ưu hoá, 𝜃 là các tham số, 𝑓𝑓(𝑥, 𝜃) là hàm mục tiêu, 𝑔(𝑥, 𝜃) là biểu thị những ràng buộc, Tập hợp Θ thường được gọi là không gian tham số. Các hệ số trong biểu thức của hàm mục tiêu và của các ràng buộc phụ thuộc vào tham số; 7 Tùy thuộc vào bản chất của 𝑓𝑓(𝑥, 𝜃) và 𝑔(𝑥, 𝜃) và liệu bài toán tối ưu hóa có các biến số nguyên hay không, các bài toán quy hoạch tham số được phân thành các lớp con khác nhau: - Nếu có nhiều hơn một tham số, tức là 𝑚 > 1, thì nó thường được gọi là bài toán quy hoạch đa tham số. - Nếu các biến số nguyên có mặt, thì bài toán được gọi là bài toán qui hoạch hỗn hợp số nguyên (đa) tham số.
- Nếu các ràng buộc là affine, thì việc phân loại tùy thuộc vào bản chất của hàm mục tiêu trong các bài toán qui hoạch tuyến tính, bậc hai và phi tuyến tính (đa) tham số (hỗn hợp-nguyên). Lưu ý rằng điều này thường giả định rằng các ràng buộc là affine. Quy hoạch phi tuyến Quy hoạch phi tuyến (QHPT) là quá trình giải quyết một vấn đề tối ưu hóa trong đó một số ràng buộc hoặc hàm mục tiêu là phi tuyến. Bài toán tối ưu hóa là tìm điểm cực trị (cực đại, cực tiểu hoặc điểm dừng) của một hàm mục tiêu trên một tập các biến thực chưa biết và có điều kiện để thỏa mãn một hệ phương trình và bất phương trình, được gọi chung là các ràng buộc.
Đây là lĩnh vực con của tối ưu hóa toán học giải quyết các vấn đề không tuyến tính. Cho 𝑛, 𝑚 và 𝑝 là các số nguyên dương. Gọi 𝑋 là tập con của 𝑅𝑛 , đặt 𝑓𝑓, 𝑔𝑖 và ℎ𝑗 là các hàm có giá trị thực trên 𝑋 với mỗi 𝑖 thuộc {1, … , 𝑚} và mỗi 𝑗 thuộc {1, … , 𝑝}, với ít nhất một trong số 𝑓𝑓, 𝑔𝑖 và ℎ𝑗 là phi tuyến tính. Bài toán tối thiểu hóa phi tuyến là bài toán tối ưu hóa dạng: Tối thiểu 𝑓𝑓(𝑥) Ràng buộc 𝑔𝑖 (𝑥) ≤ 0 với mọi 𝑖 ∈ {1, … , 𝑚} ℎ𝑗 (𝑥) = 0 với mọi 𝑗 ∈ {1, … , 𝑝} 𝑥∈𝑋 Một bài toán tối đa hóa phi tuyến được định nghĩa theo cách tương tự.
Quy hoạch rời rạc Trong các bài toán quy hoạch tuyến tính, các biến số có thể nhận những giá trị thực không âm. Tuy nhiên, trong thực tiễn thường gặp các bài toán mà các biến số chỉ có thể nhận một số hữu hạn hay đếm được giá trị, thường là các giá trị nguyên. Chẳng hạn sẽ là vô nghĩa khi đưa ra câu trả lời: cần sản xuất nửa cái bàn hay cần thuê 2,7 cái ô tô để vận chuyển hàng hoá…Trong một số bài toán, chẳng hạn bài toán vận tải với các lượng hàng cung và cầu là các số nguyên, song nhiều bài toán khác thì không phải như vậy. Vì thế trong chương này sẽ đề cập đến nội dung và phương pháp giải các bài toán tối ưu trên lưới các điểm nguyên hay trên các tập rời rạc, gọi tắt là bài toán quy hoạch rời rạc hay bài toán quy hoạch nguyên.