- 1 Bài toán quy hoạch song tuyến tính 5. - 1.2 Bài toán quy hoạch lõm với ràng buộc tuyến tính. - 1.2.2 Bài toán quy hoạch lõm. - 1.3 Bài toán quy hoạch song tuyến tính. - 1.3.1 Phát biểu bài toán. - 1.3.2 Quan hệ với bài toán quy hoạch lõm. - 1.3.3 Tính chất nghiệm của bài toán song tuyến tính. - 2.1.1 Biến đổi bài toán quy hoạch song tuyến tính. - Bài toán cực tiểu một hàm song tuyến tính với các ràng buộc tuyến tính đối với các biến x và biến y được gọi là một quy hoạch song tuyến tính (bilinear programming problem). - Như vậy, có thể xem quy hoạch song tuyến tính là một bài toán quy hoạch toàn phương đặc biệt.. - Đáng chú ý là bài toán quy hoạch lõm, tuyến tính từng khúc và các bài toán luồng trên mạng với phụ phí cố định (rất quen thuộc trong quản lý các chuỗi cung ứng) cũng có thể giải nhờ dùng cách diễn đạt song tuyến tính (xem [4]).. - Luận văn xét bài toán quy hoạch song tuyến tính, ký hiệu là (BP):. - Tiếp đó, giới thiệu bài toán quy hoạch song tuyến tính, tính chất nghiệm của bài toán và mối liên hệ với bài toán cực tiểu hàm lõm, tuyến tính từng khúc. - tìm nghiệm cực tiểu địa phương của bài toán quy hoạch song tuyến tính và đưa ra ví dụ minh họa thuật. - Chương 2: Thuật toán giải bài toán quy hoạch song tuyến tính trình bày thuật toán được nêu ở tài liệu tham khảo [3] để giải bài toán quy hoạch song tuyến tính. - Bài toán quy hoạch song tuyến tính. - Chương này nhắc lại các kết quả về đối ngẫu trong quy hoạch tuyến tính, bài toán quy hoạch lõm ràng buộc tuyến tính. - Tiếp đó đề cập tới bài toán quy hoạch song tuyến tính, tính chất nghiệm bài toán và mối liên hệ với bài toán cực tiểu hàm lõm, tuyến tính từng khúc. - Cuối chương nêu thuật toán tìm cực tiểu địa phương của bài toán. - Trong quy hoạch tuyến tính người ta hay xét hai dạng bài toán sau đây.. - Trong bài toán này tập ràng buộc D = {x ∈ R n : Ax >. - Trong bài toán này tập ràng buộc D = {x ∈ R n : Ax = b, x >. - Trong các bài toán trên f(x) được gọi là hàm mục tiêu. - Một phương án đạt cực tiểu của hàm mục tiêu f(x) gọi là một phương án tối ưu hay một nghiệm tối ưu của bài toán. - Sau đây là hai dạng cặp bài toán đối ngẫu thường gặp.. - là bài toán qui hoạch tuyến tính (bài toán đối ngẫu):. - 0 là bài toán qui hoạch tuyến tính (bài toán đối ngẫu):. - Vì thế ta gọi (P) và (Q) là cặp bài toán qui hoạch tuyến tính đối ngẫu nhau.. - Các kết quả sau đúng cho cặp bài toán đối ngẫu (P), (Q) dạng bất kỳ.. - Nếu x là một lời giải chấp nhận được của bài toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì f (x. - (a) Cả hai bài toán đều không có nghiệm chấp nhận được.. - (b) Cả hai bài toán đều có nghiệm chấp nhận được. - Khi đó, bài toán có nghiệm chấp nhận được sẽ có giá trị tối ưu vô cực. - tùy theo bài toán max hay min).. - Quan hệ giữa cặp bài toán đối ngẫu nhau còn thẻ hiện ở định lý sau đây.. - (Cực tiểu hàm lõm hay cực đại hàm lồi) Xét bài toán tối ưu có dạng:. - Khi đó bài toán được gọi là một quy hoạch lõm với ràng buộc tuyến tính.. - Quy hoạch tuyến tính và quy hoạch lồi thuộc lớp bài toán một cực trị ( hàm mục tiêu của bài toán có nhiều nhất một giá trị cực tiểu. - Bài toán quy hoạch lõm thuộc lớp bài toán như thế.. - Mục tiếp sau sẽ chỉ ra rằng bài toán quy hoạch song tuyến tính có thể phát biểu như một bài toán quy hoạch lõm với hàm mục tiêu lõm, tuyến tính từng khúc và với các ràng buộc tuyến tính.. - Ta gọi bài toán tối ưu với hàm mục tiêu song tuyến tính và các hàm ràng buộc song tuyến tính là bài toán song tuyến tính (bilinear problem) và các bài toán này có thể xem như một lớp con của quy hoạch toàn phương (quadratic programming).. - Quy hoạch song tuyến tính có nhiều ứng dụng đa dạng trong các trò chơi ma trận có ràng buộc, bài toán bù và bài toán phân việc 3 - chiều, Markovian.. - Nhiều bài toán nguyên 0 - 1 có thể phát biểu như các bài toán song tuyến tính.. - Trong luận văn chúng tôi xét bài toán song tuyến tính sau đây, ký hiệu bài toán là BP:. - Trong đó min y∈Y f (x, y) là bài toán tuyến tính. - Bởi vì nghiệm của bài toán tuyến tính đạt tại đỉnh của miền chấp nhận được nên:. - Sử dụng ký hiệu này, bài toán BP có thể phát biểu lại thành:. - Từ nhận xét này cho thấy BP tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc với ràng buộc tuyến tính.. - Ngược lại, có thể chỉ ra rằng bất kì bài toán cực tiểu hàm mục tiêu lõm, tách biến và tuyến tính từng khúc có thể quy được về bài toán quy hoạch song tuyến tính. - Để thiết lập mối quan hệ này, ta xét bài toán tối ưu dưới đây:. - (3) Lập bài toán quy hoạch song tuyến tính sau đây:. - là một nghiệm tói ưu của bài toán (4) thì x ∗ là một nghiệm tối ưu của bài toán (2) Chú ý là không đòi hỏi X là một đa diện lồi. - Nếu X là một đa diện lồi thì cấu trúc của bài toán (4) là tương đương với (BP).. - Hơn nữa, ta có thể chỉ ra rằng có thể đưa bất kì bài toán cực tiểu hàm lõm toàn phương về bài toán quy hoạch song tuyến tính. - Nói riêng, xét bài toán tối ưu sau đây. - Ta xây dựng bài toán quy hoạch song tuyến tính như sau:. - Nếu x ∗ là một nghiệm của bài toán (5) thì (x. - là một nghiệm của bài toán (6). - Mục trước cho thấy rằng BP tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc. - Bài toán BP trở thành bài toán tuyến tính và y ∗ là một nghiệm của bài toán nhận được. - là một nghiệm của bài toán BP, thì. - Cụ thể y ∗ là một nghiệm tối ưu nhất của bài toán min x∈X f (x, y. - thỏa mãn điều kiện (7) và y ∗ là nghiệm duy nhất của bài toán min y∈Y f (x. - Nhớ rằng BP tương đương với bài toán cực tiểu hàm lõm, tuyến tính từng khúc. - Mục này đề cập tới phương pháp tìm một nghiệm của bài toán song tuyến tính. - Do BP tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc, nên có thể dùng bất kỳ thuật toán giải bài toán sau để giải bài toán trước. - Nói riêng, ta có thể dùng thuật toán siêu phẳng cắt đã đề xuất cho hai bài toán đó. - là một nghiệm ε tối ưu toàn cục của bài toán. - thì ta có thể thay X bởi tập X 1 , nghĩa là xét bài toán tối ưu. - Bằng cách đổi mới cả hai tập, nghĩa là xét bài toán tối ưu. - thuật toán siêu phẳng cắt (xem Thuật toán 2) có thể cho phép tìm nghiệm toàn cục của bài toán với số lần lặp ít hơn.. - Chương này trình bày thuật toán được nêu ra ở tài liệu tham khảo [3], để giải bài toán quy hoạch song tuyến tính. - Ta xét bài toán quy hoạch song tuyến tính: tìm véctơ n - chiều x và véctơ n 0 - chiều y sao cho:. - Theo Định lý 1.3.4, tập tất cả các nghiệm tối ưu của bài toán (2.1) chứa ít nhất một phần tử (x. - Bài toán (2.1) có thể viết lại thành:. - Từ lý thuyết đối ngẫu của quy hoạch tuyến tính trực tiếp suy ra rằng (2.1) tương đương với bài toán tìm véctơ n chiều x và véctơ m 0 chiều u sao cho:. - Sau đây thay cho bài toán (2.1), ta giải trực tiếp bài toán (2.2). - Sau đó, ở mục 2.2 sẽ trình bày thuật toán tìm nghiệm tối ưu của bài toán (2.2) và xét sự hội tụ của thuật toán. - Bài toán (2.2) bây giờ có thể viết lại thành:. - Hàm mục tiêu của bài toán (2.3) là tuyến tính, nhưng tập ràng buộc của bài toán nói chung là một tập không lồi. - Hơn nữa, tập nghiệm tối ưu của bài toán có thể không liên thông. - x 1 , y 1 , x 2 , y 2 là tập nghiệm tối ưu của bài toán.. - Λ , với z = c T x + b T u , (x , u )là một nghiệm tối ưu của bài toán (1.1) khi và chỉ khi với mỗi x ∈ X có tồn tại u sao cho:. - Mục này trình bày thuật toán giải bài toán (2.2). - n, ta giải một bài toán tuyến tính:. - n, cần giải một bài toán tuyến tính. - v i n bài toán tuyến tính ở Bước 3 có thể diễn đạt lại như sau:. - 1 , trong đó π là nghiệm của bài toán sau:. - Xét bài toán quy hoạch song tuyến tính [2, 0]. - Phát biểu đối ngẫu của bài toán này là. - trong đó y ∗ là nghiệm đối ngẫu tối ưu của bài toán thứ ba được giải ở Bước 0.. - Mục này giải lại bài toán (LP 1 ) theo thuật toán siêu phẳng cắt.. - Nghiệm tối ưu của bài toán quy hoạch song tuyến tính là:. - Chương này giới thiệu thuật toán nêu ở [3] tìm nghiệm của bài toán quy hoạch song tuyến tính với miền ràng buộc rời nhau và với giả thiết các tập ràng buộc X, Y bị chặn. - Thuật toán hội tụ về nghiệm đúng của bài toán quy hoạch song tuyến tính ban đầu và được minh họa bằng ví dụ số cụ thể.. - Luận văn đề cập tới bài toán quy hoạch song tuyến tính, một dạng đặc biệt của quy hoạch toàn phương. - Nói chung, quy hoạch song tuyến tính là một bài toán tối ưu không lồi, không lõm và thuộc lớp bài toán tối ưu toàn cục, rất khó giải. - tìm nghiệm cực tiểu địa phương của bài toán quy hoạch song tuyến tính khi miền ràng buộc bị chặn.. - Cách đưa bài toán quy hoạch song tuyến tính về bài toán tối ưu tương đương trên một tập không lồi. - Từ đó có thể tìm nghiệm đúng của bài toán quy hoạch song tuyến tính với miền ràng buộc tách biến và với giả thiết miền ràng buộc bị chặn, theo thuật toán dựa trên điều kiện tối ưu của nghiệm bài toán.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt