Введение
Принятие решений всегда было и остается наиважнейшим аспектом человеческой деятельности. Существуют различные подходы к принятию решений:
· на основе предшествующего опыта;
· на основе здравого смысла;
· на основе метода аналогий; интуитивный и др.
Однако практика управления во всех областях и на всех уровнях нуждается в широком и эффективном использовании математических методов. Создание систем управления невозможно без разработки соответствующей теории принятия решений, отвечающей практическим запросам.
Математическая теория принятия оптимальных (рациональных, целенаправленных) решений называется теорией исследования операций. Задачей теории исследования операций является построение количественных методов анализа процессов принятия решений во всех областях человеческой деятельности. Эта деятельность должна быть, во-первых, целенаправленна, т.е. направлена на достижение определенной цели или целей, и, во-вторых, при предварительном анализе должны быть использованы количественные методы, т.е. формализованные (математические) модели.
С точки зрения математического описания под принятием решений понимается выбор определенного элемента из некоторого множества. При этом определяется правило выбора, целесообразность выбора и понятие оптимальности решения.
Исследование операций — это раздел прикладной математики, который занимается построением математических моделей анализа реальных задач и процессов управления и принятия решений (экономических, социальных, технических, военных и др.). Он структурно оформился в период второй мировой войны и включает в себя ряд разделов, отличающихся друг от друга различными математическими моделями задач поиска оптимальных решений.
Математическая модель нужна для детального предварительного анализа реального явления. Математика проводит количественный и качественный анализ модели, помогает предсказать, как поведёт себя система в различных условиях и даёт рекомендации для принятия «наилучшего» решения.
Перед теорией исследования операций стоят следующие проблемы:
• разработка математических моделей процессов принятия решений, включая определение принципов оптимальности решений;
• исследование вопросов существования оптимальных решений для различных классов задач;
• получение необходимых и достаточных условий оптимальности решений для различных классов задач;
• разработка численных методов определения оптимальных решений.
Основные понятия исследования операций.
Изложение любого предмета начинается с определения или описания используемых в нем основных понятий. В исследовании операций естественно надо начинать с самого понятия «операция».
Операцией называется совокупность действий, направленных на достижение некоторой цели или совокупность целенаправленных действий.
Наличие цели в операции подразумевает существование активных участников, которые преследуют эту цель. Для выделения таких участников в особую группу существует понятие оперирующей стороны.
Оперирующей стороной (ОС) называется совокупность лиц, которые стремятся в данной операции к поставленной цели. Кроме того, в операции могут присутствовать и другие действующие лица, которые оказывают влияние на ход операции, но не преследуют цель оперирующей стороны, в частности, могут стремиться к собственным целям. При изучении операции рассмотрение ведется с позиции оперирующей стороны, а основная задача исследования состоит в поиске и сравнении различных путей достижения поставленной цели.
В оперирующей стороне удобно выделить участника, который называется исследователем операции. Исследователь операции принадлежит к оперирующей стороне и преследует ту же цель, однако он, как правило, сам не принимает решения по выбору способов действий, а только помогает в этом оперирующей стороне, дает научную основу для принятия решений.
Принципиальное отличие исследователя операции от оперирующей стороны в целом состоит в том, что в момент проведения исследования, которое зачастую отделено от самой операции весьма большим промежутком времени он может не иметь всей информации, которая будет у оперирующей стороны в момент проведения операции. Однако он должен предвидеть возможность поступления такой информации и давать рекомендации с учетом этой информации, т.е. предлагать не фиксированные действия, а правила поведения как функции от ожидающейся информации. Это обстоятельство еще более осложняет задачу исследователя операции.
Ответственность за принятие решений и окончательный выбор лежит на оперирующей стороне. Основным инструментом исследователя операции являются математические модели. Несмотря на их большое разнообразие, существуют важнейшие элементы, которые присутствуют практически во всех моделях.
Так в любой операции для достижения поставленной цели оперирующая сторона должна иметь некоторый запас ресурсов (например, минеральное сырье, техническое оборудование, деньги, рабочую силу, вычислительную технику и т. д.). В математической модели операции соответствующий элемент принято называть активными средствами. Действия, направленные на достижение поставленной цели, представляют собой способы использования активных средств.
Соответствующий элемент математической модели называют стратегией и обычно обозначают переменной х. Переменная х может быть скалярной величиной, вектором или функцией.
Стратегии являются факторами, влияющими на ход операции, контролируемыми оперирующей стороной, т.е. выбираемыми ею по своему усмотрению. Кроме них существуют неконтролируемые факторы, влияющие на ход операции, которыми оперирующая сторона не распоряжается, например природные условия. Неконтролируемые факторы будем обозначать переменной у. Общее описание модели должно включать также сведения об информированности оперирующей стороны и исследователя операции об обстановке протекания операции, т.е. о значениях неконтролируемых факторов.
Неконтролируемые факторы, исходя из информированности о них исследователя операции, можно разбить на три группы: фиксированные, случайные, неопределенные.
— это такие факторы, значения которых точно известны исследователю операции. Случайные неконтролируемые факторы представляют собой случайные величины, законы (функции) распределения которых точно известны исследователю операции.
Неопределенные неконтролируемые факторы являются детерминированными или случайными величинами, относительно которых исследователю операции известна лишь область возможных значений или класс возможных законов распределения. Необходимо подчеркнуть, что неконтролируемые факторы описываются с позиции исследователя операции, что же касается оперирующей стороны в целом, то у нее в момент проведения операции может появиться дополнительная информация, существенно сужающая или даже исключающая неопределенность. Но так как мы занимаемся вопросами исследования операций, для нас важна именно информированность исследователя, т.е. информация, доступная в момент проведения исследования, хотя возможное содержание информации, поступающей в момент проведения операции, при этом также должно учитываться.
Ход операции можно описать некоторым набором фазовых переменных. Степень соответствия хода операции поставленной цели в математической модели характеризуется критерием эффективности W, который представляет собой некоторую функцию (в общем случае, векторфункцию) зависящую от фазовых переменных, стратегий и неконтролируемых факторов.
В математической модели эквивалентом цели операции является, как правило, требование максимизации критерия эффективности. Существует много различных классификаций математических моделей. В частности, модели бывают динамические, в которых явно присутствует переменная времени, и статические, в которых этой переменной нет.
В реальности все процессы протекают во времени, поэтому динамические модели, вообще говоря, более точно описывают действительность. Но для проведения исследования часто ограничиваются более простыми статическими моделями. При этом стратегию и воздействие неконтролируемых факторов представляют в виде единичного акта, фазовые переменные исключают, и критерий эффективности представляют как функцию только стратегий и неконтролируемых факторов, т.е. W=F(x,y). (1.1)
Переход от динамической формы модели к статической называется нормализацией. Фактически в ходе исследования можно сразу строить статическую модель, минуя динамическую. Несмотря на внешнюю простоту выражения (1.1), связь между значениями критерия, стратегии и неконтролируемого фактора может быть весьма сложной. Иногда ее не удается представить в явном виде, тогда она задается с помощью промежуточных соотношений или в виде вычислительного алгоритма.
Содержательно всякая задача исследования операций является оптимизационной, т.е. состоит в выборе среди некоторого множества допустимых стратегий тех, которые можно в том или ином смысле квалифицировать как оптимальные. При этом допустимость каждого решения понимается в смысле возможности его фактического осуществления, а оптимальность – в смысле его целесообразности.
Допустимость определяется возможностью реализации соответствующих действий при имеющихся ресурсах. Ограниченность ресурсов выражается в виде математических ограничений, чаще всего имеющих вид равенств и неравенств.
Оптимальность, целесообразность решения предполагает наличие в каждой задаче исследования операций некоторой системы целей, описываемых критерием (критериями) эффективности, и принципа оптимальности (иногда называемого критерием оптимальности). Формально принципом оптимальности называется отображение из множества всех допустимых стратегий в некоторое его подмножество. Чаще всего оно определяется требованиями максимизации (или минимизации) одной или нескольких числовых функций, значения которых выражают степень осуществления целей при соответствующем допустимом решении. Каждая такая функция называется критерием эффективности или целевой функцией.
Иногда эффективность определяется не целевой функцией, а отношением предпочтения, когда применительно к парам допустимых решений указывается, какое из решений этой пары предпочтительней.
Для построения математической модели операции в общем случае рекомендуется выполнить следующую последовательность работ:
- изучение условий задачи и определение важнейших факторов;
- выделение известных и неизвестных параметров;
- выявление управляемых и неуправляемых факторов;
- анализ информации о значениях параметров и дополнение условий задачи недостающими сведениями;
- составление математической модели (математическое выражение целевых функций и соотношений и связей между параметрами);
- определение принципа оптимальности (в общем случае весьма нетривиальный и ответственный этап) и формулировка задачи.
Дадим краткую характеристику этапов операционного исследования.
1. В самом общем случае поводом для изучения и совершенствования системы служат зафиксированные симптомы, обнаруживающие проблемные вопросы в работе системы.
2.Установленные симптомы проблемы могут образовывать связанную цепочку фактов (тенденцию), которая помогает сформулировать проблему.
3.Важнейшим этапом исследования системы является четкая формулировка проблемы, которая присутствует на данном уровне жизнедеятельности системы.
4.Качественный системный анализ – это расщепление целостной системы (операции) на отдельные элементы (сущности).
Для этого нужно:
- выделить изучаемую систему (операцию) из вышестоящей системы (операции);
- сформулировать цель, выполняемую системой (операцией);
- перечислить факторы, которые влияют на достижение цели;
- определить возможные ограничения, в рамках которых можно совершенствовать систему (операцию).
5.Количественный системный анализ предполагает описать все перечисленные факторы, которые участвуют в операции на количественном уровне, т.е. на основе измеримых параметров.
Для этого:
- устанавливается критерий К – величина, количественно измеряющая степень достижения цели системы (операции);
- вводятся количественные внутренние параметры системы, которые измеряют факторы, участвующие в описании системы (операции);
- все множество этих параметров необходимо разбить на две части:
а) неуправляемые параметры (константы), которые мы в данной конкретной системе (операции) менять не можем (производительность, нормы расхода материалов и т.п.), их обозначают как коэффициенты А = (а1, а2, …, ак);
б) управляемые параметры (переменные) – величины, которые мы можем менять Х = (х1, х2, …, x n).
6. Суть математического моделирования – установление количественных связей между введенными величинами К, А, и X в виде так называемой операционной модели. Первая часть операционной модели - это модель целевой функции, она устанавливает функциональную зависимость критерия К от неуправляемых параметров А и управляемых величин X в виде W = f(X, A).
f – может быть функция, заданная аналитически, таблично или алгоритмом. В ряде практических задач в качестве элементов множества X выступают функции. В этом случае f - функционал. Задачи такого рода называются вариационными и в данном пособии не рассматриваются.
Для целевой функции указывается направление улучшения критерия показатель эффективности
W = f(X, A) → min(max). (1.1)
Этим выражением и определяется смысл оптимизации системы (операции). Вторая часть операционной модели – математическое описание ограничений на выбор переменных Х.
Все ограничения в общем виде можно записать в виде неравенств (равенств):
φi(X, A) ≤ 0, i =m, 1,. (1.2)
Каждая функция φi(X, A) называется функцией ограничения.
В некоторых задачах имеются требования на сам вид переменных Х или К.
X Î D
K ∈ M (1.3)
Модель 1.1, 1.2, 1.3 позволяет поставить задачу оптимизации системы (операции) как математическую задачу: найти такие управляемые переменные Х, которые удовлетворяли бы системе ограничений 1.2, 1.3 и обеспечивали бы наилучшее значение критерия К.
7.Решение поставленной математической задачи требует привлечения методов оптимизации, включающих кроме классических математических методов также и специальные методы исследования операций. Реальные задачи приводят к большой размерности (до десятков тысяч). Поэтому современные методы нахождения оптимальных решений ориентированы на использование компьютерных средств.
8.Сопоставляя полученное решение с содержательной постановкой задачи можно обнаружить противоречия или какие-нибудь некорректные элементы решения. Причиной некорректности могут быть ошибки в математической модели или неучет некоторых существенных ограничений. На этом этапе может принимать участие лицо, принимающее решение (ЛПР). Если полученное решение приемлемо – оно принимается, если нет - необходимо вернуться на этап математического моделирования или даже на более ранние этапы исследования.
9.Найденное оптимальное решение X* позволяет подготовить управляющее решение в форме документа для ЛПР. Таким образом, операционное исследование – итерационный процесс, который сходится к определенному оптимальному решению. Рассмотренная схема является примерной. Она позволяет лучше понять смысл системного анализа и исследования операций как науки. Исследование операций (ИСО) - это наука о количественном обосновании оптимальных решений на основе построения и использования математической модели. К сожалению, процесс перевода на количественное описание сложных систем и операций не является технологией. Математическая модель может получиться удачной или неудачной для получения практических решений. Вот почему знаменитый операционист Томас Саати иронично определил науку «Исследование операций» как «искусство давать плохие советы в тех практических случаях, в которых другие науки ничего не могут посоветовать».
Математическое моделирование – самый сложный этап ИСО. Математическая модель – это такое описание системы, которое позволяет специалисту выполнить цель исследования и оптимизации системы. Для одной и той же системы можно построить различные модели, чтобы выявить различные свойства: например аэродинамическая модель, прочностная модель и т.д. Модель должна быть адекватной реальной задаче, т.е. решения, полученные в рамках построенной модели, должны обладать такими же свойствами, что и реальная система.
К сожалению, не существует какого-либо алгоритма, по которому необходимо создать модель. Можно руководствоваться лишь принципами моделирования:
1. Необходимо решить вопрос размерности модели. Если число параметров увеличить, то мы более точно отобразим реальное событие, но в модели будет трудно выявить основные свойства (наиболее значимые). Задача становится необозримой и может не иметь решения. Поэтому число переменных по возможности стараются уменьшать, оставляя главные, существенные. Но уменьшая число переменных, мы можем опустить существенные, и модель становится неадекватной.
2. Модель зависит от точности, с которой нужно получить решение.
3. Модель зависит от того, насколько мы знаем исходные данные.
4. Подход к построению модели может быть двояким:
4.1.Создание оригинальной модели (не учитывая предыдущей модели в этой области), т.е. разработка «с чистого листа». Это может дать, а может не дать хороший результат. Преимущество: «свежий взгляд на вещи», нет чужих ошибок. Но это может быть дороже и потребует большого времени.
4.2.Использование типовых моделей для моделирования конкретных операций. В настоящее время существует большое число типовых моделей, описывающих наиболее распространенные виды операций и систем:
- модель линейного программирования (ЛП);
- модель динамического программирования;
- игровые модели;
- модель массового обслуживания;
- модель систем управления запасами;
и многие другие.
Классификация задач исследования операций
Выше мы познакомились с общей математической моделью операции и основной задачей исследования операций, состоящей в сравнении между собой стратегий и выборе из них наилучшей в том или ином смысле. Эта задача для общей модели является слишком сложной, чтобы для нее можно было получить конкретные результаты. Поэтому в общем случае можно только говорить о принципах сравнения стратегий, связанных с выбором вида оценки эффективности, и соответствующих им понятиях оптимальности.
Методы же нахождения оптимальных стратегий, без которых нельзя говорить о практическом использовании теории исследования операций, для общей модели не существуют. Поэтому в исследовании операций выделяют классы задач, представляющие собой частные случаи основной задачи, для которых такие методы могут быть созданы.
При этом классификацию проводят по двум признакам: видам неконтролируемым факторов и видам критерия эффективности и пространства стратегий.
Наиболее простую группу задач исследования операций составляют такие задачи, в которых неконтролируемых факторов нет или имеются только фиксированные неконтролируемые факторы. Раздел исследования операций, посвященный изучению подобных задач, называется математическим программированием, а сами задачи - задачами математического программирования.
Внутренняя классификация в разделе математического программирования связана уже с видом критерия эффективности и пространства стратегий. Если критерий эффективности представляет собой линейную функцию от переменных, описывающих стратегии, а пространство стратегий задается системой линейных ограничений, т.е. представляет собой многогранное множество, то получающаяся задача называется задачей линейного программирования.
Если, исходя из содержательного смысла задачи, ее решения должны быть целыми числами, то получаем задачу целочисленного программирования. Обычно в целочисленных задачах критерий и остальные ограничения (кроме условия целочисленности) предполагают линейными, поэтому целочисленные задачи можно отнести условно к линейному программированию.
Если критерий эффективности или ограничения, задающие пространство стратегий, являются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если критерий эффективности и пространство стратегий обладают свойствами выпуклости, то получающаяся задача называется задачей выпуклого программирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности выражается не в явном виде как функция от стратегий, а косвенно через уравнения, описывающие развитие процесса протекания операции во времени, то такая задача относится к динамическому программированию.
Линейное программирование (включая целочисленное программирование), нелинейное программирование (включая классические экстремальные задачи и выпуклое программирование) и динамическое программирование составляют основные подразделы математического программирования. Если имеются неопределенные неконтролируемые факторы, то при использовании гарантированной оценки эффективности получаются максиминные (или минимаксные) задачи.
Среди задач с неопределенными неконтролируемыми факторами наиболее интересными являются такие задачи, в которых неопределенность связана с действиями других разумных участников операции, преследующих свои цели. Раздел исследования операций, занимающийся изучением подобных задач, называется теорией игр. Игровые задачи также имеют свою классификацию, в соответствии с которой выделяется несколько подразделов теории игр.
Следует отметить, что практически всегда при принятии управленческих решений имеет место ситуация неоднозначности исхода как следствие неполноты информации о внешней среде. В этом случае говорят о принятии решений в ситуации риска или управлении риском. В силу вышесказанного, неполнота информации связана с наличием случайных или неопределенных неконтролируемых факторов. Иногда риск понимают в более узком смысле как совокупность различных обстоятельств и условий, создающих обстановку, для которой имеется возможность определить вероятность осуществления того или иного исхода. С такой точки зрения определенность и неопределенность представляют два крайних случая полноты исходных данных, а риск - промежуточную ситуацию.
Среди задач исследования операций со случайными неконтролируемыми факторами можно выделить задачи массового обслуживания. Эти задачи характеризуются определенным видом критериев эффективности и случайных величин, которые отражают их содержательный смысл.