Применение метода линеаризации к задачам большого объема
Диссертация
В функцию Лагранжа, ассоциированную с исходном задачей, включаем только связывающие ограничения. Строим двойственную задачу, размерность которой определяется числом связывающих оградвойственной задачи такой структуры алгоритма наискорейшего спуска, модифицированного с учетом простых ограничений. Эта градиентная процедура рассматривается как координирующий механизм для координатора верхнего… Читать ещё >
Содержание
- ГЛАВА 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. Случай вырождения
- 1. 1. Формулировка проблемы
- ГЛАВА 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. Вычислительный опыт решения задач специальной структуры
- 3. 1. -Компактное хранение информации при решении больших задач
- ЗАКЛЮЧЕНИЙ. Ш
- СПИСОК ОСНОВНОЕ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Список литературы
- Антипин A.C. Методы математического программирования, основанные на прямой и двойственной модификации функции Лагран-жа. М.: 1979. — 73с. — /Препринт / ВНИИ системных исследований/.
- Будак Б.М., Беркович Е. М., Соловьева E.H. О сходимости разностных аппроксимаций для задач оптимального управления. -jiiypii. вычисл. матем. и матем. физики, 1969, ?t 3, с. 552−547.
- Васильев Ф.П. Числеиные методы решения экстремальных задач.-М.: Наука, 1980. 520 с.
- Верина Л.Ф., Танаев B.C. декомпозиционные подходы к решению задач математического программирования. / Обзор. Экономика и матем. методы, 1975, т. XI, i.- 6, с. II60-II72.
- Волконский В.А. Оптимальное планирование в условиях большой размерности /Итеративные методы и принцип декомпозиции/. -Экономика и матем. методы, 1965, т. I, ^ 2, с. 195−219.
- Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика, 1965, М 5, с. 1-Ю.
- Глушков В.М., Молчанов И. Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений. Кибернетика, 1981, j, j с. 82−88.
- Глушков В.М., Молчанов И. Н. и др. Программное обеспечение ЭВМ Мир-I и Мир-2, т. I, Численные методы. Киев.: Наукова думка, 1976. — 280 с.
- Глушков В.М., Цейтлин Г. Е., лЗщснко Е.Л. Методы символьной мультиобработки. Киев: Наукова думка, 1980. 252 с.
- Ю. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Проблемы анализа и синтеза структурированных параллельных программ. Кибернетика, 1981, н: 3, с. I-I6.
- Глушков В.M., Цейтлин Г. S., Ющенко Е. Л. Многоуровневое структурное проектирование программ: формализация метода -сфера приложения. Кибернетика, 1931, ¡-ц с. 42−65.
- Голиков А.Й., .йадан В. Г. Итеративные методы решения задач нелинейного программирования с использованием модифицированных функций Лагранжа. -урн. вычисл. матем. и матем. физики, 1980, т. 20, i, 4, с. 874−888.
- Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. — 520 с.
- Гольштейн Е.Г., Юдин Д. Б. Новые направления в линейном программировании. М.: Сов. радио, 1966. — 524 с.
- Грицай В.П., Тальянская О. И., Терзян Т. К. О разработке структурированных программ в системе ЫУЛЬТИПРОДЕССИСТ.
- В кн.: Прикладное программирование. Киев: ИК АН УССР, 1982, с. 50−56.
- Грицай В.П., Цейтлин Г. Е. Некоторые вопросы автоматизации структурного параллельного программирования. Кибернетика, 1979, I, с. 106-III.
- Дал У., Дейкстра Э., Хоор К. Структурное программирование. -М.: Мир, 1975. 248 с.
- Данилин Ю.М., Панин В. М., Пшеничный Б. Н. Модифицированный метод линеаризации. Кибернетика, 1982, 5, с. 70−73.
- Данильченко В.Г., Остапенко В. В., Яковлева А. П. Игровой подход к водораспределению в оросительной системе. Киев, 1933. — 24 с. — /Препринт / Мн-т кибернетики АН УССР- 83−10/.
- Данциг Дж. Линейное программирование, его обобщения и применения. М.: Прогресс, 1966. — 600 с.
- Данциг дж. Б., Вулф Ф. Алгоритм разложения для задач линейного программирования. Математика, 1964, т. 8, I, с. 151−160. См. также: 33,84.
- Даугавет В.А. Модификация метода Вулфа. &-урн. вычисл. матем. и матем. физики, 1981, 21, 2, с. 504−508.
- Даугавет В.А., Малоземов В.II. Квадратичная скорость сходимости одного метода линеаризации для решения дискретных минимаксных задач. дурн. вычисл. матем. и матем. физики, 1981, т. 21, 4, с. 835−843.
- Дейкстра Э. Дисциплина программирования: М.: Мир, 1978. — 275 с. 25. демьянов В.Ф., Малоземов В. Н. Введение в минимакс. М.: Наука, 1972. — 368 с.
- Евтушенко ?О. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. -432 с.
- Ермольев Ю.М., Гуленко В. П., Царенко Т. И. Конечно-разностный метод в задачах оптимального управления. Киев: Наукова думка, 1978. — 164 с.
- Йордан Э. Структурное проектирование и конструирование программ. М.: Мир, 1979. — 409 с.
- Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964. — 839 с.
- Карманов В.Г. Математическое программирование. М.: Наука, 1975. — 272 с.
- Карцев М.А. Принципы организации параллельных вычислений, структуры вычислительных систем и их реализация. Кибернетика, 1981, ?.?2, с. 68−74.
- Комогоров В.В., Медницкий В. Г., Васенкова Н. В. Задача выпуклого программирования с разделяющимися переменными. -Экономика и матем. методы, 1930, т. ХУ1, в. 4, с. 778−784.
- Корнай И., Липтак Т. Планирование на двух уровнях. В кн.: Применение математики в экономических исследованиях, т. 3. — М.: Мысль, 1965, с. 107−136.
- Кюнци Г., Крелле В. Нелинейное программирование. М.: Сов. радио, 1965. — 301 с.
- Лэсдон Л.С. Оптимизация больших систем. М.: Наука, 1975. — 431 с.
- Ляшенко И.Н., Карагодова Е. А., Черникова Н. В., Шор Н.З. Линейное и нелинейное программирование. Вища школа, 1975. — 372 с.
- Малинников В.В. Метод разложения в решении больших задач линейного программирования с блочной структурой. Экономика и матем. методы, 1971, т. УП, й- 5, с. 733−736.
- Мартинес Солер Ф., Черняк В. И. Моделирование плановых расчетов. — М,: Экономика, 1974. — 175 с.
- Мауэр й. Штрафная константа в блочном программировании. -Изв. АН ЭССР, Физика, математика, т. 20, ??- 4, 1971, с. 401 405.
- Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых -систем. М.: Мир, 1973. — 344 с.
- Мовшович С-.М. Метод невязок для решения задач блочной структуры. Экономика и матем. методы, 1966, т. II, ^ 4, с. 571 577.
- Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975. — 528 с.
- Оскорбин Н.М. О схемах численных методов блочного программирования. Экономика и математические методы, 1981, т. ХУП, вып. 5, с. 964−972.
- Панин В.М. Метод линеаризации для задач дискретного мини-макса. Кибернетика, 1980, ¡-с 3, с. 86−90.4.5″, Панин В. М. Метод линеаризации для задачи непрерывного минимакса. Кибернетика, 1931, iu 2, с. 75−78.
- Панин В.М. Параметрический метод линеаризации для безусловной задачи дискретного минимакса. В кн.: Кибернетика и вычислительная техника. Киев, 1981, L 53, с. 71−74.
- Панин В.М., Пшеничный Б. Н. Параметрический метод линеаризации в задачах математического программирования. журн. вычисл. матем. и матем. физики, 1983, «i I, с. 61−72.
- Первозванский A.A. Математические модели в управлении производством. М.: Наука, 1975, — 615 с.
- Первозванская Т.Н., Первозванский A.A. Алгоритм поиска оптимального распределения централизованных ресурсов. Изв. АН СССР. Техническая кибернетика, 3, 1966, с. 16−19.
- Первозванская Т.Н., Первозванский A.A. Децентрализация оптимального планирования в сложной системе. Автоматика и телемеханика, ^ 7, 1968, с. 60−71.
- Полак Э. Численные методы оптимизации. Единый подход. М.: Мир, 1974. — 374 с.
- Поляк Б.Т., Третьяков Н. В. Об одном итерационном методе линейного программирования и его экономической интерпретации. -Экономика и матем. методы, 1972, т. УШ, У 5, с. 740−751.
- Попков Н.В., Тулупчук 10.М., Хилюк Л. Ф. Задача трехкритери-ального управления водохозяйственным комплексом Днепровского водохранилища /Озера Ленина/. Автоматика, 1978, к 2, с.44−53.
- Пшеничный Б.Н. Необходимые условия экстремума. М.: Наука, 1969. — 151 с.
- Пшеничный Б.Н. Алгоритмы для общей задачи математического . программирования. Кибернетика, 1970, и 5, с. 120−125.
- Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М. :1. Наука, 1980. 320 с.
- Пшеничным Б.Н. метод линеаризации. М.: Наука, 1983. -136 с.
- Пшеничный Б.Н., Данилин Ю. М. Численные методы б экстремальных задачах. Ы.: Наука, 1975. — 319 с.
- Пшеничный Б.Н., Соболенко Л. А. Ускорение сходимости метода линеаризации для задачи условной минимизации. .¿-урн. вычисл. матем. и матем. шизики, 1980, т. 20, з, с. 605 614.
- Разумихин Б.С. метод физического моделирования в математическом программировании и экономике. Метод итеративной декомпозиции и задача о распределении ресурсов. Автоматика и телемеханика, 1972, i: II, с. III-123.
- Cea j»?. Оптимизация. Теория и алгоритмы. ?L: мир, 1973. -244 с.
- Табак Д., Куо Б. Оптимальное управление и математическое программирование. 1/I.: Наука, 1975. — 280 с.
- Тыоарсон Р. Разреженные матрицы. Ы.: ¡-лир, 1977. — 190 с.
- Ульм A.iu. метод штрафных функций в задачах большой размерности. Таллин: Валгус, 1979. — 132 с.
- Умнов А.Е. метод штрафных функций в задачах большой размерности. ¿-урн. вычисл. матем. и матем. физики, 1975, т. 15,6, с. 1399−1411.
- Фаддеев д.К., Фаддеева В. Н. Вычислительные методы линейной алгебры. ы.: Физматгиз, 1960. — 656 с.
- Фаддеева В.Н., Фаддеев д.К. Параллельные вычисления в линейной алгебре. Кибернетика, 1977, б, с. 28−39.
- Фаддеева В.Н., Фаддеев д.К. Параллельные вычисления в линейной алгебре. II. Кибернетика, 1982, 3, с. 18−31.
- Федоренко Р.П. Приближенное решение задач оптимального управления. М.: Hay tea, 1978. — 486 с.
- Федоренко Р.П. Об одном алгоритме решения задач математического программирования. ¿-урн. вычисл. матем. я матем. физики, 1982, т. 22, ^ 6, с. I33I-I343.
- Химмельблау Д. Прикладное нелинейное программирование. -М.: Мир, 1975. 534 с.
- Хыоз Дж., Ыичтоы Дж. Структурный подход к программированию. М.: Мир, 1930. — 276 с.
- Цурков В.й. Декомпозиция в задачах большой размерности. -LI.: Наука, 1981. 352 с.
- Численные методы условной оптимизации / Ред. Ф. Гилл и У. Мюррэй. М.: Мир, 1977. — 290 с.
- Шор Н. З. Применение обобщенного градиентного спуска в блочном программировании. Кибернетика, 1967, 3, с. 5855.
- Шор Н. З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. — 200 с.
- Эннусте Ю.А. Проблемы декомпозиционного анализа для задач оптимального планирования. Экономика и матем. методы, 1972, т. ХШ, в. 4, с. 534−545.
- С&анЦ L. Fait pawllzt matoC% шъсtbiovi aCcjO’uUiyYia. 61A M JcmaX ovi Computed, 19% 9 5,, p .6-GSLd.
- Ъаni^Xcj B. Vavi?? fyke. R.Wl. иррелoaiadCuo teckracj-ue*>. J. Computed fybte-Yu. ?ti., i, p. <�нз-??б
- S-. В., l/i/об^е P.tootupotCiCon. pttuctpfeot (meat ргодъаилб. Орел. Re&.? <3G0, v. 8, p.
- Pease M.O. ШснЫх Cvitttiiovi patailti p^coceuo^ . «Jou-ttactC of Uajl Л б К, <36%, 1. A4, Ы-к, р. .
- Реабе Wl.CI.
- ЪакЖыь J.? non&n.ea't otzooMpCLitcon pt/nccp^. Operait.'oui Resea-tcit 9 6 5v v. 43, /V2? , p. A66 1.92. ?efeme iOecmitafrfcerf opfcmc-Vaton 6? f 0114 miento im ecieci zy&tz-wi. IEEE Utctn*. uhtuub
- Ukeo^ 7, v. С T-4.0,, p. tfi-M*93. ??foctw-an „J. Ptcu/tae deoompoiotcOH maUitmecUtCLI рьодъамб ълсоиъа. aiioccKUovi. Орел. R**., , v. /V* 4, p. 5fr- 33.
- Jocfctf 6ou/? k? fi. MtMctufcat
- Witliciviub Cl.C. CL Jtea“?*we.nf -ЬгауцрогЬсх.-biovi p’го e it ut Bu dtwiMpoubCoiA. — STA M он Яррб. l/lActf/U .7, v. ?0, /V-4, p. 35»
- Кирик Е.й. Декомпозиция одной блочной задачи квадратичного программирования со слабо связанными блоками. Киев, 1982. — 22 с. — Рукопись представлена Ученым советом Ин-та кибернетики им. В.и.Глуткова АН УССР. Деп. в ВИНИТИ 7 июля 1982 г., 3554−32.
- Пшеничный Б.Н., Кирик Е. Е. Декомпозиционный алгоритм для задачи квадратичного программирования специальной структуры. Киев, 1982. — 26 с. /Препринт / Ин-т кибернетики АН УССР: 82−40/.
- Кирик Е.Е. О решении задач нелинейного программирования с разделяющимися переменными. Кибернетика, 1933, 2, с. ПЗ-П4.