Методы решения систем уравнений матричных балансовых моделей

МЕТОДЫ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ МАТРИЧНЫХ БАЛАНСОВЫХ МОДЕЛЕЙ ПРИМЕР Необходимо рассчитать показатели межотраслевого баланса при уловном делении экономики всего на три отрасли: промышленность, сельское хозяйство и прочие отрасли. На плановый период заданы матрица коэффициентов прямых затрат a и вектор конечной продукции y: 0,30 a = 0,15 0,10 0,25 0,12 0,05 0,20 0,03 ; 0,08  56  y = 20 12  2 ТРЕБУЕТСЯ Рассчитать: • плановые объемы валовой продукции; • величину межотраслевых потоков; • чистую продукцию отраслей и представить результаты в форме межотраслевого баланса. 3 Первый вариант расчета Основан на использовании коэффициентов прямых затрат и метода Гаусса. 1) используем уравнения типа (A): n X i = ∑ aij x j + yi j =1  X 1 = 0,30 X 1 + 0,25 X 2 + 0,20 X 3 + 56   X 2 = 0,15 X 1 + 0,12 X 2 + 0,03 X 3 + 20  X = 0,10 X + 0,05 X + 0,08 X + 12 1 2 3  3 4 Первый вариант расчета 2) перенесем все слагаемые, содержащие неизвестные величины, в левую часть уравнений: 0,70 X 1 − 0,25 X 2 − 0,20 X 3 = 56  − 0,15 X 1 + 0,88 X 2 − 0,03 X 3 = 20 − 0,10 X − 0,05 X + 0,92 X = 12 1 2 3  5 Метод Гаусса • На первом шаге вычислений одно из уравнений преобразуется так, чтобы коэффициент при X1 был равен единице, а из остальных уравнений X1 исключается вообще. • На следующем шаге добиваются единичного коэффициента при X2 во втором уравнении и исключают X2 из всех последующих уравнений. • Продолжая указанную вычислительную процедуру, получают систему, в которой последнее уравнение содержит лишь одну неизвестную величину, а каждое предшествующее на одну больше. • Путем обратной подстановки, переходя от последнего уравнения к первому, находят значения всех неизвестных величин. 6 ПЕРВЫЙ ВАРИАНТ РАСЧЕТА 3) Метод Гаусса основан на последовательном исключении переменных. В примере удобнее выполнять расчеты, если 3-ье уравнение поставить на первое место. 0,70 X 1 − 0,25 X 2 − 0,20 X 3 = 56 − 0,10 X 1 − 0,05 X 2 + 0,92 X 3 = 12   − , 15 + , 88 − , 03 = 20 ⇒ X X X  0,70 X 1 − 0,25 X 2 − 0,20 X 3 = 56 1 2 3 − 0,15 X + 0,88 X − 0,03 X = 20 − 0,10 X − 0,05 X + 0,92 X = 12 1 2 3 1 2 3   7 Метод Гаусса. Первый шаг Первое уравнение делим на –0,1, затем полученное уравнение умножаем на 0,7 и отдельно –0,15 и вычитаем, соответственно, из 2-го и 3-го уравнений: − 0,10 X 1 − 0,05 X 2 + 0,92 X 3 = 12  X 1 + 0,50 X 2 − 9,20 X 3 = −120   , 70 − , 25 − , 20 = 56 ⇒ X X X   − 0,60 X 2 + 6,24 X 3 = 140 1 2 3 − 0,15 X + 0,88 X − 0,03 X = 20  0,955 X − 1,41X = 2 1 2 3 2 3   8 Метод Гаусса. Второй шаг Делим второе уравнение на –0,6 с тем, чтобы коэффициент при X2 стал равным единице. Полученное уравнение умножаем на 0,955 и вычитаем из третьего уравнения:  X 1 + 0,50 X 2 − 9,20 X 3 = −120  X 1 + 0,50 X 2 − 9,20 X 3 = −120   X 2 − 10,4 X 3 = −233,33  − 0,60 X 2 + 6,24 X 3 = 140 ⇒   0,955 X − 1,41X = 2  8,522 X 3 = 224,83 2 3   9 Метод Гаусса Из последнего уравнения находим: X3 = 26,38. Подставляя это значение во второе уравнение, получим: X2 = 41,02. Наконец, из первого уравнения имеем: X1 = 102,22. Таковы плановые объемы валовой продукции трех отраслей, необходимые для обеспечения заданного уровня конечной продукции. 10 Составление баланса Рассчитаем межотраслевые потоки средств производства xij по формуле: xij = aij · Xj Получаем: x11 = 0,30 · 102,2 = 30,6 x12 = 0,25 · 41,00 = 10,3 x13 = 0,20 · 26,40 = 5,3 и т.д. 11 Межотраслевой баланс Производящие отрасли Промышленность Потребляющие отрасли Сельское Прочие Конечная хозяйство отрасли продукция Валовая продукция Промышленность 30,6 10,3 5,3 56 102,2 Сельское хозяйство 15,3 4,9 0,8 20 41,0 Прочие отрасли 10,2 2,1 2,1 12 26,4 Чистая продукция 46,1 23,7 18,2 – – Валовая продукция 102,2 41,0 26,4 – 169,6 12 ЗАМЕЧАНИЕ Величина чистой продукции определяется как разница между валовой продукцией отрасли и суммой межотраслевых потоков в каждом столбце. Так для промышленности чистая продукция равна: 102,2 – (30,6 + 15,3 + 10,2) = 46,1; Чистая продукция для двух других отраслей рассчитывается аналогично. 13 ВТОРОЙ ВАРИАНТ РАСЧЕТА Основан на предварительном определении коэффициентов полных затрат с использованием метода Гаусса. Для расчета полных затрат используются системы уравнений вида (A), где в качестве вектора продукции принимаются единичные векторы, обозначающие выпуск единицы конечной продукции лишь в какой-то одной из отраслей. 14 Матрица полных затрат Требуется найти матрицу коэффициентов полных затрат для трех отраслей:  A11 A =  A21  A31 A12 A22 A32 A13  A23  A33  Это потребует решения трех систем уравнений, каждая из которых включает три уравнения с тремя неизвестными. 15 Полные затраты на единицу продукции промышленности и сельского хозяйства  X 1 = 0,30 X 1 + 0,25 X 2 + 0,20 X 3 + 1   X 2 = 0,15 X 1 + 0,12 X 2 + 0,03 X 3  X = 0,10 X + 0,05 X + 0,08 X 1 2 3  3  X 1 = 0,30 X 1 + 0,25 X 2 + 0,20 X 3   X 2 = 0,15 X 1 + 0,12 X 2 + 0,03 X 3 + 1  X = 0,10 X + 0,05 X + 0,08 X 1 2 3  3 ⇒  X 1 = A11 = 1,58   X 2 = A21 = 0,276  X = A = 0,187 31  3 ⇒  X 1 = A12 = 0,469   X 2 = A22 = 1,220  X = A = 0,117 32  3 16 Полные затраты на единицу продукции прочих отраслей  X 1 = 0,30 X 1 + 0,25 X 2 + 0,20 X 3   X 2 = 0,15 X 1 + 0,12 X 2 + 0,03 X 3  X = 0,10 X + 0,05 X + 0,08 X + 1 1 2 3  3 ⇒  X 1 = A13 = 0,363   X 2 = A23 = 0,103  X = A = 1,132 33  3 17 Матрица полных затрат  A11   A =  A21    A31 A12 A22 A32 A13  1,580 0,469 0,363       A23  = 0,276 1,220 0,103       0,187 0,117 1,132  A33  18 ЗАМЕЧАНИЕ • Все коэффициенты полных затрат по величине заметно превышают соответствующие коэффициенты прямых затрат. • Наибольшее различие наблюдается между полными и прямыми затратами собственной продукции каждой отрасли. Коэффициенты полных затрат здесь больше единицы, т.к. включают ту единицу продукции, которая входит в сферу конечного использования. 19 Объем производства по отраслям Для расчета объема производства по отраслям воспользуемся уравнениями вида: n X i = ∑ Aij y j ( B) j =1 X1 = A11 · y1 + A12 · y2 + A13 · y3 = 1,58 · 56 + 0,469 · 20 + 0,363 · 12 = 102,2 X2 = A21 · y1 + A22 · y2 + A23 · y3 = 0,276 · 56 + 1,22 · 20 + 0,103 · 12 = 41,0 X3 = A31 · y1 + A32 · y2 + A33 · y3 = 0,187 · 56 + 0,117 · 20 + 1,132 · 12 = 26,4. 20 ВЫВОДЫ • Сравнивая результаты расчета по системам уравнений (A) и (B), видим, что они полностью совпадают. • Однако, для однократных расчетов удобно пользоваться системой (A). • Если же производятся вариантные расчеты (с варьированием величин yi), то удобнее пользоваться системой (B). 21 МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ СИСТЕМ УРАВНЕНИЙ М Е Т О Д Г А У С С А. Рассмотрен выше. Это метод последовательного исключения неизвестных. Метод эффективен как для ручных расчетов, так и при использовании вычислительной техники. 22 МЕТОД ЖОРДАНА-ГАУССА Является разновидностью первого метода. При этом методе добиваются, чтобы каждая неизвестная осталась в конечном счете лишь в одном уравнении и была исключена не только из всех последующих уравнений, но также из всех предыдущих уравнений. В итоге, процесс исключения непосредственно приводит к решению системы и необходимость в обратной подстановке пропадает. 23 МЕТОД ПРОСТЫХ ИТЕРАЦИЙ Приближенный метод решения систем линейных уравнений. Имеет большое практическое значение. Процесс вычисления складывается из ряда последовательных шагов (итераций). Для рассмотренного выше примера исходная запись системы уравнений должна соответствовать виду (A).  X 1 = 0,30 X 1 + 0,25 X 2 + 0,20 X 3 + 56   X 2 = 0,15 X 1 + 0,12 X 2 + 0,03 X 3 + 20  X = 0,10 X + 0,05 X + 0,08 X + 12 1 2 3  3 24 МЕТОД ПРОСТЫХ ИТЕРАЦИЙ На первой итерации переменные приравниваются к свободным членам уравнений, т.е. принимается  X 1 = 56   X 2 = 20  X = 12  3 Эти значения на второй итерации подставляются в правую часть исходных уравнений и вычисляются новые значения неизвестных величин:  X 1 = 0,30 ⋅ 56 + 0,25 ⋅ 20 + 0,20 ⋅ 12 + 56 = 80,2   X 2 = 0,15 ⋅ 56 + 0,12 ⋅ 20 + 0,03 ⋅ 12 + 20 = 31,16  X = 0,10 ⋅ 56 + 0,05 ⋅ 20 + 0,08 ⋅ 12 + 12 = 19,56  3 25 МЕТОД ПРОСТЫХ ИТЕРАЦИЙ Вновь полученные значения переменных на третьей итерации опять подставляются в исходную систему:  X 1 = 0,30 ⋅ 80,2 + 0,25 ⋅ 31,16 + 0,20 ⋅ 19,56 + 56 = 90,762   X 2 = 0,15 ⋅ 80,2 + 0,12 ⋅ 31,16 + 0,03 ⋅ 19,56 + 20 = 36,356  X = 0,10 ⋅ 80,2 + 0,05 ⋅ 31,16 + 0,08 ⋅ 19,56 + 12 = 23,143  3 Метод формально прост, строго цикличен, легко программируется и реализуется на ПК. Другим его преимуществом является свойство самоисправляемости (ошибки, допущенные в процессе расчетов, не влияют на правильность окончательно получаемых результатов). 26 ИТЕРАЦИОННЫЙ МЕТОД ЗЕЙДЕЛЯ Является видоизмененным методом простых итераций. В этом методе на k-й итерации значение X1k определяется так же, как по методу простых итераций. Но при расчете X2k величина X1 подставляется уже не в (k – 1)-м, а в k-м приближении (только, что вычисленном). При вычислении X3k обе предыдущие неизвестные (X1 и X2) подставляются в k-м приближении. Наконец, в формулу для Xnk подставляются в k-м приближении все неизвестные, кроме самой Xn. В общем случае итерационный процесс по методу Зейделя сходится быстрее, чем по методу простых итераций. 27 ИТЕРАЦИОННЫЙ МЕТОД ЗЕЙДЕЛЯ Является видоизмененным методом простых итераций. В этом методе на k-й итерации значение X1k определяется так же, как по методу простых итераций. Но при расчете X2k величина X1 подставляется уже не в (k – 1)-м, а в k-м приближении (только, что вычисленном). При вычислении X3k обе предыдущие неизвестные (X1 и X2) подставляются в k-м приближении. Наконец, в формулу для Xnk подставляются в k-м приближении все неизвестные, кроме самой Xn. В общем случае итерационный процесс по методу Зейделя сходится быстрее, чем по методу простых итераций. 28 Достаточный признак сходимости итерационных процессов Если максимальная сумма абсолютных величин коэффициентов aij в правой части уравнений типа (A) меньше единицы, то процесс итераций сходится: n n n   max ∑ a1 j ; ∑ a 2 j ;...; ∑ a nj  < 1. j =1 j =1  j =1  Для проверки сходимости нашего примера воспользуемся строками матрицы aij: 0,30 + 0,25 + 0,20 = 0,75 0,15 + 0,12 + 0,03 = 0,30 0,10 + 0,05 + 0,08 = 0,23 Максимальная сумма (0,75) меньше единицы, что служит признаком сходимости вычислительного процесса. 29 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Система преобразуется – неизвестные переносят в левую часть: 0,70 X 1 − 0,25 X 2 − 0,20 X 3 = 56  − 0,15 X 1 + 0,88 X 2 − 0,03 X 3 = 20 − 0,10 X − 0,05 X + 0,92 X = 12 1 2 3  Во все уравнения вводится переменная X4 («невязка», расхождение), которую будем минимизировать: 0,70 X 1 − 0,25 X 2 − 0,20 X 3 + X 4 = 56  − 0,15 X 1 + 0,88 X 2 − 0,03 X 3 + X 4 = 20 − 0,10 X − 0,05 X + 0,92 X + X = 12 1 2 3 4  Ф.Ц . : 1000 X 4 → min  X 1 = 102,22  X = 41,02  2 ⇒  X 3 = 26,38  X 4 = 0 30