ДЕКОМПОЗИЦИИ МЕТОД, блочный метод

— метод решения задачи линейного программирования, сводящий ее к решению последовательности задач меньшей размерности.

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

при ограничениях

где — вектор-строка,

- -мерный вектор ограничения задачи, вектор условий — знак транспонирования, вектор переменных. Пусть множество планов X системы (3—4) ограничено и все ее опорные планы. В случае неограниченности множества (3—4) принципиальных трудностей не возникает. Любой план X из (3—4) можно представить в виде линейной комбинации опорных планов

Подставляя ур-ние (5) в ур-ния (1—2), представим задачу (1—4) в новой форме

при ограничениях (6—7) и

где

Задача (6—9) содержит ограничение вместо в исходной задаче, зато число переменных N во много раз больше, чем п. Однако для решения задачи (6—9) Д. м. не нужно знать все векторы На каждом шаге достаточно иметь только векторов которые входят в текущий базис задачи. Проверка базиса на оптимальность и определение вектора, подлежащего включению в базис, производится путем решения вспомагательной задачи линейного программирования с условиями (3—4). Если матрица ограничений (3) имеет блочно-диагональную форму

то вспомогательная задача распадается на г задач меньшего объема, что упрощает процедуру и сокращает время ее решения. Такой особенностью обладают, напр., матрицы транспортной задачи и ее обобщений, распределительной задачи и т. д.

Лит. см. к ст. Программирование линейное.

В. А. Трубин.