10.4 МЕТОД ДЕКОМПОЗИЦИИ НА ОСНОВЕ агрегирования в ЗАДАЧАХ БОЛЬШОЙ РАЗМЕРНОСТИ.

Одной из задач оптимального планирования с большим числом переменных и ограничений является так называемая модель отраслевого планирования. Годовой план области формируется на основе потребностей народного хозяйства в целом в ее продукции. При этом одна часть номенклатуры конечного выпуска фиксируется (так называемый “госзаказ”), а другая – находится в распоряжении отрасли или концерна. В качестве критерия выбирается максимизация выпуска свободной номенклатуры в заданном ассортиментном соотношении или максимизация прибыли (общая модель). Данная модель приводит к задаче ЛП с блочно-диагональной структурой части ограничений. Связывающие ограничения и критерий оптимальности имеют специфику, обусловленную конкретной моделью планирования. Эта специфика приводит к идее агрегирования переменных при построении декомпозиционного метода решения блочной задачи.

Постановка и математическая модель задачи

Рассмотрим задачу отраслевого планирования. Имеется отрасль (или большой концерн), которая характеризуется множеством заводов , множеством номеров изделий конечной продукции , множеством индексов номенклатуры изделий, производящихся на заводах отрасли , множеством номеров групп оборудования K_j, имеющихся на заводе j, множеством номеров комплектующих изделий, производящихся на заводе .

Предположим, что технологическая цепочка изготовления данного изделия на данном заводе фиксирована. Тогда производственные мощности каждого завода описываются (в рамках модели использования невзаимозаменяемых групп оборудования) следующими ограничениями:

(10.4.1)

где x_ij – годовой оборот выпуска изделий типа i на заводе j ; - годовой фонд времени работы оборудования группы k на заводе j ; - затраты времени работы оборудования группы k на заводе j на производство единицы изделия типа i.

Как следует из (10.4.1) величины x_ij определены на каждом заводе j только для . В дальнейшем удобно определить их для всех , полагая для этого x_ij=0 для . Связь между выпуском комплектующих изделий и выпуском конечной продукции описывается соотношением

, (10.4.2)

где y_m - годовой выпуск продукции вида m; W_ij – запас изделий вида i на заводе j на начало планового периода; e_im – число изделий вида i, входящих в единицу конечной продукции (вида m); -норматив запаса продукции m, переходящего на следующий год (в относительных единицах).

Предположим сначала, что множество номеров конечной продукции разбито на два непересекающихся подмножества , где

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

. (10.4.3)

Эта часть номенклатуры конечного выпуска называется обязательной. Предполагается, что существует вектор { } такой, что область допустимых планов не пустая. Продукция из множества называется свободной, и решение об объемах ее выпуска принимает администрация отрасли (или концерна).

Пусть администрация области определяет вектор свободной номенклатуры

{ } (10.4.4)

Вектор { } является недопустимым планом, то есть не существует величин {x_ij}, удовлетворяющих условиям (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)

Оптимальные величины x_i определяются через из (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)

где величины удовлетворяют условиям

Обозначим через при каждом множество допустимых решений блочных задач, то есть x_ij, удовлетворяющих ограничениям (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)}, агрегированных {x_i(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.

Дезагрегированное решение: x₁₁(0)=0,238; x₂₁(0)=0,238; x₁₂(0)=0,321; x₂₂(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, например, обобщенный градиентный метод.

Декомпозиция на основе агрегировання
для общей модели отраслевого планирования.

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

Рассмотрим теперь общий случай задачи отраслевого планирования. Пусть — стоимость единицы продукции x_ij. Пусть, кроме того, при выпуске изделий і-го вида на заводе j используются некоторые виды общих ресурсов l, , которые находятся в распоряжении отрасли (концерна), и их общие объемы ограничены. Обозначим через b_ijl расход ресурса l – го вида на выпуск продукции і-го вида (x_i) на заводе j, а P_l – реальный объем этого ресурса в отрасли, P_jk – объем собственного к-го ресурса на заводе j, b_ijk – норма расхода к-го ресурса на производство продукции i-го вида.

Тогда рассмотрим задачу максимизации прибыли от реализации продукции при ограничениях на общие ресурсы. Соответствующая модель задачи имеет вид:

максимизировать (10.4.55)

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

(10.4.56)

, при , x_ij=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)

при , x_ij=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 переменных, а блочной задачи имеют каждая по I_j переменных, наконец, задача максимизации функции на единичном гиперкубе включает J переменных.

На каждом шаге итеративного процесса неоднократно решается задача в агрегированных переменных (10.4.61), которая имеет небольшое количество переменных X_i, и большое число ограничений.

Сформулируем признак оптимальности промежуточного дезагрегированного решения. Пусть при некоторых весовых коэффициентах получено оптимальное решение макрозадачи (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 ⁰ обеспечивает оптимальность допустимого решения { } для задачи (10.4.55)-(10.4.58). Если же решение { } неоптимально для задачи (10.4.55)-(10.4.58) при условии ее разрешимости, то >f ⁰ .

Поскольку набор - оптимальные решения задач, двойственных к блочным (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. Решить методом агрегирования следующую задачу ЛП:

максимизировать (x₁₁+2x₁₂+3x₁₃+2x₂₁+3x₂₂+x₂₃) (1)

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

(2)

Первая итерация.

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

Составляем задачу в агрегированных переменных:

max 1,8x₁+0,66x₂ (3)

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

(4)

Решаем ее графически (см.рис.10.2) и находим х(1)=8,4 ; х(2)=5 ; max f(x₁,x₂)=18,42. Одновременно находим и дезагрегированное решение:

Записываем задачу, двойственную к агрегированной:

(5)

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

(6)

Для ее нахождения заметим, что в оптимальном решении прямой задачи как строгие равенства выполняются ограничения а) и ж). Это означает, что в оптимальном решении двойственной задачи соответствующие им двойственные переменные и не равны нулю. Тогда, решая систему ограничений (6) относительно уравнений