0.2 Bài toán đối ngẫu  (Page 3/4)

Þ $c_B^T\text{.}{B}^{-1}A\ge c^T$

Þ $\begin{array}{}y\ast \\ \\ TA\ge c^T\\ \\ \end{array}$

Þy* là một phương án của (D)

Mặt khác x* được tính bởi công thức :

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

và giá trị mục tiêu tối ưu của (P) là :

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

Ta có :

$\begin{array}{}w(y^{})=b^{T}y\ast b^T(c_B^T{B}^{-1}{)}^T=(c_B^T{B}^{-1})b\\ ={\text{c}}_B^T(B^{\text{-1}}b)=c_B^T{x}_B^{}=c_B^T{x}_B^{}=z(x^{})\end{array}$

Theo định lý 2 thì y* là phương án tối ưu của (D).

Định lý này cho phép tìm phương án tối ưu của bài toán quy hoạch tuyến tính đối ngẫu từ bài toán gốc. Trong đó :

- $c_B^T$ được xác định trong bảng đơn hình tối ưu của (P).

- B-1 gồm m cột tương ứng với m cột của ma trận cơ sở ban đầu lấy từ bảng đơn hình tối ưu của bài toán gốc.

d- Định lý 4 ( sự đối ngẫu)

Xét hai bài toán đối ngẫu 

$\begin{array}{}(P)\\ \text{max z}(x)=c^T\text{x}\\ \text{Ax}=\text{b}\\ x\ge \text{0}\\ \\ \begin{array}{}\{\{\end{array}\end{array}$ $\begin{array}{}(D)\\ \text{min w}(y)={\text{b}}^{T}y\\ A^{T}y\ge \text{c}\\ \text{y tùy ý}\\ \\ \begin{array}{}\{\{\end{array}\end{array}$

- Nếu (P) và (D) đều có phương án khả thi thì chúng có phương án tối ưu và giá trị của hàm mục tiêu tương ứng là bằng nhau.

- Nếu một trong hai bài toán có phương án tối ưu không giới nội thì bài toán còn lại không có phương án khả thi.

Chứng minh

- Đây là kết quả của định lý 3 .

- Giả sử rằng phương án tối ưu của (D) không giới nội, tức là tồn tại một phương án khả thi y của (D) sao cho w(y)= bTy nhỏ tuỳ ý. Điều này cũng có nghĩa là : với mọi M>0 lớn tuỳ ý luôn tìm được một phương án khả thi $\overline{y}$ của (D) sao cho :

Nếu (P) có phương án khả thi là $\overline{x}$ thì theo định lý 1 ta có :

Điều này dẫn đến mâu thuẩn

e- Định lý 5 (tính bổ sung )

Xét hai bài toán đối ngẫu 

$\begin{array}{}(P)\\ \text{max z}(x)=c^T\text{x}\\ \text{Ax}=\text{b}\\ x\ge \text{0}\\ \\ \begin{array}{}\{\{\end{array}\end{array}$ $\begin{array}{}(D)\\ \text{min w}(y)={\text{b}}^{T}y\\ A^{T}y\ge \text{c}\\ \text{y tùy ý}\\ \\ \begin{array}{}\{\{\end{array}\end{array}$

$\overline{x}\text{,}\overline{y}$ là phương án khả thi tương ứng của (P) và (D).

Điều kiện cần và đủ để $\overline{x}\text{,}\overline{y}$ cũng là phương án tối ưu là :

${\overline{x}}^T(A^T\overline{y}-c^T)=0$

Chứng minh

- Do $\overline{x}$ là phương án khả thi của (P) nên :

$\begin{array}{}A\overline{x}=b\\ \Rightarrow (A\overline{x}{)}^T=b^T\\ \Rightarrow {\overline{x}}^T{A}^T=b^T\\ \Rightarrow {\overline{x}}^T{A}^T\overline{y}=b^T\overline{y}\\ \Rightarrow {\overline{x}}^T{A}^T\overline{y}-{\overline{x}}^{T}c=b^T\overline{y}{\text{-c}}^T\overline{x}({\text{x}}^{T}c=c^{T}x)\\ \Rightarrow {\overline{x}}^T(A^T\overline{y}-c)=b^T\overline{y}{\text{-c}}^T\overline{x}(\ast )\end{array}$

- Theo kết quả (*) :

. Nếu $\overline{x}\text{,}\overline{y}$ là phương án tối ưu của (P) và (D) thì theo định lý 4 $\begin{array}{}{c}^T\overline{x}=b^T\overline{y}\\ \Rightarrow c^T\overline{x}-b^T\overline{y}=0\\ \Rightarrow {\overline{x}}^T(A^T\overline{y}-c)=0\end{array}$

. Nếu ${\overline{x}}^T(A^T\overline{y}-c)=0\Rightarrow b^T\overline{y}-c^T\overline{x}=0\Rightarrow b^T\overline{y}=c^T\overline{x}$

Theo định lý 2 thì $\overline{x}\text{,}\overline{y}$ là phương án tối ưu .

Giải thuật đối ngẫu

Xét hai bài toán đối ngẫu :

(P) $\begin{array}{}\text{max}\text{z}(x)=c^{T}x\\ \text{Ax}=b\\ x\ge 0\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$ và (D) $\begin{array}{}\text{min}\text{w}(y)=b^{T}y\\ A^{T}y\ge c\\ y\text{tuy}y\\ \\ \\ \begin{array}{}\\ \begin{array}{}\{\end{array}\end{array}\\ \end{array}$

Chúng ta sẽ xét xem giải thuật đơn hình cơ bản đã biết trong chương trước được áp dụng như thế nào đối với bài toán đối ngẫu.

Giả sử rằng B là một cơ sở của bài toán (P) thoả :

$y=c_B^T{B}^{-1}$ và $N^{T}y\ge c_N$

Nếu B cũng là một cơ sở khả thi của bài toán gốc, tức là $\begin{array}{}{x}_B=B^{-1}b=\overline{b}\ge 0\\ x_N=0\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ x=\\ \end{array}$ , thì (theo định lý đối ngẫu) y, x lần lượt là phương án tối ưu của bài toán đối ngẫu và bài toán gốc. Nếu không thì $\begin{array}{}{x}_B\\ x_N\\ \\ \mathrm{righ}\\ \\ \\ \\ \begin{array}{}\left[\right]\end{array}\\ x=\\ \end{array}$ không là phương án của bài toán gốc vì $x_B=\overline{b}=B^{-1}b$ không thể  0.

Để tiện việc trình bày ta xét (m=3 , n=5) :

(P) $\begin{array}{}\text{max}\text{z}(x)=c_1{x}_1+c_2{x}_2+c_3{x}_3+c_4{x}_4+c_5{x}_5\\ a_{\text{11}}{x}_1+a_{\text{12}}{x}_2+a_{\text{13}}{x}_3+a_{\text{14}}{x}_4+a_{\text{15}}{x}_5=b_1\\ a_{\text{21}}{x}_1+a_{\text{22}}{x}_2+a_{\text{23}}{x}_3+a_{\text{24}}{x}_4+a_{\text{25}}{x}_5=b_2\\ a_{\text{31}}{x}_1+a_{\text{32}}{x}_2+a_{\text{33}}{x}_3+a_{\text{34}}{x}_4+a_{\text{35}}{x}_5=b_3\\ \\ \\ \\ \begin{array}{}{x}_1,x_2,x_3,x_4,x_5\ge 0\\ \begin{array}{}\{\{\end{array}\end{array}\\ \end{array}$

Các dữ liệu của (P) đuợc trình bày trong bảng sau :

và bài toán đối ngẫu

(D) $\begin{array}{}\text{min}\text{w}(y)=b_1{y}_1+b_2{y}_2+b_3{y}_3\\ a_{\text{11}}{y}_1+a_{\text{21}}{y}_2+a_{\text{31}}{y}_3\ge c_1\\ a_{\text{12}}{y}_1+a_{\text{22}}{y}_2+a_{\text{32}}{y}_3\ge c_2\\ a_{\text{13}}{y}_1+a_{\text{23}}{y}_2+a_{\text{33}}{y}_3\ge c_3\\ a_{\text{14}}{y}_1+a_{\text{24}}{y}_2+a_{\text{34}}{y}_4\ge c_4\\ a_{\text{15}}{y}_1+a_{\text{25}}{y}_2+a_{\text{35}}{y}_3\ge c_5\\ \\ \\ \\ \begin{array}{}{y}_1,y_2,y_3\text{tuy y}\\ \begin{array}{}\{\{\{\{\end{array}\end{array}\\ \end{array}$

Người ta đưa (D) về dạng chính tắc bằng cách thêm các biến phụ y4 y5, y6, y7, y8  0. Chúng không ảnh hưởng đến hàm mục tiêu.