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

- Ngược lại thì sang bước (c)

c- Cập nhật các giá trị mới :

.Tính pivot

.Tính ma trận chuyển cơ sở k

.Tính ${\overline{A}}_{k+1}={\mu }^k{\overline{A}}_k$

.Tính ${\overline{b}}_{k+1}={\mu }^k{\overline{b}}_k$

.Tăng số lần lặp k=k+1.

Quay về bước b

Ví dụ

Giải bài toán quy hoạch tuyến tính sau đây bằng phương pháp đơn hình cải tiến :

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

Bước khởi tạo

$\begin{array}{}{\overline{A}}_0=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]{\overline{b}}_0=\left[\begin{array}{c}3\\ 6\\ 2\end{array}\right]\\ {\text{N}}_0{\text{B}}_0\end{array}$

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

Bước lặp k=0

$\begin{array}{}{x}_3\\ x_4\\ x_5\\ \\ \mathrm{righ}\\ \\ \\ \\ 3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ \\ x_{N_0}=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ x_{B_0}=\\ \\ \begin{array}{}\end{array}\\ x^0=\\ \end{array}$

$\begin{array}{}=\left[0\text{0 0}\right]\\ 3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ z(x^0)=c_{B_0}^T{\overline{b}}_0\\ \end{array}$

$\begin{array}{}=\left[2\text{1 0 0 0}\right]-\left[\text{0 0 0}\right]\\ 1\text{-1 1 0 0}\\ \text{1 2 0 1 0}\\ -1\text{2 0 0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ {\overline{c}}_0^T=c^T-c_{B_0}^T{\overline{A}}_0\\ \end{array}$

$\begin{array}{}1\\ 1\\ -1\\ \\ \mathrm{righ}\\ \\ \\ \\ []\\ \\ 3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$ suy ra pivot : ${\overline{a}}_{\text{11}}=1$

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

${\overline{A}}_1={\mu }^0{\overline{A}}_0=$ $\left[\begin{array}{ccc}\text{1}& 0& 0\\ -1& 1& 0\\ \text{1}& 0& 1\end{array}\right]$ $\begin{array}{}1\text{-1 1 0 0}\\ \text{1 2 0 1 0}\\ -1\text{2 0 0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$ = $\begin{array}{}1\text{-1 1 0 0}\\ \text{0 3 -1 1 0}\\ \text{0 1 1 0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

${\overline{b}}_1={\mu }^0{\overline{b}}_0=$ $\left[\begin{array}{ccc}\text{1}& 0& 0\\ -1& 1& 0\\ \text{1}& 0& 1\end{array}\right]$ $\begin{array}{}3\\ 6\\ 2\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$ = $\begin{array}{}3\\ 3\\ 5\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

Bước lặp k=1

$\begin{array}{}{x}_1\\ x_4\\ x_5\\ \\ \mathrm{righ}\\ \\ \\ \\ 3\\ 3\\ 5\\ \\ \mathrm{righ}\\ \\ \\ x_{N_1}=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ x_{B_1}=\\ \\ \begin{array}{}\end{array}\\ x^1=\\ \end{array}$

$\begin{array}{}=\left[2\text{0 0}\right]\\ 3\\ 3\\ 5\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ z(x^1)=c_{B_1}^T{\overline{b}}_1\\ \end{array}$

${\overline{c}}_1^T=c^T-c_{B_1}^T{\overline{A}}_1=\left[2\text{1 0 0 0}\right]-\left[\text{2 0 0}\right]$ $\begin{array}{}1\text{-1 1 0 0}\\ \text{0 3 -1 1 0}\\ \text{0 1 1 0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

= [ 0 3 -2 0 0 ]

$\begin{array}{}-1\\ \text{3}\\ 1\\ \\ \mathrm{righ}\\ \\ \\ \\ []\\ \\ 3\\ 3\\ 5\\ \\ \mathrm{righ}\\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$ suy ra pivot : ${\overline{a}}_{\text{22}}=3$

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

${\overline{A}}_2={\mu }^1{\overline{A}}_1=$ $\left[\begin{array}{ccc}1& \frac{1}{3}& 0\\ 0& \frac{1}{3}& 0\\ 0& -\frac{1}{3}& 1\end{array}\right]$ $\begin{array}{}1\text{-1 1 0 0}\\ \text{0 3 -1 1 0}\\ \text{0 1 1 0 1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$ = $\begin{array}{}1\text{0}\frac{2}{3}\frac{1}{3}\text{0}\\ \text{0 1 -}\frac{1}{3}\frac{1}{3}\text{0}\\ 0\text{0}\frac{4}{3}\text{-}\frac{1}{3}\text{1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

${\overline{b}}_2={\mu }^1{\overline{b}}_1=$ $\left[\begin{array}{ccc}1& \frac{1}{3}& 0\\ 0& \frac{1}{3}& 0\\ 0& -\frac{1}{3}& 1\end{array}\right]$ $\begin{array}{}3\\ 3\\ 5\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$ = $\begin{array}{}4\\ 1\\ 4\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

Bước lặp k=2

$\begin{array}{}{x}_1\\ x_2\\ x_5\\ \\ \mathrm{righ}\\ \\ \\ \\ 4\\ 1\\ 4\\ \\ \mathrm{righ}\\ \\ \\ x_{N_2}=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ x_{B_2}=\\ \\ \begin{array}{}\end{array}\\ x^2=\\ \end{array}$

$\begin{array}{}=\left[2\text{1 0}\right]\\ 4\\ 1\\ 4\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ z(x^2)=c_{B_2}^T{\overline{b}}_2\\ \end{array}$

${\overline{c}}_2^T=c^T-c_{B_2}^T{\overline{A}}_2=\left[2\text{1 0 0 0}\right]-\left[\text{2 1 0}\right]$ $\begin{array}{}1\text{0}\frac{2}{3}\frac{1}{3}\text{0}\\ \text{0 1 -}\frac{1}{3}\frac{1}{3}\text{0}\\ 0\text{0}\frac{4}{3}\text{-}\frac{1}{3}\text{1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

= [ 0 0 -1 -1 0 ] : thoả dấu hiệu tối ưu.

Vậy kết quả của bài toán là :

. Phương án tối ưu x = x2 = $\begin{array}{}4\\ 1\\ 0\\ 0\\ 4\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\left[\right]\left[\right]\left[\right]\end{array}\\ \\ \end{array}$

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

Phép tính trên dòng - bảng đơn hình

Các bước thực hiện giải thuật đơn hình cải tiến được trình bày lần lượt trong các bảng, gọi là bảng đơn hình. Trong thực hành, để cập nhật những giá trị mới ta có thể làm như sau :

. Tìm pivot.

. Chia dòng chứa pivot cho pivot.

. Khử các phần tử trên cột chứa pivot.

. Tính dấu hiệu tối ưu.

. Tính giá trị hàm mục tiêu .

Phương pháp biến giả cải biên

Bài toán cải biên

a- Cải biên bài toán quy hoạch tuyến tính

Người ta có thể biến đổi một bài toán quy hoạch tuyến tính chính tắc thành dạng chuẩn bằng cách cộng một cách phù hợp vào vế trái của ràng buộc i một biến giả xn+i  0 để làm xuất hiện ma trận đơn vị. Vì các biến giả cải biên có ảnh hưởng đến hàm mục tiêu nên cũng sẽ có sự cải biên hàm mục tiêu.

Vậy, người ta có thể biến đổi bài toán quy hoạch tuyến tính tổng quát, gọi là bài toán xuất phát, thành bài toán dạng chuẩn, gọi là bài toán cải biên (mở rộng)

Ví dụ :

Biến đổi bài toán quy hoạch tuyến tính sau đây thành dạng chuẩn

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

Bài toán xuất phát có các biến, ma trận ràng buộc và chi phí :

$\begin{array}{}\\ 1\text{5 0 5}\\ \text{0 -4 -1 6}\\ \text{0 3 0 8}\\ \\ \mathrm{righ}\\ \\ \\ \\ \\ \begin{array}{}{x}^T=[x_1{\text{x}}_2{\text{x}}_3{\text{x}}_4]\\ A=\end{array}\begin{array}{}\left[\right]\left[\right]\end{array}\\ \end{array}$

Bằng cách thêm biến giả x5, x6 lần lượt vào ràng buộc 2 và 3 . Ta được bài toán cải biên :

$\begin{array}{}\begin{array}{}{\text{max}\text{{}z}^{\text{'}}(x)={\mathrm{2x}}_1+x_2+x_3-x_4-M(x_5+x_6)\end{array}\\ x_1+{\mathrm{5x}}_2+{\mathrm{5x}}_4=\text{25}\\ -{\mathrm{4x}}_2-x_3+{\mathrm{6x}}_4+x_5=\text{18}\\ {\mathrm{3x}}_2+{\mathrm{8x}}_4+x_6=\text{28}\\ \\ \\ x_j\ge \text{0}(j=\mathrm{1,2,3,4,5,6})\\ \begin{array}{}\{\{\end{array}\end{array}$