Create a Joomla website with Joomla Templates. These Joomla Themes are reviewed and tested for optimal performance. High Quality, Premium Joomla Templates for Your Site
nafosted

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:

TT Họ và tên Đơn vị Nhiệm vụ
1 TS. Nguyễn Trung Thành Khoa Toán – ĐH Hải Phòng Chủ nhiệm đề tài
2 TS. Lê Đắc Nhường Khoa CNTT – ĐH Hải Phòng Nghiên cứu viên chính
3 TS. Nguyễn Gia Như Phòng sau đại học – ĐH Duy Tân Thư kí
4 TS. Lê Đăng Nguyên Phòng Khảo thí – ĐH Hải Phòng Nghiên cứu viên
5 ThS. Nguyễn Ngọc Khương Khoa CNTT – ĐH Hải Phòng Kĩ thuật viên
BÀI VIẾT CÙNG CHUYÊN MỤC