Phương pháp đơn hình (Simplex method) (4) – Dạng bảng của thuật toán « 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) (4) – Dạng bảng của thuật toán

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

Ta đã thấy, trong phương pháp đơn hình, những giá trị cần tính toán là

$\displaystyle I=\{B(1),\ldots,B(m)\}$ : bộ chỉ số của các cột cơ sở tạo nên ma trận cơ sở $\displaystyle B$ .
$\displaystyle x_B=\left[\begin{array}{rrr}x_{B(1)}&\ldots&x_{B(m)}\end{array}\right]^T$ : giá trị các biến tương ứng với ma trận cơ sở. Lưu ý là $\displaystyle x_j= 0,\forall j\neq I$ .
$\displaystyle \bar{c}^T=c^T-c_B^TB^{-1}A$ : véctơ chứa giá trị thay đổi trên các hướng.
$\displaystyle d_B=-B^{-1}A_k$ : hướng chấp nhận được thứ $\displaystyle k$ nào đó mà $\displaystyle \bar{c}_k<0$ .
$\displaystyle c^Tx=c_B^Tx_B$ : giá trị hàm mục tiêu.

Thuật toán đơn hình ở dạng bảng (full tableau) quản lý một bảng chứa tất cả các thông tin trên. Tại mỗi bước lặp, thuật toán cập nhật lại bảng này khi $\displaystyle x$ và ma trận cơ sở $\displaystyle B$ thay đổi. Bảng này như sau

$\displaystyle \left[\begin{array}{cc}-c_B^Tx_B&\bar{c}\\x_B&B^{-1}A\end{array}\right]=\left[\begin{array}{cccc}-c_B^Tx_B&c_1-c_B^TB^{-1}A_1&\ldots&c_n-c_B^TB^{-1}A_n\\ x_{B(1)}&\vdots&&\vdots\\ \vdots&B^{-1}A_1&\ldots&B^{-1}A_n\\ x_{B(m)}&\vdots&&\vdots\end{array}\right]$

Giả sử $\displaystyle k$ là cột mà $\displaystyle \bar{c}_k=c_k-c_B^TB^{-1}A_k<0$ . Ta có cột thứ $\displaystyle k+1$ của bảng là

$\displaystyle \left[\begin{array}{c}\bar{c}_k\\B^{-1}A_k\end{array}\right]=\left[\begin{array}{c}\bar{c}_k\\u\end{array}\right]=\left[\begin{array}{c}c_k-c_B^TB^{-1}A_k\\u_1\\\vdots\\u_m\end{array}\right]$

Giả sử $\displaystyle p$ là chỉ số mà

$\displaystyle u_p=-d_{B(p)}>0$ và $\displaystyle \frac{x_{B(p)}}{|d_{B(p)}|}=\frac{x_{B(p)}}{u_p}=\min_{u_i>0} \frac{x_{B(i)}}{u_i}=\theta^*$

Cập nhật $\displaystyle I=\{B(1),\ldots,B(m)\}$ : ta thay thế $\displaystyle B(p)=k$ .

Cập nhật $\displaystyle B^{-1}A_j, j=1,\ldots,n$ : Ta biết $\displaystyle {B^*}^{-1}=QB^{-1}$ nên $\displaystyle {B^*}^{-1}A_j=QB^{-1}A_j$ với $\displaystyle Q$ là ma trận biến đổi dòng sao cho $\displaystyle Qu=e_p$ với $\displaystyle u=B^{-1}A_k$ .

Cập nhật $\displaystyle x_B$ : Ta có $\displaystyle x_{B^*}={B^*}^{-1}b=QB^{-1}b=Qx_B$ . Tức là cập nhật $\displaystyle x_B$ cũng giống như cập nhật các cột $\displaystyle B^{-1}A_j$ .

Cập nhật $\displaystyle \bar{c}_j$ : Ta có

$\displaystyle \bar{c}_j=c_j-c_B^Tv$ với $\displaystyle v=B^{-1}A_j$ .

$\displaystyle \bar{c}_j^*=c_j-c_{B^*}^Tv^*$ với $\displaystyle v^*={B^*}^{-1}A_j=Qv$ .

Trong đó

$\displaystyle c_B^T=\left[\begin{array}{ccccc}c_{B(1)}&\ldots&c_{B(p)}&\ldots&c_{B(m)}\end{array}\right]$ , $v=\left[\begin{array}{ccccc}v_1&\ldots&v_p&\ldots&v_m\end{array}\right]^T$

$\displaystyle c_{B^*}^T=\left[\begin{array}{ccccc}c_{B(1)}&\ldots&c_k&\ldots&c_{B(m)}\end{array}\right]$ , $v^*=\left[\begin{array}{ccccc}v_1-\frac{u_1}{u_p}v_p &\ldots&\frac{v_p}{u_p}&\ldots&v_m-\frac{u_m}{u_p}v_p\end{array}\right]^T$

Để ý là $\displaystyle \left[\begin{array}{c}\bar{c}_j\\v\end{array}\right]$ và $\displaystyle \left[\begin{array}{c}\bar{c}_k\\u\end{array}\right]$ là cột thứ $\displaystyle j+1$ và $\displaystyle k+1$ của bảng cũ, $\displaystyle \left[\begin{array}{c}\bar{c}_j^*\\v^*\end{array}\right]$ là cột thứ $\displaystyle j+1$ của bảng mới.

Như vậy

$\displaystyle c_{B^*}^Tv^*=\sum_{i\neq p}^m c_{B(i)}(v_i-\frac{u_i}{u_p}v_p) + c_k\frac{v_p}{u_p}$

$\displaystyle =\sum_{i=1}^m c_{B(i)}v_i-\frac{v_p}{u_p}\sum_{i=1}^m c_{B(i)}u_i+ c_k\frac{v_p}{u_p}$

$\displaystyle =c_B^Tv+v_p\frac{c_k-c_B^Tu}{u_p}=c_B^Tv+v_p \frac{\bar{c}_k}{u_p}$

Suy ra

$\displaystyle \bar{c}_j^*=c_j-c_{B^*}^Tv^*=c_j-c_B^Tv-v_p \frac{\bar{c}_k}{u_p}=\bar{c_j}-v_p \frac{\bar{c}_k}{u_p}$

Đặc biệt $\displaystyle \bar{c}_k^*=\bar{c_k}-u_p \frac{\bar{c}_k}{u_p}=0$ , nghĩa là khi chỉ số $\displaystyle k$ được đưa vào bộ chỉ số cơ sở thì $\displaystyle \bar{c}_k=0$ , đây là điều ta đã biết ở bài thứ 2.

Cập nhật $\displaystyle -c_B^Tx_B$ : Ta biết $\displaystyle c_{B^*}^Tx_{B^*}=c_{B^*}^TQx_B$ nên tương tự như trên, ta cũng có

$\displaystyle c_{B^*}^Tx_{B^*}=c_B^Tx_B+x_{B(p)} \frac{\bar{c}_k}{u_p}$ hay

$\displaystyle -c_{B^*}^Tx_{B^*}=-c_B^Tx_B-x_{B(p)} \frac{\bar{c}_k}{u_p}$

Như vậy, dòng đầu tiên của bảng (gồm giá trị hàm mục tiêu và thay đổi trên các hướng) được cập nhật bằng cách cộng với hàng thứ $\displaystyle p+1$ của bảng sau khi nhân với $\displaystyle -\frac{\bar{c}_k}{u_p}$ . Để ý rằng, đây là biến đổi dòng sao cho $\displaystyle \bar{c}_k^*=0$ .

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

Xuất phát từ một nghiệm cơ sở chấp nhận được và bộ chỉ số cơ sở của nó, xây dựng bảng tương ứng của nghiệm này.
$\displaystyle \left[\begin{array}{cc}-c_B^Tx_B&\bar{c}\\x_B&B^{-1}A\end{array}\right]$
Tại mỗi bước lặp, tìm chỉ số $\displaystyle k$ sao cho $\displaystyle \bar{c}_k<0$ (giá trị thứ $\displaystyle k+1$ của dòng đầu tiên) . Nếu không có thì dừng và kết luận $\displaystyle x_B$ là nghiệm tối ưu (các tọa độ khác của $\displaystyle x$ bằng $\displaystyle {0}$ ).
Nếu các giá trị khác trên cột thứ $\displaystyle k+1$ đều không dương ( $\displaystyle u\leq 0$ ) thì dừng và kết luận bài toán QHTT không bị chặn và không có nghiệm (do $\displaystyle u=-d_B\leq 0\Rightarrow d_B\geq 0$ ) .
Ngược lại, chọn chỉ số $\displaystyle p$ sao cho $\displaystyle u_p>0,\frac{x_{B(p)}}{u_p}=\min_{u_i>0}\frac{x_{B(i)}}{u_i}$ ( $\displaystyle x_{B(p)}$ và $\displaystyle u_p$ là giá trị ở hàng $\displaystyle p+1$ cột $\displaystyle 1$ và cột $\displaystyle k+1$ ).
Đưa chỉ số $\displaystyle k$ vào thay thế $\displaystyle B(p)$ trong bộ chỉ số cơ sở.
Thực hiện các phép biến đổi dòng sao cho cột thứ $\displaystyle k+1$ trở thành véctơ toàn $\displaystyle 0$ và chỉ có duy nhất một số $\displaystyle 1$ ở hàng $\displaystyle p+1$ :
+ Nhân dòng thứ $\displaystyle p+1$ với $\displaystyle -\frac{\bar{c}_k}{u_p}$ rồi cộng vào dòng đầu tiên.
+ Nhân dòng thứ $\displaystyle p+1$ với $\displaystyle -\frac{u_i}{u_p}$ rồi cộng vào dòng thứ $\displaystyle i+1$ với $\displaystyle i=1,\ldots,m,i\neq p$ .
+ Chia dòng thứ $\displaystyle p+1$ cho $\displaystyle u_p$
Quay trở lại bước 2.

Bài viết này được đăng vào Tháng Hai 26, 2008 lúc 6:17 chiều và tập tin được lưu ở Quy hoạch tuyến tính. Tagged: biến đổi dòng, dạng bảng, phương pháp đơn hình. 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) (3) – Cải tiến thuật toán

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

	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) (4) – Dạng bảng của thuật toán

Để lại hồi âm