Suy Biến | My Weblog

Trang chủ » Suy Biến » Suy Biến | My Weblog

Có thể bạn quan tâm

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.

Từ khóa » Suy Biến