Лекции по "Экономике организации"

- Контур — замкнутый путь в орграфе.

- Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.

- Связный граф — граф, в котором все вершины связаны.

- Сильная связность. Две вершины в ориентированном графе сильно связаны, если существует путь из первой во вторую и из второй в первую.

Сильно связный орграф — орграф, в котором все вершины сильно связаны.

- Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных  ребер) является бинарной матрицей и  содержит нули на главной диагонали.

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

В случае ориентированного графа каждому  ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

- Дерево — связный граф, не содержащий циклов.

- Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.

 

- Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

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

 

Увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины  a в вершину b назовем допустимой, если выполняется одно из следующих условий:

 

1.      f(e) < c(e) и дуга согласованна

 

2.      f(e) > 0 и дуга несогласованна

 

По увеличивающей цепи можно  пустить поток величины Q, где Q = min{q(ei), 1 ≤ i ≤ l} и q(e) = {с(e) – f(e), если дуга согласованна, f(e), если дуга не согласованна}. Для того, чтобы увеличить величину потока сети на Q,  необходимо увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.

 

В своей работе [3] Форд и Фалкерсон (Ford and Fulkerson) доказали, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным.

 

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

 

Этап 1. Расстановка меток.

Все вершины получают статус непомеченных.

Процедура  расстановки меток.

Возьмем произвольный помеченный, но не просмотренный узел x. Пусть он имеет пометку [i, +, e(x)], где i – вершина из которой был помечен x; флаг, показывающий, что дуга (i,x) согласованна; e – величина потока, который можно пропустить по этой дуге. Рассмотрим все непомеченные смежные вершины y, такие что дуга (x, y) согласованна. Пометим вершину y меткой [x, +, e(y)], где e(y) = min{e(x) , c(x, y) – f(x, y)}. Затем рассмотрим все непомеченные смежные вершины y, соединенные с ней несогласованной дугой. Пометим их меткой [x, -, e(y)], где e(y) = min{e(x), f(y,x)}. Теперь все рассмотренные узлы y имеют статус помеченных, а узел x - просмотренный.

 

Эта общая для всех узлов сети процедура. Пометим источник меткой [~, ~, ∞] и будем последовательно вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только процедура будет вызвана для стока, будет получена увеличивающая цепь и следует перейти ко второму этапу. В противном случае процедура будет вызываться, пока все помеченные вершины не станут просмотренными, и если сток сети не был достигнут – увеличивающая цепь не может быть построена и по теореме Форда-Фалкерсона имеющийся поток сети является максимальным.

 

Этап 2. Изменение потока.

Процедура изменения потока дуги.

 Возьмем узел x.  Если он имеет метку [y, +, e], то увеличим поток по дуге (y, x) на e. Если он имеет метку [y, -, e], то уменьшим поток по дуге (y, x) на e. Если y не является источником, то вызовем процедуру для узла y.

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

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

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

 

Алгоритм Данцига

Этот алгоритм  отличается от алгоритма  Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 1 до n целыми числами и обозначим через di,jm длину пройденного пути из i в j где в качестве промежуточных использованы первые m вершин графа. Матрица Dm длин кратчайших путей имеет здесь размерность m*m.

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

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1} (1)

2. Кратчайший путь из вершины m в j, в котором допускаются первые m промежуточных вершин, должен иметь в своей первой части дугу из вершины m в некоторую вершину k, a во второй – кратчайший путь из вершины k в j .

dm,jm=min{d0m,k+ dm-1k,j} k=1…m-1 (2)

3. Кратчайший путь из вершины  i в m, в котором допускается первых m промежуточных вершин. Имеет своей первой частью кратчайший путь из вершины i в некоторую промежуточную вершину k. А во второй – кратчайшую дугу из k в m.

di,mm=min{dm-1i,k+ d0k,m} k=1…m-1 (3)

4. диагональный элемент матрицы  равен 0.

Алгоритм Данцига.

Перенумеровать  вершины графа, определить матрицу D0 размером n*n  где n число вершин графа. Каждый элемент этой матрицы есть длина кратчайшей дуги от одной вершины до другой.

Для каждого m принимающего значения 1,2,3…N определить матрицу Dm по формулам (2) – для строки m, (3) – для столбца m, (1) – для всех остальных элементов, кроме диагонального (di,im=0).

 

Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур:

1) Процедура помечивания вершин

2) Процедура изменения потока

 

1) Процедура помечивания вершин.

Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:

- если дуга направлена из  i в j и поток по этой дуге (fij) меньше пропускной способности дуги (cij), то вершине j присваивается метка (i+,min(e,cij-fij))

- если дуга направлена из  j в i и поток по этой дуге (fji) больше нуля, то вершине j присваивается метка (i-,min(e,fji))

Эта процедура всегда начинается с  помечивания и обработки истока. Он помечается особой меткой (-,¥). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д.

Процесс помечивания заканчивается в двух случаях:

 

1) Ни одну вершину больше нельзя  пометить, но сток не помечен.  Это значит, что найденный поток  - максимальный и алгоритм останавливается.

2) Помечается сток. В этом случае  производится изменение потока.

 

2) Процедура изменения потока.

Если сток получил метку (k+,d), то потоки будут изменяться на величину d следующим образом:

- если мы находимся в вершине  j с меткой (i+,x), то прибавляем d к fij и переходим в вершину i.

- если мы находимся в вершине  j с меткой (i-,x), то вычитаем d из fij и переходим в вершину i.

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

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

Задачи распределения  ресурса на сетях удобно рассматривать, изображая операции вершинами сети, а зависимости – дугами (представления «операции-дуги, события-вершины» и «зависимости-дуги, операции-вершины» эквивалентны [10]). Пунктиром могут быть отражены ресурсные зависимости – когда для выполнения одних и тех же операций должны быть использованы одни и те же ресурсы. Примером могут являться сети, изображенные на рисунках 6 и 7. Полным резервом операции (i; j) называется вели-

чина Dij = п

ij t – р

ij t , где п

ij t – поздний срок начала (окончания) опе-

рации, а р

ij t – ранний срок начала (окончания) операции.

Для определения оптимального распределения ресурса необходимо найти критические пути для каждого из вариантов распределения ресурса и сравнить длины этих путей (в сети, приведенной на рисунке 7, существует общий для операций «0-1» и «0-2» ресурс; потенциалы вершин, соответствующие различным способам использования этого ресурса – сначала выполняется операция «0-1», затем «0-2» и наоборот, приведены на рисунке 7 соответственно в квадратных скобках и без скобок).

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

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

выполняться одновременно.

 

Легко показать, что в рассматриваемом  примере оптимально выполнять первой операцию с минимальным t i.

Если для выполнения проекта выделено ограниченное количество ресурса, то возникает задача наилучшего его использования.

Обозначим wi – объем i-ой операции, fi(vi) – скорость ее выполнения в зависимости от количества ресурса vi. Предположим, что fi(×)– непрерывная справа неубывающая функция, причем fi(0) = 0.

Если vi(t) – количество ресурса на i-ой операции в момент времени t, то момент ti ее окончания определяется как минимальное время,

удовлетворяющее уравнению:

(5)

Если количество ресурса, используемое при выполнении некоторой операции, не изменяется во времени, то говорят, что она выполняется с постоянной интенсивностью.

Обширный класс задач КСПУ составляют задачи агрегирования – представления  комплекса операций (проекта) в виде одной операции и исследования свойств таких представлений, для которых оптимизация в рамках агрегированного описания дает решение, оптимальное для исходного (детального) описания.

 

Метод динамического программирования для многошаговых задач принятия решений. Принцип оптимальности  Беллмана. Основное функциональное уравнение. Вычислительная схема метода динамического  программирования.

 

 Предмет и основные  понятия теории игр. Применение  теории игр для оптимизации  управленческих решений. Понятие  стратегии и решения игры. Равновесия: в доминантных стратегиях, максиминное, Нэша, Байеса, Штакельберга. Матричные игры. Игры с непротиворечивыми интересами. Кооперативные игры.

 

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

 

 Методы многокритериальной  оценки альтернатив. Классификация  методов. Множества компромиссов  и согласия, построение множеств. Функция полезности. Аксиоматические  методы многокритериальной оценки. Прямые методы многокритериальной  оценки альтернатив. Методы нормализации  критериев. Характеристики приоритета  критериев. Постулируемые принципы  оптимальности: равномерности, справедливой  уступки, главного критерия, лексикографический. Методы аппроксимации функции полезности. Деревья решений. Методы компенсации. Методы аналитической иерархии. Методы порогов несравнимости. Диалоговые методы принятия решений. Качественные методы принятия решений (вербальный анализ).

 

 Принятие решений  в условиях неопределенности. Виды  неопределенности. Статистические  модели принятия решений. Критерии  Байеса—Лапласа, Гермейера, Бернулли—Лапласа, максиминный (Вальда), минимаксного риска Сэвиджа, Гурвица, Ходжеса—Лемана и др.

 

 Принятие коллективных  решений. Теорема Эрроу и ее анализ. Правила большинства, Кондорсе, Борда. Парадокс Кондорсе. Расстояние в пространстве отношений. Современные концепции группового выбора.

 

 Модели и методы  принятия решений при нечеткой  информации. Нечеткие множества.  Основные определения и операции  над нечеткими множествами. Нечеткое  моделирование. Задачи математического  программирования при нечетких  исходных условиях. Нечеткие отношения,  операции над отношениями, свойства  отношений. Принятие решений при  нечетком отношении предпочтений  на множестве альтернатив. Принятие  решений при нескольких отношениях  предпочтения.