ВЕСТНИК ВГУ, Серия физика, математика, 2001, ¹ 2 УДК 519.112.71 ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ОДНОЙ ЗАДАЧИ ТРАНСПОРТНОГО ТИПА, ПОЗВОЛЯЮЩИЕ ИСПОЛЬЗОВАТЬ РАЗЛИЧНЫЕ МЕТОДЫ ЕЕ РЕШЕНИЯ © 2001 г. И. Л. Каширина, Г. Д. Чернышова Воронежский государственный университет Рассматривается задача выбора минимального количества объектов, выполняющих заданный набор операций, в предположении, что каждый объект должен выполнять не более фиксированного числа операций, а каждая операция должна выполняться ровно одним объектом. <...> Исходные данные задачи можно представить в виде булевой матрицы A, где == Задачи такого типа имеют широкое пракai imj ij = 1,, 1,n. тическое применение и возникают, например, при проектировании программно-аппаратных многопозиционных радионавигационных систем для определения местоположения объектов и обмена данными между ними. <...> К такой постановке сводится задача выбора минимального количества объектов-ретрансляторов с ограничением на размер кластера [1]. <...> Рассмотрим некоторые алгоритмы точного и приближенного решения этой задачи, основанные на различных способах ее математической записи. <...> 1 0, 1, объектов, которые могут выполнять i-ю функцию: может выполнять j-й объект, Ji Здесь Ij Ij={i :aij >0}, Ji sgn(∑ )yij ∈ j iI = 1, если yj - т.е. й объект iI ∑ ∈ j 0, выполняет хотя бы одну операцию если ∑yij = 0. ∈ j iI Полученная задача имеет нелинейную целевую функцию и две группы ограничений транспортного типа. <...> Число единиц в решении равно m (в силу ограничений (2) в каждой из m строк стоит ровно одна единица). <...> Имеет место оценка снизу для оптимального значения целевой функции: * m ZD ∉ , то оценку можно уточнить: * f m 1D (Здесь [·] знак целой части). <...> Если , ij > 0, = {j : aij >0}, D максимально допустимое число операций, выполняемых одним объектом: 1<D<m, (4) множество операций, которые множество ,1, (3) yi m 1,1, (2) φ Эквивалентные преобразования одной задачи транспортного типа. <...> Если m= nD <...>