Постановка задачи и её математическая модель

Модель транспортной задачи используется при составлении наиболее экономичного плана перевозок однородной продукции из нескольких пунктов отправления в пункты назначения, управлении запасами, назначении служащих на рабочие места и прочее.

Постановка задачи. Пусть некий однородный продукт сосредоточен у m поставщиков A_i в количествах a_i (i=1,…, m) необходимо доставить n потребителям B_j в количестве b_j (j=1,…, n).

Известна стоимость C_ij перевозки единицы груза от i -го поставщика j -му потребителю.

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

Решение задачи. Пусть количество продукции, имеющейся в пункте i,составляет a_i. Количество продукции потребляемой в пункте j составляет b_j, C_ij - стоимость перевозки из пункта i в пункт j.

Пусть Х_ij – количество единиц груза, запланированного к перевозке от i -го поставщика к j -му потребителю. Математическая модель транспортной задачи имеет вид:

(1)

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

= , (2)

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

Если запасы превышают потребности, то есть > ,

то водится фиктивный пункт назначения (n +1) с потребностью

b_n₊₁ = - .

Если потребности превышают запасы < , вводится фиктивный пункт отправления запасов

a_m₊₁ = - .

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

> .

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