Главная / Алгоритмы и дискретные структуры /
Введение в математическое программирование / Тест 4
Введение в математическое программирование - тест 4
Упражнение 1:
Номер 1
Пусть ограничения задачи линейного программирования записаны в виде:
A1x1+A2x2+...+Anxn+An+1xn+1+...+An+mxn+m=A0
,
где А1,...,Аm
– множество линейно независимых векторов. Согласно симплекс – метода,
базисное решение определяется уравнением:
Ответ:
 
(1)
 
 
(2)
 
 
(3)
 
Номер 2
Уравнение определяет базисное решение согласно симплекс – методу,
если ограничения задачи линейного программирования имеют вид:
Ответ:
 (1)
A1x1-A2x2-...-Anxn-An+1xn+1-...-An+mxn+m=A0
;
 
 (2)
A1x1-A2x2+...+Anxn-An+1xn+1+...+An+mxn+m=A0
;
 
 (3)
A1x1+A2x2+...+Anxn+An+1xn+1+...+An+mxn+m=A0
.
 
Номер 3
Согласно симплекс – метода, верное базисное решение
при ограничениях задачи линейного программирования
A1x1+A2x2+...+Anxn+An+1xn+1+...+An+mxn+m=A0
имеет вид:
Ответ:
 (1)  
 (2)
A1x1-A2x2-...-Anxn-An+1xn+1-...-An+mxn+m=A0
;
 
 (3)
A1x1-A2x2+...+Anxn-An+1xn+1+...+An+mxn+m=A0
.
 
Упражнение 2:
Номер 1
Пусть уравнение определяет базисное решение . Предположим,
что это решение допустимо, т.е. . Если Аr
не входит в базис, то:
Ответ:
 (1) A1x1r+A2x2r+...+Amxmr ≥ Ar
 
 (2) A1x1r+A2x2r+...+Amxmr = Ar
 
 (3) A1x1r+A2x2r+...+Amxmr ≤ Ar
 
Номер 2
Пусть уравнение определяет базисное решение . При этом
Ar
не входит в базис, т.е. справедливо равенство:
A1x1r+A2x2r+...+Amxmr = Ar
.
Тогда базисное решение имеет вид:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Пусть уравнение определяет базисное решение , которое является
допустимым, т.е. . При этом справедливо равенство:
A1x1r+A2x2r+...+Amxmr = Ar
.
Это значит, что:
Ответ:
 (1) Ar
не входит в базис 
 (2) Ar
входит в базис 
 (3) Ar
выражается через этот базис 
Упражнение 3:
Номер 1
Пусть уравнение определяет базисное решение .
Обозначим решение уравнения A1x1+A2x2+...+Amxm+Arxr = А0
как . Тогда связь нового решения
со старым базисным решением
выражается следующими соотношениями:
Ответ:
 (1)  
 (2)  
 (3)  
Номер 2
Уравнение определяет базисное решение .
Новое решение связано со старым базисным решением
соотношениями:
Тогда уравнение имеет вид:
Ответ:
 (1)
A1x1-A2x2+...+Amxm-Arxr = А0
;
 
 (2)
A1x1-A2x2-...-Amxm-Arxr = А0
;
 
 (3)
A1x1+A2x2+...+Amxm+Arxr = А0
 
Упражнение 4:
Номер 1
Пусть уравнение определяет базисное решение .
Новое решение базисное решение связано со старым базисным
решением соотношениями:
.
Данное решение будет допустимым, если:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Новое базисное решение уравнения
A1x1+A2x2+...+Amxm+Arxr = А0
имеет вид .
При этом имеет место соотношение: .
Тогда новое решение:
Ответ:
 (1) не является допустимым 
 (2) является допустимым 
 (3) является базисным 
Номер 3
Пусть уравнение
A1x1+A2x2+...+Amxm+Arxr = А0
имеет решение .
Данное решение:
Ответ:
 (1) будет допустимым для всех значений xr
 
 (2) не будет допустимым ни для каких значений xr
 
 (3) будет допустимым не для всех значений xr
 
Упражнение 5:
Номер 1
Пусть новое решение уравнения
A1x1+A2x2+...+Amxm+Arxr = А0
имеет вид ,
и при этом выполняется соотношение , т.е. данное решение
является допустимым. Чтобы данное решение являлось базисным, необходимо:
Ответ:
 (1) вывести переменную xi
из базисного решения, а соответствующий вектор – из базиса 
 (2) ввести дополнительную переменную xi
в базисное решение, а соответствующий вектор – в базис 
 (3) вывести переменную xi
из базисного решения, и ввести дополнительный вектор в базис 
Номер 2
Пусть новое решение уравнения
A1x1+A2x2+...+Amxm+Arxr = А0
имеет вид ,
и при этом является допустимым. Выведем одну переменную xi
из базисного решения, а
соответствующий вектор из базиса. Тогда новое базисное решение имеет вид:
Ответ:
 
(1)
 
 
(2)
 
 
(3)
 
Номер 3
Решение уравнения
A1x1+A2x2+...+Amxm+Arxr = А0
имеет вид ,
и при этом выполняется соотношение .
Выведем одну переменную xi
из базисного решения, а соответствующий вектор из базиса.
Новое решение имеет вид .
Данное решение:
Ответ:
 (1) не является базисным 
 (2) является базисным 
 (3) является допустимым 
Упражнение 6:
Номер 1
Если для табличного симплекс – метода в качестве начального базиса выбирают базис из свободных
переменных, для которых ci = 0
, и оценки для всех небазисных переменных равны
Δj=a0j=-cj
, то соответствующее значение целевой функции
определяется соотношением:
Ответ:
 (1) a00 = Σcixi > 0, i є I;
 
 (2) a00 = Σcixi = 0, i є I;
 
 (3) a00 = Σcixi < 0, i є I;
 
Номер 2
Для табличного симплекс – метода в качестве начального базиса выбран базис из свободных переменных,
для которых ci = 0
. Соответствующее значение целевой функции определяется соотношением
a00 = Σcixi = 0, i є I
. Тогда оценки для всех небазисных
переменных равны:
Ответ:
 (1) Δj=a0j=-cj
 
 (2) Δj=-a0j=-cj
 
 (3) Δj=a0j=cj
 
Номер 3
Если для табличного симплекс – метода оценки для всех небазисных переменных равны
Δj=a0j=-cj
, а соответствующее значение целевой функции
a00 = Σcixi = 0, i є I;
, то в качестве начального базиса
выбран базис:
Ответ:
 (1) из свободных переменных, для которых ci ≠ 0
 
 (2) из зависимых переменных, для которых ci ≠ 0
 
 (3) из свободных переменных, для которых ci = 0
 
Упражнение 7:
Номер 1
Если существует такой небазисный вектор, для которого оценка отрицательна, а все элементы этого столбца
неположительны, то целевая функция задачи в области допустимых решений:
Ответ:
 (1) ограничена 
 (2) частично ограничена 
 (3) неограничена 
Номер 2
Если существует такой небазисный вектор, для которого оценка отрицательна, и целевая функция
задачи в области допустимых решений неограниченна, то все элементы этого столбца:
Ответ:
 (1) положительны 
 (2) неположительны 
 (3) неотрицательны 
Номер 3
Если существует такой небазисный вектор, для которого все элементы столбца неположительны,
а целевая функция задачи в области допустимых решений неограниченна, то для такого вектора оценка:
Ответ:
 (1) отрицательна 
 (2) неотрицательна 
 (3) положительна 
Упражнение 8:
Номер 1
Если задача линейного программирования содержит n
переменных и m
ограничений, записанных в форме неравенств (n > m
), не считая ограничений неотрицательности
переменных xi ≥ 0
, то в оптимальное решение входит:
Ответ:
 (1) не более чем m
ненулевых компонент вектора x
 
 (2) более чем m
ненулевых компонент вектора x
 
 (3) не более чем n
ненулевых компонент вектора x
 
Номер 2
Если задача линейного программирования содержит n
переменных и m
ограничений, не считая ограничений неотрицательности переменных xi ≥ 0
, и в оптимальное
решение входит не более чем m
ненулевых компонент вектора x
, то выполняется условие:
Ответ:
 (1) n < m
 
 (2) n > m
 
 (3) n = m
 
Номер 3
Если в оптимальное решение задачи линейного программирования входит не более чем m
ненулевых компонент вектора x
, все переменные xi ≥ 0
и все ограничения
записаны в форме неравенств, то задача линейного программирования содержит:
Ответ:
 (1) n
переменных и m
ограничений (n > m
) 
 (2) n
ограничений и m
переменных (n > m
) 
 (3) равное количество переменных и ограничений (n = m
)