Вопросы для повторения.

1. Правила построения двойственной задачи.

2. Запись двойственных задач в матричной форме.

3. Псевдоплан.

4. Теорема об оптимальности псевдоплана.

5. Теоремы двойственности.

6. Геометрическая интерпретация двойственных задач.

7. Постановка транспортной задачи.

8. Табличное представление транспортной задачи. Этапы решения транспортной задачи.

9. Открытие и закрытие транспортной задачи. Число уравнений и число переменных в транспортной задаче. Вырожденный и невырожденный планы транспортной задачи.

10. Классификация методов решения транспортной задачи. Устранение неоднозначности при условии одинаковых тарифов.

11. Метод северо-западного направления.

12. Метод минимального элемента.

13. Метод аппроксимации Фогеля.

Задачи для самостоятельного решения.

1. Для исходной задачи: F=2x₁+7x₂ → max

x₁, x₂ ≥0

Составить двойственную задачу и найти решение обеих задач графическим способом.

2. Для исходной задачи: F=-2x₁ -3x₂ →min

x₁, x₂ ≥0

Составить двойственную задачу и найти решение обеих задач графическим способом.

3. Для исходной задачи: : F=3x₁ +5x₂ → max

x₁, x₂ ≥0

Составить двойственную задачу и найти решение обеих задач графическим способом.

Глава 6. Балансовые модели

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

1. Экономико-математическая модель (эмм) межотраслевого стоимостного баланса (модель Леонтьева)

Предполагается, что для производства единицы продукции в j-ой отрасли требуется определённое количество затрат промежуточной продукции i-ой отрасли, равное a_ij. Величины a_ij называются коэффициентами прямых материальных затрат и рассчитываются следующим образом:

(1)

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

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

(2)

С учётом (1) систему уравнений баланса (2) можно переписать в виде

(3)

Если ввести в рассмотрение матрицу коэффициентов прямых материальных затрат вектора-столбцы валовой продукции X и конечной продукции Y:

то система уравнений (3) в матричной форме примет вид

X=AX+Y. (4)

Cистема уравнений (3), или в матричной форме (4), называется ЭММ межотраслевого баланса (моделью Леонтьева или моделью «затраты-выпуск»). С её помощью можно выполнять три варианта расчётов:

• задав в модели величины X_i валовой продукции каждой отрасли, можно определить объёмы конечной продукции каждой отрасли: Y=(I-A)X, (5) где I – единичная матрица порядка n;

• задав величины Y_i, можно определить величины X_i валовой продукции каждой отрасли: X=BY, (6) где B=(I-A)^-1 – обратная матрица к матрице I-A;

• для ряда отраслей задав величины валовой продукции, а для всех остальных отраслей задав объёмы конечной продукции, можно найти величины конечной продукции первых отраслей и объёмы валовой продукции вторых, в этом варианте расчёта удобней пользоваться системой линейных уравнений (3).

Элементы матрицы B будем обозначать через b_ij, тогда из матричного уравнения (6) для любой i-ой отрасли можно получить соотношение:

(7)

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

Коэффициент b_ij полных материальных затрат можно применять, когда необходимо определить, как скажется на валовом выпуске некоторой отрасли предполагаемое изменение объёмов конечной продукции всех отраслей:

(8)

где X_i и Y_j – изменения (приросты) величин валовой и конечной продукции соответственно.

Основные свойства матрицы А коэффициентов прямых материальных затрат.

1. А0, т.е. для всех , от до .

2. для всех от до .

Заметим, что вектор Х валовой продукции состоит из неотрицательных компонент.

Определение. Неотрицательная матрица А называется продуктивной, если существует такой неотрицательный вектор X0, что

X>АX. (9)

Очевидно, что условие (9) означает существование положительного вектора конечной продукции Y>0 для модели межотраслевого баланса (4).

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

1. матрица I-A неотрицательно обратима, т.е. существует обратная матрица (I-A)^-10;

2. матричный ряд I+A+A²+A³+= cходится, причём его сумма равна обратной матрице (I-A)^-1;

3. наибольшее по модулю собственное значение λ матрицы А, т.е. решение характеристического уравнения det(А- λI)=0, строго больше 1;

4. все главные миноры матрицы I-A, т.е. определители матриц, образованных элементами первых строк и первых столбцов этой матрицы, порядков от 1 до n, положительны.

Существует другое определение коэффициента полных материальных затрат.

Определение. Коэффициентом c_ij полных материальных затрат называется сумма прямых и косвенных затрат продукции i-ой отрасли для производства продукции j-ой отрасли через все промежуточные продукты на всех предшествующих стадиях производства.

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

B=I+C,

или в поэлементной записи

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

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

1. , где - матрица, присоединённая к матрице I-A, det(I-A) – определитель матрицы I-A. Элементами матрицы являются алгебраические дополнения элементов матрицы (I-A)^T, транспонированной к матрице I-A.

2. Метод Жордана-Гаусса. Справа к матрице I-A приписывается матрица I. В результате гауссовых преобразований слева получается матрица I, а справа – матрица .

3. Приближённое вычисление матрицы В, используя разложение в матричный ряд

Обязательным условием корректности этих расчётов является продуктивность матрицы I-A. При расчётах ограничиваются учётом косвенных материальных затрат до некоторого порядка включительно, например, до второго и третьего порядков. В этом способе коэффициенты полных материальных затрат получаются с приближением по недостатку.

Пример. Задана матрица А коэффициентов затрат трёх отраслей и вектор конечной продукции Y.

1. Проверить продуктивность матрицы I-A.

2. Построить баланс производства и распределения продукции отраслей.

Решение. Проверим выполнение первого условия продуктивности матрицы I-A. матрица А должна быть неотрицательно обратима, т.е. должна существовать обратная матрица (I-A)^-10. Чтобы проверить это, используем второе свойство: матричный ряд должен сходиться и его сумма равна . Найдём вектор-столбец X валовой продукции по отраслям.

X=BY, где B=(I-A)^-1.

Матрица В не содержит отрицательных элементов матрица А продуктивна она позволяет обеспечить определённый выпуск конечной продукции по всем отраслям.

Найдём вектор-столбец X=BY валовой продукции по отраслям.

Для нахождения первого столбца матрицы межотраслевого баланса нужно элементы первого столбца заданной матрицы А умножить на элемент x₁ вектора-столбца Х.

0,3119=35,7

0,2119=23,8

0,4119=47,6 Аналогично вычисляются элементы второго и третьего столбцов матрицы межотраслевого баланса.

0,1149=14,9 0,1338=33,8

0,3149=44,7 0,2338=67,6

0,2149=29,8 0,3338=101,4

Отрасли производящие	Отрасли потребляющие			Конечная продукция Y	Валовая продукция X
	1	2	3
1	35,7	14,9	33,8	45	119
2	23,8	44,7	67,6	30	149
3	47,6	29,8	101,4	180	338
Условно чистая продукция	11,9	59,6	135,2	255
Валовая продукция	119	149	338		606

Пример. Пусть даны три отрасли, потребляющие и производящие, и дана конечная продукция по трём отраслям. Промежуточное потребление по каждой отрасли соответственно представлено в таблице. Найти объём валовой продукции каждой отрасли, а также матрицу А коэффициентов прямых материальных затрат и матрицу коэффициентов полных материальных затрат.

Производящие отрасли	Потребляющие отрасли			Конечная продукция Yi	Валовая продукция Xi
	1	2	3
1	200	50	300	200	750
2	150	250	10	100	510
3	230	50	150	300	730
Условно чистая продукция	170	160	270	600
Xi	750	510	730

Решение.

Х₁=200+50+300+200=750;

Х₂=150+250+10+100=510;

Х₃=230+50+150+300=730.

Матрица А коэффициентов прямых материальных затрат состоит из коэффициентов а_ij, смысл которых заключается в том, что для производства продукции в j-ой отрасли, требуется определённое количество затрат промежуточной продукции в i-ой отрасли, равное а_ij.

Эта матрица показывает, сколько потреблено промежуточной продукции. Матрица коэффициентов полных материальных затрат В=(I-А)^-1. Вычислим её.

, .

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

. Откуда:

Модель Неймана.

Рассмотрим более общую модель Неймана. Рассмотрим экономику, описываемую парой (С, К), где С – пространство товаров, а К – множество производственных процессов, перерабатывающих некоторые количества товаров в другие количества тех же товаров. Под товаром (продуктом) понимаем как первичные факторы производства (земля, труд) и сырьё (нефть, уголь), так и конечные продукты производства, услуги и т.п. Будем считать, что имеется n различных товаров, количество i-го товара обозначается x_i, тогда некоторый набор товаров обозначается X=(x₁,,x_n), т.е. является n-мерным вектором. Т.к. количества товаров неотрицательны, то для любого i=1,,n x_i0 или X0. Множество всех наборов товаров называется пространством товаров С. Это множество называется пространством потому, что в нём можно сложить любые два набора и умножить любой набор товаров на любое неотрицательное число. Возможность умножения набора товаров на любое неотрицательное число отражает предположение о безграничной делимости и умножении товаров (т.е. товары устроены наподобие сахарного песка, а не авианосцев).

Предполагаем, что каждый товар имеет цену. Все цены предполагаются строго положительными. Пусть цена единицы i-го товара есть p_i, тогда вектор P=(p₁,,p_n) есть вектор цен.

Набор товаров, как вектор, имеет ту же размерность, что и вектор цен. Для набора товаров X=(x_i) и вектора цен P=(p_i) их скалярное произведение PX= =p₁x₁++p_nx_n есть число, называемое ценой набора или его стоимостью.

Множество К производственных процессов имеет в своей основе конечное число процессов (Q₁,,Q_m), которые называются базисными. Каждый базисный процесс представляет собой пару векторов Q_j=(,B_j) из С. (Векторы A_j, B_j – это векторы-столбцы. Содержательный смысл процесса Q_j таков: он затрачивает вектор А_j=(a_ij) и выпускает вектор B_j=(b_ij), т.е. перерабатывает вектор А_j в вектор B_j. По смыслу все векторы A_j, B_j неотрицательны. Обозначив А=(А₁,,А_m), B=(B₁,,B_m), получаем, что технология нашей модели задаётся парой неотрицательных матриц A, B; матрица A называется матрицей затрат, B – матрицей выпуска.

Комбинируя базисные процессы, можно получить новые процессы. Так, возьмём неотрицательные числа z_i, i=1,,m, и определим новый производственный процесс z₁Q₁++z_mQ_m, в котором затраты есть вектор , а выпуск есть вектор ; полученный производственный процесс кратко обозначим (AZ, BZ). Вектор-столбец Z=(z_i) называется вектором интенсивностей. Получившееся более широкое множество процессов и обозначим К.

Можно заметить, что в то время как базисные процессы Q₁,,Q_m соответствуют, вообще говоря, реальным отраслям, заводам, фабрикам, каждый элемент (X, Y)K есть некоторый фиктивный процесс, описывающий определённый режим совместной работы этих отраслей, заводов, фабрик. При этом X есть вектор затрат, Y – вектор выпуска.

Рассмотренная ранее модель Леонтьева есть частный случай модели Неймана при n=m, B=I. Основное отличие модели Неймана состоит в том, что всякий базисный процесс может выпускать не один продукт. Модель Неймана линейна.

Пример. Решим стандартную задачу на модель Неймана. Даны матрицы , технологических процессов, вектор цен P=(1, 5) и вектор начальных запасов Найдём интенсивности технологических процессов, максимизирующие стоимость выпуска продукции за один производственный цикл, и эту самую максимальную стоимость.

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

AZS

Z0

или (в развёрнутой форме)

30z₁+80z₂max

z₁, z₂ 0.

Решим эту задачу графическим методом.

Рис.21. Графический метод решения задачи на модель Неймана

Найдём координаты точки максимума.

-

Откуда 21z₁=42. Следовательно, z₁=2 и z₂=2.

Точка максимума (2, 2) и максимальная стоимость продукции, которая может быть выпущена за один цикл, равна 220.