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

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

Номер 1

Пусть ограничения задачи линейного программирования записаны в виде: 
A₁x₁+A₂x₂+...+A_nx_n+A_n+1x_n+1+...+A_n+mx_n+m=A₀, 
где А₁,...,А_m – множество линейно независимых векторов. Согласно симплекс – метода, 
базисное решение  определяется уравнением:

Ответ:

(1)

(2)

(3)

Номер 2

Уравнение  $A_1x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение  согласно симплекс – методу, 
если ограничения задачи линейного программирования имеют вид:

Ответ:

(1) A₁x₁-A₂x₂-...-A_nx_n-A_n+1x_n+1-...-A_n+mx_n+m=A₀;

(2) A₁x₁-A₂x₂+...+A_nx_n-A_n+1x_n+1+...+A_n+mx_n+m=A₀;

(3) A₁x₁+A₂x₂+...+A_nx_n+A_n+1x_n+1+...+A_n+mx_n+m=A₀.

Номер 3

Согласно симплекс – метода, верное базисное решение  
при ограничениях задачи линейного программирования 
A₁x₁+A₂x₂+...+A_nx_n+A_n+1x_n+1+...+A_n+mx_n+m=A₀ 
имеет вид:

Ответ:

(1)

A_1x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0

(2) A₁x₁-A₂x₂-...-A_nx_n-A_n+1x_n+1-...-A_n+mx_n+m=A₀;

(3) A₁x₁-A₂x₂+...+A_nx_n-A_n+1x_n+1+...+A_n+mx_n+m=A₀.

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

Номер 1

Пусть уравнение  $A_1x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение . Предположим, 
что это решение допустимо, т.е. . Если А_r 
не входит в базис, то:

Ответ:

(1) A₁x_1r+A₂x_2r+...+A_mx_mr ≥ A_r

(2) A₁x_1r+A₂x_2r+...+A_mx_mr = A_r

(3) A₁x_1r+A₂x_2r+...+A_mx_mr ≤ A_r

Номер 2

Пусть уравнение  $A_1x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение . При этом 
A_r не входит в базис, т.е. справедливо равенство: 
A₁x_1r+A₂x_2r+...+A_mx_mr = A_r. 
Тогда базисное решение имеет вид:

Ответ:

(1)

(2)

(3)

Номер 3

Пусть уравнение  $A_1x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение , которое является 
допустимым, т.е. . При этом справедливо равенство: 
A₁x_1r+A₂x_2r+...+A_mx_mr = A_r. 
Это значит, что:

Ответ:

(1) A_r не входит в базис

(2) A_r входит в базис

(3) A_r выражается через этот базис

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

Номер 1

Пусть уравнение  $A_1 x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение . 
Обозначим решение уравнения A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀ 
как . Тогда связь нового решения 
 со старым базисным решением 
 выражается следующими соотношениями:

Ответ:

(1)

x'_1 = x^*_1 + x_r x_{1r}; x'_2 = x^*_2 + x_r x_{2r}; \ldots ; x'_m = x^*_m + x_r x_{mr}, x_r

(2)

x'_1 = x^*_1 - x_r x_{1r}; x'_2 = x^*_2 - x_r x_{2r}; \ldots ; x'_m = x^*_m - x_r x_{mr}, x_r

(3)

x'_1 = x_r x_{1r} - x^*_1; x'_2 = x_r x_{2r} - x^*_2; \ldots ; x'_m = x_r x_{mr} - x^*_m, x_r

Номер 2

Уравнение  $A_1x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение . 
Новое решение  связано со старым базисным решением 
 соотношениями: 
 
Тогда уравнение имеет вид:

Ответ:

(1) A₁x₁-A₂x₂+...+A_mx_m-A_rx_r = А₀;

(2) A₁x₁-A₂x₂-...-A_mx_m-A_rx_r = А₀;

(3) A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀

Номер 3

Обозначим решение уравнения 
A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀
как . Связь нового решения  
со старым базисным решением  выражается соотношениями 
. 
Тогда уравнение, определяющее старое базисное решение , имеет вид:

Ответ:

(1)

A_1 x^*_1 + A_2 x^*_2 + \ldots + A_n x^*_n + A_{n+1} x^*_{n+1} + \ldots + A_{n+m} x^*_{n+m} = A_0

(2)

A_1 x^*_1 + A_2 x^*_2 - \ldots - A_n x^*_n + A_{n+1} x^*_{n+1} - \ldots - A_{n+m} x^*_{n+m} = A_0

(3)

A_1 x^*_1 - A_2 x^*_2 - \ldots - A_n x^*_n - A_{n+1} x^*_{n+1} - \ldots - A_{n+m} x^*_{n+m} = A_0

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

Номер 1

Пусть уравнение  $A_1 x^*_1 + A_2x^*_2 +\ldots + A_n x^*_n + A_{n+1} x^*_{n+1} +\ldots + 
A_{n+m}x^*_{n+m} = A_0$  определяет базисное решение .
Новое решение  базисное решение связано со старым базисным 
решением  соотношениями: 
. 
Данное решение будет допустимым, если:

Ответ:

(1)

(2)

(3)

Номер 2

Новое базисное решение уравнения 
A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀ 
имеет вид . 
При этом имеет место соотношение: . 
Тогда новое решение:

Ответ:

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

(2) является допустимым

(3) является базисным

Номер 3

Пусть уравнение 
A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀
имеет решение . 
Данное решение:

Ответ:

(1) будет допустимым для всех значений x_r

(2) не будет допустимым ни для каких значений x_r

(3) будет допустимым не для всех значений x_r

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

Номер 1

Пусть новое решение уравнения 
A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀ 
имеет вид , 
и при этом выполняется соотношение , т.е. данное решение 
является допустимым. Чтобы данное решение являлось базисным, необходимо:

Ответ:

(1) вывести переменную x_i из базисного решения, а соответствующий вектор – из базиса

(2) ввести дополнительную переменную x_i в базисное решение, а соответствующий вектор – в базис

(3) вывести переменную x_i из базисного решения, и ввести дополнительный вектор в базис

Номер 2

Пусть новое решение  уравнения 
A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀ 
имеет вид , 
и при этом является допустимым. Выведем одну переменную x_i из базисного решения, а 
соответствующий вектор из базиса. Тогда новое базисное решение имеет вид:

Ответ:

(1)

(2)

(3)

Номер 3

Решение  уравнения 
A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀ 
имеет вид , 
и при этом выполняется соотношение . 
Выведем одну переменную x_i из базисного решения, а соответствующий вектор из базиса. 
Новое решение имеет вид . 
Данное решение:

Ответ:

(1) не является базисным

(2) является базисным

(3) является допустимым

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

Номер 1

Если для табличного симплекс – метода в качестве начального базиса выбирают базис из свободных 
переменных, для которых ci = 0, и оценки для всех небазисных переменных равны 
Δ_j=a_0j=-c_j, то соответствующее значение целевой функции 
определяется соотношением:

Ответ:

(1) a₀₀ = Σc_ix_i > 0, i є I;

(2) a₀₀ = Σc_ix_i = 0, i є I;

(3) a₀₀ = Σc_ix_i < 0, i є I;

Номер 2

Для табличного симплекс – метода в качестве начального базиса выбран базис из свободных переменных, 
для которых c_i = 0. Соответствующее значение целевой функции определяется соотношением 
a₀₀ = Σc_ix_i = 0, i є I. Тогда оценки для всех небазисных 
переменных равны:

Ответ:

(1) Δ_j=a_0j=-c_j

(2) Δ_j=-a_0j=-c_j

(3) Δ_j=a_0j=c_j

Номер 3

Если для табличного симплекс – метода оценки для всех небазисных переменных равны 
Δ_j=a_0j=-c_j, а соответствующее значение целевой функции 
a₀₀ = Σc_ix_i = 0, i є I;, то в качестве начального базиса 
выбран базис:

Ответ:

(1) из свободных переменных, для которых c_i ≠ 0

(2) из зависимых переменных, для которых c_i ≠ 0

(3) из свободных переменных, для которых c_i = 0

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

Номер 1

Если существует такой небазисный вектор, для которого оценка отрицательна, а все элементы этого столбца 
неположительны, то целевая функция задачи в области допустимых решений:

Ответ:

(1) ограничена

(2) частично ограничена

(3) неограничена

Номер 2

Если существует такой небазисный вектор, для которого оценка отрицательна, и целевая функция 
задачи в области допустимых решений неограниченна, то все элементы этого столбца:

Ответ:

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

(2) неположительны

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

Номер 3

Если существует такой небазисный вектор, для которого все элементы столбца неположительны, 
а целевая функция задачи в области допустимых решений неограниченна, то для такого вектора оценка:

Ответ:

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

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

(3) положительна

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

Номер 1

Если задача линейного программирования содержит n переменных и m 
ограничений, записанных в форме неравенств (n > m), не считая ограничений неотрицательности 
переменных x_i ≥ 0, то в оптимальное решение входит:

Ответ:

(1) не более чем m ненулевых компонент вектора x

(2) более чем m ненулевых компонент вектора x

(3) не более чем n ненулевых компонент вектора x

Номер 2

Если задача линейного программирования содержит n переменных и m 
ограничений, не считая ограничений неотрицательности переменных x_i ≥ 0, и в оптимальное 
решение входит не более чем m ненулевых компонент вектора x, то выполняется условие:

Ответ:

(1) n < m

(2) n > m

(3) n = m

Номер 3

Если в оптимальное решение задачи линейного программирования входит не более чем m 
ненулевых компонент вектора x, все переменные x_i ≥ 0 и все ограничения 
записаны в форме неравенств, то задача линейного программирования содержит:

Ответ:

(1) n переменных и m ограничений (n > m)

(2) n ограничений и m переменных (n > m)

(3) равное количество переменных и ограничений (n = m)

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