Алгоритмы глобального поиска.
1. Чередование ненаправленного случайного поиска с детерминированными алгоритмами или алгоритмами направленного случайного поиска
2. Чередование направленного случайного поиска или детерминированного алгоритма с алгоритмом ненаправленного случайного поиска.
3. После определение локального минимума продолжение движения до начала нового убывания целевой функции.
4. Чередование ненаправленный случайный поиск с детерминированными алгоритмами или алгоритмами направленного случайного поиска и формированием запретных зон.
Линейное программирование. Симплекс метод.
Отметим некоторые важные положения, связанные с основными задачами линейного программирования.
1. Оптимальное решение задачи, если оно существует, располагается только на границе ОДР (а не внутри области допустимых решений ОДР, поскольку имеется возможность улучшать его вплоть до самых границ).
2. Оно (решение) может быть не единственным (если какая- либо линия ОДР параллельна линии ЦФ— это бесконечное множество оптимальных решений).
3. Задача может не иметь решения. Тогда со стороны изменения ЦФ в направлении стрелок ОДР не ограничена.
4. Решение, минимизирующее (максимизирующее), достигается в одной из вершин многоугольника ОДР.
5. Для нахождения оптимального решения достаточно последовательно перебрать и рассмотреть вершины ОДР и выбрать ту, где минимум.
|
|
|
Идея симплекс-метода как раз и состоит в последовательном улучшении достигаемого результата на основе перехода от одной вершины ОДР к другой (смежной), при сохранении допустимых значений базисных переменных. Каждый такой переход означает одновременно замену одних свободных переменных на другие.
Основная задача линейного программирования.
Задача: Среди допустимых решений системы найти оптимальное ( имеющее минимальное значение F ).
Если ранг матрицы условий r>=n , то существует или единственное решение или решений нет.
Симплекс метод решения задачи линейного программирования.
Пусть r ,m< n .
Динамическое программирование.
Суть динамического программирования заключается в сведении задачи высокой размерности к последовательному решению задач оптимизации меньшей размерности.
Минимизацию целевой функции n переменных из стартовой точки, заданной вектором X0, путем решения многошаговой задачи динамического программирования осуществляется по следующей схеме:
Нелинейное программирование.
Способы решения:
1. Сведение к линейному программированию:
a. дробно-линейное программирование;
b. квадратичное программирование.
|
|
|
2. Методы возможных направлений:
a. линейные ограничения;
b. нелинейные ограничения.
3. Градиентные методы:
a. метод проекции градиента;
b. метод условного градиента.
4. Метод последовательной безусловной оптимизации:
a. Метод штрафных функций;
b. Метод барьерных функций.
Дата добавления: 2019-02-12; просмотров: 238; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!