Грузовые автомобильные перевозки (Часть 3)
Полученная система уравнений (8.35) является линейно зависимой, так как любое ее уравнение можно представить в виде линейной комбинации остальных уравнений. Действительно, если из суммы уравнений /, 2, 3 вычесть сумму уравнений 4, 5, 6, то получим уравнение 7 и т. д. Число линейно независимых уравнений должно быть меньше на одно общего числа уравнений в системе, т. е. базис системы должен быть равен коли-
честву уравнений в системе ограничений за вычетом единицы. Так как общее число уравнений в системе определяется суммой поставщиков и потребителей, то в базисе должно быть уравнений
Для решения транспортной задачи методом потенциалов составляется базисный план, который заносится в таблицу, называемую матрицей распределительного метода.
Матрица - прямоугольная таблица чисел, состоящая из т строк и и столбцов, в которой на пересечении строк и столбцов, обычно в правых верхних углах, указывается расстояние между данным поставщиком и потребителем (в общем случае указывается показатель целевой функции).
К базисному плану предъявляются следующие требования: он
должен быть допустимым, содержать т + п-1 загруженных клеток, чтобы загруженные клетки были расположены в порядке вычеркиваемой комбинации. Для сокращения числа итераций при последующем решении желательно, чтобы базисный план был, возможно, ближе к оптимальному.
Напомним, что план считается допустимым, если все возможности поставщиков используются, а спрос всех потребителей удовлетворяется. Однако для решения транспортной задачи методом потенциалов (или любым другим методом линейного программирования) необходимо, чтобы матрица имела определенное число загруженных клеток и чтобы загруженные клетки были расположены в порядке вычеркиваемой комбинации.
Число неизвестных х в задаче равно произведению числа строк т на число столбцов п. Максимальное число уравнений, которое можно получить при решении транспортной задачи, определяется суммой поставщиков и потребителей, т. е. т + п.В этом случае, как показано выше, система уравнений является линейно зависимой. Для решения транспортной задачи базис системы должен содержать т + п -1 уравнений, а следовательно, в матрице должно быть т + п-1 загруженных клеток.