Лекция 14. ТРАНСПОРТНАЯ ЗАДАЧА (ТЗ)

Формулировка ТЗ

Транспортная задача является одной из наиболее распространенных ЗЛП и находит широкое практическое применение.

Постановка транспортной задачи. Пусть некоторый однородный продукт, сосредоточенный у m поставщиков А. в количестве а (i = 1, т) единиц, необходимо доставить п потребителям В. в количестве Ц (j = 1, п) единиц. Известна стоимость c{j перевозки единицы груза от поставщика i к потребителю j. Составить план перевозок, позволяющий с минимальными затратами вывезти все грузы и полностью удовлетворить потребителей.

Математическая формулировка транспортной задачи. Обозначим через х.. количество единиц груза, запланированных к перевозке от поставщика i к потребителю]. Стоимость каждой перевозки составит с • х...

и и

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

Мощности поставщиков

Мощности потребителей

Ь,

Ь2

Ь п

ai

С11

С12

С1п

А

С21

С22

С2п

ат

Сп>1

Сп,2

Cmn

Стоимость всего плана выразится двойной суммой

Систему ограничений можно получить из условий задачи:

  • а) все грузы должны быть вывезены, т.е.
  • 2^.. =«,,(/ = 1,т);

/=1

  • б) все потребности должны быть удовлетворены, т.е.
  • 2хи =b,, XJ = 1,я).

Z=1

Таким образом, математическая модель транспортной задачи имеет следующий вид:

т п найти F = 22 22 суху -^min (1) ;=1 ;=1

при ограничениях

22 ха = а^ = ,т,

< С _ &

2xv =bjJ = Vn,

. i=l

ху > О, i = ,т ,j = l,n.

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

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

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

т п

i=l j=l

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

п т

='LbJ~'Ea‘ ?

7 = 1 /=1

Стоимости перевозок единиц груза c;j от фиктивного поставщика до фиктивного потребителя полагаются равными нулю, так как груз не перевозится.

ТЗ имеет n+m уравнений с п т неизвестными. Матрицу перевозок X = (х..), удовлетворяющую ограничениям (2), называют допустимым планом перевозок. Допустимый план, при котором суммарная стоимость перевозок минимальна, называется оптимальным.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >