CS Study Fun – Khoa học máy tính

Learn & Enjoy …

«
»

Phương pháp đơn hình (Simplex method) (8) – Thuật toán đơn hình đối ngẫu

Đăng bởi tqlong on Tháng Hai 28, 2008

Ta đã biết bài toán đối ngẫu của bài toán QHTT dạng tổng quát

\displaystyle \min \{c^Tx:Ax\geq b\}

là bài toán

\displaystyle \max \{\lambda^Tb:\lambda^TA=c^T,\lambda^T\geq 0^T\} .

Có thể hiểu như sau:

  • Đối ngẫu của ràng buộc \displaystyle a_i^Tx_i\geq b_i là ràng buộc \displaystyle \lambda_i\geq 0.
  • Đối ngẫu của ràng buộc “\displaystyle x_j là biến tự do” là ràng buộc \displaystyle \lambda^TA_j=c_j.

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:

  • Đối ngẫu của ràng buộc \displaystyle a_i^Tx_i\leq b_i là ràng buộc \displaystyle \lambda_i\leq 0.
  • Đối ngẫu của ràng buộc \displaystyle a_i^Tx_i=b_i là ràng buộc “\displaystyle \lambda_i là biến tự do”.
  • Đối ngẫu của ràng buộc \displaystyle x_j\geq 0 là ràng buộc \displaystyle \lambda^TA_j\leq c_j.
  • Đối ngẫu của ràng buộc \displaystyle x_j\leq 0 là ràng buộc \displaystyle \lambda^TA_j\geq c_j.

Để cho dễ nhớ, ta tổng kết lại thành hai điều kiện sau:

\displaystyle (a_i^Tx_i-b_i)\lambda_i\geq 0,\forall i=1,\ldots,m

\displaystyle x_j(c_j-\lambda^TA_j)\geq 0, \forall j=1,\ldots, n

Dấu bằng chỉ xảy ra khi biến \displaystyle \lambda_i, x_j 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

\displaystyle \min \{c^Tx:Ax=b,x\geq 0\}~~(P)

thì bài toán đối ngẫu của nó là

\displaystyle \max \{\lambda^Tb:\lambda^TA\leq c^T\}~~(D)

vì các điều kiện đẳng thức \displaystyle a_i^Tx=b_i nên biến đối ngẫu \displaystyle \lambda_i là biến tự do. Bài toán đối ngẫu \displaystyle (D) 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ó nghiệm tối ưu. 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 \displaystyle B là một ma trận cơ sở của \displaystyle A (tức là \displaystyle B gồm \displaystyle m cột độc lập tuyến tính của \displaystyle A) thì

  1. \displaystyle x_B=B^{-1}b là nghiệm cơ sở của \displaystyle (P) (ta chỉ quan tâm đến \displaystyle x_B vì các thành phần khác của \displaystyle x bằng 0).
  2. \displaystyle \lambda^T=c_B^TB^{-1} là nghiệm cơ sở của \displaystyle (D).

Chứng minh (1): ta đã biết tính chất này của nghiệm cơ sở của bài toán QHTT ở dạng chuẩn tắc.

Chứng minh (2): hiển nhiên vì \displaystyle \lambda^TB=c_B nên có \displaystyle m ràng buộc độc lập tuyến tính được kích hoạt ở \displaystyle \lambda^T.

Nhận xét:

  1. Trong bảng đơn hình của bài toán gốc, \displaystyle x_B nằm ở cột đầu tiên.
  2. Còn dòng đầu tiên \displaystyle \bar{c}^T=c^T-c_B^TB^{-1}A=c^T-\lambda^TA là giá trị thay đổi trên các hướng. Việc kiểm tra điều kiện tối ưu\displaystyle \bar{c}^T=c^T-\lambda^TA\geq 0 của bài toán gốc \displaystyle (P) chính là việc kiểm tra xem\displaystyle \lambda^T có phải là nghiệm cơ sở chấp nhận được của\displaystyle (D) hay không.
  3. Giá trị hàm mục tiêu \displaystyle \lambda^Tb=c_B^TB^{-1}b=c_B^Tx_B, nghĩa là khi thuật toán đơn hình dừng (\displaystyle \lambda^T 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 \displaystyle (P) bằng với giá trị hàm mục tiêu của bài toán đối ngẫu \displaystyle (D) tại nghiệm cơ sở chấp nhận được \displaystyle \lambda^T. Suy ra \displaystyle \lambda^T cũng là nghiệm tối ưu của bài toán đối ngẫu \displaystyle (D).
  4. 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 \displaystyle x_B của bài toán gốc\displaystyle (P), 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 \displaystyle \lambda^T của \displaystyle x_B 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 \displaystyle (D).
  5. 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 \displaystyle (D), thực hiện các phép biến đổi cơ sở để nghiệm cơ sở tương ứng \displaystyle x_B của \displaystyle \lambda^T trở thành nghiệm cơ sở chấp nhận được của bài toán gốc \displaystyle (P) (và như vậy cũng là nghiệm tối ưu vì ta luôn có \displaystyle \lambda^T là nghiệm cơ sở chấp nhận được của (D), \displaystyle c^T-\lambda^TA\geq 0).

Thuật toán đơn hình đối ngẫu:

  1. Xuất phát từ một ma trận cơ sở \displaystyle B sao cho \displaystyle \bar{c}^T=c^T-c_B^TB^{-1}A\geq 0. Xây dựng bảng đơn hình của bài toán gốc.
    Lưu ý: \displaystyle x_B 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 (\displaystyle x_B\ngeq 0).
  2. Nếu \displaystyle x_B\geq 0, dừng và kết luận \displaystyle x_B là nghiệm tối ưu.
  3. Nếu có chỉ số \displaystyle p sao cho\displaystyle x_{B(p)}<0, gọi \displaystyle v_1,\ldots,v_n là các phần tử còn lại trên dòng \displaystyle p+1 của bảng đơn hình. Nếu\displaystyle v_i\geq 0,\forall i 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.
  4. Ngược lại, chọn chỉ số \displaystyle k sao cho
    \displaystyle v_k<0 và\displaystyle \frac{\bar{c}_k}{|v_k|}=\min_{j,v_j<0}\frac{\bar{c}_j}{|v_j|}
  5. Thay thế\displaystyle B(p)=k.
  6. Sử dụng các phép biến đổi dòng sao cho cột \displaystyle k+1 gồm toàn số \displaystyle 0 và chỉ có duy nhất một số \displaystyle 1 ở hàng \displaystyle p+1.

Nhận xét:

  1. Do \displaystyle x_{B(p)}<0 và \displaystyle \frac{\bar{c}_k}{v_k}<0 nên phép biến đổi bằng cách nhân dòng thứ \displaystyle p+1 với \displaystyle -\frac{\bar{c}_k}{v_k} 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 \displaystyle -c_B^Tx_B).
  2. Trong thuật toán đơn hình, ta giữ\displaystyle x_B\geq 0 và biến đổi hệ cơ sở sao cho\displaystyle \bar{c}^T\geq 0, còn trong thuật toán đơn hình đối ngẫu, ta giữ \displaystyle \bar{c}^T\geq 0 và biến đổi hệ cơ sở sao cho\displaystyle x_B\geq 0. 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).
  3. 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ở\displaystyle B sao cho\displaystyle \bar{c}^T=c^T-c_B^TB^{-1}A\geq 0. Điều kiện này luôn thỏa mãn nếu \displaystyle x_B là nghiệm tối ưu và \displaystyle B 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ơ \displaystyle b khác nhau thì ta có thể sử dụng ma trận cơ sở tối ưu \displaystyle B 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ơ \displaystyle b không làm thay đổi \displaystyle \bar{c}^T, do đó ta chỉ phải tính lại cột đầu tiên, tức là tính \displaystyle c_B^Tx_B và \displaystyle x_B).
  4. 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 \displaystyle x của bài toán gốc và một nghiệm \displaystyle \lambda^T 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\displaystyle c^Tx-\lambda^Tb\rightarrow 0 (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).
  5. 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.
  6. 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 \displaystyle m\rightarrow 3m 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à \displaystyle \Theta(n^2), nhưng độ phức tạp trung bình là \displaystyle \Theta(n\ln n) với hằng số nhỏ hơn các thuật toán khác có độ phức tạp \displaystyle \Theta(n\ln n) trong trường hợp xấu nhất.

Bài viết này được đăng vào Tháng Hai 28, 2008 lúc 11:23 sáng và tập tin được lưu ở Quy hoạch tuyến tính. Tagged: , , , , , . Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể Để lại lời nhắn, hoặc trackback từ trang của bạn.

Có mộ phản hồi tới “Phương pháp đơn hình (Simplex method) (8) – Thuật toán đơn hình đối ngẫu”

  1. Tung đã nói

    Tháng Mười 9, 2008 lúc 4:41 sáng

    Hi, blog cua ban rat bo ich, tuy nhien neu them cac term bang tieng Anh (vd: simplex method) o dau bai thi se de google ra hon. chuc vui.
    Tung.

    Trả lời

Để lại hồi âm

XHTML: Bạn có thể sử dụng những thẻ sau: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

«
»