Типичные задачи исследования операций

Основные понятия и принципы исследования операций

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

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

Цель исследования операций — предварительное количественное обоснование оптимальных решений. Заметим, что само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которым предоставлено право окончательного выбора и на которых возложена ответственность за этот выбор.

Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (его часто называют «целевой функцией»). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели.

Чтобы выбрать показатель эффективности W, нужно спросить себя: чего мы хотим, к чему стремимся, предпринимая операцию? Выбирая решение предпочтем такое, которое обращает показатель эффективности W в максимум (или же в минимум). Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум. Если показатель эффективности желательно максимизировать, мы это будем записывать в виде W  max, а если минимизировать — W  min.

План снабжения предприятий. Задача операции — обеспечить снабжение сырьем при минималь-ных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R  min).

 

 

Типичные задачи исследования операций

Чтобы познакомиться со спецификой этой науки, рассмотрим ряд типичных для нее задач. Эти задачи, намеренно взятые из самых разных областей практики, несмотря на некоторую упрощенность постановки, дают все же понятие о том, каков предмет и каковы цели исследования операций.

План снабжения предприятий. Имеется ряд предприятий, потребляющих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями какими-то путями сообщения (железнодорожными, водными, автомобильными, воздушными) со своими тарифами. Требуется разработать такой план снабжения предприятий сырьем, чтобы потребности в сырье были обеспечены при минимальных расходах на перевозки.

Задача операции — обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R  min).

Постройка магистрали. Сооружается участок железнодорожной магистрали. В нашем распоряжении — определенное количество средств: людей строительных машин, ремонтных мастерских, грузовых автомобилей и т. д. Требуется назначить очередность работ, распределить машины и людей по участкам пути, обеспечить ремонтные работы так, чтобы оно было завершено в минимально возможный срок. Требуется так спланировать строительство, чтобы закончить его как можно скорее. Естественным показателем эффективности было бы время завершения стройки, если бы оно не было связано со случайными факторами (отказы техники, задержки в выполнении отдельных работ). Поэтому в качестве показателя эффективности можно выбрать среднее ожидаемое время Т окончания стройки.

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

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

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

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

В качестве показателя эффективности можно выбрать средний процент (долю) Q больных и носителей инфекции, которых удалось выявить.

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

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

 

Цели моделирования

Решаются 2 задачи — экспертная и конструктивная.

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

Описательные модели предназначены для описания свойств или поведения реальных объектов.

Примеры. План города, отчет о деятельности фирмы, психологическая характеристика личности.

Можно назвать цели описательного моделирования в зависимости от решаемых задач: изучение объекта — наиболее полно и точно отразить свойства объекта; управление — наиболее точно отразить свойства объекта в рабочем диапазоне изменения его параметров; прогнозирование — построить модель, способную наиболее точно прогнозировать поведение объекта в будущем; обучение – отразить в модели изучаемые свойства объекта. Построение описательной модели: объект-наблюдение –кодирование-фиксация-модель.

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

 

 

Пример задачи линейного программирования.

Имеются три промышленных предприятия П1, П2, П3, требующих снабжения определенным видом сырья. Потребности в сырье каждого предприятия равны соответственно а1,а2, а3 единиц. Имеется пять сырьевых баз, расположенных от предприятий на каких-то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием Пi с базы Бj обходится предприятию в с i j рублей (первый индекс – номер предприятия, второй – номер базы).

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б1, Б2,Б3, Б4, Б5 могут дать не более b1, b2, b3, b4, b5 единиц сырья. Требуется составить такой план снабжения предприятий сырьем (то есть, с какой базы,куда и какое количество сырья везти), чтобы потребности предприятия были обеспечены при минимальных расходах на сырье. Опять поставим задачу линейного программирования.

Обозначим х i j – количество сырья, получаемое i -ым предприятием с j -ой базы. Всего план будет состоять из 15-ти элементов решения

 

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

Далее запишем ограничения-неравенства, вытекающие из производственных мощностей баз

. Запишем суммарные расходы на

сырье, которые мы хотим минимизировать. С учетом данных таблицы получим

Мы получили задачу линейного программирования – найти

такие неотрицательные значения переменных х i j, которые удовлетворяли бы ограничениям-равенствам (*), ограничениям-неравенствам (**) и обращали бы в минимум их линейную функцию (***).

 

Примеры систем массового обслуживания

СМО	Заявки	Каналы
Автобусный маршрут и перевозка пассажиров	Пассажиры	Автобусы
Производственный конвейер по обработке деталей	Детали, узлы	Станки, склады
Электрические заряды, перемещающиеся в некотором устройстве	Заряды	Каскады технического устройства

 

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

Каналы – это то, что обслуживает. Они бывают горячие (обслуживание заявки в момент поступления) и холодные(для начала обслуживания требуется время).

Источники заявок порождают заявки в случайные моменты времени согласно заданному закону распределения.

Заявки образуют потоки (поток обслуженных заявок, отказанных и т.д).

Очереди хар-ся правилами стояния в очереди (дисциплиной обслуживания).

Дисциплины обслуживания.

· FIFO-первым пришел, первым ушел.

· LIFO-последним пришел, первым ушел (патроны в рожке).

· SF-короткая очередь. В первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

· Random (случайный выбор).

 

 

Основные понятия и принципы исследования операций

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

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

Цель исследования операций — предварительное количественное обоснование оптимальных решений. Заметим, что само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которым предоставлено право окончательного выбора и на которых возложена ответственность за этот выбор.

Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (его часто называют «целевой функцией»). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели.

Чтобы выбрать показатель эффективности W, нужно спросить себя: чего мы хотим, к чему стремимся, предпринимая операцию? Выбирая решение предпочтем такое, которое обращает показатель эффективности W в максимум (или же в минимум). Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум. Если показатель эффективности желательно максимизировать, мы это будем записывать в виде W  max, а если минимизировать — W  min.

План снабжения предприятий. Задача операции — обеспечить снабжение сырьем при минималь-ных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R  min).

 

 

Типичные задачи исследования операций

Чтобы познакомиться со спецификой этой науки, рассмотрим ряд типичных для нее задач. Эти задачи, намеренно взятые из самых разных областей практики, несмотря на некоторую упрощенность постановки, дают все же понятие о том, каков предмет и каковы цели исследования операций.

План снабжения предприятий. Имеется ряд предприятий, потребляющих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями какими-то путями сообщения (железнодорожными, водными, автомобильными, воздушными) со своими тарифами. Требуется разработать такой план снабжения предприятий сырьем, чтобы потребности в сырье были обеспечены при минимальных расходах на перевозки.

Задача операции — обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R  min).

Постройка магистрали. Сооружается участок железнодорожной магистрали. В нашем распоряжении — определенное количество средств: людей строительных машин, ремонтных мастерских, грузовых автомобилей и т. д. Требуется назначить очередность работ, распределить машины и людей по участкам пути, обеспечить ремонтные работы так, чтобы оно было завершено в минимально возможный срок. Требуется так спланировать строительство, чтобы закончить его как можно скорее. Естественным показателем эффективности было бы время завершения стройки, если бы оно не было связано со случайными факторами (отказы техники, задержки в выполнении отдельных работ). Поэтому в качестве показателя эффективности можно выбрать среднее ожидаемое время Т окончания стройки.

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

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

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

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

В качестве показателя эффективности можно выбрать средний процент (долю) Q больных и носителей инфекции, которых удалось выявить.

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

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