Опорные решения. Отыскание исходного опорного решения. — КиберПедия 

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

Опорные решения. Отыскание исходного опорного решения.

2017-11-27 1347
Опорные решения. Отыскание исходного опорного решения. 0.00 из 5.00 0 оценок
Заказать работу

Определение.

Опорным решением системы линейных уравнений (1, §5) называется базисное допустимое решение (для которого векторы условий, соответствующие положительным координатам, линейно независимы). Отыскание исходного опорного решения рассмотрим на примере.

Пример.

Найти исходное опорное решение системы уравнений.

(1)

 

Система уравнений приведена к единичному базису.

Выпишем базисное решение:

.

Это базисное решение не является допустимым, т.к. x1=-1<0, x2=-4<0, x7=-1<0.

Поэтому это базисное решение не является опорным. Это происходит от того, что в данной разрешённой системе (1) среди свободных членов есть отрицательные.

Выполним следующие два преобразования:

1) Среди свободных отрицательных членов найдём наибольший по модулю (-4).

Из уравнений (1) и (4) системы линейных уравнений вычтем уравнение (2)

(2)

В результате этого преобразования свободные члены уравнений (1) и (3) стали положительными, и эти уравнения остались разрешёнными относительно неизвестных x1 и x7 соответственно.

2) Умножим уравнение (2) на (-1) в системе (1). В результате преобразований 1 и 2 все свободные члены уравнения системы стали положительными, но при этом второе уравнение системы стало неразрешённым, т.к. неизвестное x2 вошло в уравнение 1 и 3 с коэффициентом (-1) и в уравнение (2) с коэффициентом (-1) после второго преобразования.

Теперь мы должны второе уравнение разрешить относительно какой-либо переменной так, чтобы члены всех уравнений системы (2) остались неотрицательными.

Утверждение.

Если система линейных уравнений содержит уравнение , (*) в котором все то система линейных уравнений не имеет неотрицательных решений (несовместна в ОДР).

Доказательство:

Предположим противное:

Существует неотрицательное решение системы линейных уравнений . Тогда должно выполняться числовое равенство , но это числовое равенство невозможно, т.к. левая часть уравнения «≤0», а правая часть «>0».

Получили противоречие предположение о существовании такого вектора X неверно.

 

Систему линейных уравнений (2) запишем в виде таблицы.

x1 x2 x3 x4 x5 x6 x7 b
      -1   -1     -1             -2   -3   -2   -1                       3:3=1   4:4=1 10:4= 3:2=
      -1   -1             -2 -2   -1                
                                         

Во втором уравнении системы (2) найдём какой-либо положительный элемент; если такого элемента не существует, то это будет означать в соответствии с утверждением несовместность с ОДР.

Тем самым четвёртый столбец таблицы стал разрешающим.

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

Пусть (*)

Теорема: если в системе линейных уравнений (2) выполнить однократное замещение с разрешающим элементом ak4, то все свободные члены уравнений системы останутся неотрицательными.

Доказательство:

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

 

ap4 bp

ak4 bk

 

1) ap4 <0, тогда (после выполнения итерации)=

2) ap4 ≥0, тогда =

В таблице (2) в первой и во второй строке мы возьмём за разрешающий элемент a=4, находящийся во второй строке.

Выпишем опорное решение .

Замечание.

Для того чтобы найти исходное опорное решение системы линейных уравнений, надо привести систему к разрешённому виду. Если при этом все свободные члены уравнений системы будут «≥0», то базисное решение будет опорным.

Если среди свободных членов уравнений разрешённой системы есть отрицательные, то следует выполнить преобразования 1) и 2).

Пусть после выполнения этих преобразований все свободные члены уравнений стали неотрицательными, но i -е уравнение системы стало неразрешённым; выберем s -й столбец в таблице по положительному элементу ais >0 в i -й строке.

Найдём разрешающий элемент, согласно (*), при этом может оказаться:

1. Разрешающий элемент aks оказался в i -й строке, т.е. k=i.

Выполним однократное замещение с разрешающим элементом ais, тогда i-е уравнение системы станет разрешающим относительно xs, и все свободные члены уравнений системы будут неотрицательными, и мы сможем выписать исходное опорное решение.

2. Разрешающий элемент i -й строке, , при этом bk >0.

Выполним однократное замещение с разрешающим элементом aks.

 

ais bi

aks bk

 

При этом свободный член i -го уравнения уменьшится, но i -е уравнение останется неразрешённым, но свободный член уменьшится.

После конечного числа шагов придём к случаю 1., либо в i -м не останется положительных коэффициентов при неизвестных, что означает несовместность системы в ОДР, либо придём к случаю 3.

3. Поэтому, прежде чем выполнять преобразование однократного замещения с разрешающим элементом aks, нужно попробовать выбрать другой разрешающий столбец по другому положительному элементу в i -й строке. Если это сделать нельзя, то нужно выполнить однократное замещение с разрешающим элементом aks, тогда изменится состав базисных неизвестных, и выбор разрешающего элемента нужно будет начинать сначала. Через конечное число шагов придём к случаям 2. или 1., либо установим несовместность системы уравнений в ОДР.

 


Поделиться с друзьями:

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.013 с.