Bài toán đối ngẫu « CS Study Fun

Tháng Hai 2008
T2	T3	T4	T5	T6	T7	CN
		Tháng 3 »
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29

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

Đăng bởi tqlong 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

$(P)$ thỏa được – nghĩa là $\{x:Ax\geq b\}\neq\emptyset$ và $\mathrm{Opt}(P)$ bị chặn dưới.
$(D)$ thỏa được – nghĩa là $\{\lambda:A^T\lambda=c,\lambda\geq 0\}\neq\emptyset$ và $\mathrm{Opt}(D)$ bị chặn trên.
$\mathrm{Opt}(P)$ có nghiệm.
$\mathrm{Opt}(D)$ có nghiệm.
$(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 2$ và $1\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)$ và $\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)$ và $\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$ và $\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:

Đị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.
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.
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$ .

Bài viết này được đăng vào Tháng Hai 4, 2008 lúc 11:45 chiều và tập tin được lưu ở Quy hoạch tuyến tính. Tagged: cực tiểu, cực đại, farkas, Quy hoạch tuyến tính, đối ngẫu. 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ể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.

Để lại hồi âm

« Định lý đảo tổng quát

Hàm lồi (1) – Định nghĩa và tính chất cơ bản »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

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

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

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

Để lại hồi âm