Phương pháp đơn hình (Simplex method) (5) – Một số ví dụ « 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) (5) – Một số ví dụ

Đăng bởi tqlong on Tháng Hai 26, 2008

Ví dụ 1: Giải bài toán tối ưu $\displaystyle \min \{x_1-x_2:x_1+x_2\leq 1,x_1,x_2\geq 0\}$

Nhận xét: Đa diện lồi $\displaystyle P=\{x_1+x_2\leq 1,x_1,x_2\geq 0\}\subset \mathbb{R}^2$ có 3 đỉnh là $\displaystyle (0,0),(0,1),(1,0)$ . Như vậy, nghiệm tối ưu của bài toán là $\displaystyle (x_1,x_2)=(0,1)$ . Giá trị tối ưu của hàm mục tiêu là $\displaystyle -1$ .

Giải bằng dạng bảng:

Đưa về dạng chuẩn tắc bằng cách thêm biến $\displaystyle x_3$ :
$\displaystyle \min \{x_1-x_2:x_1+x_2+x_3=1,x_1,x_2,x_3\geq 0\}$

Ta có $\displaystyle c^T=\left[\begin{array}{ccc}1&-1&0\end{array}\right], A=\left[\begin{array}{ccc}1&1&1\end{array}\right],b=1$ .
Dễ thấy $\displaystyle x=\left[\begin{array}{ccc}0&0&1\end{array}\right]^T$ là nghiệm cơ sở chấp nhận được và $\displaystyle B(1)=3$ . Ta có $\displaystyle c_B=0$ nên $\displaystyle -c_B^Tx_B=0,\bar{c}^T=c=\left[\begin{array}{ccc}1&-1&0\end{array}\right]$ . Vì $\displaystyle B=1$ nên $\displaystyle B^{-1}A=A=\left[\begin{array}{ccc}1&1&1\end{array}\right]$ . Vậy ta có bảng sau
$\displaystyle \left[\begin{array}{ccccc}0&\vdots&1&-1&0\\\ldots&.&\ldots&\ldots&\ldots\\x_3=1&\vdots&1&1^*&1\end{array}\right]$
Lần lặp 1: $\displaystyle \bar{c}_2=-1<0$ nên $\displaystyle k=2$ . $\displaystyle u_1=1>0$ nên $\displaystyle p=1$ . Ta đánh dấu sao trên phần tử ở vị trí $\displaystyle (p+1,k+1)=(2,3)$ . Ta sẽ biến đổi bảng sao cho cột $\displaystyle k+1=3$ gồm toàn số $\displaystyle 0$ và chỉ có một số $\displaystyle 1$ ở vị trí này bằng cách cộng hàng số $\displaystyle 2$ vào hàng số $\displaystyle 1$ và được bảng sau
$\displaystyle \left[\begin{array}{ccccc}1&\vdots&2&0&1\\\ldots&.&\ldots&\ldots&\ldots\\x_2=1&\vdots&1&1&1\end{array}\right]$

Để ý rằng, ta đã thay $\displaystyle x_3$ bằng $\displaystyle x_2$ trong hệ cơ sở mới.
Bảng này có $\displaystyle \bar{c}\geq 0$ nên $\displaystyle x=(0,1,0)$ là nghiệm tối ưu.
Nếu ta bắt đầu từ nghiệm cơ sở $\displaystyle x=\left[\begin{array}{ccc}1&0&0\end{array}\right]^T$ thì $\displaystyle c_B=1,B=1$ , suy ra $\displaystyle -c_B^Tx_B=-1$ , $B^{-1}A=A=\left[\begin{array}{ccc}1&1&1\end{array}\right]$ , $\bar{c}^T=c^T-c_B^TB^{-1}A=\left[\begin{array}{ccc}0&-2&-1\end{array}\right]$ . Vậy ta có bảng
$\displaystyle \left[\begin{array}{ccccc}-1&\vdots&0&-2&-1\\ \ldots&.&\ldots&\ldots&\ldots\\x_1=1&\vdots&1&1^*&1^*\end{array}\right]$
Có 2 lựa chọn:
+ Nếu ta chọn $\displaystyle k=3,p=1$ thì ta sẽ được nghiệm cơ sở $\displaystyle x=(0,0,1)$ và sẽ quay về bước lặp bên trên.
+ Nếu ta chọn $\displaystyle k=2,p=1$ , ta phải biến đổi bảng bằng cách nhân hàng thứ $\displaystyle p+1=2$ với $\displaystyle 2$ rồi cộng vào hàng thứ $\displaystyle 1$ , ta được bảng

$\displaystyle \left[\begin{array}{ccccc}1&\vdots&2&0&1\\\ldots&.&\ldots&\ldots&\ldots\\x_2=1&\vdots&1&1&1\end{array}\right]$

Bảng này tương ứng với nghiệm tối ưu $\displaystyle x=(0,1,0)$ .

Ví dụ 2: Giải bài toán tối ưu $\displaystyle \min\{x_1-x_2: x_1,x_2\geq 0\}$ .

Nhận xét: Vì bất cứ số thực nào cũng có thể biểu diễn dưới dạng hiệu của 2 số không âm nên ta có tập $\displaystyle \{x_1-x_2: x_1,x_2\geq 0\}=\mathbb{R}$ . Nghĩa là bài toán tối ưu không có nghiệm.

Giải: Đây là bài toán QHTT ở dạng gốc với, $\displaystyle c^T=\left[\begin{array}{cc}1&-1\end{array}\right],A=I=\left[\begin{array}{cc}1&0\\ {0}&1\end{array}\right],b=\left[\begin{array}{c}0\\{0}\end{array}\right]$ . Tuy nhiên, cũng có thể coi đây là bài toán QHTT dạng chuẩn tắc với $\displaystyle c^T=\left[\begin{array}{cc}1&-1\end{array}\right]$ và không có $\displaystyle A,b$ , tức là số ràng buộc đẳng thức $\displaystyle m=0$ . Dễ thấy $\displaystyle x=(0,0)$ là nghiệm cơ sở chấp nhận được (có 2 ràng buộc độc lập tuyến tính được kích hoạt). Khi đó $\displaystyle \bar{c}^T=c^T=\left[\begin{array}{cc}1&-1\end{array}\right]$ , chứng tỏ nếu ta đi theo hướng $\displaystyle x_2$ , tức là $\displaystyle d=(0,1)$ , thì sẽ giảm được giá trị hàm mục tiêu. Ta có $\displaystyle d_B\geq 0$ nên suy ra bài toán QHTT không bị chặn và không có nghiệm (thật ra $\displaystyle d_B$ là véctơ rỗng, nhưng ta vẫn có thể coi như $\displaystyle d_B\geq 0$ ).

Ví dụ 3: Giải bài toán tối ưu $\displaystyle \min~ -x_1-x_2$ với các ràng buộc

$\displaystyle \begin{array}{rrr}-x_1&+2x_2&\leq 8\\2x_1&+x_2&\leq 9\\3x_1&-x_2&\leq 6\\x_1,x_2&&\geq 0\end{array}$

Giải: Ta thêm vào 3 biến $\displaystyle x_3,x_4,x_5$ để chuyển bài toán về dạng chuẩn tắc

$\displaystyle \min ~-x_1-x_2$
$\displaystyle \begin{array}{rrrrrrr}-x_1&+2x_2&+x_3&&&= 8\\2x_1&+x_2&&+x_4&&= 9\\3x_1&-x_2&&&+x_5&= 6\end{array}$
$\displaystyle x_1,x_2,x_3,x_4,x_5\geq 0$

Dễ thấy $\displaystyle x=(0,0,8,9,6)$ là nghiệm cơ sở chấp nhận được. Khi đó $\displaystyle B=I,c_B=0$ , suy ra $\displaystyle -c_B^Tx_B=0, B^{-1}A=A, \bar{c}^T=c^T$ . Ta có bảng

$\displaystyle \left[\begin{array}{rrrrrrr}0&\vdots&-1&-1&0&0&0\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots\\x_3=8&\vdots&-1&2^+&1&0&0 \\x_4=9&\vdots&2&1&0&1&0\\x_5=6&\vdots&3^*&-1&0&0&1\end{array}\right]$

Lần lặp 1: Vị trí đánh dấu (*) là lựa chọn vị trí $\displaystyle k=1,p=3$ , vị trí đánh dấu (+) là các lựa chọn khác có thể xảy ra. Chia dòng thứ 4 cho $\displaystyle 3$ , rồi nhân dòng thứ 4 với $\displaystyle 1,1,-2$ và cộng vào các dòng 1,2,3, bảng sẽ thay đổi như sau

$\displaystyle \left[\begin{array}{rrrrrrr}2&\vdots&0&-4/3&0&0&1/3\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots\\x_3=10&\vdots&0&5/3&1&0&1/3 \\x_4=5&\vdots&0&5/3^*&0&1&-2/3\\x_1=2&\vdots&1&-1/3&0&0&1/3\end{array}\right]$

Lần lặp 2: Lựa chọn duy nhất $\displaystyle k=2,p=2$ , bảng thay đổi như sau

$\displaystyle \left[\begin{array}{rrrrrrr}6&\vdots&0&0&0&4/5&-1/5\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots\\x_3=5&\vdots&0&0&1&-1&1^*\\ x_2=3&\vdots&0&1&0&3/5&-2/5\\x_1=3&\vdots&1&0&0&1/5&1/5\end{array}\right]$

Lần lặp 3: Lựa chọn duy nhất $\displaystyle k=5,p=1$

$\displaystyle \left[\begin{array}{rrrrrrr}7&\vdots&0&0&1/5&3/5&0\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots\\x_5=5&\vdots&0&0&1&-1&1\\ x_2=5&\vdots&0&1&2/5&1/5&0\\x_1=2&\vdots&4/5&0&-1/5&2/5&0\end{array}\right]$

Thuật toán dừng và cho nghiệm tối ưu $\displaystyle x=(2,5,0,0,5)$ . Giá trị tối ưu của hàm mục tiêu là $\displaystyle -7$ .

Ví dụ 4: Vẫn là bài toán trên nhưng ta bỏ đi 1 điều kiện $\displaystyle x_1\geq 0$ , ta có bài toán

$\displaystyle \min~ -x_1-x_2$
$\displaystyle \begin{array}{rrr}-x_1&+2x_2&\leq 8\\2x_1&+x_2&\leq 9\\3x_1&-x_2&\leq 6\\x_2&&\geq 0\end{array}$

Giải: Ta thêm vào 3 biến $\displaystyle x_3,x_4,x_5$ và thay $\displaystyle x_1=x_1^+ -x_1^-$ , ta có bài toán ở dạng chuẩn tắc

$\displaystyle \min~ -x_1^+ +x_1^- -x_2$
$\displaystyle \begin{array}{rrrrrrrr}-x_1^+&+x_1^-&+2x_2&+x_3&&&= 8\\2x_1^+&-2x_1^-&+x_2&&+x_4&&= 9\\3x_1^+&-3x_1^-&-x_2&&&+x_5&= 6\end{array}$
$\displaystyle x_1^+,x_1^-,x_2,x_3,x_4,x_5\geq 0$

Dễ thấy $\displaystyle x=(0,0,0,8,9,6)$ là nghiệm cơ sở chấp nhận được. Để ý rằng $\displaystyle A_1^+=-A_1^-$ nên hai cột này không bao giờ cùng ở trong hệ cơ sở, đồng thời, hai cột tương ứng trong bảng (cột 2 và cột 3) luôn là đảo dấu của nhau.

$\displaystyle \left[\begin{array}{rrrrrrrr}0&\vdots&-1&1&-1&0&0&0\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\x_3=8&\vdots&-1&1&2^+&1&0&0 \\x_4=9&\vdots&2&-2&1&0&1&0\\x_5=6&\vdots&3^*&-3&-1&0&0&1\end{array}\right]$

$\displaystyle \left[\begin{array}{rrrrrrrr}2&\vdots&0&0&-4/3&0&0&1/3\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\x_3=10&\vdots&0&0&5/3&1&0&1/3 \\x_4=5&\vdots&0&0&5/3^*&0&1&-2/3\\x_1^+=2&\vdots&1&-1&-1/3&0&0&1/3\end{array}\right]$

$\displaystyle \left[\begin{array}{rrrrrrrr}6&\vdots&0&0&0&0&4/5&-1/5\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\x_3=5&\vdots&0&0&0&1&-1&1^*\\ x_2=3&\vdots&0&0&1&0&3/5&-2/5\\x_1^+=3&\vdots&1&-1&0&0&1/5&1/5\end{array}\right]$

$\displaystyle \left[\begin{array}{rrrrrrrr}7&\vdots&0&0&0&1/5&3/5&0\\\ldots&.&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\x_5=5&\vdots&0&0&0&1&-1&1\\ x_2=5&\vdots&0&0&1&2/5&1/5&0\\x_1^+=2&\vdots&4/5&-4/5&0&-1/5&2/5&0\end{array}\right]$

Thuật toán dừng và cho nghiệm tối ưu $\displaystyle x=(2,0,5,0,0,5)$ tương ứng với nghiệm tối ưu ở bài toán ban đầu là $\displaystyle x=(2,5)$ . Giá trị tối ưu của hàm mục tiêu là $\displaystyle -7$ . Trong thực tế người ta không đưa cột $\displaystyle A_1^-$ vào bảng mà ngầm hiểu là nếu $\displaystyle \bar{c}_1^+>0$ thì $\displaystyle \bar{c}_1^-<0$ và ngược lại. Vì vậy, nếu ta bỏ đi cả điều kiện $\displaystyle x_2\geq 0$ thì nghiệm của bài toán này vẫn không thay đổi (các bước lặp vẫn tương tự như trên).

Bài viết này được đăng vào Tháng Hai 26, 2008 lúc 8:32 chiều và tập tin được lưu ở Quy hoạch tuyến tính. Tagged: dạng bảng, phương pháp đơn hình, ví dụ. 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) (4) – Dạng bảng của thuật toán

Phương pháp đơn hình (Simplex method) (6) – Khởi tạo thuật toán đơn hình, thuật toán hai pha »

	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) (5) – Một số ví dụ

Để lại hồi âm