28.7. Выбор разрешающего элемента. Симплекс-таблицы.

Условимся вектор  называть положительным (отрицательным) и писать , если его первая не равная нулю компонента положительная (отрицательная).

Будем говорить, что вектор  меньше вектора  или вектор  больше вектора , и писать  или , если .

Замечание 2. Целесообразность приведенных определений ,  для векторов  можно подтвердить следующими соображениями.

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

.

Многочлен в квадратных скобках больше нуля  в некоторой окрестности нуля. Далее  для . Значит,  для всех , где  – некоторое положительное число.

Таким образом, если вектор , то соответствующий многочлен  для  при некотором .

Вернемся теперь к системе ограничений (12), которую мы запишем в форме

Таблица 1

Базис		Свободные члены	Дополнительная матрица
форма

,                                                (12)

а линейную функцию (13) запишем в виде

.                                                                     (13)

Здесь базис .

Оформим систему равенств (12) и (13) в виде таблицы 1 (матрицы).

Табл. 1 называется симплекс-таблицей. В табл. 1 мы приписали некоторую добавочную матрицу  размера  и добавочную строку . Введем в рассмотрение векторы

.

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

Будем считать, что числа  подобраны так, что базис  положительный и матрица  невырожденная (т. е. определитель, порожденный матрицей, отличен от нуля). Вектор  выбираем произвольно. Можно считать, что .

В дальнейшем при переходе от базиса  к другому базису  записи систем ограничений (12) и линейной функции (13) будут изменяться, этому соответствует изменение табл. 1 с помощью некоторых элементарных преобразований ( см. § 4.7), которые мы распространяем и на добавочную матрицу  и добавочную строку . В результате векторы  и  будут соответственно изменяться.

Напомним, что в случае  существует  такое, что , и , где  - непустое множество и, кроме того,  хотя бы для одного .

Индексов  для которых имеет место , может быть несколько. Не имеет значения, какой из них надо взять. Но, если мы остановились на некотором , то индекс  предлагается выбрать следующим образом:

.                                                                               (26)

Элемент   разрешающий. В табл. 1 мы его поместили в рамку.

Минимум в (26) достигается для одного , потому, что если бы нашлось , для которого

,

то в матрице  были бы две пропорциональные строки и она была бы вырожденной.

Замечание 3. Так как мы рассматриваем случай  то среди  имеются такие, для которых , поэтому

,

т.е. индекс  находится среди таких , для которых .

В п. 28.5. мы брали в качестве  одно из значений , для которых . Но таких значений может быть несколько. В данном способе среди них выбирается одно такое определенное значение, обращающее в минимум .

Мы уже знаем, что в данном случае  базис  можно заменить на другой базис , которому соответствует система ограничений, эквивалентная системе (12):

   (27)

,

и линейная функция

.                              (28)

Системе равенств (27)-(28) соответствует таблица 2.

Табл. 2 получается из табл. 1 следующим образом. Делим -ю строку табл. 1 на разрешающий элемент .

Таблица 2

Базис		Свободные члены	Дополнительная матрица
форма

 

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

Этот прием соответствует замене -го уравнения разностью между ним и видоизмененным -м уравнением, умноженным на число  , что приводит к системе (27), равносильной системе (12).

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

,

поэтому

;

для

в силу правила выбора  и его единственности (см. (26)); для , очевидно,

.

Чтобы получить последнюю строку табл. 2, надо из последней строки табл. 1 вычесть видоизмененную -ю строку, умноженную на . Вектор  переходит в вектор

.

Так как , то

,

т.е. .

Новые коэффициенты линейной функции  имеют вид

.

Таким образом, мы пришли к положительному базису .

Чтобы табл. 2 была полностью аналогичной табл. 1, рекомендуем в табл. 2 переставить местами столбцы, отвечающие переменным  и .

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

.

Замечание 4. Если в процессе применения симплекс-метода мы пришли к циклу ( см. (25)), то можно взять один из базисов цикла, например , и последовательно применять к нему описанный выше способ однозначного получения нового базиса на основании правила (26) выбора разрешающего элемента. Этим гарантируется получение каждый раз базиса, отличного от всех предшествующих. Так как количество возможных базисов конечно, то мы для некоторого базиса цепи обязательно придем к случаям  или . В последнем случае возникает базис , для которого . Базисы, возникшие после , отличаются от базиса  и всех ему предшествующих базисов. Они могут создавать циклы, но состоящие из новых базисов, отличных от  и ему предшествующих. Итак, вычисления по симплекс-методу производятся следующим образом:

1. исследуются уравнения (12) с базисом  и функция ;

2. если будут иметь место случаи  или , то задача на минимум  решена;

3. если будет случай , то переходим к новому базису на основании (16), составляя таблицы 1 и 2 без добавочной матрицы ;

4. если же будет случай , то можно продолжать наш процесс в надежде, что не случится цикла. Практика показывает, что циклы бывают очень редко;

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

6. для базиса  мы выбираем матрицу  и вектор  произвольно, как было указано выше;

7. дальнейшие базисы, следуя методу, получаются определенным образом, а вместе с ними определенным образом преобразуются матрицы  и вектор ;

8. через конечное число шагов мы выясним, что , или же найдем конечный минимум .

Проследим симплекс-метод на конкретном примере.

Пример 5. Найти минимум линейной функции

при ограничениях

Решение. Здесь базис , и ограничения, и функция  записаны в форме (12)-(13). В данном случае  и в первом столбце матрицы ограничений имеются положительные элементы . Отношения . Поэтому

и этот минимум достигается на двух элементах .

Таким образом, мы имеем случай . Чтобы избежать образования цикла, используем описанный выше способ однозначного выбора разрешающего элемента (см.(26)). Для этой цели составим таблицу 1*.

Здесь  и . Поэтому разрешающим элементом будет , стоящий на пересечении строки для  и столбца для . Эту строку и столбец мы выделяем стрелками, а разрешающий элемент обводим рамкой. Преобразуем эту таблицу в таблицу 2*.

↓                                       Таблица 1*

Базис		Свободные члены	Добавочная матрица
форма

Разделим строку для  на , т.е. умножим строку для  на 4 и перенесем ее в табл. 2*.

Затем умножим вторую строку (видоизмененную) на  и вычтем из первой строки. Далее умножим вторую строку на  и вычтем из последней строки.

Строку для  переносим в табл. 2* без изменений . Кроме того, мы переставим местами столбцы для  и , тогда табл. 2* будет иметь вид:

↓                                   Таблица 2*

Базис		Свободные члены	Добавочная матрица
форма

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

Таблица 3* будет иметь следующий вид (после перестановки столбцов для  и ):

↓                                              Таблица 3*

Базис		Свободные члены	Добавочная матрица
форма

В последней строке табл. 3* имеется только один положительный коэффициент . В столбце для  все элементы также положительны. В данной таблице

.

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

↓                                             Таблица 4*

Базис		Свободные члены	Добавочная матрица
форма

 

↓                                                    Таблица 5*

Базис		Свободные члены	Добавочная матрица
форма

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

В последней строке табл. 5* все коэффициенты  отрицательные, следовательно,  (случай ).

Базис . Из табл. 5* видно, что базисное решение имеет вид .

Замечание 5. Если бы мы не следовали правилу однозначного выбора разрешающего элемента, то могли бы получить цикл, выбирая базисы в следующей последовательности:

Замечание 6. Отметим, что на каждом этапе, начиная с первого, можно было бы изменять нумерацию переменных приводя систему ограничений и функцию  к виду (12), (13).