С помощью разрешающего элемента
Разрешающим элементом матрицы называется всякий ненулевой элемент. Соответственно ему строка и столбец, в котором он расположен, называются разрешающей строкой и разрешающим столбцом. Алгоритм преобразования матрицы с помощью разрешающего элемента состоит в следующем: ○ новые элементы разрешающей строки получаются из соответствующих элементов прежней строки делением на разрешающий элемент. ○ все элементы разрешающего столбца, кроме разрешающего, равны нулю. ○ остальные элементы расширенной матрицы пересчитываются по правилу прямоугольника: еслиaij – разрешающий элемент, пересчитывается элемент aek расширенной матрицы, то
В матрице это выглядит следующим образом:
Нахождение базисных решений, основанное на использовании разрешающего элемента, производится для наглядности с помощью симплексных таблиц, исходным видом которой является запись расширенной матрицы в виде:
Последующие шаги получаются перерасчетом ее с использованием разрешающего элемента для превращения ее в ступенчатую матрицу для получения одного (первого) базисного решения. Все они (шаги) помещаются друг за другом в симплексной таблице. Если математическая модель, представляемая системой линейных алгебраических уравнений, описывает объект, переменные в которой могут принимать и отрицательные значения, то в качестве разрешающего элемента может приниматься элемент с любым знаком. Большинство задач линейного программирования (для распределения ресурсов, полей под культуры, транспортных средств и др.) имеет дело с неотрицательными переменными, поэтому необходимо уметь находить эти неотрицательные решения изучаемых систем. В этом случае алгоритм нахождения решений (неотрицательных) несколько изменяется: ○ приводим расширенную матрицу к виду, в котором все свободные члены – числа неотрицательные, умножением тех строк на (-1), в которых свободные члены – числа отрицательные; ○ за разрешающий столбец принимается тот, в котором имеется хотя бы один положительный элемент, если такового нет при положительных свободных элементах, то система вырожденна (решений не существует); ○ при наличии в разрешающем столбце нескольких положительных элементов находятся отношения соответствующих свободных элементов к этим положительным элементам, и в качестве разрешающего элемента выбирается тот, для которого это отношение наименьшее; ○ далее осуществляется пересчет таблицы по правилу прямоугольника, данные пересчета рисуются под первой таблицей. Этот метод расчета носит название симплексного. После симплексного пересчета все свободные члены остаются положительными. Выбор столбца с наименьшим отношением свободного члена и положительного элемента столбца обусловлен необходимостью создания устойчивости вычисления (меньшего накопления ошибок при использовании приблизительной оценки элементов матрицы), а также соблюдения неотрицательности свободных членов при преобразованиях. Пример 1. Найти базисные неотрицательные решения системы линейных алгебраических решений. х1+х2+х3+х4+х5=7 3х1+2х2+х3+х4-3х5= -2 х2+2х3+2х4+6х5=23 5х1+4х2+3х3+3х4-х5=12 После умножения второго уравнения на (-1) получаем исходную запись симплексной таблицы и ее преобразования по описанному алгоритму.
Максимальное количество базисных решений, как видно из таблицы, 10, но не все сочетания переменных по 2 дают решения. Получено 3 базисных решения. Других нет. Это тоже видно из таблицы. Из последнего ее шага следует, что в качестве разрешающих элементов могут быть выбраны только 3/2 и 5/4, но они приводят к уже найденным решениям, х5из базисных убрать не представляется возможным. Пример 2. Найти неотрицательные базисные решения системы линейных алгебраических решений.
Умножив второе и четвертое уравнения на (-1), получим исходную матрицу симплексной таблицы.
Две равносильных (вторая и четвертая) строки матрицы имеют однозначное решение (отрицательное, х=-8), поэтому система несовместна, а значит, не имеет неотрицательных решений. Рассмотренные методики решения системы линейных алгебраических уравнений могут быть использованы в расчетах по определению реакций в стержнях, являющихся элементами металлических ферм, расходов жидкости в разветвленных каналах, токов в разветвленных электрических цепях. Самое большое приложение они имеют при оптимизации (отыскании наилучших решений) задач линейного программирования. Особенность применения этих методик в этом случае состоит в необходимости приведения математических моделей линейного программирования к каноническому виду.
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (344)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |