Bài giảng 10: Đa diện (Polytopes)

(Nếu công thức chưa load được hoặc mờ, các bạn ấn refresh để công thức hiện và rõ nét hơn nhé!)

Phần này nghiên cứu các tính chất hình học của một lớp tập hợp lồi chặt chẽ quan trọng gọi là polytopes. Các tập hợp này xuất hiện trong nhiều ứng dụng, bao gồm lý thuyết trò chơi, lập trình tuyến tính và các bài toán tối ưu tổng quát hơn, chẳng hạn như thiết kế điều khiển phản hồi cho các hệ thống kỹ thuật.

Một đa diện lồi (polytope) trong không gian $\mathbb{R}^n$ là bao lồi của một tập hợp hữu hạn các điểm. Trong $\mathbb{R}^2$ , một đa diện lồi chính là một đa giác. Trong $\mathbb{R}^3$ , một đa diện lồi được gọi là một khối đa diện. Các đặc điểm quan trọng của một khối đa diện bao gồm mặt, cạnh và đỉnh. Ví dụ, hình lập phương có 6 mặt hình vuông, 12 cạnh và 8 đỉnh. Các định nghĩa sau đây cung cấp thuật ngữ để áp dụng không chỉ cho các không gian hai và ba chiều, mà còn cho không gian nhiều chiều hơn. Hãy nhớ rằng: số chiều của một tập hợp trong $\mathbb{R}^n$ là số chiều của mặt phẳng phẳng nhỏ nhất chứa nó. Ngoài ra, cần lưu ý rằng một đa diện lồi là một tập lồi compact đặc biệt, vì một tập hữu hạn trong $\mathbb{R}^n$ là compact, và bao lồi của tập này cũng compact – theo định lý đã nêu trong phần “Thuật ngữ và sự thật trong tô pô”.

Định nghĩa

Cho  là một tập con lồi, compact trong . Một tập con không rỗng  được gọi là một mặt (đúng nghĩa - proper) của  nếu  và tồn tại một siêu phẳng  sao cho:  và hoặc  hoặc . Siêu phẳng  được gọi là siêu phẳng đỡ của . Nếu , thì  được gọi là một mặt -chiều của .

Nếu  là một đa diện có chiều là , thì  được gọi là một đa diện -chiều. Một 0-face của  được gọi là một đỉnh. Một 1-face là một cạnh. Một mặt có chiều k−1k-1 được gọi là một mặt chính của .

Ví dụ 1: Giả sử $S$ là một khối lập phương trong không gian $\mathbb{R}^3$ . Khi một mặt phẳng $H$ được tịnh tiến trong $\mathbb{R}^3$ cho đến khi nó vừa chạm vào (tức là đỡ) khối lập phương nhưng không cắt vào bên trong của khối, sẽ có ba khả năng xảy ra cho giao điểm $H\cap S$ , tùy theo hướng của $H$ . Xem hình 1.

$H\cap S$ có thể là một mặt vuông 2 chiều (tức là một mặt chính) của khối lập phương.
$H\cap S$ có thể là một cạnh 1 chiều của khối lập phương.
$H\cap S$ có thể là một đỉnh 0 chiều của khối lập phương.

Phần lớn các ứng dụng của đa diện liên quan đến các đỉnh theo một cách nào đó, vì chúng có một thuộc tính đặc biệt được nêu ra trong định nghĩa sau.

Định nghĩa
Gọi  là một tập lồi. Một điểm  được gọi là điểm cực trị của  nếu  không nằm trong nội điểm của bất kỳ đoạn thẳng nào nằm trong . Cụ thể hơn, nếu  và  (nghĩa là  nằm giữa  và ), thì phải có  hoặc . Tập hợp tất cả các điểm cực trị của  được gọi là biên dạng của .

Một đỉnh của bất kỳ tập lồi compact nào $S$ thì tự động là một điểm cực trị của $S$ . Thực tế này sẽ được chứng minh trong quá trình chứng minh định lý 14. Khi làm việc với một đa diện, giả sử $P=\text{conv}\,\{\mathbf{v}_1,\dots,\textbf{v}_k\}$ với $\textbf{v}_1,\dots,\textbf{v}_k\in\mathbb{R}^n$ , thì thường rất hữu ích khi biết rằng các điểm $\textbf{v}_1,\dots,\textbf{v}_k$ là các điểm cực trị của $P$ . Tuy nhiên, danh sách này đôi khi có thể chứa những điểm dư thừa. Ví dụ, một vector $\textbf{v}_i$ nào đó có thể là trung điểm của một cạnh trong đa diện – trong trường hợp đó, $\textbf{v}_i$ thực ra không cần thiết để sinh ra bao lồi.

Định nghĩa sau đây mô tả tính chất của các đỉnh sao cho chúng đều là điểm cực trị.

Định nghĩa
Tập hợp  được gọi là biểu diễn tối thiểu của đa diện  nếu:
•	, và
•	với mỗi , ta có .

Mọi đa diện đều có một biểu diễn tối thiểu. Bởi vì nếu $P=\text{conv}\,\{\textbf{v}_1,\dots,\textbf{v}_k\}$ và nếu tồn tại một điểm $\textbf{v}_i$ là tổ hợp lồi của các điểm còn lại, thì $\textbf{v}_i$ có thể được loại bỏ khỏi tập mà không làm thay đổi bao lồi. Quá trình này có thể được lặp lại cho đến khi còn lại biểu diễn tối thiểu. Người ta có thể chứng minh rằng biểu diễn tối thiểu là duy nhất.

ĐỊNH LÝ 14
Giả sử  là biểu diễn tối thiểu của đa diện . Khi đó, ba mệnh đề sau là tương đương:
a.	.
b.	 là đỉnh của .
c.	 là điểm cực trị của .

Chứng minh: $(a)\Rightarrow(b)$ : Giả sử $\mathbf{p}\in M$ và đặt $Q=\text{conv}\,\{\textbf{v}:\mathbf{v}\in M,\,\mathbf{v}\ne\textbf{p}\}$ . Theo định nghĩa của $M$ , ta có $\mathbf{p}\notin Q$ , và vì $Q$ là tập compact, định lý 13 đảm bảo sự tồn tại của một siêu phẳng $H'$ tách rời hoàn toàn $\{\mathbf{p}\}$ và $Q$ . Gọi $H$ là siêu phẳng đi qua $\mathbf{p}$ và song song với $H'$ . Xem hình 2.

Khi đó $Q$ nằm trong một trong các nửa không gian đóng $H^+$ được giới hạn bởi $H$ , do đó $P\subseteq H^+$ . Vậy $H$ là một siêu phẳng đỡ $P$ tại $\mathbf{p}$ . Hơn nữa, $\mathbf{p}$ là điểm duy nhất của $P$ nằm trên $H$ , nên $H\cap P=\{\mathbf{p}\}$ , và $\mathbf{p}$ là một đỉnh của $P$ .

$(b)\Rightarrow(c)$ : Giả sử $\mathbf{p}$ là một đỉnh của $P$ . Khi đó tồn tại một siêu phẳng $H=[f:d]$ sao cho $H\cap P=\{\mathbf{p}\}$ và $f(P)\geq d$ . Nếu $\mathbf{p}$ không phải là một điểm cực biên, thì tồn tại các điểm phân biệt $\mathbf{x}$ và $\mathbf{y}$ trong $P$ sao cho $\mathbf{p}=(1-c)\mathbf{x}+c\mathbf{y}$ với $0<c<1$ . Khi đó:

$(1-c)\mathbf{x}=\mathbf{p}-c\mathbf{y}$ và $(1-c)f(\mathbf{x})=d-cf(\mathbf{y})$ vì $f(\mathbf{p})=d$

Suy ra:

$f(\mathbf{x})=\frac{d-cf(\mathbf{y})}{1-c}\geq d$ vì $f(\mathbf{x})\geq d$

Tuy nhiên, khi đó $d-cf(\mathbf{y})\geq d(1-c)$ và $cf(\mathbf{y})\leq d-d(1-c)=cd$ nên $f(\mathbf{y})\leq d$ . Mặt khác, vì $\mathbf{y}\in P$ , nên $f(\mathbf{y})\geq d$ . Suy ra $f(\mathbf{y})=d$ , và do đó $\mathbf{y}\in H\cap P$ . Điều này mâu thuẫn với giả thiết rằng $\mathbf{p}$ là một đỉnh, tức là điểm duy nhất của $P$ thuộc $H$ . Vậy $\mathbf{p}$ phải là một điểm cực biên. (Lưu ý rằng phần này của chứng minh không phụ thuộc vào việc $P$ là một đa diện. Nó đúng với mọi tập lồi compact.)

$(c)\Rightarrow(a)$ : Rõ ràng mọi điểm cực biên của $P$ phải là một phần tử của $M$ .

Ví dụ 2: Hãy nhớ rằng biên dạng (profile) của một tập $S$ là tập hợp các điểm cực biên của $S$ . Định lý 14 cho thấy rằng biên dạng của một đa giác trong $\mathbb{R}^2$ chính là tập các đỉnh. Xem hình 3. Biên dạng của một quả cầu đóng là biên của nó. Một tập mở thì không có điểm cực biên, nên biên dạng của nó là rỗng. Một nửa không gian đóng cũng không có điểm cực biên, nên biên dạng của nó cũng rỗng.

Bài tập 24 yêu cầu bạn chứng minh rằng một điểm $\mathbf{p}$ trong tập lồi $S$ là một điểm cực biên của $S$ nếu và chỉ nếu, khi loại bỏ $\mathbf{p}$ khỏi $S$ , các điểm còn lại vẫn tạo thành một tập lồi. Từ đó suy ra rằng nếu $S^\ast$ là bất kỳ tập con nào của $S$ sao cho $\text{conv}\,S^\ast=S$ , thì $S^\ast$ phải chứa biên dạng của $S$ . Các tập trong Ví dụ 2 cho thấy rằng, trong tổng quát, $S^\ast$ có thể cần phải lớn hơn biên dạng của $S$ . Tuy nhiên, nếu $S$ là tập compact, thì ta thực sự có thể lấy $S^\ast$ chính là biên dạng của $S$ , như Định lý 15 sẽ chỉ ra. Do đó, mọi tập lồi compact không rỗng $S$ đều có ít nhất một điểm cực biên, và tập hợp tất cả các điểm cực biên là tập con nhỏ nhất của $S$ mà bao lấy $S$ bằng vỏ lồi của nó.

Định lý 15
Cho  là một tập lồi compact không rỗng. Khi đó  là vỏ lồi của biên dạng của nó (tức là tập hợp các điểm cực biên của ).

Chứng minh: Chứng minh được thực hiện bằng phương pháp quy nạp theo chiều của tập $S$ .

Một ứng dụng quan trọng của định lý 15 là định lý sau đây. Đây là một trong những kết quả lý thuyết then chốt trong sự phát triển của quy hoạch tuyến tính. Các hàm tuyến tính là liên tục, và các hàm liên tục luôn đạt được giá trị lớn nhất và nhỏ nhất trên một tập compact. Ý nghĩa của định lý 16 là: với các tập lồi compact, giá trị lớn nhất (và nhỏ nhất) thực sự đạt được tại một điểm cực biên của $S$ .

Định lý 16
Cho  là một hàm tuyến tính được xác định trên một tập lồi compact không rỗng . Khi đó tồn tại các điểm cực biên  và  của  sao cho:
.

Chứng minh: Giả sử rằng $f$ đạt giá trị lớn nhất $m$ trên $S$ tại một điểm $\mathbf{v}'\in S$ . Nghĩa là $f(\mathbf{v'})=m$ . Chúng ta cần chứng minh rằng tồn tại một điểm cực biên trong $S$ cũng thỏa mãn điều này. Theo định lý 15, $\mathbf{v'}$ là một tổ hợp lồi của các điểm cực biên của $S$ . Tức là, tồn tại các điểm cực biên $\mathbf{v}_1,\ldots,\mathbf{v}_k$ của $S$ và các hệ số không âm $c_1,\ldots,c_k$ sao cho:

$\mathbf{v}_0=c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k$ với $c_1+\cdots+c_k=1$

Nếu không có điểm cực biên nào của $S$ thỏa mãn $f(\mathbf{v})=m$ , thì:

$f(\mathbf{v}_i)<m$ với mọi $i=1,\ldots,k$

Vì $f$ là tuyến tính, ta có:

$m=f(\mathbf{v'})=f(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k)=c_1 f(\mathbf{v}_1)+\cdots+c_k f(\mathbf{v}_k)$

Nhưng vì $f(\mathbf{v}_i)<m$ với mọi $i$ , nên:

$c_1 f(\mathbf{v}_1)+\cdots+c_k f(\mathbf{v}_k)<c_1 m+\cdots+c_k m=m(c_1+\cdots+c_k)=m$

Điều này mâu thuẫn với giả thiết $f(\mathbf{v'})=m$ . Do đó, phải tồn tại ít nhất một điểm cực biên $\bar{\mathbf{v}}$ của $S$ sao cho $f(\bar{\mathbf{v}})=m$ .

Chứng minh cho $\bar{\mathbf{w}}$ (đạt giá trị nhỏ nhất) cũng tương tự.

Ví dụ 3: Cho các điểm $\mathbf{p}_1=\begin{bmatrix}-1\\0\end{bmatrix},\,\mathbf{p}_2=\begin{bmatrix}3\\1\end{bmatrix}$ , và $\mathbf{p}_3=\begin{bmatrix}1\\2\end{bmatrix},$ thuộc $\mathbb{R}^2$ , đặt $S=\text{conv}\,\{\mathbf{p}_1,\mathbf{p}_2,\mathbf{p}_3\}$ Với mỗi hàm tuyến tính $f$ , hãy tìm giá trị lớn nhất $m$ của $f$ trên tập $S$ , và tìm tất cả các điểm $\mathbf{x}$ trong $S$ sao cho $f(\mathbf{x})=m$ .

a) $f_1(x_1,x_2)=x_1+x_2$

b) $f_2(x_1,x_2)=-3x_1+x_2$

c) $f_3(x_1,x_2)=x_1+2x_2$

Giải:

a) $f_1(\mathbf{p}_1)=-1,\,f_1(\mathbf{p}_2)=4,\,f_1(\mathbf{p}_3)=3$ , vì vậy $m_1=4$ . Vẽ đồ thị đường thẳng $f_1(x_1,x_2)=m_1$ , tức là $x_1+x_2=4$ , và lưu ý rằng $\mathbf{x}=\mathbf{p}_2$ là điểm duy nhất trong $S$ mà tại đó $f_1(\mathbf{x})=4$ . Xem hình 4(a).

b) $f_2(\mathbf{p}_1)=3,\,f_2(\mathbf{p}_2)=-8,\,f_2(\mathbf{p}_3)=-1$ , vì vậy $m_2=3$ . Vẽ đồ thị đường thẳng $f_2(x_1,x_2)=m_2$ , tức là $-3x_1+x_2=3$ , và lưu ý rằng $\mathbf{x}=\mathbf{p}_1$ là điểm duy nhất trong $S$ mà tại đó $f_2(\mathbf{x})=3$ . Xem hình 4(b).

c) $f_3(\mathbf{p}_1)=-1,\,f_3(\mathbf{p}_2)=5,\,f_3(\mathbf{p}_3)=5$ , vì vậy $m_3=5$ . Vẽ đồ thị đường thẳng $f_3(x_1,x_2)=m_3$ , tức là $x_1+2x_2=5$ . Ở đây, $f_3$ đạt giá trị lớn nhất tại $\mathbf{p}_2$ , tại $\mathbf{p}_3$ , và tại mọi điểm trong bao lồi của $\mathbf{p}_2$ và $\mathbf{p}_3$ . Xem hình 4(c).

Tình huống minh họa trong ví dụ 3 đối với $\mathbb{R}^2$ cũng áp dụng cho các không gian có số chiều cao hơn. Giá trị lớn nhất của một hàm tuyến tính $f$ trên một đa diện $P$ xảy ra tại giao điểm của một siêu phẳng đỡ và $P$ . Giao điểm này hoặc là một điểm cực trị duy nhất của $P$ , hoặc là bao lồi của hai hay nhiều điểm cực trị của $P$ . Trong cả hai trường hợp, giao điểm đó là một đa diện, và các điểm cực trị của nó tạo thành một tập con của các điểm cực trị của $P$ .

Theo định nghĩa, một đa diện là bao lồi của một tập hợp hữu hạn các điểm. Đây là cách biểu diễn tường minh của đa diện vì nó xác định rõ các điểm trong tập hợp. Một đa diện cũng có thể được biểu diễn ngầm định như là giao của một số hữu hạn các nửa không gian đóng. Ví dụ 4 minh họa điều này trong $\mathbb{R}^2$ .

Ví dụ 4: Cho

$\mathbf{p}_1=\begin{bmatrix}0\\1\end{bmatrix},\quad\mathbf{p}_2=\begin{bmatrix}1\\0\end{bmatrix},\quad\mathbf{p}_3=\begin{bmatrix}3\\2\end{bmatrix}$

thuộc $\mathbb{R}^2$ , và đặt $S=\text{conv}\,\{\mathbf{p}_1,\mathbf{p}_2,\mathbf{p}_3\}$ . Một phép đại số đơn giản cho thấy đường thẳng đi qua $\mathbf{p}_1$ và $\mathbf{p}_2$ được cho bởi $x_1+x_2=1,$ , và $S$ nằm về phía của đường thẳng này nơi

$x_1+x_2\geq 1$ , hoặc tương đương, $-x_1-x_2\leq-1$ .

Tương tự, đường thẳng đi qua $\mathbf{p}_2$ và $\mathbf{p}_3$ là $x_1-x_2=1$ , và $S$ nằm về phía

$x_1-x_2\leq 1$

Ngoài ra, đường thẳng đi qua $\mathbf{p}_3$ và $\mathbf{p}_1$ là $-x_1+3x_2=3$ , và $S$ nằm về phía

$-x_1+3x_2\leq 3$

Xem hình 5.

Do đó, $S$ có thể được mô tả là tập nghiệm của hệ bất phương trình tuyến tính:

$\begin{matrix}-x_1-x_2&\leq&-1\\x_1-x_2&\leq&1\\-x_1+3 x_2&\leq&3\\\end{matrix}$

Hệ này có thể được viết dưới dạng $A\mathbf{x}\leq\mathbf{b}$ , trong đó:

$A=\begin{bmatrix}-1&-1\\1&-1\\-1&3\end{bmatrix},\quad\mathbf{x}=\begin{bmatrix}x_1\\x_2\end{bmatrix},\quad\mathbf{b}=\begin{bmatrix}-1\\1\\3\end{bmatrix}.$

Lưu ý rằng bất đẳng thức giữa hai vectơ, chẳng hạn như $A\mathbf{x}\leq\mathbf{b}$ , được hiểu là áp dụng cho từng thành phần tương ứng trong các vectơ đó.

Ví dụ 5: Cho $P$ là tập hợp các điểm trong $\mathbb{R}^2$ thỏa mãn $A\mathbf{x}\leq\mathbf{b}$ , trong đó

$A=\begin{bmatrix}1&3\\1&1\\3&2\end{bmatrix},\quad\mathbf{b}=\begin{bmatrix}18\\8\\21\\\end{bmatrix}$

và $\mathbf{x}\geq 0$ . Hãy tìm biểu diễn tối thiểu của $P$ .

Giải: Điều kiện $\mathbf{x}\geq 0$ đặt $P$ trong góc phần tư thứ nhất của $\mathbb{R}^2$ , đây là một điều kiện điển hình trong các bài toán lập trình tuyến tính. Ba bất đẳng thức trong $A\mathbf{x}\leq\mathbf{b}$ liên quan đến ba đường biên sau:

$x_1+3x_2=18$
$x_1+x_2=8$
$3x_1+2x_2=21$

Cả ba đường này đều có hệ số góc âm, do đó hình dạng tổng thể của $P$ khá dễ hình dung. Ngay cả một bản phác thảo sơ bộ các đường này cũng cho thấy rằng các điểm $(0,0),\,(7,0)$ và $(0,6)$ là các đỉnh của đa diện $P$ .

Vậy còn các giao điểm của các đường (1), (2) và (3) thì sao? Đôi khi từ đồ thị ta có thể thấy rõ giao điểm nào cần bao gồm. Nhưng nếu không chắc chắn, thì thủ tục đại số sau đây sẽ rất hữu ích:

Khi tìm được một điểm giao ứng với hai bất đẳng thức, ta cần kiểm tra xem điểm đó có thỏa mãn các bất đẳng thức còn lại hay không để xác định xem nó có nằm trong đa diện không.

Giao điểm của (1) và (2) là $\mathbf{p}_{12}=(3,5)$ . Cả hai tọa độ đều không âm, nên $\mathbf{p}_{12}$ thỏa mãn điều kiện $\mathbf{x}\geq 0$ 1. Bây giờ kiểm tra bất đẳng thức thứ ba:

$3(3)+2(5)=9+10=19<21$

Điều này cho thấy $\mathbf{p}_{12}$ thỏa mãn bất đẳng thức (3), vậy $\mathbf{p}_{12}$ nằm trong đa diện $P$ .

Giao điểm của (2) và (3) là $\mathbf{p}_{23}=(5,3)$ . Điểm này thỏa mãn tất cả các bất đẳng thức, trừ có thể bất đẳng thức (1). Kiểm tra:

1(5) + 3(3) = 5 + 9 = 14 < 18

Điều này cho thấy $\mathbf{p}_{23}$ nằm trong đa diện.

Cuối cùng, giao điểm của (1) và (3) là $\mathbf{p}_{13}=(\frac{27}{7},\frac{33}{7})$ . Kiểm tra điểm này với bất đẳng thức (2):

$1(\frac{27}{7})+1(\frac{33}{7})=\frac{60}{7}\approx 8.6>8$

Do đó, $\mathbf{p}_{13}$ không thỏa mãn bất đẳng thức thứ hai, điều này cho thấy $\mathbf{p}_{13}$ không thuộc $P$ . Kết luận, biểu diễn tối tiểu của đa diện $P$ là tập hợp các điểm:

$\left\{\begin{bmatrix}0\\0\end{bmatrix},\begin{bmatrix}7\\0\end{bmatrix},\begin{bmatrix}3\\5\end{bmatrix},\begin{bmatrix}5\\3\end{bmatrix},\begin{bmatrix}0\\6\end{bmatrix}\right\}$

Phần tiếp theo của bài này sẽ thảo luận về việc xây dựng hai đa diện cơ bản trong $\mathbb{R}^3$ (và các chiều cao hơn). Đa diện đầu tiên xuất hiện trong các bài toán lập trình tuyến tính. Cả hai đa diện đều cung cấp cơ hội để hình dung $\mathbb{R}^4$ theo một cách rất đặc biệt.

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 10: Đa diện (Polytopes)

Lesson Attachments

Để lại một bình luận Hủy