Thạc Sĩ Bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu hàm phân thức a - phin

Mục lục
Mục lục i
Lời cảm ơn iii
Mở đầu 1
1 Các kiến thức cơ bản về tập lồi, hàm lồi 5
1.1 Tổ hợp lồi . 5
1.2 Tập a-phin, tập lồi đa diện 7
1.3 Nón lồi . 12
1.4 Định lý tách các tập lồi đa diện . 15
1.5 Định lý minimax 17
2 Bài toán tối ưu véc-tơ phân thức a-phin 19
2.1 Bài toán tối ưu véc-tơ . 19
2.2 Hàm phân thức a-phin 20
2.3 Bài toán tối ưu véc-tơ phân thức a-phin 23
3 Tiếp cận quy hoạch song tuyến tính giải bài toán tối ưu
trên tập hữu hiệu của bài toán tối ưu đa mục tiêu phân
thức a-phin 28
3.1 Bài toán tối ưu trên tập hữu hiệu . 28
3.2 Phương pháp giải . 34
3.2.1 Phép tính cận theo đối ngẫu Lagrange 35
3.2.2 Phép chia đôi đơn hình . 39ii
3.2.3 Thuật toán dựa trên cách tính cận Lagrange (Thuật
toán LB) . 39
3.3 Phương pháp nới lỏng 43
3.3.1 Bài toán nới lỏng . 43
3.3.2 Phương pháp giải . 44
3.3.3 Thuật toán nới lỏng (Thuật toán RLB) 44
3.4 Ví dụ 46
KẾT LUẬN CHUNG 49
Tài liệu tham khảo 51iii
Lời cảm ơn
Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và
giúp đỡ của GS. Lê Dũng Mưu (Viện Toán học Việt Nam). Tôi xin chân
thành bày tỏ lòng biết ơn sâu sắc đến Thầy.
Tôi xin cảm ơn các quý thầy, cô giảng dạy tại Viện Toán học, đã mang
đến cho tôi nhiều kiến thức bổ ích trong khoa học và cuộc sống.
Tôi xin chân thành cảm ơn các bạn đồng nghiệp, các bạn đồng môn đã
giúp đỡ tôi trong thời gian học tập tại Viện Toán học và trong quá trình
hoàn thành luận văn này.
Hà Nội, tháng 8-2011
Người viết Luận văn
Hoàng Ngọc Tuy1
Mở đầu
Bài toán tối ưu đa mục tiêu, còn được gọi là bài toán tối ưu véc-tơ được
nảy sinh trong quá trình phát triển của kinh tế-xã hội, phục vụ cho các
hoạt động kinh tế-xã hội. Ví dụ, một công ty muốn tìm một phương án sản
xuất sao cho lợi nhuận cao nhất, chất lượng sản phẩm tốt nhất, giá thành
sản phẩm rẻ nhất nhưng lại ít ảnh hưởng tới môi trường nhất. Việc lựa
chọn phương án sản xuất của công ty trên dẫn tới việc giải một bài toán
tối ưu đa mục tiêu.
Các mục tiêu của bài toán tối ưu véc-tơ thường là độc lập với nhau,
thậm chí đối kháng nhau (chẳng hạn, nếu giảm chi phí sản xuất thì khó
đảm bảo chất lượng, nếu tăng lợi nhuận thì khó đảm bảo môi trường .).
Một phương án tốt nhất cho mục tiêu này thường thì không tốt nhất đối
với các mục tiêu khác, tức là phương án tốt nhất cho tất cả các mục tiêu
(phương án lý tưởng) rất hiếm khi xảy ra. Điều này dẫn tới một khái niệm
mới về nghiệm của bài toán tối ưu đa mục tiêu là nghiệm hữu hiệu, nghiệm
hữu hiệu yếu (hay nghiệm Pareto, nghiệm Pareto yếu). Khái niệm này
được đưa ra từ cuối thế kỷ 19, nhưng tối ưu đa mục tiêu chỉ trở thành một
chuyên nghành toán học và phá triển mạnh trong vòng 40 năm gần đây.
Một bộ phận quan trọng của tối ưu đa mục tiêu là tối ưu đa mục tiêu
tuyến tính. Cho đến nay, lớp các bài toán tối ưu đa mục tiêu tuyến tính
đã được nghiên cứu gần như hoàn chỉnh cả về phương diện định tính và
định lượng. Mặc dù bài toán tối ưu đa mục tiêu phân thức a-phin (bài toán
(VP)), còn được gọi là bài toán tối ưu véc-tơ phân thức a-phin là sự mở
rộng tự nhiên của bài toán tối ưu đa mục tiêu tuyến tính nhưng lớp các bài
toán tối ưu đa mục tiêu phân thức a-phin thực sự rộng hơn lớp các bài toán2
tối ưu đa mục tiêu tuyến tính. Các kết quả nghiên cứu đã cho thấy rằng,
tập nghiệm hữu hiệu của bài toán (VP) khác biệt và phức tạp hơn nhiều
so với tập nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu tuyến tính,
nhiều tính chất của trường hợp tuyến tính không còn đúng cho trường hợp
phân thức a-phin. Nhiều vấn đề nghiên cứu của lớp các bài toán (VP) vẫn
chưa có kết quả.
Trong nhiều vấn đề thực tế về kinh tế-xã hội, người ta phải giải bài toán
tối ưu trên tập hữu hiệu và hữu hiệu yếu. Ví dụ, một nhà máy bánh kẹo
sản xuất n loại sản phẩm gồm một số loại đường, một số loại bánh kẹo.
Số lượng các sản phẩm trên là x = (x1, x2, ., xn). Nhà máy muốn tìm một
phương án sản xuất số sản phẩm x sao cho thu được lợi nhuận cao nhất.
Tuy nhiên, nhà máy cũng muốn có một phương án sản xuất sao cho đảm
bảo về nguồn cung cấp nguyên liệu lâu dài. Như vậy, thay vì tìm phương
án sản xuất số sản phẩm x
∗
trên tập các phương án sản xuất chấp nhận
được sao cho thu được lợi nhuận cao nhất, nhà máy phải tìm phương án
sản xuất số sản phẩm x
0
sao cho thu được lợi nhuận cao nhất trên tập các
phương án sản xuất đảm bảo việc cung cấp nguyên liệu. Tất nhiên, phương
án sản xuất số sản phẩm x
0
thường không cho lợi nhuận cao bằng phương
án sản xuất số sản phẩm x
∗ nhưng phương án sản xuất số sản phẩm x
0
đảm bảo được nguồn cung cấp nguyên liệu cho nhà máy sản xuất lâu dài.
Việc tìm phương án sản xuất số sản phẩm x
0
chính là việc giải bài toán
cực đại hàm lợi nhuận trên tập hữu hiệu của bài toán tối ưu véc-tơ tuyến
tính.
Bài toán tối ưu trên tập hữu hiệu và hữu hiệu yếu thuộc lớp các bài
toán tối ưu hai cấp. Bài toán này được đưa ra lần đầu tiên vào năm 1972
và hiện nay đang rất được quan tâm vì những ứng dụng thực tế của nó.
Bài toán tối ưu trên tập hữu hiệu của bài toán (VP) (bài toán (P)) và bài
toán tối ưu trên tập hữu hiệu yếu của bài toán (VP) (bài toán (WP)) là
một dạng của bài toán tối ưu hai cấp. Bài toán (P) và bài toán (WP) cũng
là sự phát triển tự nhiên của bài toán tối ưu trên tập hữu hiệu và hữu hiệu
yếu của bài toán tối ưu véc-tơ tuyến tính. Trong rất nhiều các hoạt động3
kinh tế-xã hội trên thực tế hiện nay cũng đòi hỏi phải giải bài toán này.
Ví dụ, một công ty bánh kẹo có p nhà máy (đặt tại các địa phương khác
nhau), mỗi nhà máy sản xuất n loại bánh kẹo khác nhau. Hàm lợi nhuận
f(x) của công ty phụ thuộc vào phương án sản xuất số lượng sản phẩm
x = (x1, x2, ., xn) (n loại bánh kẹo). Công ty muốn tìm một phương án sản
xuất số lượng sản phẩm x sao cho lợi nhuận thu được là cao nhất. Để tuân
thủ luật bảo vệ môi trường, công ty phải tìm một phương án sản xuất số
lượng sản phẩm x sao cho tỷ số giữa chi phí bảo vệ môi trường của mỗi
nhà máy và tổng chi phí của nhà máy ấy là nhỏ nhất. Như vậy, thay vì tìm
cực đại hàm f(x) trên tập các phương án sản xuất chấp nhận được, công
ty phải thực hiện bài toán cực đại hàm f(x) trên tập hữu hiệu của bài toán
tối ưu véc-tơ phân thức a-phin (sẽ được trình bày ở chương 3), tức là, tìm
phương án sản xuất số lượng sản phẩm x
0
sao cho thu được lợi nhuận cao
nhất trên tập các phương án sản xuất thỏa mãn yêu cầu về luật bảo vệ
môi trường.
Hiện nay, bài toán (P) và bài toán (WP) đang được nhiều người quan
tâm nhưng việc nghiên cứu các bài toán này là rất khó khăn. Bài toán tối
ưu trên tập hữu hiệu và hữu hiệu yếu của bài toán tối ưu đa mục tiêu tuyến
tính cũng là những bài toán khó và cũng mới được nghiên cứu nhưng đã
có một số phương pháp giải được công bố. Trong khi đó, mới chỉ có một
số rất ít ý tưởng về thuật toán và thuật toán để tìm nghiệm của bài toán
(P) và bài toán (WP) được công bố (xem [11], [14]). Việc nghiên cứu các
bài toán (P) và bài toán (WP) gặp rất nhiều khó khăn bởi vì tập nghiệm
của bài toán (VP) thường là không lồi, không còn là hợp của một số mặt
của đa diện ràng buộc và có cấu trúc phức tạp. Mặt khác, sự khó khăn còn
do các bài toán này mới đươc nghiên cứu trong thời gian gần đây. Hầu hết
các thuật toán được đưa ra đều yêu cầu tất cả các đỉnh của khối đa diện
ràng buộc X phải được biết trước. Do đó, các thuật toán này chỉ được xây
dựng khi các đỉnh của X dễ tính toán. Trong khi đó, việc tính toán tất cả
các đỉnh của X thường là rất khó. Thuật toán nới lỏng được trình bày ở
chương 3 chỉ đòi hỏi biết trước một đỉnh của X, từng đỉnh mới của X có4
thể được tính (nếu cần) trong mỗi bước lặp của thủ tục nhánh-cận. Vì thế,
chúng ta có thể mong rằng thuật toán này tìm thấy lời giải tối ưu toàn cục
mà không cần phải tính tất cả các đỉnh của X.
Mục đích chính của luận văn này là trình bày bài toán (VP), bài toán
(P) và bài toán (WP), trình bày hai phương pháp cùng với hai thuật toán
giải bài toán (WP). Luận văn bao gồm 3 chương.
Chương 1: trình bày lại một số kiến thức cơ bản về giải tích lồi như tập
lồi, tập lồi đa diện, nón lồi . và một số định lý là định lý tách các tập lồi
đa diện, định lý minimax, định lý đối ngẫu Lagrange.
Chương 2: trình bày bài toán (VP), trình bày một định lý của Malivert
và hệ quả của định lý này về điều kiện cần và đủ của nghiệm hữu hiệu và
hữu hiệu yếu của bài toán (VP).
Chương 3: trình bày bài toán (P) và bài toán (WP), trình bày cách
chuyển hai bài toán này về dạng dễ khảo sát hơn là (PΛ). Sau đó, trình
bày hai phương pháp để các giải bài toán (WP) là phương pháp tính cận
theo đối ngẫu Lagrange và phương pháp nới lỏng. Với mỗi một phương
pháp, chúng ta trình bày một thuật toán và chứng minh tính dừng của các
thuật toán này.
Luận văn này được hoàn thành tại Viện Toán học, Viện Khoa học tự
nhiên và Công nghệ quốc gia, dưới sự hướng dẫn của GS.TSKH Lê Dũng
Mưu. Mặc dù tác giả đã hết sức cố gắng, nhưng do thời gian có hạn và
kinh nghiệm nghiên cứu còn rất hạn chế nên khó tránh khỏi thiếu sót. Tác
giả mong được các Thầy, các Cô và bạn đọc góp ý