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 « CS Study Fun

Tháng Hai 2008
T2	T3	T4	T5	T6	T7	CN
		Tháng 3 »
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29

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

Đăng bởi tqlong 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$ là 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

Ma trận cơ sở $B=\left[\begin{array}{rrr}A_{B(1)}&\ldots&A_{B(m)}\end{array} \right]$ khả nghịch.
$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ì

Nếu $\bar{c}\geq 0$ thì $x$ là nghiệm tối ưu của bài toán QHTT.
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 (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$

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:

Đị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}$ ).
Đị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$ .
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.
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.
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)}|}$
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 (optimal basis).
Đị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 (simplex method):

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.
Tính véctơ $\bar{c}^T=c^T-c_B^TB^{-1}A$ chứa giá trị thay đổi ở các hướng.
Nếu $\bar{c}\geq 0$ , dừng và kết luận $x$ là nghiệm tối ưu.
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$ .
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.
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ế).
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:

Ta có nghiệm tối ưu $x$ và ma trận cơ sở tối ưu $B$ .
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:

Đị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.
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.
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.

Bài viết này được đăng vào Tháng Hai 25, 2008 lúc 12:24 sáng và tập tin được lưu ở Quy hoạch tuyến tính. Tagged: dạng chuẩn tắc, hướng chấp nhận được, nghiệm cơ sở, phương pháp đơn hình, suy biến, điều kiện tối ưu. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể Để lại lời nhắn, hoặc trackback từ trang của bạn.

Để lại hồi âm

« Phương pháp đơn hình (Simplex method) (1) – Bài toán QHTT, dạng chuẩn tắc và các định lý cơ bản

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

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

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

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

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

Để lại hồi âm