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

Learn & Enjoy …

Phương pháp đơn hình (Simplex method) (5) – Một số ví dụ

Posted by 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:

  1. Đư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.

  2. 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]
  3. 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.
  4. Bảng này có \displaystyle \bar{c}\geq 0 nên \displaystyle x=(0,1,0) là nghiệm tối ưu.
  5. 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]
  6. 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).

About these ads

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

 
Theo dõi

Get every new post delivered to your Inbox.

%d bloggers like this: