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

Learn & Enjoy …

Phương pháp đơn hình (Simplex method) (4) – Dạng bảng của thuật toán

Posted by Trần Quốc Long 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à

  1. \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.
  2. \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.
  3. \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.
  4. \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.
  5. \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\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]\displaystyle \left[\begin{array}{c}\bar{c}_k\\u\end{array}\right] là cột thứ \displaystyle j+1\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:

  1. 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]
  2. 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}).
  3. 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) .
  4. 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)}\displaystyle u_p là giá trị ở hàng \displaystyle p+1 cột \displaystyle 1 và cột \displaystyle k+1).
  5. Đưa chỉ số \displaystyle k vào thay thế \displaystyle B(p) trong bộ chỉ số cơ sở.
  6. 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.

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: