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

Введение к работе

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

1. Развитие и модификация уже разработанных методов и алгоритмов.

2. Создание новых алгоритмов и направлений.

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

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

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

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

а), имеет место выпуклость (в ограниченном и часто нетрадиционном смысле);

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

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

1). максимизация выпуклых функций при линейных или выпуклых ограничениях (выпуклая максимизация);

2). выпуклая минимизация на пересечении выпуклых и вогнутых множеств (выпукло- вогнутое пограммирование);

3). глобальная оптимизация функций, представимых в виде разности двух выпуклых функций (d.c. - программирование).

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

Цель работы. Исследование свойств функции, имеющих единственные решения, редукции общих задач математического программирования к выпукло- вогнутым задачам, модификация метода отсечения в Е^п, и ее связь с другими задачами математического программирования.

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

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

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

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

исследован класс полных квадратичных задач с неопределенной квадратичной матрицей квадратичных форм,

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

предложена модификация метода отсечения в 2?",

- Исследована связь модификации с задачами целочисленного,
частично- целочисленного, сепарабельного программировании и с за
дачей с фиксированными затратами,

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

Апробация работы. Результаты работы докладывались на конференции "Методы оптимизации и их приложения"(Иркутск, 1992), на научных семинарах ИМ АН МНР и СЭИ.

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