На этом шаге мы рассмотрим классификацию методов отыскания оптимальных решений в задачах исследования операций.
К основным методам отыскания оптимальных решений относится математическое программирование. В свою очередь методы математического программирования делятся на следующие:
- линейное программирование,
- нелинейное программирование,
- динамическое программирование,
- целочисленное программирование,
- стохастическое программирование,
- эвристическое программирование,
- теория массового обслуживания,
- сетевые модели планирования и управления,
- имитационное моделирование.
Рассмотренные классы задач можно решать указанными методами.
Методами математического программирования решаются следующие классы задач:
- задачи управления запасами,
- задачи распределения ресурсов,
- задачи замены и ремонта оборудования,
- задачи выбора маршрута.
С помощью теории массового обслуживания решаются задачи массового обслуживания.
С использованием сетевых моделей планирования и управления можно решать:
- задачи массового обслуживания,
- задачи упорядочивания,
- задачи сетевого планирования.
Методом имитационного моделирования решаются комбинированные задачи. Данным методом можно решить задачу любого класса, однако, данный метод не является универсальным. Его применение ограничено следующими факторами:
- Требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов;
- Решение обходится дороже, чем при использовании других методов.
Знакомство с методами исследования операций начнем с примера. Предположим, что в соответствии с деловыми обязательствами вам необходимо в течение пяти недель пять раз посетить город В (постоянное ваше пребывание — город А). Вы должны быть в городе В в понедельник первой недели и окончательно возвратиться в город А в среду пятой недели. Заказной билет из города А в город В и обратно стоит 5500, однако вы можете получить 20% скидки от стоимости билетов, если вылет придется на конец недели. Кроме того, следует учесть, что стоимость билета только в одну сторону равна 75% от стоимости заказного билета. Вы, естественно, хотите минимизировать стоимость перелетов. Как это сделать?
Описанную ситуацию можно рассматривать как задачу принятия решений, где для нахождения оптимального решения требуется определить три основных компонента.
- Что в данном случае считать альтернативными решениями?
- Каким ограничениям должно удовлетворять возможное решение?
- По какому критерию должны отбираться альтернативные решения?
В нашей задаче возможны следующие альтернативы.
- Покупка пяти заказных билетов А-В-А (т.е. из города А в город В и обратно).
- Покупка одного билета в одну сторону А-В, четырех билетов А-В-А, захватывающих конец недели, и одного "однонаправленного" билета В-А.
- Покупка билета А-В-А для первой недели, причем между датами вылетов должен быть понедельник; для последней недели покупка билета А-В-А, между датами которого должна быть среда, причем первый и последний билеты должны захватывать последние дни недели; четыре билета А-В-А, между датами которых также есть последние дни недели.
Ограничением в данной задаче являются дни прибытия: понедельник первой недели и среда пятой. В данном случае естественным критерием для оценивания возможных альтернатив является цена билетов. Альтернатива, обеспечивающая наименьшую стоимость билетов, будет наилучшей. В данном случае имеем следующие альтернативы.
Альтернатива 1: стоимость билетов = 5 х 5500 = 27500 руб.
Альтернатива 2: стоимость билетов = 0.75 х 5500 + 4 х 0.8 х 5500 + 0.75 х 5500 = 25850 руб.
Альтернатива 3: стоимость билетов = 5 х (0.8 х 5500) = 22000 руб.
Очевидно, что наилучшей является третья альтернатива.
Приведенный пример показывает основные принципиальные составляющие модели исследования операций, а именно альтернативы, ограничения и критерий отбора альтернатив. В общем случае в задачах принятия решений альтернативы зависят от определенного набора переменных, которые затем могут использоваться при формализации ограничений и критерия в виде подходящих математических функций. В результате формализации получаем математическую модель, содержащую изменяемые переменные, ограничения и функцию критерия, которая также называется целевой функцией. Решением математической модели будет такой набор значений переменных, который оптимизирует (максимизирует или минимизирует) функцию критерия и удовлетворяет всем ограничениям. Такой набор переменных называется оптимальным допустимым решением.
На следующем шаге мы рассмотрим математический аспект исследования операций.
