Ta biết rằng, bài toán quy hoạch tuyến tính hay có bài toán đối ngẫu là hay Trong bài này, ta sẽ xem xét khái niệm đối ngẫu của bài toán quy hoạch nón hay với là nón lồi có đỉnh, đóng và có phần trong khác rỗng. Ta thấy, trong bài toán quy hoạch tuyến tính, bất cứ véctơ nào thỏa mãn thì với mọi , ta có Như vậy, nếu thỏa mãn ta luôn có là cận dưới của giá trị tối ưu của bài toán gốc. Nghĩa là, về bản chất, bài toán đối ngẫu tìm cách cực đại hóa cận dưới này. Vậy trong bài toán quy hoạch nón thì sao, các điều kiện cần có của để luôn là cận dưới của giá trị tối ưu của bài toán gốc là gì ? Điều kiện đầu tiên vẫn là , còn điều kiện thứ hai chính là hoặc với 2 điều kiện này, với mọi , ta có thể viết vì . Như vậy, các véctơ cần thỏa mãn 2 điều kiện
Ta có thể viết bài toán đối ngẫu của bài toán quy hoạch nón gốc như sau Trong đó gọi là nón đối ngẫu (dual cone) của nón . Một số tính chất của nón đối ngẫu: Tính chất 1: Đối ngẫu của nón đối ngẫu chính là nón . Chứng minh: Xét , ta có , suy ra , vậy Xét , ta có Vì là nón lồi thuộc nên tồn tại sao cho (tổ hợp nón) Suy ra Vậy là hệ quả của hệ bất đẳng thức . Theo định lý Farkas thuần nhất, phải tồn tại các hệ số không âm sao cho nghĩa là , vậy . Kết luận . Tính chất 2: Nếu nón lồi có đỉnh, đóng và có phần trong khác rỗng thì nón đối ngẫu cũng là nón lồi có đỉnh, đóng và có phần trong khác rỗng. Chứng minh: (1): đóng, thật vậy, xét và bất kì. Do và hàm tuyến tính là hàm liên tục, ta cũng có nghĩa là . (2): là nón lồi, thật vậy nếu , hiển nhiên và . Lưu ý: Chứng minh (1) và (2) không phụ thuộc vào việc có là nón lồi, có đỉnh, đóng, có phần trong khác rỗng hay không. Nghĩa là luôn là nón lồi đóng với mọi tập . (3): có phần trong khác rỗng có đỉnh. Thật vậy, xét và . Vì , tồn tại . Suy ra , mâu thuẫn. Vậy . (4): có đỉnh có phần trong khác rỗng. Để chứng minh (4), ta chỉ cần chứng minh không có đỉnh và sử dụng tính chất 1 ở trên. Thật vậy, vì nên nghĩa là nón nằm trong một không gian có số chiều nhỏ hơn . Vậy , nghĩa là không có đỉnh. Nhận xét: Do tính chất (1), mệnh đề ngược lại của tính chất (2) cũng đúng. Tính chất 3: Đối ngẫu của tích Descartes các nón là tích Descartes của các nón đối ngẫu . Nhận xét: Với tính chất này ta có thể nhóm các điều kiện thành một điều kiện duy nhất . Ví dụ:
|
