РАЗРАБОТКА И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ВОГНУТОГО ПРОГРАММИРОВАНИЯ НА ОСНОВЕ ДОБАВЛЕНИЯ ОГРАНИЧЕНИЙ К ДОПУСТИМОМУ МНОЖЕСТВУ

Введение 3
Постановка задачи и алгоритм ее решения 6
Общая схема метода ветвей и границ для задачи вогнутого программирования 9
Постановка задачи и ее программная реализация 11
Алгоритм решения задачи в узле 12
Методы и поля, используемые в программе 20
Эксперименты и выводы 32
Заключение 40
Список литературы
Купить

Как известно, зачастую задачи экономики, физики, экологии, молекулярной биологии и медицины сводятся к задачам невыпуклой глобальной оптимизации. Сложность таких задач заключается в том, что они носят многоэкстремальный характер, т.е. предполагают возможность существования большого числа локальных решений, которые могут быть далеки от глобального [9].
Часто функция стоимости в таких задачах может быть представлена в виде разности двух выпуклых функций [2]. Например, в задаче поиска равновесия по Нэшу в биматричной игре [6]. Также к задачам невыпуклой оптимизации относятся двухуровневые задачи [5], которые возникают во многих областях человеческой деятельности, где появляется необходимость введения процедуры отделения множеств (задача определения кредитоспособности клиента банка, прогнозирование и диагностика в области медицины); задачи линейной дополнительности (задача торможения, задача рыночного равновесия). Кроме того, задачи целочисленного линейного программирования могут быть сведены к задачам невыпуклого программирования.
Ввиду распространенности задач невыпуклой оптимизации разрабатываются алгоритмы и методы их решения.
Рассмотрим основные подходы к решению данных задач:
1. Методы, основанные на разбиении допустимого множества [7]. При данном походе множество допустимых решений разбивается на подмножества, которые при объединении образуют исходное множество. Далее решается исходная задача, но уже на каждом из полученных подмножеств, и затем сравниваются результаты, и выбирается наилучший. Так, множество решений сужается для каждой подзадачи, однако стоит отметить, что растет количество задач.
2. Методы отсекающих плоскостей. Данные методы являются основой для создания точных и приближенных алгоритмов решения задач целочисленного программирования [3]. На каждой новой итерации сужается множество допустимых решений путем отсечения некоторой его части, тем самым уменьшая окрестность оптимального решения. И на полученном множестве отыскивается решение исходной задачи. К достоинствам таких методов можно отнести то, что они не требуют неопределенного размера оперативной памяти для хранения дерева решений, однако при каждом отсечении плоскости увеличивается множество ограничений, кроме того, при приближении к решению отсекающие плоскости начинают практически совпадать, что затрудняет решение задачи.
3. Сеточный метод. Сегодня данный подход широко применяется на практике. На множество допустимых решений накладывается сетка, имеющая различную плотность, которая зависит от предположений о положении глобального оптимума на допустимом множестве. В каждом узле рассчитывается значение целевой функции. Полученные значения сравниваются между собой, и определяется наилучшее из них. Это дает возможность отыскания решения задачи наиболее близкого к точному.
4. Метод ветвей и границ. Метод применяется для отыскания глобального решения задачи. На начальном этапе определяется верхняя и нижняя оценки исходной задачи, если они равны, то метод прекращает работу. В противном случае множество переменных разбивается на несколько подмножеств, объединение которых совпадает с исходным множеством. Данные подмножества образуют дерево подзадач, на которых рекурсивно применяется исходный метод. Алгоритм продолжает работу до тех пор, пока не будет найдено решение задачи. Данный метод является одним из наиболее надежных при решении задач, к его недостаткам можно отнести необходимость полностью решать задачи в узлах дерева, что при достаточно большой размерности задачи требует значительных затрат времени [3].
Для повышения эффективности современные алгоритмы часто являются комбинацией вышеизложенных методов решения задач оптимизации, кроме того в некоторых применяются параллельные вычисления [7].
Купить