0.1 Giải thuật đơn hình  (Page 6/7)

Ta được phương án tối ưu . Xong pha 1 . Chuyển sang pha 2.

Pha 2

Loại bỏ biến giả cải biên x6  0

Khởi tạo

$\begin{array}{}{\overline{A}}_0=\left[\begin{array}{ccccc}\frac{1}{3}& \frac{2}{3}& 0& 1& \frac{2}{3}\\ \frac{1}{3}& \frac{2}{3}& 1& 0& -\frac{1}{3}\end{array}\right]\\ {\overline{b}}_0=\left[\begin{array}{c}\frac{\text{10}}{9}\\ \frac{7}{9}\end{array}\right]\end{array}$

$c^T=\left[\begin{array}{ccccc}\text{3}& 4& 1& 0& 0\end{array}\right]$

Bước lặp k=0

Bước lặp k=1

Bước lặp k=2

Bước lặp k=3

Kết quả của bài toán đã cho :

. Phương án tối ưu  $\begin{array}{}{x}_1=\frac{8}{3}\\ x_2=0\\ x_3=0\\ x_4=0\\ x_5=\frac{1}{3}\\ \\ \begin{array}{}\{\{\{\{\end{array}\\ \end{array}$

. Giá trị hàm mục tiêu  z(x)=z(x3)= 8

Phương pháp m vô cùng lớn

Phương pháp M vô cùng lớn ( M là số vô cùng lớn ) tương tự như phương pháp hai pha, ngoại trừ ở pha 1 hàm mục tiêu cải biên có dạng sau đây cho bài toán max/min

max [z(x) - M*( tổng các biến giả cải biên) ]

min [z(x) + M*( tổng các biến giả cải biên) ]

Bằng phương pháp này, trong quá trình tối ưu, các biến giả cải biên sẽ được loại dần ra khỏi ma trận cơ sở : tất cả đều bằng 0. Nếu trong quá trình tìm phương án tối ưu mà không loại bỏ được các biến giả cải biên ra khỏi cơ sở thì bài toán vô nghiệm.

So với phương pháp hai pha thì phương pháp này tránh được việc phải cập nhật lại dữ liệu cho bài toán gốc nhưng không tiện lợi bằng trong lập trình ứng dụng.

Ví dụ : Xét bài toán tương tự như trên 

$\begin{array}{}\text{max}z(x)={\mathrm{3x}}_1+{\mathrm{4x}}_2+x_3\\ x_1+{\mathrm{2x}}_2+{\mathrm{2x}}_3+x_4=\frac{8}{3}\\ x_1+{\mathrm{2x}}_2+{\mathrm{3x}}_3-x_5=\frac{7}{3}\\ \\ \\ \\ \begin{array}{}{x}_j\ge 0(j=\text{1,2,3,4,5})\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

Thêm biến giả cải biên x6  0 vào ràng buộc thứ hai đồng thời cải biên hàm mục tiêu theo như trên ta được :

$\begin{array}{}\text{max}w(x)={\mathrm{3x}}_1+{\mathrm{4x}}_2+x_3-{\text{Mx}}_6\\ x_1+{\mathrm{2x}}_2+{\mathrm{2x}}_3+x_4=\frac{8}{3}\\ x_1+{\mathrm{2x}}_2+{\mathrm{3x}}_3-x_5+x_6=\frac{7}{3}\\ \\ \\ \\ \begin{array}{}{x}_j\ge 0(j=\text{1,2,3,4,5,6})\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

Tìm phương án tối ưu cho bài toán cải biên này bằng phương pháp đơn hình cải tiến

Khởi tạo

${\overline{A}}_0=\left[\begin{array}{cccccc}1& 2& 2& 1& 0& 0\\ 1& 2& 3& 0& -1& 1\end{array}\right]{\overline{b}}_0=\left[\begin{array}{c}\frac{8}{3}\\ \frac{7}{3}\end{array}\right]$ $c^T=\left[\begin{array}{cccccc}3& 4& 1& 0& 0& -M\end{array}\right]$

Bước lặp k=0

Bước lặp k= 1

Do x6 = 0 (vì ngoài cơ sở) nên bị loại ra khỏi bảng và ta tiếp tục tìm phương án tối ưu cho bài toán gốc đã cho có phương án cơ sở khả thi được khởi tạo như sau :

Các bước tiếp theo được thực hiện giống như phương pháp hai pha.

Quy hoạch tuyến tính suy biến

Khi thực hiện thuật toán đơn hình trường hợp bất thường có thể xảy ra là khi xác định biến ra thì tồn tại tỷ số $\frac{b_i}{a_{\text{ik}}}=0$ , tức là tồn tại bi=0, hay không có tỷ số nào dương thật sự. Người ta xem đây là trường hợp suy biến. Khi một bảng đơn hình rơi vào tình trạng suy biến thì có thể gây khó khăn mà cũng có thể không khi ta tiếp tục thực hiện thuật toán đơn hình.

Các ví dụ về quy hoạch tuyến tính suy biến

Ví dụ 1 : xét quy hoạch tuyến tính :

Đưa bài toán về dạng chuẩn :

$\begin{array}{}\text{min}\text{z}(x)=7+x_1-x_2\\ x_1-{\mathrm{2x}}_2+x_3=2\\ -{\mathrm{3x}}_1+x_4=6\\ -{\mathrm{2x}}_1+x_5=0\\ \\ \\ \\ \begin{array}{}{x}_1,x_2\ge 0\\ \begin{array}{}\{\{\end{array}\end{array}\\ \end{array}$

với ma trận hệ số là :

có chứa ma trận đơn vị. Áp dụng thuật toán đơn hình cải tiến ta được :