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

Предприятие состоит из n цехов. Каждый цех выпускает только один вид продукции. Пусть j-й цех выпускает x_j единиц продукции, из которых y_j единиц отправляет за пределы предприятия как товарную продукцию, а остающаяся часть используется другими цехами предприятия.

Пусть a_jk – кол-во продукции j-го цеха, расходуемое на производство единицы продукции k-го цеха. Числа a_ij образуют матрицу А коэффициентов прямых затрат, называемую структурной. Производственная программа предприятия представляется вектором X(x₁, …, x_n), а выпуск товарной продукции – вектором У(у₁, …, у_n). Очевидно, (Е - А)Х = У или Х = (Е - А)^-1У.

Элементы любого столбца матрицы (Е - А)^-1, называемой матрицей коэффициентов полных затрат, показывают затраты всех цехов, необходимые для обеспечения выпуска единицы товарного продукта того цеха, номер которого совпадает с номером данного столбца.

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

Дополним структурную матрицу А матрицей В коэффициентов прямых затрат, получаемых со стороны сырья, полуфабрикатов и т.п. Очевидно, затраты получаемых со стороны материалов определяются элементами матрицы S, где H *У = S, а H=В* (Е - А)^-1– матрица коэффициентов полных затрат сторонних материалов.

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

Пусть даны:

Найдем Q^-1методом Крамера:

Q-1=	-30/7 10/7 30/7 50/7 -40/7 20/7 10/7 20/7 -10/7

Проверка:

Найдем вектор-столбец производственной программы:

X= Q^-1 *Y

Найдем матрицу коэффициентов полных затрат сторонних материалов – H.

H= B* Q^-1

B* Q-1=

7 6 8 3 0 4 * 32 24 28 0 0,2 0,3

-30/7 10/7 30/7 50/7 -40/7 20/7 = 10/7 20/7 -10/7

12 6/7 38 4/7 15 5/7 -12 6/7 11 3/7 14 2/7 17 1/7 171 3/7 74 2/7 1 4/7 -2/7 1/7

=H

Элементы матрицы H находят по следующим формулам:

h11= -30/7*7+10/7*6+30/7*8=12 6/7

h21= 50/7*4-40/7*3+20/7*0=-12 6/7

…

h43=10/7*0+20/7*0,2-10/7*0,3=1/7.

Полные затраты всех ресурсов S= H *У:

Таким образом получили:

Вектор производственной программы

Полные затраты всех ресурсов

Кратчайший путь на графе.

Пусть дан граф G=(X,U). Каждой дуге графа поставим в соответствие положительное число l(u). Это число можно назвать длиной дуги. Тогда за длину пути μ принимается сумма длин дуг, входящих в μ:

L(μ)= Σ l(u)

uÎ μ

Выделяются две вершины графа – a и b. Требуется на графе G найти путь кратчайшей длины из вершины a в вершину b.

Алгоритм решения задачи:

1. Перенумеровать вершины графа G так, чтобы вершина a получила обозначение x0, а вершина b – xn (последняя по обозначению вершина).

2. Присвоить каждой вершине xi начальную метку λi: λ0=0, λi =+∞ (i>0).

3. Найти дугу u=uij=(xi,xj), для которой выполняется неравенство λi – λj >l(uij) (полагая, что ∞ – ∞=0). Для вершины xj заменить метку на новую, меньшую, метку λj = λj+l(uij).

4. Процедуру, описанную в п.3, осуществлять до тех пор, пока для каждой дуги uij не станет справедливым неравенство λj – λi ≤l(uij)

5. Найти вершину xk ÎF^-1 *xn, для которой λn = λk+l(ukn), затем вершину xm ÎF^-1 *xk, для которой λk = λm+l(umk) и т.д. После некоторого числа шагов вершина xp совпадет с вершиной x0=a. Путь μ=(a= xp,…, xm, xk, xn =b) будет кратчайшим, и его длина равна λn.

Пусть дан граф:

Решение:

Ответ: кратчайший путь из пункта 0 в пункт 8 составляет 10 через точки (x0, x1, x2, x7, x8).