Стратегия социально-экономического развития Омской области

Обратно, пусть неотрицательная  матрица А имеет число Фробениуса λ_А 1. Покажем, что она продуктивна. Возьмем неотрицательный вектор у и покажем, что у системы (2.4) существует решение х ≥ 0.

Рассмотрим следующую  неотрицательную матрицу размера (n + 1)(n+ 1):     а₁₁ а₁₂ … а_1n у₁

а₂₁ а₂₂ … а_2n у₂

А = …………….

а_n1 а_n2 … а_nn у_n

0 0 … 0 1

Где а_ij – элементы матрицы А и у₁, …, у_n – координаты вектора у. В более компактной форме матрицу можно записать так:

А = А у

0 1

Умножая эту матрицу слева  на вектор р^Т = (0, …, 0,1), легко убедиться,

Следовательно, одним из собственных значений матрицы А  является вектор λ = 1.

Пусть вектор Х = (х₁ , …, х_n , х_n+1 ) = (х , х_n+1) является собственным вектором матрицы А, т.е. АХ = λХ. В силу определения матрицы А эторавносильно тому, что

А у х = λ х

0 1 х_n+1 х_n+1

или

Ах + у х_n+1 = λх,

х_n+1 = λ х_n+1. (2.9)

Если λ ≠ 1, то из второго соотношения системы (2.9) следует, что х_n+1 = 0, в силу чего первое уравнение имеет вид Ах = λх. Следовательно, λ – собственное значение матрицы А и, по нашему предположению ‌‌‌|λ| < 1. Таким образом, λ_А = 1 является положительным и максимальным по модулю собственным значением, следовательно является числом Фробениуса. По теореме Фробениуса-Перрона у матрицы А существует неотрицательный собственный вектор х_А = ( х_А , х_n+1), соответствующий λ_А =1. Очевидно, что х_n+1 ≠ 0, так как в противном случае из (2.9) следовало бы, что Ах = х. А это противоречит тому, что число Фробениуса λ_А < 1. Поэтому мы можем считать, что х_n+1 = 1. В силу того, что х_n+1 = 1, равенство (2.9) принимает вид

Ах_А + у = х_А.

Поскольку х_А = (х_А, х_n+1) ≥ 0, то х_А ≥ 0.

Следовательно, матрица А  продуктивна.

Следствие.

Если для неотрицательной  матрицы А и некоторыого положительного вектора у уравнение (2.4) имеет  неотрицательное решение х, то матрица  А продуктивна.

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

Как было уже показано, из существования положительного решения  у уравнения (2.4) следует, что λ_А < 1. На основании теоремы Фробениуса матрица А продуктивна.

Теорема 3 (третий критерий продуктивности).

Неотрицательная матрица  А продуктивна тогда и только тогда, когда сходится бесконечный  ряд

Е + А + А² + … (2.10)

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

Пусть сходится ряд (2.10). Согласно лемме его сема равна (Е – А)^-1. При этом сумма указанного ряда будет неотрицательна, поскольку все слагаемые ряда неотрицательны. Итак, матрица (Е – А)^-1 существует и неотрицательна. Отсюда по теореме 1.3 следует продуктивность А.

Обратное утверждение (если А продуктивна, то ряд (2.10) сходится) доказывать не будем.

         Модель равновесных цен

Рассмотрим теперь балансовую модель, двойственную к модели Леонтьева  – так называемую модель равновесных  цен. Пусть, как и прежде, А –  матрица прямых затрат, х = (х₁ , х₂, …, х_n)^Т – вектор валового выпуска. Обозначим через р = (р₁ , р₂ , …, р_n)^Т вектор цен, i координата которого равна цене единицы продукции i-й отрасли; тогда, например, первая отрасль получит доход, равный р₁ х₁. Часть своего дохода эта отрасль потратит на закупку продукции у других отраслей. Так, для выпуска единицы продукции, ей необходима продукция первой отрасли в объеме а₁₁, второй отрасли в объеме а₂₁, и т.д., n-й отрасли в объеме а_n1. На покупку этой продукции ею будет затрачена сумма, равная а₁₁ р₁ + а₂₁ р₂ + … + а_n1 р_n. Следовательно, для выпуска продукции в объеме х₁ первой отрасли необходимо потратить на закупку продукции других отраслей сумму, равную х₁(а₁₁р₁+а₂₁р₂+…+ а_n1р_n). Оставшуюся часть дохода, называемую добавленной стоимостью, мы обозначим через V₁ (эта часть дохода идет на выплату зарплаты и налогов, предпринимательскую прибыль и инвестиции).

Таким образом, имеет место  следующее равенство:

х₁р₁ = х₁(а₁₁р₁+а₂₁р₂+…+ а_n1р_n) + V₁.

Разделив это равенство  на х₁ получаем:

р₁ = а₁₁ р₁ + а₂₁ р₂ + … + а_n1 р_n + v₁,

где v₁ = V₁/х₁ – норма добавленной стоимости (величина добавленной стоимости на единицу выпускаемой продукции). Подобным же образом получаем для остальных отраслей

р₂ = а₁₂ р₁ + а₂₂ р₂ + … + а_n2 р_n + v₂,

р_n = а_1n р₁ + а_2n р₂ + … + а_nn р_n + v_n.

Найденные равенства могут  быть записаны в матричной форме  следующим образом: р = А^Тр + v,

где v = (v₁, v₂, …, v_n)^Т – вектор норм добавленной стоимости. Как мы видим, полученные уравнения очень похожи на уравнения модели Леонтьева, с той лишь разницей, что х заменен на р, у – на v, А – на А^Т.

 

 

 

 

Методы оптимизации  

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

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

F (X) → max

X Є A 

Здесь Х - параметр, который менеджер может выбирать (управляющий параметр). Он может иметь различную природу - число, вектор, множество и т.п. Цель менеджера - максимизировать целевую функцию F (X), выбрав соответствующий Х.. При этом он должен учитывать ограничения X Є A на возможные значения управляющего параметра Х - он должен лежать в множестве А. Ряд примеров оптимизационных задач менеджмента приведен ниже.

Линейное  программирование 

Среди оптимизационных задач  менеджмента наиболее известны задачи линейного программирования, в которых  максимизируемая функция F(X) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера.  

Производственная задача.

 Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?  

Обозначим: Х₁ - число изготовленных стульев, Х₂ - число сделанных столов. Задача оптимизации имеет вид:

45 Х₁ + 80 Х₂  → max ,

5 Х₁ + 20 Х₂ ≤ 400 ,

10 Х₁ + 15 Х₂ ≤ 450 ,

Х₁  ≥ 0 ,

Х₂ ≥ 0 .

В первой строке выписана целевая  функция - прибыль при выпуске Х₁ стульев и Х₂ столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х₁ и Х₂ . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х₁ = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х₁ положительно. Но невозможно представить себе отрицательный выпуск - Х₁ не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.  

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс  откладывать значения Х₁ , а по вертикальной оси ординат - значения Х₂. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х_{1 ,} Х₂) объемов выпуска в виде треугольника (рис.1).

Рис.1. Ограничения по материалу  

Таким образом, ограничения  по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта  примыкающей к началу координат  зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства  на равенство. Прямая пересекает ось Х₁, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х₂, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - материал останется. 

Аналогичным образом можно  изобразить и ограничения по труду (рис.2).  

Таким образом, ограничения  по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта  примыкающей к началу координат  зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства  на равенство. Прямая пересекает ось Х₁, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х₂, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

 

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает  рабочих рук, а для производства 30 столов есть рабочая сила, но нет  материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?  

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Рис.3. Основная идея линейного  программирования. 

Таким образом, множество  возможных значений объемов выпуска  стульев и столов (Х₁ , Х₂ ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений 

5 Х₁ + 20 Х₂ = 400 ,

10 Х₁ + 15 Х₂ = 450 .

Из первого уравнения: 5 Х₁ = 400 - 20 Х₂ , Х₁ = 80 - 4 Х₂ . Подставляем во второе уравнение:

10 (80 - 4 Х₂) + 15 Х₂ = 800 - 40Х₂  + 15 Х₂ = 800 - 25 Х₂ = 450,

следовательно, 25 Х₂ = 350, Х₂ = 14, откуда Х₁ = 80 - 4 х 14 = 80 -56 =24. Итак, четвертая вершина четырехугольника - это (24, 14). 

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

Целевая функция 45 Х₁ + 80 Х₂  принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х₁ + 80 Х₂  = 2200 проходит между прямыми ограничений 5 Х₁ + 20 Х₂ = 400 и 10 Х₁ + 15 Х₂ = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14). 

Таким образом, оптимальный  выпуск таков: 24 стула и 14 столов. При  этом используется весь материал и  все трудовые ресурсы, а прибыль  равна 2200 долларам США. 

Двойственная  задача.

 Каждой задаче линейного  программирования соответствует  так называемая двойственная  задача. В ней по сравнению  с исходной задачей строки  переходят в столбцы, неравенства  меняют знак, вместо максимума  ищется минимум (или, наоборот, вместо минимума - максимум). Задача, двойственная к двойственной - эта сама исходная задача. Сравним исходную задачу (слева) и двойственную к ней (справа):

45 Х₁ + 80 Х₂  → max , 400 W₁ + 450 W₂ → min ,

5 Х₁ + 20 Х₂ ≤ 400 , 5 W₁ + 10 W₂ ≥ 45,

10 Х₁ + 15 Х₂ ≤ 450 , 20 W₁ + 15 W₂ ≥ 80,

Х₁  ≥ 0 , W₁ ≥ 0,

Х₂ ≥ 0 . W₂ ≥ 0. 

Почему двойственная задача столь важна? Можно доказать, что  оптимальные значения целевых функций  в исходной и двойственной задачах  совпадают (т.е. максимум в исходной задаче совпадает с минимумом  в двойственной). При этом оптимальные  значения W₁ и W₂ показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W₁ и W₂ называют "объективно обусловленными оценками" сырья и рабочей силы.