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

из "Оптимальные решения в экономике "

Очень эффективно, например, было бы оптимально планировать совместную деятельность сразу нескольких видов транспорта. Но возникающая при этом математическая задача будет иметь весьма большой размер, что, естественно, затруднит поиск оптимального решения, и без того осложненного тем, что такая задача принадлежит разным ведомствам . В общем здесь есть еще немало вопросов, ждущих своего решения с помощью точных математических методов. [c.46]
К задаче транспортировки грузов тесно примыкают и задачи оптимальной маршрутизации. Краткая характеристика их такова. Пусть речь идет о перевозке различных грузов между несколькими пунктами погрузки и разгрузки, причем адреса перевозок указаны заранее. Тогда дело сводится к определению того, куда нужно перебрасывать высвободившиеся вагоны или автомашины, чтобы суммарные затраты на перевозки были минимальны, т. е. чтобы минимизировалось количество холостых рейсов (о решении этих проблем на основе модели транспортной задачи см. стр. 55). [c.46]
Пусть имеются пункты производства AI, А2,. .,, Ап с объемами производства в единицу времени (месяц, квартал), равными соответственно а4, аг,. .., ап, и пункты потребления BI, Bz,. .., Вт с объемами потребления, равными Ь1 Ь2,. .., Ът соответственно. Будем предполагать, что производство и потребление сбалансированы — сумма объемов производства равна сумме объемов потребления, т. е. [c.47]
Предполагаются известными величины Сц — затраты по перевозке единицы продукта из i-ro пункта производства в у -й пункт потребления. Они могут быть выражены в стоимостной (денежной) форме или в натуре (например, в тонно-километрах). Требуется найти такой план перевозок, при котором были бы удовлетворены потребности в пунктах BI, В2,. .., Вт и при этом суммарные затраты на перевозку были бы минимальны. [c.47]
Обозначая через х количество продукта, перевозимое из i-ro пункта производства в у -й пункт потребления, приходим к следующей математической формулировке задачи. [c.47]
Всякий набор величин х (i = 1,. .., л / 1,. .., т), удовлетворяющих условиям (1) — (3), будем называть допустимым планом перевозок. План, для которого суммарные затраты достигают минимума, называется оптимальным. [c.48]
Рассмотрим теперь процесс формирования оптимального плана транспортной задачи. Возьмем конкретный числовой пример и, применив метод последовательного улучшения, детально покажем, как строится такой план. [c.49]
Пусть заданы объемы производства at = 95, a2 = 55, a3 = 50 и объемы потребления bi = 48, Ь2 = 54, Ь3 = 31, Ь4 = 37 и Ь6= 30. Затраты на перевозки записаны в табл. 6 в виде матрицы. Например, число 90 означает, что перевозка единицы продукта из пункта AI ъ пункт Bi обходится в 90 единиц (скажем, эти числа могут означать расстояния между пунктами если объем дан в тоннах, затраты выражаются в тонно-километрах). [c.49]
Нахождением нового допустимого плана заканчивается, как говорят математики, первое приближение (первая итерация). Дальше аналогичные операции проводятся снова, но уже для нового плана. Прежде всего вычисляются потенциалы, проверяются условия оптимальности. Если они выполнены, то решение закончено. Если нет, то снова производится переход к лучшему плану и т. д. [c.52]
Все же остальные значения V] — Ui — Сц равны нулю. Следовательно, в силу критерия оптимальности найденный план — наилучший, оптимальный. Затраты на его реализацию составляют 28-72 + 37-56 + 30-46 + 39-1 + 4-43-54 + 47-41 + 45-3 = 9891. [c.53]
По сравнению с первым допустимым планом, который представлялся на первый взгляд также весьма разумным, затраты в оптимальном плане уменьшились примерно на 13%. [c.53]
Рассмотрим, например, транспортную задачу в конкретных условиях, приведенных на рис. 6. Пункты производства на нем обозначены прямоугольниками, пункты потребления — кружками, а промежуточные пункты — треугольниками. Числа в скобках со знаком плюс указывают объемы производства, со знаком минус — объемы потребления, а числа, стоящие возле участков пути, выражают транспортные затраты по перевозке единицы продукта между соответствующими пунктами. В результате решения, ход которого мы не будем приводить здесь, можно найти рациональные грузопотоки, а также систему потенциалов, выражающих цену единицы продукта в различных пунктах, включая обусловленную планом рациональную транспортную наценку. На рис. 6 числа, стоящие у вертикальных отрезков, равны потенциалам, а стрелки на контуре указывают направление рациональных перевозок. [c.54]
Математическая модель транспортной задачи получает все большее и большее практическое применение. В настоящее время в Государственном комитете по материально-техническому снабжению на основе методики, разработанной по этой модели, произведено прикрепление и составлены рациональные планы перевозок для десятков видов продукции химической промышленности, промышленности строительных материалов и продукции других отраслей хозяйства, что дает миллионы рублей экономии в затратах на железнодорожный транспорт. [c.55]
Упоминавшаяся в начале этого параграфа задача маршрутизации может быть также решена с помощью транспортной модели. Для этого нужно принять в качестве однородного груза. .. пустые вагоны, направляемые от пункта выгрузки к пунктам погрузки. Полученное распределение, которое без труда находится на основе транспортной задачи, дает решение задачи об оптимальной маршрутизации, так как оно определяет пути следования вагонов. [c.55]
Очень важно знать, что транспортная задача используется не только для решения транспортных проблем. Ее первое применение действительно осуществлялось иа примере этой отрасли народного хозяйства, но вообще математическая модель транспортной задачи может описывать самые разные ситуации, очень далекие от перевозок. Задача, о которой сейчас пойдет речь,— задача размещения производства — лишний раз подтверждает это положение. [c.56]

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