3.2. Решение транспортной задачи

Решение получается путем преобразования транспортной таблицы по определенным правилам.

Решение строится в два этапа:

• на первом этапе отыскивается исходное опорное решение;

• на втором этапе методом последовательных итераций ищется оптимальное решение.

3.2.1. Определение исходного опорного решения

Исходное опорное решение может быть построено различными методами. Простейшим из них является метод «северо-западного» угла. В нем клетки транспортной таблицы заполняются, начиная с верхнего левого угла таблицы (клетка 1,1), двигаясь далее по строке вправо, или по столбцу вниз.

В первую клетку (1,1) занесем значение:

• Если a₁ > b₁, тоx₁₁=b₁ и потребности первого потребителя удовлетворены полностью, это позволяет закрыть первый столбец. Двигаемся далее по первой строке. Для этого в клетку (1,2) записываем меньшее из чиселa₁-b₁иb₂, , т.е.x₁₂ = min{ a₁-b₁ ; b₂ }.

В первую клетку (1,1) занесем значение:

• Если a₁ > b₁, тоx₁₁=b₁ и потребности первого потребителя удовлетворены полностью, это позволяет закрыть первый столбец. Двигаемся далее по первой строке. Для этого в клетку (1,2) записываем меньшее из чиселa₁-b₁иb₂, , т.е.x₁₂ = min{ a₁-b₁ ; b₂ }.

Рис.3.1

Далее двигаемся от клетки к клетке, пока на каком-то этапе не исчерпаются ресурсы и потребности.

В результате этой процедуры m+ n -1клеток будут содержать перевозки, остальные – будут пустыми.

Достоинством метода «северо-западного» угла является его простота, недостатком – его «удаленность» от оптимального решения (т.е. при построении оптимального решения требуется большее количество шагов – итераций), поскольку при его построении не учитываются цены перевозок. Этого недостатка лишены другие методы, например, наименьших стоимостей и двойного предпочтения.

3.2.2. Построение оптимального решения

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

Теорема

Для того, чтоб допустимый (опорный) план транспортной задачи 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.

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