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

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

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

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

Итак,

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

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

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

В настоящей главе рассматривается применение указанных выше алгоритмов для решения задач небольшой размеренности. Однако следует принять во внимание, что на практике размеренность таких задач гораздо больше, поэтому решаются они с использованием пакетов прикладных программ. Более того, очень часто решение транспортной задачи осуществляется в несколько этапов. Например, при перевозках типа «завод – склад – розничная продажа». В таких случаях приходится модифицировать основной алгоритм и использовать более сложные методы решения.

Постановка транспортной задачи (ТЗ)

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

Исходные параметры модели ТЗ:

n

– количество пунктов отправления

m

– количество пунктов назначения

а

i

– запас продукции в пункте отправления А

i

(

i

= 1…

n

)

(ед. тов.)

bj– спрос на продукцию в пункте назначения Bj

(

j

= 1…

m

)

(ед. тов.)

С

ij

– тариф (стоимость) перевозки единицы продукции из пункта отправления Аi в пункт назначения Вj (руб./ед. тов.)

Искомые параметры модели ТЗ:

xij– количество продукции, перевозимой из пункта направления Ai в пункт назначения Bj (ед. тов.)

L

(

X

)

– транспортные расходы на перевозку всей продукции (руб.)

Итак, имеется m пунктов отправления А1, А2, …, Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, …, am единиц. Имеется n пунктов назначения В1, В2, …, Вn, подавших заявки соответственно на b1, b2, …, bn единиц груза. Известны стоимости Сij перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj.

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

Этапы построения модели

1. Определение переменных

2. Проверка сбалансированности задачи

3. Построение сбалансированной транспортной матрицы

4. Задание целевой функции (ЦФ)

5. Задание ограничений

Транспортная модель

L(X) =

→ min

при условиях: