§ 8.2. симплекс-таблицы

§ 8.2. симплекс-таблицы

Производя расчеты по симплекс-методу, нет необходимости выписывать все вычисления столь подробно, как мы делали это в предыдущих примерах. Оказывается, весь процесс можно записать в виде последовательности однотипно заполняемых таблиц, причем каждому шагу будет отвечать переход к следующей таблице.

Описание симплекс-таблиц произведем на примере задачи (8.4), (8.5), где требуется минимизировать функцию (8.5) при ограничениях (8.4) и условиях Xj > 0 (/ = I,... , 5).

Для заполнения первой таблицы необходимо в каждом из уравнений (8.4) перенести все члены, кроме свободного, из правой части в левую, т. е. записать (8.4) в виде :

х{ а4х4 а5х5 = а,

■ х2 -р44-ру5 = р, (8.20)

х3-у4х4-у5х5 = У-Аналогичную работу следует проделать и с равенством (8.5):

/54х4 55х5 = 8.

Заглавная строка таблицы и характер заполнения, не считая стрелок, в комментариях не нуждаются. Расстановку стрелок поясним ниже.

В соответствии с ранее описанной методикой мы должны прежде всего выяснить, имеется ли в первоначальном выражении для

/= 54х4 + б5х5 + 5

хотя бы один отрицательный коэффициент при х4 и х5. Поскольку при внесении в таблицу коэффициенты при х4 и х5 поменяли знаки,

то мы должны, следовательно, выяснить, имеются ли в последней строке таблицы (не считая свободного члена 6) положительные числа. Если таковых нет, то базисное решение, отвечающее данному базису, т. е. (а, р, у, 0,0), является оптимальным, a min/ = 8— задача решена.

Предположим, что в последней строке имеется (не считая 8) положительное число 84. Отмечаем столбец, в котором оно находится,

вертикальной стрелкой. Далее просматриваем остальные числа этого столбца. Если среди них нет отрицательных чисел — это означает, что а4 > 0, р4 > 0, у4 £ 0, и мы имеем случай II. Тогда min/= со, и процесс снова прекращается.

Пусть, наконец, среди чисел отмеченного столбца, кроме последнего числа, имеются положительные числа. Это означает, что мы

и выбрать из них наименьшее.

п а Пусть, например, таковым является отношение отвечающее строке таблицы с базисным неизвестным хх. Отмечаем эту строку горизонтальной стрелкой. Элемент таблицы, стоящий в отмеченном столбце и отмеченной строке, называется разрешаю-* щим элементом. В данном случае это -а4 (в таблице он обведен пунктиром).

С этого момента начинается перестройка таблицы, цель которой состоит в переходе к новому базису {х4, х2, Ху). Ее можно осуществить при помощи все того же метода Гаусса. А именно умножаем выделенную строку на такое число, чтобы на месте разрешающего

— „ , , _„ на ^ Это с_

вуеттому, что первое из уравнений (8.20) разрешается относительно нового базисного неизвестного х4. Полученную таким образом новую строку вписываем уже в новую таблицу снова в виде первой строки. Затем к каждой из остальных строк таблицы 1 прибавляем вновь полученную строку, умноженную на такое число, чтобы в клетке отмеченного столбца появился нуль — это соответствует исключению неизвестного х4 из остальных уравнений, а также из

выражения для /. Преобразованные таким образом строки пишем в новую таблицу на место прежних строк. В результате получаем новую таблицу 2.

К новой таблице применяется та же процедура. В результате или находится оптимальное решение (случай I), или обнаруживается, что min/= со (случай II), или же производится следующий шаг (случай III) — получаем новую таблицу 3. И так далее, пока процесс не остановится (случай I или случай III).

Вот как будет выглядеть при такой методике решение примера 1 § 8.1. Исходная таблица имеет вид:

В этой таблице последняя строка (не считая свободного члена) не имеет положительных чисел. Значит, достигнуто оптимальное решение

х = ~g~. x2 = ),x^~v,x4^)х$^ ,

а минимум/равен -у-.

Разумеется, практически удобнее все таблицы «пристыковывать» друг к другу по вертикали, что позволяет, начиная со второй таблицы, не писать заглавную строку.

Итак, подведем итог в виде следующего алгоритма.

Алгоритм работы по симплекс-методу

Выделяем исходный допустимый базис и заполняем первую таблицу.

Если в последней строке полученной таблицы, кроме, быть может, первого числа, нет положительных чисел, то базисное решение является оптимальным — задача решена.

Пусть среди указанных в пункте 2 чисел имеется положительное число (скажем, в столбце*;). Отмечаем столбец ^вертикальной стрелкой. Просматриваем остальные числа этого столбца. Если среди них нет положительных чисел, то min/= <ю — задача решения не имеет.

Пусть среди просмотренных в пункте 3 чисел имеются положительные числа. Для каждого из таких чисел а составляем отношение

^, где Ь — первое число в той же строке (свободный член). Из всех

таких отношений выбираем наименьшее. Пусть оно соответствует строке для базисного неизвестного xt. Отмечаем эту строку горизонтальной стрелкой. Число а, стоящее в отмеченной строке и отмеченном столбце, называется разрешающим элементом таблицы.

Переходим к новой таблице. Для этого отмеченную строку

умножаем на ^ (чтобы на месте разрешающего элемента появилась

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

С новой таблицей возвращаемся к выполнению пункта 2.