Параллельное программирование



              

О применении схемы Гаусса решения систем линейных уравнений в транспортной задаче


Остался неясным вопрос: приходится ли в общем случае при решении систем линейных уравнений для данной задачи пользоваться схемой Гаусса, или достаточно последовательно пользоваться простыми подстановками?

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

Тогда выясним, существует ли комбинация нулей, такая, при которой в каждой строке A, с учетом неисключенной строки, остается не менее двух единиц.

Рассмотрим только n = 4 последних уравнений из (5.6): три последних уравнения из (5.7) и уравнение y4 + y8 + y12 = 7. Их матрица имеет вид

 \begin{array}{|c|c |c |c |c |c |c |c |c |c |c |c|} \hline \colorbox[gray]{0.8}1 & & & & 1& & & & 1& & & \\ \hline & 1& & & & \colorbox[gray]{0.8}1& & & & 1& & \\ \hline & & 1& & & & 1& & & &\colorbox[gray]{0.8}1 & \\ \hline & & & \colorbox[gray]{0.8}1& & & & 1& & & &1 \\ \hline \end{array}

Т.е. она состоит из m матриц с единицами по главной диагонали. Чтобы в одной строке такой матрицы остались хотя бы две единицы, необходимо оставить невычеркнутыми хотя бы два столбца. В другой строке должны быть не вычеркнуты хотя бы два обязательно других столбца. Итого, для четырех строк примера должны остаться невычеркнутыми восемь различных столбцов. Значит, вычеркнуть мы можем только четыре столбца (например, как выделено на изображении матрицы), а нам надо положить равными нулю шесть переменных! Тем самым, на базе лишь этих "нижних" уравнений образуются не менее двух уравнений с единственной переменной в левой части.

Т.к. произведение m ? n растет значительно быстрее суммы m + n, то с ростом параметров задачи указанное свойство усугубляется. Следовательно, мы с полным основанием может рассчитывать на принцип подстановки, как мы и делали в примере.

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

Например, система (5.17) при реализации схемы Гаусса проходит следующие стадии преобразования.




Содержание  Назад  Вперед