Задача линейного программирования. Симплекс метод

[Sverest]

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

$f(x)=cx \to \max$
$Ax=b$
$x \ge 0$

$c=(6, 1, -1, -2, 0)$
$b=(4, 1, 9)^T$
$\displaystyle A=\begin{pmatrix} 1 & 2 & 1 & 6 & 1\\ 3 & -1 & -1 & 1 &0 \\ 1& 3 &5 & 0 & 0 \end{pmatrix}$

функция:
$f(x)=6x_1+ x_2 -x_3 -2x_4$


$\left\{\begin{matrix} x_1+ 2x_2+ x_3+ 6x_4 + x_5=4\\ 3x_1 -x_2 -x_3 + x_4=1 \\ x_1 +3x_2+ 5x_3 =9 \end{matrix}\right.$

Какой ход действий?

[Shtorm]

Найти базисные переменные, подставить в целевую функцию, выразить целевую функцию через свободные переменные и заполнить Симплексную таблицу.

[Sverest]

Базисные это: $x_1, x_2, x_3, x_4,x_5$ ?

[Shtorm]

Нет. У Вас в системе ограничений - три независимых уравнения и 5 переменных. Следовательно, базисных переменных должно быть 3. А свободных переменных должно быть 2. Возмите матрицу $A$. Видно, что в последнем столбце два нуля и одна единица. Значит $x_5$ можно взять за базисную. В предпоследнем столбце - есть уже один нуль. Методом Гаусса получите и второй нуль в первой строке. Ну, и возмите к примеру, третий столбец с конца и методом Гаусса получите два нуля в первой и второй строке. А потом сделайте так (поделите или умножте) чтобы в этих базисных стобцах - ненулевые элементы были бы равны 1 или -1.
Вот и будут у Вас $x_3, x_4, x_5$ - базисными переменными.

[Sverest]

Shtorm в сообщении #594776 писал(а):

Следовательно, базисных переменных должно быть 3. А свободных переменных должно быть 2.

Как это определили?

Методом Гаусса — Жордана можно?
вот так получилось:

$\[\left|\hskip -\arraycolsep \begin{array}{*{5}{c}|c} 1&0&0&\frac{19}{24}&\frac{1}{12}&1\\ & & & & & \\ 0&1&0&3\frac{5}{6}&\frac{2}{3}&1\\ & & & & & \\ 0&0&1&-2\frac{11}{24}&-\frac{5}{12}&1 \end{array}\hskip -\arraycolsep \right|\]$

[Shtorm]

Честно говоря, лень проверять всю эту арифметику (ещё и при проверке могу сам ошибиться). Но если у Вас всё верно, то тогда базисными переменными будут $x_1, x_2, x_3$. Надеюсь Вы столбцы не переставляли?

[Sverest]

Shtorm в сообщении #594886 писал(а):

Честно говоря, лень проверять всю эту арифметику (ещё и при проверке могу сам ошибиться). Но если у Вас всё верно, то тогда базисными переменными будут $x_1, x_2, x_3$. Надеюсь Вы столбцы не переставляли?

Там должно быть все верно, я графическим методом его решал еще, просто пытаюсь разобраться с симплекс методом

[Shtorm]

Ну тогда перепишите преобразованную систему ограничений. Выражайте базисные через свободные и подставляйте в целевую функцию, чтоб она была выражена только через свободные.

[Sverest]

$x_1=- 0,79x_4 - 0,0833x_5+1 \\ x_2 =- 3,83x_4-0,67x_5+1 \\ x_3=2,46x_4+0,42x_5 +1$

$f(x)=-5 \frac{3}{8}x_4-1\frac{7}{12}x_5+6$

[Shtorm]

Теперь можно заполнять симплексную таблицу и не забывайте, что в последнюю строчку коэффициенты из целевой функции идут с противпоположным знаком.

[Sverest]

\begin{tabular}{c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5 \\ \hline x_1&-1&1&0&0&$\frac{19}{24}$&$\frac{1}{12}$& \\ \hline \\ x_2&-1&0&1&0&$3\frac{5}{6}$&$\frac{2}{3}$ \\ \hline \\ x_3&-1&0&0&1&-2$\frac{11}{24}$&$-\frac{5}{12}$ \end{tabular}

так правильно?
а целевую функцию куда?

[Shtorm]

Ну, во-первых, у Вас там в матрице свободные члены - единички, были со знаком плюс, а тут вы их записали со знаком минус. Надо знак плюс. И во-вторых, в симплексную таблицу необходимо добавить ещё одну строчку (последнюю), где будет отражена целевая функция и вот там уже знаки менять - только в коэффициентах, а не в свободных членах.

[Sverest]

\begin{tabular}{c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5 \\ \hline x_1&1&1&0&0&$\frac{19}{24}$&$\frac{1}{12}$& \\ \hline \\ x_2&1&0&1&0&$3\frac{5}{6}$&$\frac{2}{3}$ \\ \hline \\ x_3&1&0&0&1&-2$\frac{11}{24}$&$-\frac{5}{12}$\\ \hline \\ f &-6&0&0&0&5 $\frac{3}{8}$&$1\frac{7}{12}$\\ \end{tabular}
Вот так?

[Shtorm]

перед цифрой 6 должен быть "+". Знаки меняются только перед коэффициентами. Перед свободным членом не меняются. Ну и арифметику я не проверял.

[Sverest]

Так это надо было просто вот эту матрицу в таблицу записать?
Как теперь найти исходное опорное решение?

$\[\left|\hskip -\arraycolsep \begin{array}{*{5}{c}|c} 1&0&0&\frac{19}{24}&\frac{1}{12}&1\\ & & & & & \\ 0&1&0&3\frac{5}{6}&\frac{2}{3}&1\\ & & & & & \\ 0&0&1&-2\frac{11}{24}&-\frac{5}{12}&1 \end{array}\hskip -\arraycolsep \right|\]$

\begin{tabular}{c|c|c|c|c|c|c} \\ \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5 \\ \hline x_1&1&1&0&0&$\frac{19}{24}$&$\frac{1}{12}$& \\ \hline \\ x_2&1&0&1&0&$3\frac{5}{6}$&$\frac{2}{3}$ \\ \hline \\ x_3&1&0&0&1&-2$\frac{11}{24}$&$-\frac{5}{12}$\\ \hline \\ f &6&0&0&0&5 $\frac{3}{8}$&$1\frac{7}{12}$\\ \end{tabular}