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

Тема 2. Транспортная задача

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

 2.1. Постановка транспортной задачи

Рассмотрим систему, включающую в себя [pic 1] пунктов, где аккумулирован однородный груз. В дальнейшем будем именовать их ’’склады’’. И [pic 2] пунктов, куда этот груз должен быть доставлен. В дальнейшем будем именовать их ’’потребители’’.  Предполагается известным: количество груза [pic 3] содержащееся на каждом складе; количество груза [pic 4] которое может принять каждый потребитель; стоимость доставки единицы груза от [pic 5] ого склада до [pic 6] ого потребителя [pic 7], т.е. тариф. Множество чисел [pic 8] [pic 9] [pic 10] образуют матрицу [pic 11] называемую матрицей тарифов. Будем считать, что:

1. Технически осуществляемой является перевозка между любым складом и любым потребителем;

2. Перевозки осуществляются только со складов к потребителям, отсутствует как обратный грузопоток, так и обмен грузами между складами и потребителями.

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

Сформулируем математическую модель и осуществим формальную постановку задачи. Обозначим [pic 12] количество груза, планируемое к перевозке с [pic 13]ого склада [pic 14]ому потребителю. Всё множество этих чисел образует матрицу [pic 15] которая носит название матрицы перевозок. Тогда требование минимизации суммарных транспортных издержек может быть записано в виде целевой функции [pic 16] Требование полного удовлетворения спроса потребителей порождает ограничения вида [pic 17] требования полного исчерпания запасов грузов на складах порождает ограничения вида [pic 18] предположение об отсутствии встречных перевозок порождает ограничения неотрицательности [pic 19] Сформулированная модель ситуации представляет собой типичную задачу линейного программирования в канонической форме. Поскольку сумма элементов матрицы перевозок не зависит от порядка суммирования, т.е. [pic 20] иначе говоря, постановка задачи предусматривает  строгое равенство общего спроса потребителей запасам грузов, имеющихся на всех складах. Это условие определяет транспортную задачу закрытого типа. Однако, в реальных задачах подобное имеет место крайне редко, и обычно [pic 21] что определяет принадлежность транспортной задачи к открытому типу. Поскольку равенство складских запасов совокупному спросу потребителей естественно вытекает из оригинальной постановки задачи, решение возможно только закрытых транспортных задач. Укажем алгоритм приведения открытой транспортной задачи к закрытой. Пусть, для определенности, [pic 22] т.е. запасы грузов на складах превышают суммарный спрос. В этом случае добавляется фиктивный потребитель, спрос которого полагается равным [pic 23] но, т.к. реальных перевозок к этому потребителю нет, тарифы на перевозку грузов до этого потребителя полагаются нулевыми. Т.е. [pic 24] Фактически это означает, что часть грузов останется на складах. При [pic 25] добавляется фиктивный склад и дополнительная нулевая строка в матрицу тарифов.