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

Вопрос №11. Транспортная задача и ее решение.

 

Постановка задачи

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Цель транспортной задачи

Обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов, т.к. разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки.

Цель транспортной деятельности считается достигнутой при выполнении шести условий:

1. нужный товар;

2. необходимого  качества;

3. в необходимом  количестве доставлен;

4. в нужное время;

5. в нужное место;

6. с минимальными  затратами.

Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

История поиска методов решения

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира. Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется Транспортной задачей Монжа-Канторовича. Методы решения Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей ее можно решить проще (для задач малой размерности). Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из в груза , а в маленькие клетки — соответствующие тарифы .

Решение транспортной задачи

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей ее можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij.

Затем требуется определить опорный план и путем последовательных операций найти оптимальное решение. Опорный план можно найти методом "северо-западного угла" или методом "наименьшего элемента".

Метод северо-западного угла (диагональный). На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из Аi или полностью удовлетворяется потребность Вj.

Одним из способов решения задачи является метод минимального (наименьшего) элемента Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями. Алгоритм решения:

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

 
Затем рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления - в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока Cij. К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0. Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда-Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана-Форда. Напоминаем, что при возврате потока стоимость считается отрицательной.

Алгоритм mincost maxflow можно запускать и сразу - без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма mincost maxflow происходит не более чем за операций. (e - количество рёбер, v - количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше - порядка операций.

Пример решения транспортной задачи

Постав-       Потребители и их спрос               Мощность                      щики      1        2        3          4       поставщиков                      33       13       27         17              1       14(27)   28       21         28         27              2       10(6)    17(13)   15(1)      24         20              3       14       30       25(26)     21(17)     43                 Первоначальный план получен по методу северо-западного угла.                               Таблица - план перевозок по условию  задачи: Поставщики  и их ресурсы Потребители и их спрос B1     33 B2     13 B3     27 B4     17 A1     27 14     27 28     0 21     0 28     0 A2     20 10     6 17     13 15     1 24     0 A3     43 14     0 30     0 25     26 21     17                     Решение задачи.                                 Первоначальный план перевозок.   Задача сбалансированная (закрытая). Таблица 1. Поставщики  и их ресурсы Потребители и их спрос B1     33 B2     13 B3     27 B4     17 A1     27 14     27 28     0 21     0 28     0 A2     20 10     6 17     13 15     1 24     0 A3     43 14     0 30     0 25     26 21     17 Стоимость перевозок по данному плану составляет: 1681 Решим задачу с применением метода потенциалов. 1.Рассчитаем  потенциалы пунктов отправки  и пунктов доставки alfa и betta.            Для этого составьте систему  для заполненных клеток плана  перевозок: betta[j] - alfa[i] = C[i,j];                        где C - стоимость перевозки из  пункта i в пункт j. Решим данную  систему, полагая alfa[1]=0.                               2.Вычислим коэффициенты изменения  стоимости ( dC[i,j] ) для незаполненных клеток плана:                      dC[i,j] =betta[j] - alfa[i] - C[i,j];   Таблица 2. Поставщики  и их ресурсы Потребители и их спрос alfa B1     33 B2     13 B3     27 B4     17 A1     27 14   0 27 28   -7 0 21   -2 0 28   -13 0 0 A2     20 10 [-6] 0 6 17   0 13 15 [+6] 0 1 24   -13 0 4 A3     43 14 [+6] 6 0 30   -3 0 25 [-6] 0 26 21   0 17 -6 betta 14 21 19 15   Стоимость перевозок по данному плану составляет: 1681 Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок.  Составим цикл пересчета:  Опорная клетка: (3:1) , далее (3:3) [-6], (2:3) [+6], (2:1) [-6]  Количество единиц изменения плана: 6   Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2.   Получим следующий план перевозок (Табл.3)   Таблица 3. Поставщики  и их ресурсы Потребители и их спрос alfa B1     33 B2     13 B3     27 B4     17 A1     27 14 [-20] 0 27 28   -1 0 21 [+20] 4 0 28   -7 0 0 A2     20 10   -6 0 17   0 13 15   0 7 24   -13 0 10 A3     43 14 [+20] 0 6 30   -3 0 25 [-20] 0 20 21   0 17 0 betta 14 27 25 21   Стоимость перевозок по данному плану составляет: 1645   Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок.  Составим цикл пересчета:  Опорная клетка: (1:3) , далее (1:1) [-20], (3:1) [+20], (3:3) [-20]  Количество единиц изменения плана: 20   Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3.   Получим следующий план перевозок (Табл.4)   Таблица 4. Поставщики  и их ресурсы Потребители и их спрос alfa B1     33 B2     13 B3     27 B4     17 A1     27 14   0 7 28   -5 0 21   0 20 28   -7 0 0 A2     20 10   -2 0 17   0 13 15   0 7 24   -9 0 6 A3     43 14   0 26 30   -7 0 25   -4 0 21   0 17 0 betta 14 23 21 21   Стоимость перевозок по данному плану составляет: 1565   Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок.  Потенциалы и коэффициенты указаны в таблице 4.   Полученный план оптимальный, т.к. все коэффициенты изменения стоимости (dC[i,j]) отрицательны или равны нулю.

 

Полезное заключение

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

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

Список использованной литературы

 

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976 г.
2. Карманов В.Г. Математическое программирование. - М.; Наука, 1986г.
3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. - М.; Наука, 1978г.
4. www.fmi.asf.ru