CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Định lý đảo tổng quát

Posted by Trần Quốc Long on Tháng Hai 4, 2008

Định lý (kiểm tra tính vô nghiệm của hệ bất phương trình tuyến tính). Hệ bất phương trình

\mathcal{P}\begin{cases} a_i^T x > b_i & i = 1,\ldots,m_s\\ a_i^T x \geq b_i & i = m_s+1, \ldots, n\end{cases}

vô nghiệm nếu và chỉ nếu ít nhất một trong hai hệ bất phương trình sau

\mathcal{T}_1 \begin{cases}\lambda_i \geq 0 \\ \displaystyle\sum_{i=1}^n \lambda_i a_i = 0 \\ \displaystyle\sum_{i=1}^{m_s} \lambda_i > 0 \\ \displaystyle\sum_{i=1}^n \lambda_i b_i \geq 0 \end{cases} \mathcal{T}_2 \begin{cases}\lambda_i \geq 0 \\ \displaystyle\sum_{i=1}^n \lambda_i a_i = 0 \\ \displaystyle\sum_{i=1}^{m_s} \lambda_i = 0 \\ \displaystyle\sum_{i=1}^n \lambda_i b_i > 0 \end{cases}

có nghiệm.

Chứng minh:

\Rightarrow“: Nếu \mathcal{T}_1 có nghiệm, ta có

0=0x=\displaystyle\sum_{i=1}^n \lambda_i a_i ^T x>\sum_{i=1}^n \lambda_i  b_i \geq 0

tức là 0 > 0, mâu thuẫn.

Nếu \mathcal{T}_2 có nghiệm, ta có

0=0x=\displaystyle\sum_{i=1}^n \lambda_i a_i ^T x\geq\sum_{i=1}^n \lambda_i  b_i > 0

cũng dẫn đến mâu thuẫn, vậy \mathcal{P} không có nghiệm.

\Leftarrow“: (Sử dụng định lý Farkas) Giả sử \mathcal{P} không có nghiệm.

Xét hệ bất phương trình

\mathcal{P^*}\begin{cases} \tau - \epsilon \geq 0 \\ a_i^T x - b_i \tau - \epsilon \geq 0 & i = 1,\ldots,m_s\\ a_i^T x - b_i\tau \geq 0 & i = m_s+1, \ldots, n\end{cases}

Rõ ràng, nghiệm của \mathcal{P^*} phải có \epsilon \leq 0 vì nếu \epsilon > 0 thì \displaystyle \frac{x}{\tau} sẽ là nghiệm của \mathcal{P}. Như vậy, bất đẳng thức -\epsilon \geq 0 là hệ quả của hệ bất phương trình \mathcal{P^*}, theo định lý Farkas, ta có

\displaystyle\left[\begin{array}{r}0\\ 0 \\-1\end{array}\right]=\nu\left[\begin{array}{r}0\\1\\-1\end{array}\right]+\sum_{i=1}^{m_s}\lambda_i \left[\begin{array}{r}a_i\\-b_i\\-1\end{array}\right]+\sum_{i=m_s+1}^n\lambda_i \left[\begin{array}{r}a_i\\-b_i\\ 0 \end{array}\right]

với \nu, \lambda_i \geq 0, i = 1,\ldots,n. Viết lại hệ trên ta được

\mathcal{T}\begin{cases} \nu,\lambda_i \geq 0\\\displaystyle\sum_{i=1}^n\lambda_i a_i = 0\\\displaystyle\sum_{i=1}^n\lambda_i b_i = \nu\\\displaystyle\sum_{i=1}^{m_s}\lambda_i =1-\nu\end{cases}

Suy ra \nu \leq 1, ta xét hai trường hợp

(i) \nu = 1, rõ ràng \lambda_i, i=1,\ldots,n là nghiệm của \mathcal{T}_2.

(ii) \nu < 1, rõ ràng \lambda_i, i=1,\ldots,n là nghiệm của \mathcal{T}_1.

Nhận xét: Điểm lý thú của định lý đảo là đã chỉ ra điều kiện cần và đủ để một hệ bất phương trình vô nghiệm lại là tính có nghiệm của một hệ bất phương trình khác. Bình thường, kiểm tra tính vô nghiệm (không tồn tại nghiệm) khó hơn kiểm tra tính có nghiệm (chỉ cần chỉ ra một nghiệm).

Hệ quả 1 (Định lý Farkas không thuần nhất). Bất đẳng thức a^T x \leq b là hệ quả của hệ bất phương trình có nghiệm

a_i^T x \leq b_i, i=1,\ldots,n

nếu và chỉ nếu tồn tại bộ số \lambda_0,\lambda_1,\ldots,\lambda_n\geq 0 sao cho

\displaystyle a=\sum_{i=1}^n \lambda_i a_i, b=\lambda_0+\sum_{i=1}^n \lambda_i b_i

Chứng minh:

\Rightarrow“: Hiển nhiên

\Leftarrow“: Vì a^T x \leq b là hệ quả của hệ a_i^T x \leq b_i, i=1,\ldots,n nên hệ bất phương trình sau vô nghiệm

\mathcal{P}\begin{cases} a^T x>b \\ -a_i^T x \geq -b_i & i=1,\ldots,n\end{cases}

Áp dụng định lý đảo tổng quát và sử dụng hệ \mathcal{T}_1, ta có điều phải chứng minh (Lưu ý: do hệ a_i^T x \leq b_i, i=1,\ldots,n có nghiệm nên hệ \mathcal{T}_2 vô nghiệm).

Nhận xét:

  1. Định lý Farkas không thuần nhất chỉ ra hệ quả (bất kể suy ra bằng cách nào) của một hệ bất phương trình tuyến tính luôn luôn có thể suy ra bằng cách tổ hợp tuyến tính các bất đẳng thức của hệ bất phương trình đã cho và bất đẳng thức 0x<1.
  2. Nếu ta viết hệ bất phương trình trên dưới dạng Ax\leq B, trong đó A=[a_1,\ldots,a_n]^TB=[b_1,\ldots,b_n]^T, thì điều kiện cần và đủ có thể viết lại như sau: tồn tại \lambda=[\lambda_1,\ldots,\lambda_n]^T\geq 0 sao cho
    a=A^T\lambda, B^T\lambda\leq b.
  3. Nếu a^Tx\geq b là hệ quả của Ax\geq B. Có thể viết lại như sau -a^T x\leq-b là hệ quả của -Ax\leq -B. Điều kiện cần và đủ là tồn tại \lambda\geq 0 sao cho

-a=-A^T\lambda \Rightarrow a=A^T\lambda

-B^T\lambda\leq -b \Rightarrow B^T\lambda\geq b

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: