Транспортная задача и ее особенности

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

В общем виде транспортная задача формулируется: имеется m поставщиков и n потребителей однородного груза. Запасы i-го поставщика обозначим a_i, спрос j-го потребителя – b_j. Если обозначить c_ij – стоимость перевозки единицы груза, а x_ij – количество перевозимого груза от i-го поставщика j-му потребителю, то математическая модель задачи будет иметь вид:

1) суммарные запасы на перевозку должны быть минимальные
	(2.1)
2) объем поставок i-го поставщика равен его запасу
	(2.2)
3) объем поставок j-му потребителю равен его спросу
	(2.3)
4) неотрицательность переменных
	(2.4)

Вместо матрицы затрат c_ij может задаваться матрица расстояний d_ij.

Если суммарный объем отправляемых грузов равен потребности в этих грузах, то ТЗ называется закрытой (сбалансированной) закрытой грузов равен потребности в этих грузах, то задача называ) , иначе – открытой.

Если имеет место открытая ТЗ, ее нужно свести к закрытой форме следующим образом:

1) если спрос > предложения, то вводят фиктивного поставщика с недостающим объемом спроса; тарифы c_ij, связывающие фиктивные пункты с реальными равны штрафам за недопоставку продукции;

2) если спрос < предложения, то вводят фиктивного потребителя с недостающим объемом потребления, элементы матрицы c_ij, связывающие фиктивные пункты с реальными, равны стоимости хранения единицы нераспределенного груза.

Если указанные в п. 1, 2 затраты неизвестны, то соответствующие элементы c_ij = 0.

Транспортная задача решается в два этапа. Сначала необходимо найти исходный опорный план, а затем производится последовательно его улучшение до получения оптимального плана. На первом этапе для распределения ресурсов можно использовать правило «северо-западного угла» (здесь не учитываются тарифы и план далек от оптимального) или правило «минимального элемента», при котором необходимо осуществлять максимальные поставки ресурсов в клетки с минимальными тарифами. На втором этапе можно применить распределительный метод или метод потенциалов.