8.2. Алгоритм метода потенциалов
Решение задачи методом потенциалов включает следующие этапы:
разработку начального плана (опорного решения);
расчет потенциалов;
проверку плана на оптимальность;
поиск максимального звена неоптимальности (если условие п.
3 не было достигнуто);составление контура перераспределения ресурсов;
определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;
получение нового плана.
Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.
Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения):
метод северо-западного угла;
метод минимальной стоимости;
метод двойного предпочтения и т. д.
Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи прикрепления пунктов от-правления / = 1,3 к пунктам назначения j = 1,4. В соответствии с принятыми в подразд. 8.1 обозначениями исходные данные задачи приведены в табл. 8.2.
Таблица 8.2
Исходные данные Поставщики Потребители Запасы Вх в2 Вг ВА 1 2 3 4 60 Л2 4 3 2 0 80 Лг 0 2 2 1 100 Потребность 40 60 80 60 240
Начальный план можно составить одним из перечисленных выше методов. Воспользуемся наиболее простым методом — методом северо-западного угла. В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки («северо-западная» часть таблицы) и продолжается вниз и вправо (по диагонали).
По указанному правилу загружаем первую клетку (/ - J) = = (1 — 1) на основе следующего условия:
хп = min {ах\ b\) = min {60; 40} = 40.
Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза Аах = 60 — 40 = 20, которые и распределяем на второй пункт назначения:
xl2 = min {А а і; b2} = min {20; 60} = 20; A b2 = 40.
Продолжая преобразования аналогичным образом, получаем: х22 = niin {а2; Ab2) = min {80; 40} = 40; АЬ2 = 40 и т.
д.Результаты начального плана и расчета потенциалов представлены в табл. 8.3.
Таблица 8.3
Начальный план перевозок Поставщики Потребители Запасы Вх В2 Вз В, А Р 1
40 2
20 3 3 4 60 0 Аг і ^ 4 3 3 2 0 80 1 40 Р 40 Аг Є 0 2 Р 2
40 1
60 100 1 3 Потребность 40 60 80 60 240 РУ 1 2 1 0
В процессе решения после каждой итерации (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение следующего условия:
N= т + п - 1. (8.7)
В нашем примере т = 3, п = 4, а число загруженных клеток равно 6, т. е. соответствует условию (8.7): #=3 + 4—1 = 6. Если условие (8.7) не выполняется, план называется вырожденным. В этом случае в любые свободные клетки надо поставить столько нулей, чтобы с их учетом выполнялось условие (8.7). Клетка, в которой стоит ноль, считается занятой. Значение целевой функции по результатам расчета допустимого плана
т п
Z= X =1-40 + 2-20 + 3-40 + 2-40 + 2-40 + 1-60 = 420 д.е.
му-1
Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:
(8.8)
а І + ру = сір
где а,- — потенциал /-й строки;
ру — потенциал у'-го столбца.
Вычисляя потенциалы по выражению (8.8), принимаем для первой строки а{ = 0. Используя загруженные клетки (/ - у) = (1 — 1), (1 — 2), получаем:
+ Pi = си = 0 + р1 = 1; р1 = 1;
+ Р2 = сп = 0 + Р2 = 2; Р2 = 2.
Далее по загруженным клеткам (2 — 2), (2 — 3) определяем другие потенциалы:
а2 + Р2 = 3; а2 + 2 = 3; а2 = 1;
а2 + Рз = 2; 1 + Рз = 2; Рз = 1.
Результаты расчета потенциалов представлены в табл 8.3.
Проверяем план на оптимальность по незагруженным клеткам, используя следующее неравенство:
а, + Ру < су. (8.9)
Если для незагруженных клеток условие (8.9) выполняется, то план — оптимальный. По табл. 8.3 осуществляем проверку начального плана на оптимальность: = (1-3), 0 + 1 <3; (/- = (1-4), 0 + 0 < 4; = (2-1), 1 + 1 < 4; (/- = (2-4), 1 + 0 > 0, Лс24 = 1; (/- (3-1), 1 + 1 > 0, Дс31 = 2; (/- (3-2), 1 + 2 > 2, Дс32 = 1.
Итак, по трем клеткам условие (8.9) не выполняется, следова-тельно, начальный план требует улучшения.
Характеристики А Су показывают размер экономии транспортных издержек на 1 ед. пе-ревозимого груза. В нашем примере наибольшую экономию можно получить по клетке (/ — у) = (3 — 1), где Ас31 = 2 > {Ас24; Ас32}. Сле-довательно, клетку (3—1) необходимо загрузить за счет перераспре-деления ресурсов из других загруженных клеток. В табл. 8.3 клетку (3—1) помечаем знаком «+», так как здесь в начальном плане нахо-дится вершина максимальной неоптимальности.Контур перераспределения ресурсов составляют по следующим правилам:
этот контур представляет замкнутый многоугольник с вершинами в загруженных клетках, за исключением клетки с вершиной максимальной неоптимальности «+», и звеньями, лежащими вдоль строк и столбцов матрицы;
ломаная линия должна быть связанной в том смысле, что из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной цепи (по строке или по столбцу);
в каждой вершине контура встречаются только два звена, одно из них располагается по строке, другое — по столбцу;
число вершин контура четное, все они в процессе перераспределения делятся на загружаемые и разгружаемые;
в каждой строке (столбце) имеются две вершины: одна — загружаемая, другая — разгружаемая.
В этой клетке намечаем одну из вершин контура и далее по вы-шеизложенным правилам строим контур, вершины которого будут находиться в клетках (3-1) - (1-1) - (1-2) - (2-2) - (2-3) - — (3—3). Вершины контура последовательно подразделяем на загружаемые (3) и разгружаемые (Р), начиная с вершины максимальной неоптимальности «+» (табл. 8.3).
Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Ху ни одно из этих значений не должно превратиться в отрицательное число. Поэтому анализируют только клетки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере Хтїп = min{40; 40; 40} = 40.
Следовательно, клетки (1—1), (2—2), (3—3) полностью разгружаются. В клетке (1—2) загрузка увеличится на 40 и достигнет 60, в клетке (2—3) загрузка составит 40 + 40 = 80, и клетка (3-1) загрузится на 40 (табл. 8.4).Проверяем условие N = т + п — 1. В нашем примере т = 3, п = 4, а число загруженных клеток равно 4, т. е. условие не выполняется и 6 Ф 4. В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае следует в две клетки проставить нули (нулевой ресурс) и считать условно их загруженными. Например, в клетки (1-1) и (3-3) проставим нулевой ресурс (рис. 8.4). Получение нового плана (итерации) осуществляется в том же порядке, который был рассмотрен выше, т. е.
по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы а, и (3у;
Первый план перевозок Поставщики Потребители Запасы а/ Вх в2 Вз В\ А\ 1
0 2
60 3 4 60 0 л2 4 3 2
80 Г- Ф 0
3 80 -1 Аз 0
40 2 р 60 100 -1 Потребность 40 60 80 60 240 р, 1 2 3 2
по незагруженным клеткам производится проверка плана на оптимальность;
находится вершина максимальной неоптимальности и строится новый контур перераспределения и т. д., до тех пор, пока не будет найдено оптимальное решение, удовлетворяющее неравенству (8.9).
По результатам первой итерации имеем
т п
2=2 2суХд= 2-60 + 2-80 + 1-60 + 0-40 = 340.
/=1у=1
Ниже приведены расчеты по второй итерации и оптимальный план.
Поиск потенциалов следующий: «і + Pi = 1 о + р, = 1 01» 1; осі + р2 = 2 0 + р2 = 2 02 = 2; а2 + Рз = 2 а2 + 3 = 2 а2 = -1 а3 + pi = 0 а3 + 1 = 0 аз = -1 а3 + Рз = 2 -1 + Эз = 2 03 = 3; а3 + р4 = 1 -1 + 04 = 1 04 = 2. Проведем проверку на оптимальность:
О' — j) = (1—3); 0 + 3 < 3 (/ — У) = (1-4);0 + 2<4 (/-у) = (2-1); 1 - 1 <4
(1-У) = (2-2); 2-1 <3; (/ -У) = (3-2); 2 - 1 < 2; (/ -У) = (2-4); 2 - 1 > 0.
Клетку (2—4) необходимо загрузить.
В соответствии с перераспределением ресурсов по контуру получаем табл. 8.5, для которой вновь рассчитываем потенциалы а,- и (З,-, и последовательность вычислений повторяется.
Таблица 8.5
Оптимальный план перевозок Поставщики Потребители Запасы а, Вх В2 Вз В4 А, 1
0 2
60 3 4 60 0 А2 4 3 2
20 0
60 80 -1 Аз 0
40 2 2
60 1 100 -1 Потребность 40 60 80 60 240 р, 1 2 3 1
Для распределения, полученного в табл. 8.5, условие а,- + (Зу < Су выполняется, следовательно, план — оптимальный.
Транспортные издержки по оптимальному плану следующие:
т п
z= 1 1 СуХу =1-0 + 2-60 + 2.20 + 0-60 + 0.40 + 2-60 = 280 д.е.
/=1у=1
Таким образом, построением начального плана с последующим расчетом двух итераций получено оптимальное решение по прикреплению пунктов отправления грузов к пунктам назначения.