Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
07.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
915 Кб
Скачать
☆

Дискретная и целочисленная оптимизация

Особый класс составляют задачи оптимизации, в которых все или некоторые переменные принимают значения из дискретного ряда X{X1, …, XN}. Как правило, методы, разработанные для решения задач непрерывной оптимизации неприменимы в дискретной оптимизации. Целочисленные задачи математического программирования содержат требования целочисленности, налагаемые на часть переменных: Xi  Z, i = 1, …, N. Такие переменные могут обозначать количества элементов (число фрагментов разного типа в фракциях, их распределение в зонах разлета). При небольших N может оказаться приемлемым простой перебор вариантов, в множествах вариантов комбинаторной мощности целесообразно сочетать перебор вариантов с исключением заведомо неперспективных решений. Эта идея реализуется методами ветвей и границ: множество допустимых значений разбивают на непересекающиеся подмножества (ветвление), в которых оценивают нижние границы целевой функции. Можно существенно сократить количество анализируемых вариантов, отбирая их по формальному признаку, которому должно удовлетворять оптимальное решение. Выявление такого признака – принципа оптимальности – по математическим свойствам целевой функции требует глубокого понимания задачи и известных способов решения.

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

По структурным признакам различаются задачи безусловной и условной оптимизации по скалярным и векторным критериям. Структурные различия существенным образом определяют степень сложности задач.

Безусловная оптимизация

При отсутствии ограничений на возможные значения переменных оптимизации решением задачи является значение скалярной или векторной переменной X, доставляющее максимальное (max) или минимальное (min) значение скалярной функции W(X) на всем пространстве En:

. (1)

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

Условная оптимизация

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

min W(X)

Fk(X)  Fkтр, k =1, …, m,

ai x i bi, i=1, …, n,

где символ '' в функциональных ограничениях обозначает знак строгого или нестрогого неравенства, или знак равенства. Наличие ограничений сильно усложняет процесс поиска условного экстремума. Мощный класс методов условной оптимизации – методы возможных направлений – реализуют сложные коммерческие программные продукты. Методы штрафных и барьерных функций позволяют приводить задачу к виду (1) и использовать для решения задач с ограничениями методы безусловной оптимизации.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]