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

Learn & Enjoy …

Phương pháp đơn hình (Simplex method) (2) – Hướng làm giảm hàm mục tiêu, điều kiện tối ưu, phương pháp đơn hình

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

Định nghĩa (hướng chấp nhận được): Xét một điểm x thuộc đa diện lồi P. Ta gọi hướng d\in \mathbb{R}^n hướng chấp nhận được (feasible direction) của P tại x nếu tồn tại \theta>0 sao cho x+\theta d\in P.

Nhận xét: Trong phương pháp đơn hình, thay vì chọn một nghiệm cơ sở bất kì, ta sẽ đi từ nghiệm cơ sở chấp nhận được này đến một nghiệm cơ sở chấp nhận được khác theo một hướng chấp nhận được sao cho hàm mục tiêu sẽ giảm đi.

Nhớ lại rằng, nếu x là một nghiệm cơ sở chấp nhận được của đa diện lồi ở dạng chuẩn tắc P=\{x:Ax=b,x\geq 0\} thì tồn tại một bộ chỉ số I=\{B(1),\ldots,B(m)\} sao cho

  1. Ma trận cơ sở B=\left[\begin{array}{rrr}A_{B(1)}&\ldots&A_{B(m)}\end{array}  \right] khả nghịch.
  2. x_j=0,\forall j\notin I.

Một nghiệm cơ sở chấp nhận được khác phải tương ứng với một bộ chỉ số khác. Như vậy nếu ta xét một chỉ số k\notin I, và chọn một hướng chấp nhận được d sao cho

\forall j\notin I, d_j=\begin{cases}1& j=k\\{0}&j\neq k\end{cases}

thì đi theo hướng này, ta sẽ có

x_k+\theta d_k=x_k+\theta > 0

x_j +\theta d_j = x_j = 0,\forall j\notin I, j\neq k

tức là mọi nghiệm cơ sở chấp nhận được trên hướng này sẽ là nghiệm cơ sở tương ứng với một bộ chỉ số chỉ khác bộ chỉ số cũ ở duy nhất một chỉ số. Bây giờ ta sẽ tính các giá trị d_i, i\in I sao cho d là hướng chấp nhận được. Ta gọi đây là hướng chấp nhận được tương ứng với biến x_k (gọi tắt là hướng chấp nhận được thứ k).

Định lý (hướng chấp nhận được thứ k): Xét nghiệm cơ sở chấp nhận được x của đa diện lồi dạng chuẩn tắc P=\{x:Ax=b,x\geq 0\} và bộ chỉ số cơ sở I=\{B(1),\ldots,B(m)\} tương ứng của x. Hướng chấp nhận được thứ k\notin I là hướng d=\left[\begin{array}{rrr}d_1&\ldots&d_n\end{array}  \right]^T , trong đó

d_B=-B^{-1}A_k

với d_B=\left[ \begin{array}{rrr}d_{B(1)}&\ldots&d_{B(m)}\end{array}  \right]^T

\forall j\notin I, d_j=\begin{cases}1& j=k\\{0}&j\neq k\end{cases}

Chứng minh: Để x+\theta d\in P với \theta>0 nào đó, ta có

A(x+\theta d)=Ax=b

\Rightarrow 0=Ad=Bd_B+A_k

d_j=0,\forall j\notin I, j\neq k. Suy ra

d_B=-B^{-1}A_k

Nhận xét: Với hướng chấp nhận được thứ k, hàm mục tiêu bị thay đổi như sau

c^T(x+\theta d)-c^Tx=\theta c^Td=\theta(c_B^Td_B+c_k)=\theta(c_k-c_B^TB^{-1}A_k)

với c_B=\left[ \begin{array}{rrr}c_{B(1)}&\ldots&c_{B(m)}\end{array}  \right]^T. Mục tiêu của ta là phải chọn k sao cho c_k-c_B^TB^{-1}A_k<0 thì hàm mục tiêu sẽ giảm trên hướng chấp nhận được thứ k.

Định nghĩa (thay đổi ở hướng chấp nhận được thứ k): Xét nghiệm cơ sở chấp nhận được x của đa diện lồi dạng chuẩn tắc P=\{x:Ax=b,x\geq 0\} và ma trận cơ sở tương ứng B của x, thay đổi ở hướng chấp nhận được thứ k là đại lượng

\bar{c}_k=c_k-c_B^TB^{-1}A_k

Véctơ \bar{c}=\left[ \begin{array}{rrr}\bar{c}_1&\ldots&\bar{c}_n\end{array}  \right]^T chứa giá trị thay đổi ở tất cả các hướng

\bar{c}^T=c^T-c_B^TB^{-1}A

Nhận xét: Nếu \bar{c}_B=\left[ \begin{array}{rrr}\bar{c}_{B(1)}&\ldots&\bar{c}_{B(m)}\end{array}  \right]^T thì

\bar{c}_B^T=c_B^T-c_B^TB^{-1}B=c_B^T-c_B^T=0

Tức là với mọi chỉ số i thuộc vào bộ chỉ số cơ sở của x thì không có thay đổi trên hướng i.

Định lý (điều kiện tối ưu của nghiệm cơ sở chấp nhận được): Nếu x là nghiệm cơ sở chấp nhận được của đa diện lồi dạng chuẩn tắc P=\{x:Ax=b,x\geq 0\}\bar{c} là véc tơ chứa giá trị thay đổi trên các hướng thì

  1. Nếu \bar{c}\geq 0 thì x là nghiệm tối ưu của bài toán QHTT.
  2. Nếu x là nghiệm tối ưu và x_B>0 thì \bar{c}\geq 0. Trong đó x_B=\left[ \begin{array}{rrr}x_{B(1)}&\ldots&x_{B(m)}\end{array}  \right]^T.

Lưu ý: Khi x_B>0 ta còn gọi xnghiệm cơ sở không suy biến (nondegenerate basic solution).

Chứng minh (1): Xét một điểm y\in P, ta có y=x+d, suy ra

0=Ad=Bd_B+\displaystyle \sum_{j\notin I}d_jA_j \Rightarrow d_B=-\displaystyle \sum_{j\notin I}d_jB^{-1}A_j

c^Td=c_B^Td_B+\displaystyle \sum_{j\notin I}c_jd_j = \sum_{j\notin I}d_j (c_j-c_B^TB^{-1}A_j)=\sum_{j\notin I}d_j \bar{c}_j\geq 0

d_j=y_j-x_j=y_j\geq 0,\forall j\notin I\bar{c}_j\geq 0 theo giả thiết. Suy ra c^Ty\geq c^Tx, \forall y\in P.

Chứng minh (2): Giả sử ngược lại tồn tại k\notin I sao cho \bar{c}_k<0. Xét hướng d là hướng chấp nhận được thứ k. Do d_k=1d_j=0,\forall j\notin I, j\neq k nên nếu đi theo hướng d, các tọa độ x_j+\theta d_j\geq 0,\forall j\notin I. Mặt khác, do x_B>0 nên ta có thể chọn \theta đủ nhỏ sao cho x_B+\theta d_B\geq 0. Như vậy, đi theo hướng d ta vẫn nằm trong P nhưng lại giảm được giá trị hàm mục tiêu do \theta\bar{c}_k<0, mâu thuẫn vì x là nghiệm tối ưu.

Nhận xét:

  1. Định lý cung cấp một điều kiện có thể kiểm tra nghiệm tối ưu bằng tính toán (tính véctơ \bar{c}).
  2. Định lý vẫn để ngỏ khả năng x có thể là nghiệm tối ưu khi xnghiệm cơ sở suy biến\bar{c}\ngeq 0.
  3. Nếu x là nghiệm cơ sở không suy biến và \bar{c}\ngeq 0, ta có thể chọn hướng d chấp nhận được thứ k nào đó sao cho \bar{c}_k<0. Xuất phát từ x đi theo hướng này ta sẽ giảm được giá trị của hàm mục tiêu.
  4. Nếu d\geq 0 thì ta có thể cho \theta \rightarrow \infty mà vẫn có x+\theta d\in P, nghĩa là hàm mục tiêu không bị chặn.
  5. Nếu tồn tại i sao cho d_{B(i)}<0 (lưu ý: d_j\geq 0,\forall j\notin I), thì giá trị của \theta lớn nhất có thể được là
    \theta^*=\displaystyle \min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|}
  6. Nếu ta có x_B=B^{-1}b\geq 0\bar{c}^T=c^T-c_B^TB^{-1}A\geq 0, ta có nghiệm cơ sở x là nghiệm tối ưu và ta nói Bma trận cơ sở tối ưu (optimal basis).
  7. Định lý sau đây còn cho biết nếu chọn giá trị của \theta lớn nhất có thể được thì ta sẽ được một nghiệm cơ sở chấp nhận được tương ứng với ma trận cơ sở khác.

Định lý: Nếu x là nghiệm cơ sở chấp nhận được của đa diện lồi dạng chuẩn tắc P=\{x:Ax=b,x\geq 0\}, hướng d\ngeq 0 là hướng chấp nhận được thứ k

\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)}|}

thì x^*=x+\theta^* d là nghiệm cơ sở chấp nhận được tương ứng với bộ chỉ số B(1),\ldots,B(p-1),k,B(p+1),\ldots,B(m). Nghĩa là trong hệ cơ sở mới, ta thay A_{B(p)} bằng A_k.

Chứng minh: Rõ ràng x^*_j=x_j+\theta^* d_j=0,\forall j\notin I, j\neq k, hơn nữa do d_{B(p)}<0\theta^* =\frac{x_{B(p)}}{|d_{B(p)}|} nên x^*_{B(p)} = x_{B(p)}+\theta^* d_{B(p)} = 0. Như vậy x^*_j=0,\forall j\neq B(1),\ldots,B(p-1),k,B(p+1),\ldots,B(m). Ta chỉ còn cần chứng minh ma trận cơ sở mới

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]

ma trận khả nghịch. Xét ma trận

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]

trong đó e_i là véc tơ cơ sở thứ i trong hệ tọa độ Đềcác của \mathbb{R}^md_B=-B^{-1}A_k . Dễ thấy \det(B^{-1}B^*)=-d_{B(p)}\neq 0 do đó det(B^*)\neq 0 hay B^* khả nghịch.

Phương pháp đơn hình (simplex method):

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

    B=\left[ \begin{array}{rrr}A_{B(1)}&\ldots&A_{B(m)}\end{array}\right] 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)}|}

    Cặp chỉ số \displaystyle (p,k) còn gọi là chốt (nó chỉ ra cột ra khỏi ma trận cơ sở và cột thay thế).
  7. Thay x bằng nghiệm cơ sở chấp nhận được x+\theta^* d và ma trận cơ sở mới
    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]

    và quay lại bước 1.

Định lý (tính đúng đắn của phương pháp đơn hình): Nếu tất cả các nghiệm cơ sở chấp nhận được của bài toán QHTT

\displaystyle\mathrm{Opt}(P)=\min_x\{c^Tx|Ax= b,x\geq 0\}

đều là nghiệm cơ sở không suy biến thì phương pháp đơn hình luôn dừng và khi đó có hai khả năng xảy ra:

  1. Ta có nghiệm tối ưu x và ma trận cơ sở tối ưu B.
  2. Ta tìm được véctơ d\geq 0 sao cho Ad=0c^Td<0 và kết luận bài toán QHTT không bị chặn nên không có nghiệm tối ưu.

Chứng minh: Vì tất cả các nghiệm cơ sở chấp nhận được đều không suy biến nên ta luôn có

\theta^*=\displaystyle \min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|}>0

Nghĩa là sau mỗi bước của thuật toán, giá trị hàm mục tiêu bị thay đổi một lượng bằng

\theta c^Td=\theta (c_k-c_B^TB^{-1}A_k)=\theta \bar{c}_k<0

Tức là không có nghiệm cơ sở chấp nhận được nào bị lặp lại, hơn nữa, số lượng nghiệm cơ sở chấp nhận được là hữu hạn nên thuật toán phải dừng. Nếu thuật toán dừng ở bước 3 thì ta có nghiệm tối ưu theo định lý về điều kiện tối ưu của nghiệm cơ sở ở trên. Nếu thuật toán dừng ở bước 5, ta có d\geq 0, Ad=0c^Td=c_k-c_B^TB^{-1}A_k=\bar{c}_k<0 do đó bài toán QHTT không bị chặn và không có nghiệm tối ưu (từ x đi theo hướng d thì c^T(x+\theta d)\rightarrow -\infty.

Nhận xét:

  1. Định lý trên cho thấy tính dừng của phương pháp đơn hình khi mọi nghiệm cơ sở chấp nhận được của \displaystyle P đều không suy biến. Trong trường hợp tồn tại nghiệm cơ sở bị suy biến, phương pháp đơn hình có thể bị lặp vô hạn (mặc dù khả năng này rất hiếm khi xảy ra). Trong các bài sau, ta sẽ tìm hiểu hiện tượng này và cách khắc phục.
  2. Lựa chọn chỉ số \displaystyle k\displaystyle p là hoàn toàn tự do miễn là
    \displaystyle c_k < 0, d_{B(p)}<0\displaystyle \frac{x_{B(p)}}{|d_{B(p)}|} =\theta^*=\min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|}

    Ta sẽ thấy nếu lựa chọn \displaystyle k\displaystyle p hợp lý sẽ tránh được hiện tượng lặp vô hạn khi có nghiệm cơ sở suy biến.
  3. Tại mỗi bước lặp ta cần tính toán nghịch đảo của \displaystyle B, ta sẽ thấy cùng với việc thay đổi ma trận cơ sở, ta có thể tính nghịch đảo của ma trận cơ sở mới rất hiệu quả bởi ma trận cơ sở mới chỉ khác ma trận cơ sở cũ ở duy nhất 1 cột.

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: