УДК 519.854 Вычислительные тесты по декомпозиционному алгоритму для транспортной задачи © А. <...> А.А. Дородницына РАН, Москва, 119991, Россия 3 МФТИ (государственный университет), Долгопрудный, Московская обл., 141700, Россия Представлены вычислительные тесты по итеративному методу на основе последовательного пересчета коэффициентов функционала для транспортной задачи. <...> Оптимальное решение получено за три итерации, не использует случая вырождения, совпадает со стандартной программой по методу потенциалов. <...> Алгоритм строит последовательность решений промежуточных одномерных задач, которые не являются допустимыми для исходной задачи. <...> Имеет место монотонный рост по функционалу на псевдорешениях. <...> Получены формулы решений промежуточных двумерных задач с зацепляющимися переменными и последовательно пересчитаны коэффициенты функционалов. <...> При отсутствии допустимого решения сформулирована задача о максимальном потоке для транспортных ограничений с запретами. <...> По некоторому правилу сформированы корреспондирующие пары индексов. <...> Методы декомпозиции эффективны во многих оптимизационных задачах со многими переменными и ограничениями [1–16]. <...> В работе [17] представлен итеративный метод решения классической транспортной задачи, в котором последовательно решены задачи с двумя ограничениями из разных групп и с одной связывающей переменной. <...> В алгоритме последовательно пересчитываются коэффициенты целевой функции, затем формулируются одномерные задачи, число которых равно числу ограничений исходной задачи. <...> Полученные решения позволяют найти исходный оптимум или определить систему ограничений на переменные. <...> Допустимые решения этой системы дают оптимальное решение исходной задачи. <...> Если допустимых решений нет (вырождение), то решают задачи о максимальном потоке: находят множество так называемых взаимно удовлетворенных пар, формируют множество обобщенных производителей и потребителей и путем суммирования <...>