Chương 1 Bài toán thuê xe du lịch có hạn ngạch 1. Quy hoạch nguyên Quy hoạch nguyên (Integer Programming) , viết tắt là IP, là bài toán quy hoạch mà trong đó tất cả hoặc một phần các biến bị ràng buộc chỉ lấy giá trị nguyên. Trường hợp thứ nhất được gọi là quy hoạch nguyên hoàn toàn (Pure Integer Pro- gramming – PIP), trường hợp thứ hai được gọi là quy hoạch nguyên bộ phận (Mixed Integer Programming – MIP) 1. Dạng tổng quát của bài toán Bài toán quy hoạch nguyên tổng quát được biểu diễn dưới dạng: f ( x ) = c T x → min(max ) với các điều kiện: Ax ≤ b x≥0 x ∈ Zn Bài toán quy hoạch nguyên được gọi là hoàn toàn khi tất cả các biến đều là số nguyên và được gọi là bộ phận khi một số biến không phải là số nguyên.
Bài toán quy hoạch nguyên 0-1 là bài toán khi các biến được giới hạn là 0 hoặc 1. Ứng dụng của bài toán Ứng dụng của bài toán được phát triển dựa vào các biến thể là bài toán quy hoạch nguyên hỗn hợp và bài toán quy hoạch nguyên 0-1. 8 Lập kế hoạch sản xuất Quy hoạch nguyên hỗn hợp có nhiều ứng dụng trong sản xuất công nghiệp, bao gồm mô hình hóa việc làm. Một ví dụ quan trọng xảy ra trong quy hoạch sản xuất nông nghiệp bao gồm xác định năng suất sản xuất cho một số loại cây trồng có thể chia sẻ tài nguyên (ví dụ như đất đai, lao động, vốn, hạt giống, phân bón.
Một mục tiêu có thể là tối đa hóa tổng sản lượng mà không vượt quá các nguồn lực sẵn có. Trong một số trường hợp, điều này có thể được biểu diễn dưới dạng một chương trình tuyến tính, nhưng các biến phải được hạn chế là số nguyên. Bài toán lập lịch Bài toán này liên quan đến dịch vụ và lập lịch trình xe trong mạng lưới vận tải. Ví dụ, bài toán liên quan đến việc chỉ định xe buýt hoặc tàu điện ngầm vào các tuyến đường riêng để có thể đáp ứng được thời gian biểu, và cũng để trang bị cho họ các trình điều khiển.
Ở đây các biến quyết định nhị phân cho biết xe buýt hoặc tàu điện ngầm được gán cho tuyến đường và liệu người lái xe có được chỉ định cho một chuyến tàu hoặc tàu điện ngầm hay không. Mạng viễn thông Mục tiêu của những bài toán này là thiết kế một mạng lưới các đường dây cài đặt để đáp ứng các yêu cầu truyền thông được xác định trước và tổng chi phí của mạng là tối thiểu. Điều này đòi hỏi tối ưu hóa cả topo của mạng cùng với việc thiết lập năng suất của các đường khác nhau. Trong nhiều trường hợp, năng suất bị hạn chế là số nguyên.
Thông thường, tùy thuộc vào công nghệ được sử dụng, các hạn chế bổ sung có thể được mô hình hóa như là một bất đẳng thức tuyến tính với các biến số nguyên hoặc nhị phân. Mạng di động Nhiệm vụ quy hoạch tần số trong mạng di động GSM bao gồm việc phân phối các tần số sẵn có trên các ăng ten để người dùng có thể được đáp ứng và sự kết hợp được giảm thiểu giữa các ăng-ten. Bài toán này có thể được xây dựng như là một chương trình tuyến tính số nguyên, trong đó các biến nhị phân cho biết tần số được gán cho một ăng-ten. Các phương pháp tiếp cận giải bài toán quy hoạch nguyên Sử dụng tổng số đơn modulo Nếu bài toán có dạng max (c T x ), Ax = b với A, b, c đều nguyên và A là tổng đơn modulo, khi đó tất cả các phương án đều là số nguyên.
Do đó, đáp án trả về bằng thuật toán đơn giản được đảm bảo là nguyên. Để chỉ ra tất các các đáp án đều là nguyên, đặt x là một lời giải của bài toán. Khi đó Ax = b, x0 = [ xn1 , xn2 , ., xn j ] là các phần tử tương ứng trong cột của x. Theo định nghĩa, có ma trận vuông con B của A sao cho Bx0 = b.
9 Vì các cột của B là độc lập tuyến tính và B là ma trận vuông, theo giả định B là đơn modulo và det( B) = ±1. Vì B là ma trận không suy biến, khả nghịch nên B adj x0 = B−1 b. Theo định nghĩa B−1 = det ( B) (B adj là ma trận liên hợp của B). Khi đó: B−1 = ± B adj là nguyên x0 = B−1 b là nguyên Tất cả các đáp án có thể đều nguyền Thuật toán chính xác Khi ma trận A không hoàn toàn unimodular, có một loạt các thuật toán có thể được sử dụng để giải bài toán quy hoạch nguyên chính xác.
Một lớp các thuật toán là các phương pháp cắt mặt phẳng bằng cách giải sự lũy biến của bài toán quy hoạch nguyên và sau đó thêm các ràng buộc tuyến tính đưa ra giải pháp theo hướng nguyên mà không loại bỏ bất kỳ điểm khả thi nào. Một lớp các thuật toán khác là các biến thể của nhánh cận và phương thức giới hạn biên. Ví dụ, phương pháp nhánh cận và cắt kết hợp phương pháp cắt và phương pháp nhánh cận. Một lợi thế là các thuật toán có thể được kết thúc sớm và miễn là có ít nhất một giải pháp tích hợp đã được tìm thấy khả thi, mặc dù không nhất thiết phải tối ưu, giải pháp có thể được trả lại.
Hơn nữa, các giải pháp của sự bài toán quy hoạch nguyên lũy biến có thể được sử dụng để ước tính trường hợp xấu nhất từ giải pháp tối ưu được trả lại. Cuối cùng, phương pháp nhánh cận và giới hạn biên có thể được sử dụng để trả về nhiều giải pháp tối ưu. Lenstra năm 1983 cho thấy rằng, khi số lượng các biến được cố định, bài toán quy hoạch nguyên có thể được giải quyết trong thời gian đa thức. Phương pháp Heuristic Vì bài toán quy hoach nguyên là bài toán NP, nên nhiều trường hợp khó giải quyết được và do đó phương pháp heuristic phải được sử dụng thay thế.
Ví dụ, tìm kiếm tabu có thể được sử dụng để tìm kiếm lời giải cho bài toán quy hoạch nguyên. Để sử dụng tìm kiếm tabu để giải quyết bài toán quy hoạch nguyên, các chuyển động có thể được định nghĩa là tăng hoặc giảm một số biến ràng buộc nguyên, trong khi tất cả các biến số nguyên ràng buộc khác không đổi. Các biến không bị ràng buộc sau đó được giải. Bộ nhớ ngắn hạn có thể bao gồm các giải pháp đã được thử nghiệm trước đó trong khi bộ nhớ trung hạn có thể bao gồm các giá trị cho các biến số nguyên bị ràng buộc.
Cuối cùng, bộ nhớ dài hạn có thể hướng dẫn tìm kiếm theo các giá trị số nguyên mà chưa từng được thử. Một số phương pháp heuristic khác: Hill climbing Simulated annealing Reactive search optimization Ant colony optimization 10 Hopfield neural networks Ngoài ra còn có một loạt các phương pháp heuristic khác đối với các bài toán đặc biệt, chẳng hạn như phương pháp k-opt cho bài toán người chào hàng. Bài toán người chào hàng(Traveling Salesman Prob- lem - TSP) Bài toán người bán hàng là một trong những bài toán điển hình của tối ưu tổ hợp được định nghĩa trong thế kỉ 19 bởi nhà toán học Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman. Trò chơi Icosa của Hamilton là một trò chơi giải trí dựa trên việc tìm kiếm chu trình Hamilton.
Bài toán được phát biểu như sau: Có một người giao hàng cần đi giao hàng tại n thành phố(hoặc điểm tiêu thụ) C = {c1 , c2 , ., cn } độ dài đường đi trực tiếp từ ci đến c j là dij. Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu, mỗi thành phố chỉ đến một lần. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. Dưới dạng đồ thị bài toán được mô hình hóa như một đồ thị vô hướng có trọng số.
Đây chính là bài toán tìm chu trình Hamilton với đồ thị đầy đủ có trọng số G = (V, E), với V là tập các đỉnh với nhãn là các thành phố trong C, E là tập các cạnh nối các thành phố tương ứng, độ dài mỗi cạnh chính là độ dài đường đi giữa hai thành phố tương ứng. Trong trường hợp này, tập S sẽ là tập các chu trình Hamilton trên G, f là độ dài của chu trình, Ω là ràng buộc đòi hỏi chu trình là chu trình Hamilton (qua tất cả các đỉnh, mỗi đỉnh đúng một lần), C là tập thành phố được xét, C0 trùng với C, tập X là vectơ độ dài n: x = { x1 , x2 , ., xn } vớixi ∈ C ∀i ≤ n, còn X ∗ là các vectơ trong đó xi khác x j đối với mọi cặp (i, j). Do đó, lời giải tối ưu của bài toán TSP là một hoán vị π của tập đỉnh c1 , c2 , ., cn sao cho hàm độ dài f (π ) là nhỏ nhất, trong đó f (π ) được tính theo công thức sau: n −1 f (π ) = ∑ (d(π (i ), π (i + 1))) + d(π (n), π (1)) i =1 Trong bài toán TSP đối xứng, khoảng cách giữa hai thành phố là không đổi dù đi theo chiều nào. Như vậy đồ thị trong bài toán này là đồ thị vô hướng.
Việc đối xứng này làm giảm đi một nửa số lời giải có thể. Trong khi đó, với bài toán TSP bất đối xứng thì đường đi giữa hai thành phố có thể chỉ một chiều hoặc có độ dài khác nhau giữa mỗi chiều, tạo nên đồ thị có hướng. TSP là một trong những bài toán được nghiên cứu sâu nhất trong tối ưu hóa. Nó thường được dùng làm thước đo cho nhiều phương pháp tối ưu hóa.
Mặc dù bài toán rất khó giải trong trường hợp 11 tổng quát, có nhiều phương pháp giải chính xác cũng như heuristic đã được tìm ra để giải quyết một số trường hợp có tới hàng chục nghìn thành phố. Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch. Trong lý thuyết độ phức tạp tính toán, phiên bản quyết định của TSP (cho trước độ dài L, xác định xem có tồn tại hay không một chu trình đi qua mỗi đỉnh đúng một lần và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ. Do đó, có nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào cho TSP đều tăng theo cấp số nhân với số thành phố.