Транспортная задача. Транспортная задача (ТЗ) формулируется следующим об­разом

Транспортная задача (ТЗ) формулируется следующим об­разом. В m пунктах отправления А1,..., Аm сосредоточен од­нородный груз в количествах соответственно а1,..., аm еди­ниц. Имеющийся груз необходимо доставить потребителям B1,..., Вn, спрос которых выражается величинами b1..., bп единиц. Известна стоимость Cij перевозки единицы груза из i-го (i= 1,m) пункта отправления в j-й (j = 1,n) пункт на­значения. Требуется составить план перевозок, который пол­ностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.

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

Потребители
Поставщики		П1	П2	...	Пj	...	Пn	Запас
П1	c11	c12	...	c1j	...	c1n	а1
П2	c21	c22	...	c2j	...	c2n	а2
...	...	...	...	...	...	...	...
Пi	ci1	ci2	...	cij	...	cin	аi
...	...	...	...	...	...	...	...
Пm	cm1	cm2	...	cmj	...	cmn	аm
Спрос	b1	b2		bj	...	bn

Транспортная задача, для которой выполняется условие

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

Запишем математическую модель закрытой транспортной задачи (запас груза у поставщиков должен равняться суммарному спросу потребителей):

1) объем поставок i-гo поставщика должен равняться количеству имеющегося у него груза:

2) объем поставок j-му потребителю должен быть равен его спросу:

3) размер поставок должен выражаться неотрицательным числом:

4) общая сумма затрат на перевозку груза должна быть минимальной:

Математическая модель открытой транспортной задачи

Запас груза у поставщиков больше суммарного спроса потребителей	Запас груза у поставщиков меньше суммарного спроса потребителей
Ограничения на поставщиков:	Ограничения на поставщиков:
Ограничения на потребителей:	Ограничения на потребителей:

Пример

Найти решение транспортной задачи, исходные данные которой приведены в таблице