- •4.Какие действия с целевой функцией не влияют на результат решения задачи линейного программирования?
- •13.Опишите последовательность решения канонической задачи линейного программирования с n переменными m линейных уравнений, если 1 n – m 2.
- •16.Сформулируйте теорему о существовании опорного решения.
- •18.Сколько базисов системы векторов условий кзлп может соответствовать одному опорному решению?
- •19.Сколько ненулевых координат может иметь опорное решение?
- •22.Чему соответствуют элементы столбца ограничений в симплекс-таблицы, приведенной к базису опорного решения?
- •25.Сформулируйте теорему о достаточном условии оптимальности опорного решения.
- •26.Сформулируйте теорему о неограниченности целевой функции кзлп.
- •29.Каков критерий выбора разрешающего элемента для перехода к новому опорному решению?
- •33.Записать искусственную задачу для данной канонической задачи линейного программирования и теорему о существовании опорного решения кзлп.
- •34.Когда искусственная каноническая задача линейного программирования имеет оптимальное решение?
- •35.При каком решении искусственной кзлп исходная задача имеет опорное решение?
- •36.При каком решении искусственной кзлп исходная задача не имеет решений?
- •38.Докажите теорему о разрешимости задачи линейного программирования на минимум.
- •39.Теорема (об оптимальном решении).
18.Сколько базисов системы векторов условий кзлп может соответствовать одному опорному решению?
Любому опорному решению канонической задачи линейного программирования соответствует, по крайне мере, один базис системы векторов условий этой задачи.
Доказательство
Пусть вектор α = ( 0, …,0, α i1 , 0,…, 0, αi2 , 0, …, 0, αil, 0, …, 0 ) является опорным решением канонической задачи линейного программирования
(1)f(X) = γj xj + γ0,
(2) Аj xj =B,
(3) xj ≥ 0, j = 1, 2, …, n.
где α i1>0 , αi2>0, …, αi> 0. Тогда по определению в системе векторов условий задачи (1) – (3) векторы Ai1, Ai2, …, Ai, соответствующие ненулевым координатам данного опорного решения, образуют линейно независимую систему векторов, которую можно дополнить до базиса всей системы векторов условий данной задачи. Пусть этим базисом будет система из векторов Ai1, Ai2, … Ai Ai+1, , …, Air . Тогда небазисным векторам из системы векторов условий задачи (1) – (3) соответствуют нулевые координаты опорного решения и по определению векторы Ai1, Ai2, …, Air образуют базис опорного решения α.
19.Сколько ненулевых координат может иметь опорное решение?
Число ненулевых координат у любого опорного решения α канонической задачи линейного программирования не превышает r = rang{ A1, …, An } – ранга системы векторов условий этой задачи.
Доказательство
Пусть вектор α = ( 0, …,0, α i1 , 0,…, 0, αi2 , 0, …, 0, αil, 0, …, 0 ) является опорным решением канонической задачи линейного программирования
(1)f(X) = γj xj + γ0,
(2) Аj xj =B,
(3) xj ≥ 0, j = 1, 2, …, n.
где α i1>0 , αi2>0, …, αi> 0. Тогда по определению в системе векторов условий задачи (1) – (3) векторы Ai1, Ai2, …, Ai, соответствующие ненулевым координатам данного опорного решения, образуют линейно независимую систему векторов, которую можно дополнить до базиса всей системы векторов условий данной задачи. Пусть этим базисом будет система из векторов Ai1, Ai2, … Ai Ai+1, , …, Air . Тогда небазисным векторам из системы векторов условий задачи (1) – (3) соответствуют нулевые координаты опорного решения и по определению векторы Ai1, Ai2, …, Air образуют базис опорного решения α.
Выше было доказано, что любому опорному решению КЗЛП соответствует хотя бы один базис системы векторов условий КЗЛП. Число векторов в любом базисе системы векторов условий КЗЛП совпадает с рангом этой системы. По определению базиса опорного решения, все координаты опорного решения α, соответствующие не базисным векторам системы векторов условий КЗЛП , равны нулю. Следовательно, ненулевых координат у опорного решения α не более, чем r.
22.Чему соответствуют элементы столбца ограничений в симплекс-таблицы, приведенной к базису опорного решения?
Если симплекс таблица приведенна к базису Аi1. Аi2, … , Аir опорного решения α, то в столбце В’ находятся координаты опорного решения α, соответствующие векторам базиса Аi1. Аi2, … , Аir , то есть α1’ = αi1, α2’ = αi2, …, αr’ = αir,
Доказательство
Так как вектор α = ( 0, 0, …, 0, αi1, 0, 0, …, 0, αi2, 0, 0, …, 0, αir, 0, 0, .., 0) является опорным решением задачи (1) – (3), то он является и допустимым решением этой задачи, а следовательно, является решением системы линейных уравнений (2), то есть выполняется соотношение: (6) Аi1 αi1+ Ai2 αi2+…+ Air αir = B.
Решением системы (5) является вектор α’ = ( 0, 0, …, 0, α1’, 0, 0, …, 0, α2’, 0, 0, … , 0, αr’, 0, 0, .., 0). Системы (5) и (4) равносильны, так как получены одна из другой методом Гаусса. Поэтому вектор α’ является решением системы (4), и, следовательно, выполняться соотношение: (7) Аi1 α1’+ Ai2 α2’+…+ Air αr’ = B.
Вычитая из соотношения (6) соотношение (7), получаем соотношение:
(8)Аi1 (αi1 – α1’ )+ Ai2 (αi2 – α2’ )+…+ Air (αir – αr’ ) = Ө.
Так как векторы Аi1. Аi2, … , Аir являются базисом системы векторов условий задачи (1) – (3), то они линейно независимы. Следовательно, соотношение (8) возможно, при αi1 – α1’ = 0, αi2 – α2’ = 0, …, αir – α1’ = 0. Откуда αi1 =α1’, αi2 = α2’, …, αir = α1’