Таблица показывает множества базисных и небазисных переменных, а также решение, соответствующее данной (начальной) итерации. В разделе 3.3.1 указывалось, что начальная итерация симплекс-метода начинается из точки (* х2) = (0, 0). Это соответствует следующим множествам базисных и небазисных переменных.

Небазисные (нулевые) переменные: (jc х2).

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

Поскольку небазисные переменные хх,хг и коэффициенты при базисных переменных sv s2, s3, s4 в уравнении целевой функции равны нулю, а в формулах левых частей равенств-ограничений - 1, то отсюда сразу без дополнительных вычислений получаем, что z - 0,s1 = 24, s2 = 6, s3 = 1 и st = 2.

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

Будет ли это начальное решение оптимальным? Конечно, нет, поскольку переменные хх и х2 здесь равны нулю, а возрастание этих переменных даже на единицу приводит к увеличению значения целевой функции z= 5хх + 4х, на 5 (при увеличении хх) или 4 (при увеличении х2). Поскольку коэффициент при переменной хх в формуле целевой функции больше, чем коэффициент при х2, переменную jc, следует ввести в число базисных (в этом случае она станет вводимой). Если обратиться к приведенной выше таблице, то вводимая переменная определяется среди множества небазисных как переменная, имеющая наибольший отрицательный коэффициент в z-строке (напомним, что тут решается задача максимизации). Если так случится, что все коэффициенты в z-строке будут неотрицательными, то дальнейшее увеличение значения целевой функции будет невозможно; это будет означать, что достигнуто оптимальное решение.

Чтобы определить исключаемую переменную непосредственно из таблицы, надо вычислить точки пересечения всех функций ограничений с положительным направлением оси хх (повторим, что переменная дс, уже определена как вводимая переменная). Координаты этих точек пересечения можно вычислить как отношения правых частей равенс.тв (значение в столбце Решение ) к коэффициентам при переменной хх в этих равенствах, как показано в следующей таблице.

На рис. 3.6 видно, что неотрицательные отношения порождают точки пересечения на положительной полуоси хг Отношения (пересечения), соответствующие переменным s3 и st, исключаются из рассмотрения, поскольку для них точка пересечения лежит или на отрицательной полуоси, или на бесконечности.

Минимальное неотрицательное отношение соответствует базисной переменной sv тем самым определяя эту переменную как исключаемую (т.е. на следующей итерации ее значение будет равно нулю). Значение вводимой переменной х, в новом

решении также равно минимальному неотрицательному отношению, а именно дс, = 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 можно интерпретировать как уравнение