Luận Văn Qui 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ột mi

Qui 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ột miền chấp nhận đượcTrong những năm gần đây, các phương pháp tối ưu hoá ngày càng được áp dụng sâu rộng và hiệu quả vào các nghành kinh tế, kỹ thuật, công nghệ thông tin và các nghành khoa học khác. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính.
Một trong những lớp bài toán tối ưu đầu tiên được ngiên cứu trọn vẹn cả về lý thuyết lẫn thuật toán là bài toán qui hoạch tuyến tính (QHTT). Qui hoạch tuyến tính ngay từ khi ra đời (vào cuối năm 30 của thế kỷ XX) đã chiếm vị trí quan trọng trong tối ưu hoá. Mô hình tuyến tính là mô hình rất phổ biến trong thực tế vì sự phụ phuộc tuyến tính là sự phụ thuộc đơn giản và dễ hiểu nhất. Hơn nữa, về mặt lý thuyết chúng ta biết rằng có thể xấp xỉ với độ chính xác cao các bài toán phi tuyến bởi dãy các bài toán qui hoạch tuyến tính. Nói cách khác, các thuật toán giải QHTT là công cụ quan trọng trong việc nghiên cứu giải các bài toán phức tạp hơn. Thuật toán đơn hình do Dantzig đề xuất từ 1947, đến nay vẫn là một phương pháp được sử dụng rộng rãi. Mặc dù về lý thuyết đây là phương pháp có độ phức tạp mũ. Sau lớp bài toán qui hoạch tuyến tính, nhiều hướng nghiên cứu khác nhau xuất hiện như qui hoạch lồi, qui hoạch toàn cục và lý thuyết điều khiển tối ưu.


Bài toán qui hoạch đa mục tiêu cũng mới được phát triển và trở thành một chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà qui hoạch tuyến tính không giải được, chẳng hạn như trong một công ty ngoài việc nâng cao chất lượng sản phẩm thì công ty cũng chú trọng tới đa dạng hoá sản phẩm, già thành rẻ, doanh thu lớn, Khách hàng khi chọn mua hàng thì muốn hàng rẻ, vừa có chất lượng cao, vừa có hình thức đẹp. Tóm lại, mục đích của bài toán qui 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ột miền chấp nhận được. Do không gian giá trị của lớp bài toán này không được sắp thứ tự toàn phần, nên khái niệm nghiệm thông thường không còn thích hợp. Trong qui hoạch đa mục tiêu, cùng với khái niệm thứ tự từng phần, ta sẽ sử dụng khái niệm nghiệm hữu hiệu.


Một phương án chấp nhận được được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn.
Đầu thế kỷ XX, Pareto đã sử dụng khái niệm này khi ông nghiên cứu phúc lợi và thu nhập của dân chúng. Ông đã lập luận như sau: "Nếu thu nhập của một nhóm dân cư tăng lên, nhưng thu nhập của một nhóm khác giảm xuống thì khi đó không thể so sánh "phúc lợi" của toàn xã hội. Đó là trường hợp không so sánh được. Nhưng có thể thấy rằng, phúc lợi xã hội sẽ tăng lên nếu thu nhập của ít nhất một nhóm người nào đó lớn lên, còn thu nhập của những nhóm khác không thấp xuống". Ta nhận thấy rằng, theo quan điểm của toán học, khái niệm nghiệm hữu hiệu mà chúng ta dùng trong qui hoạch đa mục tiêu phù hợp với luận đề Pareto.


Khi hàm mục tiêu đều là hàm tuyến tính và miền ràng buộc là tập lồi đa diện khác rỗng trong , ta nhận được bài toán qui hoạch tuyến tính đa mục tiêu. Cho tới nay, có rất nhiều thuật toán đưa ra để 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, chẳng hạn: phương pháp vô hướng hoá, phương pháp tham số, phương pháp đơn hình đa mục tiêu và các dạng cải biên, phương pháp nón pháp tuyến .(xem [6, 7, 8-9, 12, 17, 19, 21-22, và 24-25]).


Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán qui hoạch tuyến tính đa mục tiêu (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng.


Trong những năm gần đây nhiều nhà toán học đã chuyển sang nghiên cứu giải quyết bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Trong báo cáo này, em sẽ trình bày thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị của H.P. Benson, đó là nội dung bài báo: "Hybrid Approach for Solving Multipe-Objective Linear Programs in Outcome Space". Jota: Vol. 98, NO. 1, July, 1998.
Kết cấu đề tài bao gồm:
Chương I: Một số khái niệm cơ bản về giải tích lồi và bài toán qui hoạch tuyến tính.
Chương II: Bài toán qui hoạch tuyến tính đa mục tiêu.
Chương III: Bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị.