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

Рассмотрим метод по этапам.

Полная главная задача или полная задача центра

Рассмотрим метод для задачи с двумя почти самостоятельными блоками, т. е. с двумя подсистемами.

Условия (2а) определяют некоторое множество решений подсистемы (2а) и одновременно некоторый многогранник D⁽¹⁾, пусть он ограниченный.

А условие (2б) определяет множество решений соответственно системы неравенств и одновременно некоторое ограничение многогранника D⁽²⁾.

Обозначим — угловые точки многогранника D⁽¹⁾, а через — угловые точки D⁽²⁾.

Каждой угловой точке соответствует опорный план и наоборот, т. е. определяя опорные планы подсистем (2а) и (2б), мы одновременно находим и угловые точки множеств D⁽¹⁾ и D⁽²⁾.

По теореме любое решение (точку) подсистемы (2а) можно представить в виде выпуклой линейной комбинации опорных решений (угловых точек многогранника D⁽¹⁾) подсистемы (2а), т. е. для любого имеет место:

Задача (6), построенная по всем угловым точкам многогранников D⁽¹⁾ и D⁽²⁾, называется полной главной задачей, или полной задачей центра. Задача (6) эквивалентна задаче (1). Решив задачу (6), найдем оптимальное значение и и Z_max . Оптимальное решение исходной задачи (1) найдем по формулам (4) и (5), подставив в них значения и , т. е.

Тогда

Но для того, чтобы построить полную главную задачу, необходимо найти все угловые точки многогранников D⁽¹⁾ и D⁽²⁾ или все опорные решения подсистем (2а) и (2б). Таких угловых точек (опорных планов) как правило много и задача (6) также как и задача (1) имеет большую размерность. Заменяя (1) задачей (6) мы облегчение не получим.

Заслуга Данцига и Вульфа состоит в том , что они показали, что для решения полной задачи центра нет необходимости или не обязательна знать заранее все опорные решения подсистем (все угловые точки), а их можно находить последовательно по мере необходимости.

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

Вводимый вектор – столбец строится по некоторой вершине многогранника D⁽¹⁾ или D⁽²⁾.

Этап1: построение ограниченной главной задачи центра.

Пусть нам удалось по две угловые точки (по 2 опорных плана) многоугольников и : и . Найдем их выпуклую линейную комбинацию.

Подставим (7) и (8) в условие (3), получим следующую ограниченную главную задачу центра:

Решим эту задачу симплекс методом. Найдем ее оптимальное решение (10) и одновременно найдем оптимальное решение двойственной задачи:

m – мерный вектор, так как — m – мерное. Проверим является ли решение (10) оптимальным решением полной главной задачи (6). Согласно основной теории симплекс метода решение ЗЛП является оптимальным, если оценки свободных переменных

Этап 2: Построение подзадач

Найдем среди оценок полной главной задачи наименьшую (относительного оптимального базиса задачи (9)). Оценки соответствующие столбцам переменных l_i, обозначается , а оценки соответственно переменных m_i — .

Запишем полную главную задачу заново

Решение подзадач

Математические модели подзадач записываем в матричной форме. Решение их также будем проводить в матричной форме. Поэтому следует правило умножения матриц. С учетом этого запишем подзадачи в след. виде:

Решив эту ЗЛП, мы найдем некоторую вершину многогранника D⁽¹⁾ (или опорное решение), для которой достигается min функции . Обозначим эту вершину .

Решив эту ПЗ, мы найдем некоторую вершину многогранника D⁽²⁾ (или соответствующее опорное решение), для которых функция достигает минимального значения. Обозначим эту вершину . Тогда

Вершины , могут быть новыми вершинами многогранника, а могут и совпадать с ранее найдеными.

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

Этап 3: Условие оптимальности решения полной главной задачи

Решив подзадачи, найдем оценки и

Это наименьшие оценки в полной главной задаче. Если и , то решая ограниченную главную задачу, мы одновременно нашли оптимальное решение (10) ограниченной главной задачи (т. е. найденные значения ) будут одновременно и оптимальным решением полной главной задачи.

Отсюда следует, что если наименьшие оценки положительны, то должны выполняться следующие условия:

Условия (*) называется условиями оптимальности решения полной главной задачи. Выполнение их означает, что в полной главной задаче все оценки и

Справедлива Теорема

План , где , является оптимальным, если для исходной задачи (1) выполняется условие оптимальности:

Если хотя бы одна из оценок или является отрицательным, т. е. условие оптимальности не выполняется, то переходим к следующему этапу.

Этап 4: Построение новой ограниченной главной задачи.

Пусть среди оценок и есть отрицательная оценка или обе отрицательные. Пусть для определенности оценка Ей соответствует вершина многогранника . Тогда любое решение представим в виде выпуклой линейной комбинации 3-х вершин, т. е.

Подставляем эти значения в условие (3) и получаем следующею новую ограниченную главную задачу:

Находим оптимальное решение задачи: и и новое оптимальное решение двойственной задачи .

Строим новые две подзадачи, решаем их и проверяем, является ли оптимальным решение новой ограниченной главной задачи одновременно и оптимальным решением полной главной задачи, т. е. проверяем выполнение условий оптимальности (*), т. е. мы повторим этапы 2 и 3 до тех пор, пока не будут выполнены условия (*).

Пусть условия (*) выполнены для ограниченной главной задачи, которая построена с учетом вершин и и оптимальное решение ее: . Тогда вычисляем значения . Тогда вектор будет оптимальным решением задачи (1).

Пример.

Дана двухуровневая система с двумя подсистемами. Центр обладает одним глобальным ресурсом в количестве 30 единиц. Каждая подсистема может выпускать по 2 продукта, используя по 2 локальных ресурса. Данные о нормах расхода ресурсов, прибыли на единицу продукции и наличии локальных ресурсов в подсистемах даны в таблицах:

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

Строим математическую модель.

Пусть 1 подсистема выпускает Х₁ единиц продукции 1 вида, Х₂ единиц продукции 2 вида. 2 подсистема – Х₃ единиц продукции 1 вида, Х₄ единиц продукции 2 вида.

Запишем отдельно почти самостоятельные блоки

Запишем эти блоки в матричной форме.

п\з следует выделить глобального ресурса x₁+x₂=10+6=16

Ответ: I подсистема получила от центра 16 единиц глобального ресурса и выпускает 10 единиц продукции 1 вида и 6 единиц продукции 2 вида. II подсистема от центра 14 единиц глобального ресурса и выпускает 16 единиц продукции 1 вида и 8 единиц продукции 2 вида.