Основные понятия ИО

Исследование операций Комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений при проведении операций

Операция Система управляемых действий, объединенная единым замыслом и направленная на достижение определенной цели.

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

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

Критерий оптимальности Это признак предпочтения решения. Включает в себя – Целевую функцию (набор целевых функций) – Направление оптимизации (набор направлений оптимизации)

Целевая функция Количественный показатель предпочтительности или эффективности решений.

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

Математическая модель задачи ИО Описание переменных, которые необходимо найти Описание критериев оптимальности Описание множества допустимых решений (ограничений, накладываемых на переменные).

Цель ИО Количественно и качественно обосновать принимаемое решение Окончательное решение принимает ответственное лицо (группа лиц), называемое ЛПР Математическая модель задачи ИО составляется в соответствии с представлениями ЛПР (информационное состояние)

Классификация задач

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

В зависимости от достоверности информации о задаче Детерминированная – Все параметры задачи заранее известны – Методы математического программирования Недетерминированная – Не все параметры задачи заранее известны – Оптимальное решение отыскать практически невозможно

Недетерминированная задача Стохастическая задача – Не все параметры известны – Имеются статистические данные о неизвестных параметрах – Для отыскания оптимального решения используются приемы: Искусственное сведение к детерминированной задаче «оптимизация в среднем» Задача в условиях полной неопределенности – Статистические данные о неизвестных параметрах отсутствуют – Изучаются в рамках теории игр

По виду критерия оптимальности Формализуемые критерии – Задачи линейного программирования – Задачи квадратичного программирования – Задачи стохастического программирования – Задачи дискретного программирования – Задачи целочисленного программирования – Задачи булева программирования Неформализуемые критерии

Многокритериальные задачи Присутствуют несколько признаков предпочтения (критериев) Критерии могут оказаться противоречивыми, т.е. решение, лучшее по определенному признаку, может оказаться худшим по другому признаку.

В случае противоречивых критериев, ИО предлагает следующие подходы к отысканию подходящего решения Замена некоторых критериев ограничениями или Сверка критериев Однокритериальная задача

В случае противоречивых критериев, ИО предлагает следующие подходы к отысканию подходящего решения Ранжирование критериев – задача с упорядоченными критериями Отыскание решений, лучших хотя бы по одному критерию – задача с независимыми критериями

Задача с упорядоченными критериями Все допустимые решения Оптимальные по самому важному критерию Оптимальные по самому неважному критерию

Задача с независимыми критериями Найти множество недоминируемых (эффективных) решений – Лучше любого другого допустимого хотя бы по одному критерию – Не хуже по всем критериям – Множество Парето

Пример многокритериальной задачи с независимыми критериями Фирма должна выполнить проекты 1 и 2. Для выполнения каждого проекта можно привлечь одного, двух или трех исполнителей. Пусть x1 и x2 - число исполнителей, привлеченных для выполнения проектов 1 и 2 соответственно. Время выполнения проекта i равно pi(xi) месяцев, а стоимость проекта i ci(xi)- млн.руб. Требуется минимизировать общее время выполнения проектов при минимальной стоимости. Значения функций заданы в таблице X123 P1(x)211 P2(x)311 C1(x)123 C2(x)445

Общее время выполнения проектов Стоимость их выполнения Определим все возможные значения пар X123 P1(x)211 P2(x)311 C1(x)123 C2(x)445 Предположим, что проект 1 и 2 выполняют по 2 исполнителя, тогда суммируем соответствующие значения в ячейках таблицы, получим пару (2,6) Если проект 1 выполняют 2, а проект 2 выполняют 3 исполнителя, то получим пару (2,7) и.т.

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

Задача отыскания множества Парето в случае двух критериев вида F 1 (x) min и F 2 (x) min Находим все точки с наименьшим значением F 1 (x), если их несколько, то выбирает из них с наименьшим значением F 2 (x) и включаем ее во множество Отсекаем точки с большим либо равным значением F 1 (x) и F 2 (x) Повторяем процедуру для оставшейся части допустимой области В результате получим Что соответствует решению которые являются недоминируемыми и образуют множество Парето этой задачи

Задания для самостоятельного выполнения Выполнить из файла Тема 1 - Многокритериальные задачи две задачи по вариантам Номер варианта совпадает с порядковым номер в списке группы (по алфавиту). Варианты контрольных работ распределите по такому же принципу