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

a- Tính ma trận nghịch đảo B-1

b- Tính các tham số :

. Phương án cơ sở khả thi tốt hơn

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

. Giá trị hàm mục tiêu $z(x)=c_B^T{x}_B$

$$ . Ma trận $\stackrel{\text{\_\_}}{N}$ = B-1N

c- Xét dấu hiệu tối ưu :

${\overline{c}}_N^T=c_N^T-c_B^T{B}^{-1}N=c_N^T-c_B^T\stackrel{\text{\_\_}}{N}$

- Nếu thì kết thúc giải thuật với phương án tối ưu là :

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

và giá trị hàm mục tiêu là :

$z(x)=c_B^T{x}_B$

- Nếu tồn tại ${\overline{c}}_s\in {\overline{c}}_N$ mà ${\overline{c}}_s>0$ thì sang bước d.

d- Xác định chỉ số của phần tử pivot trong ma trận $\overline{N}$

. Xác định chỉ số cột s của pivot

${\overline{c}}_s=\text{max}\left\{{\overline{c}}_k>0\in {\overline{c}}_N\right\}$

Nếu thì giải thuật dừng, bài toán không có phương án tối ưu. Ngược lại thì tiếp tục.

. Xác định chỉ số dòng r của pivot

$\text{min}\left\{\frac{{\overline{b}}_i}{{\overline{N}}_{\text{is}}}\text{,}{\overline{N}}_{\text{is}}>0\right\}=\frac{{\overline{b}}_r}{{\overline{N}}_{\text{rs}}}(i=\text{1,2,}\text{.}\text{.}\text{.}\text{,m})$

Phần tử ${\overline{N}}_{\text{rs}}$ trong ma trận $\stackrel{\text{\_\_}}{N}$ được gọi là phần tử pivot

Trong trường hợp bài toán min

c- Xét dấu hiệu tối ưu :

${\overline{c}}_N^T=c_N^T-c_B^T{B}^{-1}N=c_N^T-c_B^T\stackrel{\text{\_\_}}{N}$

- Nếu ${\overline{c}}_N^T\ge$ 0 thì kết thúc giải thuật với phương án tối ưu là :

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

và giá trị hàm mục tiêu là :

$z(x)=c_B^T{x}_B$

- Nếu tồn tại ${\overline{c}}_s\in {\overline{c}}_N$ mà thì sang bước d.

d- Xác định chỉ số của phần tử pivot trong ma trận $\overline{N}$

. Xác định chỉ số cột s của pivot

Nếu thì giải thuật dừng, bài toán không có phương án tối ưu. Ngược lại thì tiếp tục.

. Xác định chỉ số dòng r của pivot

$\text{min}\left\{\frac{{\overline{b}}_i}{{\overline{N}}_{\text{is}}}\text{,}{\overline{N}}_{\text{is}}>0\right\}=\frac{{\overline{b}}_r}{{\overline{N}}_{\text{rs}}}(i=\text{1,2,}\text{.}\text{.}\text{.}\text{,m})$

Phần tử ${\overline{N}}_{\text{rs}}$ trong ma trận $\stackrel{\text{\_\_}}{N}$ được gọi là phần tử pivot

e- Thực hiện các hoán vị :

. Cột thứ s trong ma trận N với cột thứ r trong ma trận B

. Phần tử thứ s trong $c_N^T$ với phần tử thứ r trong $c_B^T$

. Biến xs trong $x_N^T$ với biến xr trong $x_B^T$

f- Quay về (a)

Ví dụ : Tìm phương án tối ưu cho bài toán quy hoạch tuyến tính chính tắc sau đây bằng giải thuật đơn hình cơ bản

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

Ta có :

$\begin{array}{}A=\left[\begin{array}{cccccc}1& -1& \mid & 1& \text{0}& \text{0}\\ 1& \text{2}& \mid & 0& \text{1}& \text{0}\\ -1& \text{2}& \mid & 0& \text{0}& 1\end{array}\right]\text{b}=\left[\begin{array}{c}3\\ 6\\ 2\end{array}\right]\\ \text{N B}\\ x^T=\left[\begin{array}{cccccc}{x}_1& x_2& \mid & x_3& x_4& x_5\end{array}\right]\\ x_N^T{x}_B^T\\ c^T=\left[\begin{array}{cccccc}2& \text{1}& \mid & 0& \text{0}& \text{0}\end{array}\right]\\ c_N^T{c}_B^T\end{array}$

Lần lặp1

a- Tính ma trận nghịch đảo B-1

$B^{-1}=B=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

b- Tính các tham số

. Phương án cơ sở khả thi tốt hơn :

$\begin{array}{}{x}_3\\ x_4\\ x_5\\ \\ \mathrm{righ}\\ \\ \\ \\ 1\text{0 0}\\ 0\text{1 0}\\ 0\text{0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ []\\ \\ 3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ \\ \\ 3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ x_1\\ x_2\\ \\ \mathrm{righ}\\ \\ \\ \\ 0\\ 0\\ \\ \mathrm{righ}\\ \\ \\ \\ []\\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ x_B=\\ \\ \begin{array}{}\end{array}\\ x=\\ \end{array}$

. Giá trị hàm mục tiêu :

$z(x)=c_B^T{x}_B=\left[\begin{array}{ccc}0& 0& 0\end{array}\right]\left[\begin{array}{c}3\\ 6\\ 2\end{array}\right]=0$

. Tính ma trận :

$\stackrel{\text{\_\_}}{N}=B^{-1}N=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{cc}\text{1}& -1\\ \text{1}& \text{2}\\ -1& \text{2}\end{array}\right]=\left[\begin{array}{cc}\text{1}& -1\\ \text{1}& \text{2}\\ -1& \text{2}\end{array}\right]$

c- Xét dấu hiệu tối ưu :

${\overline{c}}_N^T=c_N^T-c_B^T\stackrel{\text{\_\_}}{N}=\left[\begin{array}{cc}2& 1\end{array}\right]-\left[\begin{array}{ccc}0& 0& 0\end{array}\right]\left[\begin{array}{cc}\text{1}& -\text{1}\\ \text{1}& \text{2}\\ -1& \text{2}\end{array}\right]=\left[\begin{array}{cc}\text{2}& \text{1}\end{array}\right]$

Chuyển sang bước d

d- Xác định chỉ số của pivot

. Xác định chỉ số cột pivot s :

${\overline{c}}_s=\text{max}\left\{{\overline{c}}_k>0\in {\overline{c}}_N\right\}$ $=\text{max}\left\{\text{2 , 1}\right\}=2={\stackrel{\text{\_\_}}{c}}_1$

Vậy s=1

Ma trận cột s=1 trong ma trận $\overline{N}$ là $\begin{array}{}1\\ 1\\ -1\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ {\overline{N}}_1=\\ \end{array}$

. Xác định chỉ số dòng pivot r :

$\text{min}\left\{\frac{{\overline{b}}_i}{{\bar{N}}_{\text{is}}}\right\}=\text{min}\left\{\frac{{\overline{b}}_1}{{\overline{N}}_{\text{11}}},\frac{{\overline{b}}_2}{{\overline{N}}_{\text{21}}}\right\}=\text{min}\left\{\frac{3}{1},\frac{6}{1}\right\}=3=\frac{{\overline{b}}_1}{{\bar{N}}_{\text{11}}}$

Vậy r = 1

e- Hoán vị

. Cột thứ s=1 trong ma trận N và cột thứ r=1 trong ma trận B

. Phần tử thứ s=1 trong $c_N^T$ với phần tử thứ r=1 trong $c_B^T$

. Biến thứ s=1 trong $x_N^T$ với biến thứ r=1 trong $x_B^T$

$A=\left[\begin{array}{cccccc}1& -1& \mid & 1& 0& 0\\ 1& 2& \mid & 0& 1& 0\\ -1& 2& \mid & 0& 0& 1\end{array}\right]\to A=\left[\begin{array}{cccccc}1& -1& \mid & 1& 0& 0\\ 0& 2& \mid & 1& 1& 0\\ 0& 2& \mid & -1& 0& 1\end{array}\right]$

$c^T=\left[\begin{array}{cccccc}2& 1& \mid & 0& 0& 0\end{array}\right]\to {\text{c}}^T=\left[\begin{array}{cccccc}0& 1& \mid & 2& 0& 0\end{array}\right]$

$x^T=\left[\begin{array}{cccccc}{x}_1& x_2& \mid & x_3& x_4& x_5\end{array}\right]\to {\text{x}}^T=\left[\begin{array}{cccccc}{x}_3& x_2& \mid & x_1& x_4& x_5\end{array}\right]$

f- Quay về bước a

Lần lặp 2

a. Tính ma trận nghịch đảo B-1

$B=\left[\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ -1& 0& 1\end{array}\right]{\text{B}}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 1& 0& 1\end{array}\right]$

b- Tính các tham số

. Phương án cơ sở khả thi tốt hơn :

$\begin{array}{}{x}_1\\ x_4\\ x_5\\ \\ \mathrm{righ}\\ \\ \\ \\ 1\text{0 0}\\ -1\text{1 0}\\ 1\text{0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ []\\ \\ 3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ \\ \\ 3\\ 3\\ 5\\ \\ \mathrm{righ}\\ \\ x_3\\ x_2\\ \\ \mathrm{righ}\\ \\ \\ \\ 0\\ 0\\ \\ \mathrm{righ}\\ \\ \\ \\ []\\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ x_B=\\ \\ \begin{array}{}\end{array}\\ x=\\ \end{array}$

. Giá trị hàm mục tiêu :

$z(x)=c_B^T{x}_B=\left[\begin{array}{ccc}2& 0& 0\end{array}\right]\left[\begin{array}{c}3\\ 3\\ 5\end{array}\right]=6$

. Tính ma trận :

$\stackrel{\text{\_\_}}{N}=B^{-1}N=\left[\begin{array}{ccc}1& 0& 0\\ \text{-1}& 1& 0\\ 1& 0& 1\end{array}\right]\left[\begin{array}{cc}\text{1}& -1\\ \text{0}& \text{2}\\ 0& \text{2}\end{array}\right]=\left[\begin{array}{cc}\text{1}& -1\\ \text{-1}& \text{3}\\ 1& \text{1}\end{array}\right]$

c- Xét dấu hiệu tối ưu :

${\overline{c}}_N^T=c_N^T-c_B^T\stackrel{\text{\_\_}}{N}=\left[\begin{array}{cc}0& 1\end{array}\right]-\left[2\text{0 0}\right]\left[\begin{array}{cc}\text{1}& -\text{1}\\ \text{-1}& \text{3}\\ 1& \text{1}\end{array}\right]=\left[-23\right]$

Chuyển sang bước d

d- Xác định chỉ số của pivot