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