Phương pháp đơn hình (Simplex method) (6) – Khởi tạo thuật toán đơn hình, thuật toán hai pha « 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

Phương pháp đơn hình (Simplex method) (6) – Khởi tạo thuật toán đơn hình, thuật toán hai pha

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

Trong các bài trước, ta luôn bắt đầu thuật toán với câu “Xuất phát từ một nghiệm cơ sở chấp nhận được…”, vậy làm thế nào để xây dựng nghiệm cơ sở này? Trong bài này ta sẽ xem xét các phương pháp để khởi tạo thuật toán đơn hình.

Khởi tạo bài toán QHTT ở dạng tổng quát: Như đã thấy ở các ví dụ trước, bài toán QHTT dạng tổng quát

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

có thể biến thành bài toán QHTT ở dạng chuẩn tắc

$\displaystyle \min \{\widehat{c}^Tz:\widehat{A}z=b,z\geq 0\}$

với $\displaystyle \widehat{c} =\left[\begin{array}{r}c\\-c\\{0}\end{array}\right]$ , $\widehat{A}=\left[\begin{array}{ccc}A&-A&-I\end{array}\right]$ , $z=\left[\begin{array}{c}x^+\\x^-\\s\end{array}\right]$ . Nghĩa là ta thay $\displaystyle x=x^+-x^-$ và thêm vào các biến bù $\displaystyle s\geq 0$ để biến bất đẳng thức thành đẳng thức. Ở dạng này, một nghiệm cơ sở chấp nhận được hiển nhiên là $\displaystyle z=\left[\begin{array}{c}x^+\\x^-\\s\end{array}\right]=\left[\begin{array}{c}0\\{0}\\b\end{array}\right]$ (chính các biến bù tạo nên hệ cơ sở ban đầu) và ma trận cơ sở ban đầu chính là $\displaystyle B=I$ ( $\displaystyle m$ cột cuối cùng của $\displaystyle \widehat{A}$ ).

Để ý rằng ta chỉ chọn được nghiệm cơ sở chấp nhận được như trên nếu $\displaystyle b\geq 0$ . May mắn là nếu $\displaystyle b_i<0$ ta có thể nhân ràng buộc $\displaystyle \widehat{a}_i^Tz=b_i$ với $\displaystyle -1$ mà vẫn giữ nguyên tập nghiệm của bài toán QHTT. Vì thế không mất tính tổng quát, ta luôn có thể giả sử $\displaystyle b\geq 0$ .

Khởi tạo bài toán QHTT ở dạng chuẩn tắc: Nếu bài toán có dạng chuẩn tắc

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

thì ta cũng thêm vào các biến bù như trên nhưng thay đổi hàm mục tiêu đi, bài toán trở thành

$\displaystyle \min \{1^Ts:\widehat{A}z= b,z\geq 0\}~~(P_2)$

với $\displaystyle z=\left[\begin{array}{c}x\\s\end{array}\right], \widehat{A} =\left[\begin{array}{cc}A&I\end{array}\right]$ . Tức là hàm mục tiêu là tổng các thành phần trong véctơ $\displaystyle s$ . Dễ thấy nghiệm cơ sở chấp nhận được ban đầu của bài toán $\displaystyle (P_2)$ là $\displaystyle z=\left[\begin{array}{c}x\\s\end{array}\right]=\left[\begin{array}{c}0\\b\end{array}\right]$ và ma trận cơ sở ban đầu chính là $\displaystyle B=I$ . Ta có thể áp dụng thuật toán đơn hình để tìm giá trị tối ưu của $\displaystyle (P_2)$ . Có 2 trường hợp có thể xảy ra:

Nếu giá trị tối ưu của $\displaystyle (P_2)$ dương thì bài toán ban đầu không thể có nghiệm chấp nhận được (bài toán không thỏa được, tập nghiệm rỗng).
Nếu giá trị tối ưu của $\displaystyle (P_2)$ bằng $\displaystyle 0$ thì ta sẽ dùng nghiệm tối ưu của bài toán này để khởi tạo nghiệm ban đầu của bài toán gốc.

Khởi tạo nghiệm cơ sở chấp nhận được của $\displaystyle (P_1)$ từ nghiệm tối ưu của $\displaystyle (P_2)$ : Dễ thấy, khi giá trị tối ưu của $\displaystyle (P_2)$ bằng $\displaystyle 0$ thì $\displaystyle s=0$ . Tức là nghiệm tối ưu của $\displaystyle (P_2)$ có dạng

$\displaystyle z=\left[\begin{array}{c}x\\s\end{array}\right]=\left[\begin{array}{c}x\\{0}\end{array}\right]$ .

Nếu tất cả $\displaystyle m$ biến cơ sở đều nằm trong $\displaystyle x$ thì rõ ràng, các biến này cũng tạo nên biến cơ sở của $\displaystyle (P_1)$ vì

Các cột tương ứng của $\displaystyle A$ độc lập tuyến tính, dẫn đến ma trận $\displaystyle B$ khả nghịch.
Các biến không phải biến cơ sở đều bằng $\displaystyle 0$ .

Vấn đề ở chỗ một số biến trong $\displaystyle s$ vẫn có thể là biến cơ sở. Ta sẽ tìm cách loạt bỏ các biến này và thay bằng các biến trong $\displaystyle x$ . Xét $\displaystyle p=1,\ldots,m$ sao cho $\displaystyle B(p)>n$ (tức là biến cơ sở tương ứng nằm trong $\displaystyle s$ ), ta sẽ tìm cách loại $\displaystyle \widehat{A}_{B(p)}$ ra khỏi hệ cơ sở và thay bằng $\displaystyle \widehat{A}_k$ nào đó với $\displaystyle k\leq n$ .

Véc tơ $\displaystyle \widehat{A}_k$ này phải độc lập tuyến tính với $\displaystyle \widehat{A}_{B(1)},\ldots,\widehat{A}_{B(p-1)},\widehat{A}_{B(p+1)},\ldots,\widehat{A}_{B(m)}$ . Tức là ma trận

$\displaystyle B^*=\left[\begin{array}{ccccccc}\widehat{A}_{B(1)}&\ldots&\widehat{A}_{B(p-1)}&\widehat{A}_k&\widehat{A}_{B(p+1)}&\ldots&\widehat{A}_{B(m)}\end{array}\right]$

khả nghịch. Ta đã biết ở bài trước, để $\displaystyle B^*$ khả nghịch thì $\displaystyle B^{-1}B^*$ khả nghịch, tức là véc tơ $\displaystyle u=B^{-1}\widehat{A}_k$ (cột thứ $\displaystyle k+1$ trong bảng đơn hình) phải có $\displaystyle u_p\neq 0$ (hàng thứ $\displaystyle p+1$ ). Như vậy, ta chỉ cần tìm chỉ số $\displaystyle k\leq n$ sao cho vị trí $\displaystyle (p+1,k+1)$ trên bảng đơn hình khác $\displaystyle 0$ . Sau đó ta thay đổi hệ cơ sở $\displaystyle B(p)=k$ bằng cách làm các thao tác biến đổi dòng $\displaystyle Q$ sao cho cột $Qu=e_p$ . Để ý là biến cơ sở $\displaystyle x_k=0$ nên các biến đổi dòng này không làm thay đổi các biến cơ sở khác, tức là nghiệm cơ sở chấp nhận được vẫn không thay đổi, ta chỉ thay đổi hệ cơ sở mà thôi (Lưu ý: như vậy, ta có nghiệm cơ sở suy biến).

Trường hợp không tìm được chỉ số $\displaystyle k$ như vậy thì sao? Tức là toàn bộ dòng thứ $\displaystyle p+1$ của bảng bằng $\displaystyle 0$ . Khi đó rõ ràng $\displaystyle g_p^TA = 0$ với $\displaystyle g_p^T$ là dòng thứ $\displaystyle p$ của $\displaystyle B^{-1}$ . Có nghĩa là dòng thứ $\displaystyle p$ của $\displaystyle A$ phụ thuộc tuyến tính vào các dòng khác, như vậy ta có thể loại bỏ ràng buộc này ra (đồng thời cũng loại bỏ luôn biến bù tương ứng) mà không làm thay đổi tập nghiệm của bài toán gốc.

Tổng kết lại, ta có thuật toán đơn hình hai pha như sau:

Pha 1: Tìm nghiệm tối ưu của bài toán

$\displaystyle \min \{1^Ts:Ax+s= b,x,s\geq 0\}~~(P_2)$

với nghiệm cơ sở chấp nhận được ban đầu $\displaystyle \left[\begin{array}{c}x\\s\end{array}\right]=\left[\begin{array}{c}0\\b\end{array}\right]$ .

Nếu giá trị tối ưu của $\displaystyle (P_2)$ dương, dừng và kết luận bài toán gốc không thỏa được.
Nếu giá trị tối ưu của bằng , với mỗi chỉ số nằm trong bộ chỉ số cơ sở (nghĩa là biến cơ sở này nằm trong ), tìm chỉ số sao cho vị trí trong bảng đơn hình khác 0.
- Nếu không tồn tại $\displaystyle k$ như vậy (toàn bộ dòng $\displaystyle p+1$ bằng 0) thì loại bỏ ràng buộc thứ $\displaystyle p$ và biến cơ sở $\displaystyle B(p)$ khỏi bộ chỉ số cơ sở.
- Nếu tìm được $\displaystyle k$ như vậy, dùng các phép biến đổi dòng để biến cột này thành cột toàn $\displaystyle 0$ và chỉ có duy nhất một số $\displaystyle 1$ ở hàng $\displaystyle p+1$ . Thay $\displaystyle B(p)=k$ .
- Lặp lại với tất cả các chỉ số $\displaystyle B(p)>n$ .

Pha 2: Quay lại giải bài toán gốc $\displaystyle (P_1)$ với nghiệm cơ sở chấp nhận được khởi tạo từ pha 1.

Nhận xét:

Thuật toán 2 pha trên giải quyết hầu hết các trường hợp có thể xảy ra trong phương pháp đơn hình (kể cả khi các ràng buộc phụ thuộc tuyến tính hoặc các ràng buộc tạo nên tập nghiệm rỗng).
Tuy nhiên, thuật toán 2 pha có thể bị khởi tạo với nghiệm cơ sở bị suy biến, dẫn đến thuật toán có thể bị lặp vô hạn.
Bằng các phương pháp tránh vòng lặp vô hạn ở bài sau, thuật toán 2 pha là thuật toán giải bài toán QHTT đầy đủ, nghĩa là nó luôn dừng (trong bất cứ trường hợp nào) và chỉ ra nghiệm tối ưu hoặc thông báo bài toán không có nghiệm.
Nếu các ràng buộc chứa cả ràng buộc đẳng thức và bất đẳng thức, ta kết hợp cả hai phương pháp trên để khởi tạo nghiệm cơ sở.

Bài viết này được đăng vào Tháng Hai 27, 2008 lúc 10:01 sáng và tập tin được lưu ở Quy hoạch tuyến tính. Tagged: hai pha, khởi tạo, nghiệm cơ sở, phương pháp đơn hình, ràng buộc. 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.

Để lại hồi âm

« Phương pháp đơn hình (Simplex method) (5) – Một số ví dụ

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

	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

Phương pháp đơn hình (Simplex method) (6) – Khởi tạo thuật toán đơn hình, thuật toán hai pha

Để lại hồi âm