Khái niệm vùng khả thi điểm cực biên

Full PDF PackageDownload Full PDF Package

This Paper

A short summary of this paper

37 Full PDFs related to this paper

Download

PDF Pack

Posted by Trần Quốc Long trên Tháng Hai 14, 2008

Định nghĩa (đa diện lồi): Tập gọi là đa diện lồi (polyhedra) trong .

Nhận xét:

1. Đa diện lồi là tập đóng, lồi.
2. cũng là đa diện lồi khi ta chọn .
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 luôn có thể biểu diễn dưới dạng

trong đó là tập đóng lồi không chứa đường thẳng, là không gian con của .

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

1. (nhân của ma trận, còn kí hiệu là ).
2. (không gian con tạo bởi các cột của ).
3. Tính chất: .

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

1. Nếu , đường thẳng nếu và chỉ nếu .
2. Đặt thì và không chứa đường thẳng.

Chứng minh (1): Nếu , ta có .

Ngược lại, nếu , tức là ( là dòng thứ của ). Xét 2 trường hợp:

• , rõ ràng khi ta sẽ có .
• thì khi ta cũng có .

Vậy chỉ còn khả năng , tức là .

Chứng minh (2): Rõ ràng nên theo (1). Ngược lại, nếu , chiếu xuống , ta có

Ta thấy nên theo (1), như vậy , suy ra . Tức là . Kết luận .

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

Nhận xét:

1. Ta thấy là đa diện lồi trong không gian con của nên nó cũng là đa diện lồi trong (ngoài điều kiện ta thêm vào các điều kiện ).
2. không chứa đường thằng nếu và chỉ nếu .

Định lý (cấu trúc của đa diện lồi có điểm cực biên): Nếu là đa diện lồi không chứa đường thẳng thì có thể biểu diễn dưới dạng

trong đó hữu hạn, là tập hữu hạn các véctơ và .

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

1. Nếu sao cho tồn tại thì .
2. Hơn nữa, với như vậy, với mọi .
3. .
4. Tập hữu hạn.
5. Tập 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ơ .

Chứng minh (1): Ta có , tức là . Nếu thì khi , ta sẽ có . Như vậy, ta phải có , tức là .

Chứng minh (2): Vì , với mọi , ta có , tức là toàn bộ tia .

Chứng minh (3): Rõ ràng nên theo (2). Ngược lại, nếu , ta sẽ chứng minh bằng quy nạp theo .

Cơ sở: với tức là định lý đúng.

Quy nạp: giả sử định lý đúng với , ta sẽ chứng minh định lý cũng đúng với . Thật vậy, chọn một véctơ . Vì không chứa đường thẳng nên (do theo định lý trên). Đồng thời, tia phải thoát ra khỏi ở một điểm nào đó, nếu không sẽ chứa toàn bộ đường thẳng . Xét siêu phẳng đỡ ở , đặt . Rõ ràng cũng là đa diện lồi, không chứa đường thẳng, theo giả thiết quy nạp điểm phải thuộc vào tập (do ta thêm một điều kiện vào đa diện lồi). Rõ ràng

tức là . Suy ra .

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 là điểm cực biên của , trong các ràng buộc được kích hoạt tại , phải có ràng buộc độc lập tuyến tính, tức là có

và độc lập tuyến tính.

Chứng minh: Thật vậy, giả sử ngược lại, chỉ có ràng buộc độc lập tuyến tính. Như vậy, tồn tại véctơ sao cho trực giao với tất cả của các ràng buộc được kích hoạt tại . Xét điểm . Rõ ràng, các ràng buộc được kích hoạt tại vẫn được kích hoạt tại , ngoài ra, với đủ nhỏ, các ràng buộc không được kích hoạt tại vẫn được thỏa mãn tại , như vậy với đủ nhỏ, tức là không phải là điểm cực biên, mâu thuẫn.

Do số lượng các bộ ràng buộc trong ràng buộc ( là số dòng của ma trận A) là hữu hạn nên số điểm cực biên, , 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 tạo bởi một điều kiện bị kích hoạt tại (tại phải có điều kiện được kích hoạt, nếu không nó phải nằm trong ). Theo giả thiết quy nạp,

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

.

Do số ràng buộc, , là hữu hạn nên nếu ta đặt , thì

.

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 luôn có thể viết dưới dạng

   (*)

   trong đó và 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 là biểu diễn từ phía ngoài ( ràng buộc ) thì biểu diễn (*) là biểu diễn từ phía trong, nghĩa là trong 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 .
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 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 thì nó đạt cực đại (cực tiểu) trong đa diện lồi đó.

Chứng minh: Nếu bị chặn trên trong đa diện lồi thì với mọi ta phải có . Thật vậy, nếu , rõ ràng với mọi ta có không bị chặn khi . Suy ra, với mọi ta có

Tức là cực đại của trên cũng là cực đại của trên .

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 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

   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.