Алгоритм получения максимальной матрицы смежности (матрицы достижимости)

• 1. Полагают i = 1. Присваивают dtj = atj для всех i = 1, п;;' = 1, п.
• 2. В строке с номером i матрицы D отыскивают элемент d" -1.
• 3. Строка i матрицы D по правилам булевой алгебры складывается со строкой; матрицы, А поэлементно di; = da ® ?, 7, 1 = 1, ?. Правила сложения булевой алгебры:

• 4. Элемент d,•, отмечают символом
• 5. Вновь просматривают строку i матрицы D с целью определения неотмеченного элемента. Таким элементом может быть и ненулевой элемент, получившийся после сложения на шаге 3. Если новый ненулевой элемент найден, то переход к шагу 3; в противном случае — переход к шагу 6.
• 6. Если i = п, то искомая матрица получена. В противном случае i = i + 1; переход к шагу 2.

На основе матрицы смежности (см. табл. 7.3) проведем расчет матрицы достижимости. Формируемая матрица достижимости, в которой выполнен расчет первой строки, представлена в табл. 7.4, а в табл. 7.5 окончательно определена матрица достижимости.

Таблица 7.4. Формируемая матрица достижимости, в которой проведен расчет первой строки вершин.

Таблица 7.5. Матрица достижимости.

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

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

Алгоритм поиска сложных контуров (автоматов) в орграфе

• 1. Положим? = 1; т = п.
• 2. Проверка: du = 1? Если «да», то переход к шагу 5; в противном случае — переход к шагу 3.
• 3. Проверка: i = т? Если «да», то решение закончено, автоматов в графе нет. В противном случае — переход к шагу 4.
• 4. Положим i = i + 1. Переход к шагу 2.
• 5. Найти произведение W, = d;, d", 1 = 1, т.
• 6. Ненулевые компоненты вектора W стоят на местах, соответствующих номерам вершин орграфа, входящих в автомат. Пусть количество ненулевых элементов в векторе W равно п.
• 7. Вычеркнуть из матрицы D строки и столбцы, соответствующие вершинам, входящим в выявленный автомат. Новая размерность матрицы D будет п.
• 8. Если п = 0, то решение закончено — все вершины вошли в определенные выше автоматы. В противном случае — переход к шагу 1.

Продолжим анализ орграфа, приведенного на рис. 7.5. В матрице достижимости (см. табл. 7.5) элемент dl, = 1. Находим произведение первой строки и первого столбца матрицы: W = (1, 0,1,1,1).

Ненулевые элементы в векторе стоят на первом, третьем, четвертом и пятом местах, следовательно, вершины Ег, Е3, Ел, Еъ входят в сложный контур (автомат). Если вычеркнуть строки 1, 3,4, 5 из матрицы D, то получится матрица, состоящая из одного элемента (размерностью п = 1), равного нулю. Поиск автоматов закончен. Единственная вершина, которая не входит в автомат, — Е2.

При анализе многокомпонентных задач, в основе которых лежат ориентированные графы, чрезвычайно важной оказывается поиск всех контуров. Для решения этой задачи можно использовать достаточно простой алгоритм, в основе которого лежит знание матрицы смежности и матрицы достижимости орграфа. Для решения задачи определения всех контуров в графе можно воспользоваться, например, модифицированным алгоритмом Джонсона^[1].

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

Построенную модель можно сделать более информативной, если дугам орграфа приписать знак «+» или «-». Знак «+» ставится в том случае, если при увеличении значения показателя, от которого идет дуга, показатель, к которому дуга приходит, увеличивается; при уменьшении показателя, от которого идет дуга, показатель, к которому дуга приходит, уменьшается.

В этом случае между показателями имеется прямо пропорциональная зависимость. Знак «-» ставится в случае, если между показателями имеется обратно пропорциональная зависимость.

Полученный орграф называется знаковым; поскольку на дугах знакового орграфа стоит «+1» или «-1», то этот коэффициент обозначим e}i.

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

Рис. 7.6. Варианты простых контуров обратной связи: а — две положительные дуги; б — две отрицательные дуги; в — дуги с разными знаками Для того чтобы продемонстрировать взаимодействие показателей в контуре, целесообразно рассмотреть простейший пример системы, состоящей из двух вершин, соединенных дугами. Рассмотрим граф на рис. 7.6, а.

Шаг 1. Пусть показатель 1 увеличится, тогда (поскольку ei2 = +1) показатель 2 также возрастет.

Шаг 2. Изменение показателя 2 вызывает рост показателя 1 в соответствии с действием обратной связи (е21 = +1).

Шаг 3. Рост показателя 1 в свою очередь вызывает еще больший рост показателя 2.

Шаг 4. Рост показателя 2 вызывает рост показателя 1 и т. д.

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

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

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

Моделирование изменения показателей проводится по шагам S = 1, 2, … Начальные значения показателей в вершинах орграфа принимаются равными К,(0), i e G. Необходимо определить последовательность значений показателей i: V,(S), S = 1, 2,… и изучить тенденции изменения каждого из рассматриваемых показателей. В имеющемся знаковом или взвешенном орграфе каждая дуга (i, j) e G имеет коэффициент ai)} причем если это знаковый орграф, то этот коэффициент равен +1 или -1, а если это взвешенный орграф, то данный коэффициент принимает определенное числовое значение со своим знаком. Для любого шага моделирования значение показателя в вершине i можно определить по формуле.

где Pj (S) — импульс,

На практике возможны различные варианты реализации приведенной выше формулы расчета значений показателей на базе импульсов (табл. 7.6).

Таблица 7.6. Варианты формул для расчета значений показателей орграфа на базе импульсов.

№. п/п.	Формула Комментарий.
		Смысл весового коэффициента — изменение показателя i при изменении показателя j на единицу. Изменения показателя накапливаются.
		Смысл весового коэффициента — перевод из одного масштаба измерения в другой. Импульс в явном виде не учитывается.
		Перевод из одного масштаба измерения в другой. Импульс в явном виде не учитывается. Изменения показателя накапливаются.
		Смысл весового коэффициента — насколько изменится показатель i при изменении показателя) на 1%. Изменения показателя накапливаются.
		Показатель определяется по «узкому месту». Накопления значений показателя нет.
		Показатель определяется по «узкому месту». Изменения показателя накапливаются.

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

где V;-(S) — значение вершины (показателя) i на шаге S; P;(S) — изменение значения вершины i на шаге t;

Орграф, отражающий взаимосвязь ряда факторов, которые определяют добычу природного ресурса, представлен на рис. 7.7. Цена на рассматриваемый природный ресурс связана с объемом продаж. Возрастание цены приводит к сокращению продаж, а рост продаж — к возрастанию цены. Заметим, что прибыль добывающих компаний зависит от роста цены и объема продаж природного ресурса. Рост прибыли влияет на увеличение добычи природного ресурса. Вместе с тем рост цены на природный ресурс стимулирует использование замещающего ресурса, что приводит к снижению объема продаж. Указанные рассуждения позволяют построить орграф для проведения имитационного моделирования (см. рис. 7.7).

Рис. 7.7. Знаковый орграф анализа добычи природного ресурса Воспользовавшись построенным орграфом, можно провести имитационные расчеты результата воздействия внешнего импульса на один или одновременно несколько показателей модели. Рассмотрим последствия увеличения добычи природного ресурса. На нулевом шаге S = 0 значения всех показателей модели и их импульсы приняты на уровне нуля (табл. 7.7). Добыча природного ресурса принимается равной единице, импульс также принимается равным единице.

Импульс, равный единице, передается от показателя «Добыча природного ресурса» показателю «Объем продаж» на шаге S = 1. Значение объема продаж на предыдущем шаге равно нулю, т. е. V2(0) = 0. Поскольку на дуге от показателя 3 «Добыча природного ресурса» к показателю 2 «Объем продаж» стоит единица, то для расчета принимается значение e3j2 = l• Формула расчета значения «Объем продаж» на шаге S = 1 принимает следующий вид:

Занесем это значение показателя «Объем продаж» на шаге S = 1 в табл. 7.7. Поскольку остальные показатели не пересчитываются, то их значения переносятся из предыдущего шага без изменений. Импульсы рассчитываются как разность между значениями соответствующих показателей, взятых на данном и предшествующем шагах.

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

Таблица 7.7. Расчет динамики показателей на основе имитационной модели на знаковом орграфе.

Показатель i	Значения показателей по шагам моделирования S
1. Цена на природный ресурс.										— 1.
2. Объем продаж.								— 1.
3. Добыча природного ресурса.
4. Объем замещения природного ресурса.
5. Прибыль добывающих компаний.										— 1.

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

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

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

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

При оценке коэффициентов методом наименьших квадратов система разбивается на множество подсистем, включающих в себя рассматриваемый показатель и непосредственно влияющие на него показатели, причем каждая пригодна для определения дисперсии единственной зависимой переменной через дисперсии и ковариации ее причин. В рассматриваемой подсистеме исследуются только непосредственные причины зависимой переменной, а связи между этими причинами суммируются ковариационными членами^[2]. Кроме того, коэффициенты петли нельзя оценить обычным методом наименьших квадратов. В этом случае целесообразно использовать двухэтапный метод наименьших квадратов, разработанный в середине 1950;х гг. Г. Тейлом^[3].

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

Для иллюстрации функционирования модели на основе взвешенного орграфа воспользуемся моделью, приведенной на рис. 7.9.

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

Таблица 7.8. Результаты моделирования изменения показателей рыночного механизма при активизации показателя продаж продукции.

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

Различают абсолютную и импульсную устойчивость.

Абсолютная устойчивость предполагает ограниченность значений в последовательности

Импульсная устойчивость предусматривает ограниченность значений в последовательности

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

Взвешенный орграф находится в состоянии абсолютного равновесия, если

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

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

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

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

Следующие два определения следует использовать последовательно: если выполняется утверждение 2 и установлен факт импульсной устойчивости, то следует проверить утверждение 3 и попытаться установить факт абсолютной устойчивости.

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

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

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

Для характеристики устойчивости контура целесообразно использовать частный критерий устойчивости U, который рассчитывается по формуле.

где? — множество дуг, составляющих простой контур орграфа.

Варианты оценок простого контура с помощью данного критерия устойчивости приведены в табл. 7.9.

Таблица 7.9. Оценка простого контура с помощью частного критерия устойчивости.

Значение критерия U	Устойчивость орграфа.		Достижимость состояния.
	импульсная.	абсолютная.	импульсная.	абсолютная.
		;		;
			;	;
	;	;	;	;
	;	;	;	;

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

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

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

Для более точного отражения нелинейной зависимости между показателями следует перейти от взвешенного орграфа к функциональному. В функциональном орграфе дугам ставится в соответствие вместо знака или весового коэффициента функциональная зависимость.

Дуге 0, 0 можно поставить в соответствие широкий набор функциональных зависимостей/ [V (S)]:

• • линейную зависимость ;
• • квадратичную зависимость ;
• • гиперболическую зависимость ;
• • логарифмическую зависимость ;
• • обратную гиперболическую зависимость

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

Таким образом, при решении многочисленных задач социоэколого-экономического развития необходимо учитывать так называемые параллелепипедные ограничения:

Для того чтобы учесть такие ограничения, следует видоизменить расчетную формулу импульсного процесса следующим образом:

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

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

Еще один подход, основанный на имитационном подходе, который часто используется при прогнозировании цен, — сценарный подход. Наиболее распространена разработка трех сценариев:

• 1) низких цен;
• 2) слабого повышения цен;
• 3) высоких цен.

В последнем прогнозе компании Shell о развитии мировой энергетики до 2050 г. было использовано два сценария: Scramble (схватка, борьба за выживание) и Blueprlnts (программа, проект, моделирование).

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

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

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

• [1] Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985.
• [2] Хейс Д. Причинный анализ в статистических исследованиях. М.: Мир, 1981.
• [3] Чепурных Н. В., Новоселов А. Л. Экономика и экология: развитие, катастрофы. М.: Наука, 1996.