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

Исследование и решение СЛАУ методом послежовательного исключения неизвестных Жордана,нахождение различных предпочитаемых эквивалентов данной СЛАУ и базисных решений, общего решения.

Суть метода сост в том, что за счёт элемен-х преобр-й, за конечное число шагов система произ-ся к так назыв-му, предпочит-му или каноническому виду, кот легко исслед-ся и решаются. Выбирается разрешающее ур-е, в кот выбир неизвестная,коэф-т при кот отличен от нуля (разреш-ая неизвестная), а коэф-т при ней назыв разрешающий коэф-т. Путём элем-х преобразований разреш-ая неизвестная искл-ся из всех урав-й системы кроме разрешающей. Берётся след ур-е и след разреш-ая перем-ая отличная от первой, далее путём элем-х преобр-й она искл-ся из всех ур-й системы кроме разрешающей и т.д. пример:

а₁₁х₁+а₁₂х₂+а_1nх_n=b_{1 –} разреш урав-е

а₁₁¹0 а_m1х₁-разреш перем-ая

нужно искл х₁ из всех ур-й кроме разрешающего. Нужно 1-е ур-е *-а₂₁/а₁₁=>

-а₂₁х₁- а₁₂*а₂₁/а₁₁*х₂ -…- а₂₁*а_1n/а₁₁*х_n=-b₁*а₂₁/а₁₁ + 2 ур-е системы

В рез-те преобр-й возможны след.случаи:

1) в процессе реш-я появл равенства 0*х₁+0-х₂+…+0-х_n=b_i в_i¹0

при появл такого равенства пишем что сис-ма несовместна.

2) левая и правая части i ур-я обращ-ся в 0, т.е.0=0 Þ данное ур-е явл линейной комбинацией ур-й вход-х в эту систему, в этом случ это ур-е исключается из всей системы

3) после того как все ур-я слау будут испол для искл неиз-х, либо будут получены решения системы, либо будет доказана её несовместимость,система будет приведена к след виду: х₁+q_1,m+1*x_m+1+…+q_1n*х_n=h₁

х₂+q_2,m+1*x_m+1+…+q_2n*х_n=h₂

_. ..............

х_m+q_m,m+1*x_m+1+…+q_mn*х_n=h_m

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

х₁=h₁-q_1,m+1-x_m+1-…-q_m*x_n

х₂=h₂-q_2,m+1-x_m+1-…-q_2n*x_n

……………………………….

x_m=h_m-q_m,m+1-x_m+1-…-q_mn*x_n

Придавая свободным неизв какие-либо зн-я будем получать опред зн-я базисных неизв-х. Такие решения слау наз частными небазисными реш-ми. В том случае, если все свободные перем-е = 0, то полученное знач-е базисных перем-х в совм-ти с нулевыми свободными назыв базисным решением слау: х₁=h₁ x₂=h₂ x_m+1=0 и т.д. х_n=0

 

4.Преобразование СЛАУ с сохранением неотрицательности правых частей уравнений,нахождение различных базисных неотрицательных решений, правила выбора разр-щей неизвестной и разр-щего уравнения,их обоснование.

Если правые части всех уравнений полученных систем окаж неотриц-ми,то соотв базисные решения также будут неотрицательными.=>чтобы получить неотриц базисные решения СЛУ,надо научиться вести процесс исключения неиз-х так, чтобы свободные члены всех ур-й на всех этапах этого процесса оставались неотрицательными.Для этого следует руковод-ся след правилам: 1)если в СЛАУ им отриц свободные члены,то все такие ур-я необх *(-1); 2)в кач-ве разр-щей приним ту переменную,коэф-т при кот хотя бы в одном ур-нии системы положителен; 3)для нахождения разрешающего уравнения находят тип отношений столбца свободных членов к положительным эл-там разр-щего солбца,в этом сл k-ое ур-е будет разр-щим

min(b_i/a_ij>o)=b_k/a_ij

Если хотя бы в одном из ур-й системы свободный член положителен,а все коэф-ты при неизв-х<0,то система неотрицательных реш-й не имеет.Преобразования системы в соотв с этими правилами наз симплекс преоб-ниями системы. Если указанный min достигается для неск-х ур-й системы,то такая система наз вырожденной. Необх-м условием вырожденной системы явл то,что свободный член хотя бы одного ур-я системы=0.

Основное нерав-во теории двойственности.

Для любых допустимых решений х(х₁,х₂,..х_n) и y(y₁,y₂,..y_n) прямой и двойственной задач ЛП справедливо нерав-во:

Док-во: ()x_j = *. Эта сумма не изменится, если мы поменяем порядок суммирования: *= ()y_j ; *

 

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

Метод потенциалов

Заполненные клетки будем называть базисными. Для каждой баз.клетки, лежащей на пересечении строки i и столбца j, напишем уравнение p_i+q_j=c_ij. Переменные p и q называют потенциалами, которых (m+n), а уравнений (m+n-1), поэтому одной переменной можно присвоить произвольной значение. - пусть р₁=0. Далее для небазисных клеток вычисляем относительные оценочные коэф-ты: = p_i+q_j-c_ij.. Находим max( >0). Решение оптимально если все <=0, если не так, то строим цикл пересчета, кот. начинается и заканчивается выбранной небазисной клеткой. Присвоим знаки вершинам цикла: выбранной небазисной клетке “+“, следующей вершине- “-“, затем знаки чередуются. Среди вершин со знаком “–“ находим наименьшее число. Затем вычитаем его из вершин со знаком “–“ и прибавляем к вершинам со знаком “+“. Допустим, что min достигается в нескольких базисных клетках, тогда выбираем любую, делаем ее небазисной, а во всех остальных ставятся нули.

Экон.смысл: оценка свободной клетки показывает, насколько уменьшатся суммарные расходы по перевозке груза, если поставить единицу груза от i-го производителя j-му потребителю

Исследование и решение СЛАУ методом послежовательного исключения неизвестных Жордана,нахождение различных предпочитаемых эквивалентов данной СЛАУ и базисных решений, общего решения.

Суть метода сост в том, что за счёт элемен-х преобр-й, за конечное число шагов система произ-ся к так назыв-му, предпочит-му или каноническому виду, кот легко исслед-ся и решаются. Выбирается разрешающее ур-е, в кот выбир неизвестная,коэф-т при кот отличен от нуля (разреш-ая неизвестная), а коэф-т при ней назыв разрешающий коэф-т. Путём элем-х преобразований разреш-ая неизвестная искл-ся из всех урав-й системы кроме разрешающей. Берётся след ур-е и след разреш-ая перем-ая отличная от первой, далее путём элем-х преобр-й она искл-ся из всех ур-й системы кроме разрешающей и т.д. пример:

а₁₁х₁+а₁₂х₂+а_1nх_n=b_{1 –} разреш урав-е

а₁₁¹0 а_m1х₁-разреш перем-ая

нужно искл х₁ из всех ур-й кроме разрешающего. Нужно 1-е ур-е *-а₂₁/а₁₁=>

-а₂₁х₁- а₁₂*а₂₁/а₁₁*х₂ -…- а₂₁*а_1n/а₁₁*х_n=-b₁*а₂₁/а₁₁ + 2 ур-е системы

В рез-те преобр-й возможны след.случаи:

1) в процессе реш-я появл равенства 0*х₁+0-х₂+…+0-х_n=b_i в_i¹0

при появл такого равенства пишем что сис-ма несовместна.

2) левая и правая части i ур-я обращ-ся в 0, т.е.0=0 Þ данное ур-е явл линейной комбинацией ур-й вход-х в эту систему, в этом случ это ур-е исключается из всей системы

3) после того как все ур-я слау будут испол для искл неиз-х, либо будут получены решения системы, либо будет доказана её несовместимость,система будет приведена к след виду: х₁+q_1,m+1*x_m+1+…+q_1n*х_n=h₁

х₂+q_2,m+1*x_m+1+…+q_2n*х_n=h₂

_. ..............

х_m+q_m,m+1*x_m+1+…+q_mn*х_n=h_m

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

х₁=h₁-q_1,m+1-x_m+1-…-q_m*x_n

х₂=h₂-q_2,m+1-x_m+1-…-q_2n*x_n

……………………………….

x_m=h_m-q_m,m+1-x_m+1-…-q_mn*x_n

Придавая свободным неизв какие-либо зн-я будем получать опред зн-я базисных неизв-х. Такие решения слау наз частными небазисными реш-ми. В том случае, если все свободные перем-е = 0, то полученное знач-е базисных перем-х в совм-ти с нулевыми свободными назыв базисным решением слау: х₁=h₁ x₂=h₂ x_m+1=0 и т.д. х_n=0

 

4.Преобразование СЛАУ с сохранением неотрицательности правых частей уравнений,нахождение различных базисных неотрицательных решений, правила выбора разр-щей неизвестной и разр-щего уравнения,их обоснование.

Если правые части всех уравнений полученных систем окаж неотриц-ми,то соотв базисные решения также будут неотрицательными.=>чтобы получить неотриц базисные решения СЛУ,надо научиться вести процесс исключения неиз-х так, чтобы свободные члены всех ур-й на всех этапах этого процесса оставались неотрицательными.Для этого следует руковод-ся след правилам: 1)если в СЛАУ им отриц свободные члены,то все такие ур-я необх *(-1); 2)в кач-ве разр-щей приним ту переменную,коэф-т при кот хотя бы в одном ур-нии системы положителен; 3)для нахождения разрешающего уравнения находят тип отношений столбца свободных членов к положительным эл-там разр-щего солбца,в этом сл k-ое ур-е будет разр-щим

min(b_i/a_ij>o)=b_k/a_ij

Если хотя бы в одном из ур-й системы свободный член положителен,а все коэф-ты при неизв-х<0,то система неотрицательных реш-й не имеет.Преобразования системы в соотв с этими правилами наз симплекс преоб-ниями системы. Если указанный min достигается для неск-х ур-й системы,то такая система наз вырожденной. Необх-м условием вырожденной системы явл то,что свободный член хотя бы одного ур-я системы=0.