Матричный анализ. Матричные методы стратегического анализа. Классификация и внедрение. Биосинтез белка и нуклеиновых кислот. Матричный характер реакций биосинтеза. Генетическая информация в клетке. Гены, генетический код и его свойства

Задание 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

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

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

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

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

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

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

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) вполне определяется значениями этого многочлена на спектре матрицы А, т.е. все многочлены g i (x), принимающие одинаковые значения на спектре матрицы имеют одинаковые матричные значения g i (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) Þ .

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

Свойство № 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 будут которым соответственно равны .

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

1. Выбор оценочных показателей и формирование матрицы исходных данных a ij , то есть таблицы, где по строкам отражаются номера систем (предприятий), а по столбцам номера показателей (i=1,2….n) - системы; (j=1,2…..n) - показатели. Выбранные показатели должны иметь одинаковую направленность (чем больше, тем лучше).

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

Выделяем в каждом столбце максимальный элемент.

Второй подход к анализу сетей Петри основан на матричном представлении сетей Петри. Альтернативным по отношению к опре­делению сети Петри в виде (Р, Т, 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. Опишите события, происходящие в системе, и условия, которые описывают систему. Постройте дерево достижимости построенной сети Петри. Опишите состояния, в которых может находиться система.

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

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

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

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

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

Классификация матриц стратегического анализа и планирования.

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

Матрицы по существующим признакам можно классифицировать следующим образом:

• Классификация по количеству исследуемых ячеек .

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

• Классификация по объекту изучения .

Классификация по объекту изучения делит матрицы на группы в зависимости от изучаемого объекта. В матрице «Осведомленность – отношение» объектом изучения является персонал, так же как и в матрице «Влияние оплаты на взаимоотношения в группе». Другим объектом исследования выступает портфель компании. В этой группе примерами могут служить матрицы Shell/DPM, BCG.

• Классификация по получаемой информации .

Данная классификация разделяет матрицы на две группы по получаемой информации: либо количественной, либо смысловой. В этой группе примером матрицы, образованной за счет информации в виде числа, является матрица вектора экономического состояния организации, а образованной за счет логической информации - матрица основных форм объединений.

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

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

Вторым этапом применения матричных методов является анализ рынка и отрасли. Здесь анализируются рынки, на которых функционирует предприятие, а также отрасль в целом. Основными в подгруппе «Рынок» являются матрица BCG, исследующая зависимость темпов роста и доли рынка, и матрица GE, анализирующая сравнительную привлекательность рынка и конкурентоспособность в отрасли и имеющая две разновидности: вариант Дэйа и вариант Мониенсона. Подгруппа «Отрасль» содержит матрицы, исследующие отраслевое окружение, закономерности развития отрасли. Основной в данной подгруппе является матрица Shell/DPM, исследующая зависимость отраслевой привлекательности и конкурентоспособности.

Следующие этапы стратегического планирования – анализ дифференциации и анализ качества. Дифференциация и качество выступают в данном случае как составляющие, с помощью которых возможно получение требуемого результата. В группе «Дифференциация» находятся три матрицы. Матрица «Улучшение конкурентной позиции» позволяет наглядно выявить закономерности и зависимости дифференциации от охвата рынка. Матрица «Дифференциация – относительная эффективность затрат» выявляет зависимость относительной эффективности затрат на данном рынке от дифференциации. Матрица «Производительность – инновации/дифференциации» показывает зависимость между производительностью данной бизнес-единицы и внедрением инноваций.

Объект исследования группы «Анализ качества» – выявление факторов и закономерностей, влияющих на такой аспект, как качество производимой продукции. Группа может включать две матрицы. Матрица «Стратегии установления цен» позиционирует продукты в зависимости от качества и цены. Матрица «Качество – ресурсоемкость» определяет соотношение качества произведенного продукта и ресурсов, на него потраченных.

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

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

Характеристика отдельных матриц

SWOT-анализ – это один из самых распространенных видов анализа в стратегическом управлении на сегодняшний день. SWOT: Strengths (Cилы); Weaknesses (Слабости); Opportunities (Возможности); Threats (Угрозы). SWOT-анализ позволяет выявить, структурировать сильные и слабые стороны компании, а также потенциальные возможности и угрозы. Достигается это за счет сравнения внутренних сил и слабостей своей компании с возможностями, которые дает им рынок. Исходя из качества соответствия, делается вывод о том, в каком направлении должна развивать свой бизнес, и в конечном итоге определяется распределение ресурсов по сегментам.

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

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

Рис.1. Матрица первичного стратегического SWOT - анализа.

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

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

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

Формальные методы можно назвать более точными и основательными. Среди наиболее известных и удачных методов анализа бизнес-портфеля с помощью формальных методов можно назвать следующие:

• Метод компании Boston Consulting Group (BCG);
• Метод компании General Electric (GE).

Метод BCG основан на принципе анализа матрицы рост/доля рынка. Этот метод планирования портфеля, который оценивает СЭБ компании с точки зрения темпов роста их рынка и относительной доли этих элементов на рынке. СЭБ делятся на «звезд», «дойных коров», «темных лошадок» и «собак» (см. рис. 2).

Т е м п р о с т а р ы н к а	в ы с о к и й	“Звезда”	“Дойные коровы”
	н и з к и й	“Дойная корова”	“Собака”
		высокое	низкое
Относительное долевое участие на рынке

Рис.2. Матрица BCG.

Вертикальная ось на рис.2, темпы роста рынка, определяет меру привлекательности рынка. Горизонтальная ось, относительная доля рынка, определяет прочность положения компании на рынке. При делении матрицы рост/доля рынка на секторы можно выделить четыре типа СЭБ.

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

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

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

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

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

С течением времени СЭБ меняет свое положение в матрице рост/доля рынка. У каждого СЭБ свой жизненный цикл. Многие СЭБ начинают как «темные лошадки» и при благоприятно складывающихся обстоятельствах переходят в категорию «звезд». Позже, по мере замедления роста рынка, они становятся «дойными коровами» и, наконец, на закате своего жизненного цикла угасают или превращаются в «собак». Компании необходимо непрерывно вводить новые товары и виды деятельности, чтобы часть из них становилась «звездами», а затем и «дойными коровами», помогающими финансировать другие СЭБ.

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

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

№	Уровни решения задач	Матрица	Основные характеристики
1	Первичный анализ	Матрица SWOT	Анализ сильных и слабых сторон предприятия, возможностей и угроз
2		Матрица MCC	Анализ соответствия миссии предприятия и его основных возможностей
3		Матрица вектора экономического развития предприятия	Анализ статистических данных
4	Анализ рынка/отрасли	Матрица BCG	Анализ темпов роста и доли рынка
5		Матрица GE	Анализ сравнительной привлекательности рынка и конкурентоспособности
6		Матрица ADL	Анализ жизненного цикла отрасли и относительного положения на рынке
7		Матрица HoferSchendel	Анализ положения среди конкурентов в отрасли и стадии развития рынка
8		Матрица Ансоффа (“рынок-продукт”)	Анализ стратегии по отношению к рынкам и продуктам
9		Матрица Портера (пяти конкурентных сил)	Анализ стратегических перспектив развития бизнеса
10		Матрица эластичности конкурентной реакции на рынке	Анализ действия фирмы по факторам конкурентоспособности товара в зависимости от эластичности реакции приоритетного конкурента по товару
11		Матрица группировки товара	Анализ группировки товара
12		Матрица “Воздействие неопределенность”	Анализ уровня воздействия и степени неопределенности при выходе на новый рынок
13	Отрасль	Матрица Купера	Анализ привлекательности отрасли и силы бизнеса
14		Матрица ShellDPM	Анализ привлекательности ресурсоемкой отрасли в зависимости от конкурентоспособности
15		Матрица стратегий переживающего спад бизнеса	Анализ конкурентных преимуществ в отраслевом окружении
16		Матрица основных форм объединений	Анализ объединения в отраслевом окружении
17	Анализ дифференциации	Матрица улучшения конкурентной позиции	Анализ дифференциации и охвата рынка
18		Матрица “Дифференциация относительная эффективность затрат”	Анализ дифференциации и относительной эффективности затрат
19		Матрица “Производительность - инновации/ дифференциации”	Анализ инноваций/ дифференциации и производительности
20	Анализ качества	Матрица “Цена-качество”	Позиционирование продукта в зависимости от качества и цены
21		Матрица “Качество- ресурсоемкость”	Анализ зависимости качества от ресурсоемкости
22	Анализ маркетинговой стратегии	Матрица стратегии расширения марочных семейств	Анализ зависимости отличительных преимуществ и сегментации целевого рынка
23		Матрица “Осведомленность- отношениек марке товара”	Анализ зависимости маржи валовой прибыли и ответной реакции сбыта
24		Матрица маркетинговых каналов	Анализ зависимости темпов развития рынка и ценности, добавляемой каналом
25		Матрица “Контакт- уровень приспособления услуг”	Анализ зависимости уровня приспособления услуг к требованиям клиентов от степени контакта с клиентом
26		Матрица “Диагностика маркетинга”	Анализ зависимости стратегии от осуществления стратегии
27	Анализ управления Руководство	Матрица способов стратегического управления	Анализ зависимости стратегии и влияния планирования
28		Матрица модели стратегического менеджмента	Анализ зависимости модели менеджмента от типа изменений
29		Матрица Херси-Бланшара	Анализ ситуативной модели руководства
30		Матрица “Комбинации размерностей стилей руководства университета Огайо”	Анализ комбинаций размерностей стилей руководства
31		Матрица “Управленческая решетка”	Анализ типов руководства
32	Персонал	Матрица “Изменение – в организации”	Анализ зависимости изменений, происходящих в организации и сопротивления этим изменениям
33		Матрица влияния оплаты на взаимоотношения в группе	Анализ зависимости взаимоотношений в группе от дифференциации оплаты
34		Матрица типов включения человека в группу	Анализ зависимости отношения к ценностям организации и отношения к нормам поведения в организации
35		Матрица “Основные деловые способности”	Анализ рынка и основных деловых способностей
36		Матрица “Важность работы”	Анализ зависимости выполнения работы от важности
37		Матрица существующих формальных систем критерия качества работы	Анализ существующих формальных систем критерия качества работы
38		Матрица результатов управления критериями качества работы	Анализ результатов управления критериями качества работы
39		Матрица Блейка-Моутона	Анализ зависимости выполнения работы от количества людей и от количества задач
40		Матрица Мак-Дональда	Анализ производительности