Итерации симплекс-метода

[HenryDukart]

Здравствуйте. Я пытаюсь решить задачу с помощью итераций симплекс метода. Ввел дополнительные переменные, чтобы привести к каноническому виду. Нашел на них ограничения. Нашел базисный план, что исходные переменные являются небазисными, а дополнительные - базисные. Начальный базисный план не вырожденный. Но после второй итерации он стал вырожденным. Что делать в этом случае? Нам говорили, что можно не искать нижние ограничения на дополнительные переменные, а взять их равными 0. Но, если в моём случае эти ограничения взять нулевыми, то начальный план не подобрать.

[iifat]

Вы б не постеснялись, да и выложили условие и ваше решение. Вот прям сюда. Ей-богу, проще было б сообразить.

[HenryDukart]

iifat, сейчас напишу.

-- 15.09.2015, 17:07 --

Задача на нахождение максимума.
$\phi=12x_1+2x_2+5x_4+3x_5$
$\left\{\begin{matrix}4x_1+2x_2+2x_5\leqslant 1 \\ x_3+3x_5 \leqslant 3 \\ 2x_2+x_4 \leqslant 3 \\ -1 \leqslant x_1 \leqslant 4 \\ 0 \leqslant x_2 \leqslant 4 \\ -4 \leqslant x_3 \leqslant 1 \\ 1 \leqslant x_4 \leqslant 5 \\ 1 \leqslant x_5 \leqslant 6 \end{matrix}\right.$

Привожу к каноническому виду и нахожу ограничения на дополнительные переменные:
$\left\{\begin{matrix}4x_1+2x_2+2x_5 + x_6= 1 \\ x_3+3x_5 +x_7 = 3 \\ 2x_2+x_4 +x_8 = 3 \\ -26 \leqslant x_6 \leqslant 8 \\ -16 \leqslant x_7 \leqslant 4 \\ -10 \leqslant x_8 \leqslant 2 \end{matrix}\right.$

Выбираю исходные переменные на границе так, чтобы дополнительные переменные не попали на границу:
$\left\{\begin{matrix}x_1=-1 \\ x_2=0 \\ x_3=-4 \\ x_4=5 \\ x_5=6 \end{matrix}\right.$

Тогда, подставляю эти значения в уравнения и нахожу первоначальный базисный план:
$x=(-1, 0, -4, 5, 6, -2, -11, -2)'$.

Базисная матрица является единичной. $ c_b=(0, 0, 0)' $.
$A'_bu=c_b, Eu=c_b, u=(0, 0, 0)'$

$\Delta_j=c_j-u'a_j, j \in J_{n}$

$\Delta_1=12, \Delta_2=2, \Delta_3=0, \Delta_4=5, \Delta_5=3$

$\Delta_1=12>0, x_1=-1=d_{*1}$ - первая переменная, на которой нарушается критерий оптимальности невырожденного базисного плана. Значит,
$j_0=1$

$l_1=sign \Delta_1=1, l_2=l_3=l_4=l_5=0$

$A_bl_b=-a_{j_0}l_{j_0}: l_6=-4, l_7=0, l_8=0$

$\Theta_{j_0}=d^*_{j_0}-d_{*j_0}=4-(-1)=5$

$\Theta_j=\left\{\begin{matrix}\frac{d^*_j-x_j}{l_j}, l_j>0 \\ \frac{d_{*j}-x_j}{l_j}, l_j<0 \\ \infty, l_j=0 \end{matrix}\right., j \in J_b$

$\Theta_6=\frac{13}{2}, \Theta_7=\infty, \Theta_8=\infty$

$\Theta=min(\Theta_{j_0}, \Theta_j)=5, j_*=1$

Пересчитываем базисный план:

$\overline{x}=x+\Theta l=(-1, 0, -4, 5, 6, -2, -11, -2)'+5(1, 0, 0, 0, 0, -4, 0, 0)'=(4, 0, -4, 5, 6, -22, -11, -2)'$

Новый базис находится так: $J_b=(J_b\cup \{j_0\})\setminus\{j_*\}$

В этом случае базис не изменился.

На второй итерации критерий нарушился на $j_0=2$. При этом $\Theta_2=\Theta_8=4$. Если в качестве $j_*$ взять 2, то базис не изменится, а $x=(4, 4, -4, 5, 6, -22, -11, 10)'.$ Это вырожденный базис.

Сейчас попробую из базиса исключить 8 и добавить 2.

[HenryDukart]

А, будет же тоже самое, если в базис включить вторую переменную. Вот до чего пришел и не знаю, что делать.

[HenryDukart]

Для этого плана выполняются достаточные условия оптимальности, но это решение не удовлетворяет первоначальной системе неравенств.

[iifat]

iifat в сообщении #1053602 писал(а):

проще было б сообразить

Ну, я не имел в виду себя, вообще-то
У симплекс-метода, насколько помню, куча модификаций, связанных одной идеей. Те варианты, что читал я, не предусматривают ограничений типа $-1\leqslant x_1\leqslant4$. Не говорю, что это ошибка, но я б начал с ввода новой переменной $\tilde x_1=x_1+1$ и нового ограничения $\tilde x_1 + x_9=4$. По крайней мере, вот эта проблема решится

HenryDukart в сообщении #1053685 писал(а):

решение не удовлетворяет первоначальной системе неравенств

[iifat]

iifat в сообщении #1053719 писал(а):

$\tilde x_1 + x_9=4$

Соврал. =5, разумеется.