Введение к работе
Актуальность темы диссертации.
В диссертационной работе изучаются задачи сепарабельного гео-рического программирования (ГП) и специальные задачи о наимень-квадратах. Существует большое число приложений, в которых математические ели формулируются в терминах задач ГП и задач о наименьших квад-ах. Основными областями применения алгоритмов (и программ) ГП яются: задачи управления народным хозяйством, планирование техно-ических процессов производства, капиталовложений в технологии с «одическим циклом управления запасами, задачи инженерного проек-ования, гражданского строительства, судового проектирования. Сре-задач, решаемых при помощи ГП можно назвать также проектирование рных реакторов, установок для опреснения морской воды, производ-а кислорода и т.д. В Беларуси разработанные на основе нового под-;а к решению задач линейного программирования ) алгоритмы решения ;а позиномных подзадач ГП применялись в программном комплексе оик" для автоматизированного проектирования оптимальных по сто-істи материалов и расходу арматуры перекрестных железобетонных гок. В ИТК АН Беларуси разработан пакет программ для решения задач іиномного ГП (ПП "Позином"), возникающих при решении оптимизацион-: проектных задач.
На протяжении последних десятилетий квадратичное программирова-і (КП) наряду с линейным программированием является одним из самых г/лярных разделов современного математического программирования, .ойчивый интерес исследователей к КП обусловлен несколькими факто-щ, среди которых в первую очередь следует отметить многочисленные юстоятельные приложения моделей КП в технике и экономике. Важной іастью применения методов КП являются общие алгоритмы нелинейного >граммирования и оптимального управления. Сильный импульс развитию
Р.Габасов, Ф.М.Кириллова. Методы линейного программирования, 4.1-3. Изд-во БГУ, Минск, 1977,.1978, 1980.
методов КІІ дали исследования по методам решения сложных оптимизаи онных задач, в которых квадратичная задача исследуется как вспомог тельная и решается для определения подходящего направления. В час ности, задача о наименьших квадратах иногда возникает как час некоторой более обширной вычислительной проблемы. Почти каждая опт мизационкая задача требует применения того или иного метода прибд жения и чаще всего в качестве аппроксимаций выбирают задачи о на меньших квадратах.
Несмотря на интенсивные исследования нелинейных задач, ну» признать, что эффективные алгоритмы для решения отдельных задач создания программного обеспечения для них все еще далеки от завери ния. Одним из факторов повышения эффективности численных методов нелинейном программировании, как и в других разделах оптимизац> является дополнительный учет специфики решаемой задачи. За счет j ложнения логической структуры общего метода часто удается снизі его трудоемкость и требования, предъявляемые к объему памяти и мс ности вычислительной техники при решении специальных классов зaдa^
2. Связь работы с крупными научными программами, темами.
Диссертационная работа выполнялась по темам важнейших научно-исследовательских работ в области естественных наук отдела теории процессов управления Института математики АН Беларуси:
"Математические методы и программное обеспечение нелинейные экстремальных задач" No 0187.0027644 (Постановление Президиума АН БССР No 155 от 25.12.86);
"Методы решения негладких экстремальных задач и их приложения" (Постановление Президиума АН Беларуси No 147 от 06.12.88).
3. Цель и задачи исследования
Целью работы является разработка конструктивных методов решеї специальных задач ГП и КП. В задачи исследования входило:
построение прямого, двойственного и комбинированного методо: последовательных аппроксимаций для решения безусловных задач ГП;
построение прямо-дзойсгаенных методов решения безусловных задач о наименьших квадратах;
построение прямо-двойственных методов для решения задач о наименьших квадратах с простыми ограничениями на переменные;
построение прямого, двойственного и комбинированного методов ї решения сепарабельных задач ГП с простыми ограничениями;
программная реализация разработанных методов и проведение зпериментов.
Научная новизна полученных результатов.
В диссертационной работе разработаны прямые, двойственные и лбинированные методы последовательной аппроксимации для решения зусловной задачи ГП и задачи ГП с простыми ограничениями. В повоєнних методах впервые используется принцип накопления аппрокси-эующих функций, который отличается появлением на очередной итера-i дополнительной составляющей аппроксимирующей функции.
Метод последовательной аппроксимации и его модификации, разра-ганные автором, впервые применены для построения прямых и двойст-шых методов решения условных и безусловных задач о наименьших ідратах. Разработаны конструкции прямо-двойственных алгоритмов для гавременного эффективного решения прямой и двойственной задач о шеньших квадратах.
Предложенные методы являются точными, релаксационными, сходящи-гя к оптимальному решению. Для всех задач доказаны критерии опти-іьности и разработаны вычислительные процедуры, позволяющие легко /ществить программную реализацию методов. В частности, в работе инфицирован метод накопления оптимальных признаков для решения дачи КП с одним ограничением-равенством, метод обратной кубической троксимаций для решения нелинейных уравнений на отрезке, метод тиномиальной аппроксимации для решения систем нелинейных уравне-І, а также некоторые другие специальные вычислительные алгоритмы т применялись для решения основных задач диссертации).
Практическая значимость полученных результатов
Как было показано ранее, рассмотренные в диссертационной работе іачи являются математическими моделями ряда практических проблем інятия решений в конкретных социально-экономических, технических и ^гих системах. Так как все методы, разработанные для решения этих дач, являются новыми, го они представляют интерес для создания зграммного обеспечения задач ГП и задач о наименьших квадратах и следующей работы в этой области.
Предложенный в работе принцип накопления аппроксимирующих 4 ций и основанный на нем подход к выбору подходящего направления гут быть применены и к другим задачам выпуклого сепарабельного граммирования. Описанные конструкции комбинированных (прямо - р ственных) алгоритмов позволяют эффективно решать как прямые, тан двойственные задачи такого типа.
6. Экономическая значимость полученных результатов
Результаты диссертационной работы могут быть применены при ектировании строительных конструкций, но оценить экономическую фективность результатов диссертационной работы в настоящее время представляется возможным.
7. Основные положения диссертации, выносимые на защиту-
На защиту выносятся следующие результаты:
разработка прямого, двойственного, и комбинированного методо решения безусловных задач ГП;
построение прямого и двойственного алгоритмов решения безус ной задачи о наименьших квадратах и разработка прямо-двойстве конструкций для решения прямой и двойственной задач ' о' каимен квадратах;
построение алгоритмов решения, задач о наименьших квадратах простыми ограничениями на переменные;
разработка прямо-двойственных методов решения задач ГП с пр тыми ограничениями на переменные.
8. Личный вклад соискателя
Основные результаты диссертации получены лично автором. В і местных работах по ГП [і, 2] автору диссертации принадлежит ра1 ботка принципа накопления аппроксимирующих функций на итерациях і мого и двойственного методов, а также- разработка процедур поі шага, методов решения нелинейных уравнений и систем нелинейных у] нений специального вида. В [з] автором.доказаны критерии оптим: ности для прямой и двойственной задач ГП с простыми ограничени: на переменные и разработаны прямой и двойственный методы реші этих задач; доказана сходимость предложенных методов.
Апробация результатов диссертации.
По теме диссертации сделаны доклады на Международной конферен-DGOR, GMOOR и OGOR "Symposium on Operation Research" (SOR'95) ilaccay, Германия, 1995), Международной математической конферен-, досвященной 25 -летию Гомельского госуниверситета (г.Гомель, 4), VIII Всесоюзной конференции "Проблемы теоретической киберне-и" (г.Горький, 1988), Межгосударственной научной конференции намические системы: устойчивость, управление, оптимизация" Минск, 1993), научных чтениях "Динамические системы: устойчи-ть, управление, оптимизация" (г.Минск, 1990).
Результаты диссертации неоднократно обсуждалсь на объединенном
инаре по конструктивным методам оптимизации кафедры методов опти-
ьного управления Белгосуниверситета и отдела теории процессов
авления Института математики АН Беларуси (руководители - профес-
Р.Габасов, профессор Ф.М.Кириллова).
Опубликованность результатов.
Результаты диссертации опубликованы в 4 статьях и в 5 тезисах чных конференций.
Структура и объем диссертации.
Диссертация состоит из введения, общей характеристики работы и
ырех глав, а также приложений. Объем диссертации - 100 страниц,
ем списка использованных источников (112 наименований ) - 8 стра-
;, объем приложений — 15 страниц.