База ответов ИНТУИТ

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

<<- Назад к вопросам

Задача линейного программирования в канонической форме имеет вид: максимизировать L(x) = Σcjxj, j=1,...,n при условиях ΣAjxj = b, j=1,...,n, xj ≥ 0. Двойственная задача к ней задача записана так: минимизировать L'_{\partial e}(y) = \sum b_{\mu} y_{\mu}, \mu = 1,\ldots,m при условиях A^T_j y \ge c_j, \sum a_{\mu} y_{mu} \ge c_j, \mu = 1,\ldots,m,  j=1,\ldots,n Тогда выполняется условие:

(Отметьте один правильный вариант ответа.)

Варианты ответа
n ≤ m и ранг матрицы A равен n
n ≥ m и ранг матрицы A равен n(Верный ответ)
n = m и ранг матрицы A равен n
Похожие вопросы
Пусть двойственная задача линейного программирования имеет вид: минимизировать L'_{\partial e}(y) = \sum b_{\mu} y_{\mu}, \mu = 1,\ldots,m при условиях A^T_j y \ge c_j, \sum a_{\mu} y_{mu} \ge c_j, \mu = 1,\ldots,m,  j=1,\ldots,n и при этом n ≥ m и ранг матрицы A равен m. Тогда задача, записанная в канонической форме, имеет вид:
Если задача сформулирована в виде: максимизировать \sum с_i x_i, \; i=1,\ldots,n при условиях
\begin{aligned}& a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \le b_1 \\& a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \le b_2 \\& \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\& a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \le b_n, \; x_1 \ge 0, x_2 \ge 0, \ldots, x_n \ge 0 .\end{aligned}
то это задача:
Пусть задача сформулирована в виде:максимизировать \sum c_i x_i, \; i=1,\ldots,n при условиях
\begin{aligned}& a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1 \\& a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n = b_2 \\& \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\& a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n = b_n, \; x_1 \ge 0, x_2 \ge 0, \ldots, x_n \ge 0 .\end{aligned}
Данная форма записи является:
Пусть задача линейного программирования задана в канонической форме: максимизировать L(x) = Σcjxj, j=1,...,n при условиях ΣAjxj = b, j=1,...,n, xj ≥ 0. Предположим, что n ≥ m и ранг матрицы A равен m. Тогда двойственная задача имеет вид:
Обозначим решение уравнения A1x1+A2x2+...+Amxm+Arxr = А0как \{ x'1, x'2, \ldots, x'_m, x'_r \}. Связь нового решения x'_1, x'_2, \ldots, x'_m, x'_r со старым базисным решением x^*_1, x^*_2, \ldots, x^*_m выражается соотношениями 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. Тогда уравнение, определяющее старое базисное решение x^*_1, x^*_2, \ldots, x^*_m, имеет вид:
Пусть уравнение 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 определяет базисное решение x^*_1, x^*_2, \ldots, x^*_m. Обозначим решение уравнения A1x1+A2x2+...+Amxm+Arxr = А0 как \{ x'1, x'2, \ldots, x'_m, x'_r \}. Тогда связь нового решения x'_1, x'_2, \ldots, x'_m, x'_r со старым базисным решением x^*_1, x^*_2, \ldots, x^*_m выражается следующими соотношениями:
Если прямая задача линейного программирования имеет вид: максимизировать Σ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. Условия ограничения двойственной задачи имеют вид:
Пусть задача нелинейного программирования задана следующим образом: минимизировать f(x) при условиях gi(x) ≤ 0, i = 1,...,m. Известно, что существует некоторый вектор Δ* ≥ 0, такой, что L(x*,Δ) ≤ L(x**) ≤ L(x,Δ*) и \Delta^{*T}g(x^*) = \sum \lambda^*_i g_i(x^*) = 0. Функции gi(x) удовлетворяют условию регулярности Слейтера. Тогда:
Задача линейного программирования сформулирована в каноническом виде:максимизировать \sum c_i x_i, \; i=1,\ldots,n. Тогда условия ограничения имеют вид:
Рассмотрим задачу нелинейного программирования: минимизировать f(x) при g_i(x) = - \eta^T_i x + b_i \le 0,  i = 1,\ldots,m. Для входящего вектора справедливы следующие условия: \Delta g^T_i(x – x^*) \le 0 или \Delta f(x^*)(x – x^*) \ge 0 для всех x є S.Тогда скаляры i}, для которых справедливо соотношение Δf(x*)=Σλiηi(x) = -ΣλiΔgi(x*), i є I, являются: