Раздел 2. Транспортная задача

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

Исходными параметрами при построении модели для решения транспортной задачи являются:

1) n – количество пунктов отправления, m – количество пунктов назначения.

2) a_i – запас продукции в пункте отправления A _i (i = 1, n) [ед. прод.].

3) b_j – спрос на продукцию в пункте назначения B _j (j =1, m) [ед. прод.].

4) c_ij – тариф (стоимость) перевозки единицы продукции из пункта отправления A _i в пункт назначения B _j [руб. / ед. прод.].

Искомыми параметрами при построении модели для решения транспортной задачи являются:

1) x _ij – количество продукции, перевозимой из пункта отправления A _i в пункт назначения B _j [ед. прод.].

2) L (X) – транспортные расходы на перевозку всей продукции [руб.].

Основными этапами построения модели для решения транспортной задачи являются:

I. Определение переменных. (Этот этап весьма формален, т.к. переменными как правило служат x _ij – количество продукции, перевозимой из пункта отправления A _i в пункт назначения B _j).

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

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

Для фиктивных перевозок вводятся фиктивные тарифы c ^ф, величина которых обычно приравнивается к нулю c ^ф =0. Но в некоторых ситуациях величину фиктивного тарифа можно интерпретировать как штраф, которым облагается каждая единица недопоставленной продукции. В этом случае величина c^ф может быть любым положительным числом.

Иногда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов c^з. Запрещающие тарифы должны сделать невыгодными перевозки в соответствующих направлениях. Для этого величина запрещающих тарифов должна быть больше реальных тарифов в транспортной матрице