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

Learn & Enjoy …

Bài toán đối ngẫu

Posted by Trần Quốc Long on Tháng Hai 4, 2008

Định nghĩa 1 (Quy hoạch tuyến tính – Bài toán gốc). Bài toán quy hoạch tuyến tính (gốc) là bài toán tìm cực tiểu sau

\displaystyle\mathrm{Opt}(P)=\min_x\{c^Tx|Ax\geq b\}.

Nhận xét:
1. Theo định lý Farkas không thuần nhất, do c^Tx\geq\mathrm{Opt}(P) (giả sử có nghiệm) là hệ quả của hệ bất phương trình Ax\geq b, tồn tại \lambda sao cho \lambda\geq 0, A^T \lambda = c, suy ra c^Tx = \lambda^TAx \geq \lambda^Tb với mọi x sao cho Ax\geq b.

2. Như vậy, nếu \lambda\geq 0, A^T \lambda = c thì b^T\lambda là cận dưới của \mathrm{Opt}(P).

Định nghĩa 2 (Quy hoạch tuyến tính – Bài toán đối ngẫu). Bài toán đối ngẫu của (P) là bài toán tìm cực đại sau

\displaystyle\mathrm{Opt}(D)=\max_\lambda\{b^T\lambda|A^T\lambda=c,\lambda\geq 0\}.

Định lý 1 (Tính đối ngẫu). Hai bài toán gốc và đối ngẫu có các tính chất sau:

(i) Đối ngẫu của bài toán đối ngẫu là bài toán gốc.
(ii) c^Tx\geq b^T\lambda với mọi x,\lambda thỏa mãn ràng buộc của (P),(D).
(iii) Các tính chất sau đây tương đương

  1. (P) thỏa được – nghĩa là \{x:Ax\geq b\}\neq\emptyset\mathrm{Opt}(P) bị chặn dưới.
  2. (D) thỏa được – nghĩa là \{\lambda:A^T\lambda=c,\lambda\geq 0\}\neq\emptyset\mathrm{Opt}(D) bị chặn trên.
  3. \mathrm{Opt}(P) có nghiệm.
  4. \mathrm{Opt}(D) có nghiệm.
  5. (P), (D) đều thỏa được. Khi đó \mathrm{Opt}(P) = \mathrm{Opt}(D).

Chứng minh:

Chứng minh (i) và (ii): hiển nhiên suy ra từ nhận xét ở trên.

Chứng minh (iii):

1\Rightarrow 4: c^Tx\geq\mathrm{Opt}(P) là hệ quả của hệ phương trình có nghiệm Ax\geq b, theo định lý Farkas không thuần nhất, suy ra

\exists\lambda\geq 0, A^T\lambda=c,b^T\lambda\geq\mathrm{Opt}(P)

Theo (ii), b^T\lambda\leq\mathrm{Opt}(P), vậy b^T\lambda=\mathrm{Opt}(P)\geq\mathrm{Opt}(D). Nghĩa là \mathrm{Opt}(D) có nghiệm.

4\Rightarrow 2: hiển nhiên.

2\Rightarrow 3: theo (i), đối ngẫu của bài toán đối ngẫu là bài toán gốc, vì thế 1\Rightarrow 4 chứng tỏ 2\Rightarrow 3.

3\Rightarrow 1: hiển nhiên.

Như vậy, ta có 1\Leftrightarrow 2\Leftrightarrow 3\Leftrightarrow 4, ta cần chứng minh những mệnh đề này cũng tương đương với mệnh đề 5. Thật vậy, theo (ii), hiển nhiên 5\Rightarrow 1. Ngược lại, 1\Leftrightarrow 21\Rightarrow \mathrm{Opt}(P)=\mathrm{Opt}(D), nên 1\Rightarrow 5.

Định lý 2 (Tính chất nghiệm) Giả sử hai bài toán (P),(D) đều thỏa được, khi đó x,\lambda là hai nghiệm của \mathrm{Opt}(P)\mathrm{Opt}(D)

  • nếu và chỉ nếu c^Tx-b^T\lambda=0 (khoảng cách đối ngẫu bằng 0).
  • nếu và chỉ nếu \left[Ax-b\right]_i.\lambda_i=0,\forall i (độ vênh ở ràng buộc bù nhau).

Chứng minh:

c^Tx-b^T\lambda=c^Tx-\mathrm{Opt}(P)+\mathrm{Opt}(D)-b^T\lambda\geq 0

Vậy x,\lambda là hai nghiệm của \mathrm{Opt}(P)\mathrm{Opt}(D) nếu và chỉ nếu c^Tx-b^T\lambda=0.

c^Tx-b^T\lambda=\lambda^TAx-b^T\lambda=\left[Ax-b\right]^T\lambda\geq 0

Do Ax-b\geq 0\lambda\geq 0, c^Tx-b^T\lambda=0 nếu và chỉ nếu \left[Ax-b\right]_i.\lambda_i=0,\forall i.

Nhận xét:

  1. Định lý về tính đối ngẫu và tính chất của nghiệm cho thấy mối quan hệ mật thiết giữa hai bài toán (P),(D), đặc biệt giá trị tối ưu (nếu có) của cả hai bài toán trùng nhau.
  2. Là hệ quả của định lý Farkas nên tính có nghiệm của bài toán này là bằng chứng về tính có nghiệm của bài toán kia. Đặc biệt, khi một trong hai bài toán không có lời giải chứng tỏ bài toán kia không thỏa được hoặc giá trị tối ưu không bị chặn, tức là cũng không có lời giải.
  3. Tính chất bù nhau của độ vênh ở ràng buộc của hai bài toán khá thú vị:
    Nếu \left[Ax-b\right]_i\neq 0 thì chắc chắn \lambda_i=0.
    Nếu \lambda_i\neq 0 thì chắc chắn \left[Ax-b\right]_i=0.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: