МЕТОД ДЕКОМПОЗИЦИИ

ДЕКОМПОЗИЦИИ МЕТОД, блочный метод (decomposition method) – метод решения задачи программирования линейного, сводящий ее к последовательности задач меньшей размерности. Суть Д.м. можно объяснить на примере решения задачи программирования линейного с двумя системами ограничений, заданных в виде равенств. Взяв одну из этих систем, определяют опорные планы, через которые выражается решение задачи линейного программирования в виде выпуклой линейной комбинации.

Затем рассматривают коэф., входящие в линейную комбинацию в качестве новых переменных, в результате чего исходная задача линейного программирования сводится к новой задаче с меньшим числом ограничений. Эта задача решается итерационным методом; на каждом шаге итерации нужно знать лишь текущий базис задачи. Если матрица ограничений исходной задачи линейного программирования имеет блочно-диагональную структуру, решение задачи по Д.м. значительно упрощается. Это используется при решении трапсп. задачи и ее обобщений, распределительной задачи и т.д. Д.м. разработали в 1960 г. американские ученые Дж.Данциг и Ф.Вулф.