Алгоритм метода потенциалов

 

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

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

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

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

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

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

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

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

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

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

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

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

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

- метод двойного предпочтения и т. д.

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

 

 

Таблица 7.2 – Исходные данные задачи

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

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

Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза Δa₁ = 60 - 40 = 20, кото­рые и распределяем на второй пункт назначения:

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

 

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

Таблица 7.3 – Начальный план перевозок

 

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

N=m+n-1 (7)

 

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

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

(8)

где α_i, – потенциал i-и строки; β_j — потенциал j-го столбца.

Вычисляя потенциалы по выражению (8), принимаем для пер­вой строки

α₁ = 0. Используя загруженные клетки (i-j) = (1-1), (1 - 2), получаем:

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

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

(9)

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

Итак, по трем клеткам условие (9) не выполняется, следова­тельно, начальный план требует улучшения. Характеристики Δc_ij показывают размер экономии транспортных издержек на 1 ед. пе­ревозимого груза. В нашем примере наибольшую экономию можно получить по клетке (i -j) = (3-1), где Δc₃₁ = 2 > { Δc₂₄; Δc₃₂}. Сле­довательно, клетку (3-1) необходимо загрузить за счет перераспре­деления ресурсов из других загруженных клеток. В табл. 3 клетку (3-1) помечаем знаком «+», так как здесь в начальном плане нахо­дится вершина максимальной неоптимальности.

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

- этот контур представляет замкнутый многоугольник с вершина­
ми в загруженных клетках, за исключением клетки с вершиной
максимальной неоптимальности «+», и звеньями, лежащими
вдоль строк и столбцов матрицы;

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

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

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

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

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

Перераспределение ресурсов по контуру осуществляется с це­лью получения оптимального плана. В процессе перераспределе­ния ресурсов по контуру в соответствии с условием неотрицатель­ности переменных x_ij ни одно из этих значений не должно превра­титься в отрицательное число. Поэтому анализируют только клет­ки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере X_min = min{40; 40; 40} = 40. Следовательно, клетки (1 — 1), (2—2), (3—3) полностью разгружаются. В клетке (1—2) загрузка увеличится на 40 и достиг­нет 60, в клетке (2—3) загрузка составит 40 + 40 = 80, и клетка (3—1) загрузится на 40 (табл. 4).

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

- по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы αi, и βj ;

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

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

 

 

Таблица 7.4 – Первый план перевозок

 

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

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

Поиск потенциалов следующий:

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

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

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

 

Таблица 7.5 – Оптимальный план перевозок

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

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

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