Suy biến trong toán học là gì?

By
admin
-
0
5302
Suy biến trong toán học là gì?

Mục lục bài viết

1. Suy biến là gì?

Suy biến là Hao hụt đi trong quá trình chuyển hoá: Năng lượng suy biến theo nguyên lí Carnot.

2. Suy biến trong toán học?

Trở ngại cuối cùng trong thuật toán đơn hình là tình huống lặp vô hạn khi gặp phải nghiệm cơ sở bị suy biến. Có hai nguyên nhân dẫn đến có thể xảy ra lặp vô hạn khi tiến hành thuật toán đơn hình:

  1. Khi tính toán \displaystyle \theta^*, có hai giá trị \displaystyle p,q mà
    \displaystyle \frac{x_{B(p)}}{|d_{B(p)}|}=\frac{x_{B(q)}}{|d_{B(q)}|}=\theta^*

    nên khi cập nhật, ta có \displaystyle x_{B*(q)}=x_{B(q)}-x_{B(p)}\frac{|d_{B(q)}|}{|d_{B(p)}|}=0 . Tức là ta đi đến một nghiệm cơ sở bị suy biến.

  2. Thuật toán đi đến một nghiệm cơ sở bị suy biến (có it nhất một biến cơ sở bằng 0) và
    \displaystyle \theta^*=\frac{x_{B(p)}}{|d_{B(p)}|}=\min_{i,d_{B(i)}<0}\frac{x_{B(i)}}{|d_{B(i)}|} = 0

    do \displaystyle x_{B(p)}=0. Như vậy, nghiệm cơ sở không thay đổi mà chỉ có hệ cơ sở thay đổi. Có thể xảy ra trường hợp các véctơ cơ sở bị tráo đổi theo cách vòng tròn mà nghiệm cơ sở không hề thay đổi, dẫn tới tình huống lặp vô hạn (mặc dù khả năng này rất hiếm khi xảy ra).

Để ý rằng, trong phương pháp đơn hình, ta có quyền chọn cặp chỉ số chốt \displaystyle (p,k) miễn là

\displaystyle \bar{c}_k<0, u=B^{-1}A_k, u_p>0, \frac{x_{B(p)}}{u_p}=\min_{i,u_i>0}\frac{x_{B(i)}}{u_i} =\theta^*

Người ta chứng minh được rằng, nếu chọn \displaystyle (p,k) theo những luật nhất định thì sẽ tránh được tình huống lặp vô hạn. Trong bài này, ta sẽ xem xét hai phương pháp đơn giản để khử vòng lặp vô hạn, đó là luật từ điển và luật Bland.

Định nghĩa (thứ tự từ điển): Ta nói véctơ \displaystyle u\in \mathbb{R}^n có thứ tự từ điển nhỏ hơn véctơ \displaystyle v\in \mathbb{R}^n, kí hiệu là \displaystyle u\lessdot v hay v\gtrdot u nếu

\displaystyle i=\min\{i:u_i\neq v_i\}, u_i<v_i

nghĩa là ở chỉ số đầu tiên mà \displaystyle u_i\neq v_i thì \displaystyle u_i<v_i

Lưu ý: định nghĩa có thể mở rộng cho hai véc tơ không có cùng số chiều, nhưng trong bài này ta chỉ quan tâm đến các véctơ có cùng số chiều.

Định nghĩa (thứ tự từ điển dương): Ta nói véctơ \displaystyle u\in \mathbb{R}^n có thứ tự từ điển dương (gọi tắt là thứ tự dương) nếu \displaystyle 0\lessdot u hay u\gtrdot 0.

Định nghĩa (luật từ điển): Luật từ điển là cách chọn chỉ số dòng \displaystyle p tại mỗi bước lặp sao cho dòng được chọn có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt \displaystyle u_p.

Định lý (tính dừng của luật từ điển): Nếu trong bước chọn dòng \displaystyle p, ta luôn chọn dòng có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt \displaystyle u_p thì

  1. Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, các dòng này vẫn có thứ tự dương.
  2. Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, thứ tự từ vựng của dòng đầu tiên tăng.
  3. Nếu các dòng của bảng ban đầu (trừ dòng đầu tiên) có thứ tự dương thì thuật toán đơn hình luôn dừng.

Chứng minh (1): Với những dòng mà \displaystyle u_i\leq 0 thì \displaystyle -\frac{u_i}{u_p}\geq 0 nên nhân dòng \displaystyle p với \displaystyle -\frac{u_i}{u_p} rồi cộng vào dòng \displaystyle i ta vẫn có thứ tự dương.

Với những dòng mà \displaystyle u_i>0, \frac{x_{B(i)}}{u_i}>\frac{x_{B(p)}}{u_p} thì \displaystyle x_{B^*(i)}=x_{B(i)}-x_{B(p)}\frac{u_i}{u_p}>0, tức là dòng \displaystyle i vẫn có thứ tự dương vì \displaystyle x_{B^*(i)} là giá trị đầu tiên trong dòng thứ \displaystyle i).

Với những dòng mà \displaystyle u_i>0, \frac{x_{B(i)}}{u_i}=\frac{x_{B(p)}}{u_p} thì sau biến đổi dòng, dòng\displaystyle i vẫn có thứ tự dương vì dòng \displaystyle p chia cho \displaystyle u_p có thứ tự từ điển nhỏ hơn dòng \displaystyle i chia cho \displaystyle u_i. Thật vậy, giả sử cột \displaystyle k là cột đầu tiên mà

\displaystyle \frac{v_i}{u_i}>\frac{v_p}{u_p}

Trong đó \displaystyle v_i, v_p lần lượt là các giá trị ở cột \displaystyle k tại các hàng\displaystyle i, p. Suy ra

\displaystyle v_i^*=v_i-v_p\frac{u_i}{u_p}>0

Vì \displaystyle v_i^* là giá trị đầu tiên khác\displaystyle 0 trên dòng\displaystyle i sau khi biến đổi dòng nên dòng\displaystyle i có thứ tự dương.

Chứng minh (2): vì \displaystyle \bar{c}_k<0 nên\displaystyle -\frac{\bar{c}_k}{u_p} >0. Do vậy, khi nhân dòng thứ \displaystyle p với \displaystyle -\frac{\bar{c}_k}{u_p} rồi cộng vào dòng đầu tiên, thứ tự từ điển của dòng đầu tiên sẽ tăng lên (do dòng \displaystyle p có thứ tự dương).

Chứng minh (3): Do số bảng đơn hình là hữu hạn (bằng số bộ cơ sở có thể có), mà thứ tự từ điển của dòng đầu tiên lại luôn tăng, nên đến lúc nào đó, thuật toán đơn hình phải dừng.

Nhận xét: Để tạo được các dòng có thứ tự dương trong bảng ban đầu, ta có thể đảo chỗ các biến bù lên đầu, như vậy ma trận \displaystyle B^{-1}\widehat{A}=\left[\begin{array}{rr}I&A\end{array}\right], hơn nữa, \displaystyle x_B\geq 0 (cột đầu tiên của bảng) nên tất cả các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương.

Định nghĩa (Luật Bland): Cách lựa chọn cặp chỉ số chốt\displaystyle (p,k) sau đây gọi là luật Bland:

  1. Trong bước chọn cột, chọn chỉ số \displaystyle k nhỏ nhất sao cho\displaystyle \bar{c}_k<0.
  2. Trong bước chọn dòng, chọn chỉ số \displaystyle p nhỏ nhất sao cho\displaystyle \frac{x_{B(p)}}{u_p}=\theta^*.

Định lý (tính dừng của luật Bland): Nếu lựa chọn cặp chỉ số chốt \displaystyle (p,k) theo luật Bland thì thuật toán đơn hình luôn dừng.

Nhãn:luật Bland, luật từ điển, phương pháp đơn hình, suy biến, thứ tự từ điển
Posted in Quy hoạch tuyến tính | Leave a Comment »

Phương pháp đơn hình (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

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  là hướng chấp nhận được 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 và

\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

vì 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\} và \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 x là nghiệm cơ sở không suy biến.

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

vì d_j=y_j-x_j=y_j\geq 0,\forall j\notin I và \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=1 và d_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 x là nghiệm cơ sở suy biến và \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 và \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 B là ma trận cơ sở tối ưu.
  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 và

\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 và \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]

là 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}^m và d_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:

  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 c\geq 0, dừng và kết luận x là nghiệm tối ưu.
  4. Nếu 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=0 và c^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=0 và c^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 và \displaystyle p là hoàn toàn tự do miễn là
    \displaystyle c_k < 0, d_{B(p)}<0 và \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 và \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.

RELATED ARTICLESMORE FROM AUTHOR