Исследование_операций

Лекция 1

Введение

Операцией называется любая система действий, которая связана единым замыслом, направлена на достижение определенной цели и требует выбора того или иного решения. Исследование операций иногда называется теорией принятия решения, поскольку главное в операции – это выбрать решение.

Исследование операций – это теория, изучающая математические методы и модели, решения задач, связанные с принятием решений в той или иной ситуации.

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

2. Математического программирования.
3. Теории управления или кибернетика.
4. Теория игр.
5. Теория оптимизации.
6. Теория систем массового обслуживания.
7. Статистическая теория принятия решений (игры с природой).

 

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

1. Если выбирать решения приходится в процессе противодействия, то есть существует как бы противник, который мешает. Такие задачи относятся к теории игр.
2. Это принятие решения в условиях неопределенности, то есть когда нет полной информации о возможных решениях. Здесь необходим вероятностный подход и теории статистического принятия решений (игры с природой).
3. Выбирать наилучшее решение нужно не только с учетом текущего момента, но и с прогнозом на будущее. В такой ситуации используют прогностическое моделирование.
4. Решение часто приходится принимать в автоматическом режиме, пытаясь поддержать некое состояние равновесия. Для решения подобных задач разработаны методы кибернетики и теории автоматического управления.

В каждом из этих вариантов  существует множество подзадач, которые  мы будем рассматривать при изучении того или иного раздела.

Основы теории оптимизации

Постановка задачи оптимизации «Дана некая функция f(x₁,x₂,…,x_n) эта функция называется целевой. Необходимо найти либо максимум, либо минимум». Эти задачи легко преобразовать друг к другу. Кроме целевой функции вводятся некие ограничения: g_i(x₁,x₂,…,x_n)³0  p_i(x₁,x₂,…,x_n)=0 ограничения могут быть в виде неравенств, и в виде равенств. Это и есть задача оптимизации. Задачи делятся на параметрические и многопараметрические (многомерные). Суть задачи подобрать параметры, которые соответствуют максимуму или минимуму. Могут существовать несколько критерий одновременно.

Обычно критерии не могут быть совершенно не связанные друг с другом, их можно  связать между собой. Таким образом, в случае многокритериальной  оптимизации обычно стараются создать однокритериальный. В дальнейшем будем считать, что у нас однокритериальная задача.

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

1. Если целевая функция линейная и ограничения тоже линейные, то такая задача называется задачей линейного программирования. Задачи ЛП изучены хорошо, поэтому существует метод линеаризации – это преобразование задач нелинейных в линейные.
2. Если целевая функция представляется квадратичной формой, то задача называется задачей квадратичного программирования. Линейная задача тоже может свестись к квадратичной, поскольку решить квадратичное легче.

В настоящее время продолжает развиваться  теория кубического программирования. Она еще до конца не разработана.

3. Если ограничения на целевую функцию отсутствует или является (ограничения только на переменную), то такая задача называется задачей безусловной оптимизации.
4. Если функция нелинейная и существует ограничения (сложные), то  задача относится к нелинейной оптимизации.
5. Если в задачи существуют параметры, зависящие от времени и они существенно влияют на решения, то каждый момент времени решения разное и оптимальное решение представляет из себя функцию, зависящую от эволюции. Методы решения в данном варианте относятся к теории методом динамического программирования.

Задача линейного программирования

Целевая функция может  быть представлена как сумма этих величин

Ограничения могут быть представлены в виде

     (ограничения в виде равенств)  (ограничения в виде неравенств)

Совокупность х_i называется вектором неизвестных и решение ищется как значение этого вектора неизвестных, при котором функция f обладает максимум или минимум. Коэффициент также образует вектор, который называется вектором ресурсов. Принято всегда приводить задачу к специальному стандартному виду.

Требования к стандартному виду задачи ЛП:

1. Параметры х_i должны быть больше или равны нулю (х_i³0). Если есть такое ограничение, которое допускает отрицательное значение х_i, то делают замену переменных так, чтобы новое х_i не было отрицательным.
2. Ограничения в виде неравенств преобразуются в ограничения в виде равенств.
3. Элементы, стоящие справа должны быть неотрицательными в равенствах, то есть b_i³0.