Постановка задачи и алгоритм метода потенциалов

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них являет­ся, как правило, распределение ресурсов, находящихся у т про­изводителей (поставщиков), по п потребителям этих ресурсов. В логистическом управлении наиболее часто встречаются следующие задачи, относящиеся к транспортным:

• прикрепление потребителей ресурса к производителям;

• привязка пунктов отправления к пунктам назначения;

• взаимная привязка грузопотоков прямого и обратного нап­равлений;

• отдельные задачи оптимальной загрузки промышленного оборудования;

• оптимальное распределение объемов выпуска промышлен­ной продукции между заводами-изготовителями.

Рассмотрим экономико-математическую модель прикрепле­ния пунктов отправления к пунктам назначения. Имеется т пунктов отправления груза и объемы отправления по каждому пункту а₁, а ₂..., а_т. Известна потребность в грузах b₁, b₂.....b_п по каждому из пунктов назначения. Задана матрица стоимостей доставки по каждому варианту c_ij, Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколь­ко груза должно быть отправлено из каждого i -го пункта отправ­ления (от поставщика) в каждый j -й пункт назначения (до потре­бителя) — х_ij, с минимальными транспортными издержками.

В общем виде исходные данные представлены в табл. 5.8.

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

объем отправляемых грузов равен суммарному объему

потребности в этих грузах по пунктам назначения

(5.1)

Таблица 5,8

Если такого равенства нет (потребности выше запасов, или наоборот), задачу называют открытой, т. е.:

(5.2)

Для написания модели необходимо все условия (ограниче­ния) и целевую функцию представить в виде математических уравнений.

Все грузы из i -х пунктов должны быть отправлены, т. е.

(5.3)

Все j -е пункты (потребители) должны быть обеспечены груза­ми в плановом объеме:

(5.4)

Суммарные объемы отправления должны равняться суммар­ным объемам назначения:

(5.5)

Должно выполняться условие неотрицательности перемен­ных: x ³ 0, x_{ij ³} 0, Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(5.6)

В модели (5.3)—(5.6) вместо матрицы стоимостей перевозок (c_{i j}) могут задаваться матрицы расстояний. В таком случае в каче­стве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (5.5), уравнение баланса служит обязательным условием решения транспортной задачи. Поэтому если в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме:

• если потребности по пунктам назначения превышают запа­сы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

• если запасы поставщиков превышают потребности потре­бителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов за­дача решается как закрытая.

Транспортным задачам присущи следующие особенности:

• распределению подлежат однородные ресурсы;

• условия задачи описываются только уравнениями;

• все переменные выражаются в одинаковых единицах изме­рения;

• во всех уравнениях коэффициенты при неизвестных равны единице;

• каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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