Теорема. Для того, чтоб допустимый (опорный) план транспортной задачи X={ xij}, был оптимальным, необходимо и достаточно

Для того, чтоб допустимый (опорный) план транспортной задачи X={ x_ij}_, был оптимальным, необходимо и достаточно, чтобы существовала система чисел ; , удовлетворяющих условиям:

	(3.5)
	(3.6)

Соотношения (3.5) и (3.6) называются условиями потенциальности оптимального плана транспортной задачи. Набор величин приписывается строкам (первой строке - U₁, второй – U₂ и т.д.), поэтому U₁ называется потенциалом первой строки, U₂ – потенциалом второй строки и т.д. Аналогично, набор величин приписывается столбцам (первому столбцу - V₁, второму - V₂ и т.д.) и эти величины называются потенциалами соответствующих столбцов.

Алгоритм решения ТЗ методом потенциалов состоит из следующих этапов.

1. Для опорного решения рассчитывают систему потенциалов (используя соотношения (3.6)).
2. Проверка опорного решения на оптимальность – выявление нарушений (используя соотношения (3.5)).
3. Если соотношения (3.5) выполняется для всех клеток без перевозок, то опорное решение является оптимальным и процесс решения закончен. Если соотношение (3.6) не выполняется хотя бы для одной из клеток без перевозок, переходим к пункту 4.
4. Улучшаем план перевозок (получаем новое опорное решение) и переходим к пункту 1.

Расчет системы потенциалов по формуле (3.6) в пункте 1 данного алгоритма можно выполнить множеством способов. Для определения m+n неизвестных (общее число величин в системе потенциалов ; ) имеем m+n-1 уравнений (количество клеток с перевозками в опорном плане). Поэтому для построения системы потенциалов задаемся потенциалом одного из поставщиков или потребителей, а далее вычисляем потенциалы для всех остальных строк и столбцов через занятые клетки.

Соотношение (3.5), которое используется в пункте 2 данного алгоритма для проверки оптимальности решения, можно переписать в виде

(3.7)

Величины назовем невязками. Невязки вычисляются для клеток без перевозок. В любом опорном решении все переменные разбиты на две группы: x_pq – базисные переменные и x_kl – свободные переменные. Суммарная стоимость перевозок может быть выражена через свободные переменные следующим образом:

Если все величины неположительны, то опорное решение оптимально. Если хотя бы в одной клетке это условие нарушается (, т.е. существует клетка с нарушением), то план перевозок может быть улучшен.

Улучшение плана перевозок (пункт 4 данного алгоритма) заключается в построении замкнутого контура (цикла). Этот контур содержит клетку (вершина №1) с максимальным превышением (т.е. положительной невязкой), а все остальные вершины обязательно содержат перевозки. Контур может иметь различную конфигурацию, но обязательно в каждой вершине угол между сторонами равен 90°, т.е. две последовательные вершины лежат или в одной строке или в одном столбце (рис.3.2.). Самопересечения допускаются.

Контур всегда содержит четное количество вершин.

Рис.3.2.

Величина, определяющая перераспределение, равна наименьшему значению из перевозок, стоящих в четных вершинах цикла. Допустим, что эта величина равна q. После этого перераспределяют объемы перевозок внутри контура, для чего к объемам перевозок в нечетных вершинах добавляют величину q, а из объемов в четных вершинах вычитают эту же величину. В результате этой процедуры получают улучшенный план, в котором общие затраты на перевозку меньше, чем в предыдущем, на величину . Новый план также является опорным (допустимым), так как в каждой строке и столбце в одной клетке объем увеличился, а в другой – уменьшился на одну и ту же величину. Количество вершин с перевозками в новом плане не больше, чем m+ n -1.

Если количество клеток уменьшилось, то нельзя построить систему потенциалов, и такой план называется вырожденным. Для выхода из этой ситуации, в одну из клеток без перевозок проставляют фиктивную перевозку малого объема – e. И далее решают эту задачу как невырожденную, а в оптимальном плане заменяют e нулями.

Поиск по сайту: