Đề tài nghiên cứu cơ bản do Quỹ Phát triển khoa học và công nghệ Quốc gia tài trợ năm 2015 (NAFOSTED)

27-07-17 Dac-Nhuong Le 0 comment

Tên đề tài: Phân chia tài nguyên: Độ phức tạp và Thuật toán xấp xỉ

Chủ nhiệm: TS Nguyễn Trung Thành, Khoa Toán – Trường ĐH Hải Phòng

Thời gian thực hiện: 24 tháng (2016-2017)

Tóm tắt vấn đề nghiên cứu: Phân chia tài nguyên (resource allocation) là một trong những bài toán cơ bản nhưng có vai trò đặc biệt quan trọng trong Toán học, Khoa học máy tính, Khoa học xã hội, và Kinh tế học. Các ứng dụng nổi bật của bài toán này bao gồm: tối ưu hoá trong sản xuất và lập kế hoạch (manufacturing and scheduling), quản lý khủng hoảng (crisis management), quản lý giao thông hàng không (airport traffic management), vận tải (logistic), giao thông công cộng (public transport), vệ tinh quan sát trái đất (Earth Observation Satellites), đấu giá tổ hợp (combinatorial auction), smart grid (lưới thông minh). Bài toán phân chia tài nguyên có thể phát biểu đơn giản như sau: cho trước m món hàng hoá khác nhau và n khách hàng (khách hàng ở đây có thể là các cá nhân, công ty, hay tập thể nào đó); cần phân chia các món hàng hoá này cho các khách hàng theo một tiêu chí nào đó, với các ràng buộc cho trước đối với tập các món hàng. Ở đây, ta giải thiết rằng mỗi khách hàng có đánh giá riêng đối với các món hàng hoá mà họ có thể được nhận. Các đánh giá này có thể được biểu thị bằng nhiều cách khách nhau. Chẳng hạn, mỗi khách hàng có thể sắp xếp các món hàng hoá từ thấp đến cao theo mức độ ưa thích của họ; hay sử dụng một hàm số (tuyến tính hay phi tuyến) m biến số để định lượng giá trị cụ thể của các món hàng hoá. Về mặt toán học, một dạng cơ bản của bài toán phân chia tài nguyên có thể được mô hình hoá như sau:

tt

Bài toán phân chia tài nguyên là một bài toán tối ưu rời rạc (hoặc liên tục) thuộc lớp NP-khó (tức là hầu như không thể tìm được lời giải tối ưu trong “thời gian đa thức”). Do đó, các hướng nghiên cứu hiện nay đều tập trung vào việc tìm kiếm các lời giải xấp xỉ với sai số nhỏ chấp nhận được.

Mục đích của đề tài: Đề tài tập trung nghiên cứu độ phức tạp tính toán và lời giải xấp xỉ cho một lớp các biến thể của bài toán phân chia tài nguyên, dựa trên cách mà mỗi khách hàng biểu thị sự ưa thích của họ đối với tập món hàng.

Danh sách thành viên:

TTHọ và tênĐơn vịNhiệm vụ
1TS. Nguyễn Trung ThànhKhoa Toán – ĐH Hải PhòngChủ nhiệm đề tài
2TS. Lê Đắc NhườngKhoa CNTT – ĐH Hải PhòngNghiên cứu viên chính
3TS. Nguyễn Gia NhưPhòng sau đại học – ĐH Duy TânThư kí
4TS. Lê Đăng NguyênPhòng Khảo thí – ĐH Hải PhòngNghiên cứu viên
5ThS. Nguyễn Ngọc KhươngKhoa CNTT – ĐH Hải PhòngKĩ thuật viên


Leave a reply