Устойчивость и эффективные алгоритмы решения задач дискретной оптимизации с многими критериями и неполной информацией

Abstract

Досліджено проблему стійкості векторних задач дискретної оптимізації з різними принципами оптимальності щодо збурень всіх вхідних даних задачі на основі отриманих результатів про властивості ядра стійкості та підмножини тих допустимих розв’язків, що стійко не належать оптимальній множині. Наведено огляд останніх результатів стосовно оцінок радіуса стійкості розв’язків багатокритеріальних булевих задач з нелінійними критеріями. Для задачі з відомим оптимальним значенням цільової функції побудовано алгоритм з найкращою відомою гарантованою оцінкою. У наведеній схемі використано групові технології і динамічні нижні оцінки для оптимального значення цільового функціонала, які можуть застосовуватись для різних версій задач з неповною інформацією.

The problem of stability of vector discrete optimization problems with different principles of optimality with respect to perturbations of all input data of the problem is investigated. The results are obtained on the basis of research of properties of kernel of stability and subset of those feasible solutions which steadily do not belong to the optimum set. It is given a review of the last results, in relation to the estimations of radius of solutions stability of Boole multicriteria problems with nonlinear criteria. We proposed parametric scheme for the semi online multiprocessor scheduling problem with given total processing time. We also provide the best known worst-case bounds algorithm for the problem. For a problem with the known optimum value of objective function an algorithm with the best known guaranteed estimation is built. In the resulted chart are used technologies of groups and dynamic lower estimations for the optimum value of objective functional, which can be used for the different versions of problems with incomplete information.