УДК 519.68 ВЕРОЯТНОСТНЫЙ ПОДХОД К РЕШЕНИЮ ТРЕХИНДЕКСНОЙ АКСИАЛЬНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ. <...> ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ А. Г. Трегубов, С. Н. Медведев Воронежский государственный университет Поступила в редакцию 10.10.2015 г. Аннотация. <...> В статье представлена формулировка трёхиндексной аксиальной задачи о назначениях, предложен адаптивный алгоритм решения, основанные на переходе к вероятностной постановке задачи и проведено сравнение данного алгоритма с базовым «жадным». <...> Одной из самых известных задач дискретной оптимизации является задача о назначениях (ЗОН), которая в своей классической формулировке сводится к задаче о распределении претендентов по рабочим местам с целью минимизации затрат. <...> На пути использования таких оценок (за счёт углубления памяти алгоритма, оценивания средних значений функций и т. п.) появляются различные модификации «жадных» алгоритмов. <...> Для трёхиндексной аксиальной задачи известен базовый «жадный» алгоритм, основанный на поиске минимального элемента в плоских матрицах при фиксировании одного из индексов [1]. <...> А именно, при каждом фикВЕСТНИК ВГУ, СЕРИЯ: СИСТЕМНЫЙ АНАЛИЗ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, 2015, № 4 31 1, (3) А. Г. Трегубов, С. Н. Медведев сированном 1,= ищется локальный минимум kn m,ijn{ }= ij x v k i ccv kk и фиксируется соответствующее назначение 1. <...> = На основе данного базового метода предлагается построение адаптивного алгоритма решения аксиальной трехиндексной ЗОН (1)–(5). <...> Для этого осуществляется переход к вероятностной постановке задачи на основе рандомизации переменных [2]. <...> Задача минимизации целевой функции LX → заменяется задачей минимизации её математического ожидания ( ) minX∈Ω M LX → ( ( )) minXX∈Ω { }: X – множество случайных величин X с реализациями из множества ,Ω { }:XX . <...> Здесь где {} XX X личин, i X – случайная величина с рядом распреk ij деления: Возможные значения Вероятность p где , , 1, . <...> Решение неравенства – условия локального улучшения (УЛУ) ( ij 1, = 1, . <...> Формулу движения выберем следуюN <...>