Исследование операций. Теория игр

 решений. Примеры, иллюстрирующие теорию, имеют экономический и производственный характер.
     Материал излагается на уровне, доступном читателю, знакомому с математическим программированием, элементами теории вероятное гей и высшей математики. Второе издание пособия позволит читателям получить полное представление о возможностях практического применения методов исследования операций для решения, в том числе и на ЭВМ. экономических. производственных и других задач. В пособии приведено множество примеров задач прикладного характера с подробными решениями и необходимыми пояснениями. В конце каждой главы даны задачи для самостоятельного решения. Они различны по степени трудности, однако имеют непосредственную смысловую связь с рассматриваемыми проблемами. Самостоятельное решение задач, безусловно, будет способствовать более глубокому усвоению изучаемою материала и развитию навыков операционных исследований.
    Необходимоеть второю издания учебною пособия вызвана отсутствием учебной литературы по данному курсу.
    Материал книги распределен между авторами следующим образом: Л.С. Костевич написал предисловие, гл. 2-4, 6. 12, 13. 15; А.А. Лапко-гл. 1,5. 7-11, 14.
    Авторы выражают глубокую благодарность рецензентам: коллективу кафедры управления информационными ресурсами Академии управления при Президенте Республики Беларусь. лично ее заведующему кандидату технических наук, доценту В.И. Новикову и доктору технических наук, профессору А.С. Гринбергу, а также заведующему лабораторией исследования операций Объединенного института проблем информатики Национальной академии наук Беларуси доктору технических наук Г.М. Левину за объективные и доброжелательные рецензии на рукопись второго издания учебного пособия, за ценные замечания и советы, которые способствовали его улучшению.
   Все отзывы и пожелания просим направлять по адресу: 220048, Минск, проспект Победителей, 11, издательство «Вы-шэйшая школа».

Авторы

ОСНОВНЫЕ ПРИНЦИПЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

1.1. Предмет исследования операций

   Потребность управления сложными, в том числе и экономическими. объектами вызвала к жизни специальные методы, облегчающие принятие правильных решений. Эти методы обычно объединяют гермином «исследование операций». Первоначально их использовали преимущественно для выработки и обоснования принимаемых решений в военных операциях. В настоящее время методы исследования операций находят применение в самых различных областях человеческой деятельности: промышленности, сельском хозяйстве, транспорте. торговле, здравоохранении, бытовом обслуживании, охране окружающей среды и г.д.
   Что же такое исследование операций? Для уяснения лого понятия воспользуемся двумя определениями.
   1.  Исследованием операций называется теория математических моделей принятия оптимальных решений и практика их использования¹ ².
   2.   Исследование операций представляет собой искусство давать плохие от веты па ге практ ические вопросы, на которые даются еще худшие ответы другими способами .
   Первое определение отражает математическую сторону вопроса и иначе может быть сформулировано следующим образом: под исследованием операций понимается применение математических, количественных методов для обоснования решений, принимаемых в тех областях целенаправленной человеческой деятельности, в которых существуют различные пути, ведущие к достижению цели.
   Суть второго определения, данного в шутку специалистом в области исследования операций Г.Л. Саати, заключается в том, что практические ситуации, в которых приходится при

¹ Общая теория систем: сб. статей. М.. 1966.

² Оптнер. Л. Системный анализ для решения деловых промышленных проблем / Л. Оптнер. М.. 1969.

5

  нимать решения, бывают настолько сложными и важными, что даже незначительная «помощь» математических методов является весьма существенной.
     Подводя итог сказанному, надо отметить, что исследование операций в самом общем смысле может быть охарактеризовано как применение научных принципов, методов и средств к задачам, связанным с функционированием организационных систем, с целью предоставить тем, кто управляет этими системами, оптимальные решения. Таким образом, предметом исследования операций являются системы, представляющие собой взаимодействующую совокупность объектов и предназначенные для достижения некоторой конкретной цели. Определение места исследования операций среди наук и математических методов, связанных с вопросами управления производством, представляет некоторые трудности. Рассматривая исследование операций как научную дисциплину, необходимо помнить, что она находится на стыке наук, оперирующих не только количественными, но и качественными фактами. Для того чтобы ближе познакомиться с задачами исследования операций и их характерными особенностями, рассмотрим некоторые примеры.
    1.    На новой автостраде сооружается сеть автозаправочных станций (/\ЗС). Количество отпущенных средств ограниченно. Требуется рациональным образом выбрать параметры этой сети. т.е. дать ответы на следующие вопросы: какое количество АЗС строить; какое количество бензоколонок устанавливать на каждой станции; каково должно быть количество обслуживающего персонала, чтобы обеспечивался заданный уровень качества обслуживания и расходы, связанные с функционированием всей сети, были минимальными?
    2.   Организуется снабжение группы промышленных предприятий сырьем, которое поставляется заготовительными организациями, находящимися в различных географических пунктах страны. Требуется разместить заказы на сырье так, чтобы издержки, связанные с его заготовкой и доставкой, были минимальными и все потребности в сырье удовлетворялись в заданные сроки.
    3.   Для организации заготовок сезонной продукции создается сеть временных заготовительных пунктов. Требуется выбрать параметры этой сеги (количество заготовительных пунктов, места их размещения, количество обслуживающего персонала на каждом пункте и т.д.) таким образом, чтобы экономический эффект создания этой сети был максимальным.
    Рассмотренные примеры позволяют составить представление об отличительных особенностях задач исследования операций. Несмотря на то что эти примеры относятся к различным областям человеческой деятельности, в них легко заметить некоторые общие черты. Так, в каждом из них речь идет

6

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

1.2. Операция и ее математическая модель

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


7

  сторона всегда имеет в своем распоряжении некоторый запас ресурсов и. используя и расходуя их, добивается поставленной цели. Эти ресурсы называются активными средствами, а способы их использования, расходования - стратегиями оперирующей стороны. Оптимальными считаются стратегии. которые по определенным соображениям являются предпочтительнее других. Следовательно, операция - это управляемое мероприятие, и от оперирующей стороны зависит выбор стратегий (т.е. параметров, характеризующих способ организации операции), ведущих к достижению поставленной цели. Результаты операции зависят от имеющегося количества активных средств, а при фиксированном количестве - от выбираемых стратегий. Другими словами, исход операции зависит от факторов, находящихся в распоряжении оперирующей стороны. Эти факторы (параметры) называются контролируемыми. Однако на исход операции влияют также факторы, которые не зависят от действий оперирующей стороны и которые она изменять не вправе, - это так называемые неконтролируемые факторы. Они определяют обстановку проведения операции. Например, в сельском хозяйстве при планировании урожайности необходимо учитывать такой неконтролируемый фактор, как метеоусловия.
    Задача исследования операций заключается в выборе и количественном обосновании оптимальных стратегий с учетом обстановки проведения операции. Этими вопросами занимается исследователь операции - лицо или группа лиц, принадлежащих к оперирующей стороне. Исследователю операции в процессе принятия решения отведена особая роль. Он только исследует операцию, сам же решения по ее управлению, как правило, не принимает, поскольку часто лишен всей информации, характеризующей обстановку проведения операции.
    В процессе поиска и обоснования оптимальных стратегий исследователю операции приходится заниматься анализом получаемых решений на чувствительность, т.е. исследовать влияние отклонений от оптимальных решений на исход операции. Решение этой задачи очень важно при системном подходе к исследованию операции, когда она рассматривается как составная часть системы взаимосвязанных операций. Несколько взаимосвязанных операций всегда можно объединить в одну более сложную, но при этом процесс исследования, как правило, также усложняется. Поэтому на практике в ряде случаев удобнее с точки зрения исследователя разделять исследуемую операцию на более мелкие.

8

1.2.2. Критерий эффективности
   Исследователь операции должен иметь возможность оценивать различные исходы операции, соответствующие различным стратегиям. Для оценки исхода используется критерий эффективности (в литературе также применяются термины «критерий качества», «критерий оптимальности», «показатель эффективности» и др.). Критерий эффективности является математическим эквивалентом цели операции, позволяющим количественно оценивать степень достижения этой цели. Каждой конкретной цели операции соответствует свой критерий эффективности.
   Приведем примеры:
   1. На промышленном предприятии организуется система мероприятий по экономии производственных ресурсов. Критерий эффективности - сумма сэкономленных ресурсов.
   1. Организуется система мероприятий, направленных на повышение надежности технического устройства. Критерий эффективности - вероятность выхода устройства из строя.
   3. Необходимо организовать доставку груза от ряда поставщиков к потребителям. Критерий эффективности - суммарные издержки, связанные с доставкой грузов.
   В одних задачах критерий эффективности (в дальнейшем будем обозначать его Ф) необходимо обратить в максимум, а в других - в минимум. Но задача, в которой Ф необходимо минимизировать, легко сводится к задаче максимизации (для этого достаточно, например, умножить Ф на -1). В дальнейшем там. где это не оговорено, будем подразумевать, что критерий Ф требуется обратить в максимум. При рассмотрении конкретных примеров будем пользоваться как критериями эффективности, которые необходимо максимизировать, так и критериями, которые требуется минимизировать.
   Критерий эффективности должен обладать рядом свойств: простотой (не содержать большого количества второстепенных связей и факторов, затрудняющих его исследование); представительностью (отражать основную, а не второстепенные цели операции); критичностью (достаточно сильно изменяться при изменении параметров, характеризующих выбор той или иной стратегии); единственностью (каждой операции должен соответствовать единственный критерий эффективности, хотя данное требование удается выполнить далеко не всегда).
   Можно выделить два вида целей операций и соответственно два вида критериев эффективности.
   1.   Качественные цели, суть которых состоит в том, что они могут быть достигнуты или нет. Критерий эффективности

2. Зак. 940

9

в этом случае характеризует лишь факт достижения или недостижения цели. Математически критерий эффективности, соответствующий качественной цели, может быть записан так: Ф = I, если цель достигается: Ф - 0. если цель не достигается (или Ф = -<х . если необходимо подчеркнуть, что цель обязательно должна быть достигнута).
    Например, в некотором районе страны организуется система мероприятий по борьбе с траловыми облаками. Критерий эффективности в данном случае можно записать следующим образом:
_ (1, если выпадение града предотвращено;
(0 или - оо, если град выпал.
    Любые мероприятия в данной операции, не приводящие к достижению цели, считаются неэффективными.
    2.    Количественные цели - это цели, суть которых состоит в стремлении к увеличению или уменьшению показателя, характеризующего уровень достижения цели и зависящего от стратегий и неконтролируемых факторов, т.е. этот показатель, являющийся количественной мерой степени достижения цели операции, и является критерием эффективности. Примером количественного критерия эффективности может служить любой из критериев, рассмотренных на с. 9.
   Для применения количественных методов исследования строится математическая модель операции. Желательно, чтобы каждой модели операции соответствовал единственный критерий эффективности.

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

10

существенные факторы, оказывающие наибольшее влияние на течение и исход операции.
   Построение математической модели - своего рода искусство. которым можно овладеть только опытным путем, постепенно. Это наиболее важная и ответственная часть операционного исследования.
   Математические модели, используемые в исследовании операций, можно разделить на статистические и аналитические.
   Статистическая модель в настоящее время неразрывно связана с электронными информационными технологиями. Развитие вычислительной техники позволило «разыгрывать» операции с помощью ЭВМ и получать соответствующие статистические характеристики, интересующие исследователя и характеризующие операцию. Статистические модели позволяют наиболее полно учитывать все связи, факторы, описывающие операцию, и заменять однократное исследование сложной модели многократным исследованием простых моделей. Эти модели можно использовать там. где никакие другие методы и модели неприменимы. К недостаткам статистических моделей относятся большие временные затраты, необходимые для получения числовых характеристик операции. К тому же в процессе получения числовых характеристик нельзя сделать никаких выводов о влиянии различных факторов на исход операции. В этом отношении более удобными являются аналитические модели, которые с помощью алгебраических, дифференциальных, интегральных уравнений позволяют установить формульные зависимости между основными факторами операции. Аналитические модели чаще всего используются в тех случаях, когда либо число параметров не слишком велико, либо зависимости между ними не очень сложные. Они удобны также тем. что для исследования можно применять самые разнообразные математические методы и приемы (математическое программирование, теорию вероятностей с такими разделами, как теория массового обслуживания и теория случайных процессов, теорию графов, дифференциальные и интегральные уравнения и т.д.). Чаще всего применяются совместно аналитические и статистические модели операций. Такое объединение позволяет наиболее полно использовать достоинства как одних, так и других моделей.
   По сути математического описания аналитические модели могут быть разделены на детерминированные и стохастические. Характерной особенностью детерминированных моде
КХ

  лей является то. что все факторы, характеризующие рассматриваемую операцию, считаются известными исследователю операции. Стохастические модели содержат случайные факторы. относительно которых известны лишь законы их распределения. Стохастические модели обычно сложнее, чем детерминированные. как по построению, так и по исследованию.
     По числу этапов различаются многоэтапные и одноэтапные модели. Многоэтапные модели используются при рассмотрении операций, развивающихся во времени, и могут быть разделены на ряд взаимосвязанных этапов. Одноэтапные модели рассматриваются в некоторый фиксированный момент времени.
     Метод математического моделирования фактически сводит изучение явлений внешнего мира к математическим задачам. По этой причине под моделями иногда понимают изложение задач в форме, допускающей их решение математическими методами. Это важный аспект моделирования, ибо от характера и вида математической модели зависит выбор математического аппарата, необходимого для решения задачи.
    Важным следствием применения методов исследования операций для решения широкого круга практических задач явилось выделение небольшого числа классов, к которым сводится большинство из них. Вследствие частой повторяемости задач определенных классов были разработаны методы построения их моделей и получения решений на этих моделях. В связи с этим в дальнейшем при исследовании операций различных видов, как это принято в литературе по исследованию операций, будем использовать термин «задача», а не «модель».
    В зависимости от типа исследуемых операций различают следующие классы задач: назначения и распределения ресурсов; ремонта, замены и надежности оборудования; поиска; построения имитационных моделей и деловых игр; выбора маршрутов; упорядочения и согласования; массового обслуживания; состязательные; управления запасами.

1.3. Основные классы задач исследования операций

1.3.1. Классификация по типам задач

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

12

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

13