28.8. Условия существования базиса

28.8. Условия существования базиса.

Поясним, как можно привести систему ограничений (4)

(4)

к системе вида (12)

, (12)

т. е. выясним, когда переменные образуют базис. Как нам известно, система (4) разрешима (совместна) тогда и только тогда, когда ранг матрицы

равен рангу расширенной матрицы

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

Кроме того, всегда можно добиться путем перенумерации переменных того, чтобы

Теорема 2. Для того чтобы неизвестные из системы (4) образовывали базис, необходимо и достаточно, чтобы

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

Доказательство. Пусть . Применяя правило Крамера (см. § 4.2), имеем

Учитывая свойства определителей, получаем равенства вида (12)

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

Обратно, пусть система есть базис, т. е. выполняются соотношения (12). Для матрицы равенств (12)

Допустимыми элементарными преобразованиями эта матрица переходит в матрицу равенств (4). При этом определители и переходят в определители и пропорционально. Поэтому

Пример 6. Найти базисные переменные в системе ограничений

где - некоторое число.

Решение. Если , то система ограничений несовместна в области . Поэтому будем считать . Выясним, при каком элементы будут базисом. Имеем

Отсюда

Таким образом, при все отношения и - базис.

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

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

Итак

Последняя матрица определяет следующую систему уравнений:

Аналогичным образом можно проверить, при каком переменные образуют базис.

28.9. Задачи. Найти минимум функции при ограничениях

Приведем решение первой задачи. Итак, необходимо найти минимум линейной формы при ограничениях

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

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

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

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

Отношение , следовательно, согласно теореме 2 п. 28.8 элементы не образуют базиса.

Проверим тройку :

Отношение и тройка также не образует базиса.

Исследуем тройку :

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

Чтобы написать систему ограничений вида (12), преобразуем матрицу системы ограничений к необходимому виду. Предварительно переставим столбцы коэффициентов при и соответственно на второе и третье места.

Тогда

Последняя матрица определяет систему уравнений

(27)

Линейная форма через свободные переменные и запишется следующим образом:

или

Таким образом, теперь необходимо найти минимум линейной функции

при ограничениях (27).

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

В данном случае и в первом столбце матрицы ограничений имеется положительный элемент .

Отношение , т.е. мы имеем случай и - разрешающий элемент. Составим первую симплекс таблицу:

↓ Таблица 6*

Базис

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

Форма

Здесь разрешающий элемент . Преобразуем таблицу 6* в таблицу 7*. Строку для умножим на 5 и перенесем ее в табл. 7*. Строку для перенесем в табл. 7* без изменений (так как ).

Затем умножим первую строку на 2 и прибавим результат к последней строке. Далее умножим первую строку на 2 и вычтем из строки для формы . Кроме того, переставим местами столбцы для и . В результате табл. 7* будет иметь следующий вид:

↓ Таблица 7*

Базис

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

Форма

В табл. 7* коэффициенты формы неположительны , поэтому при ограничениях (27)

и задача решена.

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