Tài liệu Tập lồi đa diện và ứng dụng trong qui hoạch tuyến tính đa mục tiêu

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ BÍCH HẠNH TẬP LỒI ĐA DIỆN VÀ ỨNG DỤNG TRONG QUI HOẠCH TUYẾN TÍNH ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ BÍCH HẠNH TẬP LỒI ĐA DIỆN VÀ ỨNG DỤNG TRONG QUI HOẠCH TUYẾN TÍNH ĐA MỤC TIÊU Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TS TRẦN VŨ THIỆU Thái Nguyên - 2015 i Mục lục Danh sách ký hiệu iii Danh sách hình vẽ iv Mở đầu 1 1 Cấu trúc tập lồi đa diện 4 1.1 Tập lồi và tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Hướng lùi xa của tập lồi đa diện . . . . . . . . . . . . . . . . . . 8 1.3 Biểu diễn tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . 11 2 3 Nón pháp tuyến của tập lồi đa diện 18 2.1 Nón pháp tuyến của tập lồi . . . . . . . . . . . . . . . . . . . . 18 2.2 Nón pháp tuyến âm của tập lồi đa diện . . . . . . . . . . . . . . 25 Phương pháp nón pháp tuyến 28 3.1 Bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . . . . . . . . 28 3.2 Thuật toán nón pháp tuyến . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Tìm đỉnh hữu hiệu ban đầu . . . . . . . . . . . . . . . . 33 3.2.2 Tìm các đỉnh hữu hiệu và cạnh hữu hiệu . . . . . . . . . 34 3.2.3 Tìm các diện hữu hiệu số chiều lớn hơn 1 . . . . . . . . . 38 3.2.4 Tìm các diện hữu hiệu (n -1) chiều . . . . . . . . . . . . 41 ii 3.2.5 3.3 Tập hữu hiệu trong R2 và R3 . . . . . . . . . . . . . . . 41 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Kết luận 45 Tài liệu tham khảo 46 Phụ lục 47 iii Danh sách ký hiệu Rn : Không gian n chiều A ⊂ B : A là tập con của B M ⊆ Rn : M là tập con trong Rn Rec A: Nón lùi xa của A B(x, ε): Hình cầu tâm x bán kính ε dim A: Số chiều của A rank A: Hạng của A cone{a1 , a2 , a3 }: Nón sinh bởi hệ véctơ {a1 , a2 , a3 } Nc (X): Nón pháp tuyến của C tại x ri(A): Phần trong tương đối của tập A | I | : Số phần tử của I a ≥ b: Quan hệ không âm a > b: Quan hệ nửa dương a >> b: Quan hệ thực sự dương conv(X): Bao lồi của tập X iv Danh sách hình vẽ 1.1 Tập A lồi, Tập B không lồi . . . . . . . . . . . . . . . . . . . . . 6 1.2 Đường thẳng và véctơ chỉ phương . . . . . . . . . . . . . . . . . 8 1.3 Tập lồi không bị chặn và hướng lùi xa . . . . . . . . . . . . . . . 9 1.4 Biểu diễn tập đa diện qua đỉnh và cạnh vô hạn (hướng cực biên) . 17 2.1 Tập X và nón X + 19 2.2 Minh họa Bổ đề 2.2 và Mệnh đề 2.1 . . . . . . . . . . . . . . . 21 3.1 D1 và D2 : x1 , x2 - đỉnh hữu hiệu, [x1 , x2 ] - cạnh hữu hiệu . . . . 29 3.2 Sơ đồ khối Thuật toán 1: Tìm các cạnh hữu hiệu kề x0 . . . . . . 37 3.3 Sơ đồ khối Thuật toán 2: Tìm các diện hữu hiệu ` chiều kề x0 . . 40 Hình 2.2. Nón cone {a1 , a2 , a3 } ⊂ R3 . 1 Mở đầu Tập lồi đa diện có các tính chất rất đáng chú ý và được sử dụng rộng rãi trong lý thuyết và ứng dụng, đặc biệt trong giải tích lồi và tối ưu hóa. Tập lồi đa diện là một dạng tập lồi có cấu trúc đơn giản và có thể được biểu diễn thông qua tập (hữu hạn) các đỉnh và cạnh của nó. Nhiều bài toán tối ưu tuyến tính (một hay nhiều mục tiêu) được giải hiệu quả nhờ khai thác cấu trúc của tập lồi đa diện, đặc biệt là cấu trúc đỉnh cạnh, diện, nón pháp tuyến ... Nón pháp tuyến là sự mở rộng khái niệm véctơ pháp tuyến của mặt cong trơn đã biết trong giải tích cổ điển khi nghiên cứu cấu trúc các mặt cong và các tính toán trên mặt cong. Nón pháp tuyến của tập lồi do Minkowski (1911) đưa ra đầu tiên, sau đó là Fenchel (1953) để xử lý các đối tượng không trơn, như tập lồi. Rockafellar (1970) đã nghiên cứu có hệ thống về nón pháp tuyến của các tập lồi. Tiếp đó là nghiên cứu mở rộng của Morduhovic (1980) và Clark (1983) về xây dựng nón pháp tuyến qua các véctơ pháp tuyến gần kề và qua dưới vi phân của các hàm Lipschitz. Năm 2000, Nguyễn Thị Bạch Kim và Đinh Thế Lục [5] đã đưa ra khái niệm nón pháp tuyến âm và xây dựng điều kiện tối ưu cho bài toán qui hoạch đa mục tiêu tuyến tính theo ngôn từ nón pháp tuyến. Từ đó đề xuất phương pháp nón pháp tuyến khá đơn giản để tìm các diện nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu tuyến tính. Có thể nói hiện nay nón pháp tuyến là một phương tiện không thể thiếu để thiết lập các điều kiện tối ưu cho các bài toán tối ưu không trơn. Sau khi 2 được học về Giải tích lồi và các kiến thức toán học có liên quan, với mong muốn tìm hiểu sâu hơn về những kiến thức đã học, các kiến thức mở rộng và ứng dụng của những kiến thức này, chúng tôi chọn đề tài luận văn "Tập lồi đa diện và ứng dụng trong qui hoạch tuyến tính đa mục tiêu" Luận văn này có mục đích tìm hiểu, trình bày lại các kết quả chính về tập lồi đa diện và ứng dụng các kết quả này trong xây dựng cơ sở lý luận cho phương pháp nón pháp tuyến [5] giải bài toán tối ưu đa mục tiêu tuyến tính. Nội dung luận văn được viết trong ba chương. Chương 1 "Cấu trúc tập lồi đa diện" trình bày những kiến thức cơ bản về tập lồi, tập lồi đa diện và các khái niệm liên quan (đỉnh, cạnh và diện của tập lồi đa diện, nón lồi và nón lồi đa diện, hướng lùi xa và nón lùi xa, ...). Tập lồi đa diện không bị chặn. Tập lồi đa diện khác rỗng. Chương 2 "Nón pháp tuyến của tập lồi đa diện" trình bày một số kiến thức chuẩn bị về nón pháp tuyến, nón pháp tuyến âm của tập lồi đa diện tại một điểm và các khái niệm liên quan về tập chuẩn tắc và tập chuẩn tắc âm. Đồng thời giới thiệu các kết quả nêu ra ở [5] làm cơ sở lý luận cho phương pháp nón pháp tuyến tìm nghiệm hữu hiệu (tối ưu Paeto) của bài toán tối ưu đa mục tiêu tuyến tính. Chương 3 "Phương pháp nón pháp tuyến" trình bày chi tiết phương pháp nón pháp tuyến đề xuất trong [5] tìm các đỉnh, cạnh và diện nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu tuyến tính trên tập lồi đa diện cho trước. Các thuật toán được mô tả chi tiết và diễn giải qua các sơ đồ khối và ví dụ minh họa: - Thuật toán 1: Tìm các cạnh hữu hiệu đi từ đỉnh hữu hiệu x0 đã biết. - Thuật toán 2: Tìm các diện hữu hiệu ` chiều kề đỉnh hữu hiệu x0 đã biết. - Thuật toán 3: Tìm các diện hữu hiệu (n - 1) chiều. - Thuật toán 4: Tìm tập điểm hữu hiệu trong R2 , R3 . 3 Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn còn có những thiếu sót nhất định, kính mong quý thầy cô và các bạn đóng gópý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này tác giả luận văn xin bày tỏ lòng cảm ơn sâu sắc tới GS. TS. Trần Vũ Thiệu, người đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả trân trọng cảm ơn các giảng viên Trường Đại học Khoa học - Đại học Thái Nguyên, Viện Toán học - Viện Hàn lâm Khoa học và Công nghệ Việt Nam tạo mọi điều kiện thuận lợi trong quá trình học tập và nghiên cứu. Thái Nguyên, tháng 05 năm 2015 Tác giả Nguyễn Thị Bích Hạnh 4 Chương 1 Cấu trúc tập lồi đa diện Chương này trình bày các kiến thức cơ bản về tập lồi, tập lồi đa diện, nón lồi và nón lồi đa diện. Đặc biệt lưu ý các khái niệm đỉnh, cạnh và diện của tập lồi đa diện, đặc trưng của các tập lồi đa diện không bị chặn, cách biểu diễn một tập lồi đa diện qua các đỉnh và cạnh của nó. Nội dung của chương được tham khảo từ các tài liệu [1], [2], [3] và [4]. 1.1 Tập lồi và tập lồi đa diện Trước hết là những khái niệm liên quan tới tập afin trong Rn . Định nghĩa 1.1. (Tập afin). Tập M ⊆ Rn được gọi là tập afin (affine set) nếu ∀a, b ∈ M, λ ∈ R thì λa + (1 − λ)b ∈ M , tức là hễ M chứa hai điểm nào đó thì M chứa trọn đường thẳng đi qua hai điểm ấy. Một số tính chất cơ bản của các tập afin: • Nếu M là tập afin thì a + M = {a + x : x ∈ M } cũng là một tập afin (a ∈ Rn ). • Giao của một họ bất kỳ các tập afin cũng là một tập afin. • M ⊆ Rn là một tập afin khi và chỉ khi M = {x ∈ Rn : Ax = b} với A ∈ Rm×n , b ∈ Rm . 5 • M 6= Ø là một tập afin khi và chỉ khi M = x0 + L với x0 ∈ M và L là một không gian con. L được xác định duy nhất và được gọi là không gian con song song (parallel subspace) với M (M nhận được bằng cách tịnh tiến L tới điểm x0 ∈ M ). Định nghĩa 1.2. Bao afin (affine hull) của một tập E là giao của tất cả các tập afin chứa E, ký hiệu aff(E). Đó là tập afin nhỏ nhất chứa E. Định nghĩa 1.3. Thứ nguyên (hay số chiều - dimension) của một tập afin M được định nghĩa bằng số chiều của không gian con song song với M. Định nghĩa 1.4. (Tập lồi). Tập C ⊆ Rn được gọi là một tập lồi (convex set) nếu với mọi x1 , x2 ∈ C và mọi λ ∈ [0, 1] ta có λx1 + (1 − λ)x2 ∈ C . Thứ nguyên của tập lồi C, ký hiệu dim C, được định nghĩa bằng thứ nguyên của aff C (bao afin của C). Theo Định nghĩa 1.4 thì tập Ø , tập gồm duy nhất một phần tử, tập afin và toàn bộ không gian Rn đều là các tập lồi. Để hiểu rõ khái niệm tập lồi, ta nhớ rằng nếu λ ∈ [0, 1] thì λx1 + (1 − λ)x2 là 1 1 1 điểm thuộc đoạn thẳng nối x1 và x2 trong Rn . Chẳng hạn, khi λ = thì x1 + x2 2 2 2 1 2 1 là điểm nằm giữa x và x . Ngược lại, với mỗi điểm x trên đoạn thẳng nối x và x2 ta tìm được giá trị λ ∈ [0, 1] sao cho x = λx1 + (1 − λ)x2 . Như vậy tập C lồi có nghĩa là nếu x1 , x2 ∈ C thì mọi điểm trên đoạn thẳng nối x1 và x2 cũng thuộc C. Định nghĩa 1.5. (Tổ hợp lồi). Cho x1 , · · · , xk ∈ Rn . Nếu λ1 , · · · , λk ∈ [0, 1] và λ1 + · · · + λk = 1 thì x = λ1 x1 + · · · + λk xk gọi là một tổ hợp lồi (convex combination) của x1 , · · · , xk và gọi là một tổ hợp lồi chặt (strictly convex combination) nếu 0 < λi < 1 với mọi i = 1, · · · , k. 6 Hình 1.1: Tập A lồi, Tập B không lồi Bổ đề 1.1. Giao của một số hữu hạn tập lồi trong Rn là một tập lồi. Trong số các tập lồi thì tập đa diện có vai trò đặc biệt quan trọng và được dùng nhiều trong lý thuyết tối ưu. Trước khi nêu định nghĩa tập đa diện, ta cần hiểu rõ khái niệm siêu phẳng và nửa không gian đóng. Định nghĩa 1.6. (Siêu phẳng). Cho véctơ a ∈ Rn , a 6= 0 và số b ∈ R. Tập H = {x ∈ Rn |aT x = a1 x1 +· · ·+an xn = b} gọi là một siêu phẳng (hyperplane) trong Rn . Đó là tập nghiệm của một phương trình tuyến tính trong Rn . Ví dụ 1.1. Trong không gian 3 chiều R3 , phương trình x1 −2x2 +3x3 = 4 xác định một siêu phẳng trong R3 . Đó là mặt phẳng gồm tất cả các điểm (x1 , x2 , x3 ) ∈ R3 nghiệm đúng x1 − 2x2 + 3x3 = 4 Định nghĩa 1.7. (Nửa không gian đóng). Cho véctơ a ∈ Rn (a 6= 0) và số b ∈ R. Khi đó, các tập H1 = {x ∈ Rn |aT x = a1 x1 + · · · + an xn ≤ b}, H2 = {x ∈ Rn |aT x = a1 x1 + · · · + an xn ≥ b} gọi là các nửa không gian đóng (closed half-spaces) xác định bới siêu phẳng aT x = b. Ví dụ 1.2. Trong mặt phẳng R2 , xét siêu phẳng (trường hợp này là đường thẳng) x1 + x2 = 2. Siêu phẳng này tạo ra hai nửa không gian H1 = {x ∈ R2 |x1 + x2 ≤ 2} và H2 = {x ∈ R2 |x1 + x2 ≥ 2}. 7 Bổ đề 1.2. Mọi siêu phẳng và nửa không gian là các tập lồi. Từ các định nghĩa 1.4 và 1.7, ta đi đến định nghĩa tập đa diện, đó là đối tượng nghiên cứu của hầu hết phần còn lại của chương này. Định nghĩa 1.8. (Tập đa diện). Nếu P ⊆ Rn là giao của một số hữu hạn các nửa không gian đóng thì P được gọi là một tập đa diện (polyhedral set). Một cách hình thức, cho a1 , · · · , am ∈ Rn , là tập hữu hạn các véctơ cột và b1 , · · · , bm , là các hằng số. Xét các nửa không gian đóng Hi = {x ∈ Rn |hai , xi ≥ bi }. Khi đó, P = m T Hi là một tập đa diện. i=1 Mỗi bất phương trình hai , xi ≥ bi gọi là một ràng buộc (constraint) của P. Ta ∗ nói điểm x0 ∈ P thỏa mãn chặt ràng buộc i∗ nếu hai , x0 i ≥ bi∗ . Như vậy, tập đa diện chính là tập nghiệm của một hệ bất phương trình tuyến tính Ax ≥ b với A = [a1 , · · · , am ]T là ma trận cấp m × n và b = (b1 , · · · , bm )T ∈ Rm là véctơ cột với các thành phần b1 , · · · , bm . Do mỗi phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính nên một tập đa diện cũng là tập nghiệm của một hệ phương trình và bất phương trình tuyến tính ai1 x1 + ai2 x2 + · · · + ain xn = bi , i = 1, · · · , p, ai1 x1 + ai2 x2 + · · · + ain xn ≥ bi , i = p + 1, · · · , m. Bổ đề 1.3. Tập đa diện là một tập lồi. (Vì là giao của m tập lồi). Do tính chất này nên ta thường quen gọi tập đa diện là tập lồi đa diện (polyhedral convex set). Một tập lồi đa diện có thể không bị chặn. Một tập lồi đa diện bị chặn còn được gọi là một đa diện lồi (polytope). Các đa giác lồi theo nghĩa thông thường trong mặt phẳng (tam giác, hình chữ nhật, hình thang, ...) là những ví dụ cụ thể về đa diện lồi. 8 1.2 Hướng lùi xa của tập lồi đa diện Mục này nêu một số đặc trưng của các tập lồi (đa diện) không bị chặn. Định nghĩa 1.9. (Đường thẳng). Cho hai véctơ x0 , d ∈ Rn (d 6= 0). Đường thẳng (line) đi qua x0 theo hướng d là tập các điểm x(λ) = x0 + λd với λ ∈ R. Véctơ d gọi là véctơ chỉ phương (direction) của đường thẳng. Ví dụ 1.3. Hình 1.2 vẽ đường thẳng đi qua x0 = (0, 1) theo hướng d = (2, 1). Đường thẳng này là tập điểm ` = {(x1 , x2 ) ∈ R2 |x1 = 0 + 2λ, x2 = 1 + λ, λ ∈ R}. Hình 1.2: Đường thẳng và véctơ chỉ phương Định nghĩa 1.10. (Tia). Cho điểm x0 ∈ R và véctơ chỉ phương d ∈ Rn (d 6= 0). Tia (ray) đi từ x0 theo hướng d là tập điểm Γ = {x|x = x0 + λd, λ ≥ 0}. Ví dụ 1.4. Với x0 = (0, 1) và d = (2, 1) như ở ví dụ trước, tia đi từ x0 theo hướng d là tập điểm Γ = {(x1 , x2 ) ∈ R2 |x1 = 0 + 2λ, x2 = 1 + λ, λ ≥ 0}. Đó là nửa đường thẳng l nằm trong góc phần tư thứ nhất vẽ ở Hình 1.2. Tia đặc trưng cho tập lồi không bị chặn. Cụ thể, một tập lồi là không bị chặn nếu ta chỉ ra nó chứa một tia. Lớp tập lồi không bị chặn đáng chú ý là các nón lồi. 9 Định nghĩa 1.11. (Nón lồi). Cho tập lồi K ⊆ Rn . Khi đó, K là một nón lồi (convex cone) nếu với mọi x ∈ K và mọi λ ≥ 0, ta có λx ∈ K . Một tập lồi đa diện mà đồng thời là một nón lồi gọi là một nón lồi đa diện (polyhedral convex cone). Theo định nghĩa trên, mọi nón lồi chứa gốc. Hơn nữa, với mọi x ∈ K, λ ≥ 0 thì λx ∈ K , cho nên nón lồi chứa tia 0 + λx ⊆ K, λ ≥ 0. Như vậy, mỗi nón lồi chính là được tạo nên từ các tia đi từ gốc. Một khái niệm quan trọng khác giúp hiểu rõ các tập lồi không bị chặn là khái niệm hướng lùi xa và nón lùi xa. Có thể hiểu hướng lùi xa như một hướng di chuyển mà từ một điểm bất kỳ thuộc tập lồi không bị chặn ta có thể đi mãi mãi theo hướng đó và không bao giờ rời khỏi tập lồi đó. Định nghĩa 1.12. (Hướng lùi xa). Cho một tập lồi C ⊆ Rn . Véctơ d ∈ Rn , d 6= 0 gọi là một hướng lùi xa (recession direction) của C nếu với mọi x0 ∈ C tia đi từ x0 theo hướng d nằm hoàn toàn trong C. Một cách hình thức, ta phải có {x|x = x0 + λd, λ ≥ 0} ⊆ C với mọi x0 ∈ C . Ví dụ 1.5. Xét tập lồi không bị chặn vẽ ở Hình 1.3. Tập này có hướng lùi xa d = (1, 0)T . Từ một điểm bất kỳ x0 ∈ C ta có thể vẽ một mũi tên hướng về bên phải (theo hướng d) với độ dài tùy ý mà mũi tên vẫn nằm trọn trong tập lồi C. Hình 1.3: Tập lồi không bị chặn và hướng lùi xa 10 Tập lồi đa diện được sử dụng trong tối ưu hóa thường có thêm giả thiết P nằm trong orthant dương của Rn (nghĩa là x ≥ 0 là ràng buộc của P). Khi đó, có mối quan hệ đáng chú ý sau giữa ma trận A xác định P và hướng lùi xa của P. Định lý 1.1. Giả sử P ⊆ Rn là một tập đa diện xác định bởi P = {x ∈ Rn : Ax ≥ b, x ≥ 0} Khi đó, d là một hướng lùi xa của P khi và chỉ khi Ad ≥ 0, d ≥ 0, d 6= 0 Chứng minh. "Phần khi:" Giả sử d ∈ Rn thỏa mãn Ad ≥ 0, d ≥ 0 và d 6= 0. Khi đó, với mọi x0 ∈ P , tức Ax0 ≥ b, x0 ≥ 0, và mọi λ ≥ 0, ta có A(x0 + λd) = Ax0 + λAd ≥ b + λ × 0 = b và x0 + λd ≥ 0, chứng tỏ x0 + λd ∈ P với mọi λ ≥ 0. Theo định nghĩa, d là một hướng lùi xa của P. "Phần chỉ khi": Giả sử d là một hướng lùi xa của P. Theo định nghĩa hướng lùi xa, d 6= 0. Hơn nữa, d là một hướng lùi xa của P khi và chỉ khi A(x + λd) ≥ b, x + λd ≥ 0 với mọi λ ≥ 0 và mọi x ∈ P, tức x ∈ Rn thỏa mãn Ax ≥ b, x ≥ 0. Nhưng A(x + λd) = Ax + λAd ≥ b với mọi λ ≥ 0 chỉ đúng nếu Ad ≥0. Cũng vậy, x + λd ≥ 0 với mọi λ ≥ 0 chỉ đúng nếu d ≥0. Hệ quả 1.1. Nếu P0 = {x ∈ Rn : Ax = b, x ≥ 0}. Khi đó, d là một hướng lùi xa của P khi và chỉ khi Ad = 0, d ≥ 0, d 6= 0. Định nghĩa 1.13. (Nón lùi xa). Nón lồi tạo nên bởi tập tất cả các hướng lùi xa của một tập lồi C và véctơ 0 gọi là nón lùi xa (recession cone) của C, ký hiệu rec C 11 Ví dụ 1.6. Với các tập đa diện P và P0 vừa xét ở trên thì recP = {d ∈ Rn : Ad ≥ 0, d ≥ 0} và recP0 = {d ∈ Rn : Ad = 0, d ≥ 0} 1.3 Biểu diễn tập lồi đa diện Trước hết, ta đề cập tới khái niệm diện (nói riêng là đỉnh và cạnh) của một tập lồi và tập lồi đa diện. Định nghĩa 1.14. (Diện của tập lồi). Một tập con lồi F của một tập lồi C gọi là một diện (face) của C nếu x, y ∈ C mà λx + (1 − λ)y ∈ F, 0 < λ < 1 thì [x, y] ⊆ F, nghĩa là một đoạn thẳng bất kỳ thuộc C mà có một điểm bên trong nó thuộc F thì cả đoạn thẳng ấy phải nằm trọn trong F. Tất nhiên, tập ∅ và bản thân C cũng là một diện của C. Một diện của C, khác ∅ và khác C, gọi là một diện thực sự (proper face) của C. Ví dụ, các diện thực sự của khối lập phương trong R3 là 8 đỉnh, 12 cạnh và 6 mặt của nó. Định nghĩa 1.15. (Điểm cực biên). Một diện có thứ nguyên (số chiều) 0 gọi là một điểm cực biên (extreme point) của C. Nói cách khác, x0 ∈ C là một điểm cực biên của C nếu không tồn tại x1 , x2 ∈ C, x1 6= x0 hoặc x2 6= x0 sao cho x0 = λx1 + (1 − λ)x2 với λ ∈ (0, 1) . Điểm cực biên của tập đa diện P gọi là một đỉnh (vertex) của P. Điểm cực biên của tập lồi C đơn giản chỉ là điểm thuộc C không thể biểu diễn được dưới dạng một tổ hợp lồi chặt (Định nghĩa 1.5) của hai điểm khác nhau của C. Ta sẽ thấy rằng các điểm cực biên phải nằm ở những vị trí đặc biệt của tập lồi. Định nghĩa 1.16. (Điểm biên). Cho tập (có thể không lồi) C ∈ Rn . Điểm x0 ∈ Rn là điểm biên (boundary point) của C nếu với mọi ε > 0 ta có 12 B(x0 , ε) ∩ C 6= ∅ và B(x0 , ε) ∩ (Rn \ C) 6= ∅ trong đó B(x0 , ε) = {x ∈ Rn : ||x − x0 || ≤ ε} là hình cầu (đóng) tâm x0 , bán kính ε. Nói cách khác, điểm biên của tập C là điểm (không nhất thiết thuộc C) sao cho trong bất kỳ hình cầu tâm tại điểm đó, bán kính tùy ý đều có những điểm thuộc C và những điểm không thuộc C. Tập các điểm biên của C gọi là biên (boundary) của C, ký hiệu ∂C . Bổ đề 1.4. Cho C là một tập lồi. Nếu x là một điểm cực biên của C thì x phải ở trên biên của C. Định lý sau nêu quan hệ giữa đỉnh của tập đa diện với giao của các siêu phẳng. Định lý 1.2. Giả sử P ⊆ Rn là tập lồi đa diện xác định bởi P = {x ∈ Rn : Ax ≥ b} trong đó A ∈ Rm×n và b ∈ Rm . Điểm x0 ∈ P là một đỉnh của P khi và chỉ khi x0 là giao của n siêu phẳng độc lập tuyến tính lập nên từ các ràng buộc của P. Chứng minh. (⇐) Giả sử x0 ∈ P (tức Ax0 ≥ b) là giao của n siêu phẳng độc lập tuyến tính, nghĩa là từ A có thể lấy ra ma trận không suy biến G ∈ Rn×n và từ b lấy ra véctơ tương ứng g ∈ Rn sao cho Gx0 = g . Nếu x0 không phải là một đỉnh của P thì tìm được x1 , x2 ∈ P, x1 6= x0 hoặc x2 6= x0 và λ ∈ (0, 1) sao cho x0 = λx1 + (1 − λ)x2 . Do Gx0 = g nên Gx0 = λGx1 + (1 − λ)Gx2 = b. Mặt khác, do x1 , x2 ∈ P nên Gx1 ≥ g, Gx2 ≥ g . Kết hợp với λGx1 + (1 − λ)Gx2 = b và 0 < λ < 1 suy ra Gx1 = Gx2 = b. Do G không suy biến nên x0 = x1 = x2 , ta gặp mâu thuẫn. Vậy x0 là một đỉnh của P. 13 (⇒) Giả sử x0 là một đỉnh của P. Theo Bổ đề 1.4, x0 là một điểm biên của P và do đó có ít nhất một ràng buộc i nào đó của P thỏa mãn chặt tại x0 , tức i 0 a , x = bi (vì nếu trái lại, x0 sẽ không thuộc biên của P). Giả thiết phản chứng rằng x0 là giao của r < n siêu phẳng độc lập tuyến tính (nghĩa là chỉ có r < n ràng buộc xác định P thỏa mãn chặt tại x0 ). Khi đó, từ ma trận A có thể lấy ra ma trận con G ∈ Rr×n và từ b lấy ra véctơ tương ứng g ∈ Rr sao cho Gx0 = g . Các siêu phẳng độc lập tuyến tính kéo theo các hàng của G độc lập tuyến tính và do đó phương trình Gd = 0 có nghiệm khác 0. Tiếp đó, ta tìm được số ε > 0 sao cho  a) x1 = x0 + εd thỏa mãn Gx1 = g và ai , x1 > bi với mọi ràng buộc còn lại.  b) x2 = x0 + εd thỏa mãn Gx2 = g và ai , x2 > bi với mọi ràng buộc còn lại. Từ a) và b) suy ra x1 , x2 ∈ P và x0 = (x1 + x2 )/2, trái với x0 là một đỉnh của P. Vậy x0 là giao của n siêu phẳng độc lập tuyến tính. Bổ đề 1.5. Số đỉnh của tập đa diện P = {x ∈ Rn : Ax ≥ b, x ≥ 0} là dương và hữu hạn. Định nghĩa 1.17. (Đỉnh suy biến). Cho tập đa diện P = {x ∈ Rn : Ax ≥ b}. Giả sử x0 là một đỉnh của P. Nếu x0 thỏa mãn chặt (với dấu bằng) đúng n ràng buộc xác định P thì x0 gọi là một đỉnh không suy biến (non-degenerate vertex), trái lại (x0 thỏa mãn chặt hơn n ràng buộc) thì x0 gọi là một đỉnh suy biến (degenerate vertex). Cho tập đa diện P 6= ∅ xác định bởi hệ bất phương trình tuyến tính i  a , x ≥ bi , i = 1, 2, · · · , m.  Với x ∈ P , ký hiệu I(x) = {i : ai , x = bi } là tập chỉ số những ràng buộc mà x  thỏa mãn chặt. Đặt I0 = {i : ai , x = bi , ∀x ∈ P }. Tính chất đặc trưng của các diện (nói riêng, các đỉnh và cạnh) của P được cho trong định lý sau (xem [6], tr. 31). 14 Định lý 1.3. (Diện). Một tập con lồi khác rỗng F ⊂ P là một diện thực sự của P khi và chỉ khi   F = {x : ai , x = bi , i ∈ I, ai , x ≥ bi , i ∈ / I} với I là tập chỉ số sao cho I0 ⊂ I ⊂ {1, · · · , m} (I gọi là tập chỉ số xác định diện F). Hơn nữa, ta có dim F = n - rank {ai : i ∈ I} và dim P = n - rank {ai : i ∈ I0 }. Định nghĩa 1.18. (Cạnh và đỉnh kề). Một diện của tập đa diện P có thứ nguyên 1 gọi là một cạnh (edge): cạnh là hữu hạn nếu diện đó là một đoạn thẳng, cạnh là vô hạn nếu diện đó là một nửa đường thẳng (tức tia) hay cả đường thẳng. Hai đỉnh của P gọi là kề nhau (adjacent) nếu chúng được nối với nhau bằng một cạnh hữu hạn. Từ Định lý 1.3 trực tiếp suy ra hệ quả sau.  Hệ quả 1.2. Nếu P là tập đa diện xác định bởi hệ ai , x ≥ bi , i = 1, · · · , m thì: a) Điểm x0 ∈ P là một đỉnh của P khi và chỉ khi rank {ai : i ∈ I(x0 )} = n, nghĩa là x0 thỏa mãn chặt n ràng buộc độc lập tuyến tính của P; b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) Γ ⊂ P là một cạnh của P thì Γ được xác định bởi một tập chỉ số I sao cho rank {ai : i ∈ I} = n − 1. Các cạnh vô hạn của tập lồi đặc trưng bởi các hướng cực biên theo nghĩa sau. Định nghĩa 1.19. (Hướng cực biên). Cho tập lồi C ⊆ Rn . Hướng lùi xa d của C gọi là một hướng cực biên (extreme direction) nếu không tồn tại hai hướng lùi xa d1 , d2 khác của C (tức d1 6= d, d2 6= d) và hai số λ1 , λ2 > 0 sao cho d = λ1 d1 + λ2 d2 . Ví dụ 1.7. Góc không âm R2+ = {x ∈ R2 : x1 ≥ 0, x2 ≥ 0} có hai hướng cực biên, đó là d1 = (1, 0)T và d2 = (0, 1)T , trong khi đó d = (1, 1)T cũng là một hướng lùi xa, nhưng không là một hướng cực biên, bởi vì d = d1 + d2 .