поддержка
проекта:
разместите на своей странице нашу кнопку!И мы
разместим на нашей странице Вашу кнопку или ссылку. Заявку прислать на
e-mail
код нашей кнопки:
Исследование операций
Исследование операций - математическая дисциплина, изучающая методы
поиска наилучших решений для случаев, когда и сами решения, и факторы,
которые надо учесть при их принятии, могут быть выражены в
количественной форме или в виде предпочтений. Методы исследования
операций используются, когда необходимо реализовать какую-либо операцию
- совокупность действий, связанных с достижением определенных целей. Это
может быть, например, планирование производства тех или иных изделий;
разработка схемы перевозок, обеспечивающих снабжение населенных пунктов;
выбор пищевого рациона, содержащего достаточное количество питательных
веществ, и т. д. Операция характеризуется двумя видами количественных
факторов: неконтролируемыми факторами, значения которых в данной
ситуации известны, но не зависят от лица, принимающего решение, и
контролируемыми (управляемыми) факторами х1,
...,хп, которые от него зависят, но в определенных пределах, выражаемых
математическими ограничениями: неравенствами, равенствами или какими-то
специальными условиями. Любой допустимый (т. е. удовлетворяющий
ограничениям) набор значений jq,-..., хп является решением. Поскольку
возможных решений много, желательно выбрать из них наилучшее
(оптимальное). Для этого должны существовать критерии качества (критерии
оптимальности), которые, как правило, выражаются в виде функций f (х1,
..., хп). Функция, оценивающая качество, называется целевой. Оптимальное
решение - это экстремум целевой функции. Таким образом, исследование
операций оказывается весьма тесно связанным с теорией принятия решений.
Пусть, например, нужно произвести продукцию трех видов в количествах х\,
хз . Эта продукция требует четырех видов ресурсов. Запасы ресурсов
ограниченны, расход каждого ресурса на единицу каждого вида продукции
известен. Известно также, что доход, получаемый при производстве единицы
г'-го вида продукции, равен с,-. Требуется найти такой план, при котором
доход был бы максимальным.
Допустимое решение здесь - это любой набор величин х1,
х2, при котором не происходит перерасхода ресурсов; неконтролируемые
факторы - запасы b1, b2,
b3, Ь4 ресурсов, расходы
aij-го ресурса на единицу j-го вида
продукции с,-. Целевая функция имеет вид
Математическая задача заключается в следующем: найти точку (xj,
xi, x3) в трехмерном пространстве,
удовлетворяющую заданным ограничениям, в которой /достигает максимума.
В зависимости от характера целевых функций и факторов, участвующих в
задаче, выделяются различные классы задач исследования операций, которые
решаются различными математическими методами. Задачи с одной целевой
функцией называются задачами математического программирования. Описанная
выше задача о максимизации дохода относится к этому классу. Задачи с
несколькими целевыми функциями (критериями оптимальности) называются
многокритериальными задачами. Они возникают, когда либо лицо,
принимающее решение, стремится его оптимизировать сразу по нескольким
критериям, либо лиц, принимающих решение, несколько и у каждого из них
свой критерий оптимальности. Пример многокритериальной задачи - типичная
бытовая ситуация, когда в пределах имеющейся суммы хочется купить и
побольше, и получше. Математическая специфика многокритериальных задач
заключается в том, что решение, оптимальное по одному критерию, не
является оптимальным по всем остальным. Поэтому требуется некоторое
дополнительное правило, согласующее различные критерии и называемое
принципом оптимизации. Наиболее употребительны принцип оптимальности по
Парето и различные приемы сведения задачи к однокритериальной. Решение
0c]t..., хп) называется "оптимальным по Парето", если любое отклонение
от него ухудшает хотя бы один из критериев. Сведение задачи к
однокритериальной происходит либо путем свертки, либо путем выбора
главного критерия. Свертка заключается в том, что в качестве целевой
функции выбирается некоторая функция от исходных критериев /1, ...,/п.
Чаще всего это бывает "взвешенная" сумма axf\ + ... + a,Jn , где вес а,-
тем больше, чем важнее критерий /(. При выборе главного критерия
оптимизация ведется по нему, а остальные либо учитываются, если
приходится выбирать между решениями, оптимальными для главного критерия,
либо формулируются как ограничения. Например, если нужно купить конфет
на 1000 руб. побольше и получше, но главный критерий - получше, то в
первом случае сначала выбираются те конфеты, которые больше нравятся, а
если самых лучших - несколько сортов, то из них -
самые дешевые; во втором случае с самого начала учитываются ограничения
на цену и выбираются лучшие среди тех, которые не дороже некоторой цены
(установленной заранее). Этот пример показателен тем, что в нем наряду с
количественным критерием (стоимостью) участвует критерий качества конфет,
который нельзя выразить числом, но можно представить системой
предпочтений (т. е., например указать, что сорт а лучше сорта b, с лучше
b, a b и d примерно одинаковы).
В исследовании операций различаются статические и динамические задачи. В
статической задаче неконтролируемые факторы считаются неизменными. В
динамической задаче обычно речь идет о планировании на протяжении
некоторого отрезка времени, в течение которого эти факторы меняются,
причем их изменение на каждом шаге зависит от решений, выбранных на
предыдущих шагах.
Задачи исследования операций могут быть детерминированными и
стохастическими (вероятностными). Детерминированной задача называется
тогда, когда все ее факторы известны точно. В вероятностных задачах
факторы известны лишь с некоторой вероятностью. До сих пор приводились
примеры детерминированных задач. Рассмотрим некоторые вероятностные
задачи.
Магазин, торгующий скоропортящимся товаром (хлебом, молоком или
ежедневными газетами), должен определить объем ежедневного заказа этих
товаров с целью максимизации дохода. Если объем заказа выше спроса, то
непроданный товар портится, и магазин несет убытки; если объем ниже
спроса, то теряется возможный доход. Спрос нельзя предвидеть точно,
однако в стабильной обстановке известна его статистика, т. е. для любого
значения спроса известна вероятность того, что он будет именно таким.
Решение этой задачи также может быть вероятностным: например, с частотой
1/3 заказывать объем V1 и с частотой 2/3 заказывать объем V2. Задачи
такого типа называются задачами управления запасами.
Другой распространенный тип вероятностных задач исследования операций -
задачи, связанные с системами массового обслуживания. Системы массового
обслуживания характеризуются наличием пунктов (или каналов) обслуживания,
потоком заявок на обслуживание и дисциплиной обслуживания, т. е.
порядком, в котором обслуживаются поступившие заявки. Каждый канал
способен обслужить любую заявку, но, может быть, с разной
производительностью. Примеры таких систем - кассовый зал магазина или
вокзала (каналы - кассы, заявки - покупатели), автозаправочная станция (каналы
- бензоколонки; заявки - автомобили), многопроцессорная вычислительная
система (каналы - процессоры, внешние устройства; заявки - программы).
Основной вероятностный фактор - поток заявок и связанные с ним длины
очередей. Целевыми функциями, отражающими эффективность обслуживания,
могут быть средняя длина очереди, среднее время ожидания обслуживания,
средний доход, приносимый системой, и т. д.
Упомянутые выше методы опираются на математические модели решаемых задач.
Однако часто в задаче, для которой надо принять решение, взаимосвязи
между факторами хотя и могут быть выражены математическими формулами, но
настолько сложны, что методы поиска оптимальных решений либо отсутствуют,
либо неприемлемы по затратам машинного времени. В этих случаях
приходится обходиться машинным прогнозом последствий отдельных (как
правило, не оптимальных) решений. Такой анализ называется имитационным
моделированием. Машинная имитация начинается с некоторого исходного
состояния. После выбора решения в этом состоянии вычисляется следующее
состояние, затем снова выбирается решение и т. д. При этом моделируются
и источники неконтролируемых внешних факторов. Помимо проблем, связанных
с математическим описанием и программной реализацией имитационной модели,
важными и плохо формализуемыми проблемами здесь являются выбор
конкретных решений, которые надо промоделировать, и интерпретация
полученных результатов.