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

А)      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) получаем:

, .

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

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