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

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 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
3 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 41ii
3.2.5 Tập hữu hiệu trong R
2 và R
3 . 41
3.3 Ví dụ minh họa 43
Kết luận 45
Tài liệu tham khảo 46
Phụ lục 47iii
Danh sách ký hiệu
R
n : Không gian n chiều
A ⊂ B: A là tập con của B
M ⊆ R
n : M là tập con trong R
n
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{a 1 , a 2 , a 3 }: Nón sinh bởi hệ véctơ {a 1 , a 2 , a 3 }
N c (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 Xiv
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 + Hình 2.2. Nón cone {a 1 , a 2 , a 3 } ⊂ R
3 . 19
2.2 Minh họa Bổ đề 2.2 và Mệnh đề 2.1 . 21
3.1 D 1 và D 2 : x 1 , x 2 - đỉnh hữu hiệu, [x 1 , x 2 ] - 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ề x 0 37
3.3 Sơ đồ khối Thuật toán 2: Tìm các diện hữu hiệu ` chiều kề x 0 401
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 khi2
đượ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 x 0 đã 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 x 0 đã 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 R
2 , R
3 .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