BỘ KHOA HỌC VÀ CÔNG NGHỆ
HỆ THỐNG THÔNG TIN QUỐC GIA VỀ KHOA HỌC, CÔNG NGHỆ VÀ ĐỔI MỚI SÁNG TẠO

Các nhiệm vụ khác
liên kết website
Lượt truy cập
 Lượt truy cập :  31,636,982
  • Kết quả thực hiện nhiệm vụ

101.01-2019.325

2023-52-0645/NS-KQNC

Thuật toán cho bài toán tối ưu tổ hợp và các vấn đề có liên quan

Trường Đại Học Cần Thơ

Bộ Giáo dục và Đào tạo

Quốc gia

TS. Nguyễn Trung Kiên

TS. Nguyễn Thư Hương, TS. Nguyễn Thanh Hùng(1), TS. Phạm Thị Vui, TS. Lê Phương Thảo

Toán học cơ bản

01/04/2020

01/04/2023

2023

Cần Thơ

95 tr. + phụ lục

Nghiên cứu tính chất nghiệm của các bài toán tối ưu tổ hợp bao gồm bài toán tối ưu với hàm kmax (lấy giá trị lớn thứ k), các dạng khác nhau của bài toán xếp ba lô (knapsack problem), bài toán vị trí với p vị trí mới. Từ đó, rút ra được điều kiện tối ưu cho từng bài toán. Trong bài toán tối ưu tổ hợp ngược, ta cố gắng thay đổi các tham số với sai khác nhỏ nhất ứng với hàm mục tiêu sao cho nghiệm được xác định trước thỏa mãn điều kiện tối ưu ứng với tham số mới. Vì vậy, việc nghiên cứu tính chất của các hàm mục tiêu, hay còn gọi là hàm chi phí, là chìa khóa để giải quyết bài toán tối ưu tổ hợp ngược. Nghiên cứu các giải thuật thường gặp của bài toán tối ưu tổ hợp như giải thuật tham lam, giải thuật phân đôi, quy hoạch động… nhằm áp dụng giải quyết một số bài toán đã nêu trong thời gian đa thức. Nghiên cứu các bài toán kinh điển thuộc lớp NP-đầy đủ để có thể đưa một bài toán tối ưu tổ hợp về một bài toán trong lớp này. Từ đó, ta có thể chứng minh được tính chất NP-khó của một số mô hình đề xuất.

Thuật toán, Bài toán tối ưu, Hàm kmax, Bài toán xếp ba lô, Tham số, Bài toán vị trí

24 Lý Thường Kiệt, Hà Nội

22295