Контрольная работа по "Математике". 96

№1. Сформулируйте определение числа и вектора Фробениуса неотрицательной матрицы. Сформулируйте теорему Фробениуса-Перрона.

Определение: Максимальное по модулю собственное значение λ_А неотрицательной матрицы А называется числом Фробениуса матрицы А, а соответствующий ему неотрицательный собственный вектор _А- вектором Фробениуса для А.

Теорема: 1) λ_А – действительное неотрицательное число. Существует неотрицательный собственный вектор _А, соответствующий данному собственному значению. 2) Если А>0, то λ_А>0 и существует положительный собственный вектор.

 

№2. Докажите следующее утверждение: если >0 - собственный вектор неотрицательной матрицы, то он является ее вектором Фробениуса.

Обозначим через α  собственное  значение, которому принадлежит вектор , следовательно, выполнено равенство А =α . Умножая его с лева на и учитывая А= λ_А , имеем А = λ_{А ,} так что α = λ_А . Поскольку по условию >0, то не равно нулю, так что α=λ_А, что и заканчивает доказательство.

 

№3. Докажите следующее утверждение. Пусть s и S –минимальная и максимальная суммы элементов столбцов матрицы А. Тогда число Фробениуса λ_А матрицы А удовлетворяет неравенству s< λ_А,S.

Дано: s и S – min и max суммы элементов столбцов матрицы A. λ_A – число Фробениуса. Доказать: s≤λ_A≤S.

Пусть _A – вектор Фробениуса, сумма координат которого равна 1, то есть l^T _A=1.   A A=λA A;

Учитывая, что  = ^TA, получим A=λ_А( ^T A), поэтому λ_А= A= s₁x₁+s₂x₂+…+s_nx_n и отсюда следует, что s(x₁+…+x_n) _A S(x₁+…x_n). Учитывая, что сумма координат вектора _A равна 1, из неравенства получаем s .

 

№4. Запишите структурную  таблицу и уравнение межотраслевого баланса Леонтьева для трехотраслевой модели экономики; укажите экономический  смысл входящих в уравнение величин. Запишите формулу вычисления элементов матрицы Леонтьева через известные элементы структурной таблицы межотраслевого баланса.

Произв. потребление	Конечное потребление	Валовой выпуск
X11 X12 … X1n	Y1	X1
X21 X22 … X2n	Y2	X2
…	…	…
X1n Xn2 ... Xnn	Yn	Xn

 – уравнение межотраслевого баланса (уравнение Леонтьева). Вектора валового выпуска -  , матрица прямых затрат – A, вектор конечного продукта - . а_ij= , где - объем продукции i отрасли, расходуемой в производстве j отраслью, - валовый выпуск j отрасли.

 

№.5 Сформулируйте  и докажите первый критерий продуктивности, т.е. теорему о том, что матрица  А≥0 продуктивна тогда и только тогда, когда матрица (E-A)^-1 существует и неотрицательна.

Пусть существует (E-A)^-1 ≥0, тогда x=(E-A)^{-1 *}y, где оба множителя > 0, следовательно, x≥0, а значит, матрица продуктивна. Пусть А продуктивна. (E-A)x=e₁, значит с₁≥0, (E-A)x=e₂, значит с₂≥0, следовательно, (с₁,с₂,c_n)=C≥0. (E-A)C=E≥C=(E-A)^-1≥0

 

 

 

№6. Докажите, что если неотрицательная квадратная матрица продуктивна, то её число Фробениуса меньше 1.

Пусть неотрицательная  матрица A продуктивна. Тогда для  любого неотрицательного вектора  существует решение уравнения . Пусть , тогда, очевидно, . Умножив равенство слева на левый вектор Фробениуса и учитывая, что , получим , или . Так как и , , то , . Поэтому из последнего равенства вытекает, что .

 

№ 7. Сформулируйте определение запаса продуктивности неотрицательной матрицы. Выведите формулу для вычисления запаса продуктивности через число Фробениуса.

Пусть А>0 – продуктивная матрица. Запасом продуктивности матрицы А назовем такое число α>0, что все матрицы λА, где 1<λ<1+α, продуктивны, а матрица (1+α)*А не продуктивна.

Выведение формулы: 1) А; 2) E-λA; 3) |E-λA|=0; 4) α=λ-1.

 

№ 8.  Запишите структурную  таблицу межотраслевого баланса  Леонтьева и уравнение модели равновесных цен для двухотраслевой экономики; укажите экономический  смысл входящих в уравнение величин. Запишите формулу вычисления через известные элементов матрицы Леонтьева через известные элементы структурной таблицы межотраслевого баланса.

Матрица Леонтьева:

A= |a11  a12|

      |a21  a22|

|E-A|= |1-a11    a12 |

           |a21     1-a22|

|E-A|^-1= 1/((1-a11)(1-a22)-(a21*a22)) * |1-a22   -a21 |

                                                                |-a12    1-a11|

_                  _

X=|E-A|^-1 * Y  _       _    _

Модель равновесных цен:   P=A^Tp + v, где вектор v=(v¹, v², … ,vⁿ)^T – вектор норм добавленной стоимости. Как мы видим, полученные уравнения очень похожи на уравнения модели Леонтьева, с той лишь разницей, что вектор х заменен на вектор р, вектор y – на вектор v, матрица А заменена на транспонированную - A^T.

Модель равновесных цен позволяет, зная величины норм добавленной стоимости, прогнозировать цены на продукцию отраслей. Она также позволяет прогнозировать изменение цен и инфляцию, являющиеся следствием изменения цены в одной из отраслей.

 

 

№9. Приведите примеры задач линейного программирования на минимум( задача о диете) и на максимум (задача об использовании ресурсов): текстовую формулировку и математическую постановку задачи.

Задача о  диете. Пусть имеется 2 вида продуктов П₁ и П₂, содержащих питательные вещества А, В, С. В 1кг продуктов П₁ и П₂ содержится определенное количество питательных веществ того или иного вида.

Известно: a, b, c – ежесуточное потребление А, В и С соответственно.

s₁,s₂ – стоимости 1 кг продуктов П₁ и П₂ соответственно.

Требуется рассчитать количество x₁ продукта П₁ и количество x₂ продукта П₂ так, чтобы обеспечить необходимое количество питательных веществ при min затратах на продукты.

Общая стоимость продуктов будет f = s₁x₁ + s₂x₂

Математическая задача о диете  состоит в отыскании значений неизвестных x₁, x₂, удовлетворяющих условиям:

 и f = s₁x₁ + s₂x₂ ® min

Задача об использовании ресурсов. Пусть ресурсы трех видов R₁, R₂, R₃ имеются в количествах соответственно b₁,b₂,b₃ в у.е.

Т₁,Т₂ – выпускаемые предприятием товары.

a_ij- число единиц ресурса R_i (i = 1, 2, 3), необходимое для производства единицы товара T_i (j = 1, 2).

с₁,с₂ – доход с единицы каждого вида товаров соответственно.

х₁, х₂ – количество товаров Т₁ и Т₂ соответственно.

Доход предприятия f = c₁x₁ + c₂x₂.

Математическая задача об использовании ресурсов состоит в отыскании значений неизвестных x₁, x₂, удовлетворяющих условиям:

   и  f = c₁x₁ + c₂x₂ ® max

 

№ 10. Приведите  общую постановку ЗЛП. Дайте определения  следующим терминам: целевая функция, допустимое множество задачи, оптимальное решение, оптимальное множество.

Если целевая функция  и система ограничений линейны, т. е. каждая из них имеет вид a₁x₁ + a₂x₂ + … +a_nx_n +b, то задача математического программирования называется задачей линейного программирования (ЗЛП).

На практике часто встречаются такие ситуации, когда достичь какого-то результата можно не одним, а несколькими  различными способами. Когда решений  много, ищется наилучшее. Математически  это сводится к задаче: найти max (min)  f(x) при условии, что переменная x пробегает некоторое заранее известное множество X. f(x) ® max(min), x ϵ Х.

Такая задача называется задачей оптимизации. Множество X называется допустимым множеством данной задачи, а функция f(x) – целевой функцией. Следует находить не только само значение max (min)  f, но и точку или точки, если их несколько, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений называют оптимальным множеством и обозначают X*.

 

 

№. 11. Что такое стандартная форма задачи линейного программирования? Что такое каноническая форма задачи линейного программирования? Приведите пример задачи, форма которой не является ни канонической, ни стандартной. Приведите эту задачу к канонической и стандартной формам.

Каноническая форма  ЗЛП, помимо нетривиальных  ограничений, включает в себя только уравнения (пример транспортная ЗЛП)

Стандартная форма ЗЛП  состоит только из неравенств, включая  тривиальные ограничения.

Пример 1. Привести данную ЗЛП к каноническому виду.

   2х₁ + х₃>=40                                 2х₁ + х₃ – x₄=40

   3х₂ + х₃ = 30     f=20х₁ + 5х₂ + 30х₃ -> min          3х₂ + х₃ = 30    

   Х_i >=0                                                                     Х_i >=0

 Пример 2. Привести заданную ЗЛП к стандартному виду.

    2х₁ + х₃>=40                                      2х₁ + х₃ >=40

    3х₂ + х₃ - x₄ = 30  f=20х₁ + 5х₂ + 30х₃ -> min  3х₂ + х₃ - 30>= 0    

    Х_i >=0                                                                          Х_i >=0                                                                        

 

№ 12. Опираясь на алгоритм графического метода, постройте две задачи линейного программирования с одной и той же целевой функцией f(x₁, x₂)=x₁+x₂, в одной из которых существует единственная точка максимума, а в другой – бесконечное множество точек минимума. Допустимую область задачи изобразите на чертеже и задайте системой неравенств.

1)  f(x₁, x₂)=x₁+x₂ -> max  2) f(x₁, x₂)=x₁+x₂  -> min

     x₁+x₂≤6 (1)  x₁+x₂≥3 (1)

     2x₁+x₂≤8 (2)   x₁+x₂≤6 (2)

     x₁≥0   x₂≥0   2x₁+x₂≤8(3)

  x₁≥0   x₂≥0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Точка максимума единственная – с координатами (2;4). Координаты мы получили, приравняв (1) и (2).

 

 

№ 13. Опираясь на алгоритм графического метода, постройте две задачи линейного программирования с одной и той же целевой функцией f(x₁, x₂)=x₁+x₂, в одной из которых существует единственная точка минимума, а в другой – бесконечное множество точек максимума. Допустимую область задачи изобразите на чертеже и задайте системой неравенств.

1)     f(x1, x2)=x1+x2  ->   min        x1+x2≤6 (1)        2x1+x2≤8 (2)        x1≥0   x2≥0 Точка минимума единственная и совпадает с началом координат, т.е. имеет координаты (0;0)

2) f(x1, x2)=x1+x2   ->   max      x1+x2≤6 (1)      x1≥0   x2≥0   Линия уровня совпадает  с единственной прямой (1), поэтому  существует множество точек максимума.

14. Опираясь  на алгоритм графического метода, постройте две задачи линейного  программирования с одной и той же целевой функцией f(x₁, x₂)=x₁+x₂, в одной из которых существует единственная точка минимума, а в другой целевая функция не ограничена сверху. Допустимую область задачи изобразите на чертеже и задайте системой неравенств.

1)    f(x1, x2)=x1+x2  -->    min       x1+x2≤6 (1)       2x1+x2≤8 (2)       x1≥0   x2≥0                                    ●       Точка минимума единственная и совпадает  с началом координат, т.е. имеет  координаты (0;0).

2)   f(x1, x2)=x1+x2   -->    max       x1+x2≥6 (1)      2x1-x2≤24 (2)       x1≥0   x2≥0                                       Функция не ограничена сверху, поэтому fmax=∞.

15. Опираясь  на алгоритм графического метода, постройте две задачи линейного  программирования с одной и  той же целевой функцией f(x₁,x₂) = x₁ + x_2, в одной из которых существует единственная точка максимума, а в другой целевая функция не ограничена снизу. Допустимую область задачи изобразите на чертеже и задайте системой неравенств.

А)  f(x₁,x₂) = x₁ + x₂  à max

        x₁ + 2x₂ ≤ 16

       2x₁ + x₂  ≤ 14

       3x₁ + 3x₂  ≥ 6

       x₁, x₂  ≥ 0

Б) f(x₁,x₂) = x₁ + x₂ à max

      x₂ ≤   2

      x₁ + x₂ ≤ 15

      x₁ ≥ 0

 

16. Опираясь на алгоритм  графического метода, постройте  две задачи линейного программирования  с одной и той же целевой  функцией f(x₁,x₂) = x₁ + x_2, в одной из которых существует бесконечное множество точек минимума, а в другой целевая функция не ограничена сверху. Допустимую область задачи изобразите на чертеже и задайте системой неравенств.

А)      f(x₁,x₂) = x₁ + x₂ à min

x₁ + x₂ ≥ 1

0 ≤  x₂  ≤ 3

0 ≤  x₁ ≤  4

 

Задача имеет бесконечное  множество точек минимума

Б)      f(x₁,x₂) = x₁ + x₂ à max

x₁ - x₂ ≥ -3

x₁ - x₂ ≤   -3

x₁, x₂  ≥ 0

 

 

Функция не ограничена сверху

 

17. Опираясь  на алгоритм графического метода, постройте две задачи линейного программирования с одной и той же целевой функцией f(x₁,x₂) = x₁ + x_2, в одной из которых существует бесконечное множество точек максимума, а в другой целевая функция не ограничена снизу. Допустимую область задачи изобразите на чертеже и задайте системой неравенств.

А)  f(x₁,x₂) = x₁ + x₂ à max

x₁ + x₂ ≥ 5

x₁, x₂  ≥ 0

Задача имеет бесконечное 

множество точек максимума

 

 

 

 

Б) f(x₁,x₂) = x₁ + x₂ à max

x₂ ≤   2

x₁ + x₂ ≤ 15

x₁ ≥ 0

Функция не ограничена снизу

 

№ 18. Рассматривается задача линейного программирования, в которой целевая функция исследуется на минимум. Является ли симплекс-таблица окончательной?

БП	X1	X2	X3	X4	СЧ
X3	5	-2	1	0	3
X4	-1	3	0	1	4
F	-2	-3	0	0	-10

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

Ответ: х₁=0, х₂=0, х₃=3, х₄=4, f _min=10

 

№ 19. Рассматривается задача линейного программирования, в которой целевая функция исследуется на минимум. Является ли симплекс-таблица окончательной?

БП	X1	X2	X3	X4	СЧ
X3	5	-2	1	0	3
X4	-1	3	0	1	4
F	-2	3	0	0	10

Не окончательная, т.к. в последней строке есть положительные  элементы.

5  -2  1   0  3            -13/3   0   1   2/3   1/3

-1  3  0   1  4   ->     -1/3     1   0    1/3   4/3

-2  3 0   0  10           -1       0    0     -1      6

Ответ: f_min=6, единственное решение.

 

№ 20. Рассматривается  задача линейного программирования, в которой целевая функция  исследуется на минимум. Является ли симплекс-таблица окончательной?

БП	X1	X2	X3	X4	СЧ
X3	-5	-2	1	0	3
X4	-1	3	0	1	4
F	-2	3	0	0	10

Не окончательна. Так как в целевой функции (последняя строка) есть положительный элемент =3. В столбце с этим положительным элементом есть положительное число (во второй строке) = 3. Ее и возьмем за разрешающий элемент:

БП	X1	X2	X3	X4	СЧ
Х3	-17/3	0	1	2/3	17/3
Х2	1/3	1	0	1/3	4/3
F	-1	0	0	-1	6

F(0,4/3,17/3,0)=6 – окончательное решение. Так как последняя строка не содержит положительных элементов, а в силу того, что функция исследуется на минимум, то план нас устраивает.

 

№ 21. Рассматривается  задача линейного программирования, в которой целевая функция  исследуется на минимум. Является ли симплекс-таблица окончательной?

БП	X1	X2	X3	X4	СЧ
X3	5	-2	1	0	3
X4	-1	3	0	1	4
F	0	-3	0	0	10

Окончательная, т.к. в  последней строке не положительных элементов.

Ответ: f_min=10, единственность решения.

 

№ 22. Рассматривается  задача линейного программирования, в которой целевая функция  исследуется на максимум. Является ли симплекс-таблица окончательной?

БП	X1	X2	X3	X4	СЧ
X3	5	-2	1	0	3
X4	-1	3	0	1	4
F	2	3	0	0	10

Окончательная, т.к. в  последней строке нет отрицательных  элементов.

Ответ: f_max=10, единственность решения.

 

№ 23. Рассматривается  задача линейного программирования, в которой целевая функция  исследуется на максимум. Является ли симплекс-таблица окончательной?

БП	X1	X2	X3	X4	СЧ
X3	5	-2	1	0	3
X4	-1	3	0	1	4
F	-2	3	0	0	10

f_max=-f_min

Т.к в последней  строке есть положительный элемент, а в соответствующем ему столбце есть положительный элемент, то решение может быть улучшено. Выполняем шаг симплекс метода

БП	Х1	Х2	Х3	Х4	СЧ
Х1	1	-2/5	1/5	0	3/5
Х4	0	13/5	1/5	1	23/5
F	0	11/5	2/5	0	56/5

Т.к. в последней строке у нет отрицательных элементов, то для нашей функции, исследуемой на максимум, таблица является окончательной f _max (3/5,0,0,23/5) = 11 + 1/5 = 56/5

 

 

№ 24. Рассматривается задача линейного  программирования, в которой целевая функция исследуется на максимум. Является ли симплекс-таблица окончательной?

БП	Х1	Х2	Х3	Х4	СЧ
Х3	5	-2	1	0	3
Х4	-1	-3	0	1	4
F	2	-3	0	0	10
F	-2	3	0	0	-10

maxF=-minF

В последней строке есть положительный элемент, но в соответствующем  ему столбце (не учитывая строку F)  нет положительных элементов, следовательно maxf = -minf=беск

 

№ 25. Рассматривается  задача линейного программирования, в которой целевая функция исследуется на максимум. Является ли симплекс-таблица окончательной?

БП	Х1	Х2	Х3	Х4	СЧ
Х3	5	-2	1	0	3
Х4	-1	3	0	1	4
F	0	3	0	0	10
F	0	-3	0	0	-10

Данная таблица –  окончательная, потому что в строке оценок задачи максимум отсутствуют отрицательные оценки. Решение рассматриваемой задачи линейного программирования имеет вид f_max=f(0;0;3;4)=10. Поскольку нулевая оценка присутствует в небазисном столбце (x₁), решение не единственно.

 

№ 26. Приведите пример двух взаимно двойственных задач линейного программирования. Сформулируйте правило построения двойственной задачи. Исходная задача линейного  программирования: = c1x1 + c2x2 + ... + cnxn → max;
a11x1+ a12x2 + ... + a1nxn ≤ b1,  a21x1 + a22x2 + ... + a2nxn ≤ b2, ...             am1x1 + am2x2 + ... + amnxn ≤ bm;
xj ≥ 0,
Двойственная ей задача: = b1y1 + b2y2 + ... + bmym → min;
a1a11y1 + a21y2 + ... + am1ym ≥ c1,  a12y1 + a22y2 + ... + am2ym ≥ c2, ...             a1ny1 + a2ny2 + ... + amnym ≥ cn;
yi ≥ 0,   .

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется  максимум целевой функции, то  в двойственной ей - минимум. 

2. Коэффициенты при переменных  в целевой функции одной задачи  являются свободными членами  системы ограничений другой задачи.

3. В исходной ЗЛП все функциональные  ограничения - неравенства вида  “≤”, а в задаче, двойственной  ей, - неравенства вида “≥”. 

4. Коэффициенты при переменных  в системах ограничений взаимно  двойственных задач описываются  матрицами, транспонированными относительно друг друга.

5. Число неравенств в системе  ограничений одной задачи совпадает  с числом переменных в другой.

6. Условие неотрицательности  переменных сохраняется в обеих  задачах. 
№ 27. Сформулируйте и докажите основное неравенство для взаимно двойственных задач линейного программирования. Сформулируйте достаточный признак оптимальности.

Основное нер-во двойственности. Пусть Х – какое-нибудь допустимое решение задачи I, а У – какое-нибудь допустимое решение задачи II. Тогда справедливо неравенство f(x)<φ(Y)

Доказательство: Имеем AX<B, откуда следует (АХ)^T<B^T или X^TA^T<B^T. Умножим обе части этого неравенства справа на матрицу У>0=0, получим (X^TA^T)Y<B^TY или, в ввиду ассоциативности умножения матриц,

X^T(A^TY)<B^TY=φ(Y) (I)

Аналогично имеем ATY>С; умножив обе части слева на матрицу XT>0, будем иметь

X^T(A^TY)>X^TC=f(X) (II)

Соединяя два полученных неравенства I и II, можем записать

F(X)<X^TA^TY< φ(Y),

откуда и следует  основное неравенство f(X)< φ(Y).

 

№ 28. Сформулируйте первую и вторую теоремы двойственности. Докажите вторую теорему двойственности.

Первая теорема  двойственности. Если исходная задача имеет оптимальное решение, то и двойственная ей также имеет оптимальное решение. При этом оптимальные значения целевых функций обеих задач равны: f_max=g_min.

Вторая теорема  двойственности. Если хотя бы одно оптимальное решение одной из двойственных задач обращает  
i-е ограничение этой задачи в строгое неравенство, то i-я компонента (т.е. x_i или u_i) каждого оптимального решения второй двойственной задачи равна нулю.

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

Доказательство: Пусть и – оптимальные решения пары двойственных задач. Тогда для  , 

Они удовлетворяют следующим ограничениям:

.     (3)

Умножим (3), соответственно, на и , и просуммируем полученные выражения:

.    (4)       

Из основной теоремы  двойственности следует

.                                                  (5)

И с учетом (4) получаем:

, .

Первое из этих выражений  можем переписать в виде ,

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