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

Learn & Enjoy …

Posts Tagged ‘điểm cực biên’

« Những bài viết trước

Phương pháp đơn hình (Simplex method) (1) – Bài toán QHTT, dạng chuẩn tắc và các định lý cơ bản

Đăng bởi tqlong on Tháng Hai 23, 2008

Định nghĩa 1 (Quy hoạch tuyến tính). Bài toán quy hoạch tuyến tính (linear programming) là bài toán tìm cực tiểu sau

\displaystyle\mathrm{Opt}(P)=\min_x\{c^Tx|Ax\geq b\}.

Xem thêm ở bài về bài toán đối ngẫu.

Nhận xét:

  1. Nếu cỡ của ma trận A là m\times n, ràng buộc Ax\geq b tương đương với m ràng buộc nhỏ
    a_i^Tx\geq b_i, i=1,\ldots m

    với a_i^T là dòng thứ i của ma trận A.

  2. Để cho tiện, trong loạt bài này ta kí hiệu a_i^T (chữ cái thường) là dòng thứ i của ma trận A, còn cột thứ j của ma trận A kí hiệu là A_j (chữ cái hoa).

Định nghĩa 2 (Dạng chuẩn tắc). Bài toán quy hoạch tuyến tính ở dạng chuẩn tắc (standard form) là bài toán tìm cực tiểu sau:

\displaystyle\mathrm{Opt}(P)=\min_x\{c^Tx|Ax= b,x\geq 0\}

Nhận xét:

  1. Dạng chuẩn tắc có thể đưa về dạng gốc bằng cách thiết lập ma trận như sau
    \displaystyle\mathrm{Opt}(P)=\min_x\{c^Tx|\widehat{A}x\geq \widehat{b}\}

    trong đó \widehat{A}=\left[\begin{array}{r}A\\-A\\I\end{array}\right], \widehat{b}=\left[\begin{array}{r}b\\-b\\ {0}\end{array}\right] ,

  2. Dạng gốc có thể đưa về dạng chuẩn tắc bằng cách thiết lập ma trận như sau
    \displaystyle\mathrm{Opt}(P)=\min_x\{\widehat{c}^Tz|\widehat{A}z= b,z\geq 0\}

    trong đó z=\left[\begin{array}{c}x^+\\x^-\\s\end{array}\right], \widehat{A} = \left[\begin{array}{rrr}A & -A & -I\end{array}\right], \widehat{c} = \left[\begin{array}{rrr}c & -c & 0\end{array}\right].

  3. Như vậy, hai dạng của bài toán quy hoạch tuyến tính là tương đương. Tuy nhiên, trong phương pháp đơn hình, người ta sử dụng dạng chuẩn tắc bởi dạng này có một số tính chất rất thuận lợi cho việc tìm ra điểm cực biên.

Định lý (hàm tuyến tính bị chặn đạt cực trị trong đa diện lồi). Nếu hàm tuyến tính bị chặn dưới trong đa diện lồi P thì nó đạt cực tiểu trong đa diện lồi đó. Đồng thời nếu đa diện lồi không chứa đường thẳng thì hàm tuyến tính đó đạt cực tiểu tại một trong các điểm cực biên.

Chứng minh: Xem trong bài cấu trúc của đa diện lồi.

Hệ quả: Với bài toán quy hoạch tuyến tính ở dạng chuẩn tắc, do điều kiệnx\geq 0 nên đa diện lồi tạo nên bởi các ràng buộc không chứa đường thẳng. Do đó, hàm tuyến tính phải đạt giá trị cực tiểu (nếu có) ở một trong các điểm cực biên.

Định nghĩa (nghiệm cơ sở): Điểm x gọi là nghiệm cơ sở (basic solution) của đa diện lồi P=\{x:Ax\geq b\} nếu có n ràng buộc được kích hoạt tại x độc lập tuyến tính, tức là tồn tại tập chỉ số I=\{i_1, \ldots, i_n\}

a_i^Tx=b_i, i\in I và \{a_i, i\in I\} độc lập tuyến tính.

Lưu ý: Nghiệm cơ sở có thể không phải là điểm nằm trong đa diện lồi.

Định nghĩa (nghiệm cơ sở chấp nhận được): Điểm x là nghiệm cơ sở chấp nhận được (basic feasible solution) của P nếu x\in P và x là nghiệm cơ sở của P.

Định lý (điều kiện của điểm cực biên của đa diện lồi): Cho điểm x là điểm thuộc đa diện lồi P=\{x:Ax\geq b\}, các mệnh đề sau đây tương đương

  1. x là điểm cực biên của P.
  2. x là đỉnh của P.
  3. x là nghiệm cơ sở chấp nhận được của P.

Chứng minh:

“1\Rightarrow 3“: Xem trong bài cấu trúc của đa diện lồi.

“3\Rightarrow 2“: Nếu x là nghiệm cơ sở chấp nhận được, tức là tồn tại I=\{i_1, \ldots, i_n\}

a_i^Tx=b_i, i\in I và \{a_i, i\in I\} độc lập tuyến tính.

Chọn c= \displaystyle -\sum_{i\in I} a_i, ta sẽ chứng minh hàm tuyến tính c^Tx đạt cực đại duy nhất trên P tại x. Thật vậy, xét một điểm y\in P, ta có

c^Ty=\displaystyle -\sum_{i\in I} a_i^Ty\leq \displaystyle -\sum_{i\in I} b_i = -\sum_{i\in I} a_i^Tx=c^Tx

Như vậy, hàm tuyến tính c^Tx đạt cực đại trên P tại x. Đồng thời ta cũng thấy dấu bằng không thể xảy ra trong bất đẳng thức này nếu y\neq x, vì nếu như vậy, ta sẽ có a_i^Ty=b_i,\forall i\in I, nhưng do \{a_i, i\in I\} độc lập tuyến tính nên điểm thỏa mãn n đẳng thức này chỉ có duy nhất 1 điểm x. Vậy c^Ty<c^Tx,\forall y\in P, y\neq x, tức là x là đỉnh của P.

“2\Rightarrow 1“: Xem trong bài siêu phẳng đỡ và điểm cực biên.

Nhận xét:

  1. Định lý chứng tỏ 3 khái niệm điểm cực biên, đỉnh, nghiệm cơ sở chấp nhận được là tương đương trong đa diện lồi. Ta có thể sử dụng các tính chất của cả ba khái niệm này cùng lúc.
  2. Điểm cực biên là khái niệm có tính chất hình học (điểm không nằm giữa hai điểm nào trong tập) rất khó kiểm tra (vì phải kiểm tra mọi cặp điểm) còn nghiệm cơ sở chấp nhận được lại là khái niệm rất dễ kiểm tra bằng thuật toán (điểm có n ràng buộc được kích hoạt).

Hệ quả: Do số tổ hợp chập n của m là hữu hạn nên ta có một thuật toán đơn giản sau để giải bài toán quy hoạch tuyến tính (dạng gốc)

  1. Lần lượt chọn từng bộ n ràng buộc, kiểm tra tính độc lập tuyến tính.
  2. Nếu bộ ràng buộc không độc lập tuyên tính quay lại bước 1 chọn bộ ràng buộc khác.
  3. Nếu bộ ràng buộc độc lập tuyến tính, giải hệ phương trình tương ứng của bộ ràng buộc này (coi như các ràng buộc được kích hoạt) để tìm ra nghiệm cơ sở x^* .
  4. Kiểm tra xem x^* có là nghiệm cơ sở chấp nhận được hay không? Nếu đúng thì tính giá trị của hàm tại điểm này, so sánh với giá trị tốt nhất đang có và thay đổi giá trị này nếu cần. Sau đó quay lại bước 1 chọn bộ ràng buộc khác.

Nhận xét:

  1. Thuật toán này không phải là thuật toán hiệu quả vì số lượng n ràng buộc trong m ràng buộc tăng theo hàm mũ.
  2. Tuy nhiên, thuật toán này chứng tỏ bài toán QHTT là bài toán giải được (decidable), nghĩa là thuật toán luôn dừng và cho ra kết quả (chỉ ra nghiệm hoặc chỉ ra không có nghiệm).

Định lý (điều kiện của nghiệm cơ sở của đa diện lồi ở dạng chuẩn tắc): Cho đa diện lồi P=\{x:Ax=b,x\geq 0\} và giả sử \{a_i^T, i=1,\ldots,m\} độc lập tuyến tính, điểm x là nghiệm cơ sở của P nếu và chỉ nếu tồn tại bộ chỉ số B(i),i=1,\ldots, m sao cho

  1. Ma trận B=\left[\begin{array}{rrr}A_{B(1)}&\ldots&A_{B(m)}\end{array}\right] gồm các cột tương ứng của ma trận A là ma trận khả nghịch.
  2. x_j=0,\forall j\neq B(1),\ldots,B(m).

Ta gọi ma trận B là ma trận cơ sở tương ứng của x.
Chứng minh:

“\Rightarrow“: Giả sử (1) và (2) đều xảy ra, ta sẽ chứng minh x là nghiệm cơ sở của P. Thật vậy, các ràng buộc được kích hoạt tại x là

a_i^Tx=b_i,\forall i=1,\ldots, m

x_j=e_j^Tx=0,\forall j\neq B(1),\ldots,B(m)

với e_j=\left[\begin{array}{rrrrr}0&\ldots&1&\ldots&0\end{array}\right]^T là véc tơ thứ j trong hệ cơ sở của hệ tọa độ Đềcác.

Các véctơ e_j không thể là tổ hợp tuyến tính của các véctơ a_i vì nếu như vậy, tức là tồn tại (\lambda_1,\ldots,\lambda_m)\neq 0 sao cho

\displaystyle\sum_{i=1}^m\lambda_i a_i^T=e_j^T

Suy ra

\displaystyle\sum_{i=1}^m\lambda_i b_i^T=0 ,

với b_i^T là các dòng của B vì j\neq B(1),\ldots,B(m), suy ra mâu thuẫn vì B khả nghịch. Vậy tại x có n ràng buộc độc lập tuyến tính, hay x là nghiệm cơ sở của P.

“\Leftarrow“: Giả sử x là nghiệm cơ sở của P, do có n ràng buộc độc lập tuyến tính được kích hoạt nên x là điểm duy nhất mà cả n ràng buộc này được kích hoạt. Giả sử các chỉ số B(1),\ldots,B(k) là các chỉ số mà x_{B(i)}\neq 0, i=1,\ldots, k. Rõ ràng k\leq m vì có ít nhất n-m ràng buộc dạng x_j\geq 0 được kích hoạt (do chỉ có m ràng buộc dạng a_i^Tx=b_i, i=1,\ldots,m đã được kích hoạt). Ta có

Ax = \displaystyle\sum_{i=1}^n x_i A_i=\sum_{i=1}^k x_{B(i)} A_{B(i)}=b

Ta sẽ chứng minh các cột A_{B(1)},\ldots, A_{B(k)} độc lập tuyến tính. Thật vậy, giả sử tồn tại bộ số \lambda_{B(i)}, i=1,\ldots,k không đồng thời bằng {0} sao cho

\displaystyle\sum_{i=1}^k\lambda_{B(i)} A_{B(i)}=0

Suy ra nếu đặt \lambda=\left[\begin{array}{rrr}\lambda_1&\ldots&\lambda_n\end{array}\right]^T sao cho \lambda_i = 0, \forall i\neq B(1),\ldots, B(k) thì

A(x+\lambda) = \displaystyle\sum_{i=1}^k (x_{B(i)}+\lambda_{B(i)}) A_{B(i)}=b

Nghĩa là véc tơ x không phải là véc tơ duy nhất kích hoạt n ràng buộc độc lập tuyến tính, mâu thuẫn. Vậy các cột A_{B(1)},\ldots, A_{B(k)} độc lập tuyến tính. Hơn nữa, do m hàng của ma trận A độc lập tuyến tính nên không gian tuyến tính tạo bởi các cột của A phải là \mathbb{R}^m. Suy ra, nếu k<m ta có thể chọn thêm các cột A_{B(k+1)},\ldots,A_{B(m)} khác để tạo nên một bộ cơ sở của \mathbb{R}^m. Bộ chỉ số B(1),\ldots, B(m) rõ ràng thỏa mãn hai điều kiện (1) và (2).

Nhận xét: Đối với bài toán QHTT ở dạng chuẩn tắc, thuật toán trên có thể biến đổi như sau:

  1. Chọn một bộ chỉ số B(1),\ldots,B(m). Kiểm tra xem ma trận B có khả nghịch không.
  2. Nếu ma trận B khả nghịch, tính x_B=B^{-1}b với
    x_B=\left[\begin{array}{rrr}x_{B(1)}&\ldots&x_{B(m)}\end{array}\right] .
  3. Kiểm tra điều kiện x_B\geq 0, nếu đúng thì đặt x_j=0,\forall j\neq B(1),\ldots,B(m). Khi đó x là nghiệm cơ sở chấp nhận được của P.
  4. Tính giá trị của hàm mục tiêu tại x, thay đổi giá trị tốt nhất hiện tại nếu cần. Rồi chuyển về bước 1 chọn bộ chỉ số khác.

Đăng trong Quy hoạch tuyến tính | Tagged: , , , , , , , , , , | Leave a Comment »

Tập lồi (7) – Cấu trúc của đa diện lồi

Đăng bởi tqlong on Tháng Hai 14, 2008

Định nghĩa (đa diện lồi): Tập P=\{x\in \mathbb{R}^n :Ax\leq b\} gọi là đa diện lồi (polyhedra) trong \mathbb{R}^n.

Nhận xét:

  1. Đa diện lồi là tập đóng, lồi.
  2. \mathbb{R}^n cũng là đa diện lồi khi ta chọn A=0, b\geq 0.
  3. Các ràng buộc của bài toán quy hoạch tuyến tính tạo nên đa diện lồi.

Định lý (cấu trúc của đa diện lồi): Đa diện lồi P=\{x\in \mathbb{R}^n :Ax\leq b\} luôn có thể biểu diễn dưới dạng

P=P^*+L

trong đó P^* là tập đóng lồi không chứa đường thẳng, L=\mathrm{Null}A là không gian con của \mathbb{R}^n.

Lưu ý: Nhắc lại khái niệm trong đại số tuyến tính:

  1. \mathrm{Null}A=\{x:Ax=0\} (nhân của ma trận, còn kí hiệu là \mathrm{Ker}A).
  2. \mathrm{Im}A=\{y:y=Ax\} (không gian con tạo bởi các cột của A).
  3. Tính chất: \mathrm{Im}A^T=(\mathrm{Null}A)^\perp.

Chứng minh: Ta sẽ chứng minh theo thứ tự sau

  1. Nếu x\in P, đường thẳng \{x(t):x+th, x\in P,t\in \mathbb{R},h\neq 0\}\subset P nếu và chỉ nếu h\in\mathrm{Null}A.
  2. Đặt P^*=P\cap\mathrm{Im}A^T=\{x\in \mathrm{Im}A^T,Ax\leq b\} thì P=P^*+\mathrm{Null}A và P^* không chứa đường thẳng.

Chứng minh (1): Nếu h\in\mathrm{Null}A, ta có A^T(x+th)=A^Tx\leq b,\forall t\in\mathbb{R}.

Ngược lại, nếu A(x+th)\leq b,\forall t, tức là a_i^T(x+th)\leq b_i,\forall i,t (a_i là dòng thứ i của A). Xét 2 trường hợp:

  • a_i^Th>0, rõ ràng khi t\rightarrow \infty ta sẽ có a_i^T(x+th)>b_i.
  • a_i^Th<0 thì khi t\rightarrow -\infty ta cũng có a_i^T(x+th)>b_i.

Vậy chỉ còn khả năng a_i^Th=0,\forall i, tức là h\in\mathrm{Null}A.

Chứng minh (2): Rõ ràng P^*\subset P nên P^*+\mathrm{Null}A\subset P theo (1). Ngược lại, nếu x\in P, chiếu x xuống \mathrm{Im}A^T, ta có

x=y+z, y\in \mathrm{Im}A^T, z\in\mathrm{Null}A

Ta thấy y=x-z nên y\in P theo (1), như vậy y\in P\cap\mathrm{Im}A^T=P^*, suy ra x\in P^*+\mathrm{Null}A. Tức là P\subset P^*+\mathrm{Null}A. Kết luận P=P^*+\mathrm{Null}A.

Để thấy P^* không chứa đường thẳng, để ý rằng P^*\subset P nên mọi đường thẳng trong P^* cũng là đường thẳng trong P, nghĩa là hướng của đường thẳng này nằm trong \mathrm{Null} A, vô lý vì P^* nằm trong không gian trực giao với \mathrm{Null} A.

Nhận xét:

  1. Ta thấy P^* là đa diện lồi trong không gian con của \mathbb{R}^n nên nó cũng là đa diện lồi trong \mathbb{R}^n (ngoài điều kiện Ax\leq b ta thêm vào các điều kiện a_i^Tx\leq 0,-a_i^Tx\leq 0,\forall i).
  2. P không chứa đường thằng nếu và chỉ nếu \mathrm{Null}A=\{0\}.

Định lý (cấu trúc của đa diện lồi có điểm cực biên): Nếu P=\{x\in \mathbb{R}^n :Ax\leq b\} là đa diện lồi không chứa đường thẳng thì P có thể biểu diễn dưới dạng

P=\mathrm{Conv}V+\mathrm{Cone}R

trong đó V=\mathrm{Ext}P hữu hạn, R là tập hữu hạn các véctơ và \mathrm{Cone}R=\{r:Ar\leq 0\}.

Chứng minh: Ta sẽ chứng minh theo thứ tự sau

  1. Nếu r\neq 0 sao cho tồn tại x\in P:x+tr\in P,\forall t>0 thì Ar\leq 0.
  2. Hơn nữa, với r như vậy, với mọi y\in P, y+tr\in P,\forall t>0.
  3. P=\mathrm{ConvExt}P+\{r:Ar\leq 0\}.
  4. Tập V=\mathrm{Ext}P hữu hạn.
  5. Tập \{r:Ar\leq 0\} là tập tất cả các tổ hợp nón của một tập hữu hạn véctơ R=\{r_1,\ldots,r_k\}.

Chứng minh (1): Ta có A(x+tr)\leq b,\forall t>0, tức là a_i^T(x+tr)\leq b_i,\forall i, t>0. Nếu a_i^Tr>0 thì khi t\rightarrow \infty, ta sẽ có a_i^T(x+tr)>b_i. Như vậy, ta phải có a_i^Tr\leq 0,\forall i, tức là Ar\leq 0.

Chứng minh (2): Vì Ar\leq 0, với mọi y\in P, t>0, ta có A(y+tr)\leq Ay\leq b, tức là toàn bộ tia \{y(t)=y+tr,t>0\} \subset P.

Chứng minh (3): Rõ ràng \mathrm{ConvExt}P\subset P nên \mathrm{ConvExt}P+\{r:Ar\leq 0\}\subset P theo (2). Ngược lại, nếu x\in P, ta sẽ chứng minh x\in\mathrm{ConvExt}P+\{r:Ar\leq 0\} bằng quy nạp theo n=\dim P.

Cơ sở: với n=0 tức là P=\{x\} định lý đúng.

Quy nạp: giả sử định lý đúng với n<k, ta sẽ chứng minh định lý cũng đúng với n=k. Thật vậy, chọn một véctơ r\neq 0, r\in\{r:Ar\leq 0\}. Vì P không chứa đường thẳng nên Ar\neq 0 (do \mathrm{Null}A=\{0\} theo định lý trên). Đồng thời, tia \{x(t)=x-tr, t>0\} phải thoát ra khỏi A ở một điểm x^*\in\partial P nào đó, nếu không P sẽ chứa toàn bộ đường thẳng \{x(t)=x+tr,t\in \mathrm{R}\}. Xét siêu phẳng \Pi=\{x:f^Tx=a\} đỡ P ở x^*, đặt Q=\Pi\cap P. Rõ ràng Q cũng là đa diện lồi, không chứa đường thẳng, theo giả thiết quy nạp điểm x^* phải thuộc vào tập \mathrm{ConvExt}Q+\{r:Ar\leq 0,f^Tr=0\} (do ta thêm một điều kiện f^Tx=a vào đa diện lồi). Rõ ràng

\mathrm{ConvExt}Q\subset\mathrm{ConvExt}P

\{r:Ar\leq 0,f^Tr=0\}\subset\{r:Ar\leq 0\}

tức là x^*\in \mathrm{ConvExt}Q+\{r:Ar\leq 0,f^Tr=0\}\subset\mathrm{ConvExt}P+\{r:Ar\leq 0\}. Suy ra x=x^*+tr \in\mathrm{ConvExt}P+\{r:Ar\leq 0\}.

Chứng minh (4): Kết luận (4) là hệ quả của bổ đề sau đây

Bổ đề (điều kiện cực biên của đa diện lồi): Nếu x là điểm cực biên của P, trong các ràng buộc được kích hoạt tại x, phải có n ràng buộc độc lập tuyến tính, tức là có

a_{i_1}^Tx=b_{i_1},\ldots,a_{i_n}^Tx=b_{i_n} và (a_{i_1},\ldots,a_{i_n}) độc lập tuyến tính.

Chứng minh: Thật vậy, giả sử ngược lại, chỉ có k<n ràng buộc độc lập tuyến tính. Như vậy, tồn tại véctơ h\neq 0 sao cho h trực giao với tất cả a_{i_j} của các ràng buộc được kích hoạt tại x. Xét điểm x(\epsilon)=x+\epsilon h, \epsilon\in \mathbb{R} . Rõ ràng, các ràng buộc được kích hoạt tại x vẫn được kích hoạt tại x(\epsilon), ngoài ra, với |\epsilon|>0 đủ nhỏ, các ràng buộc không được kích hoạt tại x vẫn được thỏa mãn tại x(\epsilon), như vậy x+\epsilon h,x-\epsilon h\in P với |\epsilon|>0 đủ nhỏ, tức là x không phải là điểm cực biên, mâu thuẫn.

Do số lượng các bộ n ràng buộc trong m ràng buộc (m là số dòng của ma trận A) là \mathrm{C}_n^m hữu hạn nên số điểm cực biên, |\mathrm{Ext}P|, cũng là hữu hạn.

Chứng minh (5): Để chứng minh kết luận (5) ta cũng dùng cách quy nạp như chứng minh (3), tuy nhiên, ta không chọn siêu phẳng đỡ bất kì mà chọn siêu phẳng \Pi_i tạo bởi một điều kiện a_i^Tx\leq b_i bị kích hoạt tại x^* (tại x^*\in\partial P phải có điều kiện được kích hoạt, nếu không nó phải nằm trong \mathrm{rint}P). Theo giả thiết quy nạp,

x^* \in \mathrm{Conv}Ext(\Pi_i\cap P)+\mathrm{Cone}R_i

với R_i là tập hữu hạn. Như vậy

x=x^*+th\in\mathrm{Conv}\mathrm{Ext}(\Pi_i\cap P)+\mathrm{Cone}(R_i\cup\{r\}).

Do số ràng buộc, m, là hữu hạn nên nếu ta đặt R=\displaystyle\cup_{i=1}^m R_i\cup\{r\}, thì

x\in\mathrm{Conv}\mathrm{Ext}P+\mathrm{Cone}R.

Nhận xét:

  1. Qua hai định lý trên, tổng hợp lại, ta luôn có khẳng định sau: Đa diện lồi P=\{x:Ax\leq b\} luôn có thể viết dưới dạng
    P=\mathrm{Conv}V+\mathrm{Cone}R=\left\{\displaystyle \sum_{i=1}^I\lambda_i v_i+\sum_{j=1}^J\mu_j r_j\right\} (*)

    trong đó \lambda_i,\mu_j\geq 0, \displaystyle \sum_{i=1}^I\lambda_i=1 và I, J hữu hạn.

  2. Có thể chứng minh mọi tập có dạng (*) đều là đa diện lồi.
  3. Nếu coi biểu diễn \{x:Ax\leq b\} là biểu diễn từ phía ngoài (A,b ràng buộc P) thì biểu diễn (*) là biểu diễn từ phía trong, nghĩa là trong P có một số hữu hạn véctơ mà tất cả các véctơ khác có thể biểu diễn bằng các véctơ này.
  4. Với tập đóng, lồi và bị chặn, ta đã biết P=\mathrm{ConvExt}P.
  5. Hai cách biểu diễn như vậy giúp hiểu rõ cấu trúc của đa diện lồi, đồng thời còn giúp trả lời các vấn đề mà nếu chỉ sử dụng biểu diễn ngoài rất khó giải thích (xem tiếp ở dưới).
  6. Bổ đề về điều kiện cực biên của đa diện lồi là cơ sở của phương pháp đơn hình giải bài toán quy hoạch tuyến tính.

Định lý (các phép biến đổi đa diện lồi): Nếu P là đa diện lồi thì

  1. Ảnh của đa diện lồi qua ánh xạ affine ngược cũng là đa diện lồi.
  2. Ảnh của đa diện lồi qua ánh xạ affine cũng là đa diện lồi.
  3. Giao của hai đa diện lồi là đa diện lồi.
  4. Tổng của hai đa diện lồi là đa diện lồi (hay tổng quát hơn tổ hợp tuyến tính các đa diện lồi cũng là đa diện lồi).

Chứng minh: (1) và (3) là hệ quả trực tiếp của biểu diễn ngoài, (2) và (4) là hệ quả trực tiếp của biểu diễn trong vì đây là các phép toán biến đổi tập lồi và nón lồi (Lưu ý, rất khó chứng minh (2) và (4) nếu chỉ sử dụng biểu diễn ngoài).

Định lý (hàm tuyến tính bị chặn đạt cực trị trong đa diện lồi): Nếu hàm tuyến tính bị chặn trên (chặn dưới) trong đa diện lồi P thì nó đạt cực đại (cực tiểu) trong đa diện lồi đó.

Chứng minh: Nếu f^Tx bị chặn trên trong đa diện lồi P=\mathrm{Conv}V+\mathrm{Cone}R thì với mọi r\in\mathrm{Cone}R ta phải có f^Tr\leq 0. Thật vậy, nếu f^Tr>0, rõ ràng với mọi x\in P ta có f^T(x+tr) không bị chặn khi t\rightarrow \infty. Suy ra, với mọi x\in P, x=\displaystyle \sum_{i=1}^I\lambda_i v_i+r, r\in\mathrm{Cone}R ta có

\displaystyle f^T x=\sum_{i=1}^I\lambda_i f^Tv_i+f^Tr\leq\sum_{i=1}^I\lambda_i f^Tv_i\leq\max_{v_i\in V}f^Tv_i

Tức là cực đại của f^Tx trên V cũng là cực đại của f^Tx trên P.

Nhận xét:

  1. Định lý đảm bảo bài toán quy hoạch tuyến tính luôn có nghiệm nếu hàm mục tiêu bị chặn.
  2. Khi P không chứa đường thẳng, cực đại của hàm mục tiêu luôn có thể đạt được ở một trong các điểm cực biên.
  3. Với bài toán quy hoạch tuyến tính ở dạng chuẩn tắc
    \displaystyle \mathrm{Opt}(P)=\max \{c^Tx: Ax=b,x\geq 0\}

    các ràng buộc tạo nên tập nghiệm luôn có điểm cực biên (không chứa đường thẳng) vì các biến đều có ràng buộc không âm.

Đăng trong Giải tích lồi, Quy hoạch tuyến tính | Tagged: , , , , , , , , , , , , , , , , | Leave a Comment »

« Những bài viết trước