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

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

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

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

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

$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₁-A₂x₂-...-A_nx_n-A_n+1x_n+1-...-A_n+mx_n+m=A₀;

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

Пусть ограничения задачи линейного программирования записаны в виде: 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_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$ определяет базисное решение $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$ выражается соотношениями $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_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$ определяет базисное решение $x^*_1, x^*_2, \ldots, x^*_m$ . При этом A_r не входит в базис, т.е. справедливо равенство: A₁x_1r+A₂x_2r+...+A_mx_mr = A_r. Тогда базисное решение имеет вид:

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

Уравнение $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$ определяет базисное решение $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$ Тогда уравнение имеет вид:

Пусть уравнение $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$ определяет базисное решение $x^*_1, x^*_2, \ldots, x^*_m$ . Предположим, что это решение допустимо, т.е. $x^*_1 \ge 0, x^*_2 \ge 0, \ldots, x^*_m \ge 0$ . Если А_r не входит в базис, то:

Пусть уравнение $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$ определяет базисное решение $x^*_1, x^*_2, \ldots, x^*_m$ , которое является допустимым, т.е. $x^*_1 \ge 0, x^*_2 \ge 0, \ldots, x^*_m \ge 0$ . При этом справедливо равенство: A₁x_1r+A₂x_2r+...+A_mx_mr = A_r. Это значит, что:

Пусть двойственная задача линейного программирования имеет вид: минимизировать $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. Тогда задача, записанная в канонической форме, имеет вид:

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

Согласно симплекс – метода, верное базисное решение при ограничениях задачи линейного программирования A1x1+A2x2+...+Anxn+An+1xn+1+...+An+mxn+m=A0 имеет вид: