ĐẠ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
i1
Đị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 conea 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 xM 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 jI 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 .
i1
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
iI
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
iI
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 coneai : 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 y0Q 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 -