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

Learn & Enjoy …

Phương pháp đơn hình (Simplex method) (3) – Cải tiến thuật toán

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

Trong bài này, ta sẽ xem xét một cải tiến của phương pháp đơn hình ở bài trước.

Tính ma trận nghịch đảo \displaystyle {B^*}^{-1}:

Ta có

B^*=\left[ \begin{array}{rrrrrrr}A_{B(1)}&\ldots&A_B{(p-1)}&A_k&A_{B(p+1)}&\ldots&A_{B(m)}\end{array}\right]

B^{-1}B^*=B^{-1}\left[\begin{array}{rrrrrrr}A_{B(1)}&\ldots&A_B{(p-1)}& A_k&A_{B(p+1)}&\ldots&A_{B(m)}\end{array}\right]

=\left[\begin{array}{rrrrrrr}e_1&\ldots&e_{p-1}& -d_B&e_{p+1}&\ldots&e_{m}\end{array}\right]

=\left[\begin{array}{rrrrrrr}e_1&\ldots&e_{p-1}& u_B&e_{p+1}&\ldots&e_{m}\end{array}\right]

Như vậy \displaystyle B^{-1}B^* chỉ khác ma trận đơn vị \displaystyle I ở cột thứ \displaystyle p, thay vì \displaystyle e_p ta có \displaystyle -d_B. Để cho tiện, đặt \displaystyle u_B=-d_B. Giả sử \displaystyle u_B=\left[\begin{array}{rrrrrrr}u_1&\ldots&u_{p-1}& u_p&u_{p+1}&\ldots&u_m\end{array}\right]^T , lưu ý rằng \displaystyle u_p=-d_{B(p)}>0.

Nếu ta dùng biến đổi ma trận \displaystyle B^{-1}B^* bằng các phép biến đổi hàng sau

  1. Chia hàng thứ \displaystyle p cho \displaystyle u_p.
  2. Nhân hàng thứ \displaystyle p với \displaystyle -u_i rồi cộng vào hàng thứ \displaystyle i

thì ta sẽ biến ma trận \displaystyle B^{-1}B^* thành ma trận đơn vị. Các phép biến đổi này tương đương với việc nhân ma trận \displaystyle B^{-1}B^* với ma trận \displaystyle Q sau đây:

\displaystyle Q=\left[\begin{array}{rrrrr}1&\ldots&-\frac{u_1}{u_p}&\ldots&{0}\\ \vdots&\ddots&\vdots&\ddots&\vdots\\{0}&\ldots&\frac{1}{u_p}&\ldots&{0}\\ \vdots&\ddots&\vdots&\ddots&\vdots\\ {0}&\ldots&-\frac{u_m}{u_p}&\ldots&{1} \end{array} \right]

trong đó \displaystyle Q chỉ khác ma trận đơn vị ở duy nhất cột thứ \displaystyle p. Như vậy, ta có

\displaystyle QB^{-1}B^*=I \Rightarrow QB^{-1}={B^*}^{-1}.

Hay nói cách khác, nếu ta áp dụng các biến đổi hàng trên đối với ma trận \displaystyle B^{-1} thì ta sẽ được\displaystyle {B^*}^{-1}.

Với nhận xét này, ta có phương pháp đơn hình cải tiến sau:

  1. Xuất phát từ một nghiệm cơ sở chấp nhận được và nghịch đảo của ma trận cơ sở

    B^{-1}=\left[ \begin{array}{rrr}A_{B(1)}&\ldots&A_{B(m)}\end{array}\right]^{-1}
    tương ứng.
  2. Tính véctơ \bar{c}^T=c^T-c_B^TB^{-1}A chứa giá trị thay đổi ở các hướng.
  3. Nếu \bar{c}\geq 0, dừng và kết luận x là nghiệm tối ưu.
  4. Nếu \bar{c}\ngeq 0, chọn một hướng d là hướng chấp nhận được thứ k nào đó mà \bar{c}_k<0, tức là d_B=-B^{-1}A_k, d_k=1, d_j=0,\forall j\notin I, j\neq k.
  5. Nếu d\geq 0, dừng và kết luận bài toán QHTT không bị chặn và không có nghiệm.
  6. Nếu d\ngeq 0, chọn
    \theta^*=\displaystyle \min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|}
    p=\displaystyle\arg\min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|}
  7. Thay x bằng nghiệm cơ sở chấp nhận được x+\theta^* d và nghịch đảo của ma trận cơ sở mới
    {B^*}^{-1}=QB^{-1}

    và quay lại bước 1.
    Lưu ý: ta không thực sự làm phép nhân \displaystyle QB^{-1} mà áp dụng các phép biến đổi dòng như mô tả ở trên sử dụng véctơ \displaystyle u_B=-d_B.

Nhận xét:

  1. Bằng cải tiến này, thuật toán đơn hình không cần phải thực sự làm phép tính nghịch đảo của \displaystyle B^{-1} mà chỉ sử dụng các phép biến đổi dòng cơ bản để tính ra ma trận nghịch đảo này.
  2. Ta sẽ thấy, ở bài sau, cả véctơ \displaystyle \bar{c}^*=(c^T-c_{B^*}^T{B^*}^{-1}A)^T ở lần lặp sau cũng có thể tính được từ véctơ \displaystyle \bar{c} ở lần lặp trước. Vì thế, ta có thể không lưu ma trận \displaystyle B^{-1} mà lưu các ma trận \displaystyle Q của các lần lặp (lưu ý, ma trận này chỉ khác ma trận đơn vị ở duy nhất 1 cột, là một dạng ma trận rất thưa khi số ràng buộc \displaystyle m lớn).
  3. Tuy nhiên, trong thực hành, khi thuật toán chạy được một số vòng lặp nhất định, người ta lại tính toán lại nghịch đảo của ma trận cơ sở bằng phương pháp truyền thống (biến đổi Gauss) để tránh sai số khi tính toán.
  4. Do \displaystyle {B^*}^{-1}=QB^{-1} nên \displaystyle d_B^*=-{B^*}^{-1}A_k=-QB^{-1}A_k=Qd_B nghĩa là véctơ hướng \displaystyle d^* cũng có thể được tính bằng cách tương tự như tính \displaystyle {B^*}^{-1}.

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: