Имя материала: Математика в экономике

Автор: Солодовников А.С.

§ 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/= - со, и процесс снова прекращается.

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

имеем случай III и, следовательно, должны сделать шаг. Например, как мы считали ранее, пусть -а4>0, -Р4>0 (это означает а4<0, Р4 < 0), a -у4 > 0 (т. е. у4 < 0), в точном соответствии с предположением (8.7) § 8.1. В этом случае описанная ранее методика предписывает составить отношения

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

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

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

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

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

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

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

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

 

Базисные неизвестные

Свободные члены

х

х2

*3

х4

*5

х

1

1

0

0

1

-2

х2

2

0

1

0

-2

і    1 і

ХЪ

3

0

0

1

3

1

I

0

0

0

0

- 1

1

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |