С помощью разрешающего элемента

Разрешающим элементом матрицы называется всякий ненулевой элемент. Соответственно ему строка и столбец, в котором он расположен, называются разрешающей строкой и разрешающим столбцом. Алгоритм преобразования матрицы с помощью разрешающего элемента состоит в следующем:

○ новые элементы разрешающей строки получаются из соответствующих элементов прежней строки делением на разрешающий элемент.

○ все элементы разрешающего столбца, кроме разрешающего, равны нулю.

○ остальные элементы расширенной матрицы пересчитываются по правилу прямоугольника: еслиa_ij – разрешающий элемент, пересчитывается элемент a_ek расширенной матрицы, то

В матрице это выглядит следующим образом:

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

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

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

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

○ приводим расширенную матрицу к виду, в котором все свободные члены – числа неотрицательные, умножением тех строк на (-1), в которых свободные члены – числа отрицательные;

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

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

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

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

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

Пример 1. Найти базисные неотрицательные решения системы линейных алгебраических решений.

х₁+х₂+х₃+х₄+х₅=7

3х₁+2х₂+х₃+х₄-3х₅= -2

х₂+2х₃+2х₄+6х₅=23

5х₁+4х₂+3х₃+3х₄-х₅=12

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

Максимальное количество базисных решений, как видно из таблицы, 10, но не все сочетания переменных по 2 дают решения. Получено 3 базисных решения. Других нет. Это тоже видно из таблицы. Из последнего ее шага следует, что в качестве разрешающих элементов могут быть выбраны только 3/2 и 5/4, но они приводят к уже найденным решениям, х₅из базисных убрать не представляется возможным.

Пример 2. Найти неотрицательные базисные решения системы линейных алгебраических решений.

Умножив второе и четвертое уравнения на (-1), получим исходную матрицу симплексной таблицы.

Две равносильных (вторая и четвертая) строки матрицы имеют однозначное решение (отрицательное, х=-8), поэтому система несовместна, а значит, не имеет неотрицательных решений.

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