Трехиндексные задачи линейного программирования с вложенной структурой

Рассматриваются вопросы решения многоиндексных задач линейного программирования транспортного типа. В качестве метода решения предлагается подход, основанный на исследовании сводимости многоиндексных транспортных задач к потоковым алгоритмам. Предлагаются достаточные условия сводимости многоиндексных задач, связанные с исследованием вложенности системы ограничений задачи. Показывается, что данные условия являются необходимыми и достаточными для сводимости трехиндексных задач, иначе неверной является известная гипотеза о неравенстве классов P и NP.

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