О применении схемы Гаусса решения систем линейных уравнений в транспортной задаче
Остался неясным вопрос: приходится ли в общем случае при решении систем линейных уравнений для данной задачи пользоваться схемой Гаусса, или достаточно последовательно пользоваться простыми подстановками?
Подстановки мы легко выполняли в том случае, если в результате введения нулевых комбинаций у нас получались уравнения, содержащие в левой части единственную переменную. Если таких уравнений нет, то очевидна целесообразность применения схемы Гаусса.
Тогда выясним, существует ли комбинация нулей, такая, при которой в каждой строке A, с учетом неисключенной строки, остается не менее двух единиц.
Рассмотрим только n = 4 последних уравнений из (5.6): три последних уравнения из (5.7) и уравнение y4 + y8 + y12 = 7. Их матрица имеет вид
Т.е. она состоит из m матриц с единицами по главной диагонали. Чтобы в одной строке такой матрицы остались хотя бы две единицы, необходимо оставить невычеркнутыми хотя бы два столбца. В другой строке должны быть не вычеркнуты хотя бы два обязательно других столбца. Итого, для четырех строк примера должны остаться невычеркнутыми восемь различных столбцов. Значит, вычеркнуть мы можем только четыре столбца (например, как выделено на изображении матрицы), а нам надо положить равными нулю шесть переменных! Тем самым, на базе лишь этих "нижних" уравнений образуются не менее двух уравнений с единственной переменной в левой части.
Т.к. произведение m ? n растет значительно быстрее суммы m + n, то с ростом параметров задачи указанное свойство усугубляется. Следовательно, мы с полным основанием может рассчитывать на принцип подстановки, как мы и делали в примере.
Однако программирование схемы Гаусса может оказаться не только менее трудоемко. Не следует забывать, что в процессе преобразования системы уравнений и последовательного получения значений переменных оперативно устанавливается как неразрешимость или неоднозначность, так и отрицательное решение.
Например, система (5.17) при реализации схемы Гаусса проходит следующие стадии преобразования.
Вычитание первой строки из последней и формирование разности на месте второй строки:
- Вычитание пятой строки из третьей и размещение разности на месте четвертой строки:
- Сложение шестой строки с пятой и расположение разности на месте пятой строки:
Получение нулевой строки в матрице достаточно для заключения о непригодности решения (в данном случае оно не существует).
Рассмотренная транспортная задача, без ограничения пропускной способности транспортных потоков, демонстрирует параллельный алгоритм ее решения. Программа, одинаковая для всех процессоров многопроцессорной ВС или станций локальной вычислительной сети, в основной своей части реализует выборку очередного ребра, исходящего из первоначально найденной вершины многогранника решений. Вдоль него ищется смежная вершина с меньшим значением целевой функции. Процессор, нашедший такую вершину, производит замену ранее исследовавшейся вершины и вынуждает все процессоры приступить к анализу ребер, исходящих из новой вершины. Так — до неудачного поиска вершины с меньшим значением целевой функции.
Использование в качестве источника загрузки процессоров общей уточняемой базы данных, в которой хранятся исследованные варианты поиска, позволяет выявлять еще не исследованные варианты и равномерно распределять нагрузку между процессорами.
