- •Оглавление
- •1. Теорема Фробениуса-Перрона. Определение числа и вектора Фробениуса неотрицательной матрицы.
- •2. Вектор валового выпуска, вектор конечного потребления, матрица прямых затрат.
- •3. Уравнение межотраслевого баланса. Модель Леонтьева. Продуктивная матрица.
- •4. Первый и второй критерии продуктивности.
- •6. Докажите, что если неотрицательная квадратная матрица продуктивна, то ее число Фробениуса меньше 1.
- •7. Задача оптимизации. Допустимое множество. Целевая функция.
- •8. Оптимальное решение. Оптимальное множество. Задача линейного программирования (злп).
- •9. Примеры злп. Задача о банке, задача о диете, задача об использовании ресурсов.
- •10. Каноническая и стандартная формы злп. Приведение злп к стандартному и каноническому виду. Примеры.
- •11. Теоремы о существовании оптимального решения злп и о его достижимости в угловой точке в случае ограниченной целевой функции
- •12. Теорема о структуре множества оптимальных решений
- •13. Графический метод решения злп.
- •14. Симплекс-метод. Допустимый вид системы ограничений, допустимый базис, условие неотрицательности свободных членов.
- •15. Симплекс-таблица. Строка оценок. Условие оптимальности базисного решения. Условие неограниченности целевой функции. Условие существования альтернативного решения. Примеры.
- •16. Теорема о конечности симплекс-алгоритма (без доказательства).
- •17. Постановка взаимно-двойственных задач.
- •18. Основное неравенство для двойственных задач (с доказательством). Достаточный признак оптимальности.
- •19. Основная теорема двойственности. Критерий оптимальности (без доказательства).
- •20. Теорема равновесия (с доказательством).
- •21. Постановка транспортной задачи (тз).
- •22. Критерий разрешимости тз (с доказательством).
- •23. Методы построения начального опорного плана тз (метод северо-западного угла, метод минимального тарифа).
- •24. Метод потенциалов. Оценки свободных клеток. Перестановка по циклу. Условие оптимальности опорного плана.
- •25. Определение разностного уравнения порядка k . Общее решение разностного уравнения k -го порядка.
- •26. Линейное разностное уравнение k -ого порядка с постоянными коэффициентами. Теоремы об общем решении однородного и неоднородного линейного разностного уравнения (без доказательства).
- •27. Фундаментальный набор решений линейного разностного уравнения. Характеристическое уравнение. Определитель Казоратти.
- •28. Теорема о частном решении линейного неоднородного разностного уравнения (без доказательства).
- •29. Модель Самуэльсона-Хикса. Уравнение Хикса. Мультипликатор Кейнса.
- •30. Паутинная модель рынка.
- •31. Задача об определении текущей стоимости купонной облигации.
22. Критерий разрешимости тз (с доказательством).
Общее количество товара у поставщиков равно mi=1∑ai , a общая потребность в товаре в пунктах назначения есть nj=1∑bj , . Если mi=1∑ai = nj=1∑bj , т. е. суммарные запасы поставщиков равны суммарным запросам потребителей, то такая задача называется задачей с правильным балансом, а ее модель — закрытой.
Критерий разрешимости транспортной задачи — транспортная задача разрешима только, если она имеет правильный баланс.
23. Методы построения начального опорного плана тз (метод северо-западного угла, метод минимального тарифа).
Начальным опорным планом называется план перевозок X=(xij), который удовлетворяет всем ограничениям транспортной задачи. Начальный опорный план находят, заполняя не более чем m+n-1 клеток (по числу базисных переменных). Любое допустимое решение транспортной задачи можно записать в транспортную таблицу. Клетки транспортной таблицы, в которых находятся отличные от нуля (или базисные ненулевые) перевозки, называются занятыми, остальные — свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку xij , т. е. стоящая в i-ой строке и j-ом столбце, имеет номер (i,j).
При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x11 (“северо-западный угол”) и заканчивается для неизвестного xmn, т. е. идет как бы по диагонали таблицы с севера на запад.
Согласно методу минимального тарифа, выбор заполняемых клеток производят, ориентируясь на тарифы перевозок, а именно: на каждом шаге выбирают какую-нибудь клетку (i,j), равную минимальному тарифу и помещают в нее максимально возможную перевозку xij . После этого обнуляют либо столбец, либо строку в зависимости от соотношения xij=b или xij=a.
24. Метод потенциалов. Оценки свободных клеток. Перестановка по циклу. Условие оптимальности опорного плана.
Метод потенциалов используется для оценки плана. Он основан на следующей теореме: Если допустимое решение X=(xij)(i= (1;m);j= (1;n)) транспортной задачи является оптимальным, то существуют потенциалы поставщиков u1(i= (1;m)) и потребителей
v1(j= (1;n)) , удовлетворяющие условиям: u1+ v1 = cij, если xij>0, u1+ v1 ≤ cij, если xij=0.
Равенства u1+ v1 = cij, при xij>0, используются для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одно из них можно задать произвольно (как правило его берут нулевым), а остальные найти из системы.
Неравенства u1+ v1 ≤ cij, при xij=0 используются для проверки оптимальности опорного решения. Эти неравенства удобно записать в виде ∆ij = u1+ v1 - cij, при xij=0.
Числа ∆ij называются оценками свободных клеток таблицы, не входящих в базис опорного решения. В этом случае признак оптимальномти можно сформулировать так же как в симплекс-методе (в задаче на минимум): опорное решение является оптимальным, если для всех клеток таблицы оценки неположительные.
Если же ∆ij >0, то для соответствующей клетки строят цикл и улучшают решение, перераспределяя груз t=min (xij) по этому циклу. Сдвигом по циклу на величину t называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на t и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на t.