Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений

Рассмотрены две оптимизационные задачи межотраслевого планирования структурно-технологических изменений, представленные в виде квадратичных задач. Описаны возможные способы получения верхних оценок путем применения техники академика Н.З. Шора для нахождения двойственных лагранжевых оценок с использо...

Full description

Saved in:

Bibliographic Details
Date:	2010
Main Authors:	Бардадым, Т.А., Березовский, О.А.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Series:	Теорія оптимальних рішень
Online Access:	http://dspace.nbuv.gov.ua/handle/123456789/46675
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений / Т.А. Бардадым, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 40-46. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-46675
record_format	dspace
spelling	irk-123456789-466752013-07-07T03:02:46Z Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений Бардадым, Т.А. Березовский, О.А. Рассмотрены две оптимизационные задачи межотраслевого планирования структурно-технологических изменений, представленные в виде квадратичных задач. Описаны возможные способы получения верхних оценок путем применения техники академика Н.З. Шора для нахождения двойственных лагранжевых оценок с использованием функционально избыточных ограничений. Розглянуто дві оптимизаційні задачі міжгалузевого планування структурно-технологічних змін, які представлені у вигляді квадратичних задач. Описані можливі способи отримання верхніх оцінок шляхом застосування техніки академіка Н.З. Шора для знаходження двоїстих лагранжевих оцінок з використанням функціонально надлишкових обмежень. Two optimisation problems of interbranch planning of structural and technological changes formulated as quadratic type problems are considered. Possible ways for finding upper bounds by technique of Academician N.Z. Shor to find Lagrangean dual bounds with the use of superfluous constrains are described. 2010 Article Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений / Т.А. Бардадым, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 40-46. — Бібліогр.: 4 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/46675 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассмотрены две оптимизационные задачи межотраслевого планирования структурно-технологических изменений, представленные в виде квадратичных задач. Описаны возможные способы получения верхних оценок путем применения техники академика Н.З. Шора для нахождения двойственных лагранжевых оценок с использованием функционально избыточных ограничений.
format	Article
author	Бардадым, Т.А. Березовский, О.А.
spellingShingle	Бардадым, Т.А. Березовский, О.А. Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений Теорія оптимальних рішень
author_facet	Бардадым, Т.А. Березовский, О.А.
author_sort	Бардадым, Т.А.
title	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений
title_short	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений
title_full	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений
title_fullStr	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений
title_full_unstemmed	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений
title_sort	верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2010
url	http://dspace.nbuv.gov.ua/handle/123456789/46675
citation_txt	Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений / Т.А. Бардадым, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 40-46. — Бібліогр.: 4 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT bardadymta verhnieocenkidlâoptimizacionnyhzadačmežotraslevogoplanirovaniâstrukturnotehnologičeskihizmenenij AT berezovskijoa verhnieocenkidlâoptimizacionnyhzadačmežotraslevogoplanirovaniâstrukturnotehnologičeskihizmenenij
first_indexed	2025-07-04T06:06:33Z
last_indexed	2025-07-04T06:06:33Z
_version_	1836695364376199168
fulltext	40 Теорія оптимальних рішень. 2010, № 9 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассмотрены две оптимизацион- ные задачи межотраслевого пла- нирования структурно-техноло- гических изменений, представ- ленные в виде квадратичных за- дач. Описаны возможные спосо- бы получения верхних оценок пу- тем применения техники акаде- мика Н.З. Шора для нахождения двойственных лагранжевых оце- нок с использованием функцио- нально избыточных ограничений.  Т.А. Бардадым, О.А. Березовский, 2010 ÓÄÊ 519.8 Ò.À. ÁÀÐÄÀÄÛÌ, Î.À. ÁÅÐÅÇÎÂÑÊÈÉ ÂÅÐÕÍÈÅ ÎÖÅÍÊÈ ÄËß ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ ÇÀÄÀ× ÌÅÆÎÒÐÀÑËÅÂÎÃÎ ÏËÀÍÈÐÎÂÀÍÈß ÑÒÐÓÊÒÓÐÍÎ-ÒÅÕÍÎËÎÃÈ×ÅÑÊÈÕ ÈÇÌÅÍÅÍÈÉ∗∗∗∗ Введение. В работе [1] рассмотрена оптими- зационная модель планирования структурно- технологических изменений в переходной экономике, которая базировалась на уравне- ниях межотраслевого баланса. Модель пред- назначена для оптимизации изменений меж- отраслевой структуры затрат и конечных до- ходов при условии отсутствия усиления ин- фляции издержек и ограничениях на ресур- сы, выделяемые на проведение структурно- технологических преобразований. Были рас- смотрены два критерия оптимальности: А) максимизация совокупного конечного дохода потребителей, В) максимизация мультипликатора «при- рост доходов – прирост производства». Также предполагалась возможность ис- пользования не только данных двух вариан- тов целевой функции, но и их взвешенной линейной комбинации. В работе [1] приведены формулировки многоэкстремальных оптимизационных за- дач для каждой из целевых функций А) и В). Для их решения разработаны методы нахо- ждения локальных экстремумов на основе r-алгоритма в сочетании с мультистартом, которые легли в основу вычислительных мо- дулей программной системы IOMSTC (Inter- sectoral Optimization Models of Structural and ∗Работа выполнена при частичной поддерж- ке SNSF (Швейцария), проект № IZ73ZO_127962 ВЕРХНИЕ ОЦЕНКИ ДЛЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ МЕЖОТРАСЛЕВОГО ПЛАНИРОВАНИЯ... Теорія оптимальних рішень. 2010, № 9 41 Technological Changes), созданой в Институте кибернетики им. В.М. Глушкова НАН Украины. Нахождение нескольких локальных экстремумов позволяет сде- лать процесс принятия решения при определении основных направлений изме- нения технологических коэффициентов более гибким. При этом вопрос о каче- стве полученных решений (в смысле близости к глобальному) остается откры- тым. Некоторые ответы на этот вопрос можно получить, как упоминалось в [1], если представить предложенные задачи в виде невыпуклых квадратичных задач и воспользо- ваться подходом академика Н.З. Шора для получения двойственных лагранжевых оце- нок с использованием функционально избыточных ограничений [2]. Постановка квадратичных задач. Экономический смысл рассматриваемой межотраслевой модели планирования структурно-технологических изменений подробно изложен в работе [1]. Рассмотрим формулировки оптимизационных задач, которые представлены в разделе 2 работы [1], сохранив принятые там обозначения. Переменными в этих задачах выступают: - матрица , 1{ }n ij i jA a =∆ = ∆ (определяет изменения существующих значений компонент матрицы , 1{ }n ij i jA a == коэффициентов прямых затрат для n отраслей, известной также как матрица Леонтьева [3]); - вектор 1{ }n i iq q =∆ = ∆ (определяет изменения существующих значений ком- понент вектора 1{ }n i iq q == , которые определяют долю конечных доходов в каж- дой из отраслей); - вектор z (дополнительные переменные, которые отражают структуру ко- нечных доходов, получаемых от различных видов экономической деятельности). Задача A [1] максимизации совокупного конечного дохода потребителей: 1( ) = max 1 T T z h F z z → − α (1) при ограничениях =1 ( ) = , = 1, n j ji ji i j j i z a a z q q j n− + ∆ + ∆∑ , (2) (определяют дополнительные переменные) =1, ( ) ( ( ) ) ( ) , = 1, n jj jj j j j j ij ij i i j a a l q q d a a j n ≠ β + ∆ + β + ∆ + + + ∆ ≤ β∑ , (3) (исключают усиление инфляции издержек, 0 1< β < – заданный доверительный параметр) ( ) 1, = 1,jj jj j j j ja a l q q d j n+ ∆ + + ∆ + ≤ , (4) (баланс затрат и добавленной стоимости) , , , = 1, . i i i ij ij ij q q q a a a i j n∆ ≤ ∆ ≤ ∆ ∆ ≤ ∆ ≤ ∆ (5) Т.А. БАРДАДЫМ, О.А. БЕРЕЗОВСКИЙ 42 Теорія оптимальних рішень. 2010, № 9 (границы изменения коэффициентов, обусловленные особенностями сущест- вующих технологий и их физическим смыслом), =1 =1 max(0, ) , = 1, , n n kij ij k j i b a B k K−∆ ≤∑∑ (6) (ограничения на ресурсы при проведении структурно-технологических преобра- зований). Задача В [1], в которой в качестве целевой функции выступает мультипли- катор «прирост доходов – прирост производства» (мультипликатор Кейнса): 2 ( ) = maxTF z z α → (7) при тех же ограничениях (2)–(6). Для того, чтобы преобразовать задачи А и В к квадратичному виду: 1) заменим ограничение (6) на 2 =1 =1 n n kij ij k j i b y B≤∑∑ , = 1,k K , (8) 2 0ij ijy a+ ∆ ≥ , , =1,i j n ; (9) 2) в задаче А введем дополнительную переменную v : 0T Tvz z h vα + − = . (10) Тогда задаче A соответствует квадратичная задача max v (11) при ограничениях (2)–(5) и (8)–(10), а задаче В – квадратичная задача (2)–(5), (7)–(9). Двойственные лагранжевые оценки для квадратичных задач с исполь- зованием функционально избыточных ограничений. Для нахождения верх- ней оценки в квадратичных задачах максимизации * 0 0max( ) n T T x f x K x b x ∈ℜ = + , (12) 0T T i i ix K x b x c+ + = , i I∈ , 0T T i i ix K x b x c+ + ≤ , i J∈ , (13) можно применить подход, предложеный академиком Н.З. Шором – найти * * inf ( ) u D U u f −∈ ∩ ψ = ψ ≥ , (14) где ( ) max ( , ) nx u L x u ∈ℜ ψ = , ( , )L x u – функция Лагранжа для исходной задачи, D – множество двойственных переменных u , в которых матрица ( )K u квадратичной формы ( , )L x u отрицательно определена, { : 0, }iU u u i J − = ≤ ∈ . А расширение ис- ходной квадратичной постановки за счет добавления новых функционально из- быточных ограничений позволяет улучшать полученную для нее оценку (за счет большей "мобильности" квадратичной матрицы функции Лагранжа в результате ВЕРХНИЕ ОЦЕНКИ ДЛЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ МЕЖОТРАСЛЕВОГО ПЛАНИРОВАНИЯ... Теорія оптимальних рішень. 2010, № 9 43 расширения области D ). Еще в 80-х годах Н.З. Шором предлагался следующий путь расширения задачи: 1) добавление в квадратичную задачу ограничений, которые вводят новые переменные ( ) ( ) ( ) i j k R R Rα = α α , i j k α = α + α , вектор 1 2( , , , )n T i i i iα = α α α ≤ αK определяет переменную ( )iR α , которой в иcходном пространстве nℜ соответст- вует моном 1 2 ( ) n i i i iR x x x α α αα = K . Вектор α , который теоретически может выби- раться каким угодно, ограничивает количество этих переменных. (В работе [2] эта схема использовалась для понижения степени полинома при сведении его к квадратичной функции при квадратичных ограничениях. Однако следует отме- тить, что любую квадратичную функцию (полином) можно рассматривать как полином более высокой степени, коэффициенты которого при старших степенях равны нулю); 2) добавление ограничений, полученных путем перемножения ограничений задачи во всех возможных сочетаниях (по два, по три и т.д.). Полученные огра- ничения, содержащие мономы, степень которых не позволяет их представление в виде квадратичной формы, исключаются. Но тогда включаются их линейные комбинации степени не больше двух. Например, если задача имеет ограничения 2 1 1 1( , )x a x b= + , 2 2 2 2( , )x a x b= + , 1 2 3 3( , )x x a x b= + , то ограничения 2 2 1 2 1 1 2 2(( , ) )(( , ) )x x a x b a x b= + + и 2 2 2 1 2 3 3(( , ) )x x a x b= + игнориру- ются, но 2 1 1 2 2 3 3(( , ) )(( , ) ) (( , ) )a x b a x b a x b+ + = + добавляется в задачу. Сочетание этих двух приемов позволяет построить сколь угодно большое число ограничений. Описанная схема была применена для задачи нахождения глобального минимума полинома с вектором старших степеней s (отметим, что все компоненты вектора s четные, если полином ограничен снизу). Для случая, когда: 1) вводятся переменные при / 2sα = ; 2) вcледствие отсутствия ограниче- ний в исходной задаче в результате перемножений имеет место только семейство ограничений вида ( ) ( ) ( ) ( ) 0 i j k l R R R Rα α − α α = для всех i j k l α + α = α + α , был получен теоретический результат о необходимом и достаточном условии точно- сти оценки [2]. Отметим, что в качестве функционально избыточных ограничений могут выступать любые квадратичные ограничения (как с исходными переменными, так и с произвольными новыми), которые не влияют на допустимую область ис- ходной квадратичной задачи и «полезно» расширяют эффективное множество функции ( )uψ . Например, если в произвольную квадратичную задачу добавить ограничение 2 * 0 0 0T Ty x K x b x f− − + = , то двойственная оценка ψ (14) будет точной. Таким образом, возможностей построения функционально избыточных ог- раничений существует достаточно много, и главный вопрос заключается в том, Т.А. БАРДАДЫМ, О.А. БЕРЕЗОВСКИЙ 44 Теорія оптимальних рішень. 2010, № 9 какие из них следует выбирать для достижения необходимого результата (как минимум, чтобы не увеличить внешнюю задачу (по двойственным переменным) до размерности, которая делает решение задачи нереальным с практической точ- ки зрения). На сегодняшний день универсального ответа на этот вопрос нет – на практике для каждой конкретной задачи используются ее специфика, общие со- ображения и метод проб и ошибок. Нахождение верхних оценок для задач А и В. Применим технику Н.З. Шора для оценки целевых функций в вышеописанных задачах межотрасле- вого планирования. Нетрудно видеть, что для исходных квадратичных постано- вок задачи А (2)–(5), (8)–(11) и задачи В (2)–(5), (7)–(9) область отрицательной определенности для матрицы функции Лагранжа – пустое множество, и этому случаю соответствует тривиальная оценка +∞ . Поэтому предлагается модифи- цировать постановку задачи следующим образом: 1) в общем случае необходимо сделать замену переменных 2 i i i i q q q q ∆ + ∆ ∆ = ∆ −% , 2 ij ij ij ij a a a a ∆ + ∆ ∆ = ∆ −% , и заменить ограничения (5) на ог- раничения вида 22 2 2 ( )( ) , , , = 1, 4 4 ij iji i i ij a aq q q a i j n ∆ − ∆∆ − ∆ ∆ ≤ ∆ ≤% % . Для упрощения изложения дальше будем предполагать, что 0 i i q q∆ + ∆ = , и, следовательно, ог- раничения (5) заменяются на 2 22 2 , , , = 1,i i ij ijq q a a i j n∆ ≤ ∆ ∆ ≤ ∆ ; (15) 2) для переменных z и y воспользуемся несколько искусственным прие- мом, добавив ограничения 2 2 i iz z≤ , 2 2 ij iy y≤ , , =1,i j n , (16) а в задаче А еще и 2 2v v≤ . (17) Численные значения параметров z , y и v , которые задают возможные диапа- зоны изменения соответствующих переменных, определяются по результатам анализа исходной задачи. Недостаток этого приема заключается в том, что если оценка * ( )uψ = ψ достигается при u , таком что соответствующий хотя бы од- ному из ограничений (16), (17) множитель Лагранжа не равен нулю, то значение ψ будет зависить от параметров z , y и v . Поэтому для лучшего результата желательны дополнительные ограничения, которые бы «сгладили» эту зависи- мость. Однако, такое расширение имеет и свои позитивные моменты благодаря наличию ограничений типа 2 2 i ix x≤ по всем переменным. Сведем квадратичные задачи к однородному виду путем домножения всех линейных мономов в задаче ВЕРХНИЕ ОЦЕНКИ ДЛЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ МЕЖОТРАСЛЕВОГО ПЛАНИРОВАНИЯ... Теорія оптимальних рішень. 2010, № 9 45 на дополнительную бинарную переменную t , а условие бинарности учтем путем добавления в ограничения уравнения 2 1t = . (18) При этом значение двойственной оценки, как показано в [4], не изменится. Таким образом, мы получили однородные квадратичные задачи (чтобы не дублировать практически те же формулы, будем ссылаться на старые, уточнив лишь, что все линейные мономы в них домножены на переменную t ): задача (2)–(4), (8)–(11), (15)–(18) соответствует задаче А, и задача (2)–(4), (7)–(9), (15), (16), (18) – задаче В. Эти постановки будем считать базовыми, а двойственные оценки (14) для них в дальнейшем можно будет уточнять, добавляя новые функ- ционально избыточные ограничения. Используя те же приемы, которые были применены в работе [4] для доказа- тельства теорем и их следствий о сведении нахождения оценки ψ (14) в ряде случаев к безусловной задаче минимизации (на основе точной негладкой штрафной функции и того факта, что для однородных квадратичных задач ре- шение внутренней задачи достигается при 0ix = , 1,i n= ), можно доказать сле- дующую теорему. Теорема. Если множество ограничений однородной квадратичной задачи (задачи (12), (13), в которой {0}i I J∀ ∈ ∪ ∪ 0ib = ) включает набор ограниче- ний 0 2 =+ ii cx , 1i I∈ , и 0 2 ≤+ ii cx , 1i J∈ , такой, что 1 1 {1,2, , }I J n∪ = K и 1 1 { }I J∩ = ∅ , то при 1 1 i i i I i J N c c ∈ ∈   > − +     ∑ ∑ ( ) 1 maxmin max 0; , ; ( ( ))i i i u U i I J c u N u i J K u −∈ ∈ ∪   ψ = + ∈ λ    ∑ , (19) где 1{ : 0, ( \ )}iU u u i J J − = ≤ ∈ . В результате задача А и задача В сводятся к задачам вида (19), а их размер- ности равны соответственно 2(3 5 3)n n K+ + + (размерность матрицы ( )K u – 2(2 2 2)n n+ + ) и 2(3 5 1)n n K+ + + (размерность матрицы ( )K u – 2(2 2 1)n n+ + ). При такой постановке не нужно решать внутреннюю задачу (систему линейных уравнений), и ограничение на отрицательную определенность матрицы функции Лагранжа учтено непосредственно в функционале. Отметим, что при добавле- нии новых семейств функционально избыточных ограничений в виде однород- ных квадратичных ограничений (в случае наличия линейных мономов, они умножаются на ту же переменную t ) общий вид задачи (19) не меняется. Вычислительные експерименты. Для экспериментальных исследований была написана программа на языке Octave, реализующая описанный подход для нахождения оценки *ψ для задачи В (для решения задачи минимизации (19) ис- Т.А. БАРДАДЫМ, О.А. БЕРЕЗОВСКИЙ 46 Теорія оптимальних рішень. 2010, № 9 пользовалась модификация r-алгоритма [2]). В качестве тестовой выбрана семи- отраслевая модель с одним ограничением вида (6) (на ресурсы для проведения структурно-технологических преобразований), для которой мультипликатор Кейнса в известном локальном минимуме равен 0,524. Параметры ограничений (16) приняты равными: 1iz = , ij ij y a= ∆ , , =1,i j n . Размерность матрицы ( )K u равна 113 113× , количество двойственных переменных (размерность вектора u ) – 184. Полученная оценка равна 0,916. Сейчас исследования находятся на этапе определения приемлемого с вычислительной точки зрения набора избыточных ограничений, чтобы получать оценку с удовлетворяющей точностью за прием- лемое время. Т.О. Бардадим, О.А. Березовський ВЕРХНІ ОЦІНКИ ДЛЯ ОПТИМІЗАЦІЙНИХ ЗАДАЧ МІЖГАЛУЗЕВОГО ПЛАНУВАННЯ СТУКТУРНО-ТЕХНОЛОГІЧНИХ ЗМІН Розглянуто дві оптимизаційні задачі міжгалузевого планування структурно-технологічних змін [1], які представлені у вигляді квадратичних задач. Описані можливі способи отримання верхніх оцінок шляхом застосування техніки академіка Н.З. Шора для знаходження двоїстих лагранжевих оцінок з використанням функціонально надлишкових обмежень. T.O. Bardadym, O.A. Berezovskyi UPPER BOUNDS FOR OPTIMIZATION PROBLEM OF INTERSECTORAL PLANNING OF STRUCTURAL AND TECHNOLOGICAL CHANGES Two optimisation problems of interbranch planning of structural and technological changes [1] for- mulated as quadratic type problems are considered. Possible ways for finding upper bounds by tech- nique of Academician N.Z. Shor to find Lagrangean dual bounds with the use of superfluous con- strains are described. 1. Сергиенко И.В., Михалевич М.В., Стецюк П.И., Кошлай Л.Б. Модели и информаци- онные технологии для поддержки принятия решений при проведении структурно- технологических преобразований // Кибернетика и системный анализ. – 2009. – № 2. – С. 26 – 49. 2. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференци- руемая оптимизация. – Киев: Наук. думка, 1989. – 208 с. 3. Леонтьев В. Экономические эссе. – М.: Политиздат, 1990. – 417 с. 4. Березовский О.А., Стецюк П.И. Об одном способе нахождения двойственных квадратичных оценок Шора // Кибернетика и системный анализ. – 2008. – № 6. – С. 89–99. Получено 06.04.2010

Верхние оценки для оптимизационных задач межотраслевого планирования структурно-технологических изменений

Institution

Similar Items