Tài liệu Lý thuyết đối ngẫu

ĐỀ TÀI: Lý thuyết đối ngẫu
Chương II LÝ THUYẾT ĐỐI NGẪU §1. BÀI TOÁN ĐỐI NGẪU VÀ MỘT SỐ TÍNH CHẤT 1. Định nghĩa bài toán đối ngẫu: Cho bài toán Quy hoạch tuyến tính, ta gọi là bài toán (P)
Bài toán sau đây được gọi là bài toán đối ngẫu của bài toán (P), ta gọi là bài toán (Q)
Trong đó các cặp ràng buộc
,
, ,
được gọi là các ràng buộc đối ngẫu với nhau. Ví dụ: Cho bài toán Quy hoạch tuyến tính (P)
Ta sẽ viết bài toán đối ngẫu của bài toán (P). Trước tiên ta sẽ chỉ rõ các véctơ c, b và ma trận A cũng như các tập chỉ số:

Bài toán đối ngẫu sẽ là:
Giải thích:
do ràng buộc (1), (2) của bài toán gốc.
do ràng buộc (3) của bài toán gốc.
do ràng buộc (4) của bài toán gốc. Ràng buộc
của bài toán đối ngẫu do điều kiện (5) là
của bài toán gốc.Ràng buộc
của bài toán đối ngẫu do điều kiện (6) là
của bài toán gốc.Ràng buộc
của bài toán đối ngẫu do điều kiện (1) là
của bài toán gốc. Ràng buộc
,
của bài toán đối ngẫu do điều kiện (7) là
của bài toán gốc. Tương tự cặp bài toán sau đây được gọi là cặp bài toán đối ngẫu. Bài toán (P):
Bài toán (Q):
Từ đó ta thấy rằng đối ngẫu của bài toán đối ngẫu là bài toán gốc ban đầu. 2. Mối quan hệ giữa bài toán gốc và bài toán đối ngẫu: Trong phần này ta chỉ xét bài toán gốc dạng min. 2.1. Định lý 1:Cho x, y theo thứ tự là phương án của bài toán gốc và đối ngẫu ta có
hay tương đương
. Từ đó nếu tìm được
theo thứ tự là phương án của bài toán gốc và đối ngẫu sao cho
thì
là phương án tối ưu của các bài toán đó. 2.2. Định lý 2: Nếu cả hai bài toán gốc và đối ngẫu đều có tập phương án không rỗng thì cả hai bài toán đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng nhau. Từ đó nếu một trong hai bài toán gốc hoặc đối ngẫu có tập phương án khác rỗng và hàm mục tiêu không bị chặn (không bị chặn dưới nếu là bài toán min, không bị chặn trên nếu là bài toán max) thì bài toán còn lại có tập phương án bằng rỗng. 2.3. Định lý 3: Giả sử
là một phương án của bài toán gốc (P)
Khi đó, để
là phương án tối ưu của bài toán (P) điều kiện cần và đủ là tồn tại véctơ
sao cho
Trong đó
. Ví dụ: Xét xem
có phải là phương án tối ưu của bài toán Quy hoạch tuyến tính
Giải: Trước tiên ta chỉ rõ một số tập hợp:
. Từ
suy ra
. Thay
vào hai bất phương trình thứ 2, thứ 3 ta có
;
. Vậy
. Véctơ
là phương án tối ưu của bài toán khi tồn tại véctơ
sao cho
Từ hai phương trình đầu và
ta có
,
. Các nghiệm này không thỏa phương trình thứ ba. Vậy hệ đã cho vô nghiệm. Nói cách khác không tồn tại
thỏa hệ ở trên. Tóm lại, phương án
không phải là phương án tối ưu của bài toán đã cho. 2.4. Định lý 4: Nếu một trong hai bài toán (gốc hoặc đối ngẫu) có phương án tối ưu thì bài toán kia cũng có phương án tối ưu và giá trị tối ưu của hai hàm mục tiêu là bằng nhau. 2.5. Định lý 5