Алгоритм метода потенциалов. Наиболее распространенным методом решения транспортны задач признается метод потенциалов

ТРАНСПОРТНАЯ ЗАДАЧА

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

Решение задачи методом потенциалов включает в себя следующие этап:

1. Разработку начального плана (опорного решения);

2. Расчет потенциалов;

3. Проверку плана на оптимальность;

4. Поиск максимального звена не оптимальности (если условие третьего пункта не достигнуто);

5. Составление контура не распределения ресурсов;

6. Определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;

7. Получение нового плана.

Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.

Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения):

· Метод северо-западного угла;

· Метод минимальной стоимости;

· Метод двойного предпочтения и т.д.

Вычислительный алгоритм метода потенциалов рассмотрим на примере решения задачи прикрепления пунктов отправления к пунктам назначения j . В соответствии с принятыми в условиях задания обозначениями исходные данные задачи приведены в табл. 1.

Таблица 1

поставщик	потребитель	запасы
потребность

Начальный план можно составить одним из перечисленных выше методов. Воспользуемся наиболее простым методом – методом северо-западного угла. В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки «северо-западная» часть таблицы) и продолжается вниз и вправо (по диагонали).

По указанному правилу загружаем первую клетку (i – j) = (1 – 1) из условия:

Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза , которые и распределяем на второй пункт назначения:

Продолжая аналогичным образом, получаем:

и т. д.

Результаты начального плана представлены в таблице 2.

Таблица 2- Результаты начального плана

поставщик	потребитель	запасы
	р 40	з 20
		р	з 2
	+ 0 з	р 2
потребность

В процессе решения после каждой итерации (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение условия

В нашем задании т = 3, п = 4, а число загруженных клеток равно 6, т. е. соответствует условию (4.7): N=3+4-1=6, т. е. соответствует условию (4.7): . Если условие (4.7) не выполняется, план называется вырожденным. В этом случае в любые свободные клетки надо поставить столько нулей, чтобы с их учетом выполнялось условие (4.7). Клетка в которой стоит ноль, считается занятой. Значение целевой функции по результатам расчета допустимого плана:

Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:

где – потенциал i-й строки;

- потенциал j-ого столбца.

Вычисляя потенциалы по выражению (4.8), принимаем для первой строки . используя загруженные клетки (i – j) = (1 – 1), (1 – 2), получаем:

Далее по загруженным клеткам (2 – 2), (2 – 3) определяем другие потенциалы:

Результаты расчета потенциалов представлены в табл. 3.

Таблица 3- Расчет потенциалов

поставщик	потребитель	запасы
			р 80	з 0		-1
				р		-1
потребность

Проверяют план на оптимальность по незагруженным клеткам с использованием неравенства:

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

Итак, по трем клеткам условие (4.9) не выполняется, следовательно, начальный план требует улучшения. Характеристики показывают размер экономии транспортных издержек на единицу перевозимого груза. В нашем примере наибольшую экономию можно получить по клетке где . Следовательно, клетку (3 – 1) необходимо загрузить за счет перераспределения ресурсов из других загруженных клеток. В таблице клетку (3 – 1) помечаем знаком (+), так как здесь в начальном плане находится вершина максимальной неоптимальности.

Контур перераспределения ресурсов составляют по следующим правилам:

· Этот контур представляет замкнутый многоугольник с вершинами в загруженных клетках, за исключением клетки с вершиной максимальной не оптимальности (+) и звеньями, лежащими вдоль строк и столбцов матрицы;

· Ломаная линия должна быть связанной в том смысле, что из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной цепи (по строке или столбцу);

· В каждой вершине контура встречаются только два звена, одно из них располагается по строке, другое – по столбцу);

· Число вершин контура четное, вес они в процессе перераспределения делятся на загружаемые и разгружаемые;

· В каждой строке (столбце) имеются две вершины: одна загружаемая, другая разгружаемая.

В этой клетке намечаем одну из вершин контура и далее по вышеизложенным правилам строим контур, вершины которого будут находиться в клетках (3 – 1) – (1 – 1) – (1 – 2) – (2 – 2) – (2 – 3) – (3 – 3). Вершины контура последовательно подразделяем на загружаемые – 3 и разгружаемые – Р, начиная с вершины максимальной неоптимальности (+) (табл. 4.4).

Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных ни одно из этих значений не должно превратиться в отрицательное число. Поэтому анализируют только клетки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере . следовательно, клетки (1 -1), (2 – 2), (3 – 3) полностью разгружаются. В клетке (1 – 2) загрузка составит 40+40=80, и клетка (3 – 1) загрузится на 40. Проверяем условие N = m + n – 1. В нашем примере m=3, n=4, а число загруженных клеток равно 4, т. е. условие не выполняется 6 ≠ 4. В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае следует в две клетки проставить нули (нулевой ресурс) и считать их условно загруженными. Например, в клетки (1 – 1) и (3 – 3) проставим нулевой ресурс. Получение нового плана (итерации) осуществляется в том же порядке, который был рассмотрен:

· По загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы ;

· По незагруженным клеткам проводится проверка плана на оптимальность;

· Находится вершина максимальной неоптимальности и строится новый контур перераспределения, и так далее до тех пор, пока не будет найдено оптимальное решение, удовлетворяющее неравенству (4.9).

По результатам первой итерации имеем:

Ниже приведены расчеты по второй итерации (табл. 4.5) и оптимальный план.

Поиск потенциалов:

Проверка на оптимальность:

Клетку (2 – 4) необходимо загрузить.

В соответствии с перераспределением ресурсов по контуру получаем таблицу, для которой вновь рассчитываем потенциалы , и последовательность вычислений повторяется.

Таблица 4.5

поставщик	потребитель	запасы
						-1
						-1
потребность

Для распределения, полученного в таблице, условие выполняется, следовательно, план оптимальный.

Транспортные издержки по оптимальному плану:

Таким образом, построением начального плана и последующим расчетом двух итераций получено оптимальное решение по прикреплению пунктов отправления грузов к пунктам назначения.