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

Archive for Tháng Hai, 2008

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ì

$\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).
$\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:

Trong bảng đơn hình của bài toán gốc, $\displaystyle x_B$ nằm ở cột đầu tiên.
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.
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)$ .
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)$ .
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:

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$ ).
Nếu $\displaystyle x_B\geq 0$ , dừng và kết luận $\displaystyle x_B$ là nghiệm tối ưu.
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.
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|}$
Thay thế $\displaystyle B(p)=k$ .
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:

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$ ).
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).
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$ ).
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).
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 $\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.

Đăng trong Quy hoạch tuyến tính | Tagged: 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 | 1 Comment »

Phương pháp đơn hình (Simplex method) (7) – Khử lặp vô hạn, luật từ điển, luật Bland

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

Trở ngại cuối cùng trong thuật toán đơn hình là tình huống lặp vô hạn khi gặp phải nghiệm cơ sở bị suy biến. Có hai nguyên nhân dẫn đến có thể xảy ra lặp vô hạn khi tiến hành thuật toán đơn hình:

Khi tính toán $\displaystyle \theta^*$ , có hai giá trị $\displaystyle p,q$ mà
$\displaystyle \frac{x_{B(p)}}{|d_{B(p)}|}=\frac{x_{B(q)}}{|d_{B(q)}|}=\theta^*$

nên khi cập nhật, ta có $\displaystyle x_{B*(q)}=x_{B(q)}-x_{B(p)}\frac{|d_{B(q)}|}{|d_{B(p)}|}=0$ . Tức là ta đi đến một nghiệm cơ sở bị suy biến.
Thuật toán đi đến một nghiệm cơ sở bị suy biến (có it nhất một biến cơ sở bằng 0) và
$\displaystyle \theta^*=\frac{x_{B(p)}}{|d_{B(p)}|}=\min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|} = 0$

do $\displaystyle x_{B(p)}=0$ . Như vậy, nghiệm cơ sở không thay đổi mà chỉ có hệ cơ sở thay đổi. Có thể xảy ra trường hợp các véctơ cơ sở bị tráo đổi theo cách vòng tròn mà nghiệm cơ sở không hề thay đổi, dẫn tới tình huống lặp vô hạn (mặc dù khả năng này rất hiếm khi xảy ra).

Để ý rằng, trong phương pháp đơn hình, ta có quyền chọn cặp chỉ số chốt $\displaystyle (p,k)$ miễn là

$\displaystyle \bar{c}_k<0, u=B^{-1}A_k, u_p>0, \frac{x_{B(p)}}{u_p}=\min_{i,u_i>0}\frac{x_{B(i)}}{u_i} =\theta^*$

Người ta chứng minh được rằng, nếu chọn $\displaystyle (p,k)$ theo những luật nhất định thì sẽ tránh được tình huống lặp vô hạn. Trong bài này, ta sẽ xem xét hai phương pháp đơn giản để khử vòng lặp vô hạn, đó là luật từ điển và luật Bland.

Định nghĩa (thứ tự từ điển): Ta nói véctơ $\displaystyle u\in \mathbb{R}^n$ có thứ tự từ điển nhỏ hơn véctơ $\displaystyle v\in \mathbb{R}^n$ , kí hiệu là $\displaystyle u\lessdot v$ hay $v\gtrdot u$ nếu

$\displaystyle i=\min\{i:u_i\neq v_i\}, u_i<v_i$

nghĩa là ở chỉ số đầu tiên mà $\displaystyle u_i\neq v_i$ thì $\displaystyle u_i<v_i$ .

Lưu ý: định nghĩa có thể mở rộng cho hai véc tơ không có cùng số chiều, nhưng trong bài này ta chỉ quan tâm đến các véctơ có cùng số chiều.

Định nghĩa (thứ tự từ điển dương): Ta nói véctơ $\displaystyle u\in \mathbb{R}^n$ có thứ tự từ điển dương (gọi tắt là thứ tự dương) nếu $\displaystyle 0\lessdot u$ hay $u\gtrdot 0$ .

Định nghĩa (luật từ điển): Luật từ điển là cách chọn chỉ số dòng $\displaystyle p$ tại mỗi bước lặp sao cho dòng được chọn có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt $\displaystyle u_p$ .

Định lý (tính dừng của luật từ điển): Nếu trong bước chọn dòng $\displaystyle p$ , ta luôn chọn dòng có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt $\displaystyle u_p$ thì

Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, các dòng này vẫn có thứ tự dương.
Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, thứ tự từ vựng của dòng đầu tiên tăng.
Nếu các dòng của bảng ban đầu (trừ dòng đầu tiên) có thứ tự dương thì thuật toán đơn hình luôn dừng.

Chứng minh (1): Với những dòng mà $\displaystyle u_i\leq 0$ thì $\displaystyle -\frac{u_i}{u_p}\geq 0$ nên nhân dòng $\displaystyle p$ với $\displaystyle -\frac{u_i}{u_p}$ rồi cộng vào dòng $\displaystyle i$ ta vẫn có thứ tự dương.

Với những dòng mà $\displaystyle u_i>0, \frac{x_{B(i)}}{u_i}>\frac{x_{B(p)}}{u_p}$ thì $\displaystyle x_{B^*(i)}=x_{B(i)}-x_{B(p)}\frac{u_i}{u_p}>0$ , tức là dòng $\displaystyle i$ vẫn có thứ tự dương vì $\displaystyle x_{B^*(i)}$ là giá trị đầu tiên trong dòng thứ $\displaystyle i$ ).

Với những dòng mà $\displaystyle u_i>0, \frac{x_{B(i)}}{u_i}=\frac{x_{B(p)}}{u_p}$ thì sau biến đổi dòng, dòng $\displaystyle i$ vẫn có thứ tự dương vì dòng $\displaystyle p$ chia cho $\displaystyle u_p$ có thứ tự từ điển nhỏ hơn dòng $\displaystyle i$ chia cho $\displaystyle u_i$ . Thật vậy, giả sử cột $\displaystyle k$ là cột đầu tiên mà

$\displaystyle \frac{v_i}{u_i}>\frac{v_p}{u_p}$

Trong đó $\displaystyle v_i, v_p$ lần lượt là các giá trị ở cột $\displaystyle k$ tại các hàng $\displaystyle i, p$ . Suy ra

$\displaystyle v_i^*=v_i-v_p\frac{u_i}{u_p}>0$

Vì $\displaystyle v_i^*$ là giá trị đầu tiên khác $\displaystyle 0$ trên dòng $\displaystyle i$ sau khi biến đổi dòng nên dòng $\displaystyle i$ có thứ tự dương.

Chứng minh (2): vì $\displaystyle \bar{c}_k<0$ nên $\displaystyle -\frac{\bar{c}_k}{u_p} >0$ . Do vậy, khi nhân dòng thứ $\displaystyle p$ với $\displaystyle -\frac{\bar{c}_k}{u_p}$ rồi cộng vào dòng đầu tiên, thứ tự từ điển của dòng đầu tiên sẽ tăng lên (do dòng $\displaystyle p$ có thứ tự dương).

Chứng minh (3): Do số bảng đơn hình là hữu hạn (bằng số bộ cơ sở có thể có), mà thứ tự từ điển của dòng đầu tiên lại luôn tăng, nên đến lúc nào đó, thuật toán đơn hình phải dừng.

Nhận xét: Để tạo được các dòng có thứ tự dương trong bảng ban đầu, ta có thể đảo chỗ các biến bù lên đầu, như vậy ma trận $\displaystyle B^{-1}\widehat{A}=\left[\begin{array}{rr}I&A\end{array}\right]$ , hơn nữa, $\displaystyle x_B\geq 0$ (cột đầu tiên của bảng) nên tất cả các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương.

Định nghĩa (Luật Bland): Cách lựa chọn cặp chỉ số chốt $\displaystyle (p,k)$ sau đây gọi là luật Bland:

Trong bước chọn cột, chọn chỉ số $\displaystyle k$ nhỏ nhất sao cho $\displaystyle \bar{c}_k<0$ .
Trong bước chọn dòng, chọn chỉ số $\displaystyle p$ nhỏ nhất sao cho $\displaystyle \frac{x_{B(p)}}{u_p}=\theta^*$ .

Định lý (tính dừng của luật Bland): Nếu lựa chọn cặp chỉ số chốt $\displaystyle (p,k)$ theo luật Bland thì thuật toán đơn hình luôn dừng.

Đăng trong Quy hoạch tuyến tính | Tagged: luật Bland, luật từ điển, phương pháp đơn hình, suy biến, thứ tự từ điển | Leave a Comment »

« Những bài viết trước

	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

Archive for Tháng Hai, 2008

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

Phương pháp đơn hình (Simplex method) (7) – Khử lặp vô hạn, luật từ điển, luật Bland