решении также равно минимальному неотрицательному отношению, а именно дс, = 4 (сравните с точкой В на рис. 3.6). Значение целевой функции при этом значении ;c, возрастет до 20 (= 5x4).

Рис. 3.6. Графическая интерпретация отношений как точек пересечения

Замена исключаемой переменной j-, на вводимую переменную дс, приводит к новым множествам базисных и небазисных переменных и новому решению в точке В.

Небазисные (нулевые) переменные: (j,, дг2).

Базисные переменные: (xv s2, s3, st).

Теперь необходимо выполнить преобразования в последней таблице так, чтобы в столбцах "Базис" и "Решения" получить новое решение, соответствующее точке В. Вычисление нового базисного решения основывается на методе исключения переменных (методе Гаусса-Жордана), который описан в разделе А.2.7. Эти вычисления громоздкие и объемные, что делает компьютер незаменимым средством для решения задач линейного программирования. Вы должны освоить ручной способ вычислений хотя бы для того, чтобы понять, как работает симплекс-метод. После этого, вы, вероятно, никогда не будете выполнять вычисления вручную.

В следующей таблице, которая пока совпадает с начальной таблицей задачи ЛП, определим ведущий столбец, ассоциируемый с вводимой переменной, и ведущую строку, ассоциируемую с исключаемой переменной. Элемент, находящийся на пересечении ведущего столбца и ведущей строки, назовем ведущим.

Ведущий столбец

Процесс вычисления нового базисного решения состоит из двух этапов.

1. Вычисление элементов новой ведущей строки.

Новая ведущая строка = текущая ведущая строка / ведущий элемент.

2. Вычисление элементов остальных строк, включая z-строку.

Новая строка = текущая строка - ее коэффициент в ведущем столбце х новая ведущая строка.

В нашем примере выполняем такие вычисления.

1. Новая ведущая .-строка = текущая ведущая .-строка / 6.

2. Новая z-строка = текущая z-строка - (-5) х новая ведущая строка.

3. Новая .-строка = текущая зустрока - (1) х новая ведущая строка.

4. Новая jycTpoKa = текущая -строка - (-1) х новая ведущая строка.

5. Новая л-4-строка = текущая .-строка - (0) х новая ведущая строка.

Новая симплекс-таблица, соответствующая новому базисному решению (xv s2, s3, st), имеет следующий вид (проверьте результаты вычислений!).

Отметим, что новая таблица обладает теми же свойствами, что и начальная: только небазисные переменные хг и sx равны нулю, в столбце "Решение" представлено новое базисное решение (хх = 4, s2 = 2, s3 - 5, st = 2) вместе с новым значением целевой функции z (= 20). Это результат применения метода Гаусса-Жордана.

Из последней таблицы видно, что полученное базисное решение не является оптимальным, поскольку в z-строке переменная хг имеет отрицательный коэффициент. Как и в начальной таблице, строку z можно интерпретировать как уравнение

2 5 z=-x,-s. +20.

3 " 6

Из последнего уравнения следует, что увеличение значения переменной х2 (ее текущее значение равно нулю) приведет к увеличению значения целевой функции. Таким образом, переменная х2 должна стать вводимой в базис.

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

Вычисления показывают, что минимальное (неотрицательное) отношение соответствует переменной s2, которая становится исключаемой; при этом значение отношения (= 3/2) равно новому значению переменной х2. Соответствующее увеличение

2 3

значения целевой функции составит -х - = 1 hz = 20 + 1 = 21.

В этой ситуации ведущей строкой будет -строка, а ведущим столбцом - столбец, соответствующий переменной х2. Ведущий элемент равен 4/3.

Вычисляем элементы новой симплекс-таблицы.

1. Новая ведущая ,у2-строка = текущая .-строка / - .

2. Новая строка z-строка = текущая z-строка - (- - ) х новая ведущая строка.

3. Новая лустрока = текущая л-строка - -j х новая ведущая строка.

4. Новая .-строка = текущая .-строка - - х новая ведущая строка.

5. Новая -строка = текущая -строка - 1 х новая ведущая строка. Эти вычисления приводят к следующей таблице.

Поскольку z-строка не имеет отрицательных коэффициентов, соответствующих небазисным переменным sx и s2, полученное решение оптимально.