Решение СЛАУ на примере распределения транспортных расходов.

Метод простых итераций

Приводим матрицу к диагональному виду, как и в методе Гаусса. В нашем примере матрица и так уже отсортирована как надо.

Для каждой строки матрицы элемент Хnна диагонали меняем местами со свободным членом, меняя и знак.

Уравнения будут выглядеть так:

А) 1600 + 0 * Б + 0 * В + 20 * Г       = 120 * А

Б) 20 * А + 2300 + 0 * В + 0 * Г       = 170 * Б

В) 0 * А + 40 * Б + 2600 - 105 * Г    = 55 * В

Г) 0 * А + 0 * Б + 50 * В + 3100      = 140 * Г

.. и разделим каждое уравнение на коэффициент в правой части уравнений:

А) 13,33 + 0 *Б + 0 * В + 0,17 * Г       = А

Б) 0,12 *А + 13,53 + 0 * В + 0 * Г       = Б

В) 0 * А + 0,73 * Б + 47,27 - 1,91 * Г  = В

Г) 0 * А + 0 * Б + 0,36 * В + 22,14      = Г

Проще говоря, мы разрешили каждое уравнение (n) относительно Хn.

Матрица примет вид:

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

О итерация - Подставляем в каждое уравнение значение неизвестных (А,Б,В,Г) равными 0, получаем первое решение

1 итерация – подставляем в каждое уравнение значение неизвестных (А,Б,В,Г), рассчитанные на предыдущей итерации
                  - рассчитываем погрешности для каждого неизвестного вычитанием текущего решения из предыдущего.
                  - сравниваем максимальное значение погрешности с заданной точностью. Если погрешность меньше, тогда решение найдено.

И так далее, пока не будет найдено решение.

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

Результат метода итераций такой:

А = 18,2243072542

Б = 15,6734479099

В = 20,1683619754

Г = 29,3458435562

Код метода такой:

  Функция РешитьМетодомИтераций(Матрица)

       Если Матрица=НеопределеноТогда

             Возврат Неопределено;

       КонецЕсли;

       Если Точность= 0 Тогда

             Сообщить("Не указана точность вычислений.");

             Возврат Неопределено;

       КонецЕсли;

       КоличествоСтрок=Матрица.Количество();

       КоличествоСтолбцов=Матрица[0].Количество();

       Решение=Новый Массив(КоличествоСтрок);

       // отсортируем матрицу так, чтобы по диагонали располагались наибольшие по модулю значения

       Для Стр= 0 По КоличествоСтрок-1 Цикл

             //Поиск максимального элемента в столбце

             МаксимальныйЭлементСтолбца=Матрица[Стр][Стр];

             НомерСтрокиМаксЭлемента=Стр;

             Для ПодСтр=СтрПоКоличествоСтрок-1 Цикл

                    Если МодульЧисла(Матрица[ПодСтр][Стр])>МодульЧисла(МаксимальныйЭлементСтолбца) Тогда

                           МаксимальныйЭлементСтолбца=Матрица[ПодСтр][Стр];

                           НомерСтрокиМаксЭлемента=ПодСтр;

                    КонецЕсли;

             КонецЦикла;

             //Система не разрешима если максимальный элемент равен нулю

             Если МаксимальныйЭлементСтолбца= 0 Тогда

                    Возврат Неопределено;

             КонецЕсли;

             //Меняем текущую строку со строкой с максимальным элементом

             Если НомерСтрокиМаксЭлемента<>Стр Тогда

                    Для Стб= 0 По КоличествоСтолбцов-1 Цикл

                           Буфер=Матрица[Стр][Стб];

                           Матрица[Стр][Стб]=Матрица[НомерСтрокиМаксЭлемента][Стб];

                           Матрица[НомерСтрокиМаксЭлемента][Стб]=Буфер;

                    КонецЦикла;

             КонецЕсли;

       КонецЦикла;

// например, матрица стала такой:

//     x1       x2     x3     x4     Св Чл

//     -120     0      0      20     -1600 // уравнение для х1

//     20     -170    0       0      -2300 // уравнение для х2

//     0        40    -160    0      -2600 // уравнение для х3

//     0        0        50   -140   -3100 // уравнение для х4

       //Разрешим каждое уравнение относительно Хn

       Для Стр= 0 поКоличествоСтрок- 1 Цикл

             // Меняем местами коэффициент аргумента Хn и свободный член, одновременно меняя знак.

             // Как при перестановке члена уравнения за знак "="

             Буфер=-Матрица[Стр][Стр];

             Матрица[Стр][Стр]=-Матрица[Стр][КоличествоСтолбцов-1];

             Матрица[Стр][КоличествоСтолбцов-1]=Буфер;

             // разделим строку на коэффициент аргумента Хn, т.е на значение в буфере

             Для Кол= 0 поКоличествоСтолбцов- 1 Цикл

                    Матрица[Стр][Кол]=Матрица[Стр][Кол]/Буфер;

             КонецЦикла;

       КонецЦикла;

// Матрица из примера примет вид:

//     x1           x2           x3        x4       Св Чл

//     13,333      0           0         0,167     1            // уравнение для х1

//     0,118    13,529      0            0         1            // уравнение для х2

//     0           0,727    47,273   -1,909     1            // уравнение для х3

//     0           0          0,357      22,143    1            // уравнение для х4

/ колонки: от 0 до КоличествоСтрок матрицы - для значений вычисленных Х

// колонки: + КоличествоСтрок матрицы - для значений погрешностей П

// еще одна колонка для мычисления максимального значения погрешности в строке

       МассивРешений=НовыйМассив();

    // добавим нулевое решение

       СтрокаРешения=Новый Массив(КоличествоСтрок+КоличествоСтрок+ 1);

       Для Инд= 0 поСтрокаРешения.ВГраница() Цикл

             СтрокаРешения[Инд]= 0;

       КонецЦикла;

       МассивРешений.Добавить(СтрокаРешения);

       ВсегоРешений=МассивРешений.Количество();

       РешениеЕсть=Ложь;

       Пока не РешениеЕсть Цикл

             ПредыдущееРешение=МассивРешений[ВсегоРешений-1];

             // добавим новую строку решения

             СтрокаРешения=Новый Массив(КоличествоСтрок+КоличествоСтрок+ 1);

             СтрокаПогрещностей="";

             Для Инд= 0 поКоличествоСтолбцов- 2 Цикл

                    // найдем уравнение матрицы, соответствующее решаемому аргументу Х

                    УравнениеМатрицы=Матрица[Инд];

                    РешениеХ= 0;

                    //Обойдем все колонки уравнения и сложим, перемножив на значения Х из предыдущего решения

                    Для Кол= 0 поКоличествоСтолбцов- 2 Цикл

                           Если Кол=Инд Тогда

                                  РешениеХ=РешениеХ+УравнениеМатрицы[Кол];

                           Иначе

                                  РешениеХ=РешениеХ+УравнениеМатрицы[Кол]*ПредыдущееРешение[Кол];

                           КонецЕсли;

                    КонецЦикла;

                    СтрокаРешения[Инд]=РешениеХ;

                    // рассчитаем когрешности

                    ИндПогрешности=КоличествоСтолбцов-1 +Инд;

                    СтрокаРешения[ИндПогрешности]=РешениеХ-ПредыдущееРешение[Инд];

                    СтрокаПогрещностей=СтрокаПогрещностей+Строка(Формат(СтрокаРешения[ИндПогрешности],"ЧРД=.; ЧГ=0"))+",";

             КонецЦикла;

                    // добавим решение в массив решений

                    МассивРешений.Добавить(СтрокаРешения);

                    ВсегоРешений=ВсегоРешений+ 1;

                    // определим, найдено ли решение

                    СтрокаПогрещностей=СтрокаПогрещностей+"0";

                    ПогрешностьРешения= 0;

                    Выполнить("ПогрешностьРешения = Макс("+СтрокаПогрещностей+");");

                    Если ПогрешностьРешения= 0 Тогда

                           Прервать;

                    КонецЕсли;

                    СтрокаРешения[КоличествоСтрок+КоличествоСтрок]=ПогрешностьРешения;   

                    РешениеЕсть=ПогрешностьРешения<Точность;

       КонецЦикла;

       КоличествоИтераций=ВсегоРешений- 1;// исключили нулевое решение

       Для Стр= 0 поКоличествоСтолбцов-2 Цикл

             Решение[Стр]=СтрокаРешения[Стр];

       КонецЦикла;

       Возврат Решение;

КонецФункции// РешитьМетодомИтераций()

Сравним решения СЛАУ

  Как видно из результатов вычислений разными методами, решения расходятся, начиная с 7 знака после запятой. В контексте решаемой задачи 6 знаков после запятой будет более чем достаточно.

4. Подставляем в таблицу движений полученные значения.

На последнем шаге решения задачи умножим количества операций на рассчитанные «суммы ТР на единицу» и получим сумму движений.

 Задача решена

 Во вложении обработка, в которой я реализовал сравнение двух методов решения СЛАУ на примере массива 4 х 5

Полезные ссылки

 Метод Гаусса

Метод простых итераций

Благодарности.

Sitkovskiy Konstantin - за функцию решения СЛАУ по методу Гаусса