Свойства комбинаторных оптимизационных безусловных задач на размещениях с линейной и дробно-линейной целевыми функциями

Abstract

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

The properties of unconditional combinatorial optimization problems on a set of arrangements with linear and linear-fractional objective functions are considered. We prove that in linear problem any extremal is an element of certain set of polyarrangements. Also we substantiate how to construct the set of extremals in a problem with linear-fractional objective function when one of extremals is know.