решении также равно минимальному неотрицательному отношению, а именно дс, = 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), имеет следующий вид (проверьте результаты вычислений!).
Базис | | | | | | | | Решение |
| | | -2/3 | | | | | |
| | | | | | | | |
<- S2 | | | | -1/6 | 113Я | | | шшшшш |
| | | 1.5/3 4 | | | | | |
| | | .- 1 . | | | | | |
Отметим, что новая таблица обладает теми же свойствами, что и начальная: только небазисные переменные хг и sx равны нулю, в столбце "Решение" представлено новое базисное решение (хх = 4, s2 = 2, s3 - 5, st = 2) вместе с новым значением целевой функции z (= 20). Это результат применения метода Гаусса-Жордана.
Из последней таблицы видно, что полученное базисное решение не является оптимальным, поскольку в z-строке переменная хг имеет отрицательный коэффициент. Как и в начальной таблице, строку z можно интерпретировать как уравнение
2 5 z=-x,-s. +20.
3 " 6
Из последнего уравнения следует, что увеличение значения переменной х2 (ее текущее значение равно нулю) приведет к увеличению значения целевой функции. Таким образом, переменная х2 должна стать вводимой в базис.
Далее определим исключаемую переменную. Для этого вычислим отношения правых частей равенств, соответствующих ограничениям, к коэффициентам, стоящим прих, в этих равенствах.
Базис | Коэффициенты при х2 | Решение | | Отношение |
| | | | = 4/(2/3) = 6 |
| | | | = 2/(4/3) = 3/2 (минимум) |
| | | | = 5/(5/3) = 3 |
| | | | = 2/1=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 х новая ведущая строка. Эти вычисления приводят к следующей таблице.
Базис | | | | | | | | Решение |
| | | | | | | | |
| | | | | -1/2 | | | |
| | | | -1/8 | | | | |
| | | | | -5/4 | | | |
| | | | | -3/4 | | | |
Поскольку z-строка не имеет отрицательных коэффициентов, соответствующих небазисным переменным sx и s2, полученное решение оптимально.