МИНИСТЕРСТВА ОБРАЗОВАНИЯ И НАУКИ  РЕСПУБЛИКИ                 КАЗАХСТАН

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА АЛМАТЫ

АЛМАТИНСКИЙ КОЛЛЕДЖ УПРАВЛЕНИЯ И РЫНКА

 

 

 

 

 

 

 

 

 

 

 

 

НА ТЕМУ: “ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ”

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                         ПРОВЕРИЛА:  АЙМУХАНБЕТОВА Ш.Е

                                       ВЫПОЛНИЛА:  УЧАЩИЕСЯ III КУРСА СПЕЦИАЛЬНОСТИ ПРОГРАММНОЕ

ОБЕСПЕЧЕНИЕ  ВТ И АС 

НАБИЕВА А.Б

 

 

 

 

АЛМАТЫ 2007 Г

 

       СОДЕРЖАНИЕ

 

1. Общая задача линейного программирования
2. Элементы линейной алгебры и геометрии выпуклых множеств
3. Свойства задачи линейного программирования
4. Теоретические основы методов линейного программирования
5. Геометрические методы решения задач линейного программирования
6. Применение метода Жордана – Гаусса к решению системных линейных уравнений
7. Библиографический список

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

     Примеры задач линейного программирования позволяют сформировать общую задачу линейного программирования. Дана система m  линейных уравнений и неравенств  с  n   переменными

 

          α ₁₁x₁ + α₁₂x₂ + …+ α_1n x_n ≤ b₁,

          α ₂₁x₁ + α₂₂x₂ + …+ α_2n x_n ≤ b₂,

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

          α _k1x₁ + α_k2x₂ + …+ α_kn x_n ≤ b_k,

          α _k +l,l +  α_k+1,2x₂ + …+ α_k+1,n x_n =  b_k+1

          α _k+2,1x₁ + α_k+2,2x₂ + …+ α_k+2,n x_n = b_k+2

          …………………………………………

          α _m1x₁ + α_m2x₂ + …+ α_mn x_n = b_m

и линейная функция

          F = c₁ x₁ + c₂ x₂ + …+ c_n x_n

 

Необходимо найти такое решение системы   Х=(x₁, x₂,…,х_j,…, x_n), где     х_j ≥0 (j = 1,2,…, l:l  ≤ n), при котором линейная функция  F принимает оптимальное значение. Система называется системой ограничений, а функция F – линейной функцией цели. Более кратко общую задачу линейного программирования можно представить в виде:

               F = Σc_jx_j → max (или → min)

при ограничениях:

 

          Σ α_ijx_j ≤ b_i(i = 1,2,…,k),

          Σ α_ijx_j ≤ b_i(i =k + 1, k + 2,…,m),

         X_j ≥0 (j = 1,2,…,l;l ≤ n).

Оптимальным решением задачи линейного программирования называется решения Х=(x₁, x₂,…,х_j,…, x_n) система ограничений удовлетворяющее условию, при котором линейная функция принимает оптимальное значение. Термины «решение» и «план» – синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй – о содержательной стороне (экономические интерпретации). При условии, что все переменные неотрицательны (X_j ≥0, j = 1,2,…,n), система ограничений состоит лишь из одних неравенств ,- такая задача линейного программирования называется стандартной, если система ограничений из одних уравнений, та задача называется канонической. Так, в приведенном выше примерах задач линейного программирования задачи 1 и 2 – стандартные, задача 4 – каноническая, а задача, а задача 3 – общая.

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

    Ранг матрицы. Эквивалентные матрицы. Дана прямоугольная матрица.

 

               α₁₁ α_{12 …} α_1n

     A =    α₂₁ α_22… α_2n

                     …………………

               α_n1α_n2….… α_nn

выделим в этой матрице к произведенных столбцов и к произведенных строк (k ≤ m, k ≤ n). Определитель которого порядка, составлений из элементов матрицы А, расположенных на пересечении выделенных строк и столбцов, называются минором которого порядка матрицы А. матрица А имеет

 

         С · С миноров которого порядка.

Рассмотрим всевозможные миноры матрицы А,  отличные от нуля. Рангом матрицы А называется наибольший порядок минора этой матрицы принимают равным нулю. Всякий отличный от нуля минор матрицы, порядок которого равен рангу этой матрицы называется базисным минором матрицы. Ранг матрицы А будем обозначать через r(A). r(A) = r(B) , матрицы А и В называется эквивалентными. В этом случае записывают А ~ В. ранг матрицы не изменяется от элементарных приобретений. Под элементами преобразованиями понимается:

1. замена строк столбцами, α столбцов соответственно строками;
2. перестановка строк матрицы;
3. вычеркните строки, все элементы которой равны нулю;
4. умножение какой – либо строки на число не равно нулю;
5. прибавление к матрицам одной строки соответствующих элементов другой строки.

ПРИМЕР 1

 

Определить ранг матрицы

 

            2  3  4

            4  6  8

           6  9  12

 

определитель матрицы второго и третьего порядка.

 

 

 

 

 

        4   6                             1  2

М =          = 0;          М =              

        6  9                              2  4

 все миноры второго и третьего порядка равны нулю, следовательно, ранг матрицы  r (A) = 1

 

ПРИМЕР 2

 

       1 0 0 0 5

       0 0 0 0 0

       2 0 0 0 11

 

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

 

        1    5

        2    11         

 

 так как                 1    5

                                        = 0 = 1,  то ранг матрицы r (A) = 2

                             2    11

 

 ПРИМЕР 3.  Сколько миноров второго порядка имеет матрица

 

        α₁₁  α₁₂ α₁₃

А =  α₂₁ α₂₂ α₂₃

           α₃₁ α₃₂ α₃₃

 

 

С • С = 3·3 = 9  миноров второго порядка

Исследования систем  m  линейных  уравнений  с  n  неизвестными. Дана система m линейной уравнений с  n  неизвестными.

 

 α₁₁ x₁ + α₁₂ x₂ +…+ α_1nx_n  = b₁

 α₂₁ x₁ + α₂₂ x₂ +…+ α_2nx_n  = b₂

_{……………………………………………………..}

α _m1 x₁ + α_m2 x₂ +…+ α_mnx_n  = b_m

 

      Решением этой системы называется совокупность n  чисел

 (x₁, x₂,…, x_n), которое при подстановки в уравнения, обращают их в тождества. Система уравнений называется совместный, если она имеет хотя бы одно решение. Если же система не имеет ни одного решения, то она называется несовместной. Совместная система называется определенной, если она имеет больше одного решения.

 

Матрица

 

       

 

                    α₁₁  α₁₂ … α_1n

           А =   α₂₁ α₂₂ … α_2n

                            ………………….

                            α₃₁ α₃₂ …α_3n

называется матрицей системы. Матрица

 

                    α₁₁  α₁₂ … α_1n b₁

           А =   α₂₁ α₂₂ … α_2n b₂

                            ……………………..

                            α_m1 α_m2 …α_mn b_m

называется расширенной матрицей этой системы.

  Для совместной системы необходимо и достаточно, чтобы ранг матрицы система равнялся рангу расширенной матрицы  этой системы.

           r(A) = r(A₁) = r

Если  b = b₂ = … b_n = 0,   то система линейного уравнения называется однородной. Однородная система уровней всегда совместна. Если ранг совместной системы равен числу  неизвестных (т.е. r = n), то система будет определенной. Если же ранг совместимой системы меньших числа неизвестных, то система неопределенная.

 

 

 

 

 

 

 

 

 

 

 

 

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

 Матричная форма записи:

 

            F = CX → max (min)

при ограничениях

 

             АX = В,

             X ≥ 0

 

где

 

                                    α₁₁ α_12… α_1n                          x₁                                        b₁

                                    α₁₁ α_{11 …} α₁₁                         x₂                          b₂

С = (с₁,с₂,…,с_n); A = ……………  ;    X = …                  B =   …

                                                 α₁₁ α_{11 …} α₁₁                          x_n                          b_m

 

здесь  С —    матрица – строка, А – матрица систем, Х – матрица – столбец переменных, В – матрица – столбец свободных членов.

   Векторная форма записи:

 

         F = CX → max (min)

при ограничениях

         p₁x₁ + p₂x₂ + …+ p_nx_n = p

        x   ≥ 0

где CX – скалярное произведение векторов С = (с₁,с₂,…,с_n) и

X = (x₁,x₂,…,x_n),  векторы

 

 

          α₁₁                      α₁₁                     α_1n                b₁

P₁ =   α₁₁ ,    P₂ =  α₁₁   ,  P₁=   α_2n        , P₁=   b₁

                 …               …                …                  …

          α₁₁                     α₁₁               α_mn                        b₁

  состоят соответственно из коэффициентов при переменных и свободных членов. Векторное неравенство  x ≥ 0 означает, что все компоненты вектора неотрицательны, т.е.  x _j≥ 0, j = 1,2,…,n.                        

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

Х₁=(x₁, x₂,…, x_n) и   Х₂=(x₁, x₂,…, x_n) – два допустимых решения задачи, заданной в матричной форме. Тогда  АХ₁ = В и  АХ₂=В

     Рассмотрим выпуклую линейную комбинацию решений Х₁  и Х₂, т.е.  х = α₁х₁ + α₂х₂   при  α₁≥0,  α₂ ≥0  и  α₁ + α₂ = 1 и покажем, что она также является допустимым решением системы самом деле

AX = A(α₁х₁+ α₂х₂) = α₁AX₁ + (1 — α₁) AX₂ = α₁B + (1 — α₁)B = B, т.е. решение Х  удовлетворяет систему. Но так как х₁≥0,  х₂ ≥0  ,  α₁ ≥0,

Α₂ ≥0, то и х ≥0, т.е решение   Х  удовлетворяет и условно. Итак, доказано, что множество всех допустимых решений задачи линейного программирования выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которое в дальнейшем будет называть одним термином – многогранником решений. Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме. В этом разложении среди значений

 F(x_j)(j = 1,2,…,p) выберем максимальную. Пусть оно соответствует угловой точке    x_к (1≤ k ≤ p); обозначим его через M , т.е. F(x_к) = М.

Заменим в выражении каждое значение этим максимальным значением М. тогда, учитывая, что α_j ≥0, Σ α_j = 1,

F(x*) ≤ α₁M + α₂M + …+ α_pM  = M Σ α_j =M.  Под  предположению оптимальное решение, поэтому, с одной стороны, F(x*)≥ F(x_к) = М,

то с другой стороны, доказано, что F(x*)≤ М, следовательно,

F(x*) = М = F(x_к), где  x_к – угловая точка.  Итак, существует угловая точка x_к , линейная функция принимает  максимальное значение более  чем в одной угловой точке, например, в точках

 X₁, X₂,…,X_q 1≤ q ≤p ; F(X₁,) = F(X₂) = …= F(X_q) = M.

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е

F(X) = F(α,X₁ + α₂X₂ + …+ α_qX_q) = α₁F(X₁) + α₂F(X₂) + …+ α_q F(X_q) = = α₁M + α₂M + …+ α_qM = MΣα_j = M,

т.е. линейная функция. F принимает максимальное значение в произвольной точке Х, является выпуклой линейной комбинацией угловых точек Х₁,Х₂,…,Х_q.

Каждому допустимому базисному  решению задачи линейного программирования соответствует  угловая точке многогранника решений соответствует допустимое базисное решение.

 

 

 

 

      Пусть Х₁=(x₁, x₂,…, x_m ;0,0,…,0) – допустимое базисное решение системных ограничений задачи, в котором первые m компонент – основные переменные, а остальные n – m компонент – не основанные переменные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х – угловая точка многогранника решений. Предположим противное, т.е. что Х не является угловой точкой. Точку Х можно представить  внутренней точкой отрезка, соединяющего две различные не совпадающие с  Х, точки

                   Х₁=(x₁, x₂,…, x_m ;0,0,…,0) и

                   Х₂=(x₁, x₂,…, x_m ;0,0,…,0)

другими  словами, — выпуклой линейной комбинацией точек x₁ и x₂ многогранника решений, т.е

                   X = α₁ X₁ + α₂ X₂

где α₁≥0, α₂≥0, α₁ + α₂ = 1 (полагаем, что α₁ = 0, α₂ = 0, ибо в противном случае точка Х  совпадает с точкой X₁  или X₂)

Запишим векторное равенство в координатной форме:

 

                 Х₁ =  α₁ X₁ + α₂ X₂,

                  ……………………..

                Х₁ =  α₁ X_m + α₂ X_m,

                0 = α₁ X_m+1 + α₂ X_m+1,

                ………………………

                0 = α₁ X_n + α₂ X_n

Поскольку  x_j≥0,  x_j≥0 (j = 1,2,…,n),  x₁>0, x₂>0, то из последних n – m  равенств следует, что X_m+1 = 0,…, X_n = 0, X_n = 0, т.е. в решениях x₁, x₂  и  х  система уравнений значения n – m компонент равны в данном случае нулю. Эти компоненты можно считать значениями не основных переменных. Но значения не основных переменных однозначно определяют  значения основных, следовательно,

x₁= x₁ = x₁,…, x_m = x_m = x₂. Таким образом, все n  компонент в решениях  х, x₁ и x₂  совпадают, и значит, точки x₁  и x₂ сливаются, что противоречит допущению.  Следовательно, х – угловая точка многогранника решений. Докажем обратное утверждение. Пусть

Х =(x₁, x₂,…, x_m ;0,0,…,0) угловая  точка многогранника решений и первые ее m  координат  положительны.  Покажем, что х – допустимое базисное решение. Если векторы P₁, P₂,…, P_m  линейно независимы, то ранг r матрицы А,  составленной из компонент этих векторов, равен  m, т.е. определить |А| ≠ 0, следовательно, переменные x₁, x₂,…, x_m является основными, и  решение

Х =(x₁, x₂,…, x_m ;0,0,…,0) – базисное, допустимое, т.е. утверждение доказано.

 

     Предположим противное, т.е. векторы P₁, P₂,…, P_m  линейно зависимы, тогда в равенстве  α₁ P₁ + α_m P_m +…+ α_n P_n = 0

Хотя бы один из коэффициентов α₁,…, α_m,…, α_n  отличен от нуля. умножим почтенно равенство на множитель μ >0

                   μ α₁ P₁ + …+ μ α_m P_m +…+ μ α_n P_n = 0

 

подставив координаты угловой точки  Х  многогранника решений в системе ограничений, получим

                   р₁ х₁ + …+  р_m х_m +…+  р_n х_n = 0

 

Равенство  почтенно сложим с равенством, а затем вычтем его из равенства. Получим

                   P₁ (х₁ + μ α₁) +  P_m (х_m + μ α_m ) + P_n (х_n + μ α_m )= P

                   P₁ (х₁ — μ α₁) +  P_m (х_m — μ α_m ) + P_n (х_n — μ α_m )= P

 

Сравнивая полученные равенства с равенством, заключаем, что при любом μ система ограничений удовлетворяет решения

 

                 х₁ = (х₁ + μ α₁,…, х_m + μ α_m; 0,0,…,0)

                 х₂ = (х₁ — μ α₁,…, х_m — μ α_m; 0,0,…,0)

 

Поскольку x_j≥0 (j = 1,2,…,n), то можно подобрать μ настолько малым, что все компоненты решений  х₁  и х₂  будут неотрицательны.

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

 

½( х₁ + х₂) = (х₁ ,х₂,… х_m; 0,0,…,0) = x,  т.е.векторы   Р₁ , Р₂ ,…, Р_m  линейно независимы  и   x – допустимое базисное решение задачи. Из этого непосредственно вытекает важное следствие. Если задача линейного программирования имеет оптимальное решение, то оно совпадают, по крайней мере, с одним из ее допустимым базисных решений. Итак, оптимизм линейной функции задачи линейного программирования следует искать среди конечного числа и допустимых базисных решений.

 

 

 

 

 

 

 

 

 

         Выпуклое множества точек определения как множество, которое вместе с любыми своими двумя точками содержит весь отрезок, их соединяющий. Однако в случае  n  переменных не ясно, что следует понимать под «отрезком» в n – мерном пространстве.  Очевидно, надо дать аналитическое определение этого понятия. Начнем с  n = 2 (двумерного пространства, плоскости). Пусть

x₁ = (x₁, x₂)  и  x₂ = (x₁, x₂) – точки плоскости  0_x·1X₂ а x = (x₁, x₂) – любая точка отрезка   x₁x₂. Очевидно, что отношение  α длин отрезков xx₂  и  x₁x₂  удовлетворяет  условию  0 ≤ α ≤ 1.  Запишем это отношение α через координаты точек.

   Получим

 

                           α = x₁ — x₁/ x₁ — x₁ = x₂ – x₂/ x₂ – x₂

откуда

 

                           x₁ = α x ₍₁₎ + (1 – α) x₁,

                           x₂ = α x ₂ + (1 – α) x₂

где                    

                           0 ≤ α ≤ 1

Пологая 

                           α₁ = α    и   α₂ = 1 – α, условия примут вид

                         

                         x₁ = α₁x ₁ + α₂x₁ ,

                         x₂ = α₁x ₂ + α₂x₂ ,

 

                     α₁ ≥0,  α ≥0, α₁ + α₂ = 1

понимая, что в нем все операции выполняются покоординатное

 (т.е. отдельно по переменной x₁ и  отдельно по переменной x₂). Таким образом, отрезок  x₁x₂  можно определить как множество  точек, удовлетворяющих условиям. В случае n – мерного  пространства определение отрезка будет таким же – множества точек, удовлетворяющих условиям если под x₁  и x₂  подразумевать  точки n – мерного пространства.

          x₁ = (x₁, x₂,…, x_n)   и     x₂ = (x₁, x₂,…, x_n)

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

 

 

 

 

 

 

 

        Точка Х называется выпуклой линейной комбинацией точек   x₁, x₂,…, x_n, если выполнения условия

           x = α₁x ₁ + α₂x₂ +…+  α_nx_n-n

          α_j ≥ 0 (j = 1,2,…,n), Σ α_j = 1

Так, например, выражение  (1/6) x ₁ + (1/2) x ₂ + ( 1/3) x ₃ есть выпуклая линейная комбинация точек   x ₁, x ₂, x ₃, а выражения  

(1/3) x ₁ + (1/2) x ₂ + ( 1/3) x ₃ или (1/3) x ₁ — (1/2) x ₂ + ( 7/6) x ₃ является линии, но не выпукление комбинации тех точек (в первом 1/3 + ½ + 1/3 ≠ 1, а  во втором α₂ = — 1/2  > 0).

Очевидно, что в частном случае при  n = 2  выпуклой линейной комбинацией двух точек  является соединяющий  их отрезок. По этому множество точек является выпуклым, если оно вместе с любыми своими двумя точками содержит их произвольную выпуклую линейную комбинацию. Рассмотрим теорему о представлении  выпуклого многогранника.

   Теорема.  Выпуклый n – мерный многогранник является  выпуклой линейной комбинацией своих угловых точек.

Возьмем для простоты  n = 2,  а в качестве многогранника треугольник   x₁ x₂ x₃. Через произвольную точку  Х лежит на этом отрезке, то

         Х = α₁x ₁ + α₄x₄,

         α₁ ≥ 0, α₂ ≥ 0, α₁ + α₄ =1

 

 Точка  x₄  лежит на отрезке   x₂x₃,  следовательно, x₄ = α₂x ₂ + α₃x ₃ где  α₂≥ 0, α₂ + α₃ =1

 

         X = α₁x ₁ + α₄(α₂x ₂ + αx ₃ = α₁x ₁ + α₂ α ₄ x ₂ + α₃ α₄ x .

 

Обозначим  t₁ = α₁, t₂ = α₂ α₄, t₃ = α ₃ α₄,  получим окончательно

 

        X = t ₁x ₁ + t ₂x ₂ + t ₃x ₃ ,

где

         t ₁  ≥0, t ₂  ≥0, t ₃ ≥0  и     t ₁+ t ₂+ t ₃ = 1

 

                                                        х₂

                                                        

                                                                  х           

                                              х

 

                        х                                                  х₃

 

 

 

 

 

 

    Таким образом точка Х  есть выпуклая линейная комбинация угловая точек  треугольника   Х₁Х₂Х₃. Из теоремы следует что выпуклой многогранник порождается своими угловыми точками или вершинами: отрезок – двумя точками, треугольник – тремя, тетраэдр – четырьмя точками множеством, не определяется однозначно своими условиями точками; любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

       Рассмотрим  основную задачу линейного программирования в стандартной форме с двумя переменными. К какой форме может быть сведена и каноническая задача, когда число переменных n  больше числа уравнений   m  на  2, т.е   n –m = 2.  Рассмотрим так  называемую линию уровня линейной функции F, т.е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение   α ,  т.е  F = α,

или

                    с₁х₁ + с₂х₂ = α

линии уровня широко используется, например, на картах прогнозы погоды, где извилистые линии – так называемые изо термы есть не что иное, как линии уровня температуры Т = с.  Еще более простым примером линий уровня является параллель не географический карте. Это линии уровня широты. Предположим, надо найти самую северную точку какой – либо области, например страны или материка. Это будет точка, через которую проходит параллель с самой большой широтой. Именно так и надо поступать при геометрическом решении задач линейного программирования. На многоугольное решение следует найти точку, через которую проходит линия уровня функции F  с наибольшим или наименьшим уровнем. Уравнение линии уровня функции есть уравнение прямой линии. При различных уровнях    α   линии уровня параллельны, так как их угловые коэффициенты определения только соотношением между коэффициентами с₁  и  с₂  и следовательно, равны. Таким образом, линии уровня функции  F – это своеобразные «параллели», расположенное обычно под углом к осям координат. Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении, в другую сторону – только убывает.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

        Дана система линейного уравнения

 

    α₁х₁ + α ₁₂х₂ + …+ α _1nх_n = b₁

    α ₂₁х₁ + α ₂₂х₂ + …+ α _2nх_n = b₂

     _{……………………………………………………}

   α₁х₁ + α ₁₂х₂ + …+ α _1nх_n = b₁

   α _m1х₁ + α _m2х₂ + …+ α _mnх_n = b_m

 

В матрице  А  этой системы выберем отличий от нуля элемент α_pq.  Этот элемент будет называется разрешающим элементом, р – й столбец разрешающий столбец, а  q – я строка – разрешающая строка.

Рассмотрим  новую систему уравнений

 

    α₁х₁ + α ₁₂х₂ + …+ α _1n х_n = b₁

    α ₂₁х₁ + α ₂₂х₂ + …+ α _2n х_n = b₂

        _{……………………………………………………}

     α₁х₁ + α ₁₂х₂ + …+ α _1nх_n = b₁

     α _m1х₁ + α _m2х₂ + …+ α _mnх_n = b_m

с матрицей А  коэффициенты и свободные члены которой определяется по формулам.

 

          α_{ij =} α_ij — α_ip· α_qj / α_qp

                                                                            , i≠q

          b_i = b_i  — α_ip∙ b_q / α_qp

 

в частности   α_ip= 0,  если  i ≠ q. Если же   i = q,  то принимаем

 α_qj = α_qj,  b_q = b_q. Таким образом q – е  уравнение системе  и   одинаковы, а коэффициенты при х_р  во всех уравнениях система, кроме      q – го уравнения, равны  0. Следует иметь в виду, что система и одновременно совместимы или несовместимы. В случае совместности система и равносильны. Для  определения элемента

α_ij  матрицы А полезно иметь в виду  так называется «правило прямоугольника». Рассмотрим  4  элемента матрицы А: α_ij(элемент, подлежащий  преобразований) а  qр  и  элементы  α_ip и  α_qj следует из элементов  α_ij  вычесть произведение элементов α_ip  и α_qj   расположенных  в противоположных вершинах прямоугольника, деленное на разрешающих элемент   α_qp :

 

α_ij……………….α_ip

• _•
• _{………………………………•}

α_qj                       α_qp

 

 

        Аналогичным  образом можно преобразовать система, приняв за разрешающий элемент матрицы А  элемент   asr ≠ 0, s ≠ 0, r ≠ p

После этого преобразования  все коэффициенты при   х_r    кроме a_sr   будут  равны нужно. Полученная система может быть слова преобразовано. Если    r = n,  то после ряда преобразований придем к системе уравнений вида:

 

                        к₁ x ₁ = l₁,

                        к₂ x ₂ = l₂,

                       …………

                       к_n x _n = l_n

 

из которой находятся значения неизвестных. Описанный способ решения, основанной на последовательном исключении неизвестных, называется способом   Жордана – Гаусса.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Каракулов А.К., “Математическое моделирование”, — Алматы :

    изд. КазАТК им. М. Тынышпаева, 2005 год.

2. Ташев А.А., “Информационные системы”, — Алматы:

      изд. КазАТК им. М. Тынышпаева, 2005 год.