Общая постановка транспортной задачи. Критерии оптимизации

 

Цель решения транспортной задачи – минимизация затрат на перевозки.

Постановка задачи:

· имеется “m” пунктов отправления А₁, А₂, …, А _m, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а ₁ , а ₂ , …, а _m единиц.

· имеется “n” пунктов назначения В₁, В₂, …В_n, подавших заявки соответственно на b₁ , b₂, …, b_n единиц груза.

Сумма всех заявок равна сумме всех запасов:

Известны стоимости с_ij перевозки единицы груза от каждого пункта отправления А_i до каждого пункта назначения В_j (i = 1, 2, … m; j = 1, 2, … n).

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

(1)

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

(2)

Суммарная стоимость всех перевозок, то есть сумма величин x_ij умноженных на соответствующие стоимости с_ij должна быть минимальной:

Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (1) и (2) – все заявки удовлетворены, все запасы исчерпаны.

 

Рассмотрим на конкретном примере решение практической задачи методом потенциалов, который включает несколько этапов:

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

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

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

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

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

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

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

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

Пример. На двух складах А и В имеются соответственно 50 и 40 т груза. Требуется спланировать перевозки к трем потребителям С, Д и Е так, чтобы потребитель С получил 30 т, Д – 20 т, Е – 40 т, а затраты на перевозку были минимальными.

Стоимость перевозок единицы груза (1 тонны) в у.д.е. от складов к потребителям заданы в табл.1. (с₁₁=3; с₁₂=2; с₁₃=1; с₂₁=3; с₂₂=5; с₂₃=6)

Таблица 1

Стоимость перевозок

Потребители Склады	С	Д	Е
А	x11	x12	x13
В	x21	x22	x23

Составим математическую модель задачи на множестве решений системы:

При этом количество пунктов отправления m = 2, а количество пунктов назначения n =3.

Найти минимальное значение целевой функции:

F = 3 x₁₁ + 2 x₁₂ + x₁₃ + 3 x₂₁ + 5 x₂₂ + 6 x₂₃.