Правило определения вектора вводимого в базис.
Среди всех оценок индексной строки выбирается наименьшая отрицательная оценка, которая соответствует небазисному вектору, вводимый в базис.
Правило определения базисного вектора, вместо которого вводится небазисный (заменяемый).
Для этого определяется величина Q, равная минимуму из отношения компонент вектора В к соответствующим положительным компонентам вектора, вводимого в базис.
Q=min{
;
;
}=
Замечание: если значение Q одинаково для нескольких отношений, то в принципе выбирается любое, но для более оптимального процесса выбирается компотента вектора В. Следовательно, в базисе должен быть заменен вектор A5. Таким образом, процедура перехода к новому опорному решению (новому базису) состоит в приведении вектора A1 к вектору A5 (0;1;0).Эта процедура происходит с помощью преобразований Жордана-Гаусса.
Б |
СБ |
В |
A1 |
A2 |
A3 |
A4 |
A5 |
А6 |
С1=5 |
С2=4 |
С3=3 |
С4=0 |
С5=0 |
С6=0 |
|||
A4 |
0 |
50 |
0 |
11/4 |
7/4 |
1 |
-1/4 |
0 |
A1 |
5 |
15 |
1 |
1/4 |
1/4 |
0 |
¼ |
0 |
А6 |
0 |
0 |
0 |
3/2 |
1/2 |
0 |
-1/2 |
1 |
Zj-Cj |
75 |
0 |
-11/4 |
-7/4 |
0 |
5/4 |
0 |
|
В исходной симплекс-таблице делим всю строку, соответствующую заменяемому базисному вектору, начиная со столбца В, поэлементно на 4. Эта строка называется направляющей.
Столбец, соответствующий небазисному вектору, вводимого в базис, называется направленным столбцом. На пересечении направляющего столбца и строки находится направляющий элемент. Всю направляющую строку делим на 4 и вносим в новую таблицу. Для получения нуля в первой строке и направляющем столбце надо из первой строки вычесть поэлемнтно вторую и т.д. Для получения нуля в третьей строке и направляющем столбце нужно из этой строки вычесть вторую, умноженную на два.
Оценки индексной строки можно не пересчитывать, т.к. базисным векторам соответствует оценка равная нулю, и индексная строка пересчитывается аналогично другим строкам. Задача не всегда имеет решение.
Теорема 4.3 «Условие неразрешимости задачи ЛП»
Задача ЛП не имеет решения, если среди компонентов векторов, вводимых в базис (всех возможных векторов), нет положительных компонентов.
В этом случае невозможно найти величину Q и задача считается не разрешимой.
Теорема 4.4: «Условие вырожденности оптимального плана или его неединственности»
Пусть Х* оптимальный план. Если среди индексных оценок небазисных векторов есть нулевая оценка, а среди коэффициентов разложения вектора, соответствующего данной нулевой оценке по базису, есть хотя бы один положительный элемент, то существует, по крайней мере, еще один оптимальный план, на котором значение целевой функции такое же как и на данном.
Содержательно: это означает, что прямая, соответствующая целевой функции, параллельна одной из граней многогранника.