Combinatorial optimization under uncertainty and formal models of expert estimation

Abstract

Previously, the author formalized the concepts of uncertainty, compromise solution, compromise criteria and conditions for a quite general class of combinatorial optimization problems. The functional of the class’ problems contains linear convolution of weights and arbitrary numerical characteristics of a feasible solution. It was shown that the efficiency of the presented algorithms for the uncertainty resolution is largely determined by the efficiency of solving the combinatorial optimization problem in a deterministic formulation. A part of the formulated compromise criteri a and conditions uses expert weights. Previously, the author and his disciples also formulated combinatorial optimization models, optimality criteria, criteria for decisions’ consistency. The models allow to evaluate and justify the degree of stability and reliability of the estimated values of empirical coefficients using a formally ill-conditioned empirical pairwise comparison matrix of arbitrary dimension. The matrix may contain zero elements. The theoretical research and statistical experiments allowed to choose the most efficient of these optimization models. In this article, on the base of earlier results by the author and his disciples, we formalize and substantiate the efficiency of the proposed sequential procedure for expert estimation of weights that determine compromise criteria and conditions. The procedure is an integral part of the algorithm introduced by the author to solve combinatorial optimization problems under uncertainty of the mentioned class. We give unified algorithm for efficient uncertainty resolution that includes original and efficient formal procedure for expert coefficients’ estimation using empirical matrices of pairwise comparisons.Раніше автором для досить загального класу задач комбінаторної оптимізації, функціонал яких містить лінійну згортку ваг і довільних числових характеристик допустимого розв'язку, були формалізовані поняття невизначеності, компромісного розв'язку, компромісних критеріїв та умов. Було показано, що ефективність наведених алгоритмів розв'язання невизначеності в значній мірі визначається ефективністю розв'язання задачі комбінаторної оптимізації в детермінованій постановці. Частина сформульованих компромісних критеріїв і умов використовує експертні вагові коефіцієнти. Раніше також автором і його учнями були сформульовані моделі комбінаторної оптимізації, критерії оптимальності, критерії узгодженості рішень, що дозволяють за формально погано узгодженою емпіричною матрицею парних порівнянь довільної розмірності, яка, можливо, містить нульові елементи, знаходити та обґрунтовувати ступінь стійкості та достовірності знайдених значень емпіричних коефіцієнтів. Проведені теоретичні дослідження та статистичні експерименти дозволили виділити з цих моделей оптимізації найбільш ефективні. У даній статті на основі отриманих раніше автором і його учнями результатів формалізовано і обґрунтовано ефективність запропонованої послідовної процедури знаходження експертних вагових коефіцієнтів, що визначають компромісні критерії та умови, як складової частини алгоритму розв'язання для введеного автором класу задач комбінаторної оптимізації в умовах невизначеності. Наводиться єдиний алгоритм ефективного розв'язання невизначеності, який включає в себе оригінальну ефективну формальну процедуру знаходження експертних коефіцієнтів за емпіричними матрицями парних порівнянь.