Lý thuyết cơ bản về quy hoạch tuyến tính  (Page 6/8)

( dòng 3 được chọn )

Khi đó người ta chọn x3=1 nên thu được một phương án tốt hơn được xác định như sau :

$\begin{array}{}{x}_2=w_1=w_3=0\\ x_1=2{\text{x}}_3=1{\text{w}}_2=1\end{array}$

Giá trị tương ứng của hàm mục tiêu là z(x)=-13

Bước tiếp theo là biến đổi bài toán (II) thành một bài toán tương đương bằng cách từ dòng 3 ( dòng đựợc chọn ) tính x3 theo các biến còn lại và thế giá trị nhận được vào các dòng còn lại, ta được :

$\begin{array}{}\text{min}\text{z}(x)=\text{-13}+w_1+{\mathrm{3x}}_2+w_3\\ x_1={\text{2-2w}}_1-{\mathrm{2x}}_2+w_3\\ w_2=1+{\text{2w}}_1+{\mathrm{5x}}_2\\ x_3=1+{\text{3w}}_1+x_2-{\text{2w}}_3\\ \\ \\ \\ \begin{array}{}{x}_1,x_2,x_3,w_1,w_2,w_3\ge 0\\ \begin{array}{}\{\{\end{array}\end{array}\\ \end{array}$ (III)

Đến đây vì không có hệ số nào của hàm mục tiêu là âm nên không thể làm giảm giá trị của hàm mục tiêu theo cách như trên nữa. Phương án thu được ở bước sau cùng chính là phương án tối ưu của bài toán.

Đối với bài toán max, thay cho việc làm tăng biến có hệ số âm trong hàm mục tiêu người ta làm tăng biến có hệ số dương cho đến khi các hệ số trong hàm mục tiêu hoàn toàn âm.

Dấu hiệu tối ưu

Ma trận cơ sở - phương án cơ sở - suy biến

Xét bài toán quy hoạch tuyến tính chính tắc

$\begin{array}{}\text{min/max}z(x)=c^{T}x\\ \text{Ax}=b\\ x\ge 0\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$ (P)

a- Ma trận cơ sở

Người ta gọi cơ sở của bài toán quy hoạch tuyến tính chính tắc (P) là mọi ma trận B không suy biến (có ma trận nghịch đảo) mxm trích ra từ m cột của ma trận ràng buộc A. Các cột còn lại được gọi là ma trận ngoài cơ sở, ký hiệu là N .

b- Phương án cơ sở - Phương án cơ sở khả thi

B là một cơ sở của bài toán (P).

Khi đó, bằng cách hoán vị các cột của A người ta có thể luôn luôn đặt A dưới dạng :

A = [ B N ]

Do đó, người ta cũng phân hoạch x và c như sau :

xT = [ xB xN ]

cT = [ cB cN ]

Một phương án x của bài toán (P) thoả :

$\begin{array}{}\text{Ax}=b\iff \left[B\text{N}\right]\\ x_B\\ x_N\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ \end{array}$

Phương án cơ sở

Người ta gọi một phương án cơ sở tương ứng với cơ sở B là một phương án đặc biệt, nhận được bằng cách cho :

xN = 0

Khi đó xB được xác định một cách duy nhất bằng cách giải hệ phương trình tuyến tính bằng phương pháp Cramer :

BxB = b  xB = B-1b

Phương án cơ sở khả thi

Một phương án cơ sở là phương án cơ sở khả thi nếu :

xB = B-1b  0

Cơ sở tương ứng với một phương án khả thi được gọi là cơ sở khả thi .

Ví dụ : xét bài toán quy hoạch tuyến tính dạng chính tắc :

$\begin{array}{}\text{min/max}z(x)=x_1-x_2+x_3-x_4+x_5+x_6\\ {\mathrm{2x}}_1+{\mathrm{2x}}_4+x_5=\text{20}\\ -{\mathrm{3x}}_1+{\mathrm{4x}}_2-{\mathrm{4x}}_4+x_6=\text{10}\\ x_1+{\mathrm{2x}}_2+x_3+{\mathrm{3x}}_4=\text{28}\\ \\ \\ \\ \begin{array}{}{x}_j\ge \text{0}(j=\text{1,2,}\text{.}\text{.}\text{.}\text{,6})\\ \begin{array}{}\{\{\end{array}\end{array}\\ \end{array}$

Ma trận ràng buộc là

$\begin{array}{}{x}_1{\text{x}}_2{\text{x}}_3{\text{x}}_4{\text{x}}_{\text{5}}{\text{x}}_6\\ 2\text{0 0 2 1 0}\\ \text{-3 4 0 -4 0 1}\\ \text{1 2 1 3 0 0}\\ \\ \mathrm{righ}\\ \\ \\ \\ \\ \begin{array}{}\begin{array}{}\left[\right]\left[\right]\end{array}\\ A=\end{array}\\ \end{array}$

Có thể chọn ba cột bất kỳ và kiểm chứng xem đó có thể là cơ sở không.

Một cơ sở được chọn và sắp xếp lại là

$\begin{array}{}{x}_5{\text{x}}_6{\text{x}}_3{\text{x}}_4{\text{x}}_1{\text{x}}_2\\ \text{1 0 0}\text{2 2 0}\\ \text{0 1 0}\text{-4 -3 4}\\ \text{0 0 1}\text{3 1 2}\\ \\ \mathrm{righ}\\ \\ \\ \\ \\ \begin{array}{}\begin{array}{}\left[\right]\left[\right]\end{array}\\ \end{array}\\ \end{array}$

Các cột x5 x6 x3 tạo thành một ma trận cơ sở . Các biến tương ứng được gọi là các biến (trong) cơ sở .

Các cột x1 x2 x4 tạo thành một ma trận ngoài cơ sở. Các biến tương ứng được gọi là các biến ngoài cơ sở.

Một phương án cơ sở khả thi của bài toán là :

c- Suy biến

Một phương án cơ sở khả thi được gọi là suy biến nếu xB = B-1b  0 có những thành phần bằng 0. Sự suy biến là một hiện tượng thường xảy ra trong một số bài toán như bài toán vận tải, dòng dữ liệu, đường đi ngắn nhất....... Đây là hiện tượng khá phức tạp (có nhiều cách giải quyết sẽ được xét sau). Vì vậy trong những phần tiếp theo ta giả sử rằng phương án cơ sở khả thi là không suy biến, tức là xB = B-1b>0 ( dương thực sự ) .