Многоиндексные транспортные задачи с декомпозиционной структурой

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

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