Многоиндексные транспортные задачи с $1$-вложенной структурой

Рассматриваются вопросы решения многоиндексных транспортных задач линейного и целочисленного линейного программирования. В качестве метода решения предлагается подход, основанный на исследовании сводимости многоиндексных транспортных задач к задаче поиска потока минимальной стоимости в древовидной сети. Доказывается, что в рамках исследуемой схемы сведе́ния условие $1$-вложенности многоиндексных задач является необходимым и достаточным условием сводимости к задаче поиска потока минимальной стоимости в древовидной сети. Предлагается алгоритм решения $1$-вложенных многоиндексных задач, требующий квадратичных от числа переменных исходной задачи вычислительных операций.

Статья представлена к публикации членом редколлегии: А. А. Лазарев