8. Решение транспортной задачи. Проверка оптим. Методом потенциалов. Улучшение плана по методу потенциалов.

9. Задачи целочисленного программирования. Задача о назначениях. Постановка. Примеры.

Целочисленная задача линейного программирования заключа­ется в максимизации функции:

 (1)

при условиях

 (2)

 

где J — некоторое подмножество множества индексов N = ={1,2,...,n}.

Если J = N (T.e. требование целочисленности наложено на все переменные), то задачу называют полностью целочисленной; если же J ¹ N, она называется частично целочисленной.

Задача о назначении

Имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность  , связанная с выполнением i-м исполнителем j-й работы  . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должне быть закреплен только один исполнитель.

Математическая модель задачи примет вид:

Каждый исполнитель назначается только на одну работу:

На каждую работу назначается только один исполнитель:

Условия неотрицательности и целочисленности

, .

10. Балансовая таблица. Смысл всех элементов. Связи в таблице.

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

Одной из задач балансового анализа является определение валового продукта  , если известно распределение конечного  . Для этого введем коэффициенты прямых затрат:        .                                                 (7.3)      Они получаются в результате деления всех элементов каждого столбца матрицы   на соответствующий элемент матрицы межотраслевых производственных связей Х. Коэффициенты прямых затрат имеют смысл количества потребления продукции j-й отрасли, необходимой для производства единицы продукции i-й отраслью. Из выражения (3) можно получить:  . Подставив последнее выражение в соотношение баланса (1), получим:        .                                       (7.4)      Если обозначить матрицу коэффициентов прямых затрат как  , то соотношение баланса (4) в матричном виде можно записать в виде:       .                                         (7.5)      Из последнего выражения можно найти значение конечного продукта при известном значении валового:        ,                               (7.6)      где   - единичная матрица того же размера, что и А.

12. Матричная форма записи балансовых уравнений. Решение системы матричным методом.

Введем в рассмотрение векторы-столбцы объёмов произведенной продукции (вектор валового выпуска), объёмов продукции конечного потребления (вектор конечного потребления) и матрицу коэффициентов прямых затрат: на листочке Тогда система уравнений (3) в матричной форме имеет вид: (4) Обычно это соотношение называют уравнением линейного межотраслевого баланса. Уравнение межотраслевого баланса можно использовать в двух целях.В первом, наиболее простом случае, когда известен вектор валового выпуска  , требуется рассчитать вектор конечного потребления  : из (4) следует, что  , где E – единичная матрица той же размерности, что и матрица прямых затрат A. Во втором случае уравнение межотраслевого баланса используется для целей планирования со следующей формулировкой задачи: для периода времени Т (например, год) известен вектор конечного потребления   и требуется определить вектор   валового выпуска. Здесь необходимо решать систему линейных уравнений (4) с известной матрицей A и заданным вектором  . Из (4) следует, что  где   обратная матрица. Она называется матрицей полных затрат.  Если решение уравнения (4) существует, то матрица A называется продуктивной. Пусть дана система   линейных уравнений с   неизвестными: 

где

     

Будем предполагать, что основная матрица   невырожденная.  Тогда, по теореме 3.1, существует обратная матрица   Помножив матричное уравнение   на матрицу   слева, воспользовавшись определением 3.2, а также утверждением 8) теоремы 1.1, получим формулу, на которой основан матричный метод решения систем линейных уравнений:

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

Пример. Решить систему линейных уравнений матричным методом.

Задана система трёх линейных уравнений с тремя неизвестными   где

   

Основная матрица системы уравнений невырожденная, поскольку её определитель отличен от нуля:

Обратную матрицу   составим одним из методов, описанных в пункте 3.

По формуле матричного метода решения систем линейных уравнений получим