О свойствах линейной безусловной задачи комбинаторной оптимизации на размещениях с вероятностной неопределенностью

Abstract

Установлено необходимое условие решения линейной безусловной евклидовой задачи комбинаторной оптимизации на размещениях при условии положительности коэффициентов целевой функции. Полученные результаты использованы для установления свойств решения линейной безусловной задачи оптимизации на размещениях для случая, когда в задании допустимого множества имеет место вероятностная неопределенность и минимум определяется в соответствии с линейным порядком, введенным на множестве дискретных случайных величин: сформулировано и обосновано условие, которое может быть положено в основу поиска решениия, и рассмотрены способы построения решения в некоторых частных случаях.

Встановлено необхідну умову розв’язання лінійної безумовної евклідової задачі комбінаторної оптимізації за умови додатності коефіцієнтів цільової функції. Отримані результати використано для встановлення властивостей розв’язку лінійної безумовної задачі оптимізації на розміщеннях для випадку, коли при заданні допустимої множини має місце імовірнісна невизначеність і мінімум визначається згідно з лінійним порядком, введеним на множині дискретних випадкових величин: сформульовано та обґрунтовано умову, що може бути покладена в основу пошуку розв’язку, і розглянуто способи побудови розв’язку в деяких окремих випадках.

The paper establishes the necessary condition for the solution of a linear unconditional problem of combinatorial optimization on arrangements where coefficients of objective function are positive. These results are used to establish the properties of the solution of linear unconditional optimization problem on arrangements for the case where probabilistic uncertainty takes place in the definition of the feasible domain and the minimum is defined according to the linear order introduced on the set of discrete random variables: we formulate and prove the condition that can underlie the search for solution and the ways of constructing the solution in some special cases.