Người ta chứng minh được rằng (tương tự như chứng minh đã biết), các dạng ràng buộc khác cũng có các ràng buộc đối ngẫu tương ứng: Để cho dễ nhớ, ta tổng kết lại thành hai điều kiện sau: Dấu bằng chỉ xảy ra khi biến là biến tự do và ràng buộc là đẳng thức. Như vậy, nếu bài toán QHTT ở dạng chuẩn tắc thì bài toán đối ngẫu của nó là vì các điều kiện đẳng thức nên biến đối ngẫu là biến tự do. Bài toán đối ngẫu cũng là một bài toán QHTT, ta hoàn toàn có thể chuyển nó về dạng chuẩn tắc rồi giải bằng phương pháp đơn hình. Trong bài này, ta sẽ xem xét một phương pháp khác, sử dụng bảng đơn hình của bài toán gốc (bài toán gốc đã ở dạng chuẩn tắc) để giải bài toán đối ngẫu. Lưu ý là nếu bài toán đối ngẫu có nghiệm tối ưu thì bài toán gốc cũng có . Thuật toán này được gọi là thuật toán đơn hình đối ngẫu (dual simplex method). Định lý (tính tương ứng của nghiệm cơ sở của hai bài toán): Nếu là một ma trận cơ sở của (tức là gồm cột độc lập tuyến tính của ) thì - là nghiệm cơ sở của (ta chỉ quan tâm đến vì các thành phần khác của bằng 0).
- là nghiệm cơ sở của .
Chứng minh (1): ta đã biết tính chất này của của bài toán QHTT ở dạng chuẩn tắc. Chứng minh (2): hiển nhiên vì nên có ràng buộc được kích hoạt ở . Nhận xét: - Trong bảng đơn hình của bài toán gốc, nằm ở cột đầu tiên.
- Còn dòng đầu tiên là giá trị thay đổi trên các hướng. Việc kiểm tra điều kiện tối ưu của bài toán gốc chính là việc kiểm tra xem có phải là nghiệm cơ sở chấp nhận được của hay không.
- Giá trị hàm mục tiêu , nghĩa là khi thuật toán đơn hình dừng ( là nghiệm cơ sở chấp nhận được), giá trị hàm mục tiêu của bài toán gốc bằng với giá trị hàm mục tiêu của bài toán đối ngẫu tại nghiệm cơ sở chấp nhận được . Suy ra cũng là nghiệm tối ưu của bài toán đối ngẫu .
- Vậy có thể hiểu thuật toán đơn hình là thuật toán xuất phát từ một nghiệm cơ sở chấp nhận được của bài toán gốc, ta thực hiện một loạt các phép biến đổi hệ cơ sở sao cho nghiệm cơ sở tương ứng của trở thành nghiệm cơ sở chấp nhận được (và cũng là nghiệm tối ưu) của bài toán đối ngẫu .
- Thuật toán đơn hình đối ngẫu là thuật toán xuất phát từ một nghiệm cơ sở chấp nhận được của , thực hiện các phép biến đổi cơ sở để nghiệm cơ sở tương ứng của trở thành nghiệm cơ sở chấp nhận được của bài toán gốc (và như vậy cũng là nghiệm tối ưu vì ta luôn có là nghiệm cơ sở chấp nhận được của ).
Thuật toán đơn hình đối ngẫu: - Xuất phát từ một ma trận cơ sở sao cho . Xây dựng bảng đơn hình của bài toán gốc.
Lưu ý: trong cột đầu tiên của bảng có thể không phải là nghiệm cơ sở chấp nhận được ().
- Nếu , dừng và kết luận là nghiệm tối ưu.
- Nếu có chỉ số sao cho, gọi là các phần tử còn lại trên dòng của bảng đơn hình. Nếu thì dừng và kết luận bài toán đối ngẫu (và bài toán gốc) không bị chặn và không có nghiệm tối ưu.
- Ngược lại, chọn chỉ số sao cho
và
- Thay thế.
- Sử dụng các phép biến đổi dòng sao cho cột gồm toàn số và chỉ có duy nhất một số ở hàng .
Nhận xét: - Do và nên phép biến đổi bằng cách nhân dòng thứ với rồi cộng vào dòng đầu tiên luôn làm giảm giá trị hàm mục tiêu (làm tăng giá trị ở góc trái trên của bảng ).
- Trong thuật toán đơn hình, ta giữ và biến đổi hệ cơ sở sao cho, còn trong thuật toán đơn hình đối ngẫu, ta giữ và biến đổi hệ cơ sở sao cho. Ta cũng có thể thấy các thao tác trên đây đều ngược lại với các thao tác ở thuật toán đơn hình (gốc).
- Khi nào thì ta sử dụng thuật toán đơn hình đối ngẫu? Để ý rằng ta phải chọn điểm xuất phát là ma trận cơ sở sao cho. Điều kiện này luôn thỏa mãn nếu là nghiệm tối ưu và là ma trận cơ sở tối ưu. Vì vậy, trong trường hợp ta cần giải bài toán QHTT thêm nhiều lần nữa với các giá trị véctơ khác nhau thì ta có thể sử dụng ma trận cơ sở tối ưu của lần giải đầu tiên làm ma trận cơ sở ban đầu của các bài toán này và áp dụng thuật toán đơn hình đối ngẫu (Lưu ý: thay đổi véctơ không làm thay đổi , do đó ta chỉ phải tính lại cột đầu tiên, tức là tính và ).
- Nói chung, trong hai thuật toán đơn hình, luôn luôn có một thuật toán có xuất phát điểm dễ dàng hơn. Vì vậy, trong thực hành (cài đặt), người ta thường sử dụng luân phiên hai thuật toán này. Một cách khác là sử dụng đồng thời ý tưởng của cả hai thuật toán (primal-dual method/schema), nghĩa là xuất phát từ một nghiệm của bài toán gốc và một nghiệm của bài toán đối ngẫu, ta biến đổi cả hai nghiệm sao cho khoảng cách đối ngẫu (duality gap). Ta sẽ còn quay lại vấn đề này trong loạt bài về các phương pháp điểm trong (interior point methods) giải bài toán QHTT. Ý tưởng của các phương pháp này là xuất phát từ một điểm bên trong đa diện lồi, biến đổi điểm này để đi đến nghiệm tối ưu – tức là đi ra một điểm cực biên (ngược lại với phương pháp đơn hình, ta luôn ở trên biên của đa diện lồi vì nghiệm cơ sở chấp nhận được chính là điểm cực biên).
- Các phương pháp điểm trong được chứng minh là có độ phức tạp thuật toán đa thức (polynomial complexity) trong mọi trường hợp, trong khi đó, phương pháp đơn hình trong trường hợp xấu nhất có độ phức tạp lũy thừa (exponential complexity). Có thể hiểu nôm na là do phương pháp đơn hình chạy trên biên của đa diện lồi nên mất nhiều thời gian để đi đến nghiệm tối ưu (nếu nghiệm này nằm ở mặt bên kia của đa diện). Còn các phương pháp điểm trong thì đi từ bên trong của đa diện ra ngoài biên (theo những quy tắc nhất định) nên bất kể nghiệm tối ưu nằm ở đâu thuật toán cũng không bị ảnh hưởng lớn.
- Tuy có độ phức tạp lũy thừa, phương pháp đơn hình vẫn được cài đặt thành công và có ứng dụng rất rộng rãi trên nhiều bài toán QHTT lớn (hàng nghìn biến và ràng buộc). Lí do là trong thực hành, người ta nhận thấy thuật toán đơn hình thường đi đến nghiệm tối ưu chỉ trong lần lặp. Tương tự như thuật toán sắp xếp nổi tiếng Quicksort, độ phức tạp trong trường hợp xấu nhất là , nhưng độ phức tạp trung bình là với hằng số nhỏ hơn các thuật toán khác có độ phức tạp trong trường hợp xấu nhất.
Nhãn: nghiệm cơ sở, phương pháp điểm trong, phương pháp đơn hình, Quicksort, ràng buộc, đối ngẫu This entry was posted on Tháng Hai 28, 2008 at 11:23 sáng and is filed under Quy hoạch tuyến tính. You can follow any responses to this entry through the RSS 2.0 feed. You can , or trackback from your own site. | 
