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

Сопряженным базисом называется такая система из m линейно - независимых векторов матрицы ограничений прямой задачи $\{ A_i \}_{i \in I \delta}$ , для которой базисное решение y соответствующей системы линейных уравнений вида $A^T_i y = c_i, \quad i \in I \delta$ , удовлетворяет ограничениям:

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

Варианты ответа

$A^T_j y \le c_j, \sum a_{\mu}y_{\mu} \le c_j, \; \mu = 1,\ldots,m, \; j = 1,\ldots,n$

$A^T_j y = c_j, \sum a_{\mu}y_{\mu} > c_j, \; \mu = 1,\ldots,m, \; j = 1,\ldots,n$

$A^T_j y \ge c_j, \sum a_{\mu}y_{\mu} \ge c_j, \; \mu = 1,\ldots,m, \; j = 1,\ldots,n$ (Верный ответ)

Похожие вопросы

Пусть для некоторой системы, состоящей из m линейно - независимых векторов матрицы ограничений прямой задачи $\{ A_i \}_{i \in I \delta}$ , базисное решение y соответствующей системы линейных уравнений вида $A^T_i y = c_i, \quad i \in I \delta$ , удовлетворяет ограничениям $A^T_j y \ge c_j, \sum a_{\mu}y_{\mu} \ge c_j, \; \mu = 1,\ldots,m, \; j = 1,\ldots,n$ Тогда данная система носит название:

Пусть некоторое базисное решение y системы линейных уравнений вида $A^T_i y = c_i, \quad i \in I \delta$ , удовлетворяет ограничениям $A^T_j y \ge c_j, \sum a_{\mu}y_{\mu} \ge c_j, \; \mu = 1,\ldots,m, \; j = 1,\ldots,n$ Тогда вектора матрицы ограничений прямой задачи $\{ A_i \}_{i \in I \delta}$ , составляющие сопряженный базис, являются:

Пусть известен некоторый сопряженный базис $\{ A_i \}_{i \in I \delta}$ , которому соответствует псевдоплан x, базисные компоненты которого x_i = x_i0≥0 для всех i є Iδ. При этом $A_j = \sum A_i x_{ij}; A_0 = \sum A_i x_i, i \in I \delta$ Тогда:

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

Пусть известен некоторый сопряженный базис $\{ A_i \}_{i \in I \delta}$ , которому соответствует псевдоплан x. При этом псевдоплан x является оптимальным решением и $A_j = \sum A_i x_{ij}; A_0 = \sum A_i x_i, i \in I \delta$ Тогда для базисных компонентов справедливо условие:

Рассмотрим задачу нелинейного программирования: минимизировать 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} ≥ 0, для которых справедливо соотношение:

Рассмотрим задачу нелинейного программирования: минимизировать 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Δg_i(x^*), i є I, являются:

Обозначим решение уравнения A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀как $\{ 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$ . Обозначим решение уравнения A₁x₁+A₂x₂+...+A_mx_m+A_rx_r = А₀ как $\{ 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$ выражается следующими соотношениями:

Пусть уравнение $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$ .Новое решение $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$ . Данное решение будет допустимым, если: