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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Thay đổi )

Twitter picture

You are commenting using your Twitter account. Log Out / Thay đổi )

Facebook photo

You are commenting using your Facebook account. Log Out / Thay đổi )

Google+ photo

You are commenting using your Google+ account. Log Out / Thay đổi )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: