ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ (ИСО). Исследование операций – это комплексная математическая дисциплина, занимающаяся построением, анализом и применением. - презентация

1 ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ (ИСО). Исследование операций – это комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений при проведении операций. Операция – система управляемых действий, объединенная единым замыслом и направленная на достижение определенной цели Цель ИСО количественно и качественно обосновать принимаемое решение. Окончательное решение принимает ответственное лицо (либо группа лиц), называемое лицо, принимающее решение (ЛПР). Математическая модель задачи ИСО составляется в соответствии с представлениями ЛПР об этой задаче, т.e. в соответствии с его информационным состоянием. При этом важно, чтобы математическая модель задачи была наиболее адекватной, т.e. наиболее правильно отражала информационное состояние ЛПР. Для этого разработчик математической модели должен работать в тесном контакте с ЛПР.

2 Примеры операций: Пример 1. Предприятие выпускает несколько видов изделий, при изготовлении которых используются ограниченные ресурсы различного типа. Требуется составить план выпуска изделий на месяц, т.е. указать количество выпускаемых изделий каждою вида, так, чтобы максимизировать прибыль при выполнении ограничений на потребляемые ресурсы. Пример 2. Требуется создать сеть временных торговых точек так, чтобы обеспечивать максимальную эффективность продаж. Для этого требуется определить - число точек, - их размещение, - количество персонала и их зарплату, - цены на товары. Пример 3. Требуется организовать строительство магазина. При этом необходимо указать порядок выполнения работ во времени и распределить требуемые ресурсы между работами так, чтобы завершить строительство вовремя и минимизировать его стоимость.

3 Набор управляющих параметров (переменных) при проведении операции называется решением. Решение называется допустимым, если оно удовлетворяет набору определенных условий. Решение называется оптимальным, если оно допустимо и, по определенным признакам, предпочтительнее других, или, по крайней мере, не хуже. Признак предпочтения называется критерием оптимальности. Критерий оптимальности включает в себя целевую функцию и направление оптимизации или набор целевых функций и соответствующих направлений оптимизации. Целевая функция – это количественный показатель предпочтительности или эффективности решений. Направление оптимизации – это максимум (минимум), если наиболее предпочтительным является наибольшее (наименьшее) значение целевой функции. Например, критерием может быть максимизация прибыли либо минимизация расходов. Математическая модель задачи ИСО включает в себя: 1)описание переменных, которые необходимо найти 2) описание критериев оптимальности 3) описание множества допустимых решений (ограничений, накладываемых на переменные).

4 Классификация задач ИСО Классификация по зависимости параметров задачи от времени. 1. Статическая задача. Принятие решения происходит при условии, что все параметры задачи заранее известны и не изменяются но времени. Процедура принятия решения осуществляется один раз. 2. Динамическая задача. В процессе принятия решения параметры задачи изменяются по времени. Процедура принятия решения осуществляется поэтапно и может быть представлена и виде процесса, зависящего от времени, в том числе непрерывно. Пример – навигационная задача. Классификация в зависимости от достоверности информации о задаче. 1. Детерминированная задача. Все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются методы математического программирования. 2. Недетерминированная задача. Не все параметры задачи заранее известны. Например, необходимо принять решение об управлении устройством, некоторые узлы которого могут непредсказуемо выходить из строя. Оптимальное решение недетерминированной задачи ИСО отыскать практически невозможно. Однако некоторое "разумное" решение отыскать можно

5 Классификация по виду критерия оптимальности. Критерий оптимальности может иметь любой вид, в том числе неформализуемый. Наиболее распространенные формализуемые критерии оптимальности заключаются в оптимизации (минимизации либо максимизации) одной либо нескольких скалярных целевых функций. Функция называется скалярной, если ее значением является некоторое число. Задача оптимизации скалярной функции на заданном множестве допустимых числовых решений называется задачей математического программирования. Наиболее изученными представителями однокритериальных задач математического программирования, т.е. задач с одной целевой функцией, являются следующие задачи. Задачи линейного программирования. Целевая функция линейная, множество допустимых решений – выпуклый многогранник. Задачи квадратичного программирования. Целевая – функция квадратичная, а множество допустимых решений – выпуклый многогранник. Задачи стохастического программирования. Это задачи линейного программирования с неизвестными числовыми параметрами, о которых имеются статистические данные. Задачи дискретного программирования. Множество допустимых решений – дискретное множество. Задачи целочисленного программирования. Множество допустимых решений – точки целочисленной решетки. Задачи булева программирования. Множество допустимых решений – 0-1 матрицы.

6 Математический инструментарий исследования операций Рассмотрим некоторые математические дисциплины, наиболее часто используемые при решении задач исследования операций. Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования широко используются для решения распределительных задач. Линейное программирование (ЛП) – является наиболее простым и лучше всего изученным разделом математического программирования. В нем рассматриваются задачи, у которых показатель оптимальности представляет собой линейную функцию от переменных задачи, а ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств. Соответственно нелинейное программирование рассматривает задачи с нелинейными целевыми функциями и ограничениями. Задачи, решаемые с помощью сетевого моделирования (теория графов), могут быть сформулированы и решены методами линейного программирования, но специальные сетевые алгоритмы позволяют решать их более эффективно. Примеры: задачи нахождения кратчайшего пути, критического пути, максимального потока, минимизации стоимости потока в сети с ограниченной пропускной способностью и др.

7 Целевое программирование представляет собой методы решения задач линейного программирования с несколькими целевыми функциями, которые могут конфликтовать друг с другом. Целочисленное линейное программирование используется для решения задач, у которых все или некоторые переменные должны принимать целочисленные значения. Динамическое программирование предполагает разбиение задачи на несколько этапов, каждый из которых представляет собой подзадачу относительно одной переменной и решается отдельно от других подзадач. Аппарат теории вероятностей используется во многих задачах исследования операций, например, для прогнозирования (регрессионный и корреляционный анализ), вероятностного управления запасами, моделирования систем массового обслуживания, имитационного моделирования и др. Методы моделирования и прогнозирования временных рядов позволяют выявить тенденции изменения фактических значений параметра Y во времени и прогнозировать будущие значения Y. Теория игр и принятия решений рассматривает процессы выбора наилучшей из нескольких альтернатив в ситуациях определенности (данные известны точно), в условиях риска (данные можно описать с помощью вероятностных распределений), в условиях неопределенности (вероятностное распределение либо неизвестно, либо не может быть определено). Методы и модели теории нечетких множеств позволяют в математической форме представить и использовать для принятия решений субъективную словесную экспертную информацию: предпочтения, правила, оценки значений количественных и качественных показателей.

8 Под операциями обычно понимают целенаправленные управляемые процессы Под исследованием операций понимается применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности

9

10