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

$z^{\text{'}}(x)$ là hàm mục tiêu cải biên sẽ được giải thích trong phần tiếp theo.

Các biến, ma trận ràng buộc các hệ số và chi phí của bài toán cải biên là

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

b- Quan hệ giữa bài toán xuất phát và bài toán cải biên

Người ta kiểm chứng rằng :

- Nếu $x^T=[x_1{x}_2\text{.}\text{.}\text{.}{x}_n]$ là phương án (tối ưu) của bài toán xuất phát thì ${\overline{x}}^T=[x_1{x}_2\text{.}\text{.}\text{.}{x}_n\text{0 0}\text{.}\text{.}\text{.}\text{0}]$ là phương án (tối ưu) của bài toán cải biên tương ứng.

Vậy nếu bài toán cải biên không có phương án tối ưu thì bài toán xuất phát cũng sẽ không có phương án tối ưu.

- Nếu ${\overline{x}}^T=[x_1{x}_2\text{.}\text{.}\text{.}{x}_n\text{0 0}\text{.}\text{.}\text{.}\text{0}]$ là phương án tối ưu của bài toán cải biên thì $x^T=[x_1{x}_2\text{.}\text{.}\text{.}{x}_n]$ là phương án tối ưu của bài toán xuất phát

- Nếu bài toán cải biên có một phương án tối ưu mà trong đó có ít nhất một biến giả có giá trị dương thì bài toán xuất phát không có phương án tối ưu.

- Nếu bài toán cải biên (dạng chuẩn) có phương án tối ưu thì cũng sẽ phương án cơ sở tối ưu.

Ví dụ

1- Xét bài toán :

$\begin{array}{}\text{min}z(x)=x_1+{\text{2x}}_2+x_4-{\text{5x}}_5\\ -{\text{3x}}_3-{\text{9x}}_4=0\\ x_2-{\text{7x}}_3-{\text{5x}}_4-{\text{2x}}_5=5\\ x_1-\frac{1}{3}{x}_2+\frac{2}{3}{x}_3+\frac{4}{3}{x}_4+\frac{1}{3}{x}_5=\frac{2}{3}\\ \\ \\ \\ \\ \begin{array}{}{x}_j\ge \text{0}(j=\text{1,2,3,4, 5})\\ \begin{array}{}\{\{\{\end{array}\end{array}\\ \end{array}$

Bài toán cải biên không có phương án tối ưu nên bài toán xuất phát cũng không có phương án tối ưu .

2- Xét bài toán :

$\begin{array}{}\text{min z}(x)=-{\text{16x}}_1+{\text{7x}}_2+{\text{9x}}_3\\ -\frac{2}{3}{x}_1-\frac{1}{3}{x}_2+x_3=\frac{1}{3}\\ -{\text{5x}}_1+{\text{5x}}_2=7\\ \\ \\ \\ \begin{array}{}{x}_j\ge \text{0}(j=\text{1,2,3})\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

Phương án tối ưu của bài toán cải biên :

$\left[\begin{array}{cccc}{x}_1& x_2& x_3& x_4\end{array}\right]=\left[\begin{array}{cccc}0& \frac{7}{5}& \frac{\text{22}}{\text{15}}& 0\end{array}\right]$

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

$\left[\begin{array}{ccc}{x}_1& x_2& x_3\end{array}\right]=\left[\begin{array}{ccc}0& \frac{7}{5}& \frac{\text{22}}{\text{15}}\end{array}\right]$

3- Xét bài toán :

Phương án tối ưu của bài toán cải biên :

$\left[\begin{array}{cccccc}{x}_1& x_2& x_3& x_4& x_5& x_6\end{array}\right]=\left[\begin{array}{cccccc}0& 0& \text{25}& \text{43}& 2& 0\end{array}\right]$

Bài toán xuất phát không có phương án tối ưu .

Hai phương pháp biến giả cải biên thương dùng là phương pháp hai pha và phương pháp M vô cùng lớn .

Phương pháp hai pha

Pha 1

Tìm phương án tối ưu cho bài toán cải biên với hàm mục tiêu cải biên là :

min (tổng tất cả biến giả cải biên)

Pha 2

Tìm phương án tối ưu cho bài toán xuất phát với phương án cơ sở khả thi xuất phát là phương án tối ưu tìm được ở pha 1. Ở pha 2 này các biến giả cải biên bị loại ra khỏi ma trận các hệ số ràng buộc, và vectơ chi phí được cập nhật lại, do đó dấu hiệu tối ưu cũng được cập nhật lại

Đây là phương pháp thuận lợi cho việc lập trình ứng dụng giải thuật đơn hình cải tiến.

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

Đưa bài toán về dạng chính tắc bằng cách thêm biến phụ x4 , x5 ta được

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

Ma trận các hệ số ràng buộc là :

A= $\begin{array}{}12210\\ 1230-1\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ \\ \end{array}$ không chứa ma trận đơn vị

Áp dụng phương pháp đơn hình cải biên hai pha như sau :

Pha 1

Thêm biến giả (cải biên ) x6  0 vào ràng buộc thứ hai để được ma trận đơn vị . Khi đó bài toán cải biên có dạng :

$\begin{array}{}\text{min}w(x)=x_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}$

Có ma trận các ràng buộc là :

$\begin{array}{}12210\text{0}\\ 1230-1\text{1}\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ A=\\ \end{array}$ có chứa ma trận đơn vị

Giải bài toán cải biên bằng giải thuật đơ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}0& 0& 0& 0& 0& 1\end{array}\right]$

Bước lặp k=0

Bước lặp k= 1