10.4 МЕТОД ДЕКОМПОЗИЦИИ НА ОСНОВЕ агрегирования в ЗАДАЧАХ БОЛЬШОЙ РАЗМЕРНОСТИ.
Одной из задач оптимального планирования с большим числом переменных и ограничений является так называемая модель отраслевого планирования. Годовой план области формируется на основе потребностей народного хозяйства в целом в ее продукции. При этом одна часть номенклатуры конечного выпуска фиксируется (так называемый 'госзаказ'), а другая - находится в распоряжении отрасли или концерна. В качестве критерия выбирается максимизация выпуска свободной номенклатуры в заданном ассортиментном соотношении или максимизация прибыли (общая модель). Данная модель приводит к задаче ЛП с блочно-диагональной структурой части ограничений. Связывающие ограничения и критерий оптимальности имеют специфику, обусловленную конкретной моделью планирования. Эта специфика приводит к идее агрегирования переменных при построении декомпозиционного метода решения блочной задачи.
Постановка и математическая модель задачи
Рассмотрим задачу отраслевого планирования. Имеется отрасль (или большой концерн), которая характеризуется множеством заводов
, множеством номеров изделий конечной продукции
, множеством индексов номенклатуры изделий, производящихся на заводах отрасли
, множеством номеров групп оборудования Kj, имеющихся на заводе j, множеством номеров комплектующих изделий, производящихся на заводе
.
Предположим, что технологическая цепочка изготовления данного изделия на данном заводе фиксирована. Тогда производственные мощности каждого завода описываются (в рамках модели использования невзаимозаменяемых групп оборудования) следующими ограничениями:
(10.4.1)
где xij - годовой оборот выпуска изделий типа i на заводе j ;
- годовой фонд времени работы оборудования группы k на заводе j ;
- затраты времени работы оборудования группы k на заводе j на производство единицы изделия типа i.
Как следует из (10.4.1) величины xij определены на каждом заводе j только для
. В дальнейшем удобно определить их для всех
, полагая для этого xij=0 для
. Связь между выпуском комплектующих изделий и выпуском конечной продукции описывается соотношением
, (10.4.2)
где ym - годовой выпуск продукции вида m; Wij - запас изделий вида i на заводе j на начало планового периода; eim - число изделий вида i, входящих в единицу конечной продукции (вида m);
-норматив запаса продукции m, переходящего на следующий год (в относительных единицах).
Предположим сначала, что множество номеров конечной продукции
разбито на два непересекающихся подмножества
, где 
Продукция из подмножества
является важнейшей для отрасли с точки зрения народнохозяйственных потребностей, она входит в госзаказ. Объемы выпуска продукции из подмножества либо фиксируются, либо задаются ограничениями снизу,то есть
. (10.4.3)
Эта часть номенклатуры конечного выпуска называется обязательной. Предполагается, что существует вектор {
} такой, что область допустимых планов не пустая. Продукция из множества
называется свободной, и решение об объемах ее выпуска принимает администрация отрасли (или концерна).
Пусть администрация области определяет вектор свободной номенклатуры
{
} (10.4.4)
Вектор {
} является недопустимым планом, то есть не существует величин {xij}, удовлетворяющих условиям (10.4.1) и (10.4.2). В этом случае возникает проблема сокращения компонент вектора (10.4.4).
Вектор {
} является допустимым планом. В этом случае существует бесконечное число способов размещения заказов на изготовление комплектующих изделий по заводам и, кроме того, определенная доля производственных мощностей отрасли может быть не загружена.
Таким образом, в обоих случаях администрация (плановый орган) отрасли сталкивается с необходимостью пересмотра вектора (10.4.4), который можно интерпретировать как желательную структуру выпуска свободной номенклатуры конечной продукции. Тогда конечный план выпуска свободной номенклатуры определяется как:
.
Компоненты вектора
в (10.4.4) называются пропорциями или ассортиментными соотношениями, а величина
- числом ассортиментных наборов (числом комплектов).
Далее предположим, что компоненты вектора обязательной номенклатуры фиксированы. Запишем (10.4.2) в соответствии с разбиением вектора конечной продукции
. (10.4.5)
Обозначим суммарный запас изделия в отрасли на начало нового планового периода (года) через
, а суммарный объем изделия i, необходимого для выпуска конечной продукции обязательной номенклатуры
и, наконец, і-тую компоненту ассортиментного соотношения выпуска комплектующих изделий обозначим через
.
С использованием этих обозначений (10.4.5) запишется в виде
.
Введем также обозначения
.
Тогда оптимизационная задача запишется окончательно в виде:
максимизировать
(10.4.6)
при ограничениях
(10.4.7)
, если
если
(10.4.8)
, (10.4.9)
. (10.4.10)
Задача (10.4.6)-(10.4.10) является задачей ЛП и для ее решения можно использовать стандартные методы. Однако на практике это связано с трудностями из-за огромной размерности реальных задач отраслевого планирования.
Анализ ограничений этой задачи показывает, что она имеет блочную структуру: ограничения (10.4.7), (10.4.8) относятся к отдельным заводам j и являются блочными, а ограничения (10.4.9) сугубо отраслевые, или связывающие, относятся к всем заводам отрасли. Кроме того, данная блочная задача обладает дополнительно специфическими особенностями : оптимизируемая переменная
не входит в блочные ограничения, связывающие ограничения имеют специальный вид, а в критерий входит лишь одна переменная
. Эти особенности и учитываются при построении декомпозиционного алгоритма.
Метод разложения на основе агрегирования
Наличие в равенствах (10.4.9) сумм
приводит к идее ввести новые переменные - полные выпуски по всем заводам отрасли (концерна):
, (10.4.11)
которые естественно назвать агрегированными переменными. Вводятся также удельные выпуски изделия типа i на заводе j:
,
которые еще называют весами (или коэффициентами) агрегирования.
Очевидно, выполняются условия
. (10.4.12)
Пусть заданы веса агрегирования, удовлетворяющие (10.4.12). Тогда, подставляя в (10.4.6)-(10.4.8) переменные
и вводя обозначения
, приходим к задаче в агрегированных переменных:
максимизировать
(10.4.13)
при ограничениях
(10.4.14)
; (10.4.15)
(10.4.16)
Задачу (10.4.13)-(10.4.16) назовем задачей в агрегированных переменных или макрозадачей.
Запишем двойственную задачу к задаче (10.4.6)-(10.4.8):
минимизировать
(10.4.17)
при условиях
; (10.4.18)
; (10.4.19)
. (10.4.20)
Двойственная задача для задачи в агрегированных переменных записывается так:
минимизировать
(10.4.21)
при ограничениях
; (10.4.22)
; (10.4.23)
. (10.4.24)
Пусть
- единственные оптимальные решения задачи (10.4.21)-(10.4.24). Для каждого фиксированного индекса формируются блочные ('заводские') задачи:
максимизировать
(10.4.25)
при ограничениях
, (10.4.26)
. (10.4.27)
Двойственные задачи для блочных задач (10.4.25)-(10.4.27) при каждом
записываются в виде:
минимизировать
(10.4.28)
при ограничениях
. (10.4.29)
Итеративный процесс решения строется следующим образом [52]. При некоторых фиксированных весовых коэффициентах
, удовлетворяющих условиям (10.4.12), решается задача в агрегированных переменных (10.4.13)-(10.4.16). Как будет показано в дальнейшем, эта задача при некоторых предположениях решается аналитически. С помощью двойственных оценок
формируют функционалы блочных задач (10.4.25)-(10.4.27). Пусть
- оптимальные решения этих задач. Введем переменные
(10.4.30)
где
- оптимальные решения задачи в агрегированных переменных. Величины
называются дезагрегированными решениями. Новые весовые коэффициенты агрегирования определяются в виде функции
от переменных
согласно соотношению
(10.4.31)
где
.
Заметим, что для коэффициентов
, описывающихся (10.4.31), выполняются условия (10.4.12).
Опишем общую схему декомпозиционного алгоритма на основе агрегирования (7,25). Если рассматривать задачи в агрегированных переменных (10.4.13)-(10.4.16) с коэффициентами, удовлетворяющими (10.4.31), то оптимальное значение функционала является функцией от параметров
. Эту функцию обозначим через
. Возникает задача максимизации функции
на единичном гиперкубе
. Пусть максимум достигается при некоторых
. Тогда коэффициенты
для следующей итерации процесса определяются по формуле (10.4.31) при
. Алгоритм формирует последовательность дезагрегированных решений
, которые вместе с
являются допустимыми к исходной задаче (10.4.6)-(10.4.10). Далее проверяется критерий оптимальности решения
для задачи (10.4.6)-(10.4.10) (условие окончания итеративного процесса).Далее доказывается строгая монотонность значений функционала
, соответствующих дезагрегированным решениям
и
,и таким образом решается вопрос о сходимости последовательности из допустимых решений
и
к оптимальному решению исходной задачи (10.4.6)-(10.4.10).
Далее предположим, что указанный итеративный процесс начинается с весовых коэффициентов, дающих строго положительное значение
для задачи в агрегированных переменных. А поскольку это число на каждой итерации возрастает, то для всех макрозадач выполняется неравенство
> 0. Предположим также, что выпуск каждого изделия ненулевой, то есть
, что заведомо выполняется на практике. Сформулируем критерий оптимальности дезагрегированного решения
.
Пусть при некоторых коэффициентах
, удовлетворяющих (10.4.12), получено оптимальное решение
задачи в агрегированных переменных (10.4.13)-(10.4.16), а
- соответствующее дезагрегированное решение. Пусть
- единственное решение двойственной задачи (10.4.21)-(10.4.24). Вводятся обозначения
. (10.4.32)
Величины
и
представляют собой значения функционалов блочных задач (10.4.25)-(10.4.27) на оптимальном и дезагрегированном решениях соответственно. Положим также
.
Имеет место следующая теорема (52).
Теорема 10.1. Справедливы следующие утверждения:
а)
;
б)
тогда и только тогда, когда
для всех j.
Доказательство. Дезагрегированное решение является допустимым к блочным задачам. Оно удовлетворяет условиям (10.4.17), в силу (10.4.13) и (10.4.16). Это решение удовлетворяет также (10.4.26) согласно следующей цепочке неравенств:
(10.4.33)
Поскольку
допустимые решения исходных ('заводских') задач (10.4.25)-(10.4.27), а
- их оптимальные решения, то утверждение а) теоремы 10.1 - доказано. Далее в силу определений
и
и утверждения а) теоремы, устанавливаем справедливость утверждения б) теоремы. Следовательно, теорема доказана.
Следующая теорема устанавливает условие оптимальности дезагрегированного решения (52).
Теорема 10.2. Пусть для оптимальных решений
,
и
прямой и двойственной макрозадач и оптимальных решений блочных задач {
} выполняются равенства
. (10.4.34)
Тогда дезагрегированное решение
, где
,
, составляет оптимальный план исходной задачи (10.4.6)-(10.4.10).
Доказательство. Поскольку
> 0, то в силу теоремы 2.7 двойственности условие (10.4.23) выполняется как строгое равенство, то есть
. Умножая равенства (10.4.15), выписанные для оптимального решения, на
и суммируя по i, получаем
.
Из последних двух соотношений имеем

Рассмотрим дезагрегированое решение
. Легко убедиться , что это решение будет допустимо к исходной задаче (10.4.6)-(10.4.10), а значение целевого функционала на этом решении есть
.Имеем следующую цепочку равенств:
.
Сравнивая последнее равенство с (10.4.34), получаем
. (10.4.35)

Далее рассмотрим оптимальные решения
,
двойственных блочных задач (10.4.28)-(10.4.30). Можно легко проверить, что набор {
}, {
},
,
,
является допустимым планом к двойственной задаче (10.4.27)-(10.4.30). Функционал
на этом решении принимает значение
. (10.4.36)
По теореме 2.2 двойственности (см.гл.2) для блочных задач имеют место равенства
,
. (10.4.37)
Подставляя (10.4.37) в (10.4.36), получаем
(10.4.38)
Итак, имеем допустимые решения пары двойственных задач (10.4.6)-(10.4.10) и (10.4.17)-(10.4.20), значения целевых функций которых выражаются соответственно через (10.4.35) и (10.4.38).
Равенство
, (10.4.39)
согласно основной теореме двойственности 2.2, обеспечивает оптимальность решений
для исходной задачи (10.4.6)-(10.4.10). Но из (10.4.35) и (10.4.38) следует, что равенство (10.4.39) эквивалентно
, или, в силу леммы,
. Следовательно, теорема 10.2 доказана. Таким образом, выполнение соотношения (10.4.33) является условием окончания алгоритма.
Аналогично доказывается и следующая теорема [52].
Теорема 10.3. Пусть исходная задача (10.4.6)-(10.4.10) имеет решения и при некоторых
получен дезагрегированный план
, не оптимальный для задачи (10.4.6)-(10.4.10). Тогда существуют такие j, для которых
и потому имеет место неравенство
. (10.4.40)
Задача в агрегированных переменных
Ядром декомпозиционного метода является многократное решение задачи в агрегированных переменных (10.4.13)-(10.4.16). На каждом шаге итеративного процесса при максимизации функции
на единичном кубе
макрозадача решается для некоторых значений параметров
.
В связи с этим важным является выяснение свойств решения задачи в агрегированных переменных (10.4.13).
Выразим величины Xі через
согласно (10.4.15)
. (10.4.41)
Подставляя (10.4.41) в (10.4.14), получаем
.
Из последних неравенств получаем выражение для оптимального значения переменной
. (10.4.42)
Оптимальные величины xi
определяются через
из (10.4.41).
Рассмотрим двойственную задачу (10.4.21)-(10.4.24). В силу
на основе теоремы 2.7 из главы 2 соотношения (10.4.22) выполняются на оптимальном решении как равенства, то есть
. (10.4.43)
Подставляя (10.4.43) в (10.4.23), приходим к следующей задаче:
минимизировать
. (10.4.44)
при ограничениях
. (10.4.45)
Пусть минимум в (10.4.42) достигается на единственной паре индексов (j*,k*). Тогда имеем
. (10.4.46)
В данном случае задача (10.4.44)-(10.4.45) имеет единственное решение

(10.4.47)
если
.
Величины
согласно (10.4.43), (10.4.47) равняются
;
(10.4.48)
и определяются однозначно. Такой случай называют простым. В более сложном случае минимум в (10.4.42) достигается на некотором множестве пар индексов (j,k), которое обозначим через R. Тогда (10.4.42) можно записать в виде

Для величин
имеем задачу:
минимизировать
(10.4.49)
при ограничениях
. (10.4.50)
Задача (10.4.49), (10.4.50) имеет не единственное решение, и возникает дополнительный вопрос об определении величин, которые формируют функционалы блочных задач. Этот случай будем называть вырожденным. В обоих случаях нахождение оптимального решения в агрегированных переменных сводится к определению минимального элемента некоторой матрицы большой размерности. Таким образом, все трудности, связанные с большой размерностью, сводятся к задаче перебора.
Далее исследуем вырожденный случай в задаче (10.4.49), (10.4.50). Множество ее решений принадлежит многограннику с вершинами
где
. (10.4.51)
Перенумеруем последовательно все элементы множества R. Полученное множество номеров обозначим через
.
Подставляя (10.4.51) в (10.4.48), получим следующее выражение:
. (10.4.52)
Здесь подразумевается, что существует взаимно однозначное соответствие между элементами множеств R и
. Таким образом, все решения двойственной макрозадачи можно представить в виде
(10.4.53)
где величины
удовлетворяют условиям
.
Обозначим через
при каждом
множество допустимых решений блочных задач, то есть xij, удовлетворяющих ограничениям (10.4.26), (10.4.27) при фиксированных
.
Рассмотрим максиминную задачу
. (10.4.54)
Если
,
- ограниченные множества, то задача (10.4.54) имеет седловую точку, которую обозначим
. При этом для каждого j величины
,
являются оптимальными решениями блочных задач с функционалами, содержащими
.
Обозначим через
значение величины h для седловой точки {
}. Тогда критерий оптимальности дезагрегированного решения в случае вырожденности формулируется так (52).
Теорема 10.4. Достаточным условием оптимальности дезагрегированного решения
для исходной задачи (10.4.6)-(10.4.10) в случае вырожденности является выполнение равенства
.
Как видим, критерий оптимальности в случае вырожденности совпадает с критерием для невырожденности.
Локальная монотонность и сходимость метода.
Доказательство сходимости алгоритма декомпозиционного метода агрегирования базируется на доказательстве роста функционала от дезагрегированных решений на каждом шаге итеративного процесса. Данный факт выводится на основании исследования дифференциальных свойств функции
. Рассмотрим невырожденный случай. Справедлива следующая теорема.
Теорема 10.5. Пусть при некоторых коэффициентах {
} получено оптимальное решение задачи в агрегированных переменных (10.4.13)
и двойственная задача имеет единственное решение{
}. Пусть дезагрегированное решение
, где
не является оптимальным решением для исходной задачи (10.4.6)-(10.4.10). Тогда существует допустимое решение для задачи (10.4.6)-(10.4.10) со строго большим значением функционала, чем
.
Доказательство этой теоремы приводится в (52).
Исследуем теперь вопрос о сходимости итеративного метода. Пусть некоторому фиксированному шагу с номером n рассматриваемого процесса соответствуют весовые коэффициенты агрегирования
. Пусть
- оптимальное решение для задачи в агрегированных переменных (10.4.13)-(10.4.16) для весовых коэффициентов
, а
, где
-соответствующее дезагрегированное решение. Наконец, величины
- единственное решение двойственной задачи (10.4.21)-(10.4.24) в простом случае. Положим для шага n (итерации) алгоритма

Пусть по определению
. Справедливо следующее утверждение о сходимости метода.
Теорема 10.6. Пусть для весовых коэффициентов
, удовлетворяющих условиям (10.4.12), оптимальные значения
задач в агрегированных переменных (10.4.13)-(10.4.16) ограничены сверху, оптимальные значения
ограничены снизу положительной константой, а множества оптимальных решений двойственных макрозадач (10.4.21)-(10.4.24) ограничены в совокупности. Тогда последовательность дезагрегированных решений
является максимизирующей и из нее можно выделить подпоследовательность, сходящуюся к оптимальному решению исходной задачи (10.4.6)-(10.4.10).
Доказательство теоремы следует из того, что монотонно возрастающая в силу теоремы 10.5 и ограниченная по предположению последовательность имеет предел.
Описание алгоритма агрегирования
Используя вышеизложенные теоретические положения,опишем алгоритм декомпозиции на основе агрегирования для задачи (10.4.6)-(10.4.10).
Предварительный этап.
Зададимся начальными весовыми коэффициентами агрегирования
.
Запишем задачу в агрегированных переменных (10.4.13)-(10.4.16) и найдем ее решение
(0),
, а также соответствующее дезагрегированное решение {
(0)} и двойственные оценки величин
,
.
Для заданного набора оценок {
} сформируем блочные задачи вида (10.4.25)-(10.4.27), находим их решения
, а также величину критерия
.
Если
, то конец, найденное дезагрегированное решение {
} - оптимально, иначе - переход к первой итерации.
k-ая итерация. Пусть уже проведена (k-1)-я итерация и
.
Записываем новые коэффициенты агрегирования
в соответствии с (10.4.31).
Будем искать максимум функции
в единичном гиперкубе (то есть при
). Если принять
,
то задача сводится к одномерному поиску максимума
, которую решаем методом Фибоначчи (см.гл.6).
Находим оптимальные значения
и соответствующие им новые значения весовых коэффициентов {
(k)}, агрегированных {xi(k)}, и дезагрегированных переменных{
}.
Строим матрицу вида
, находим ее минимальный элемент (j*,k*) и определяем оптимальные двойственные оценки в соответствии с (10.4.48).
Решаем блочные задачи (10.4.25)-(10.4.27), находим их оптимальные решения {
}, а также
(k).
Проверяем условие оптимальности
. Если оно выполняется, то конец, текуще дезагрегированное решение - оптимально, иначе переходим к (k+1)-й итерации.
Пример 10.4.
Максимизировать 
при условиях


Выберем такие начальные значения коэффициентов
=0,5;
=0,5;
=0,8;
=0,2. Оптимальное решение макрозадачи для этих коэффициентов
=1,476;
=0,476;
=0,476. Компоненты матрицы левой части (10.4.42) следующие : 1,476; 1,555; 1,558; 1,909.
Дезагрегированное решение:
x11(0)=0,238; x21(0)=0,238; x12(0)=0,321; x22(0)=0,095.
Блочные задачи имеют решения
(0)=0 ;
(0)=0,5 ;
(0)=0 ;
(0)=0,333. Находим величину
(0)=
(0)-
(0)=0,126.
Первая итерация. В результате ее выполнения получаем
.
Весовые коэффициенты равны:
.
Компоненты матрицы
вида (10.4.42) следующие: 1,588 ; 1,625 ; 1,526 ; 1,588.
Дезагрегированное решение: 
Оптимальные решения блочных задач:

Вторая итерация. В результате ее выполнения получаем точное оптимальное решение. Имеем
.
Весовые коэффициенты равны :
.
Дезагрегированное решение:
, оно совпадает с оптимальным решением данной задачи. Матрица
вида (10.4.42) имеет вид: [1,583 ; 1,583 ; 1,583 ; 1,583], то есть минимум достигается сразу на всех четырех элементах. Тем не менее оптимальные двойственные оценки
вычисляются по невырожденной двойственной макрозадаче. Наконец:
,
.
В общем случае при решении задач произвольной размерности блочные задачи решаются симплекс-методом, а для нахождения седловой точки целесообразно использовать методы, изложенные в гл.6, например, обобщенный градиентный метод.
Декомпозиция на основе агрегировання
для общей модели отраслевого планирования.
Выше была рассмотрена модель отраслевого планирования с критерием максимума выпуска свободной части конечной продукции. Соответствующая целевая функция зависит от переменной
.
Рассмотрим теперь общий случай задачи отраслевого планирования. Пусть
- стоимость единицы продукции xij. Пусть, кроме того, при выпуске изделий і-го вида на заводе j используются некоторые виды общих ресурсов l,
, которые находятся в распоряжении отрасли (концерна), и их общие объемы ограничены. Обозначим через bijl расход ресурса l - го вида на выпуск продукции і-го вида (xi) на заводе j, а Pl - реальный объем этого ресурса в отрасли, Pjk - объем собственного к-го ресурса на заводе j, bijk - норма расхода к-го ресурса на производство продукции i-го вида.
Тогда рассмотрим задачу максимизации прибыли от реализации продукции при ограничениях на общие ресурсы. Соответствующая модель задачи имеет вид:
максимизировать
(10.4.55)
при ограничениях
(10.4.56)
, при
, xij=0 при
(10.4.57)
,
. (10.4.58)
Здесь соотношения (10.4.56), (10.4.57) - блочные, где номер j, как и ранее, соответствует фиксированному блоку, а (10.4.58) - связывающие ограничения.
Для задачи (10.4.55)-(10.4.58) запишем двойственную задачу:
минимизировать
(10.4.59)
при ограничениях
(10.4.60)
;
;
;
;
, (10.4.61)
причем, переменные
соответствуют (10.4.56), а
l - ограничениям (10.4.58).
Как и ранее, введем агрегированные переменные
;
, и весовые коэффициенты агрегирования
, Фиксируя коэффициенты
и подставляя
в (10.4.55) - (10.4.58) получим задачу в агрегированных переменных:
максимизировать
(10.4.61)
при ограничениях

;
(10.4.62)

(10.4.63)
;
. (10.4.64)
Здесь введены обозначения
(10.4.65)
Двойственная задача для задачи (10.4.61)-(10.4.64) имеет вид:
минимизировать
(10.4.66)
при ограничениях
;
(10.4.67)
;
;
;
;
, (10.4.68)
где переменные
соответствуют (10.4.62), а переменные
- (10.4.63).
Пусть {
} - оптимальные двойственные оценки (переменные) задачи (10.4.66)-(10.4.68). Сформулируем задачи для отдельных блоков:
\ минимизировать
(10.4.69)
при ограничениях
;
; (10.4.70)
при
, xij=0 при
. (10.4.71)
Двойственные задачи для блочных задач имеют вид:
минимизировать
(10.4.72)
при ограничениях
, (10.4.73)
;
(10.4.74)
где двойственные переменные
соответствуют (10.4.70).
Алгоритм решения задачи конструируется по общей схеме алгоритма декомпозиции на основе агрегирования. При этом сводим задачу (10.4.55)-(10.4.58) к задачам меньших размерностей. Действительно, исходная задача имеет
переменных. Задача в агрегированных переменных (10.4.61) содержит I переменных, а блочной задачи имеют каждая по Ij переменных, наконец, задача максимизации функции
на единичном гиперкубе включает J переменных.
На каждом шаге итеративного процесса неоднократно решается задача в агрегированных переменных (10.4.61), которая имеет небольшое количество переменных Xi,
и большое число ограничений.
Сформулируем признак оптимальности промежуточного дезагрегированного решения. Пусть при некоторых весовых коэффициентах получено оптимальное решение
макрозадачи (10.4.61)-(10.4.61), а
- соответствующее дезагрегированное решение. Пусть
- единственное оптимальное решение задачи (10.4.66)-(10.4.68), а
- оптимальные решения блочных задач (10.4.69)-(10.4.71).
Теорема 10.7. Достаточным условием оптимальности решения {
} задачи (10.4.55)-(10.4.58) является выполнение равенства
. (10.4.75)
Если же задача (10.4.55)-(10.4.58) - разрешима и {
} - неоптимальное решение, то в соотношении (10.4.75) знак равенства заменяется знаком '>'.
Доказательство. Дезагрегированное решение
является допустимым к исходной задаче (10.4.55)-(10.4.58). Это проверяется непосредственной подстановкой
в (10.4.56) и (10.4.58) с учетом (10.4.62), (10.4.63) и обозначений (10.4.11). Соответствующее значение целевой функции
исходной задачи равно
, (10.4.76)
Набор {
,
},где
,
,
,
- оптимальные решения задач, двойственных к блочным (10.4.72), является допустимым решением задачи, двойственной для задачи (10.4.55)-(10.4.58). Это следует из соотношений (10.4.73), (10.4.74), (10.4.60).
Значение функционала
для указанного решения есть
. (10.4.76)
Согласно теореме 2.5 двойственности равенство
=f 0 обеспечивает оптимальность допустимого решения {
} для задачи (10.4.55)-(10.4.58). Если же решение {
} неоптимально для задачи (10.4.55)-(10.4.58) при условии ее разрешимости, то
>f 0 .
Поскольку набор
- оптимальные решения задач, двойственных к блочным (10.4.72), то по теореме 2.5, для оптимальных решений блочных задач и двойственных к ним будем иметь
для всех
.
Подставляя это выражение в (10.4.76), с учетом
, получим условия оптимальности (10.4.75).
Таким образом, теорема 10.7 доказана.
Подытоживая, получим критерий оптимальности в виде
(10.4.77)
Опишем теперь алгоритм декомпозиции на основе агрегирования для задачи ЛП. Пусть общая задача ЛП с блочно-диагональной структурой части ограничений задана в виде (10.4.55)-(10.4.58).
Предварительный этап.
Задаемся начальными коэффициентами агрегирования
(
), решаем задачу в агрегированных переменных (10.4.61)-(10.4.64) и находим
,
,
.
Решаем двойственную задачу (10.4.66)-(10.4.68) и находим оптимальные двойственные переменные {
},{
}.
Решаем блочные задачи (10.4.69)-(10.4.71) и находим оптимальные решения {
}.
Проверяем условие (10.4.77). Если оно строго равно нулю, то конец,
- оптимальное решение, в противном случае, если оно имеет знак >, переходим к первой итерации.
(k+1)-я итерация. Пусть в результате k-й итерации получены
(k) и
(k).
Записываем
.
Находим

и определяем
и
.
В случае, если принять
=
для всех j, можно использовать для поиска эффективный метод одномерного поиска, например Фибоначчи, или 'золотого сечения'.
Решаем задачу в агрегированных переменных (10.4.61)-(10.4.64) при заданных
и находим
(k+1);
;
( k+1).
Решаем двойственную задачу (10.4.66)-(10.4.68) к агрегированной и находим оптимальные оценки {
},
.
Решаем блочные задачи (10.4.69)-(10.4.71) при найденных значениях {
},
и находим {
};
;
.
Проверяем признак оптимальности. Если при найденных значениях {
},{
} и {
} условие (10.4.75) выполняется как строгое равенство, то конец {
} - оптимальные решения исходной задачи, в противном случае переходим к (k+1)-й итерации.
Пример 10.5. Решить методом агрегирования следующую задачу ЛП:
максимизировать (x11+2x12+3x13+2x21+3x22+x23) (1)
при ограничениях
(2)

Первая итерация.
Выбираем начальные коэффициенты агрегирования

Составляем задачу в агрегированных переменных:
max 1,8x1+0,66x2 (3)
при ограничениях
(4)
Решаем ее графически (см.рис.10.2) и находим х(1)=8,4 ; х(2)=5 ; max f(x1,x2)=18,42. Одновременно находим и дезагрегированное решение:


Записываем задачу, двойственную к агрегированной:
(5)
при ограничениях
(6)
.
Для ее нахождения заметим, что в оптимальном решении прямой задачи как строгие равенства выполняются ограничения а) и ж). Это означает, что в оптимальном решении двойственной задачи соответствующие им двойственные переменные
и
не равны нулю. Тогда, решая систему ограничений (6) относительно уравнений
, находим 
При этом min
=18,42.
Записываем подзадачи для отдельных блоков.
Первая подзадача (І=1): найти
(7)
при ограничениях


Решив ее графически, находим 
Вторая подзадача (І=2): найти
(8)
при ограничениях


Находим ее решение : 
Третья подзадача: найти

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


Решив ее (например графически), находим

Проверяем условие оптимальности:

Поскольку
, то текущее решение не оптимально, и переходим ко второй итерации.
Следующие итерации выполняем аналогично - через три итерации получим решение {
}, для которого выполняется признак оптимальности:

Поскольку
(3)=0, то дезагрегированное решение {
(3)} - оптимально. Оно равно:

Для этого решения f({
})=28.