Применение метода линеаризации к задачам большого объема тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Кирик, Елена Евстафьевна

• Кирик, Елена Евстафьевна
• кандидат физико-математических наук
• 1983

Оглавление диссертации кандидат физико-математических наук Кирик, Елена Евстафьевна

ВВЕДЕНИЕ

ГЛАВА I. БЛОЧНЫЕ ЗАДАЧИ СО СВЯЗЫВАЮЩИМИ ПЕРЕМЕННЫМИ

§ 1.1. Формулировка проблемы

1.1.1. Процессы, приводящие к задачам со связывающими переменными.

1.1.2. Постановка задачи .I?

1.1.3. Процедура расчленения

§ 1.2. Координирующая и вспомогательные задачи

1.2.1. Определения

1.2.2. Условия регулярности

1.2.3. Целевая функция координирующей задачи 20 1,2Л. Локальные координирующие задачи

§ 1.3. Декомпозиционный алгоритм для задачи квадратичного программирования со связывающими переменными

1.3.1. Процедура решения координирующей задачи Критерий оптимальности

1.3.2. Описание алгоритма

1.3.3. Рекуррентные формулы

§ 1.4. Обоснование конечной сходимости

§ 1.5. Случай вырождения

ГЛАВА 2. БЛОЧНЫЕ ЗАДАЧИ СО СВЯЗШАВДШ ОГРАНИЧЕНИЯМИ

§ 2.1. Декомпозиция, использующая механизм множителей

Лагранжа.

2.1.1. Реальные процессы, описываемые задачами со связывающими ограничениями

2.1.2. декомпозиция и двойственность

2.1.3. Двойственная координирующая задача. Основные определения.

2.1.4. Максимизация квадратичной функции в регулярной области.

2.1.5. Процедура выхода из нерегулярной точки

§ 2.2. Алгоритм для решения блочной задачи квадратичного программирования со связывающими ограничениями

§ 2.3. Обоснование сходимости

§ 2.4. Задача со слабо связанными блоками

2.4.1. Сведение к задаче со связывающими переменными

2.4.2. Исследование координирующей задачи

2.4.3. Построение локальных координирующих задач

2.4.4. Процедура решения локальных задач

2.4.5. Критерий оптимальности процесса

§ 2.5. Алгоритм для решения задачи квадратичного программирования со слабо связанными блоками

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ РЕШЕНИЯ ЗАДАЧ СПЕЦИАЛЬНО)!

СТРУКТУРЫ.'.

§ 3.1.-Компактное хранение информации при решении больших задач.

3.1.1. Задачи со слабо заполненными матрицами ограничений

3.1.2. Задачи с двусторонними ограничениями

3.1.3. Задачи с блочно-диагональной структурой ограничений.

§ 3.2. Возможности организации параллельных вычислений на многопроцессорных ЭВМ

3.2.1. Распараллеливание процесса вычислений при реализации декомпозиционных алгоритмов

3.2.2. Обращение симметричной матрицы специального вида.

3.2.3. Естественный- параллелизм и параллелизм смежных операций процесса (1.8)

§ 3.3. Вычислительный опыт решения задач специальной структуры.

ЗАКЛЮЧЕНИЙ . Ш

СПИСОК ОСНОВНОЕ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Применение метода линеаризации к задачам большого объема»

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

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

В настоящей работе рассматриваются большие задачи математического программирования. К экстремальным за/дачам сводятся очень многие проблемы прикладного характера и они зачастую обладают специальной структурой. Так, в задачах с линейными ограничениями ненулевые элементы матриц ограничений могут появляться лишь в диагональных блоках и в относительно малом числе связующих строк или столбцов ^35 , 74^.

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

В первом случае для решения задач специального вида используются общие методы математического программирования. При этом основные вычислительные трудности связаны с хранением больших массивов информации и с операциями над ними. Большие разреженные матрицы /матрицы, имеющие малый процент ненулевых элементов/ обычно хранятся в ЭВМ в упакованном виде, т.е. хранятся только ненулевые элементы вместе с необходимой информацией об их положении в матрице [бЗ^. Например, при использовании симплекс-метода для решения линейных задач большой размерности основные вычислительные трудности связаны с обращением матрицы базиса [бЗ , 88]. Если матрица условий задачи имеет специальную структуру, то необходимые вычисления могут быть выполнены с использованием матрицы меньшей размерности. Такой подход, к примеру, реализуется при применении метода учета двусторонних ограничений [82^[ или метода приведения базиса к треугольному виду [35^.

Методы, принадлежащие ко второму классу, основаны на разложении системы на подсистемы меньшей размерности. Обычно выделяются подсистемы первого и второго уровня таким образом, что подсистемы второго уровня определяют соответствующие изменения в подсистемах первого уровня. Задача второго уровня состоит в координации функционирования элементов первого уровня с целью получения общего решения исходной задачи. два основных декомпозиционных подхода были выдвинуты в начале шестидесятых годов нашего столетия при исследовании больших задач линейного программирования Дж. Данцигом, Ф. Вул-фом [21^, И. Корнай, Т. Липтаком [33^. Принцип Данцига - Вул-фа повлек за собой многочисленный поток работ, развивающих центральные идеи в различных направлениях. Если в исходном варианте решение координирующей задачи основано на методе улучшения плана в линейном программировании /см., например, /, то в последующих работах исходили из метода одновременного решения прямой и двойственной задачи [35], сокращения невязок обобщенного градиентного спуска [75][, использования модифицированных функций Лагранжа [52^ и других процедур. Применялись также игровые подходы [5*]. С помощью линеаризации и аппроксимации принцип Данцига-Вулфа распространялся на нелинейные задачи [35 , 92}. Техника разложения Данцига-Вулфа была перенесена и на некоторые специальные экстремальные задачи [37, 79, 86, 95].

В подходе Данцига-Вулфа за основу принимается разбиение условий задачи линейного программирования по строкам. Разбиение линейных ограничений задачи по столбцам положено в основу подхода Корнай-Липтака. В первоначальном варианте [зз] координирующая задача сводилась к отысканию седловой точки, или к решению максиминной задачи, для которой использовались методы теории игр. В последующих работах для решения главной задачи применялся метод возможных направлений £49], использовались множители Лагранжа при организации спуска по градиенту [91], выравнивание двойственных оценок [бО^ и другие. Декомпозиция Корнаи-Липтака была развита для нелинейных блочно-сепарабель-ных задач математического программирования / [зэ], [65*], [^9з] и др./.

В дальнейшем была разработана декомпозиция на основе разделения переменных, релаксации ограничений, разложение, связанное с агрегированием переменных, параметрическая декомпозиция и т.д. Эти подходы подробно изложены в [з5*], [?з].

Различные конкретные модели приводят к определенным приемам разложения, не имеющим аналогий с основными схемами. К настоящему времени разработано довольно много различных подходов для декомпозиции специальных классов задач выпуклого программирования и оптимального управления /см., напр., монографии зв], [ад], [ад], [б1], [«] /.

В последние годы появился ряд работ обзорного характера с обширной библиографией / И, [¡4], [35*], [7з], [74], [77], [87] и др./.

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

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

В основу предлагаемого подхода положен метод линеаризации 58]. Это метод решения общей задачи математического программирования. Метод носит итерационный характер. Для нахождения очередного приближения используется линеаризованная задача. Хотя метод линеаризации имеет наибольшее значение для нелинейного случая, его применение для задачи линейного программирования также не лишено смысла.

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

Он применим к решению задач дискретного минимакса.

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

Многолетнее успешное применение метода для решения практических задач обусловило интерес к нему со стороны исследователей и появление многочисленных модификаций [1,12,13,23, 44-47,59].

Рассмотрим -подробнее идею метода линеаризации /см. [55^ , ^58^, [57 /. Пусть^гребуется минимизировать функцию ( х) , ОС € ЕЛ при ограничениях ^(зс)^О, £ £ Л , где Л конечное множество индексов. Предполагается, что все функции ч непрерывно дифференцируемы. /Более полно ограничения, при которых применим метод линеаризации, приведены, например, в [*53]/. Все ограничения и (х) заменяются на линейные путем линеаризации их в некоторой точке ОС0 . Линейная аппроксимация является наиболее грубой. Для того, чтобы решение линеаризованной задачи в точке СС0 не уходило слишком далеко от ОС о » к линеаризованной целевой функции добавляется квадратичный член.

Итак, в методе линеаризации ¡^55] для определения направления движения из точки Хо используется воспомогательная задача квадратичного программирования

Ц(*.),р>+ {*(«•)< 0, г€ V*.), где Уф (об0) - множество индексов ограничений, существенных в точке Х0 . Обзор литературы по методам, использующим другую структуру линеаризованной задачи можно найти в [^26,57,69, 7 о].

Для решения вспомогательной задачи в рекомендуется метод сопряженных градиентов, сходящийся для задачи квадратичного программирования за конечное число шагов. Возможно использование и других конечных методов решения задач квадратичного программирования [22,34,57,58,74-] .

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

В существующих методах решения нелинейных задач большого объема требуется определенная структура расчленяемой задачи ^94-3 . В частности, существенными условиями оказываются выпуклость и аддитивная сепарабельность функций, определяющих критерий и ограничения. Поскольку расчленению в нашем случае будет подвергаться вспомогательная задача, которая обладает этими свойствами, то нет необходимости предъявлять подобные требования к исходной задаче. Таким образом, расширяется класс задач нелинейного программирования, которые могут быть решены с применением специальных приемов.

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

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

В главе I рассматриваются блочные задачи со связывающими переменными.

В § 1.1 перечисляются некоторые классы практических задач, которые приводят к подобным математическим моделям, а такке кратко излагается метод разделения переменных /см., напр.,[35]/ применяемый для решения задач подобного типа.

В § 1.2 формулируются подзадачи, на которые распадается вспомогательная задача метода линеаризации при фиксированных связывающих переменных, и строится координирующая задача с неявной целевой функцией. В [74*] и других работах описываются методы решения подобных координирующих задач, основанные на исследовании структуры целевой функции и ее производных в очередной допустимой точке. для задачи квадратичного программирования с единичной мат-трицей квадратичной формы удается уточнить структуру целевой функции координирующей задачи в целом. С этой целью вводятся определения регулярной точки, регулярной области и доказывается следующий факт /лемма 1.1/: в каждой регулярной области целевая функция координирующей задачи является квадратичной.

В п.1.3.1 предлагается процедура замены координирующей задачи с неявной кусочно-квадратичной целевой функцией последовательностью задач квадратичного программирования, которые мы назвали локальными координирующими задачами /ЛКЗ/. Принцип построения МЗ изложен в п. 1.2.4.

Подробно декомпозиционный алгоритм для блочной задачи квадратичного программирования со связывающими переменными сформулирован в п.1.3.2. Приведен критерий оптимальности /теорема 1.1/, выведены рекуррентные формулы для облегчения пересчета ЛКЗ /лемма 1.2/.

В § 1.4 приводится подробное обоснование конечной сходимости алгоритма.

В § 1.5 исследован случай вырождения /в очередной допустимой точке не выполняются условия регулярности/. Приводятся соответствующие рекомендации и обосновывается конечная сходимость алгоритма для этого случая.

В главе 2 рассмотрен второй основной тип блочных задач -задачи со связывающими ограничениями. Построен декомпозиционный алгоритм для блочной задачи квадратичного программирования со связывающими ограничениями /§ 2.2/. При разбиении этой задачи на подзадачи используются двойственные оценки связывающих ограничении /. Исходной схемой подобного рода является принцип декомпозиции Данцига-Вулфа [21"1 . Однако, в отличие от линейных задач, в задачах с нелинейными целевыми функциями возможна полная децентрализация принятия решений, т.е. оптимальная точка находится непосредственно при решении вспомогательных подзадач.

В функцию Лагранжа, ассоциированную с исходном задачей, включаем только связывающие ограничения. Строим двойственную задачу, размерность которой определяется числом связывающих оградвойственной задачи такой структуры алгоритма наискорейшего спуска, модифицированного с учетом простых ограничений. Эта градиентная процедура рассматривается как координирующий механизм для координатора верхнего уровня, задача которого состоит в решении двойственной проблемы при заданных значениях двойственной целевой функции и ее градиента. На нижнем уровне решаются подзадачи и находятся эти значения. В [50*] использован прием "усредненного градиента". В случае произвольных выпуклых функций для решения таких двойственных задач- применимы обобщенные градиентные методы минимизации негладких функций Г?б1.

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

В § 2.3 исследована скорость сходимости алгоритма.

В главе 2, кроме того, приведена процедура решения задачи квадратичного программирования со слабо связанными блоками, основанная на сведении задачи со связывающими ограничениями к задаче со связывающими переменными и использующая результаты главы I. Локальные координирующие задачи в данном случае имеют более сложную структуру, чем описанные в главе I, поэтому в п.2.4.4 подробно рассматривается процедура их решения.

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

В § 3.1 рассматриваются вопросы компактного хранения информации при применении метода линеаризации и приводятся модификаничений. В продемонстрировано применение для решения ции метода сопряженных градиентов для различных структур матрицы ограничений квадратичной за/;ачи.

В § 3.2 на примере алгоритма § 1.3 анализируются возможности организации параллельных вычислений на многопроцессорных ЭВМ.

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

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

С ЬА б реализации алгоритма § 2.2. При составлении схемы использовался псевдокод, описанный в [15^.

Изложенные результаты докладывались на семинарах "Выпуклый анализ и экстремальные задачи", "Теория оптимальных решений" в Институте кибернетики АН УССР, на семинаре кафедры теории оптимальных процессов Львовского государственного университета, на Ш Республиканской конференции "Вычислительная математика в современном научно-техническом прогрессе" /г. Канев/ и опубликова

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

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

ЕУЬ Компоненты векторов обозначаются индексами сверху. Нижние индексы обозначают элементы некоторой последовательности. Скалярное произведение двух векторов обозначается , ны в работах

Под нормой вектора понимается его евклидова норма

IXII = /<ос7^>

Звездочка сверху обозначает транспонирование. Под вектором X будем понимать вектор-столбец. Тогда X обозначает вектор-строку. Соответственно, А* - транспонированная матрицаЛ .

Нумерация формул, теорем, лемм, определений двойная. Первое число означает номер главы.

В заключение автор выражает глубокую и искреннюю благодарность научному руководителю профессору Б.Н.Пшеничному за постоянное внимание к работе.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Кирик, Елена Евстафьевна

Основные результаты работы состоят в следующем.

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

2. Введено определение локальной координирующей задачи /ЛКЗ/. Построен декомпозиционный алгоритм для блочной задачи квадратичного программирования со связывающими переменными, основанный на замене координирующей задачи с неявной целевой функцией последовательностью ЛКЗ.

3. Выведены рекуррентные формулы для реализации смены ЛКЗ.

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

5. Построен декомпозиционный алгоритм для блочной задачи квадратичного программирования со связывающими ограничениями.

6. Построен декомпозиционный алгоритм для задачи со слабо связанными блоками, основанный на сведении задачи со связывающими ограничениями к задаче со связывающими переменными и использующий результаты пп. 1-2.

7. Доказаны критерии оптимальности, обоснована сходимость и исследована скорость сходимости предложенных алгоритмов.

8. Рассмотрена возможность применения параллельных вычислений при реализации алгоритмов.

9. Проанализированы результаты вычислительных экспериментов.

ЗАКЛЮЧЕНИЕ

Для простоты изложения мы полагали, что в матрицах блочных задач имеется по два диагональных блока. Все результаты естественным образом распространяются на случай задач с произвольным количеством блоков. Если число блоков в ограничениях равно А/ , то при фиксированных связывающих переменных /алгоритмы § 1.3 и § 2.5/ или при преобразовании задачи минимизации со связывающими ограничениями в задачу минимизации функции Лаг-ранка /алгоритм § 2.2/ получаем не 2, а /V независимых подзадач. Целевые функции координирующих задач /1.5/ и /2.7/ состоят в этом случае из N Í составляющих и имеют вид N

Ф(р„)= £ ъ (p**i)+111Р^111'' t-l ш гдэ^(рм)=тСп1сГр{+|1!р411г, Aipi+Btp^i < О и кы=£ ксЫ+с-и, где kv (-«)= Km^í-' (¿Г ) p¿ + 5 líP¿ И®, á 0

Pi соответственно.

В схемах § 3.1, использующих компактное хранение при решении задач минимизации, на каждом этапе происходит параллельное преобразование не 2, а N векторов, где N - количество блоков исходной задачи.

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

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

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

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

- из это возможно, явных выражений этих функций.

Список литературы диссертационного исследования кандидат физико-математических наук Кирик, Елена Евстафьевна, 1983 год

1. Антипин A.C. Методы математического программирования, основанные на прямой и двойственной модификации функции Лагран-жа. М.: 1979. - 73с. - /Препринт / ВНИИ системных исследований/.

2. Будак Б.М., Беркович Е.М., Соловьева E.H. О сходимости разностных аппроксимаций для задач оптимального управления. -jiiypii. вычисл. матем. и матем. физики, 1969, ¡t 3, с. 552-547.

3. Васильев Ф.П. Числеиные методы решения экстремальных задач.-М.: Наука, 1980. 520 с.

4. Верина Л.Ф., Танаев B.C. декомпозиционные подходы к решению задач математического программирования. / Обзор. Экономика и матем. методы, 1975, т. XI, i.; 6, с. II60-II72.

5. Волконский В.А. Оптимальное планирование в условиях большой размерности /Итеративные методы и принцип декомпозиции/. -Экономика и матем. методы, 1965, т. I, ^ 2, с. 195-219.

6. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика, 1965, М 5, с. 1-Ю.

7. Глушков В.М., Молчанов И.Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений. Кибернетика, 1981, j,j с. 82-88.

8. Глушков В.М., Молчанов И.Н. и др. Программное обеспечение ЭВМ Мир-I и Мир-2, т. I, Численные методы. Киев.: Наукова думка, 1976. - 280 с.

9. Глушков В.М., Цейтлин Г.Е., лЗщснко Е.Л. Методы символьной мультиобработки. Киев: Наукова думка, 1980. 252 с.

10. Ю. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Проблемы анализа и синтеза структурированных параллельных программ. Кибернетика, 1981, н: 3, с. I-I6.

11. Глушков В.M., Цейтлин Г.S., Ющенко Е.Л. Многоуровневое структурное проектирование программ: формализация метода -сфера приложения. Кибернетика, 1931, ¡ц с. 42-65.

12. Голиков А.Й., .йадан В.Г. Итеративные методы решения задач нелинейного программирования с использованием модифицированных функций Лагранжа. -урн. вычисл. матем. и матем. физики, 1980, т. 20, i,, 4, с. 874-888.

13. Головкин Б.А. Параллельные вычислительные системы. М. : Наука, 1980. - 520 с.

14. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов. радио, 1966. - 524 с.

15. Грицай В.П., Тальянская О.И., Терзян Т.К. О разработке структурированных программ в системе ЫУЛЬТИПРОДЕССИСТ.

16. В кн.: Прикладное программирование. Киев: ИК АН УССР, 1982, с. 50-56.

17. Грицай В.П., Цейтлин Г.Е. Некоторые вопросы автоматизации структурного параллельного программирования. Кибернетика, 1979, I, с. 106-III.

18. Дал У., Дейкстра Э., Хоор К. Структурное программирование. -М. : Мир, 1975. 248 с.

19. Данилин Ю.М., Панин В.М., Пшеничный Б.Н. Модифицированный метод линеаризации. Кибернетика, 1982, 5, с. 70-73.

20. Данильченко В.Г., Остапенко В.В., Яковлева А.П. Игровой подход к водораспределению в оросительной системе. Киев, 1933. - 24 с. - /Препринт / Мн-т кибернетики АН УССР; 83-10/.

21. Данциг Дж. Линейное программирование, его обобщения и применения. М. : Прогресс, 1966. - 600 с.

22. Данциг дж. Б., Вулф Ф. Алгоритм разложения для задач линейного программирования. Математика, 1964, т. 8, I, с. 151-160. См.также: 33,84.

23. Даугавет В.А. Модификация метода Вулфа. &урн. вычисл. матем. и матем. физики, 1981, 21, 2, с. 504-508.

24. Даугавет В.А., Малоземов В.II. Квадратичная скорость сходимости одного метода линеаризации для решения дискретных минимаксных задач. дурн. вычисл. матем. и матем. физики, 1981, т. 21, 4, с. 835-843.

25. Дейкстра Э. Дисциплина программирования: М. : Мир, 1978. - 275 с.25. демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М. : Наука, 1972. - 368 с.

26. Евтушенко ¿О.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М. : Наука, 1982. -432 с.

27. Ермольев Ю.М., Гуленко В.П., Царенко Т.И. Конечно-разностный метод в задачах оптимального управления. Киев : Наукова думка, 1978. - 164 с.

28. Йордан Э. Структурное проектирование и конструирование программ. М. : Мир, 1979. - 409 с.

29. Карлин С. Математические методы в теории игр, программировании и экономике. М. : Мир, 1964. - 839 с.

30. Карманов В.Г. Математическое программирование. М. : Наука, 1975. - 272 с.

31. Карцев М.А. Принципы организации параллельных вычислений, структуры вычислительных систем и их реализация. Кибернетика, 1981, ¡.¿2, с. 68-74.

32. Комогоров В.В., Медницкий В.Г., Васенкова Н.В. Задача выпуклого программирования с разделяющимися переменными. -Экономика и матем. методы, 1930, т. ХУ1, в. 4, с. 778-784.

33. Корнай И., Липтак Т. Планирование на двух уровнях. В кн. : Применение математики в экономических исследованиях, т. 3. - М. : Мысль, 1965, с. 107-136.

34. Кюнци Г., Крелле В. Нелинейное программирование. М. : Сов. радио, 1965. - 301 с.

35. Лэсдон Л.С. Оптимизация больших систем. М. : Наука, 1975. - 431 с.

36. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Вища школа, 1975. - 372 с.

37. Малинников В.В. Метод разложения в решении больших задач линейного программирования с блочной структурой. Экономика и матем. методы, 1971, т. УП, й- 5, с. 733-736.

38. Мартинес Солер Ф., Черняк В.И. Моделирование плановых расчетов. - М, : Экономика, 1974. - 175 с.

39. Мауэр й. Штрафная константа в блочном программировании. -Изв. АН ЭССР, Физика, математика, т. 20, ¡¡; 4, 1971, с. 401405.

40. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых -систем. М. : Мир, 1973. - 344 с.

41. Мовшович С-.М. Метод невязок для решения задач блочной структуры. Экономика и матем. методы, 1966, т. II, ^ 4, с. 571577.

42. Моисеев Н.Н. Элементы теории оптимальных систем. М. : Наука, 1975. - 528 с.

43. Оскорбин Н.М. О схемах численных методов блочного программирования. Экономика и математические методы, 1981, т.ХУП, вып. 5, с. 964-972.

44. Панин В.М. Метод линеаризации для задач дискретного мини-макса. Кибернетика, 1980, ¡с 3, с. 86-90.4.5«, Панин В.М. Метод линеаризации для задачи непрерывного минимакса. Кибернетика, 1931, iü 2, с. 75-78.

45. Панин В.М. Параметрический метод линеаризации для безусловной задачи дискретного минимакса. В кн. : Кибернетика и вычислительная техника. Киев, 1981, L 53, с. 71-74.

46. Панин В.М., Пшеничный Б.Н. Параметрический метод линеаризации в задачах математического программирования. журн. вычисл. матем. и матем. физики, 1983, „i I, с. 61-72.

47. Первозванский A.A. Математические модели в управлении производством. М. : Наука, 1975, - 615 с.

48. Первозванская Т.Н., Первозванский A.A. Алгоритм поиска оптимального распределения централизованных ресурсов. Изв. АН СССР. Техническая кибернетика, 3, 1966, с. 16-19.

49. Первозванская Т.Н., Первозванский A.A. Децентрализация оптимального планирования в сложной системе. Автоматика и телемеханика, ^ 7, 1968, с. 60-71.

50. Полак Э. Численные методы оптимизации. Единый подход. М. : Мир, 1974. - 374 с.

51. Поляк Б.Т., Третьяков Н.В. Об одном итерационном методе линейного программирования и его экономической интерпретации. -Экономика и матем. методы, 1972, т. УШ, У 5, с. 740-751.

52. Попков Н.В., Тулупчук 10.М., Хилюк Л.Ф. Задача трехкритери-ального управления водохозяйственным комплексом Днепровского водохранилища /Озера Ленина/. Автоматика, 1978, к 2, с.44-53.

53. Пшеничный Б.Н. Необходимые условия экстремума. М. : Наука, 1969. - 151 с.

54. Пшеничный Б.Н. Алгоритмы для общей задачи математического . программирования. Кибернетика, 1970, и 5, с. 120-125.

55. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М. :1. Наука, 1980. 320 с.

56. Пшеничным Б.Н. метод линеаризации. М. : Наука, 1983. -136 с.

57. Пшеничный Б.Н., Данилин Ю.М. Численные методы б экстремальных задачах. Ы. : Наука, 1975. - 319 с.

58. Пшеничный Б.Н., Соболенко Л. А. Ускорение сходимости метода линеаризации для задачи условной минимизации. .¿урн. вычисл. матем. и матем. шизики, 1980, т. 20, з, с. 605614.

59. Разумихин Б.С. метод физического моделирования в математическом программировании и экономике. Метод итеративной декомпозиции и задача о распределении ресурсов. Автоматика и телемеханика, 1972, i,: II, с. III-123.

60. Cea j»¿. Оптимизация. Теория и алгоритмы. ¡L : мир, 1973. -244 с.

61. Табак Д., Куо Б. Оптимальное управление и математическое программирование. 1/Í. : Наука, 1975. - 280 с.

62. Тыоарсон Р. Разреженные матрицы. Ы. : ¡лир, 1977. - 190 с.

63. Ульм A.iü. метод штрафных функций в задачах большой размерности. Таллин: Валгус, 1979. - 132 с.

64. Умнов А.Е. метод штрафных функций в задачах большой размерности. ¿урн. вычисл. матем. и матем. физики, 1975, т. 15,6, с. 1399-1411.

65. Фаддеев д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. ы. : Физматгиз, 1960. - 656 с.

66. Фаддеева В.Н., Фаддеев д.К. Параллельные вычисления в линейной алгебре. Кибернетика, 1977, б, с. 28-39.

67. Фаддеева В.Н., Фаддеев д.К. Параллельные вычисления в линейной алгебре. II. Кибернетика, 1982, 3, с. 18-31.

68. Федоренко Р.П. Приближенное решение задач оптимального управления. М. : Hay tea, 1978. - 486 с.

69. Федоренко Р.П. Об одном алгоритме решения задач математического программирования. ¿урн. вычисл. матем. я матем. физики, 1982, т. 22, ^ 6, с. I33Í-I343.

70. Химмельблау Д. Прикладное нелинейное программирование. -М. : Мир, 1975. 534 с.

71. Хыоз Дж., Ыичтоы Дж. Структурный подход к программированию. М. : Мир, 1930. - 276 с.

72. Цурков В.й. Декомпозиция в задачах большой размерности. -LÍ. : Наука, 1981. 352 с.

73. Численные методы условной оптимизации / Ред. Ф. Гилл и У. Мюррэй. М. : Мир, 1977. - 290 с.

74. Шор Н.З. Применение обобщенного градиентного спуска в блочном программировании. Кибернетика, 1967, 3, с. 5855.

75. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев : Наукова думка, 1979. - 200 с.

76. Эннусте Ю.А. Проблемы декомпозиционного анализа для задач оптимального планирования. Экономика и матем. методы, 1972, т. ХШ, в. 4, с. 534-545.

77. С&анЦ L. Fait pawllzt matoC% шъсtbiovi aCcjO'uUiyYia . 61A M JcmaX ovi Computed, 19% 9 5, , p .6<e>-GSLd.

78. Ъаni^Xcj B.? Vavi ¿¿fyke. R.Wl. иррел ^oaiadCuo teckracj-ue*>. J. Computed fybte-Yu. ¿ti.,i, p. <нз-££б\

79. S-. В., l/i/об^е P. ^tootupotCiCon. pttuctpfeot (meat ргодъаилб . Орел. Re&. ? <3G0, v. 8, p.

80. Pease M.Ö. ШснЫх Cvitttiiovi patailti p^coceüó^ . "Jou-ttactC of Uajl Л б К, <36%,1. A4 , Ы-к , р. .

81. Реабе Wl.CÍ. <£nte/tu'oia wai^ces. ^ patttomugontKiae of ЛСЖ,, Ш, YG ,p. 314.

82. ЪакЖыь J. ß non&n.ea't otzooMpCLitcon pt/nccp^ . Opérait.'oui Resea-tcit 9 6 5v v. 43 , /V2 £ , p. A66 1.92. ¿efeme iOecmitafrfcerf opfcmc-Vaton 6¡f 0114 miento im eciecí zy&tz-wi . IEEE Ütctn*. úhtuúb

83. Ukeo^ 7 , v. С T-4.0, , p.tfi-M*93. ¿¿foctw-an "J. Ptcu/taê deoompoiótcOH maUitmecUtCLÍ рьодъамб ълсоиъа. aiioccKÜovi . Орел . R**. , , v. /V* 4 ,p. 5fr- 33.

84. Jocfctf 6ou/¿ k¿ fi. MtMctufcat <sftaflest wouiUuma/t p'bo^taiAAiMxiAj^ jotoé бгилЛ.-kectu/LL ¡ílóití ¿vi ¿oudtct ancl ¿hfotmattOH. •*><xen.ce¿ , , p. ibd iS?.

85. Wítliciviub Cl.C. CL Jtea"£*we.nf -ЬгауцрогЬсх.-biovi p'го ê it ut Bu dtwiMpoubCoiA . — STA M он Яррб . l/lActf/U .7 , v. ¿0, /V-4, p. 35"

86. Кирик Е.й. Декомпозиция одной блочной задачи квадратичного программирования со слабо связанными блоками. Киев, 1982. - 22 с. - Рукопись представлена Ученым советом Ин-та кибернетики им. В.и.Глуткова АН УССР. Деп. в ВИНИТИ 7 июля 1982 г., 3554-32.

87. Пшеничный Б.Н., Кирик Е.Е. Декомпозиционный алгоритм для задачи квадратичного программирования специальной структуры. Киев, 1982. - 26 с. /Препринт / Ин-т кибернетики АН УССР : 82-40/.

88. Кирик Е.Е. О решении задач нелинейного программирования с разделяющимися переменными. Кибернетика, 1933, 2,с. ПЗ-П4.