Тема 1. Математические и эвристические методы и модели, используемые при выработке управленческих решений (стр. 1 )

ТЕМА 1. Математические и эвристические методы и модели, используемые при выработке управленческих решений

План темы.

1.  Классификация научно-практических методов, применяемых при принятии решений.

2.  Задачи оптимизации: формулировка задачи, критерии оптимизации, классификация.

3.  Эвристические (качественные) методы разработки управленческих решений.

Методы принятия управленческих решений — это конкретные способы, с помощью которых может быть решена проблема. Их существует довольно много, например:

декомпозиция — представление сложной проблемы как совокупности простых вопросов;

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

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

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

Приведем классификацию научно-практических методов принятия решений на группы и состав этих групп.

Первый класс представляют общенаучные методы, вклю­чая:

а) системный анализ;

б) комплексный анализ;

в) дифференциацию и интеграцию;

г) программно-целевое планирование.

Второй класс представлен традиционными способами об­работки информации и принятия решений, в которые входят:

а) метод сравнения;

б) метод относительных и средних величин;

в) графический метод;

г) метод группировки;

д) балансовый метод.

Третий класс составляют способы принятия решений на основе детерминированного факторного анализа, включая:

а) метод цепных подстановок;

б) индексный метод;

в) метод абсолютных разниц;

г) метод относительных разниц;

д) интегральный метод;

е) метод пропорционального деления (долевого участия);

ж) метод дифференциального исчисления;

з) метод взвешенных конечных разностей;

и) метод простого прибавления неразложимого остатка;

к) логарифмический метод;

л) метод коэффициентов;

м) метод дробления приращения факторов.

Четвертый класс составляют способы принятия решений на основе стохастического факторного анализа. К ним отно­сятся принятия решений, основанные на методах:

а) корреляционного анализа;

б) дисперсионного анализа;

в) компонентного анализа;

г) современного многомерного факторного регрессионного анализа.

Пятый класс составляют способы принятия решений на основе оптимизации показателей эффективности. К ним от­носятся:

а) методы линейного программирования;

б) методы динамического программирования;

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

г) методы теории игр;

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

е) методы управления запасами ресурсов;

ж) методы распознавания образов.

Шестой класс составляют способы, базирующиеся на ос­нове анализа схем стратегического развития. К этим способам относятся:

а) метод GAP-анализа («продукт—рынок»);

б) метод матрицы BCG (Бостонской консультативной груп­пы);

в) модель Томпсона и Стрикланда;

г) портфельная матричная модель Мак-Кинси DPM;

д) модель «7S»;

е) модель комплексного делового анализа PIMS;

ж) модель ситуационного SWOT-анализа.

Седьмой класс составляют способы, связанные с управле­нием персоналом, включая:

а) континуум лидерского поведения Танненбаума—Шмидта;

б) ситуационная модель Фидлера;

в) модель зрелости исполнителей Херсея и Бланшарда;

г) модель «путь—цель» Торенса, Митчелла и Хауса;

д) ситуационная модель Стинсона—Джонсона;

е) модель принятия решений Врума—Йеттона—Яго.

Восьмой класс составляют методы, основанные на инст­рументах управления качеством. К этим методам относятся: семь основных «инструментов» (seven basic tools) и семь новых «инструментов» (seven new tools) повышения качества.

Семь основных инструментов качества включают:

♦ стратификацию;

♦ контрольный листок;

♦ гистограмму;

♦ диаграмму Парето;

♦ диаграмму Исикавы;

♦ диаграмму рассеяния;

♦ контрольные карты.

Девятый класс составляют методы теории квалиметрии. Эти методы традиционно содержат такие этапы, каждый из которых характеризуются множеством методов.

Десятый класс составляют методы комплексного эконо­мического анализа хозяйственной деятельности (АХД) орга­низации. Этот класс методов составляют:

а) методы выявления и подсчета резервов при АХД;

б) методы функционально-стоимостного анализа;

в) методы маржинального анализа;

г) методы анализа формирования и размещения капитала;

д) методы анализа эффективности и интенсивности исполь­зования капитала предприятия;

е) методы анализа эффективности использования основно­го капитала;

ж) методы анализа использования материальных ресурсов предприятия;

з) методы анализа использования трудовых ресурсов пред­приятия;

и) методы анализа маркетинговой деятельности предприя­тия;

к) методы анализа производства и реализации продукции; л) методы анализа себестоимости продукции.

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

Задачи оптимизации можно разделить на: принятие решений в условиях определенности - исходные данные - детерминированные; принятие решений в условиях неопределенности - исходные данные - случайные величины.

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

В общем виде обратная детерминированная задача будет выглядеть следующим образом.

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

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

Очень часто реальные задачи содержит помимо выше перечисленных факторов, еще одну группу - неизвестные факторы. Тогда обратную задачу можно сформулировать следующим образом.

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

Это уже другая, не чисто математическая задача (недаром в ее формулировке сделана оговорка "по возможности"). Наличие неопределенных факторов переводит эту задачу в новое качество: она превращается в задачу о выборе решений в условиях неопределенности.

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

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

ТЕМА 2. Графы и сети.

План темы.

1.  Понятие и свойства графов. Способы задания графа. Эйлеров цикл. Гамильтонов цикл.

2.  Задача о соединении городов.

3.  Максимальный поток.

4.  Кратчайший маршрут.

5.  Критический путь.

Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом (рис. 2.1).

Рис. 2.1

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

В этом случае вершины А и В называются связанными.

Граф называется связным, если любая пара его вершин связана (рис. 2.2).

Рис. 2.2.

Рис. 2.3.

Граф, изображенный на рис. 2.3, несвязен.

Маршрут называют цепью, если каждое ребро графа встречается в нем не более одного раза (вершины в цепи могут повторяться и несколько раз) (рис. 2.4). Цепь, начальная и конечная вершины которой совпадают, называется циклом (рис. 2.5)

Рис. 2.4

Рис. 2.5

Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно. Вершина А на рис. 4 четна – в ней сходятся 2 ребра, а вершина В нечетна – в ней сходится 3 ребра. Число ребер, сходящихся в вершине графа, называется степенью (порядком) этой вершины.

Граф называется конечным, если множество его ребер конечно. Примером бесконечного графа может служить прямоугольная сетка, заданная на всей плоскости.

Способы задания графа.

1.  Явное задание графа как алгебраической системы.

<{a, b,c, d},{u, v,w, x}; {(u, a),(u, b),(v, b),(v, c),(w, c),(w, a),(x, c), (x, d)}>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a, b,c, d}; {(a, b), (b, a),(b, c),(c, b),(a, c),(c, a),(c, d),(d, c)}>. В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a, b},{b, c},{a, c},{c, d}} и граф мы будем записывать как пару (V, E), где V – множество вершин, а E – множество рёбер.

В дальнейшем мы будем опираться именно на второе определение графа.

2.  Геометрический

3.  Матрица смежности a b c d a 0 1 1 0 b 1 0 1 0 c 1 1 0 1 d 0 0 1 0

Эйлеров и гамильтонов циклы

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

Теорема 1 (Критерий эйлеровости графа). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин – чётные числа.

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

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

Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.

Связный граф без циклов называется деревом. Примером дерева служит генеологическое дерево (рис. 2.6).

Рис. 2.6

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

Задача о соединении городов

С деревьями связана и одна из проблем минимального соединения, внешне напоминающая задачу о коммивояжере, но значительно про­ще разрешаемая (для решения этой проблемы построены эффектив­ные алгоритмы).
Имеется п городов — А1, А2, . . . , Ап, которые нужно связать ме­жду собой сетью дорог. Стоимость сооружения дороги, соединяющей города Ai и Ak, известна и равна c(Ai, Ak).

Какой должна быть сеть дорог, связывающая все города, чтобы стоимость ее сооружения была минимальной?

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

Алгоритм (план реализации)

На 1-м шаге связываем два города с наиболее дешевым соединя­ющим звеном е1.

На каждом следующем шаге добавляем самое дешевое из звеньев еi (если имеется несколько звеньев с одинаковой стоимостью, выби­раем любое из них), в результате присоединения которого к уже по­строенным звеньям найденная сеть удлиняется еще на одно звено, но никакого цикла не образуется. При поиске добавляемого звена надо перебирать все ребра, имеющие общую вершину с уже построенной сетью. Последний шаг алгоритма имеет номер п — 1.

Стоимость строительства полученной сети минимальна и равна

,

Пусть, например, нужно соединить города А, В, С и D. Стоимость строительства дорог, соединяющих любые два города, известна и в условных единицах представлена в таблице:

	А	В	С	D
А	—	11	13	12
В	11	—	6	9
С	13	6	—	10
D	12	9	10	—

Сеть дорог минимальной стоимости состоит из 3 (4—1 = 3) звеньев и строится так: сначала выбирается самый дешевый участок доро­ги — ВС (его цена равна 6), затем он удлиняется на самый дешевый из оставшихся — BD (его цена равна 9). И на последнем, третьем шаге вновь выбирается самый дешевый (но так, чтобы не образова­лось никакого цикла) — АВ (его цена равна 11) (рис. 2.7). Таким образом, стоимость строительства равна+ 9 + 11).

Рис. 2.7

Максимальный поток

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

Рис. 2.8  Рис. 2.9

Подобных сечений, разделяющих пункты А и В, может быть не­сколько (рис. 2.9), и каждое из них обладает своей пропускной спо­собностью. Из того, что поток из пункта А в пункт В должен прохо­дить через каждое разделяющее сечение, вытекает, что максимально возможный поток не может превосходить пропускной способности ни одного из этих сечений.

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

Рассмотрим сеть, заданную на рис. 2.10. Требуется найти максимально возможный поток из узла 1 в узел 7.

Рис. 2.10

Вычислим пропускную способность ключевых сечений. Имеем:

пропускная способность сечения {(1,2), (1,3)} равна 4,

пропускная способность сечения {(2,4), (3,5)} равна 4,

пропускная способность сечения {(1,3), (2,3), (6,7)} равна 5,

пропускная способность сечения {(5,7), (6,7)} равна 2.

Сравнивая пропускные способности сечений, получаем, что мак­симальный поток от вершины 1 к вершине 7 равен 2.

Кратчайший маршрут

Дана сеть, каждое ребро которой помечено числом, равным его дли­не. Требуется найти кратчайший маршрут, ведущий от выделенного узла к каждому из узлов сети.

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

Рассмотрим сеть, заданную на рис. 2.11, с выделенным узлом 1.

Рис. 2.11

Прямой ход алгоритма

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

Ребро, связывающее узлы 1 и 3, является кратчайшим маршру­том от узла 1 к узлу 3 (любой другой маршрут от узла 1 к узлу 3 длиннее), и поэтому узлу 3 приписывается постоянная метка (15,1).

Таким образом, по окончании 1-го шага узлы 1 и 3 имеют посто­янные метки, узлы 2 и 4 — временные метки, а узлы 5, 6 и 7 никаких меток не имеют (рис. 2.13).

Замечание. При получении постоянной метки узел 3 выделяется так же, как и узел 1.

2-й шаг. Отбираются все узлы, которые соединены с узлом 3 од­ним ребром и не имеют постоянных меток. Это узлы 2, 4 и 6.

(20,1) Рис. 2.12

(20,1) Рис. 2.13

Сравнивая длины маршрутов 1-2 и 1-3-2, замечаем, что длина первого (20) меньше длины второго (15 + 10 = 25). Поэтому метка (20,1) узла 2 остается неизменной.

Сравнивая длины маршрутов 1-4 и 1-3-4, замечаем, что длина первого (25) больше длины второго (15 + 8 = 23). Поэтому временная метка (25,1) узла 4 меняется на метку (23,3).

Узел 6 получает метку (45,3).
Замечание. Первое число в метке указывает длину маршрута от уз­ла 1, а второе — номер предшествующего узла.

Ребро, связывающее узлы 1 и 2, является кратчайшим маршру­том от узла 1 к узлу 2 (любой другой маршрут от узла 1 к узлу 2 длиннее), и поэтому узлу 2 приписывается постоянная метка (20,1).

Таким образом, по окончании 2-го шага узлы 1, 2 и 3 имеют посто­янные метки, узлы 4 и 6 — временные метки, а узлы 5 и 7 никаких меток не имеют (рис. 2.14).

3-й шаг. Отбираются все узлы, которые соединены с узлом 2 од­ним ребром и не имеют постоянных меток. Это узлы 5 и 7.

Узел 5 получает метку (40,2).

Узел 7 получает метку (60,2).

Маршрут 1-3-4, связывающий узлы 1 и 4, является кратчайшим маршрутом от узла 1 к узлу 4 (любой другой маршрут от узла 1 к узлу 4 длиннее); поэтому узлу 4 приписывается постоянная метка (23,3).

Таким образом, по окончании 3-го шага узлы 1, 2, 3 и 4 имеют постоянные метки, а узлы 5, 6 и 7 — временные метки (рис. 2.15).


Рис. 2.14 Рис. 2.15

4-й шаг. Отбираются все узлы, которые соединены с узлом 4 од­ним ребром и не имеют постоянных меток. Это узел 6.

Сравнивая длины маршрутов 1-3-6 и 1-3-4-6, замечаем, что дли­ны первого (45) и третьего (45) больше длины второго (43). Поэтому временная метка (45,3) узла 6 меняется на метку (43,4).

Маршрут 1-2-5, связывающий узлы 1 и 5, является кратчайшим маршрутом от узла 1 к узлу 5 (любой другой маршрут от узла 1 к узлу 5 длиннее), и поэтому узлу 5 приписывается постоянная метка (40,2).

Таким образом, по окончании 4-го шага узлы 1, 2, 3, 4 и 5 имеют постоянные метки, а узлы 6 и 7 — временные метки (рис. 2.16).

Рис. 2.16

Рис. 2.17

Следующие два шага позволяют дать постоянные метки узлам 6 и 7 — (43,4) и (49,5) соответственно (рис. 2.17).

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

Обратный ход алгоритма

Используя вторую компоненту метки, определяем последователь­ность вершин в каждом кратчайшем маршруте. Например:

метка (49,5) узла 7 указывает на предшествующий узел 5,

метка (40,2) узла 5 указывает на предшествующий узел 2,

метка (20,1) узла 2 указывает на предшествующий узел 1.

В результате обратная последовательность узлов кратчайшего маршрута от узла 1 к узлу 7 имеет вид

Ответ:

Узел	Маршрут	Длина
2	1 - 2	20
3	1 - 3	15
4	1- 3- 4	23
5	1- 2- 5	40
6	1-	43
7	1	49

Критический путь