Đăng ký Đăng nhập
Trang chủ Tối ưu véctơ tuyến tính và ứng dụng vào mô hình kinh tế...

Tài liệu Tối ưu véctơ tuyến tính và ứng dụng vào mô hình kinh tế

.PDF
63
139
113

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------- NGUYỄN HOÀNG TUẤN ANH TỐI ƢU VÉCTƠ TUYẾN TÍNH VÀ ỨNG DỤNG VÀO MÔ HÌNH KINH TẾ LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN – NĂM 2013 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------- NGUYỄN HOÀNG TUẤN ANH TỐI ƢU VÉCTƠ TUYẾN TÍNH VÀ ỨNG DỤNG VÀO MÔ HÌNH KINH TẾ 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 TS. NGUYỄN VĂN QUÝ THÁI NGUYÊN – NĂM 2013 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC LỜI CẢM ƠN ...................................................................................................... v Mở đầu.................................................................................................................. 1 Chƣơng 1: Một số khái niệm cơ bản.................................................................. 3 1.1. Tập affine ................................................................................................... 3 1.2. Tập lồi ........................................................................................................ 3 1.3. Tập lồi đa diện ........................................................................................... 4 1.4. Nón pháp tuyến của tập lồi đa diện......................................................... 6 1.5. Tập chỉ số pháp tuyến............................................................................... 8 1.6 Nón pháp tuyến âm, chỉ số pháp tuyến âm ........................................... 11 1.7 Kết luận .................................................................................................... 13 Chƣơng 2: Phƣơng pháp nón pháp tuyến giải bài toán quy hoạch tuyến tính đa mục tiêu ......................................................................................................... 14 2.1. Điểm hữu hiệu ......................................................................................... 14 2.2. Bài toán quy hoạch tuyến tính đa mục tiêu .......................................... 15 2.3 Thuật toán nón pháp tuyến giải bài toán quy hoạch tuyến tính đa mục tiêu ................................................................................................................... 17 2.3.1 Diện hữu hiệu (t.ư., hữu hiệu yếu) ...................................................... 18 2.3.2 Lược đồ tính toán ............................................................................... 19 2.3.3 Thuật toán EFFI xác định các diện hữu hiệu của bài toán qui hoạch tuyến tính đa mục tiêu .................................................................................. 21 2.3.3.1 Xác định đỉnh hữu hiệu đầu tiên ................................................... 22 2.3.3.2. Xác định các đỉnh hữu hiệu và cạnh hữu hiệu kề một đỉnh hữu hiệu cho trước ........................................................................................... 23 2.3.3.3 Xác định các diện hữu hiệu số chiều lớn hơn 1 kề một đỉnh hữu hiệu cho trước ........................................................................................... 28 2.3.4 Thuật toán WEFFI xác định các diện hữu hiệu yếu của bài toán qui hoạch tuyến tính đa mục tiêu........................................................................ 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.3.4.1. Tìm nghiệm hữu hiệu yếu đầu tiên. ............................................. 31 2.3.4.2. Xác định các cạnh hữu hiệu yếu và đỉnh hữu hiệu yếu kề một đỉnh hữu hiệu yếu cho trước. ............................................................................ 31 2.5 Kết luận ..................................................................................................... 33 Chƣơng 3: Tiếp cận tối ƣu véctơ vào mô hình kinh tế Nash - Cournot ....... 34 3.1. Giới thiệu về mô hình cân bằng thị trƣờng Nash - Cournot .............. 34 3.2. Tiếp cận tối ƣu vectơ với mô hình Nash - Cournot ............................. 39 3.2.1 Mô hình tối ưu vectơ Cournot ............................................................. 39 3.2.2 Tìm một nghiệm hữu hiệu Pareto cho mô hình................................... 43 3.3 Kết luận ..................................................................................................... 55 KẾT LUẬN ........................................................................................................ 56 TÀI LIỆU THAM KHẢO ................................................................................ 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Luận văn này được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên dưới sự hướng dẫn tận tình của Tiến sĩ Nguyễn Văn Quý. Tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc về sự tận tâm và nhiệt tình của thầy trong suốt quá trình tác giả thực hiện luận văn. Trong quá trình học tập và làm luận văn, thông qua các bài giảng, tác giả luôn được sự quan tâm giúp đỡ của các Giáo sư công tác tại Viện Toán học Việt Nam, các thầy cô giáo trong Đại học Thái Nguyên. Từ đáy lòng mình, tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các Thầy Cô. Tác giả xin chân thành cảm ơn Ban giám hiệu, phòng Đào tạo Khoa học và Quan hệ quốc tế, Khoa Toán – Tin trường Đại học Khoa học, Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tôi xin gửi lời cảm ơn tới gia đình, bạn bè và các đồng nghiệp đã động viên tôi vượt qua những khó khăn trong cuộc sống để tôi có điều kiên tốt nhất khi nghiên cứu. Tác giả Nguyễn Hoàng Tuấn Anh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Từ xa xưa, xuất phát từ những nhu cầu thực tế như việc xây dựng, đo đạc diện tích đất trồng, đi biển, tính toán buôn bán,… con người đã quan tâm tới các bài toán tìm các giá trị lớn nhất (cực đại) hay nhỏ nhất (cực tiểu), tức là tìm phương án tốt nhất để đạt mục tiêu mong muốn trong một điều kiện hoàn cảnh nào đó. Về mặt lý thuyết, bài toán tối ưu ra đời từ rất sớm với sự đóng góp to lớn của các nhà toán học nổi tiếng như: P. Fermat (1601-1665), L. Euler (17071783), P. Dirichlet (1805-1859),… Nhưng phải đến những năm 30 và 40 của thế kỷ 20, Qui hoạch toán học, hay còn gọi là Toán tối ưu mới hình thành với tư cách là một lý thuyết độc lập với những nghiên cứu khác nhau: đầu tiên là Qui hoạch tuyến tính, tiếp đó là Qui hoạch lồi, Qui hoạch toàn cục và Lý thuyết điều khiển tối ưu. Các bộ môn này phát triển mạnh mẽ và được ứng dụng rộng rãi để giải quyết các bài toán thực tế nảy sinh trong nhiều lĩnh vực như sản xuất, kinh tế, kỹ thuật,…Nét đặc trưng của các bộ môn này là cùng qui về việc tối ưu một hàm mục tiêu duy nhất trong những điều kiện nhất định, tuy nhiên trong thực tế, cùng một lúc người ta phải theo đuổi nhiều mục tiêu khác nhau. Chẳng hạn trong sản xuất ngoài việc nâng cao năng suất lao động, người ta còn quan tâm tới đa dạng hóa sản phẩm, đảm bảo chất lượng hàng hóa, hạ giá thành sản phẩm,… Khi mua hàng, ta vừa muốn được hàng rẻ, vừa muốn hàng đạt chất lượng cao, hình thức đẹp,… khi đó, qui hoạch đa mục tiêu (hay còn gọi là tối ưu véctơ) sẽ cung cấp các công cụ giúp chúng ta giải quyết các vấn đề này. Một bộ phận quan trọng của qui hoạch đa mục tiêu là qui hoạch tuyến tính đa mục tiêu. Đối tượng nghiên cứu chính của nó là lớp các bài toán qui hoạch đa mục tiêu với các hàm mục tiêu là tuyến tính và tập ràng buộc M  R n là một tập lồi đa diện. Đây là lớp bài toán có ý nghĩa ứng dụng đặc biệt quan trọng trong thực tế. Qui hoạch đa mục tiêu có rất nhiều ứng dụng, đặc biệt là trong lý thuyết quyết định, quản lý, công nghiệp, hành chính,… Mục đích của bài toán qui Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn hoạch tuyến tính đa mục tiêu là tối ưu đồng thời nhiều hàm mục tiêu độc lập với nhau trên mọi miền chấp nhận được khác rỗng M  R n . Do không gian giá trị này được sắp thứ tự toàn phần nên khái niệm nghiệm tối ưu thông thường không còn thích hợp nữa. Vì vậy, thay vào đó, cùng với khái niệm về thứ tự từng phần người ta đưa ra khái niệm nghiệm hữu hiệu. Đây là nền tảng của tối ưu véctơ. Việc xây dựng các thuật toán xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu của bài toán được sự quan tâm của nhiều tác giả như: Armand, Benson, Evans,… Các thuật toán đưa ra thường sử dụng phương pháp đơn hình đa mục tiêu, phương pháp tham số, phương pháp vô hướng hóa ( xem [15], [16] và các tài liệu trích dẫn kèm theo). Sử dụng khái niệm về nón pháp tuyến của tập lồi đa diện, các tác giả Đinh Thế Lục và Nguyễn Thị Bạch Kim đã đưa ra phương pháp nón pháp tuyến để giải bài toán tối ưu véctơ tuyến tính (xem [12],[13] ). Một trong những ứng dụng của tối ưu véctơ trong kinh tế là tiếp cận tối ưu véctơ đối với các mô hình kinh tế nổi tiếng có nhiều ứng dụng thực tiễn như mô hình cân bằng thị trường độc quyền tập đoàn Nash – Cournot (xem [7]). Luận văn gồm 3 chương: Chương 1: Trình bày một số khái niệm cơ bản về tập lồi đa diện. Chương 2: Trình bày phương pháp nón pháp tuyến giải bài toán quy hoạch tuyến tính đa mục tiêu. Chương 3: Trình bày cách tiếp cận tối ưu véc tơ với mô hình kinh tế Nash – cournot. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chƣơng 1 Một số khái niệm cơ bản Chương này trình bày một số kết quả cơ bản của giải tích lồi thường hay được sử dụng trong lý thuyết tối ưu. Nội dung chính của chương chủ yếu dựa trên các tài liệu [1], [3] và [4]. 1.1. Tập affine Định nghĩa 1.1. Đường thẳng đi qua 2 điểm a, b  Rn là tập hợp tất cả các điểm x  R n có dạng: x   a  (1   )b,   R . Định nghĩa 1.2. Tập hợp M trong Rn chứa đường thẳng đi qua 2 điểm bất kì của nó thì được gọi là tập affine. Định nghĩa 1.3. Đoạn thẳng đi qua 2 điểm a, b  R n kí hiệu bởi [a,b] là tập hợp có dạng: x  R n : x   a  (1   )b, 0    1 Định nghĩa 1.4. Cho một tập hợp C bất kì trong Rn , tập affine nhỏ nhất chứa C được gọi là bao affine của C và kí hiệu là aff C. Định nghĩa 1.5. Tập hợp tất cả các điểm x  ( x1, x2 ,..., xn )  Rn thỏa mãn bất phương trình tuyến tính: a, x   , a  R n \ 0 ,   R được gọi là nửa không gian đóng. Nửa không gian được cho bởi: a, x   , a  R n \ 0 ,   R được gọi là nửa không gian mở. 1.2. Tập lồi Định nghĩa 1.6. Một tập M trong không gian Rn được gọi là tập lồi nếu nó thỏa mãn điều kiện: a, b  M ,  0,1 thì x  a  1    b  M . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Từ định nghĩa dễ dàng nhận thấy, nếu M là tập lồi thì nó chứa mọi đoạn thẳng nối hai điểm bất kì của nó. n n i 1 i 1 1 2 n n Định nghĩa 1.7. Cho x , x ,..., x  R . Nếu x   i xi , i  0,  i  1 thì x được gọi là tổ hợp lồi của x1 , x 2 ,..., x n . Mệnh đề 1. 1. Tập M  R n là lồi khi và chỉ khi nó chứa tất cả các tổ hợp lồi của các phần tử thuộc M. Định nghĩa 1.8. Tập M  Rn được gọi là một nón với đỉnh nếu: x  M ,   0 thì: x  a   ( x  a)  M Nếu M là một nón có đỉnh tại a và M lại là tập lồi thì M được gọi là một nón lồi. Định lý 1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số và phép lấy tổ hợp tuyến tính. Nói cách khác, nếu A và B là 2 tập lồi trong Rn thì các tập sau cũng là lồi: (i) A  B : x : x  A, x  B (ii)  A   B : x  a   b : a  A, b  B,  ,   R . Một cách tổng quát chúng ta có: giao của một họ bất kỳ các tập lồi cũng là tập lồi. Định nghĩa 1.9. Giao của tất cả các tập lồi chứa tập S  Rn được gọi là bao lồi của tập S và kí hiệu là convS. Định lý 1.2. Bao lồi của tập S  Rn chứa tất cả các tổ hợp lồi của các phần tử của nó. 1.3. Tập lồi đa diện Định nghĩa 1.10. Một tập lồi đa diện trong Rn là giao của một số hữu hạn các nửa không gian đóng. Nói cách khác, một tập lồi đa diện M chính là tập nghiệm của một hệ hữu hạn các bất đẳng thức tuyến tính: a i , x  bi , i  1,...., m Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (1.1) http://www.lrc-tnu.edu.vn trong đó a1 ,..., a m là các vectơ hàng n-chiều, x là vectơ cột n-chiều và b1 ,..., bm là các số thực. Định nghĩa 1.11. (i) Một tập con lồi khác rỗng F  M được gọi là một diện của M nếu bất cứ đoạn thẳng nào nằm trong M và có một điểm trong tương đối x  F đều nằm trọn trong F. Nghĩa là: x  F , x   y  1    z, 0    1, y, z  M  y  F , z  F . (ii) Số chiều (hay thứ nguyên) của diện F, ký hiệu bởi dimF, được định nghĩa là số chiều của đa tạp tuyến tính nhỏ nhất chứa nó. (iii) Diện 0 - chiều gọi là một đỉnh. (iv) Diện 1- chiều gọi là một cạnh. Một đỉnh (hay cạnh) của một diện của M cũng là một đỉnh (hay cạnh) của chính M. Mệnh đề 1.2. Tập con khác rỗng F  M là diện của M khi và chỉ khi tồn tại một tập chỉ số I  1,..., m sao cho F là tập nghiệm của hệ: ai , x  bi , i  I (1.2) a , x  b j , j 1,..., m \ I , i   đồng thời khi đó ta có: dim F  n  rank ai : i  I . Ở đây, rank a i : i  I  là số các vectơ độc lập tuyến tính cực đại trong bộ các   vectơ ai : i  I . Định nghĩa 1.12. Nón lùi xa của tập lồi đa diện P được ký hiệu và định nghĩa bởi: Re cP : v  R n : x  tv  M với mọi x  M và t  0  Mệnh đề 1.3. i) Nón lùi xa RecM của tập lồi đa diện M là tập nghiệm của hệ ai , x  0, i  1,..., m; (1.3) ii) Re cM  0 khi và chỉ khi M là bị chặn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn   Định nghĩa 1.13. Cho tập các vectơ v1,..., vk  R n . Nón lồi sinh bởi các vectơ này được ký hiệu và định nghĩa bởi:   k  cone v1,..., v k : v : v   ivi với i  0, i  1,..., k i1   Định nghĩa 1.14. Đối với một tập X  Rn cho trước, nón cực (polar) X0 của tập X được định nghĩa bởi: X 0 : v  R n : v, x  0  x  X  . Từ định nghĩa chúng ta dễ dàng nhận thấy nón cực của một tập lồi đa diện cũng là một tập lồi đa diện. 1.4. Nón pháp tuyến của tập lồi đa diện Định nghĩa 1.15. Cho X là một tập lồi khác rỗng trong Rn và một điểm x0  X . Nón pháp tuyến của X tại x0, kí hiệu là N X  x 0  và được định nghĩa như sau: N X  x 0  : v  R n : v, x  x 0  0  x  X  . Từ định nghĩa ta dễ dàng suy ra N X  x 0  là một nón lồi đóng có đỉnh tại 0 và N X  x 0   0 khi x0 là một điểm trong của X. Xét một tập lồi đa diện cố định P khác rỗng trong Rn được xác định bởi hệ (1.1). Với mỗi x0  M ta kí hiệu:     I x0 : i 1,..., m ai , x0  bi .   Như thường lệ, ta gọi I x0 là tập hợp các chỉ số của những ràng buộc chặt tại x0. Cho F là một diện của tập lồi đa diện M. Kí hiệu.   I F : i 1,..., m : ai , x  bi  x  F . Ta gọi IF là tập chỉ số xác định diện F. Như vậy, F là nghiệm của hệ (1.2) với I = IF. Mệnh đề sau đây mô tả mối liên hệ giữa các tập chỉ số IF và I(x) với x  F . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mệnh đề 1.4. Cho IF là tập chỉ số xác định một diện F của M. Khi đó với mỗi x  F tập chỉ số IF là tập con của I(x) và IF = I(x) khi và chỉ khi x là một điểm trong tương đối của F. Chứng minh. Vì x  F nên I F  I  x  là hiển nhiên từ định nghĩa. Giả sử x là j IF . một điểm trong tương đối của F và Khi đó, nếu a j , x = b j thì a j , x = b j với mọi x  F . Điều này mâu thuẫn với giả thiết. Do đó, a j , x > b j , nghĩa là Ngược lại, giả sử j  I  x  . Vì vậy, I F  I  x  . I F  I  x  . Gọi là diện nhỏ nhất của M chứa x. Khi đó x là một điểm tương đối của F và F là một diện của F. Một mặt ta có IF  IF vì F  F . Mặt khác, theo phần đầu của chứng minh, ta có I  x   I F . Do đó. Vì vậy F  F và x là một điểm tương đối của F.  Từ định nghĩa có thể thấy rằng nón pháp tuyến của các điểm trong tương đối của một diện F là trùng nhau. Với lý do đó, ta kí hiệu N(F) là nón pháp tuyến của M tại một điểm trong tương đối của F và gọi nó là nón pháp tuyến của diện F. Theo Mệnh đề 1.3, ta có: N  F   conea i : i  I F  . Giả sử Fi ,..., FK  là tập tất cả các diện của M bao gồm cả chính M. Ta có biểu K K k 1 k 1 M  U FK  U ri FK , diễn: ở đây riFk là kí hiệu phần trong tương đối của Fk. Điều này nhận được trực tiếp từ các tính chất: (i) Mỗi đa diện là hợp của phần trong tương đối và các diện con của nó; (ii) Phần trong tương đối của diện 0 - chiều bằng chính nó. Đặt N M  U N  Fk  . K k 1 Ta có mệnh đề sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i) N M   xM  N M  x  và Mệnh đề 1.5. ii) N M   Re cM  0 Hệ quả 1.1. Tập N P là một nón lồi đa diện và N M  R n khi và chỉ khi M là bị chặn. Mối quan hệ giữa tập các diện F1 ,..., FK  của một tập lồi đa diện M và tập các nón pháp tuyến  N  F1  ,..., N  FK  được mô tả bởi mệnh đề sau. Mệnh đề 1.6. (i) Nếu Fi là một diện của Fj thì N(Fj) là một diện của N(Fi). Ngược lại, nếu N là một diện của N(Fi) thì tồn tại một diện Fk của M sao cho N  N  Fk  và Fi  Fk . (ii) riN  Fi   riN  Fj   0 voi i  j . 1.5. Tập chỉ số pháp tuyến Xét một tập lồi đa diện cố định khác rỗng M được xác định bởi hệ ràng buộc a i , x  bi , i  1,...m (1.4) trong đó a1,..., a m , a là các vectơ hàng n-chiều, x là vectơ cột n-chiều và bi , i  1,..., m là các số thực. Giả thiết rằng hệ (1.4) không có bất đẳng thức thừa, nghĩa là không tồn tại một chỉ số k 1,..., m nào cho hệ (1.4) tương đương với ai , x  bi , i i,..., m \ k  . hệ: Để phục vụ cho việc tính toán, sau đây ta đưa ra khái niệm tập chỉ số pháp tuyến. Định nghĩa 1.16. Một tập con I  1,..., m được gọi là tập chỉ số pháp tuyến nếu tồn tại một điểm x  M sao cho N M  x   cone  a i : i  I  . Rõ ràng không phải bất kỳ tập con nào của tập 1,...,m cũng là tập chỉ số pháp tuyến. Dưới đây sẽ trình bày mối liên hệ giữa các diện của một tập lồi đa diện M xác định bởi hệ (1.4) và các tập chỉ số pháp tuyến. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mệnh đề 1.7. Tập I  1,..., m là tập chỉ số pháp tuyến khi và chỉ khi tập I xác định một diện F của M. Chứng minh. Cho I là tập chỉ số xác định một diện F của M, tức là F được xác ai , x  bi , i  I định bởi hệ : a j , x  b j , j 1,... ,m \ I . Gọi x0   là một điểm trong tương đối của F. Khi đó, I x0  I . Theo định nghĩa, I là một tập chỉ số pháp tuyến.   Ngược lại, cho I  1,...,m và I là một tập chỉ số pháp tuyến. Theo định nghĩa, tồn tại một điểm x0  M sao cho    NM x0  cone ai : i  I Do đó với mỗi i  I ta có ai , x0  biểu diễn của M nên dễ thấy rằng ai , x0 x0  M với mọi x  M . Nói cách khác, ai , x phiếm hàm ai , . trên M đạt cực tiểu tại . x 0 . Vì không có ràng buộc thừa trong  bi với mọi i  I . Hơn nữa, vì nên tập nghiệm F của hệ ai , x  bi , i  I a j , x  b j , j 1,... ,m \ I là khác rỗng. Theo mệnh đề 1.2, F là một diện của M. Giả sử x0 là một đỉnh của tập lồi đa diện M. Nhắc lại rằng   I x0 : i 1,..., m : ai , x0  bi    là tập hợp các chỉ số của những ràng buộc chặt tại x0. Kết quả sau chỉ ra điều   kiện để một tập con I  I x0 là một tập chỉ số pháp tuyến. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hệ quả 1.2. Cho I  I  x 0  và I có n-1 phần tử. Khi đó I là một tập chỉ số pháp tuyến khi và chỉ khi hệ: ai , x  bi , i  I (1.5) a j , x  b j , j 1,..., m \ I có một nghiệm khác với x0. Chứng minh. Giả sử I là một tập chỉ số pháp tuyến. Theo mệnh đề 1.7, I xác định một diện F của M, tức F là tập nghiệm của hệ (1.5). Mệnh đề 1.2 chỉ ra rằng   dim F  n  rank ai : i  I  n   n 1  1. Do đó hệ này có một nghiệm khác với x0 . □ Khẳng định sau đây có thể suy ra trực tiếp từ định nghĩa và Mệnh đề 1.7. Hệ quả 1.3. Giả sử I1 , I 2  1,..., m là hai tập chỉ số pháp tuyến. Nếu I 0  I1  I 2  0 thì I0 cũng là một tập chỉ số pháp tuyến. Bây giờ giả sử rằng có r cạnh E1 ,...Er xuất phát từ đỉnh x0 của tập lồi đa diện M. Gọi I Ei là tập chỉ số xác định cạnh Ei, với i = 1,...,r. Khi đó, mỗi tập I E có ít i nhất n-1 phần tử. Cho J  i,..., r  . Giả thiết rằng J có l phần tử và l  min r, n  1 . Xét một điểm: x0 xj x   l  1 jI l  1 J với x j  E j \  x 0  , j  J . Như qui ước ở phần trên, I  x J  được kí hiệu là tập hợp các chỉ số của những ràng buộc chặt tại xJ. Kết quả sau cho phép ta xác định diện lớn nhất của M chứa xJ như một điểm trong tương đối. Mệnh đề 1.8. Giả sử I  x J   0 . Khi đó I  x J  là một tập chỉ số pháp tuyến. Hơn nữa, diện F xác định bởi I F  I  x J  chứa bao lồi của tất cả các cạnh EJ , j 1,..., r thoả mãn I Ej  I  x J  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.6 Nón pháp tuyến âm, chỉ số pháp tuyến âm Cho C là một ma trận cấp  p x n  với các hàng c1,..., c p . Định nghĩa 1.17. i) Véctơ v  R n được gọi là véctơ C-âm nếu tồn tại các số âm p 1  0,..., p  0 sao cho v   ici . i1 ii) Véctơ v R n được gọi là véctơ C-âm yếu nếu tồn tại các số không dương 1  0,..., p  0 và các i không đồng nhất bằng không sao cho v  i 1 i c . p i Dễ thấy các véctơ C- âm có các tính chất sau: a) Cho p  n và C là ma trận đồng nhất. Khi đó v  R n là C-âm nếu và chỉ nếu v  0; b) Tập các véctơ C-âm trùng với phần trong tương đối của nón sinh bởi các 1 p véctơ c ,..., c . Cho M là tập lồi đa diện được xác định bởi hệ (1.4). Định nghĩa 1.18. i) Nón pháp tuyến của M tại x0 được gọi là nón pháp tuyến âm nếu nó chứa một véctơ C-âm.   ii) Một tập chỉ số con I  1,..., m được gọi là tập chỉ số âm nếu nón sinh bởi a : i  I chứa một véctơ C-âm. i Từ định nghĩa ta thấy rằng, việc kiểm tra tính âm và âm yếu của một tập chỉ số I được qui về việc xác định sự tồn tại nghiệm của một hệ phương trình và bất phương trình tuyến tính.   Mệnh đề 1.9. i) Tập con I  1,..., m là một tập chỉ số âm khi và chỉ khi hệ sau có nghiệm. j i p  i a    j c iI j 1 i  0,  j  0 với i  I , j  1,..., p Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (1.6) http://www.lrc-tnu.edu.vn   ii) Tập con I  1,..., m là một tập chỉ số âm yếu khi và chỉ khi hệ sau có nghiệm. j i p  i a    j c iI j 1 i  0,  j  0 với i  I , j  1,..., p (1.7) p   j 1 j 1 Nhận xét 1.1. Lưu ý rằng,   ,   là nghiệm của (1.6) khi và chỉ khi t   ,   là nghiệm của (1.6) với mọi t > 0. Do đó trong hệ (1.6) thay vì điều kiện lấy j  0 ta  j  1 với j  1,..., p . Đặt  'j   j  1  0, j  1,..., p và đổi biến trong hệ (1.6) ta nhận được hệ bất đẳng thức tuyến tính trong đó không có các bất phương trình với dấu bất đẳng thức chặt.   Ta kí hiệu I1 là tập các chỉ số i  1,..., m với  ai là véctơ C-âm; I3 là tập  các chỉ số i  1,..., m với ai là véctơ C-âm nhưng ai không phải là véctơ C-âm   và I : 1,..., m \ I  I . Rõ ràng các tập I1, I2, I3 là đôi một không giao nhau 2 1 3 và I1  I 2  I3  1,..., m . Mệnh đề 1.10. Giả sử I  I1  I 2  I3 là một tập chỉ số pháp tuyến âm sao cho   nón sinh bởi các vectơ ai : i  I không chứa một không gian con tuyến tính nào. Khi đó tồn tại một tập chỉ số pháp tuyến âm I 0  I   I1  I 2  .   Chứng minh. Cho I  i ,..., i  I  I  I là một tập chỉ số pháp tuyến âm. 1  1 2 3 Ta chứng minh Mệnh đề bằng cách qui nạp theo  . Cho   1 . Giả sử I là một tập chỉ số pháp tuyến âm. Theo định nghĩa nón   cone ai1 phải chứa một véctơ C-âm. Do đó ai1 phải là một véctơ C-âm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Suy ra I  I1 . Chọn I 0  I ta thấy ngay rằng kết luận của mệnh đề nghiệm đúng. Giả sử   1 . Rõ ràng I   I1  I 2   0 . Nếu I  I3  0 thì Mệnh đề đã được khẳng định. Nếu I  I3  0 , ta giả sử i  I 3 . Theo định nghĩa,  a i là  véctơ C-âm. Vì I là tập chỉ số pháp tuyến âm nên cone ai : i  i1,..., i chứa một véctơ C-âm. Ta khẳng định rằng phần trong tương đối của nó không chứa tất cả các véctơ C-âm. Thật vậy, giả sử phần trong tương đối của nó chứa tất cả các véctơ C-âm, vì a i là véctơ C-âm nên coneai : i  i1,..., i  phải chứa véctơ 0 trong phần trong tương đối của nó. Điều này mâu thuẫn với giả thiết của   mệnh đề rằng nón sinh bởi các vectơ ai : i  I không chứa một không gian còn tuyến tính nào. Suy ra, tồn tại một véctơ C-âm v nằm ngoài phần trong   tương đối của cone ai : i  i1,...,i . Đoạn nối véctơ v này với một véctơ C-   âm nằm trong phần trong tương đối của cone ai : i  i1,..., i sẽ cắt một diện   của nón cone ai : i  i1,..., i có chứa một véctơ C- âm. Số véctơ sinh ra diện này là nhỏ hơn hẳn  . Theo giả thiết qui nạp, tồn tại một nón pháp tuyến âm sinh bởi các véctơ có chỉ số nằm trong I1  I 2 . Tập chỉ số xác định nón này là tập chỉ số pháp tuyến âm nằm trong I   I1  I 2  . Mệnh đề đã được chứng □ minh. 1.7 Kết luận Trong chương này trình bày khái niệm các khái niệm cơ bản về tập affine, tập lồi, tập lồi đa diện, nón pháp tuyến, chỉ số pháp tuyến của tập lồi đa diện và nón pháp tuyến âm, chỉ số pháp tuyến âm. Đây là những kiến thức liên quan tới phần trình bày của luận văn ở Chương 2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chƣơng 2 Phƣơng pháp nón pháp tuyến giải bài toán quy hoạch tuyến tính đa mục tiêu Nội dung chính của chương này là trình bày về bài toán quy hoạch tuyến tính đa mục tiêu và phương pháp nón pháp tuyến giải bài toán. Trước hết chúng ta sẽ trình bày một số khái niệm cơ bản dẫn tới khái niệm về bài toán quy hoạch tuyến tính đa mục tiêu. 2.1. Điểm hữu hiệu Kí hiệu  p là không gian Euclide p - chiều. Phần trong, phần trong tương đối và biên của một tập con Q   Véctơ e = (1,1,...,1), i p p được ký hiệu tương ứng là intQ, riQ và Q. là véctơ có tất cả các thành phần đều bằng 1, tức ei = 1  i = 1,2,...,p.     Cho hai véctơ y1  y11, y12 ,..., y1p , y 2  y12 , y22 ,..., y 2p   p . Ta viết y1  y2 nếu yi1  yi2  i = 1,2,....,p;  p y1  y2 nếu y1  y2 và y1  y 2 ; y1  y2 nếu yi1  yi2  i = 1,2,....,p. Nói cách khác, y1  y2 nếu y1  y2  p ; y1  y2 nếu y1  y 2   p \ 0  ;   y1  y2 nếu y1  y2 int  p ; trong đó  p    y   y1, y2 ,..., y p    p : yi  0 i  1,2,..., p  .   Định nghĩa 2.1. Cho Q là tập con khác rỗng trong  p . Ta nói điểm y0Q là: (i) điểm hữu hiệu (hay điểm cực tiểu Pareto) của Q nếu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn   y Q sao cho y0 > y, tức là Q  y 0   p     y . 0 (ii) điểm hữu hiệu yếu (hay điểm cực tiểu Pareto yếu) của Q nếu   y Q sao cho y0 >> y, tức là Q  y 0  int  p    0. Kí hiệu MinQ là tập tất cả các điểm hữu hiệu của Q và WMinQ là tập tất cả các điểm hữu hiệu yếu của Q. Theo định nghĩa ta có: MinQ  WMinQ Lƣu ý: Các khái niệm điểm hữu hiệu và điểm hữu hiệu yếu của một tập hợp Q   p theo hướng cực đại được định nghĩa hoàn toàn tương tự. Các kết quả sau đây là tương đối hiển nhiên: (i) Nếu y0 là một điểm hữu hiệu hoặc là một điểm hữu hiệu yếu của tập Q thì y0 phải thuộc vào biên Q của Q; (ii) Q là tập compact khác rỗng thì ta luôn có Min Q ≠  . Sau đây là điều kiện cần và đủ để một điểm y0  p là một điểm hữu hiệu (hữu hiệu yếu) của tập con lồi khác rỗng Q   p . Định lý 2.1 (Theo Định lý 2.10 trang 91, [11]) Cho Q là một tập con lồi khác rỗng trong không gian  p . Khi đó, điểm y0 Q là điểm hữu hiệu (tương ứng hữu hiệu yếu) của Q khi và chỉ khi tồn tại vectơ   0 (tương ứng  > 0) thuộc  p sao cho y0 là nghiệm cực tiểu của bài toán quy hoạch lồi với hàm mục tiêu tuyến tính: Min (, y) với điều kiện y Q. 2.2. Bài toán quy hoạch tuyến tính đa mục tiêu n Cho X là tập con lồi đóng khác rỗng trong  và f j :  n   , j  1, 2,..., p là các hàm lồi nhận giá trị hữu hạn trên X. Bài toán qui hoạch lồi đa mục tiêu được phát biểu như sau: Min f(x) với điều kiện x  X, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (CMOP) http://www.lrc-tnu.edu.vn
- Xem thêm -

Tài liệu liên quan