Дискретно-непрерывная математика (стр. 65 )

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

Если сумма по каждой строке А точно равна единице, то матрица называется стохастической. Из приведенных выше рассуждений следует, что в замкну­той модели х(I—A*)=0 матрица А* — стохастическая, а в незамкнутой модели х(I—A)=w матрица А — суб-cтохастическая. Приведем без доказательства следую­щую теорему.

Теорема 5.1. Пусть А — субстохастическая матрица. Обратная матрица (I—A)-1 существует тогда и только тогда, когда в ориентированном графе D(A) нет замк­нутых сильно связных подграфов или когда в каждом сильно связном подграфе H, замкнутом в D(А), сущест­вует вершина, для которой сумма элементов соответст­вующей строки А меньше чем единица.

Эту теорему можно переформулировать следующим образом.

Теорема 5.2. Пусть А*—стохастическая матрица и А — любая главная подматрица А*. Обратная матри­ца (I—A)-1 существует тогда и только тогда, когда не существует сильно связного подграфа, который является еамкнутым в D(A) и в D(A*).

Доказательство. Предположим, что Н является сильно связным подграфом D(A). Тогда Н замкнут в D(A), а соответствующая ему матрица А является сто­хастической тогда и только тогда, когда Н замкнут в D(A*). Из теоремы 8.1 следует, что ни один замкнутый сильно связный подграф в D(A) не замкнут в D(A*).

Следствие 5.3. Пусть А *—стохастическая матрица. Если D(A*) —сильно связный граф (т. е. А* неприводима или неразложима), то

(I—A)-1 существует для любой главной подматрицы А матрицы А*.

Упражнения

1. Пусть А—неотрицательная квадратная матрица порядка п, в которой сумма по каждой строке положительная. Показать, что в ориентированном графе D(A), построенном для матрицы А: (1) су­ществует, по крайней мере один замкнутый сильно связный подграф; (2) каждая вершина D(A) связана ие менее чем c одним замкнутым сильно связным подграфом в D(A).

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

3. Пусть А—неотрицательная квадратная матрица порядка п, х — положительный (n×1) вектор-столбец и у — положительная (1×n) вектор-строка. Пусть обозначает ограниченную матрицу по­рядка

п+1 следующего вида:Ориентированный граф D() сильно сзязный. Показать, что если А в отличается от нуль-матрицы, то является примитивной и точная верхняя граница — индекс примитивности γ() равна 4.

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

Потребление (сумма по строкам).

Определитель этой матрицы равен 38.

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

Рис. 5.1.

Сумма этих произведений, взятая по всем деревьям равна определителю приведенной выше мат­рицы. Таким образом, 2+16+0+2+8+0+8+2=38. Положительные деревья соответствуют матрицам, суммы элементов строк которых больше или равны нулю, а эле­менты, расположенные вне главной диагонали, не явля­ются положительным. Таким образом, единственное по­ложительное дерево гарантирует положительный опре­делитель. Такие матрицы (например, матрицы Леонтьева) с доминирующей диагональю представляют большой ин­терес для математической экономики.

5.3. Линейное программирование и потоки в сетях

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

Пусть вершины v0 и vn ориентированного графа обоз­начают источник и сток некоторого вещества, протека­ющего по дугам. Кроме того, предположим, что дуге из вершины vi в вершину vj поставлена в соответствие про­пускная способность или верхнее ограничение на величи­ну потока . Наконец, пусть Cij обозначает стоимость единицы потока по дуге. Теперь задачу о потоке можно представить в виде задачи линейного программирова­ния, в которой требуется минимизировать

для общего потока с из v0 в vn при условиях

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

5.4. Задачи типа ПЕРТ

(В русской литературе принят термин СПУ (сетевое планирование н управление).

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

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

Хотя некоторые операции проекта независимы друг от друга, в общем случае между ними существует до­статочно сильная зависимость по времени, например, операция аi должна быть закончена прежде, чем может быть начата операция aj. Если заданы все такие времен­ные зависимости, то их можно удобно представить в ви­де ориентированного графа, как показано на рис. 8.2.

Рис. 5.2.

Каждая дуга графа соответствует одной операции, а каждая вершина, называемая событием, соответствует некоторому моменту времени. В частности, вершина v1 представляет собой начало всего проекта, a v8 — его окончание. Промежуточные вершины служат для отра­жения взаимосвязи операций во времени. Вершины вы­бираются и сопоставляются с дугами так, что для каж­дой операции (дуги) и события (вершины) справедливо следующее основное утверждение: если операция а име­ет начальное событие в виде вершины v, то она не мо­жет быть начата до тех пор, пока все операции, закан­чивающиеся в v, не будут выполнены. Естественно а может начаться в любой другой момент после того, как выполнены все предшествующие операции. Например, на рис. 5.2 операция 10 (так же как и 12) может быть

начата только после выполнения операций 5 и 7. Кос­венно начало операции 10 зависит также от моментов выполнения операций 1, 2 и 4, так как они непосредст­венно определяют начало операций 5 и 7. В начале про­екта могут выполняться только операции 1, 2 и 3. Про­ект считается законченным после выполнения операций 11, 12 и 13 (а, следовательно, всех операций проекта). Граф такого типа, представляющий процесс выпол­нения операций, является основой многих методов ор­ганизационного управления и, в частности, широко из­вестного метода ПЕРТ и метода критического пути. Он позволяет проводить анализ различных вариантов выполнения проектов.

Для иллюстрации основного типа проводимого ана­лиза предположим, что для выполнения каждой опера­ции а требуется известное время t(a).