54. Вырожденное распределение в транспортных задачах; избавление от вырожденности. Вычеркиваемая комбинация.

Решение называется вырожденным, если число перевозок в транспортной таблице меньше, чём (m + n — 1). Данную проблему можно разрешить, проставив в независимые клетки очень маленькие, по сути равные нулю объемы перевозок. Число перевозок увеличивается таким образом до (m + n - 1).

Транспортная задача является вырожденной и невырожденной. Вырожденной является такая задача, в которой количество клеток в плане меньше m+n-1, где m - количество поставщиков, n – количество потребителей. Избавление от вырожденности: от случайно размещаемых нулевых клеток в плане до перебора по очереди всех пустых клеток.

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

Пусть в строке i находится клеток, не считая нулевой. Посмотрим, что определяют эти уравнения. Если строка i в процессе занесения в план клетки (i, j) обнуляется, а столбец j – нет, то этим уравнением определяется переменная и ( – 1) переменных u, кроме, естественно, переменной , которая определится, когда обнулится столбец j. Если столбец обнуляется вместе со строкой, то определяется переменных v, а добавление нулевой ячейки определяется переменная (не забываем, что в последней заполненной строке нет нулевой клетки). Теперь посчитаем уравнения и переменные. Поскольку все столбцы в процессе составления плана обнулены, то сумма равна общему количеству столбцов, то есть m. Поскольку при обнулении каждой строки (кроме последней) определяется одна переменная , то при обнулении всех строк мы определили n‑1 переменных. Общее количество определенных переменных составляет m + (n‑1).

55.Теорема оптимальности транспортной задачи.

Если для некоторого распределения транспортной задачи выполняется условия:

А) + = – для занятых клеток;

Б) + ≤ – для свободных клеток, то данное распределение является оптимальным.

Величины u(i) называют потенциалами строк, а величины - потенциалами столбцов.

56.Потенциалы и способ их расчета.

Для нахождения потенциалов строк и столбцов пользуются рассуждениями исходя из теоремы оптимальности. Количество уравнений, исходя из этого условия равняется m+m-1,а количество неизвестных и равняется m+n.Таким образом, количество переменных больше количества уравнений, причем, все уравнения линейно независимы. Решение такой системы линейных уравнений являются неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. На практике =0.Получается система из m+n-1 уравнений с m+n-1 неизвестными переменными. Эту систему можно решить любым методом и получить определенное решение. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один из потенциалов известен, и, исходя из условия теоремы оптимальности, вычисляются значения остальных неизвестных потенциалов.