Главная / Алгоритмы и дискретные структуры /
Введение в математическое программирование / Тест 5
Введение в математическое программирование - тест 5
Упражнение 1:
Номер 1
Если x0
и y0
– допустимые решения прямой
и двойственной задач, т.е. Ax0≤b
и ATy0≥c
, то:
Ответ:
 (1) cTx0≥bTy0
 
 (2) cTx0<bTy0
 
 (3) cTx0≤bTy0
 
Номер 2
Если значения целевой функции прямой задачи никогда не превышают значений целевой функции
двойственной задачи, т.е. cTx0≤bTy0
, то допустимые
решения прямой и двойственной задач имеют вид:
Ответ:
 (1) Ax0≤b
и ATy0≥c
 
 (2) Ax0≤b
и ATy0≤c
 
Номер 3
Выберите верное утверждение:
если Ax0≤b
и ATy0≥c
, то:
Ответ:
 (1) cTx0<bTy0
 
 (2) cTx0≥bTy0
 
 (3) cTx0≤bTy0
 
Упражнение 2:
Номер 1
Если x0
и y0
– допустимые решения прямой и
двойственной задач, и кроме того, cTx0=bTy0
, то:
Ответ:
 (1) x0
и y0
– оптимальные решения пары прямых задач 
 (2) x0
и y0
– оптимальные решения пары двойственных задач 
 (3) x0
и y0
– оптимальные решения прямой и двойственной задач 
Номер 2
Если x0
и y0
– оптимальные решения пары двойственных
задач, и кроме того, cTx0=bTy0
, то:
Ответ:
 (1) x0
и y0
– допустимые решения прямой и двойственной задач 
 (2) x0
и y0
– допустимые решения пары прямых задач 
 (3) x0
и y0
– допустимые решения пары двойственных задач 
Номер 3
Если x0
и y0
допустимые решения прямой и
двойственной задач и при этом x0
и y0
– оптимальные решения
пары двойственных задач, то справедливо соотношение:
Ответ:
 (1) cTx0>bTy0
 
 (2) cTx0<bTy0
 
 (3) cTx0=bTy0
 
Упражнение 3:
Номер 1
Пусть дана прямая задача: максимизировать
Σcjxj, j=1,...,n
при ограничениях
Σaijxj≤b, i=1,...,m, xj≥0, j=1,...,n
.
Если в оптимальном решении данной задачи i
–е ограничение выполняется как неравенство,
то оптимальное значение соответствующей двойственной переменной:
Ответ:
 (1) положительно 
 (2) неотрицательно 
 (3) равно нулю 
Номер 2
Пусть дана прямая задача: максимизировать
Σcjxj, j=1,...,n
при ограничениях
Σaijxj≤b, i=1,...,m, xj≥0, j=1,...,n
.
Если оптимальное значение соответствующей двойственной переменной равно нулю, то в оптимальном решении данной
задачи i
–е ограничение выполняется:
Ответ:
 (1) как нестрогое неравенство 
 (2) как равенство 
 (3) как строгое неравенство 
Номер 3
Если в оптимальном решении некоторой задачи i
–е ограничение выполняется как
строгое неравенство и оптимальное значение соответствующей двойственной переменной равно нулю, то данная
задача является:
Ответ:
 (1) прямой 
 (2) двойственной 
 (3) обратной 
Упражнение 4:
Номер 1
Если в оптимальном решении двойственной задачи ограничение j
выполняется как строгое неравенство, то оптимальное решение соответствующей переменной прямой задачи:
Ответ:
 (1) равно нулю 
 (2) неотрицательно 
 (3) положительно 
Номер 2
Если оптимальное значение переменной прямой задачи равно нулю, то в оптимальном решении
двойственной задачи ограничение j
выполняется как:
Ответ:
 (1) строгое равенство 
 (2) строгое неравенство 
 (3) нестрогое неравенство 
Номер 3
Если в оптимальном решении некоторой задачи ограничение j
выполняется
как строгое неравенство и при этом оптимальное значение переменной прямой задачи равно нулю, то
данная задача является:
Ответ:
 (1) прямой 
 (2) обратной 
 (3) двойственной 
Упражнение 5:
Номер 1
Прямая и двойственная задачи имеют оптимальные решения тогда и только тогда, когда:
Ответ:
 (1) они обе имеют допустимые решения 
 (2) прямая задача имеет допустимое решение 
 (3) двойственная задача имеет допустимое решение 
Номер 2
Если прямая и двойственная задачи имеют допустимые решения, то:
Ответ:
 (1) оптимальное решение имеет двойственная задача 
 (2) оптимальное решение имеет прямая задача 
 (3) оптимальные решения имеют и прямая, и двойственная задачи 
Номер 3
Если прямая и двойственная задачи имеют допустимые решения, и при этом
двойственная задача имеет оптимальное решение, то:
Ответ:
 (1) прямая задача также имеет оптимальное решение 
 (2) прямая задача не имеет оптимального решения 
 (3) прямая задача в этом случае не имеет решения 
Упражнение 6:
Номер 1
Допустимый вектор x0
оптимальный тогда и только тогда,
когда в двойственной задаче имеется такое допустимое решение y0
, что:
Ответ:
 (1) cTx0>bTy0
 
 (2) cTx0=bTy0
 
 (3) cTx0=-bTy0
 
Номер 2
Если в двойственной задаче имеется такое допустимое решение y0
, что
cTx0=bTy0
, то допустимый вектор x0
:
Ответ:
 (1) является оптимальным 
 (2) не является оптимальным 
 (3) является двойственным 
Номер 3
Если в двойственной задаче допустимый вектор x0
является оптимальным и
при этом выполняется условие cTx0=bTy0
, то:
Ответ:
 (1) y0
является допустимым решением 
 (2) y0
является оптимальным решением 
 (3) y0
является оптимальным допустимым решением 
Упражнение 7:
Номер 1
Если прямая задача линейного программирования имеет вид: максимизировать
Σcjxj, j=1,...,n
при условиях
Σaijxj≤bi, i=1,...,m1<m; Σaijxj=bi, i=m1+1,m1+2,...,m; xj≥0; j=1,...,n1<n
.
Тогда двойственная ей задача имеет вид:
Ответ:
 (1)
минимизировать Σbiyi, i=1,...,m
при условиях
Σаijyi≥cj, j=1,...,n1≤n; Σаijyi=cj, j=n1+1, n1+2,...,n
 
 (2)
максимизировать Σbiyi, i=1,...,m
при условиях
Σаijyi≥cj, j=1,...,n1≤n; Σаijyi=cj, j=n1+1, n1+2,...,n
 
 (3)
минимизировать Σbiyi, i=1,...,m
при условиях
Σаijyi≥cj, j=1,...,n1≤n; Σаijyi=0
.
 
Номер 2
Двойственная задача линейного программирования имеет вид:
минимизировать Σbiyi, i=1,...,m
при условиях
Σаijyi≥cj, j=1,...,n1≤n; Σаijyi=cj, j=n1+1, n1+2,...,n
.
Тогда прямая задача имеет вид:
Ответ:
 (1)
минимизировать Σcjxj, j=1,...,n
при условиях
Σaijxj≤bi, i=1,...,m1<m; Σaijxj=bi, i=m1+1,m1+2,...,m; xj≥0; j=1,...,n1<n
 
 (2)
максимизировать Σcjxj, j=1,...,n
при условиях
Σaijxj≤bi, i=1,...,m1<m; Σaijxj=bi, i=m1+1,m1+2,...,m; xj≥0; j=1,...,n1<n
 
 (3)
максимизировать Σcjxj, j=1,...,n
при условиях
Σaijxj≤bi, i=1,...,m1<m; Σaijxj=0
.
 
Номер 3
Если прямая задача линейного программирования имеет вид: максимизировать
Σcjxj, j=1,...,n
при условиях
Σaijxj≤bi, i=1,...,m1<m; Σaijxj=bi, i=m1+1,m1+2,...,m; xj≥0; j=1,...,n1<n
.
Тогда двойственная ей задача имеет вид: минимизировать Σbiyi
.
Условия ограничения двойственной задачи имеют вид:
Ответ:
 (1)
Σаijyi≥cj, j=1,...,n1≤n; Σаijyi=cj, j=n1+1, n1+2,...,n
 
 (2)
Σаijyi≤cj, j=1,...,n1≤n; Σаijyi=cj, j=n1+1, n1+2,...,n
 
 (3)
Σаijyi≥cj, j=1,...,n1≤n; Σаijyi=0
.
 
Упражнение 8:
Номер 1
Если x
и y
– допустимые решения прямой и двойственной задач
и если при этом
Σcjxj = Σbiyi, j=1,...,n; i=1,...,m
, то:
Ответ:
 (1) x
и y
- оптимальные решения прямой задачи 
 (2) x
и y
- оптимальные решения двойственной задачи 
 (3) x
и y
- оптимальные решения и прямой, и двойственной задач 
Номер 2
Если x
и y
- оптимальные решения прямой и двойственной задач,
и при этом выполняется условие
Σcjxj = Σbiyi, j=1,...,n; i=1,...,m
,
то x
и y
являются:
Ответ:
 (1) допустимыми решениями этих задач 
 (2) допустимыми решениями прямой задачи 
 (3) допустимыми решениями двойственной задачи 
Номер 3
Если x
и y
– допустимые решения прямой и двойственной задач и
при этом они являются оптимальными решениями этих задач, то справедливо соотношение:
Ответ:
 (1) Σcjxj > Σbiyi, j=1,...,n; i=1,...,m
 
 (2) Σcjxj = Σbiyi, j=1,...,n; i=1,...,m
 
 (3) Σcjxj = -Σbiyi, j=1,...,n; i=1,...,m