Планирование перевозок грузов

из "Введение в экономико-математическое моделирование "

Планирование перевозок грузов — важнейшая задача, занимающая особое место среди других проблем планирования. Современное производство, дающее основательную экономию с ростом масштабов выпуска продукции и с углублением специализации, приводит к необходимости осуществлять транспортировку сырья и полуфабрикатов между предприятиями. Если учесть огромные размеры нашей страны и то, что значительная часть населения, потребляющего продукцию народного хозяйства, проживает в европейской части страны, а основные запасы энергетических ресурсов и сырья сосредоточены в азиатской части, то становится ясно, что масштабы перевозок должны быть весьма значительными. Естественно, что столь же значительны затраты на перевозки — они составляют десятки миллиардов рублей ежегодно. Уменьшение этих затрат хотя бы на несколько процентов приводит к значительной экономии. Отсюда проистекает важность научного подхода к проблемам перевозок. [c.180]
Поскольку выполняется условие (4.1), то в последних двух ограничениях неравенства можно заменить на равенства, т. е. [c.181]
Последнее условие означает, что не должно быть перевозок груза туда, где он не нужен потребителю. Транспортные модели двух описанных здесь типов называются открытыми. [c.182]
Заметим, что во втором варианте транспортной модели открытого типа потребитель, спрос которого не будет удовлетворен, выбирается в соответствии с затратами на перевозку грузов. Такой подход верен не всегда, часто приходится учитывать в критерии задачи потери потребителей от неполучения грузов, поэтому задача может уже не быть транспортной задачей или даже задачей линейного программирования вообще. Если эти потери пропорциональны количеству недополученного груза, то критерий остается линейным и мы опять приходим к задаче линейного программирования. [c.182]
Эта задача также может быть сведена к транспортной задаче. [c.184]
Кроме того, имеется условие неотрицательности величин Хц Хц О, i=l,. .., щ / = . т. [c.184]
Транспортные задачи в сетевой постановке. Теперь попытаемся подойти к задаче перевозки грузов с несколько отличных позиций. Описанный ранее способ формулировки задачи перевозки состоял в том, что считалась возможной перевозка грузов из каждого пункта-отправителя в каждый из пунктов-потребителей я была известна матрица с ц удельных затрат на эти перевозки. При таком представлении каждый из пунктов-отправителей связан с пунктом-потребителем отдельной дорогой с характерными именно для нее затратами перевозки. Если же взглянуть на карту местности, на которой расположены интересующие нас пункты, то можно увидеть, что дороги соединяют большинство пунктов друг с другом не непосредственно, а проходят через другие пункты. Более того, груз из одного пункта в другой возможно провезти несколькими путями. Поэтому часто задачу перевозки грузов формулируют не в матричной постановке, как принято называть подход, описанный ранее в этом параграфе, а в так называемой сетевой постановке, основывающейся на явном представлении структуры транспортной сети. Очень простая транспортная сеть приведена на рис. 3.2, а. Внутри каждого кружка римской цифрой изображен номер этого пункта (в сетевых постановках пункты нумеруются без разделения на поставщиков и потребителей). Второе число означает мощность или спрос в этом пункте. В случае мощности перед числом стоит знак плюс, в случае спроса — минус. Около отрезков, связывающих кружки, поставлены числа, указывающие расстояние между пунктами или затраты на перевозку единицы груза по дороге между пунктами, которые эта дорога соединяет. На рисунке размеры отрезков могут не быть пропорциональны числам, стоящим около них. [c.185]
По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, то часть грузов можно будет перевозить по другим дорогам. Однако при. этом изменится величина затрат при перевозке единицы груза, так что в матричной постановке величина с,-3- окажется зависимой от Xtj и задача станет нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие исследователи предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач на сети. Сформулируем транспортную задачу в сетевой постановке в математической форме. [c.187]
Каждому отрезку (дуге) (i, /),-соединяющему узел i с узлом /, ставится в соответствие неотрицательное число dti (оно поставлено на рис. 3.3 рядом с дугой), характеризующее пропускную способность магистрали. Это число можно интерпретировать как максимальное количество груза, которое может быть доставлено из пункта i в пункт / за единицу времени. В узлах транспортной сети либо происходит пересечение нескольких транспортных магистралей, либо меняется пропускная способность (например, узел I на рис. 3.3). [c.188]
В задаче о максимальном потоке мощность источника г , равная спросу в пункте потребления, не считается заданной. Наоборот, в задачах такого типа требуется максимизировать величину у для заданной транспортной сети. [c.188]
Задача о максимальном потоке может быть поставлена и в более сложном виде. Например, часто накладываются ограничения на пропускные способности узлов. [c.189]
С помощью методов потенциалов решим транспортную задачу, условия которой приведены на рис. 3.2, а. При этом будем считать, что ограничения на пропускные способности коммуникаций отсутствуют п коммуникации не имеют направления. [c.189]
Такой исходный план для сети, изображенной на рис. 3.2, а, приведен на рис. 3.2, б, где перевозки изображены в кружках со стрелками, указывающими их направление. [c.190]
Конечно, в задачах, встречающихся в практических исследованиях, сети бывают значительно сложнее, так что для расчета требуется провести значительное число описанных здесь шагов. Тем не менее во многих случаях с помощью метода потенциалов удалось решить практические задачи даже без использования ЭВМ. По своему смыслу потенциалы близки к двойственным переменным соответствующей задачи линейного программирования в матричной постановке (см., например, [13]). [c.191]

Вернуться к основной статье