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

, ( i = 1 n )

, ( j= 1 m )(1.1)

Xij ³ 0 (i = 1 m; j= 1 n )

Целевая функция представляет собой транспортные расходы на осуществление всех перевозок в целом. Первая группа ограничений указывает, что запас продукции в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте. Наглядной формой представления модели ТЗ является транспортная матрица.

Таблица 2.

Общий вид транспортной матрицы

Из модели (1.1.) следует, что сумма запасов продукции во всех пунктах отправления должна равняться суммарной потребности во всех пунктах потребления, то есть:

(1.2)

Как уже отмечалось, если (1.2) выполняется, то ТЗ называется сбалансированной, в противном случае – несбалансированной.

Наиболее рациональным прикреплением поставщиков к потребителям будет то, при котором суммарные затраты на перевозку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта

и каждый поставщик отгружает весь произведенный им продукт

.

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

Поскольку ограничения модели (1.1) могут быть выполнены только при сбалансированной ТЗ, то при построении транспортной модели необходимо проверять условие баланса (1.2).

Несбалансированную ТЗ приводят к виду, показанному выше, искусственно: в модель вводятся фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.

В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть

b

ф

= > 0

(1.3)

Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:

аф = > 0

(1.4)

Введение фиктивного потребителя или отправителя повлечет необходимость формального задания фиктивных (реально не существующих) тарифов (сф

ij

) для фиктивных перевозок.

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