Введение в математическое программирование

Упражнение 1:

Номер 1

Если x₀ и y₀ – допустимые решения прямой 
и двойственной задач, т.е. Ax₀≤b и A^Ty₀≥c, то:

Ответ:

(1) c^Tx₀≥b^Ty₀

(2) c^Tx₀<b^Ty₀

(3) c^Tx₀≤b^Ty₀

Номер 2

Если значения целевой функции прямой задачи никогда не превышают значений целевой функции 
двойственной задачи, т.е. c^Tx₀≤b^Ty₀, то допустимые 
решения прямой и двойственной задач имеют вид:

Ответ:

(1) Ax₀≤b и A^Ty₀≥c

(2) Ax₀≤b и A^Ty₀≤c

Номер 3

Выберите верное утверждение: 
если Ax₀≤b и A^Ty₀≥c, то:

Ответ:

(1) c^Tx₀<b^Ty₀

(2) c^Tx₀≥b^Ty₀

(3) c^Tx₀≤b^Ty₀

Упражнение 2:

Номер 1

Если x₀ и y₀ – допустимые решения прямой и 
двойственной задач, и кроме того, c^Tx₀=b^Ty₀, то:

Ответ:

(1) x₀ и y₀ – оптимальные решения пары прямых задач

(2) x₀ и y₀ – оптимальные решения пары двойственных задач

(3) x₀ и y₀ – оптимальные решения прямой и двойственной задач

Номер 2

Если x₀ и y₀ – оптимальные решения пары двойственных 
задач, и кроме того, c^Tx₀=b^Ty₀, то:

Ответ:

(1) x₀ и y₀ – допустимые решения прямой и двойственной задач

(2) x₀ и y₀ – допустимые решения пары прямых задач

(3) x₀ и y₀ – допустимые решения пары двойственных задач

Номер 3

Если x₀ и y₀ допустимые решения прямой и 
двойственной задач и при этом x₀ и y₀ – оптимальные решения 
пары двойственных задач, то справедливо соотношение:

Ответ:

(1) c^Tx₀>b^Ty₀

(2) c^Tx₀<b^Ty₀

(3) c^Tx₀=b^Ty₀

Упражнение 3:

Номер 1

Пусть дана прямая задача: максимизировать 
Σc_jx_j, j=1,...,n при ограничениях 
Σa_ijx_j≤b, i=1,...,m, x_j≥0, j=1,...,n. 
Если в оптимальном решении данной задачи i–е ограничение выполняется как неравенство, 
то оптимальное значение соответствующей двойственной переменной:

Ответ:

(1) положительно

(2) неотрицательно

(3) равно нулю

Номер 2

Пусть дана прямая задача: максимизировать 
Σc_jx_j, j=1,...,n при ограничениях 
Σa_ijx_j≤b, i=1,...,m, x_j≥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

Допустимый вектор x₀ оптимальный тогда и только тогда, 
когда в двойственной задаче имеется такое допустимое решение y₀, что:

Ответ:

(1) c^Tx₀>b^Ty₀

(2) c^Tx₀=b^Ty₀

(3) c^Tx₀=-b^Ty₀

Номер 2

Если в двойственной задаче имеется такое допустимое решение y₀, что
c^Tx₀=b^Ty₀, то допустимый вектор x₀:

Ответ:

(1) является оптимальным

(2) не является оптимальным

(3) является двойственным

Номер 3

Если в двойственной задаче допустимый вектор x₀ является оптимальным и 
при этом выполняется условие c^Tx₀=b^Ty₀, то:

Ответ:

(1) y₀ является допустимым решением

(2) y₀ является оптимальным решением

(3) y₀ является оптимальным допустимым решением

Упражнение 7:

Номер 1

Если прямая задача линейного программирования имеет вид: максимизировать 
Σc_jx_j, j=1,...,n при условиях 
Σa_ijx_j≤b_i, i=1,...,m₁<m; Σa_ijx_j=b_i, i=m₁+1,m₁+2,...,m; x_j≥0; j=1,...,n₁<n. 
Тогда двойственная ей задача имеет вид:

Ответ:

(1) минимизировать Σb_iy_i, i=1,...,m при условиях Σа_ijy_i≥c_j, j=1,...,n₁≤n; Σа_ijy_i=c_j, j=n₁+1, n₁+2,...,n

(2) максимизировать Σb_iy_i, i=1,...,m при условиях Σа_ijy_i≥c_j, j=1,...,n₁≤n; Σа_ijy_i=c_j, j=n₁+1, n₁+2,...,n

(3) минимизировать Σb_iy_i, i=1,...,m при условиях Σа_ijy_i≥c_j, j=1,...,n₁≤n; Σа_ijy_i=0.

Номер 2

Двойственная задача линейного программирования имеет вид: 
минимизировать Σb_iy_i, i=1,...,m при условиях 
Σа_ijy_i≥c_j, j=1,...,n₁≤n; Σа_ijy_i=c_j, j=n₁+1, n₁+2,...,n. 
Тогда прямая задача имеет вид:

Ответ:

(1) минимизировать Σc_jx_j, j=1,...,n при условиях Σa_ijx_j≤b_i, i=1,...,m₁<m; Σa_ijx_j=b_i, i=m₁+1,m₁+2,...,m; x_j≥0; j=1,...,n₁<n

(2) максимизировать Σc_jx_j, j=1,...,n при условиях Σa_ijx_j≤b_i, i=1,...,m₁<m; Σa_ijx_j=b_i, i=m₁+1,m₁+2,...,m; x_j≥0; j=1,...,n₁<n

(3) максимизировать Σc_jx_j, j=1,...,n при условиях Σa_ijx_j≤b_i, i=1,...,m₁<m; Σa_ijx_j=0.

Номер 3

Если прямая задача линейного программирования имеет вид: максимизировать 
Σc_jx_j, j=1,...,n при условиях 
Σa_ijx_j≤b_i, i=1,...,m₁<m; Σa_ijx_j=b_i, i=m₁+1,m₁+2,...,m; x_j≥0; j=1,...,n₁<n. 
Тогда двойственная ей задача имеет вид: минимизировать Σb_iy_i. 
Условия ограничения двойственной задачи имеют вид:

Ответ:

(1) Σа_ijy_i≥c_j, j=1,...,n₁≤n; Σа_ijy_i=c_j, j=n₁+1, n₁+2,...,n

(2) Σа_ijy_i≤c_j, j=1,...,n₁≤n; Σа_ijy_i=c_j, j=n₁+1, n₁+2,...,n

(3) Σа_ijy_i≥c_j, j=1,...,n₁≤n; Σа_ijy_i=0.

Упражнение 8:

Номер 1

Если x и y – допустимые решения прямой и двойственной задач 
и если при этом 
Σc_jx_j = Σb_iy_i, j=1,...,n; i=1,...,m, то:

Ответ:

(1) x и y - оптимальные решения прямой задачи

(2) x и y - оптимальные решения двойственной задачи

(3) x и y - оптимальные решения и прямой, и двойственной задач

Номер 2

Если x и y - оптимальные решения прямой и двойственной задач, 
и при этом выполняется условие 
Σc_jx_j = Σb_iy_i, j=1,...,n; i=1,...,m, 
то x и y являются:

Ответ:

(1) допустимыми решениями этих задач

(2) допустимыми решениями прямой задачи

(3) допустимыми решениями двойственной задачи

Номер 3

Если x и y – допустимые решения прямой и двойственной задач и 
при этом они являются оптимальными решениями этих задач, то справедливо соотношение:

Ответ:

(1) Σc_jx_j > Σb_iy_i, j=1,...,n; i=1,...,m

(2) Σc_jx_j = Σb_iy_i, j=1,...,n; i=1,...,m

(3) Σc_jx_j = -Σb_iy_i, j=1,...,n; i=1,...,m

Введение в математическое программирование - тест 5