Математическое программирование (линейное программирование). Киселева Э.В - 11 стр.

неизвестного. Процесс продолжают до тех пор, пока не будут ис-                                                                       ′ = 1, ста-
                                                                                       2) все элементы разрешающего столбца, кроме a rs
пользованы все уравнения.
                                                                                   нут равными нулю;
    Рассмотрим систему:
                                                                                       3) элементы, не принадлежащие разрешающей строке и раз-
     ⎧ a11 x1 + a12 x2 + ⋅ ⋅ ⋅ + a1n xn = b1 ,                                     решающему столбцу, вычисляются по формуле:
     ⎪ a x + a x + ⋅⋅⋅ + a x = b ,
     ⎪ 21 1       22 2              2n n     2                                                                aij a rs − ais a rj
     ⎨                                                                                               aij′ =                         , i ≠ r, j ≠ s .         (2.2)
     ⎪L L L L L L L L                                                                                                a rs
     ⎪⎩ am1 x1 + am 2 x2 + ⋅ ⋅ ⋅ + amn xn = bm .                                            …              j-й                      …              s-й
    Расчеты по методу последовательных исключений будем                                                  столбец                                 столбец
проводить в таблицах Гаусса. В исходной таблице будем записы-                               i-я             aij                     …               ais
вать расширенную матрицу системы, дополнив ее последним,                                  строка
контрольным столбцом, элементы которого получены путем                                      …                 …                                        …
суммирования по строкам таблицы:
                                                                                            r-я               arj                   …                  ars
  x1    x2     …     xs        …           xn    Свободный
                                                    член             ∑                    строка
                                                               n

  a11   a12    …     a1s       …           a1n           b1   ∑a     1j   + b1         После вычисления последнего, контрольного элемента в ка-
                                                              j =1                 ждой строке производится сравнение его с суммой элементов со-
  …     …      …     …         …           …             …           …             ответствующей строки.
                                                               n
                                                                                       В ходе применения метода Жордана–Гаусса возможны сле-
  ar1   ar2    …     ars       …           arn           br   ∑a
                                                              j =1
                                                                     rj   + br
                                                                                   дующие случаи:
  …     …      …     …         …           …             …           …                 1. В процессе исключений левая часть уравнения системы
                                                               n                   обращается в нуль, а правая часть равна некоторому числу b, от-
 am1    am2    …     ams       …           amn       bm       ∑a
                                                              j=1
                                                                     mj   + bm     личному от нуля, т.е. получаем равенство:
                                                                                                   0 ⋅ x1 + 0 ⋅ x2 + ... + 0 ⋅ xn = b (b ≠ 0)
    Каждый шаг метода начинается (как мы говорили ранее) с                         Это означает, что система уравнений не имеет решения, так как
выбора разрешающего элемента. Пусть, например, в качестве раз-                     полученному уравнению не могут удовлетворять никакие значе-
решающего элемента выбран элемент ars ≠ 0 , тогда r-cтрока, в                      ния неизвестных x1 , x2 ,K , xn .
которой расположен разрешающий элемент, называется разре-                              2. Левая и правая части какого-либо уравнения обращаются в
шающей строкой, а S-столбец – разрешающим столбцом.                                нуль (0 = 0). Это означает, что это уравнение является линейной
    Переход к новой таблице осуществляется по следующим                            комбинацией остальных, ему удовлетворяет любое найденное
правилам:                                                                          решение системы, поэтому оно может быть отброшено.
      1) элементы разрешающей r-строки вычисляются так:                                3. После того, как все уравнения использованы для исключе-
                                    arj                                            ния неизвестных, придем к таблице, либо содержащей искомое
                           arj′ =          ( j = 1,n),                     (2.1)   решение, либо показывающей несовместность системы ограни-
                                    ars
                                                                                   чений.
                                      23                                                                                    24