5.4. Транспортная задача

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

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

Примем следующие обозначения:

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

Тогда, при наличии баланса производства и потребления,

,

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

, где ; .

Минимизирующий общую стоимость всех перевозок

,

При условии, что из любого пункта производства вывозится весь продукт

, где , (28)

И любому потребителю доставляется необходимое количества груза

, где , (29)

Причем, по смыслу задачи

, …, .

Для решения транспортной задачи чаще всего применяется метод потенциалов, при котором вводят обозначение вектора симплексных множителей или потенциалов:

.

Тогда:

, где ; .

Откуда следует:

, где ; .

При этом один из потенциалов можно выбирать произвольно, т. к. в системе (28) и (29) одно уравнение линейно зависит от остальных, а остальные потенциалы находятся, так что для базисных значений .

Предположим, что однородный продукт, находящийся в трех пунктах производства (m=3), необходимо доставить в четыре пункта потребления (n=4). При этом матрица транспортных затрат на перевозку единицы продукта из любого пункта отправления в любой пункт назначения, вектор объемов запасов продукта в пунктах производства и вектор объемов продукта, необходимых пунктам потребления, имеют вид:

,

,

.

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

,

Больше, чем требуется всем потребителям

,

Т. е. имеем открытую модель транспортной задачи.

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

единиц,

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

Тогда, первое базисное допустимое решение легко построить по правилу «северо-западного угла». А т. к. оценки базисных клеток транспортной таблицы равны нулю, то, приняв, что , первая транспортная таблица и потенциалы имеют вид:

Т. к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 14, то строим цикл пересчета: 14-13-23-24 и производим перераспределение поставок вдоль цикла пресчета:

* ® ® 0 9 6 34 45 25

Получаем второе базисное допустимое решение и находим новые потенциалы, полагая что :

,

Т. к. теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы соответствует клетке 22, то строим цикл пересчета: 22‑12‑14‑24 и производим перераспределение поставок вдоль цикла пресчета:

11 9 ® ® 0 20 * 25 11 14

Отсюда получаем третье базисное допустимое решение и находим новые потенциалы, принимая :

Т. к. наибольшая положительная оценка всех свободных клеток транспортной таблицы теперь соответствует клетке 21, то строим цикл пересчета: 21-11-14-24 и производим перераспределение поставок вдоль цикла пресчета:

30	20	®			®	16	34
*	14			14	0

Получаем четвертое базисное допустимое решение и находим новые потенциалы, принимая :

Т. к. наибольшая положительная оценка всех свободных клеток транспортной таблицы соответствует клетке 33, то строим цикл пересчета: 33-23-21-11‑14‑34 и производим перераспределение поставок вдоль цикла пресчета:

16		34	®				®	14		36
14	45					16	43
	*	2					2	0

Получаем пятое базисное допустимое решение и находим новые потенциалы, опять принимая :

Теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы соответствует клетке 25, отсюда строим цикл пересчета: 25-23-33- и производим перераспределение поставок вдоль этого цикла пресчета:

43	*	®			®	15	28
2	28			30	0

Получаем пятое базисное допустимое решение и снова находим новые потенциалы, принимая :

Находим оценки всех свободных клеток таблицы:

Все , где ;

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

,

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

< Предыдущая		Следующая >