Определение транспортной задачи

 

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

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

а) величины, характеризующие объёмы производства в каждом исходном пункте и спрос в каждом пункте назначения;

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

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

Цель построения модели состоит в определении количества продукции, которое следует перевезти из каждого исходного пункта в каждый пункт назначения, с тем чтобы общие транспортные расходы были минимальными. На рисунке 1.2 изображена транспортная модель в виде сети с исходными пунктами и пунктами назначения. Исходным пунктам и пунктом назначения соответствуют вершины. Дуга, соединяющая исходный пункт с пунктом

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

Пусть - количество продукции, перевозимой из исходного пункта в пункт назначения ; тогда задача линейного программирования транспортного типа в общем виде формулируется следующим образом:

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