ВЕСТНИК ВГУ, Серия физика, математика, 2003, ¹ 1 УДК 519.112.71 РАСПРЕДЕЛИТЕЛЬНАЯ ЗАДАЧА С РАЗРЫВНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ © 2003 А. В. Мухин, Г. Д. Чернышова Воронежский государственный университет Исследуются условия разрешимости и методы решения дискретной распределительной задачи с разрывной целевой функцией. <...> Предлагается алгоритм точного решения, основанный на методе ветвей и границ. <...> ВВЕДЕНИЕ Имеется набор задач и несколько возможных исполнителей. <...> В силу специализации или профессиональных навыков каждый исполнитель в состоянии выполнить лишь некоторые из задач. <...> Производственные возможности исполнителей также ограничены определенным числом решаемых задач. <...> Требуется распределить все задачи среди минимального числа исполнителей. <...> Исходными данными задачи являются булева матрица A, где если i - й исполнитель в состоянии выполнить - ю задачу, иначе aj i,m j ij = 1, 0, ; == , 1, 1,n и вектор (),1, i DD i m== , определяющий максимальное число задач, выполняемых i -м исполнителем. <...> Любая допустимая точка содержит n единиц, так как ограничение (3) требует, чтобы в каждом столбце стояла ровно одна единица. <...> Заметим, что если для некоторого i выполняется неравенство то можно положить дем считать, что ≤≤ ∀ =Da i = 1 iij j ∑ ∀= , оценка снизу имеет вид 1 im 1, Di m= таким образом, чтобы 12 ≥ D . <...> Упорядочим последовательность {}, 1, kl D D i im = {} min( ) L Ll D n = {: ∑ ik k 1 является нижней оценкой целевой функции. <...> УСЛОВИЯ РАЗРЕШИМОСТИ ИСХОДНОЙ ЗАДАЧИ Обозначим через J число элементов в множестве J . <...> Ji В силу замечания и уравнения (2) имеем ** jJ i∈I j Полученное противоречие доказывает несовместность системы. <...> Алгоритм строит строго возрастающую последовательность множеств {}k aij −1 = . <...> . Так как последовательность 2 ограничена сверху, алгоритм является корректным. <...> Решение задачи методом потенциалов предполагает получение начальной базисной точки. <...> Наиболее распространенными алгоритмами являются метод минимального элемента и метод северо-западного угла. <...> В силу <...>