close

Вход

Забыли?

вход по аккаунту

?

USLGRAD

код для вставкиСкачать
Метод условного градиента
Разработчик
Дуплик С.В.,
1998г.
1. Постановка задачи.
Дана выпуклая функция , непрерывно дифференцируемая, выпуклая на некотором выпуклом, замкнутом, ограниченном множестве , которое задается системой ограничений:
. . .
Ограничения в общем случае могут быть как линейными, так и нелинейными.
Найти .
Обозначим . Тогда постановка задачи запишется в виде:
найти , где .
2. Описание метода.
В методе условного градиента строится итерационный процесс, на каждом шаге которого решаются две вспомогательные задачи: минимизация на множестве U линейной функции и одномерная задача минимизации.
Пусть - очередное приближение к решению задачи. Тогда в окрестности точки функция f(X) представима в виде:
,
и линейная функция
(1)
является приближением f(X) с точностью до величины в окрестности точки .
Поставим вспомогательную задачу минимизации этой линейной функции на множестве U: найти . (2)
Пусть - решение этой задачи. Так как множество U замкнуто и ограниченно, а линейная функция непрерывна, то точка всегда существует, а так как U выпукло, то . Если достигает минимума на U более, чем в 1 точке, то в качествевозьмем любую из них.
В общем случае задача (2) является задачей нелинейного программирования. Укажем случаи, когда нахождение точки возможно напрямую.
1) Множество U задано линейными ограничениями. Тогда задача (2) представляет из себя задачу линейного программирования, и ее решение можно найти с помощью симплекс-метода.
2) Множество U представляет собой n-мерный параллелепипед:
Тогда:
, если , если (4)
, если 3) Множество U - шар радиуса R с центром в точке :
.
Тогда . (5)
4) Множество U задано любыми ограничениями (как линейными, так и нелинейными). В этом случае имеем задачу выпуклого программирования, для решения которой использован метод отсекающих плоскостей Келли.
Этот метод заключается в следующем: заключим область U в некоторый выпуклый многогранник (см. рис. 1). Таким образом задача нелинейного программирования сводится к задаче линейного программирования, которая описана в пункте 1. Находя решение полученной задачи линейного программирования (пусть это будет точка X*), отсекаем его специально построенным алгоритмом, получая новый многогранник. Решаем задачу линейного программирования с исходной целевой функцией для полученного многогранника (получаем точку X**) и т.д. Последовательность оптимальных решений задач линейного программирования сходится к решению исходной задачи нелинейного программирования.
Рис. 1
Формально это выглядит следующим образом:
1) Выбираются произвольно точки , l - произвольное число большее или равное 1. В каждой из этих точек строятся касательные плоскости к каждому из нелинейных ограничений по формулам:
, i=1,2, ... ,m; j=1,2, ... ,l.
Количество таких ограничений равно .
2) Решается задача линейного программирования для полученных ограничений и линейной функции (1). Пусть - решение этой задачи.
Если , то - решение исходной задачи нелинейного программирования.
3) Строится множество .
4) К имеющимся уже ограничениям добавляются новые ограничения вида:
,
отсекающие точку .
5) Осуществляется возврат к шагу 2.
Здесь получается точное решение вспомогательной задачи. Но в общем случае получается приближенное решение вида:
, (6)
где , .
Пусть найдена. Следующее (k+1)-е приближение находится по формуле:
, (7)
где .
Так как множество U выпукло, то .
Величина шага находится как решение задачи одномерной оптимизации на отрезке [0,1] второй вспомогательной функции:
, где (8)
.
Точное определение возможно не всегда. Поэтому вместо (8) можно определить из условия:
, , . (9)
Условие окончания вычислений: , или , или .
3. Алгоритм вычислений по методу условного градиента.
1) Задать исходные данные:
а) коэффициенты целевой функции
б) количество, типы (линейное, нелинейное) и коэффициенты функций-ограничений
в) начальную точку
г) точность вычислений.
2) Найти вспомогательную точку (непосредственно или решением вспомогательной задачи линейного или нелинейного программирования).
3) Вычислить величину шага решением задачи одномерной оптимизации.
4) Найти следующую точку по формуле (3).
5) Проверить условие достижения заданной точности. Если оно выполняется, то найденная точка является решением задачи. Иначе перейти к шагу 2.
4. Руководство пользователя.
Программа состоит из набора окон (форм).
После запуска программы на экране появляется главное окно (см. рис. 2).
Рис. 2
Данное окно предназначено для ввода коэффициентов целевой функции и выбора типа задачи. Для перехода к следующему окну нужно нажать кнопку "Следующий". При этом происходит проверка введенных данных и переход к следующему окну в зависимости от указанного типа задачи.
Для выхода из программы нажать кнопку "Выход".
При выборе задачи с ограничениями на значения переменных появляется окно, представленное на рис. 3.
Рис. 3
Это окно предназначено для ввода нижней и верхней границы значений переменных x1 и x2. После ввода для перехода к следующему окну нажать кнопку "Следующий". Для возврата к предыдущему окну нажать кнопку "Предыдущий".
При выборе задачи с линейными ограничениями появляется окно, представленное на рис. 4.
Рис. 4
Это окно предназначено для ввода количества и коэффициентов линейных ограничений, вид которых указан внизу окна. После ввода для перехода к следующему окну нажать кнопку "Следующий". Для возврата к предыдущему окну нажать кнопку "Предыдущий".
Максимальное число ограничений - 10.
Примечание. Уравнения вида "больше или равно" перед вводом свести к "меньше или равно".
При выборе задачи с нелинейным ограничением типа окружности появляется окно, представленное на рис. 5.
Рис. 5
Это окно предназначено для ввода координат центра и радиуса окружности. После ввода для перехода к следующему окну нажать кнопку "Следующий". Для возврата к предыдущему окну нажать кнопку "Предыдущий".
При выборе задачи с нелинейным ограничением типа окружности появляется окно, представленное на рис. 6.
Рис. 6
Это окно предназначено для ввода количества и коэффициентов линейных и нелинейных ограничений.
Для задания типов ограничений служат переключатели в нижней части окна. Если ограничение является нелинейным, то соответствующий переключатель необходимо включить (щелкнуть по нему мышью). Повторный щелчок снимает признак нелинейности.
После ввода для перехода к следующему окну нажать кнопку "Следующий". Для возврата к предыдущему окну нажать кнопку "Предыдущий".
Максимальное число ограничений - 10.
Примечания.
1. Уравнения вида "больше или равно" перед вводом свести к "меньше или равно".
2. Проверяется соответствие признака нелинейности (задаваемого переключателем) коэффициентам при нелинейных членах уравнения. Если ограничение линейное (переключатель выключен), а хотя бы один из коэффицентов при нелинейных членах не равен нулю, то выдается сообщение об ошибке.
После ввода ограничений появляется окно с запросом на ввод начальной точки и точности вычислений, представленный на рис. 7
Рис. 7
После ввода данных и перехода к расчетам нажать кнопку "Готово".
Примечание. Если начальная точка не принадлежит допустимой области, задаваемой ограничениями, то выдается сообщение об ошибке.
Далее по введенным данным производится расчет точки минимума и вывод окна с результатами (см. рис. 8).
Рис. 8
В данном окне выведены исходные данные:
* коэффициенты целевой функции,
* начальная точка,
* точность вычислений
и результаты расчета:
* результаты расчета в каждой итерации,
* координаты точки минимума,
* значение целевой функции в этой точке,
* сообщение об окончании вычислений или об ошибке.
Возможны следуюшие сообщения:
СообщениеОписаниеРешение найденоНормальное завершение цикла вычислений.
В окне - правильное значение результатаСлишком много итерацийКоличество итераций превысило максимально допустимое (см. 4.1). Возможно взята слишком большая точность, достижение которой невозможно. Возьмите меньшую точность и повторите расчет.Симплекс-метод. Решения нетВспомогательная задача линейного программирования не имеет решения (возможно ограничения описывают незамкнутую область). Назначения кнопок:
КнопкаОписаниеИзменить ограниченияВ зависимости от типа задачи осуществляется переход к соответствующему окну для ввода ограниченийИзменить параметрыПоявляется окно с запросом на ввод начальной точки и точности вычисленийНовый расчетПоявляется главное окно с запросом на ввод коэффициентов целевой функции и выбор типа задачиВыходВыход из программы Графический модуль
Версия 2.0 программы, реализующей метод условного градиента, представляет собой дополненную версию 1.0. В программу были внесены следующие изменения:
* включен модуль вывода на экран графика решения
* внесены небольшие изменения в метод отсекающих плоскостей Келли
* исправлены некоторые неточности в программе
* добавлены ярлыки оперативной подсказки для кнопок и некоторых редакторов
5. Описание графического модуля
Графический модуль предназначен для вывода на экран графиков уравнений-ограничений, линий уровня целевой функции и хода решения. Окно автоматически максимизируется на весь экран и в дальнейшем не может изменять свои размеры.
Работа с графическим модулем.
Для просмотра графика на форме с результатами расчетов нужно нажать кнопку "График". На экране появится графическое окно (см. рис. 9).
рис. 9
Далее для вывода графика нужно нажать кнопку "Вывести". После просмотра графика можно вернуться к форме с результатами, нажав кнопку "Закрыть" или выйти из программы, нажав кнопку "Выход".
Для увеличения или уменьшения отображаемой области нужно изменить координаты границ области на панели масштабирования, после чего снова нажать кнопку "Вывести". Для возврата к исходным координатам нужно нажать кнопку "Восстановить".
Примечания.
1. Поскольку по обеим осям взят одинаковый масштаб, то изменение координат границы только по одной оси может не привести к увеличению изображения.
2. Добавив одинаковое значение к начальной и конечной координатам границ оси можно сдвинуть изображение по этой оси.
20
2
Документ
Категория
Рефераты
Просмотров
223
Размер файла
4 022 Кб
Теги
uslgrad
1/--страниц
Пожаловаться на содержимое документа