Что такое матричный анализ затрат. Матричные методы стратегического анализа

Исторически первой моделью корпоративного стратегического планирования принято считать так называемую модель «роста - доли», которая больше известна как модель Бостонской консалтинговой группы (BCG).

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

Появление модели BCG явилось логическим завершением одной исследовательской работы, проведенной в свое время специалистом консалтинговой компании Boston Consulting Group.

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

Также было установлено, что эта тенденция имеет место почти в любом рыночном секторе.

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

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

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

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

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

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

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

  • 1) увеличение доли бизнеса организации на рынке;
  • 2) борьба за сохранение доли бизнеса организации на ранке;
  • 3) максимальное использование положения бизнеса на рынке;
  • 4) освобождение от данного вида бизнеса.

Решения, которые предполагает модель BCG, зависят от положения конкретного вида бизнеса организации, стратегическом пространстве, образуемом двумя координатными осями. Использование этого параметра в модели BCG возможны по 3 причинам:

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

повышенные темпы роста рынка воздействуют на объем денежной наличности со знаком «-» даже в случае довольно высокой нормы прибыли, так как требует повышенных инвестиций в развитие бизнеса.

Существует две модели BCG: классическая и адаптированная. Рассмотрим Классическую модель:

Структура Классической модели:

На оси абсцисс выставляется измерение некоторых конкурентных позиций организации в данном бизнесе в виде отношения объемов продаж организации в данном бизнесе к объему продаж крупнейшего в данной бизнес - области конкурента.

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

Каждая нанесенная окружность характеризует только 1 бизнес - область, характерную для данной организации.

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

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

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

В оригинальной модели BCG принято, что границей высоких и низких темпов роста является 10% увеличения продаж в год.

Каждому из этих квадратов даются образные названия (например: матрицу BCG называют «Зоопарком»).

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

«Дойные коровы»: это бизнес - области, которые в прошлом получили относительно большую долю рынка, однако со временем рост соответствующей отрасли заметно замедлился, поток денежной наличности в этой позиции хорошо сбалансирован, поскольку для инвестиций в такую бизнес - область требуется самый необходимый минимум. Такая бизнес - область может принести хороший доход организации (Это бывшие «Звезды»).

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

«Собаки»: это бизнес - области с относительно небольшой долей на рынке в медленно развивающихся отраслях. Поток денежной наличности незначителен, порой даже отрицателен.

Но не многие используют Классическую модель, так как она непрактична из-за необходимости получения актуальных данных о состоянии рынка и доли, занимаемой компанией и ее конкурентом. Поэтому для расчетов используем

Адаптированную модель:

Адаптированная матрица BCG строится на основе внутренней информации компании. Необходимые данные - объемы продаж продукции за определенный период, который не может быть менее 12 месяцев, в дальнейшем, для отслеживания динамики, необходимо добавлять данные за следующие 3 месяца (т.е. данные за 12, 15, 18, 21, 24 месяца). Данные необязательно должны начинаться с января месяца, но должны быть по месяцам. Также важно учитывать сезонность продаж товаров или услуг для продукции вашей компании. В рассматриваемой компании товарный портфель состоит из 5 групп товаров, а также имеются данные об их продажах за период январь - декабрь 2013г.

Таблица 5. Данные по продажам предприятия ООО НордВест

– умножив вес на оценку и просуммировав полученные значения по всем факторам, получим взвешенную оценку / рейтинг привлекательности рынка

Таблица 7. Оценка привлекательности отрасли

Таблица 8. Оценка конкурентной позиции в отрасли

2 .Строим Матрицу Мак - Кинси для ООО Норд-Вест

По оси x откладываем 3,6 балла, по оси у откладываем 2,9 балла. На пересечении данных баллов мы попадаем в квадрат «Успех 3». Который присущ организациям, рыночная привлекательность которых держится на среднем уровне, но при этом их преимущества на данном рынке очевидны и сильны. Стратегические выводы из анализа на основе матрицы McKinsey очевидны: компания ООО Норд-Вест "попадает в квадрат «Успех 3»

Рис. 4. Матрица Мак-Кинси

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


Керамическая плитка

Ячеистый бетон


Крупно форматный кирпич

Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter

Курс лекций по дисциплине

«Матричный анализ»

для студентов II курса

математического факультета специальности

«Экономическая кибернетика»

(лектор Дмитрук Мария Александровна)

Глава 3. Функции от матриц.

  1. Определение функции.

Df. Пусть функция скалярного аргумента. Требуется определить, что понимать под f(A), т.е. нужно распространить функцию f(x) на матричное значение аргумента.

Решение этой задачи известно, когда f(x) многочлен: , тогда.

Определение f(A) в общем случае.

Пусть m(x) минимальный многочлен А и он имеет такое каноническое разложение, собственные значения А. Пусть многочлены g(x) и h(x) принимают одинаковые значения.

Пусть g(A)=h(A) (1), тогда многочлен d(x)=g(x)-h(x) аннулирующий многочлен для А, так как d(A)=0, следовательно, d(x) делится на линейный многочлен, т.е. d(x)=m(x)*q(x) (2).

Тогда, т.е. (3), .

Условимся m чисел для f(x) таких называть значениями функции f(x) на спектре матрицы А, а множество этих значений будем обозначать.

Если множество f(Sp A) определено для f(x), то функция определена на спектре матрицы А.

Из (3) следует, что многочлены h(x) и g(x) имеют одинаковые значения на спектре матрицы А.

Наши рассуждения обратимы, т.е. из (3) (3) (1). Таким образом, если задана матрица А, то значение многочлена f(x) вполне определяется значениями этого многочлена на спектре матрицы А, т.е. все многочлены gi(x), принимающие одинаковые значения на спектре матрицы имеют одинаковые матричные значения gi(A). Потребуем, чтобы определение значения f(A) в общем случае подчинялось такому же принципу.

Значения функции f(x) на спектре матрицы А должны полносильно определить f(A), т.е. функции, имеющие одни и те же значения на спектре должны иметь одно и то же матричное значение f(A). Очевидно, что для определения f(A) в общем случае, достаточно найти многочлен g(x), который бы принимал те же значения на спектре А, что и функция f(A)=g(A).

Df. Если f(x) определена на спектре матрицы А, то f(A)=g(A), где g(A) многочлен, принимающий на спектре те же значения, что и f(A),

Df. Значением функции от матрицы А назовем значение многочлена от этой матрицы при.

Среди многочленов из С[x], принимающих одинаковые значения на спектре матрицы А, что и f(x), степени не выше (m-1), принимающий одинаковые значения на спектре А, что и f(x) это остаток от деления любого многочлена g(x), имеющего те же значения на спектре матрицы А, что и f(x), на минимальный многочлен m(x)=g(x)=m(x)*g(x)+r(x).

Этот многочлен r(x) называют интерполяционным многочленом Лагранжа-Сильвестра для функции f(x) на спектре матрицы А.

Замечание. Если минимальный многочлен m(x) матрицы А не имеет кратных корней, т.е. , то значение функции на спектре.

Пример:

Найти r(x) для произвольной f(x), если матрица

. Построим f(H 1 ). Найдем минимальный многочлен H 1 последний инвариантный множитель :

, d n-1 =x 2 ; d n-1 =1;

m x =f n (x)=d n (x)/d n-1 (x)=x n 0 n кратный корень m(x), т.е. n-кратные собственные значения H 1 .

, r(0)=f(0), r (0)=f (0),…,r (n-1) (0)=f (n-1) (0) .

  1. Свойства функций от матриц.

Свойство № 1. Если матрица имеет собственные значения (среди них могут быть и кратные), а, то собственными значениями матрицы f(A) являются собственные значения многочлена f(x): .

Доказательство:

Пусть характеристический многочлен матрицы А имеет вид:

Посчитаем. Перейдем от равенства к определителям:

Сделаем замену в равенстве:

Равенство (*) справедливо для любого множества f(x), поэтому заменим многочлен f(x) на, получим:

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

ЧТД.

Свойство № 2. Пусть матрица и собственные значения матрицы А, f(x) произвольная функция, определенная на спектре матрицы А, тогда собственные значения матрицы f(A) равны.

Доказательство:

Т.к. функция f(x) определена на спектре матрицы А, то существует интерполяционный многочлен матрицы r(x) такой, что, а тогда f(A)=r(A), а у матрицы r(A) собственными значениями по свойству № 1 будут которым соответственно равны.

ЧТД.

Свойство № 3. Если А и В подобные матрицы, т.е. , и f(x) произвольная функция, определенная на спектре матрицы А, тогда

Доказательство:

Т.к. А и В подобны, то их характеристические многочлены одинаковы одинаковы и их собственные значения, поэтому значение f(x) на спектре матрицы А совпадает со значение функции f(x) на спектре матрицы В, при чем существует интерполяционный многочлен r(x) такой, что f(A)=r(A), .

ЧТД.

Свойство № 4. Если А блочно-диагональная матрица, то

Следствие: Если, то, где f(x) функция, определенная на спектре матрицы А.

  1. Интерполяционный многочлен Лагранжа-Сильвестра.

Случай № 1.

Пусть дана. Рассмотрим первый случай: характеристический многочлен имеет ровно n корней, среди которых нет кратных, т.е. все собственные значения матрицы А различны, т.е. , Sp A простой. В этом случае построим базисные многочлены lk(x):

Пусть f(x) функция, определенная на спектре матрицы А и значениями этой функции на спектре будут. Надо построить.

Построим:

Обратим внимание, что.

Пример: Построить интерполяционный многочлен Лагранжа-Сильвестра для матрицы .

Построим базисные многочлены:

Тогда для функции f(x), определенной на спектре матрицы А, мы получим:

Возьмем , тогда интерполяционный многочлен

Случай № 2.

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

Случай № 3.

Рассмотрим общий случай. Пусть минимальный многочлен имеет вид:

где m1+m2+…+ms=m, deg r(x)

Составим дробно-рациональную функцию:

и разложим ее на простейшие дроби.

Обозначим: . Умножим (*) на и получим

где некоторая функция, не обращающаяся в бесконечность при.

Если в (**) положить, получим:

Для того, чтобы найти ak3 надо (**) продифференцировать дважды и т.д. Таким образом, коэффициент aki определяется однозначно.

После нахождения всех коэффициентов вернемся к (*), умножим на m(x) и получим интерполяционный многочлен r(x), т.е.

Пример: Найти f(A), если , где t некоторый параметр,

Проверим, определена ли функция на спектре матрицы А

Умножим (*) на (х-3)

при х=3

Умножим (*) на (х-5)

Таким образом, - интерполяционный многочлен.

Пример 2.

Если , то доказать, что

Найдем минимальный многочлен матрицы А:

- характеристический многочлен.

d 2 (x)=1, тогда минимальный многочлен

Рассмотрим f(x)=sin x на спектре матрицы:

функция является определенной на спектре.

Умножим (*) на

.

Умножим (*) на :

Вычислим, взяв производную (**):

. Полагая ,

, т.е. .

Итак, ,

Пример 3.

Пусть f(x) определена на спектре матрицы, минимальный многочлен которой имеет вид . Найти интерполяционный многочлен r(x) для функции f(x).

Решение: По условию f(x) определена на спектре матрицы А f(1), f (1), f(2), f (2), f (2) определены.

Используем метод неопределенных коэффициентов:

Если f(x)=ln x

f(1)=0 f (1)=1

f(2)=ln 2 f (2)=0.5 f (2)=-0.25

4. Простые матрицы.

Пусть матрица, так как С алгебраически замкнутое поле, то ха

Задание 1

Вычислить сумму матриц kA+mB, если

Элементы матрицы суммы определяются по формуле:

cij=kaij+mbij .

Вычислим элементы первой строки матрицы суммы:

С11=-4 * 2+5 * 3=7

С12=-4 * (-1)+5 * 7=39

С13=-4 * 4+5 * (-2)=-26

С21=-4 * 6+5 * 9=21

С22=-4 * 3+5 * 1=-7

С23=-4 * 0+5 * 6=30

С31=-4 * (-7)+5 * (-4)=8

С32=-4 * 5+5 * 8=20

С33=-4 * 9+5 * 5=-11

Таким образом, матрица суммы примет вид:

Задание 2

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

Используем алгоритм нахождения обратной матрицы:

  • 1. Матрица квадратная (число строк равно числу столбцов), следовательно, обратная к ней матрица существует.
  • 2. Находим определитель исходной матрицы:
  • ?А=-3 * 3 * 3+1 * (-5) * 1+0 * (-4) * 3-1 * 3 * 3-(-4) * 1 * 3-0 * (-5) * (-3)=-29 ? 0
  • 3. Находим матрицу, состоящую из алгебраических дополнений элементов исходной матрицы:

А11=(-1) 2 * 3 * 3-0 * (-5)=-9

А12=(-1) 3 * -4 * 3-1 * (-5)=7

А13=(-1) 4 * -4 * 0-1 * 3=-3

А21=(-1) 3 * 1 * 3-0 * 3=-3

А22=(-1) 4 * -3 * 3-1 * 3=-12

А23=(-1) 5 * -3 * 0-1 * 1=1

А31=(-1) 4 * 1 * (-5)-3 * 3=-14

А32=(-1) 5 * -3 * (-5)-(-4) * 3=-27

А33=(-1) 6 * -3 * 3-(-4) * 1=-5

Таким образом, получаем матрицу:

4. Полученную матрицу транспонируем:

5. Последнюю матрицу делим на определитель исходной матрицы и получаемобратную матрицу:

6. Осуществляем проверку полученного результата. Для этого находим произведение полученной матрицы на исходную:

А -1 .* А=А * А -1 =*= ==


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

Задание 3

Решить систему линейных уравнений методом Крамера, Гаусса.

Решение:

1)Решить систему методом Крамера.

Составляем матрицу системы:

Вычисляем определитель этой матрицы:

0 * (-8) * 4+3 * 2 * (-5)+7 * 2 * 9-9 * (-8) * (-5)-3 * 7 * 4-0 * 2 * 2=-348?0

Находим определители?1 , ?2, ?3, получающиеся из исходного определителя заменой соответственно первого, второго и третьего столбцов столбцомсвободных членов:

1==2 * (-8) * 4+3 * 2 * (-3)+9 * 5 * 2-9 * (-8) * (-3)-3 * 5 * 4-2 * 2 * 2=-276

2==0 * 5 * 4+2 * 2 * (-5)+9 * 7 * (-3)-9 * 5 * (-5)-2 * 7 * 2-0 * 2 * (-3)=- 40

3==0 * (-8) * (-3)+3 * 5 * (-5)+2 * 7 * 2-2 * (-8) * (-5)-3 * 7 * (-3)-0 * 5 * 2=- 64

Теперь используя формулы Крамера

х1=, х2=, х3= ,

находим решение системы:

Х1==,=0,79 х2==,=0,11 х3===0,18

2) Решим систему методом Гаусса.

Составляем расширенную матрицу системы, в которую входят коэффициенты при переменных и свободные члены:

Умножим 2-ую строку на (5). Умножим 3-юу строку на (7). Добавим 3-ую строку к 2-ой:

Умножим 1-ую строку на (26). Умножим 2-ую строку на (3). Добавим 2-ую строку к 1-ой:

Из 1-ой строки выражаем x 3

Из 2-ой строки выражаем x 2

26х 2 =- +4=0,11

Из 3-ой строки выражаем x 1

5х 1 =-2 * 0,11- - 3=0,79

Задание 4

матрица определитель линейный крамер гаусс

Вычислить определитель 4-го порядка

Запишем разложение определителя по четвертой строке:

А==0 * А 41 +3 * А 42 +0 * А 43 +1 * А 44

где Aij - алгебраическое дополнение элемента ij a .

Найдем алгебраические дополнения по формуле А ij =(-1) i+j , где m ij - минор элемента ij a, который получается из исходного определителя вычеркиванием строки и столбца, на пересечении которых стоит данный элемент.

А 42 =(-1) 4+2 * m 42 =(-1) 6 * =4 * 7 * (-9)+7 * (-7) * 0+1 * (-1) * 0 - 0 * 7 * 0 - 7 * 1 * (-9) - 4 * (-7) * (-1)=-217

А 44 =(-1) 4+4 * m 44 =(-1) 8 * =4 * (-3) * (-1)+0 * 7 * 0+1 * 1 * 7-7 * (-3) * 0-0 * 1 * (-1)-4 * 7 * 1=-9

Подставляем полученные значения в разложение определителя:

3 * А 42 +А 44 =3 * (-217)+(-9)=-660

Задание 5

матрица обратный определитель линейный крамер гаусс

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

Задача.

Затраты трех видов сырья А, B, C на производство единицы каждого из трех типов продукции I, II, III и запасы каждого вида сырья заданы в таблице (Таблица 1):

Таблица 1

Продукция

Вид сырья

Запасы сырья

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

Запишем систему линейных уравнений, используя данные, приведенные в таблице:

где - объемы выпускаемой продукции каждого вида.

Для решения воспользуемся методом Гаусса. Запишем расширенную матрицу системы:

Запишем систему в виде расширенной матрицы:

Умножим 2-ую строку на (-2). Добавим 2-ую строку к 1-ой:

Умножим 2-ую строку на (3). Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Умножим 1-ую строку на (2). Добавим 2-ую строку к 1-ой:

Теперь исходную систему можно записать как:

x 2 = /2

x 1 = /3

Из 1-ой строки выражаем x 3

Из 2-ой строки выражаем x 2

Из 3-ой строки выражаем x 1

Второй подход к анализу сетей Петри основан на матричном представлении сетей Петри. Альтернативным по отношению к опре­делению сети Петри в виде (Р, Т, I, О) является определение двух матриц D - и D + , представляющих входную и выходную функции. Каждая матрица имеет m строк (по одной на пе­реход) и n столбцов (по одному на позицию). Определим D - = #(p i , I(t j)), a D + = #(p i , O(t j)). D - определяет входы в переходы, D + - выходы.

Матричная форма определения сети Петри (Р, Т, D - , D +) экви­валентна стандартной форме, используемой нами, но позволяет дать определения в терминах векторов и матриц. Пусть e[j] - m-вектор, содержащий нули везде, за исключением j-й компоненты, равной единице. Переход t j представляется m-вектором-строкой е[j].

Теперь переход t j в маркировке µ разрешен, если µ > e[j] D - , а результат запуска перехода t j в маркировке µ, записывается как:

δ(t j) = µ - e[j] D - + e[j] D + = µ + e[j] D

где D = D + - D - - составная матрица изменений.

Тогда для последовательности запуска переходов σ = t j 1 , t j 2 , … , t jk имеем:

δ(σ) = µ + e D + e D + … + e D =

= µ + (e + e + … + e)D = µ + f(σ) D

Вектор f(σ) = e + e + ... + e называется вектором за­пусков последовательности σ = t j 1 , t j 2 , … , t jk , f(σ) j p - это число запусков перехода t p в последовательности t j 1 , t j 2 , … , t jk . Вектор запусков f(σ), следовательно, является вектором с неотри­цательными целыми компонентами. (Вектор f(σ) - это отображение Париха последовательности σ = t j 1 , t j 2 , … , t jk).

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

Пусть w = (w 1 ,w 2 , … , w n) - вектор-столбец. Тог­да, если µ - начальная маркировка, а µ" - произвольная дости­жимая маркировка, т.е. µ" принадлежит R(C,µ), необходимо, чтобы µ w = µ" w. Теперь, поскольку µ" достижима, существует последовательность запусков переходов σ = t j 1 , t j 2 , … , t jk , которая переводит сеть из µ в µ". Поэтому

µ" = µ + f(σ) D

Следовательно,

µ w = µ" w = (µ + f(σ) D) w = µ w + f(σ) D w, поэтому f(σ) D w = 0.

Поскольку это должно быть верно для всех f(σ) , имеем D w = 0.

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

Это обеспечивает простой алгоритм проверки сохране­ния, а также позволяет получать вектор взвешивания w.

Развитая матричная теория сетей Петри является инструментом для решения проблемы достижимости. Предположим, что марки­ровка µ" достижима из маркировки µ. Тогда существует последо­вательность (возможно, пустая) запусков переходов σ, которая приводит из µ к µ". Это означает, что f(σ) является неотрицатель­ным целым решением следующего матричного уравнения для х:

µ" = µ + x D

Следовательно, если µ" достижима из µ, тогда данное уравнение имеет решение в неотрицательных целых; если данное уравнение не имеет решения, тогда µ" недостижима из µ.

Рассмотрим, например, маркированную сеть Петри, изображенную на рис.1:

Рис. 1. Сеть Петри, иллюстрирующая метод анализа, основанный на мат­ричных уравнениях

Матрицы D - и D + имеют вид:

t 1 t 2 t 3 t 1 t 2 t 3

p 1 1 0 0 p 1 1 0 0

D - = p 2 1 0 0 D + = p 2 0 2 0

p 3 1 0 1 p 3 0 1 0

p 4 0 1 0 p 4 0 0 1

а матрица D:

В начальной маркировке µ = (1, 0, 1, 0) переход t 3 разрешен и приводит к маркировке µ" = (1, 0, 0,1).

µ" = µ + e D = (1, 0, 1, 0) + (0, 0, 1) D =

= (1, 0, 1, 0) + (0, 0, -1, 1) = (1, 0, 0, 1).

Последовательность σ = t 3 , t 2 , t 3 , t 2 , t 1 представляется вектором запусков f(σ) = (1, 2, 2) и получает маркировку µ":

µ" = (1, 0, 1, 0) + (1, 2, 2) D = (1, 0, 1, 0) + (0, 3, -1, 0) = (1, 3, 0, 0)

Для определения того, является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1,0, 1, 0), имеем уравнение:

(1, 8, 0, 1) = (1, 0, 1,0)+ x D

которое имеет решение х = (0, 4, 5). Это соответствует последова­тельности σ = t 3 , t 2 , t 3 , t 2 , t 3 , t 2 , t 3 , t 2 , t 3

(1, 7,0, 1)=(1, 0, 1, 0) + x D

не имеет решения.

Матричный подход к анализу сетей Петри очень перспективен, но имеет и некоторые трудности. Заметим прежде всего, что мат­рица D сама по себе не полностью отражает структуру сети Петри. Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц D + и D - , но затем взаимно уничтожаются в матрице D = D + - D - . Это отражено в предыдущем примере позицией p 4 , и переходом t 3 .

Другая проблема - это отсутствие информации о последова­тельности в векторе запуска. Рассмотрим сеть Петри на рис. 2. Предположим, мы хотим определить, является ли маркировка (0, 0, 0, 0, 1) достижимой из (1, 0, 0, 0, 0). Тогда имеем уравнение

(1, 0, 0, 0, 0)=(0, 0, 0, 0, 1) + x D

Рис. 2. Другая сеть Петри, служащая для иллюстрации матричного ана­лиза

Это уравнение не имеет однозначного решения, но сводится к мно­жеству решений {a\f(o) = (1, х 2 , х 6 - 1, 2х 6 , х е - 1, х 6)}. Оно определяет взаимосвязь между запусками переходов. Если поло­жим х 6 = 1 и х 2 = 1, то /(о) = (1, 1, 0, 2, 0, 1), но этому вектору запуска соответствуют как последовательность 44444. так и п0- следовательность 44444- Следовательно, хотя и известно число запусков переходов, порядок их запуска неизвестен.

Еще одна трудность заключается в том, что решение уравнения является необходимым для достижимости, но недостаточным. Рассмотрим простую сеть Петри, приведенную на рис. 3. Если мы хотим определить, является ли (0, 0, 0, 1) достижимым из (1, 0, 0, 0), необходимо решить уравнение

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

Это уравнение имеет решение /(а) = (1, 1), соответствующее двум последовательностям: tit 2 и / 3 / t . Но ни одна из этих двух последо­вательностей переходов невозможна, поскольку в (1,0, 0, 0) ни t it ни 4 не разрешены. Таким образом, решения уравнения не­достаточно для доказательства достижимости.

Контрольные вопросы и задания

1. Постройте граф сети Петри для следующей сети Петри:

P={p 1 ,p 2 ,p 3 ,p 4 }, T={t 1 ,t 2 ,t 3 ,t 4 ,t 5 },

I(t 1)={}, O(t 1)={p 1 },

I(t 2)={p 1 }, O(t 2)={p 2 },

I(t 3)={p 2 ,p 2 ,p 4 }, O(t 3)={p 1 ,p 3 },

I(t 4)={}, O(t 4)={p 3 },

I(t 5)={p 3 }, O(t 5)={p 4 ,p 4 }.

2. Постройте граф сети Петри для следующей сети Петри:

P={p 1 ,p 2 ,p 3 ,p 4 }, T={t 1 ,t 2 ,t 3 ,t 4 },

I(t 1)={}, O(t 1)={p 1 ,p 1 ,p 1 ,p 1 ,p 2 },

I(t 2)={p 2 }, O(t 2)={ p 1 ,p 1 p 1 ,p 1 ,p 1 ,p 1 ,p 3 },

I(t 3)={p 1 ,p 1 ,p 1 ,p 1 ,p 1 ,p 1 }, O(t 3)={ p 2 ,p 2 p 2 ,p 2 p 4 ,p 4 },

I(t 4)={ p 2 ,p 3 p 4 ,p 4 }, O(t 4)={p 3 }.

3. Для сети Петри из упр.1 для маркировки m=(5,4,0,0) указать разрешенные переходы.

4. Для сети Петри из упр.2 для маркировки m=(7,12,2,1) указать разрешенные переходы.

5. Покажите, что ÈR(C,m)=N n , где mÎN n .

6. Докажите, что если m‘Î R(C,m), то R(C,m‘)Í R(C,m).

7. Докажите, что m‘Î R(C,m) тогда и только тогда, когда R(C,m‘)Í R(C,m).

8. Постройте множество достижимости для сети Петри из упр.1.

9. Постройте множество достижимости для сети Петри из упр.2.

10. Сети Петри со своими фишками и правилами запусков во многом напоминают игры, имеющие игровое поле: шашки, нарды, ним, го и др. Можно придумать игру для одного - четырех человек, состоящую из игрового поля (в качестве поля используется сеть Петри) и набора фишек. Фишки распределены по позициям сети Петри, и игроки по очереди выбирают разрешенные переходы и запускают их. Определите правила игры, предусматривающие следующее:

a Как определено начальное расположение фишек? (Например, каждый игрок начинает игру, имея одну фишку в домике или каждый игрок получает n фишек на всем поле по желанию и т.д.).

b Какова цель игры? (Захватить фишки своего противника; получить наибольшее количество фишек; как можно скорее избавиться от своих фишек и т.д.).

c Не нужно ли раскрасить фишки для разных игроков? (В соответствии с этим определите правила запуска переходов).

d Не стоит ли присвоить очки различным переходам? (Тогда очки игрока определяются суммой переходов, запущенных им).

На основе этого опишите игру, приведите пример игры.

11. Разработайте программу, которая реализует игру из упр.10, где в качестве вашего противника выступает компьютер для заданной сети Петри.

12. Постройте систему моделирования для выполнения сети Петри. Запуск разрешенных переходов задается пользователем системы моделирования.

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

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

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

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

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

18.Разработать алгоритм моделирования блок-схем сетью Петри.

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

20.Разработайте модель, основанную на сетях Петри, для моделирования химических реакций.

21.Рассмотрите построение не дерева, а графа достижимости. Если вершина x порождает последующую вершину z с m[z]=m[y] для некоторой неграничной вершины y, вводится помеченная соответствующим образом дуга от x к y. Опишите алгоритм построения графа достижимости.

22.Покажите, что алгоритм построения графа достижимости сходится, и исследуйте его свойства, сравнивая его с алгоритмом построения дерева достижимости.

23.Дерево достижимости нельзя использовать для решения проблемы достижимости, т.к. теряется информация в связи с введением понятия символа w. Он вводится, когда приходим к маркировке m‘ и на пути от корня к m‘ имеется такая маркировка m, что m‘>m. В этом случае можно получить все маркировки вида m+n(m‘-m). Исследуйте возможность использования выражения a+bn i вместо w, для того чтобы представить значения компонент. Если вы сможете определить дерево достижимости, в котором все векторы маркировок представляются выражениями, тогда решение задачи достижимости определяется просто решением системы уравнений.

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

25.Разработайте с помощью матричного подхода к анализу алгоритм определения ограниченности сети Петри.

26.Разработайте алгоритм решения задачи равенства двух сетей Петри. Сеть Петри C 1 =(P 1 ,T 1 ,I 1 ,O 1) с маркировкой m 1 равна сети Петри C 2 =(P 2 ,T 2 ,I 2 ,O 2) с маркировкой m 2 , если R(C 1 ,m 1)= R(C 2 ,m 2).

27.Разработайте алгоритм решения задачи подмножества двух сетей Петри. Сеть Петри C 1 =(P 2 ,T 2 ,I 2 ,O 2) с маркировкой m 2 есть подмножество сети Петри C 1 =(P 1 ,T 1 ,I 1 ,O 1) с маркировкой m 1 , если R(C 1 ,m 1)Í R(C 2 ,m 2).

28.Разработайте алгоритм решения задачи достижимости. В сети Петри C=(P,T,I,O) с маркировкой m маркировка m‘ достижима из m, если m‘ÎR(C,m).

29.Разработайте алгоритм задачи достижимости подмаркировки. Для подмножества P’ Í P и маркировки m‘ существует ли m‘’ÎR(C,m), такая, что m‘’(p i)=m‘(p i) для всех p i ÎP’?.

30.Разработайте алгоритм задачи достижимости нуля. Выполняется ли m‘ÎR(C,m), где m‘(p i)=0 для всех p i ÎP?

31.Разработайте алгоритм задачи достижимости нуля в одной позиции. Для данной позиции p i ÎP существует ли m‘ÎR(C,m) с m‘(p i)=0?

32.Разработайте алгоритм решения задачи активности сети Петри. Активны ли все переходы t j ÎT?

33.Разработайте алгоритм решения задачи активности одного перехода. Активен ли данный переход t j ÎT?

34.Сеть Петри называется обратимой, если для каждого перехода t j ÎT найдется переход t k ÎT, такой, что

#(p i ,I(t j))=#(p i ,O(t k)), #(p i ,O(t j))=#(p i ,I(t k)),

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

35. Разработайте алгоритм решения задачи равенства для обратимых сетей Петри.

36.Задача о курильщиках. Каждый из трех курильщиков непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы табак, бумага и спички. Один из курильщиков всегда имеет бумагу, другой - спички, третий - табак. Агент обладает бесконечными запасами бумаги, спичек и табака. Агент кладет две составные части на стол. Курильщик, имеющий третий недостающий ингредиент, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех ингредиентов, и цикл повторяется. Предложите активную сеть Петри, которая моделирует задачу о курильщиках.

37. Автоматная сеть Петри - это сеть Петри, в которой каждый переход может иметь точно один выход и один вход,т.е. для всех t j ÎT ½I(t j)½=1 и ½O(t j)½=1. Разработайте алгоритм построения конечного автомата, который эквивалентен заданной автоматной сети Петри.

38. Маркированный граф есть сеть Петри, в которой каждая позиция является входом для точно одного перехода и выходом точно одного перехода,т.е. для каждого перехода p i ÎP ½I(p i)½=1 и ½O(p i)½=1. Разработайте алгоритм решения задачи достижимости для маркированных графов.

39.Рассмотрите класс сетей Петри, которые являются и маркированными графами, и автоматными сетями Петри.

40.Постройте сеть Петри, моделирующую системы, описанные в приложении 8. Опишите события, происходящие в системе, и условия, которые описывают систему. Постройте дерево достижимости построенной сети Петри. Опишите состояния, в которых может находиться система.