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

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

Имеется ряд пунктов производства A₁, A₂, …, A_m с объемами производства в единицу времени (месяц, квартал), равными соответственно a₁, a₂, …, a_m  и пункты потребления B₁, B₂, …, B_n, потребляющие за тот же промежуток времени, соответственно b₁, b₂, …, b_n  продукции. В случае, если решается закрытая (сба­лансированная) задача, сумма объемов производства на всех m пунктах-поставщиках равна сумме объемов потребления на всех n пунктах-по­лу­ча­те­лях:

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

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет то, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта

и каждый поставщик отгружает весь произведенный им продукт

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

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

Несбалансированную (отк­рытую) Т.з. приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.

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