Критерий разрешимости ТЗ (с доказательством).

       Общее количество товара у поставщиков равно ^m_i=1∑a_i, a общая потребность в товаре в пунктах назначения есть ⁿ_j=1∑b_j,. Если ^m_i=1∑a_i = ⁿ_j=1∑b_j, т. е. суммарные запасы поставщиков равны суммарным запросам потребителей, то такая задача называется задачей с правильным балансом, а ее модель — закрытой.

       Критерий разрешимости транспортной задачи — транспортная задача разрешима только, если она имеет правильный баланс.

23. Методы построения начального опорного плана ТЗ (метод северо-западного угла, метод минимального тарифа).

       Начальным опорным планом называется план перевозок X=(x_ij), который удовлетворяет всем ограничениям транспортной задачи. Начальный опорный план находят, заполняя не более чем m+n-1 клеток (по числу базисных переменных). Любое допустимое решение транспортной задачи можно записать в транспортную таблицу. Клетки транспортной таблицы, в которых находятся отличные от нуля (или базисные ненулевые) перевозки, называются занятыми, остальные — свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку x_ij, т. е. стоящая в i-ой строке и j-ом столбце, имеет номер (i,j).

       При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x₁₁ (“северо-западный угол”) и заканчивается для неизвестного x_mn, т. е. идет как бы по диагонали таблицы с севера на запад.

       Согласно методу минимального тарифа, выбор заполняемых клеток производят, ориентируясь на тарифы перевозок, а именно: на каждом шаге выбирают какую-нибудь клетку (i,j), равную минимальному тарифу и помещают в нее максимально возможную перевозку x_ij. После этого обнуляют либо столбец, либо строку в зависимости от соотношения x_ij=b или x_ij=a.

 

24. Метод потенциалов. Оценки свободных клеток. Перестановка по циклу. Условие оптимальности опорного плана.

       Метод потенциалов используется для оценки плана. Он основан на следующей теореме: Если допустимое решение X=(x_ij)(i= (1;m);j= (1;n)) транспортной задачи является оптимальным, то существуют потенциалы поставщиков u₁(i= (1;m)) и потребителей

v₁(j= (1;n)), удовлетворяющие условиям: u₁+ v₁ = c_ij, если x_ij>0, u₁+ v₁≤ c_ij, если x_ij=0.

           Равенства u₁+ v₁ = c_ij, при x_ij>0, используются для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одно из них можно задать произвольно (как правило его берут нулевым), а остальные найти из системы.

           Неравенства  u₁+ v₁≤ c_ij, при x_ij=0 используются для проверки оптимальности опорного решения. Эти неравенства удобно записать в виде ∆_ij = u₁+ v₁- c_ij, при x_ij=0.

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

       Если же ∆_ij >0, то для соответствующей клетки строят цикл и улучшают решение, перераспределяя груз t=min (x_ij) по этому циклу. Сдвигом по циклу на величину t называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на t и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на t.

 

25. Определение разностного уравнения порядка k. Общее решение разностного уравнения k -го порядка.

       Уравнение вида F(n;x_n;x_n+1;...;x_n+k)=0, где k-фиксированное, а n-произвольные натуральные числа, x_n;x_n+1;...;x_{n+k —} члены некоторой неизвестной числовой последовательности, называется разностным уравнением порядка k.

           Общим решением разностного уравнения k-го порядка называется его решение

x_n=φ(n; C₁; C₂;...;C_k), зависящее от k независимых произвольных постоянных  C₁; C₂;...;C_k. Количество k постоянных равно порядку разностного уравнения, а независимость означает, что ни одно из постоянных нельзя выразить через другие.

 

26. Линейное разностное уравнение k -ого порядка с постоянными коэффициентами. Теоремы об общем решении однородного и неоднородного линейного разностного уравнения (без доказательства).

Линейным разностным уравнением k-ого порядка с постоянными коэффициентами называется уравнение вида:

, где a_i – постоянные коэффициенты ().

Теорема об общем решении линейного неоднородного уравнения.

Общее решение линейного неоднородного разностного уравнения  есть сумма частного решения  этого уравнения и общего решения соответствующего ему однородного уравнения.

Теорема об общем решении линейного однородного уравнения.

Пусть  - система, состоящая из k линейно независимых решений линейного однородного разностного уравнения, тогда общее решение этого уравнения задается формулой: .