автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Исследование методов декомпозиции некоторых задач линейного и выпуклого программирования

хчшской

I.........I

На правах рукописи

иипкии

Специальность 05.13.16. -.....-11римслюпие ш>г

числительной техники, математического моделирования и математических методов в. научных исследованиях

Диссертация на соискание ученой степени кандидата физико-математических наук

аучныи руководитель д.ф.-м.н.,

Москва................... 1.999 г

Оглашгслие

$ II» дет и( 2

1. О некоторых (и 1Имо« или и.....пых задачах математиче.....

ской «жиномиьи и 1ироц(Ч'гах: согласования их решений. 7

1.1. Две классические задали..........................7

1.2. Обобщенная транспортная задала.............................10

1.3. Производственные модели. . . . . . ........................25

1.4. Производственно.....территориальные комплексы. . ...........35

1.5. О некоторых оценках и аппроксимации блочных условий.. 46

2. ДекомIюаиция зада1!и лшп*итого #|^)Жм|ишрования со

связующими ограничениями ж перейдёнными. 52

2.1. Поггамоти задачи в общем виде............................52

2.2. Прямой и двойственный процессы. ............ . . 57

2.3. Достаточное условие оптимальности решения. ...... 69

2.4. Объединенная производственно.......транспортная задача, . , 74

О согласовании локальных и глоЬмьных шггммадм!ых плав

3.1.

3.2.

[остановка задачи....................

[ервый вариант разложения глобальной задачи.

о и со

3.3. Второй, вариант разложения глобальной задачи. . . . . . 101

Заключение. 118

Список литературы.

П ноде.н ия.

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

мизационных задал началась в конце 50......х......................начале 60.....х г.г. (для

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

и ч с

ниченжи) и продолжалась в трудах многих исследователей, посколь......

ку разложение "большой" задали; рассматривалось как эффективное

средство преодоления ограничений по ресурсам: памяти и быстродей......

ствия ЭВМ. Этот аспект исследований остается актуальным: (несмотря на появление мощных пакетов прямого решения задач: матема.....

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

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

децентрализации: решений ..............более общим: образом: .................. механизмов

формирования, развития и функционирования разнообразных иерар.....

хических систем:: производственных, экономических, социальных и т.д. С этой точки: зрения становятся существенными тонкие детали поведения, связанные с конкретными особенностям:! и внутренней

структурой исследуемого объекта (как, например, в механике...................не

общая < иггема ураппений IIыогона, а следствия, скажем, для абсо* лютно твердого тела).

В диссертации в качестве объекта приложений разрабатываемых методов изучаются механизмы получения м согласования (в рамках глобальной: задачи более общего характера) оптимальных отраслевых и,па,поп, пранда, не и наиболее общей ишможной постановке;, а когда

целочисленные переменные не используются и задала остается вы......

пуклой. В действительности:, здесь возникает еще одна проблема........................

более адэкватного описания отраслевой задачи, поскольку классиче......

скал: производственно.....транспортная задача с одним видом: транспор......

та носит оценочный характер. Сопоставление отраслевых и глобаль......

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

Математический аналог такого рода неопределенности возникает в классической схеме блочной задачи: линейного программирования со связующими ограничениями и пере:м< и ними. Однако известно, что в общем случае для се декомпозиции можно пред пожить только трехуровневую схему Данцига.....Вулфа. Соответствии^ возникает вопрос;

нет ли в практических задачах каких......то особом по« той, использова......

ние которых позволило бы эту схему упростить. Такая особенность нашлась. Оказалось, что в рассматриваемых в диссертации задачах: (прямо или поел«1 .жвжшонтиш преобразований) удается получить систему, у которой на пересечении блоков, соответствующих связующим ограничениям и переменным, оказывается подматрица с нулевыми элементами. Такого рода системы и оказались математическим объектом проведенных в диссертации исследевалий. Следует отметить, однако, что приложение к конкретным: задачам: связано с весьма тонкими структурными особенностями, формирующих их соотношений, пи явление которых представляет е/шоетоятельныж интерес и: позволяет понять внутренние (и не всегда очевидные) свойства

изучаемых систем,

Основные цели и задачи: диссертации,

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

2. Изучение математических особенностей этих: задач с целью полу.....

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

3. Изучение параллельных процессов декомпозиции задачи линейно.....

го программирования: с нулевыми элементами! в пересечении блоков со связующими переменными и ограничениям:! (в простран......

ствах исходных и двойственных переменных).

4. Разработка аналогичных схем для разложения задачи выпуклого программирования (в прикладном аспекте для описания взаимодействий отраслевых систем: в рамках некоторого единого про......

изводственного комплекса).

5. Разработка алгоритмов согласования оптимальных решений ал......

проксимационных задал линейного прораммирования с варьиру......

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

6. Изучение последовательной и параллельной схем разложения вы......

пуклой зал

III лучи ]Я [ЮПИ ПН

1. Построены транспортные и производственные задачи на бихро.....

матическом ориентированном графе; предложен метод их объ.....

единения в единую задачу и алгоритм ее разложения в сопряжен.....

ных пространствах (конечномерных).

2. Изучены углоиил сущоспюпаиии решений локальных задал, По

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

ми из модифицированных локальных задач; построены допуска.....

ющие проверку в ходе вычислений критерии существования (от......

м) решений глобальной задах:

3. Изучен общий случай:, допускающий использование параллель.....

ных вычислений: при одновременном разложении: исходной и: двойственной: задач: линейного программирования со связующими пе.....

р еменными и огр аничениями.

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

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

5. Построены: и изучены два варианта алгоритмов разложения вы.....

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

Иц) пк гическая цииннть работы:, Построенные в работе зада......

ни, допускающие одновременную декомпозицию в пространствах они......

сывающих их: физических и экономических показателей, позволяют даже в малоразмерных вычислительных экспериментах на условной

информации выявить многие особенности и характерные черты по......

ведения разнообразных производственных: и экономических систем, не прибегал к дорогостоящим и не нслтда целесооОра.апим акппери ментам:,

Апробации работ««. Результаты работы докладывались авто......

ром на 2......ой Московской международной конференции по исследова......

ник) операций (Россия, г. Москва, 1.7-20 ноября 1.998 г.), международ......

ном: симпозиуме "Экономико-математические методы: в АПК: Исто......

рия и перспективы" (Россия, г. Москва, 13..........1.5 апреля 1.999 г,), науч......

ных семинарах отдела, сложных систем Ш1, РАН,

Публикации. Основное содержание диссертации опубликовано в 7 научных работах,

Структура и объем: работы. Диссертация: состоит из введе.....

ния, трех глав, заключения и списка литературы. Содержание ра......

боты изложено на 125 страницах. Список литературы содержит 47 наименований. В работе имеется 12 таблиц и: 4 рисунка.-

ii «1111,1 I (

математи согласов

н е к о1 г* > 11 )ы х н м и и:« 1 с; 1 ш; I ии 1 ш 1 л л . ¡а ,11 а • ы я «

ческой экономики и прещессах пия их ромюпий.

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

ограничениями и переменными, исследование которой и является од......

ной: из целей настоящей работы, Таким: образом, отбор следующих ниже задач произведен, скорее, в соответствии с целями настоящего исследования и не претендует на полноту. Более полные и систематизированные их обзоры можно найти в фундаментальных монографиях [1, 18, 30, 34, 35, 38, 39, 40].

»

.1 ..1. Две классические задали:,

Как известно, изучение задачи: линейного программирования началось с постановки и анализа двух экстремальных задан: о максимизации выпуска продукции: в комплекте |12, 1.4|

к..............> шах (1.

ь?............Ума <°> д >°> С1-2)

1 /................../ *

шчМ

3

У>;<1, «i > 0, (1.3)

т в

i

0, Vj .............. Pißy > 0, (1.4)

К =1, (1.5)

i

^ ^Vj.............•» min. (1.6)

i

и: транспортной задачи;, посвященном оптимизации перевозок однородных грузов [1.3, 15, 45, 46]

^ к ('ijXij..............> min,

.............5........>..............k, ^.......]хч > fib (L7)

i » Жу > 0.

Матрица, формирующая условия: задачи (1.7), имеет замечатель......

ную особенность......................каждый ее столбец содержит всего два ненуле......

вых: элемента (+1,-1). Как известно |9, 13, 15, 17, 29, 41, 45, 46], именно это позволяет предложить для ее решения эффективные специализированные алгоритмы и порождает ряд весьма тонких свойств многогранника условий, которые являются: предметом новейших исследований [29]. Пара двойственных задач: (LI)............(1.6) обладает почти

аналогичным свойством:, поскольку все ее переменные, кроме h, связаны: с двухкомпонентной структурой [1.7] столбца вида (......1.......1,............а,;.,),

причем исходя: из физического смысла а,;/ > 0. Но так как матрица содержит при переменной h один: столбец общего вида, то прямо использовать " хорошие" структурные особенности: остальной ее части для построения: какого.......либо специализировалного алгоритма не

удается.

Однако для решения задачи (1.1)..........(1.5) можно предложить такой ва.....

риант метода Данцига Форда Фулкерсона [9): устанавливая каким-либо образом: начальные значения: р-1 > 0 двойственных переменных в (1.2), можно доопределить их значения в (1.3), полагая: uj = maxp-ajj,

J i " ' '

а затем: оценить сверху значение h в (1.1) по допустимому решению двойственной задачи, так как h < /го::::::::

Далее, пусть I]1 = {г : v{- = р-Ч,?} и Jf = {j : и- = р-Ч?}- Рассмо......

трим пару вспомогательных двойственных задач

L>

mm,

^ ®<ijiij.....f......ei > hoX°h

.............E&>...........

>: 0,

Ь > 0,

kl?

& > 0, e» > 0,

Wij.............tj < 0,

Si < 1,

..........1,,/i

max

(1.8) (1.9)

(1.10)

(1.11) (1.12) (1.13)

.Если минимум в (1.8) достигает нулевого значения, то, как легко видеть, решение, оптимальное в первой из указанной: пары двойственных задач, будет оптимальным и в (1.1) (1.5). 'Если же значение минимума окажется положительным, то, комбинируя решение tj

двойственной в (1.8)...........(1.13) задачи с исходным набором:: р] = р{-......I......ersj,

v ...... v- ......(Tij, можно, во.....первых, в силу двойственных: условий: в

(1.9)............(1.12) получить при: некотором: W > 0 допустимое решение задачи (1.2)—(1.6), двойственной к (1.1)..........(1.5), с лучшей: оценкой: значения функционала (1.1) h < hi < ho и, во.......вторых, добавить к мно......

жеству пар (¿,j), на котором: ищется оптимальное решение задачи:

(1.8)...........(1.12), по крайней мере, один новый элемент. Иначе говоря, воз.....

никает монотонный (по Л,д, п = 0,1,...) процесс, во внутреннем: цикле которого решается: задача с двухкомпонентной структурой матрицы ограничений.

По.....видимому, это наиболее простой приме]:), показывающий как

осложняется' решение задачи: с блочной подструктурой ограничений

при появлении хотя бы одной связующей переменной (ибо в структур......

ном: отношении задачи: (1.1)..........(1.6) и: (1.7) только этим: и отличаются

друг от друга). Кроме того, можно предположить, как: отмечалось также в [20, 38, 44], что при решении такого типа задач должны: быть

эффективны методы, использующие одновременное движение в про.......

странствах исходных и двойственных переменных.

1.2. Обобщенная транспортная задача.

Как самостоятельная, прикладная задача модель (1.7) довольно бы......

стро утратила актуальность, но в качестве элемента, формирующего блочные подструктуры, входила в ограничения весьма разнообразных задал: отраслевой оптимизации, построенных на использовании: модели многопродуктовой производственно-транспортной задали |23|,

Для: дальнейшего представляет интерес обобщенная версия: транс.....

портной задачи, разработанная для оптимизации: портфеля торговых

контрактов [24], Суть обобщения заключается в том, что для органа:.....

зации перевозок некоторого набора продуктов используется: несколько видов транспорта с ограничениями на объемы грузооборота и с

учетом: ряда дополнительных факторов, например, таких: как: затра.....

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

к той, как она представлена в [19].

Пусть множеством г Е I определен набор продуктов, перевозки которых между совокупностью пунктов 1,з € I/, I ф з некоторой

рераспределение нагрузки между ними может происходить, вообще говоря, лишь в некоторых пунктах сети в результате специальных процессов, моделирующих происходящие в реальности операции по перевалке грузов. Соответственно, в набор исходных данных, кроме традиционно используемых в таких задачах коэффициентов транспортных затрат (на перемещение единицы продукта % из пункта I в пункт 5 видом: транспорта т), входят коэффициенты затрат с- (на перевалку единицы продукта г в пункте I), приведенные дальности

Ь}?т = перемещения продуктов (где ..................дальность, а щп...............

коэффициент приведения) и ограничения на объемы грузооборота по видам: средств перевозок кт. Пусть, кроме того, Щ..............верхние границы объемов перевалок, <;],(].......................заданные объемы вывоза и ввоза

(продукта % для: пункта I), а переменными х\8т и: х\ устанавливаются объемы перевозок и перевалок, которые должны: быть определены при решении оптимизационной задачи. Тогда модель.......................в форме канонической пары [5] двойственных: задач: линейного программирования.....................

будет включать соотношения

сети осуществляются различными видами транспорта т Е М. Пе-

(1.14)

(1.15)

£*L-*i= С. <<> (i.i6)

[,m WjI

P\> 0. (1-17)

- E > -Л». Г > 0, (1.18)

*L>o, (i.i9)

a?j>0, vj..............wj..........Pi < c[, (1.20)

X>kr.......v!ti-p!xi)-Er,mkm^max. (1.21)

¿,i m

При отбрасывании условий (LI8) эти задали распадаются на блоки по индексу г, а разделение по видам транспорта становится несущественным. В самом деле, зафиксируем некоторую тройку г, 1,5 и

положим Mus ....... {т : c-3m ........ mine-*"1}. Тогда двойственные огранит

нения (1.19), принимающие вид w\..........и- < c'"sm, выполняются строго

для всех т £ Мцй и, следовательно, по дополняющей нежесткости х)вт = 0. Кроме того, переменные x\smf т Е Мц8, входят в ограничения (1.15),(1.16) и функционал (1.14) только в составе суммы по ш, которая может быть заменена одной переменной Таким: образом:, задача оказывается эквивалентна классической однопродуктовой транспортной задаче с одним: видом транспорта (1.7).

Ограничения по верхним границам объемов перевалки в (1.17) существенны так как с их помощью, полагая Щ = 0 или Щ > 0, можно отделить фиктивные перевалки от реальных, рассматривая, когда, это удобно, каждый пункт сети как пункт с перевалками всех проходящих через него продуктов. По своему содержательному смыслу коэффициенты затрат 48т и с\ должны быть неотрицательны:, а значит, как

видно из (1.15)..........(1.20), двойственная задала имеет допустимое peine.....

ние v- = w\ = р\ = 0 для всех ¿,1; цт = 0 для всех т. Соответственно,

по основной теореме линейного программирования [5, 411 обе задали (1.14)...........(1.21) имеют оптимальные решения тогда и только тогда, когда существует допустимое решение у первой из них. Предполагая

существование этого решения и складыва