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

Dấu hiệu tối ưu

Theo trên, khi một bài toán quy hoạch tuyến tính có phương án tối ưu thì tồn tại một cơ sở khả thi (tối ưu) B* , tức là phương án cơ sở x* tương ứng với B* là phương án tối ưu.

Vấn đề bây giờ là xác định một thủ tục để tìm B*. Chúng ta sẽ thấy rằng thủ tục đó được suy ra một cách trực tiếp từ việc chứng minh dấu hiệu tối ưu sau đây.

Ðịnh lý 4 (dấu hiệu tối ưu)

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}$

Điều kiện cần và đủ để một phương án cơ sở khả thi x có dạng :

$\begin{array}{}{x}_B=B^{-1}b\ge 0\\ x_N=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ x=\\ \end{array}$

của bài toán là phương án tối ưu là :

đối với bài toán max

${\overline{c}}_N^T=c_N^T-c_B^T{B}^{-1}\text{N}\ge \text{0}$ đối với bài toán min

Với :

A = [ B | N ]

cT= [ cB | cN ]

Người ta thường gọi :

cN là chi phí ngoài cơ sở

cB là chi phí cơ sở

${\overline{c}}_N^T$ là chi phí trượt giảm

$c_B^T{B}^{-1}N$ là lượng gia giảm chi phí

Chứng minh (cho bài toán max)

Ðiều kiện đủ

Giả sử x* là một phương án cơ sở khả thi với ma trận cơ sở B và thoả

thì cần chứng minh x* là phương án tối ưu, nghĩa là chứng minh rằng với mọi phương án bất kỳ của bài toán ta luôn có :

z(x)  z(x*)

Xét một phương án khả thi x bất kỳ , x thoả :

$\{\begin{array}{c}\text{Ax}=b\\ x\ge 0\end{array}$ $\Rightarrow \{\begin{array}{c}\left[\begin{array}{cc}B& N\end{array}\right]\left[\begin{array}{c}{x}_B\\ x_N\end{array}\right]=b\\ \begin{array}{cc}\begin{array}{}\\ x_B\ge 0\end{array}& \begin{array}{}\\ x_N\ge 0\end{array}\end{array}\end{array}$

B là ma trận cơ sở của phương án cơ sở khả thi x*

B có ma trận nghịch đảo là B-1

 $\begin{array}{}{\text{Bx}}_B+{\text{Nx}}_N=b\\ x_B\ge {\text{0 x}}_N\ge 0\\ \\ \begin{array}{}\{\end{array}\\ \end{array}$

 $\begin{array}{}{B}^{\text{-1}}{\text{Bx}}_B+B^{\text{-1}}{\text{Nx}}_N=B^{\text{-1}}\text{b}(B^{\text{-1}}B=I)\\ x_B\ge {\text{0 x}}_N\ge 0\\ \\ \begin{array}{}\{\end{array}\\ \end{array}$

 $\begin{array}{}{x}_B+B^{\text{-1}}{\text{Nx}}_N=B^{\text{-1}}\text{.}b\\ x_B\ge {\text{0 x}}_N\ge 0\\ \\ \begin{array}{}\{\end{array}\\ \end{array}$

 $\begin{array}{}{x}_B=B^{\text{-1}}{\text{b-B}}^{\text{-1}}{\text{Nx}}_N\\ x_B\ge {\text{0 x}}_N\ge 0\\ \\ \begin{array}{}\{\end{array}\\ \end{array}$

Tính giá trị hàm mục tiêu đối với phương án x ta được :

z(x)= cTx

= $\left[\begin{array}{cc}{c}_B^T& c_N^T\end{array}\right]\left[\begin{array}{c}{x}_B\\ x_N\end{array}\right]=c_B^T{x}_B+c_N^T{x}_N$

= $c_B^TB^{-1}b-B^{-1}{\text{Nx}}_N+c_N^T{x}_N$

= $c_B^T{B}^{-1}b-c_B^T{B}^{-1}{\text{Nx}}_N+c_N^T{x}_N$

= $c_B^T{B}^{-1}b+(c_N^T{\text{-c}}_B^T{B}^{-1}N)x_N$ (1)

Vì x* là phương án cơ sở khả thi tương ứng với ma trận cơ sở B nên

$\begin{array}{}{x}_B^{}=B^{-1}b\ge 0\\ x_N^{}=0\\ \\ \begin{array}{}\{\end{array}\\ \end{array}$

Tính giá trị hàm mục tiêu đối vơi phương án cơ bản x* ta được :

z(x*)= cTx*

= $\left[\begin{array}{cc}{c}_B^T& c_N^T\end{array}\right]\left[\begin{array}{c}{x}_B^{}\\ x_N^{}\end{array}\right]=c_B^T{x}_B^{}+c_N^T{x}_N^{}$

= $c_B^T{x}_B^{}=c_B^T{B}^{-1}b$ ( vì $x_N^{}=0$ )(2)

Từ (1) và (2) ta có :

z(x)  z(x*)vì

Vậy x* là phương án tối ưu.

Ðiều kiện cần

Giả sử $\begin{array}{}x\ast \\ x_B^{}=B^{-1}b\ge 0\\ x_N^{}=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ \end{array}$ là phương án tối ưu với ma trận cơ sở B, cần chứng minh rằng : .

( ${\overline{c}}_N$ là vectơ có n-m thành phần)

Ta sẽ chứng minh điều này bằng phản chứng.

Giả sử rằng tồn tại một thành phần cs của ${\overline{c}}_N$ mà cs>0. Dựa vào cs người ta xây dựng một vectơ x như sau :

$\begin{array}{}{x}_B=x_B^{}-B^{-1}{\text{Nx}}_N\\ x_N={\text{θI}}_s\ge 0\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ x=\\ \end{array}$

Trong đó >0 và Is là một vectơ có (n-m) thành phần bằng 0, trừ thành phần thứ s bằng 1 . Vậy

$\begin{array}{}{x}_N={\text{θI}}_s\ge 0\\ x_B=x_B^{}-B^{-1}{\mathrm{N\theta I}}_s=B^{-1}b-B^{-1}N{\text{θI}}_s\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ x=\\ \end{array}$ (*)

Do B-1b  0 nên người ta có thể chọn >0 đủ nhỏ để xB>0

Vậy x được chọn như trên sẽ thoả :

x  0(3)

Ta kiểm chứng x thỏa ràng buộc của bài toán bằng cách tính :

Ax= $\left[\begin{array}{cc}B& N\end{array}\right]\left[\begin{array}{c}{x}_B\\ x_N\end{array}\right]={\text{Bx}}_B+{\text{Nx}}_N$

= $Bx_B^{}-B^{-1}N{\text{θI}}_s+N{\text{θI}}_s$

= $B{\text{B}}^{-1}b-B^{-1}N{\text{θI}}_s+N{\text{θI}}_s$

= ${\text{BB}}^{-1}b-{\mathrm{BB}}^{-1}{\mathrm{N\theta I}}_s+N{\text{θI}}_s$

= $b-N{\text{θI}}_s+N{\text{θI}}_s$

= b(4)

Từ (3) và (4) cho thấy x là một phương án khả thi của bài toán

Bây giờ ta chỉ ra mâu thuẩn bằng so sánh giá trị hàm mục tiêu tại x và x* . Ta có :

z(x)= cTx

= $\left[\begin{array}{cc}{c}_B^T& c_N^T\end{array}\right]\left[\begin{array}{c}{x}_B\\ x_N\end{array}\right]=c_B^T{x}_B+c_N^T{x}_N$

= $c_B^Tx_B^{}-B^{-1}{\text{Nx}}_N+c_N^T{x}_N$

= $c_B^T{x}_B^{}-c_B^T{B}^{-1}{\text{Nx}}_N+c_N^T{x}_N$

= $c_B^T{x}_B^{}+c_N^T{x}_N^{}-c_B^T{B}^{-1}{\text{Nx}}_N+c_N^T{x}_N(\text{vì}{c}_N^T{x}_N^{}=0)$

= $\left[c_B^T{c}_N^T\right]\left[\begin{array}{c}{x}_B^{}\\ x_N^{}\end{array}\right]+c_N^T-c_B^T{B}^{-1}N{\text{x}}_N$

= $c^T{x}^{}+c_N^T-c_B^T{B}^{-1}N{\text{θI}}_s$

= $c^T{x}^{}+{\overline{c}}_N^T{\text{θI}}_s$ = $c^T{x}^{}+{\overline{c}}_N^T{I}_s\theta$

= z(x*) + ${\overline{c}}_s\theta$ >z(x*) ( vì ${\overline{c}}_s\theta >0$ )

Vậy x* không phải là phương án tối ưu nên mâu thuẩn với giả thiết .

Chú ý

Qua việc chứng minh định lý dấu hiệu tối ưu ta thấy rằng từ một phương án cơ sở khả thi chưa tối ưu có thể tìm được các phương án khả thi càng lúc càng tốt hơn nhờ lặp lại nhiều lần công thức (*). Vấn đề được đặt là đại lượng  được chọn như thế nào để nhanh chóng nhận được phương án tối ưu.