Методы оптимизации, их место в теории исследования операций
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ
А.Ю.Щеглов
МЕТОДЫ ОПТИМИЗАЦИИ
Конспект лекций
Санкт-Петербург
Методы оптимизации, их место в теории исследования операций.
Метод оптимизации как дисциплина, представляет собой раздел теории исследования операций, задачей которой является поиск в рамках принятой модели решений, отвечающих экстремальным значениям критерия.
Операцией называется совокупность взаимосогласованных действий направленных на достижение определенной цели. До тех пор, пока цель не определена, нет смысла говорить об операции. Если же цель определена, как правило, есть несколько путей ее достижения, среди которых необходимо найти лучший. Понятие лучший что-либо означает, когда определен показатель или критерий качества выбираемых решений.
Любую операцию можно охарактеризовать следующими составляющими:
- Стратегией (вариант решения) называется допустимый или возможный способ достижения цели.
- Действующими факторами операции называются объективные условия, определяющие ее особенности и влияющие на ее исход.
- Критерием эффективности операции или стратегии называется показатель достигнутого соответствия между полученным результатом и целью операции.
- Состоянием операции в некоторый момент времени называют совокупность ее характеристик проявляющихся в данный момент.
Под параметром стратегии понимается локальное качество операции, обусловливаемое его действующими факторами и учитываемое критерием эффективности стратегии.
Под моделированием параметров (или соответственно моделированием системы) понимается определение зависимостей изменения локальных качеств (или критериев оптимальности) с учетом действующих факторов операции.
Математической моделью операции называются формальные соотношения, устанавливающие связь принятого критерия эффективности с действующими факторами операции.
Решением (ограниченным множеством решений) связанным с выбранной математической моделью называется конкретный набор значений параметров полученных в результате использования этой математической модели.
Схематично этапы исследования операций можно представить следующим образом:
| Содержание этапов | этапы |
| Формулировка цели операции, обоснованный выбор критерия эффективности | |
| Анализ системы с целью: 1. выбор исходного множества стратегий. 2. обоснованный выбор множеством исходных параметров, описывающих стратегию с учетом сформулированной цели операции. | |
| При необходимости моделировании параметров стратегии (построение математической модели параметров) | |
| Построение математической модели операции – получение формальной зависимости, изменения критерия качества от изменения параметров системы. | |
| Получение решения – выбор оптимального набора параметров (соответственно оптимальной стратегии с учетом сформулированной цели операции). |
Место методов оптимизации в общей теории исследования операций – оптимальным образом решение формализованной задачи. Методы оптимизации используются на 4-5, при необходимости на 3.
Системой называется упорядоченная совокупность материальных объектов (элементов) объединенных какими-либо связями (напр. механич, электрич и т.д.) предназначенных для достижения определенной цели.
Если исходить из понятия, что поведение системы есть последовательный ряд операций, то системы можно классифицировать следующим образом:
|
Детерминированной считается такая система, в которой составные части взаимодействуют друг с другом точно предсказуемым образом. Ее поведение предсказуемо, если известно текущее состояние элементов и законы преобразования циркулирующие между ними.
Вероятностной называют систему, возможное поведение которой и его последствия описываются на языке теории вероятности, здесь знание текущего состояния и особенности взаимной связи элементов не достаточно для однозначного предсказания будущего, что обуславливает необходимость вероятностной оценки.
Игровой является система, осуществляющая разумный выбор своего поведения в будущем. В основе выбора лежат неформальные соображения, руководствоваться которыми может лишь человек.
Другим важным классификационным признаком системы является ее степень сложности. По этому признаку их разделяют на:
- простые состояния, которые не многочисленны и легко поддаются описанию.
- сложные отличающиеся разнообразием внутренних связей, но допускающие их описание.
- крупномасштабные, не поддающиеся какому-либо описанию связей.
Важное место в исследованиях различного характера является структура системы, и возможность ее расчленяемости на подсистемы, каждая из которых может иметь свой критерий эффективности.
Принцип расчленяемости системынаходится, в основе так называемого системного подхода состоящего в том, что задачу оптимизации можно упростить, сформулировав и решив ее для отдельных подсистем с учетом того, в какой мере критерий эффективности подсистемы влияет на критерий эффективности системы в целом.
Эвристика оказывается полезной и независимой при решении задач имеющих не числовую природу или характеризуемых сложностью определения каких-нибудь параметров либо их формализованного сравнения.
Методы оптимизации классифицируются по числу критериев оптимальности. Их подразделяют на однокритериальные либо многокритериальные. В последнем случае при выборе оптимального решения необходимо учитывать уже не один критерий, а их совокупность, как правило, характеризуемых разнородными параметрами, что усложняет их сравнительную оценку. Здесь, как правило, не обойтись без эвристики.