При условии отсутствия “0-строк” (ограничений-равенств) и “свободных” переменных (т.е. переменных, на которые не наложено требование неотрицательности).
2. В случае присутствия ограничений-равенств и “свободных” переменных поступают следующим образом.
Выбирают разрешающий элемент в “0-строке” и делают шаг модифицированного жорданова исключения, после чего вычеркивают этот разрешающий столбец. Данную последовательность действий продолжают до тех пор, пока в симплексной таблице остается хотя бы одна “0-строка” (при этом таблица сокращается).
Если же присутствуют и свободные переменные, то необходимо данные переменные сделать базисными. И после того, как свободная переменная станет базисной, в процессе определения разрешающего элемента при поиске опорного и оптимального планов данная строка не учитывается (но преобразуется).
Рассматривая
симплекс-метод, мы предполагали, что
задача линейного программирования
является невырожденной, т.е. каждый
опорный план содержит ровно
положительных компонент, где
– число ограничений в задаче. В вырожденном
опорном плане число положительных
компонент оказывается меньше числа
ограничений: некоторые базисные
переменные, соответствующие данному
опорному плану, принимают нулевые
значения. Используя геометрическую
интерпретацию для простейшего случая,
когда
(число небазисных переменных равно 2),
легко отличить вырожденную задачу от
невырожденной. В вырожденной задаче в
одной вершине многогранника условий
пересекается более двух прямых,
описываемых уравнениями вида
.
Это значит, что одна или несколько сторон
многоугольника условий стягиваются в
точку.
А
налогично
при
в вырожденной задаче в одной
вершине пересекается более 3-х плоскостей
.
В
предположении о невырожденности
задачи находилось только одно значение
,
по которому определялся индекс
выводимого из базиса вектора условий
(выводимой из числа базисных переменной).
В вырожденной задаче
может достигаться на нескольких индексах
сразу (для нескольких строк). В этом
случае в находимом опорном плане
несколько базисных переменных будут
нулевыми.
Если задача линейного программирования оказывается вырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана. Так называемое, явление зацикливания. Хотя в практических задачах линейного программирования зацикливание явление крайне редкое, возможность его не исключена.
Один
из приемов борьбы с вырожденностью
состоит в преобразовании задачи путем
“незначительного” изменения вектора
правых частей системы ограничений на
величины
,
таким образом, чтобы задача стала
невырожденной, и, в то же время, чтобы
это изменение не повлияло реально на
оптимальный план задачи.
Чаще реализуемые алгоритмы включают в себя некоторые простые правила, снижающие вероятность возникновения зацикливания или его преодоления.
Пусть
переменную
необходимо сделать базисной. Рассмотрим
множество индексов
,
состоящее из тех
,
для которых достигается
.
Множество индексов
,
для которых выполняется данное условие
обозначим через
.
Если
состоит из одного элемента, то из базиса
исключается вектор условий
(переменная
делается небазисной).
Если
состоит более чем из одного элемента,
то составляется множество
,
которое состоит из
,
на которых достигается
.
Если
состоит из одного индекса
,
то из базиса выводится переменная
.
В противном случае составляется множество
и т.д.
Практически правилом надо пользоваться, если зацикливание уже обнаружено.
В общем случае линейное уравнение имеет вид:Уравнение имеет решение: если хотя бы один из коэффициентов при неизвестных отличен от нуля. В этом случае любой -мерный вектор называется решением уравнения, если при подстановке его координат уравнение обращается в тождество.
Дать характеристику системе уравнений .
Решение :
1. Входит ли в состав противоречивое уравнение? (Если коэффициенты, в этом случае уравнение имеет вид: и называется противоречивым .)
2. Найти все разрешенные переменные . (Неизвестная называется разрешенной для системы уравнений, если она входит в одно из уравнений системы с коэффициентом +1, а в остальные уравнения не входит (т.е. входит с коэффициентом, равным нулю).
3. Является ли система уравнений разрешенной? (Система уравнений называется разрешенной , если каждое уравнение системы содержит разрешенную неизвестную, среди которых нет совпадающих)
В общем случае разрешенная система уравнений имеет вид:Разрешенные неизвестные, взятые по одному из каждого уравнения системы, образуют полный набор разрешенных неизвестных системы. (в нашем примере это )
Разрешенные неизвестные, входящие в полный набор, называют также базисными (), а не входящие в набор — свободными ().
На данном этапе главное понять что такое разрешенная неизвестная (входящая в базис и свободная).
Общим решением разрешенной системы уравнений называется совокупность выражений разрешенных неизвестных через свободные члены и свободные неизвестные:
Частным решением называется решение, получающиеся из общего при конкретных значениях свободных переменных и неизвестных.
Базисным решением называется частное решение, получающееся из общего при нулевых значениях свободных переменных.
Пример 1. Найти общее, базисное и какое-либо частное решение системы уравнений:Теорема (1)
Разрешенная система уравнений всегда совместна (потому что она имеет хотя бы одно решение); причем если система не имеет свободных неизвестных, (то есть в системе уравнений все разрешенные входят в базис) то она определена (имеет единственное решение); если же имеется хотя бы одна свободная переменная, то система не определена (имеет бесконечное множество решений).
Решение :
1. Проверяем является ли система разрешенной?
2. Включаем в набор разрешенные неизвестные — по одному из каждого уравнения .
3. Записываем общее решение в зависимости от того какие разрешенные неизвестные мы включили в набор .
4. Находим частное решение . Для этого приравниваем свободные переменные, которые мы не включили в набор приравнять к произвольным числам.
Ответ: частное решение (один из вариантов)
5. Находим базисное решение . Для этого приравниваем свободные переменные, которые мы не включили в набор к нулю.
Системы линейных уравнений приводятся к равносильным разрешенным системам с помощью элементарных преобразований.
Теорема (2)
Если какое-либо уравнение системы умножить на некоторое отличное от нуля число , а остальные уравнения оставить без изменения, то . (то есть если умножить левую и правую часть уравнения на одно и то же число то получится уравнение, равносильное данному)
Теорема (3)
Если к какому-либо уравнению системы прибавить другое , а все остальные уравнения оставить без изменения, то получится система, равносильная данной . (то есть если сложить два уравнения (сложив их левые и правые части) то получится уравнение равносильное данным)
Следствие из Теорем (2 и 3)
Если к какому-либо уравнению прибавить другое, умноженное на некоторое число , а все остальные уравнения оставить без изменения, то получится система, равносильная данной .
Если у нас есть система уравнений и мы хотим преобразовать ее в разрешенную систему уравнений в этом нам поможет метод Жордана-Гаусса.
Преобразование Жордана с разрешающим элементом позволяет получить для системы уравнений разрешенную неизвестную в уравнении с номером . (пример 2).
Преобразование Жордана состоит из элементарных преобразований двух типов:Допустим мы хотим сделать неизвестную в нижнем уравнении разрешенной неизвестной. Для этого мы должны разделить на , так чтобы сумма .
Пример 2 Пересчитаем коэффициенты системы
При делении уравнения с номером на , его коэффициенты пересчитываются по формулам:
Чтобы исключить из уравнения с номером , нужно уравнение с номером умножить на и прибавить к этому уравнению.
Теорема (4) О сокращении числа уравнений системы.
Если система уравнений содержит тривиальное уравнение, то его можно исключить из системы, при этом получится система равносильная исходной.
Теорема (5) О несовместимости системы уравнений.
Если система уравнений содержит противоречивое уравнение, то она несовместна.
Алгоритм решения систем уравнений методом Жордана-Гаусса состоит из ряда однотипных шагов, на каждом из которых производятся действия в следующем порядке:
Найти : два общих и два соответствующих базисных решения
Решение :
Вычисления приведены в нижеследующей таблице:
Справа от таблицы изображены действия над уравнениями. Стрелками показано к какому уравнению прибавляется уравнение с разрешающим элементом, умноженное на подходящий множитель.
В первых трех строках таблицы помещены коэффициенты при неизвестных и правые части исходной системы. Результаты первого преобразования Жордана с разрешающим элементом равным единице приведены в строках 4, 5, 6. Результаты второго преобразования Жордана с разрешающим элементом равным (-1) приведены в строках 7, 8, 9. Так как третье уравнение является тривиальным, то его можно не учитывать.
Рассмотрим решение ЗЛП симплекс-методом и изложим ее применительно к задаче максимизации.
1. По условию задачи составляется ее математическая модель.
2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.
3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.
Симплекс таблица: вписывается система ограничительных уравнений и целевая функция в виде выражений, разрешенных относительно начального базиса. Строку, в которую вписаны коэффициенты целевой функции F, называют F-строкой или строкой целевой функции.
4. Находят начальный опорный план, производя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным отношениям, и не принимая во внимание знаки элементов F-строки. Если в ходе преобразований встретится 0-строка, все элементы которой, кроме свободного члена, нули, то система ограничительных уравнений задачи несовместна. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то система ограничительных уравнений не имеет неотрицательных решений.
Приведение системы (2.55), (2.56) к новому базису будем называть симплексным преобразованием. Если симплексное преобразование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входящими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая наоборот - из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.
5. Найденный начальный опорный план исследуется на оптимальность:
а) если в F-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;
б) если в F-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то <
в) если в F-строке есть хотя бы один отрицательный элемент, а в его столбце есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого указанный столбец надо назначить разрешающим, по минимальному симплексному отношению найти разрешающую строку и выполнить симплексное преобразование. Полученный опорный план вновь исследовать на оптимальность. Описанный процесс повторяется до получения оптимального плана либо до установления неразрешимости задачи.
Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу F-строки, мы обеспечиваем возрастание функции F.
Немного сложней определяется переменная, подлежащая исключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует, как уже установлено, положительность базисных компонент в новом опорном плане.
В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обязательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разрешающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:
1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагаем, что ограничения задачи совместны);
2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);
3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;
4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент y-строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на следующем шаге вновь обращаются к t-строке. Если задача разрешима, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.
Нахождение исходного опорного плана, канонический вид ЗЛП
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования - симплексного метода или метода последовательного улучшения плана.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение по отношению к цели задачи; до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных элемента:
Способ определения какого-либо первоначального допустимого базисного решения задачи;
Правило перехода к лучшему (точнее, не худшему) решению;
Критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
В литературе достаточно подробно описываются: нахождение начального опорного плана (первоначального допустимого базисного решения), тоже - методом искусственного базиса, нахождение оптимального опорного плана, решение задач с помощью симплексных таблиц.
58. Основная теорема симплекс метода.
???????????????????????????????????????????????????????????????????????
59. Альтернативный оптимум в ЗЛП, вырожденность в ЗЛП.
Вырожденность в задачах линейного программирования
Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно m положительных компонент, где m - число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда n - m = 2 (число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0. Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку. Аналогично при n - m = 3 в вырожденной задаче в одной вершине пересекается более 3-х плоскостей xi = 0. В предположении о невырожденности задачи
находилось только одно значение, по которому определялся индекс выводимого из базиса вектора условий (выводимой из числа базисных переменной). В
вырожденной задаче может достигаться на нескольких индексах сразу (для нескольких строк). В этом случае в находимом опорном плане несколько базисных переменных будут нулевыми. Если задача линейного программирования оказывается вырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана. Это - так называемое явление зацикливания. Хотя в практических задачах линейного программирования зацикливание явлеется довольно редким, возможность его не исключена. Один из приемов борьбы с вырожденностью состоит в преобразовании задачи путем "незначительного" изменения вектора правых частей системы ограничений на величины таким образом, чтобы задача стала невырожденной, и, в то же время, чтобы это изменение не повлияло реально на оптимальный план задачи. Чаще реализуемые алгоритмы включают в себя некоторые простые правила, снижающие вероятность возникновения зацикливания или его преодоления. Пусть переменную xj необходимо сделать базисной. Рассмотрим
множество индексов E0, состоящее из тех i, для которых достигается. Множество индексов i, для которых выполняется данное условие обозначим через E0,. Если E0, состоит из одного элемента, то из базиса исключается вектор условий Ai (переменная xi делается небазисной). Если E0 состоит более чем из одного элемента, то составляется множество E1, которое состоит из , на которых достигается . Если E1 состоит из одного индекса k, то из базиса выводится переменная xk. В противном случае составляется множество E2 и т.д. Практически правилом надо пользоваться, если зацикливание уже обнаружено.
Альтернативный оптимум в ЗЛП???????????????????????????
60. Метод искусственного базиса. М-задача. Теорема о связи между решениями исходной задачи и М-задачи.
Метод искусственного базиса.
Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:
max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.
В ограничения и в функцию цели вводят так называемые «искусственные переменные» Rj следующим образом:
∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj
При введении искусственных переменных в методе искусственного базиса в функцию цели им приписывается достаточно большой коэффициент M, который имеет смысл штрафа за введение искусственных переменных. В случае минимизации искусственные переменные прибавляются к функции цели с коэффициентом M. Введение искусственных переменных допустимо в том случае, если в процессе решения задачи они последовательно обращаются в нуль.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑cixi, а другая – для составляющей M ∑Rj Рассмотрим процедуру решения задачи на конкретном примере.
Пример 1. Найти максимум функции F(x) = -x1 + 2x2 - x3 при ограничениях:
x1≥0, x2≥0, x3≥0 .
Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи
2x1 + 3x2 + x3 + R1 = 3;
x1 + 3x3 + R2 = 2 ;
Функция цели F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).
Выразим сумму R1 + R2 из системы ограничений: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, тогда F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .
При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x1, x2 , x3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.
Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x3, которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R2 должна быть из базиса исключена. Ведущий элемент обведен контуром.
В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:
x1=0; x2=7/9; Fmax=8/9.
Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥
Условие задачи
Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.
Решение задачи симплекс М методом
1) Определение оптимального плана производства
Пусть x1, x2, x3 - количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:
F = 10·x1 + 8·x2 + 12·x3 –>max
Вводим дополнительные переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0, чтобы неравенства преобразовать в равенства.
Чтобы выбрать начальный базис, вводим искусственные переменные x8 ≥ 0, x9 ≥ 0 и очень большое число M (M –> ∞). Решаем М методом.
F = 10·x1 + 8·x2 + 12·x3 + 0·x4 + 0·x5 + 0·x6 + 0·x7– M·x8– M·x9 –>max
В качестве базиса возьмем x4 = 2000; x5 = 1000; x8 = 100; x9 = 50.
Данные заносим в симплекс таблицу
Симплекс таблица № 1
Целевая функция:
0 · 2000 + 0 · 1000 + (– M) · 100 + (– M) · 50 = – 150M
Вычисляем оценки по формуле:
Δ1 = 0 · 5 + 0 · 4 + (– M) · 1 + (– M) · 0 – 10 = – M – 10
Δ2 = 0 · 2 + 0 · 5 + (– M) · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + (– M) · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 0 + 0 · 0 + (– M) · (–1) + (– M) · 0 – 0 = M
Δ7 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · (–1) – 0 = M
Δ2 = 0 · 0 + 12 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ3 = 0 · 0 + 12 · 1 + 10 · 0 + 8 · 0 – 12 = 0
Δ4 = 0 · 1 + 12 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ5 = 0 · (–1) + 12 · 1/4 + 10 · 0 + 8 · 0 – 0 = 3
Δ6 = 0 · 1 + 12 · 1 + 10 · (–1) + 8 · 0 – 0 = 2
Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450
Ответ: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450То есть необходимо произвести x1 = 100 единиц продукции вида А, x2 = 50 единиц продукции вида Б и x3 = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит Fmax = 2450 единиц.
Теорема о связи между решениями исходной задачи и М-задачи.
???????????????????????
Метод Гаусса-Жордана предназначен для решения систем линейных алгебраических уравнений (СЛАУ). Он является модификацией метода Гаусса . Если метод Гаусса осуществляется в два этапа (прямой ход и обратный) то метод Гаусса-Жордана позволяет решить систему в один этап. Подробности и непосредственная схема применения метода Гаусса-Жордана описаны в примерах.
Во всех примерах $A$ обозначает матрицу системы, $\widetilde{A}$ - расширенную матрицу системы. О матричной форме записи СЛАУ можно прочесть .
Пример №1
Решить СЛАУ $ \left\{ \begin{aligned} & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end{aligned} \right.$ методом Гаусса-Жордана.
Давайте перейдём от последней полученной нами матрице к системе:
$$ \left\{ \begin{aligned} & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2;\\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1. \end{aligned} \right. $$
Упрощая полученную систему, имеем:
$$ \left\{ \begin{aligned} & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end{aligned} \right. $$
Полное решение без пояснений выглядит так:
Хоть этот способ выбора разрешающих элементов вполне допустим, но предпочтительнее выбирать в качестве разрешающих элементов диагональные элементы матрицы системы. Мы рассмотрим этот способ ниже.
Так как этот способ решения полностью аналогичен предыдущему (за исключением выбора разрешающих элементов), то подробные пояснения пропустим. Принцип выбора разрешающих элементов прост: в первом столбце выбираем элемент первой строки, во втором столбце берём элемент второй строки, в третьем столбце - элемент третьей строки и так далее.
Первый шаг
В первом столбце выбираем элемент первой строки, т.е. в качестве разрешающего имеем элемент 4. Понимаю, что выбор числа 2 кажется более предпочтительным, так как это число всё-таки меньше, нежели 4. Для того, чтобы число 2 в первом столбце переместилось на первое место, поменяем местами первую и вторую строки:
$$ \left(\begin{array} {ccc|c} 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end{array} \right)\rightarrow \left(\begin{array} {ccc|c} 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end{array} \right) $$
Итак, разрешающий элемент представлен числом 2. Точно так же, как и ранее, разделим первую строку на 2, а затем обнулим элементы первого столбца:
$$ \left(\begin{array} {ccc|c} 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end{array} \right) \begin{array} {l} I:2 \\\phantom{0} \\ \phantom{0} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end{array} \right) \begin{array} {l} \phantom{0} \\ II-4\cdot I\\ III+3\cdot I \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end{array} \right). $$
Второй шаг
На втором шаге требуется обнулить элементы второго столбца. В качестве разрешающего элемента выбираем элемент второй строки, т.е. 1. Разрешающий элемент уже равен единице, поэтому никаких строк менять местами не будем. Кстати сказать, если бы мы захотели поменять местами строки, то первую строку трогать не стали бы, так как она уже была использована на первом шаге. А вот вторую и третью строки запросто можно менять местами. Однако, повторюсь, в данной ситуации менять местами строки не нужно, ибо разрешающий элемент уже оптимален - он равен единице.
$$ \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end{array} \right) \begin{array} {l} I+2\cdot II \\ \phantom{0}\\ III-5\cdot II \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end{array} \right). $$
Второй шаг окончен. Переходим к третьему шагу.
Третий шаг
На третьем шаге требуется обнулить элементы третьего столбца. В качестве разрешающего элемента выбираем элемент третьей строки, т.е. 37/2. Разделим элементы третьей строки на 37/2 (чтобы разрешающий элемент стал равен 1), а затем обнулим соответствующие элементы третьего столбца:
$$ \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end{array} \right) \begin{array} {l} \phantom{0}\\ \phantom{0}\\ III:\frac{37}{2} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end{array} \right) \begin{array} {l} I+2\cdot III\\II+3/2\cdot III\\ \phantom{0} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end{array} \right). $$
Ответ получен: $x_1=-2$, $x_2=1$, $x_3=-1$. Полное решение без пояснений выглядит так:
Все остальные примеры на этой странице будут решены именно вторым способом: в качестве разрешающих будем выбирать диагональные элементы матрицы системы.
Ответ : $x_1=-2$, $x_2=1$, $x_3=-1$.
Пример №2
Решить СЛАУ $ \left\{ \begin{aligned} & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27;\\ & -3x_1-2x_2-2x_3-10x_4=1. \end{aligned} \right.$ методом Гаусса-Жордана.
Запишем расширенную матрицу данной системы : $\widetilde{A}=\left(\begin{array} {cccc|c} 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end{array} \right)$.
В качестве разрешающих элементов станем выбирать диагональные элементы матрицы системы: на первом шаге возьмём элемент первой строки, на втором шаге элемент второй строки и так далее.
Первый шаг
Нам нужно обнулить соответствующие элементы первого столбца. В качестве разрешающего элемента возьмём элемент первой строки, т.е. 3. Соответственно первую строку придётся разделить на 3, чтобы разрешающий элемент стал равен единице. А затем обнулить все элементы первого столбца, кроме разрешающего:
$$ \left(\begin{array}{cccc|c} 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end{array}\right) \begin{array} {l} I:3\\ \phantom{0}\\\phantom{0}\\\phantom{0}\end{array} \rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end{array}\right) \begin{array} {l} \phantom{0}\\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end{array} \rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end{array}\right). $$
Второй шаг
Переходим к обнулению соответствующих элементов второго столбца. В качестве разрешающего элемента мы уславливались взять элемент второй строки, но сделать этого мы не в силах, так как нужный элемент равен нулю. Вывод: будем менять местами строки. Первую строку трогать нельзя, так как она уже использовалась на первом шаге. Выбор небогат: или меняем местами вторую и третью строки, или же меняем местами четвёртую и вторую. Так как в четвёртой строке наличествует (-1), то пусть в "обмене" поучавствует именно четвёртая строка. Итак, меняем местами вторую и четвёртую строки:
$$ \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end{array}\right)\rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) $$
Вот теперь всё в норме: разрешающий элемент равен (-1). Бывает, кстати, что смена мест строк невозможна, но это обговорим в следующем примере №3. А пока что делим вторую строку на (-1), а затем обнуляем элементы второго столбца. Обратите внимание, что во втором столбце элемент, расположенный в четвёртой строке, уже равен нулю, поэтому четвёртую строку трогать не будем.
$$ \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \begin{array} {l} \phantom{0}\\II:(-1) \\\phantom{0}\\\phantom{0}\end{array} \rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \begin{array} {l} I-1/3\cdot II\\ \phantom{0} \\III-2\cdot II\\\phantom{0}\end{array} \rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end{array}\right). $$
Третий шаг
Приступаем к обработке третьего столбца. В качестве разрешающего элемента мы условились брать диагональные элементы матрицы системы. Для третьего шага это означает выбор элемента, расположенного в третьей строке. Однако если мы просто возьмём элемент 7 в качестве разрешающего, то всю третью строку придётся делить на 7. Мне кажется, что разделить на (-2) попроще. Поэтому поменяем местами третью и четвёртую строки, и тогда разрешающим элементом станет (-2):
$$ \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end{array}\right) $$
Разрешающий элемент - (-2). Делим третью строку на (-2) и обнуляем соответствующие элементы третьего столбца:
$$ \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end{array}\right) \begin{array} {l} \phantom{0}\\ \phantom{0} \\III:(-2)\\\phantom{0}\end{array}\rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end{array}\right) \begin{array} {l} I-2/3\cdot III\\ \phantom{0} \\ \phantom{0}\\IV-7\cdot III\end{array}\rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & -39\end{array}\right). $$
Четвёртый шаг
Переходим к обнулению четвёртого столбца. Разрешающий элемент расположен в четвёртой строке и равен числу $-\frac{39}{2}$.
$$ \left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & -39\end{array}\right) \begin{array} {l} \phantom{0}\\ \phantom{0} \\ \phantom{0}\\IV:\left(-\frac{39}{2}\right) \end{array}\rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end{array}\right) \begin{array} {l} I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom{0} \end{array}\rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\end{array}\right). $$
Решение окончено. Ответ таков: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Полное решение без пояснений:
Ответ : $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.
Пример №3
Решить СЛАУ $\left\{\begin{aligned} & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4+14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_4-21x_5=-9. \end{aligned}\right.$ методом Гаусса-Жордана. Если система является неопределённой, указать базисное решение.
Подобные примеры разбираются в теме "Общее и базисное решения СЛАУ" . Во второй части упомянутой темы данный пример решён с помощью метод Гаусса . Мы же решим его с помощью метода Гаусса-Жордана. Пошагово разбивать решение не станем, так как это уже было сделано в предыдущих примерах.
$$ \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end{array}\right) \begin{array} {l} \phantom{0} \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I\\ V+2\cdot I\\VI+4\cdot I \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end{array}\right) \begin{array} {l} \phantom{0} \\ II:5 \\ \phantom{0}\\ \phantom{0}\\ \phantom{0} \\ \phantom{0}\end{array} \rightarrow \\ \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end{array}\right) \begin{array} {l} I+2\cdot II \\ \phantom{0}\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right). $$
Полагаю, что одно из сделанных преобразований всё-таки требует пояснения: $IV:3$. Все элементы четвёртой строки нацело делились на три, поэтому сугубо из соображений упрощения мы разделили все элементы этой строки на три. Третья строка в преобразованной матрице стала нулевой. Вычеркнем нулевую строку:
$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right) $$
Нам пора переходить к третьему шагу, на котором должны быть обнулены элементы третьего столбца. Однако диагональный элемент (третья строка) равен нулю. И смена мест строк ничего не даст. Первую и вторую строки мы уже использовали, поэтому их трогать мы не можем. А четвёртую и пятую строки трогать нет смысла, ибо проблема равенства нулю разрешающего элемента никуда не денется.
В этой ситуации проблема решается крайне незамысловато. Мы не можем обработать третий столбец? Хорошо, перейдём к четвёртому. Может, в четвёртом столбце элемент третьей строки будет не равен нулю. Однако четвёртый столбец "болеет" той же проблемой, что и третий. Элемент третьей строки в четвёртом столбце равен нулю. И смена мест строк опять-таки ничего не даст. Четвёртый столбец тоже не можем обработать? Ладно, перейдём к пятому. А вот в пятом столбце элемент третьей строки очень даже не равен нулю. Он равен единице, что довольно-таки хорошо. Итак, разрешающий элемент в пятом столбце равен 1. Разрешающий элемент выбран, поэтому осуществим дальшейшие преобразования метода Гаусса-Жордана:
$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right) \begin{array} {l} I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom{0}\\ IV+III\\ V+2\cdot III \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \rightarrow \\ \rightarrow\left|\text{Удаляем нулевые строки}\right|\rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end{array}\right)$$
Мы привели матрицу системы и расширенную матрицу системы к ступенчатому виду. Ранги обеих матриц равны $r=3$, т.е. надо выбрать 3 базисных переменных. Количество неизвестных $n=5$, поэтому нужно выбрать $n-r=2$ свободных переменных. Так как $r < n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":
На "ступеньках" стоят элементы из столбцов №1, №2, №5. Следовательно, базисными будут переменные $x_1$, $x_2$, $x_5$. Свободными переменными, соответственно, будут $x_3$, $x_4$. Столбцы №3 и №4, соответствующие свободным переменным, перенесём за черту, при этом, конечно, не забыв сменить им знаки.
$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end{array}\right)\rightarrow \left(\begin{array}{ccc|ccc} 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end{array}\right). $$
Из последней матрицы получим общее решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5}-\frac{13}{5}x_3-\frac{4}{5}x_4;\\ & x_2=\frac{3}{5}+\frac{1}{5}x_3-\frac{2}{5}x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4. \end{aligned}\right.$. Базисное решение найдём, приняв свободные переменные равными нулю, т.е. $x_3=0$, $x_4=0$:
$$ \left\{\begin{aligned} & x_1=-\frac{99}{5};\\ & x_2=\frac{3}{5};\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end{aligned}\right. $$
Задача решена, осталось лишь записать ответ.
Ответ : Общее решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5}-\frac{13}{5}x_3-\frac{4}{5}x_4;\\ & x_2=\frac{3}{5}+\frac{1}{5}x_3-\frac{2}{5}x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4. \end{aligned}\right.$, базисное решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5};\\ & x_2=\frac{3}{5};\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end{aligned}\right.$.
Приведенные выше преобразования удобно выполнять в специальных таблицах, называемых симплекс-таблицами.
В симплекс-таблице выделяются следующие блоки:
Запишем решение задачи примера из раздела 3.3 в симплекс-таблицах:
Все исходные данные, содержащиеся в математическом условии задачи, переносятся в первую симплексную таблицу. Зануляя свободные переменные, получаем опорный план
В последнюю строку первой симплекс-таблицы заносим критерий в неявной форме
Исключаем из этого критерия базисную переменную x 4 , приводя критерий к виду
Для оптимальности решения все оценки должны быть неотрицательны
Решение не оптимальное, т.к. есть отрицательные оценки.
Оценки могут быть вычислены по формулам. Произведение представляет из себя, текущий вектор матрицы условий, тогда оценку свободной переменной можно вычислить как скалярное произведение вектора коэффициентов при базисных переменных на текущий вектор матрицы условий минус коэффициент целевой функции при этой переменной. Так, для получаем значение
Разрешающим столбцом выбираем тот, где наименьшая по величине оценка (если задача на максимум). А для выбора разрешающей строки нужно среди всех строк найти, выраженная из которой переменная, уменьшаясь, которая быстрее обращается в ноль.
В итоге, мы получаем, что разрешающий столбец - , а разрешающая строка - . Значит из списка базисных выходит переменная и входит переменная.
Решение не оптимальное, т.к. есть отрицательная оценка -2.
Решение оптимальное, т.к. все оценки больше нуля. Очевидно, что увеличить нельзя.
Правила построения симплекс-таблиц
Симплекс-таблица строится для какого-либо опорного решения.
Пусть опорное решение. Симплекс-таблица для этого решения имеет вид
Базисная матрица B = (A 1 , A 2 , … A m)
· при базисных переменных текущая матрица единичная.
· в правой нижней клетке - значение критерия
Этапы симплекс-метода
Мысленно строится четырехугольник на диагонали, соединяющей искомый элемент с разрешающим. Тогда новое значение элемента равно прежнему значению минус произведение элементов на противоположной диагонали, деленное на разрешающий элемент.
Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.
Замечание : Если в разрешающей строке был нулевой элемент, значит этот столбец не меняется; если в разрешающем столбце есть нулевой элемент, то соответствующая строка не меняется.
