Тема 6. Транспортная логистика Презентация подготовлена преподавателем кафедры «Прикладной математики» Тесёлкиной Е.С. - презентация

1 Тема 6. Транспортная логистика Презентация подготовлена преподавателем кафедры «Прикладной математики» Тесёлкиной Е.С.

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

3 Задачи ТЛ решаются во взаимной связи с другими задачами логистики, такими, как производственная логистика (ПС), складская логистика, логистика запасов, сбытовая логистика, информационная логистика.

4 «Задача коммивояжера»

5 Постановка задачи Имеется n городов, пронумерованных числами 1,2,..., n. Для любой пары городов (i,j) задано расстояние (время, путевые расходы) C(i,j) 0 между ними. В общем случае C(i,j) C(j,i), причём С(i,i) =. Иногда С(i,j) = при i j, если переезд от города i до города j невозможен или очень дорог.

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

7 Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i, j) – время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.

8 Описанная модель имеет большое прикладное значение: различные её варианты могут возникать, например, в задачах, связанных с развозкой почты, готовой продукции и т.д.

9 Замкнутый маршрут (i1, i2,…,in, i1), проходящий, через каждый город один и только один раз, т.е. набор переездов (дуг) (i1,i2), (i2,i3), …, (in-1,in), (in,i1) называется гамильтоновым циклом или просто циклом, маршрутом коммивояжёра и обозначается через х = (i1,i2), (i2,i3), …, (in-1,in), (in,i1). Гамильтонов цикл

10 Через Т обозначим множество всех гамильтоновых циклов, а через F(x) – издержки цикла Х. Необходимо отыскать такой маршрут х*, что F(x*) = min F(x). x T

11 Для записи постановки задачи в терминах ЗЦЛП (задачи целочисленного линейного программирования) определим переменные следующим образом: х ij = 1, если коммивояжер переезжает и i-го города в j-й; х ij =0, в противном случае. Тогда задача заключается в отыскании значений переменных, удовлетворяющих следующим соотношениям: (1)

12 при условиях (въезд в город j); (2) (выезд из города i); (3), i j, j,i =2,...,n; (4) xij = {0,1},, целые, i =1,...,n, j =1,...,n. (5) Ограничения (4) требуют, чтобы маршрут образовывал контур, т.е. служат для устранения нескольких не связанных между собой маршрутов и циклов.

13 Пример, когда маршрут распадается на два не связанных между собой подцикла

14 Решение Решение описанной выше математической модели можно реализовать с помощью надстройки «Поиск решения» в Excel (см. пример «6_Задача коммивояжера.xlsx»). Кроме того задача может быть решена методом ветвей и границ. Выбирайте любой удобный для вас способ.

15 Применение метода ветвей и границ для решения задачи коммивояжера Допустимый маршрут х представим как множество упорядоченных пар городов:. Длина F(х) маршрута х равна сумме соответствующих элементов C(i,j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов. Обозначим через матрицу расстояний. Чтобы запретить переезды вида (i,i) положим С(i,i) = + (i = 1,…, n).

16 Обозначим через Z 0 = F(x 0 ) верхнюю границу длин всех маршрутов, т.е. F(x*) Z 0, где x* - оптимальный гамильтонов цикл (маршрут). Определить F(x 0 ) можно, отыскав какой- либо произвольный допустимый маршрут коммивояжёра и подсчитав его издержки. Например, допустимым будет являться следующий гамильтонов цикл x 0 = (1,2); (2,3); (3,4); ((4,5); (5,1).

17 Пусть Тогда – редуцированная матрица. Пусть – сумма констант редуцирования.

18 Тогда для любого маршрута справедливо = = d(х) Это неравенство показывает, что в качестве нижней оценки издержек любого цикла х на множестве Т можно взять суммарную константу приведения d(х) матрицы С.

19 Ветвление Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся подмножеством множества Х. При этом начальная вершина соответствует множеству всех маршрутов Х. На каждом шаге из числа кандидатов на ветвление выбирается множество Х 1 с наименьшей оценкой. Оно разветвляется на два подмножества и. Подмножество состоит из всех маршрутов множества Х 1 содержащих некоторую выбранную на данном шаге дугу (r, s), подмножество, – из всех маршрутов множества Х 1, не содержащих дуги (r,s).

20 Ребро дерева, соединяющее вершины Х 1 и, помечается (r,s), а ребро дерева, соединяющее Х1 и помечается.

21 Ясно, что для разбиения лучше выбирать множество с минимальной нижней оценкой, так как вероятнее всего именно в нём содержится оптимальный цикл х*. Дугу (r,s) будем выбирать из следующих соображений: С одной стороны, издержка с rs должна быть как можно меньше, чтобы в конце концов из всех фиксированных дуг получить гамильтонов цикл, близкий к оптимальному. С другой стороны, будем максимально увеличивать нижнюю оценку d(y) множества, тогда возрастает вероятность того, что для разбиения всякий раз будет выбираться множество, и появится возможность быстрее получить гамильтонов цикл. Если при этом окажется, что его издержки меньше z 0, то z 0 будет скорректирована (уменьшена), а это сократит число просматриваемых циклов.

22 Кроме того, такой подход к выбору дуги (r,s) позволяет сократить объём хранимой в памяти информации, а именно, необходимо иметь исходную матрицу издержек С(Т), рабочую матрицу C ( ) и информацию о каждом множестве: его нижнюю оценку издержек и все фиксированные и запрещённые для него дуги. Если в процессе решения задачи нужно будет разбивать множество, отличное от, то соответствующую ему матрицу издержек можно восстановить их исходной матрицы С(Т) на основании этой информации.

23 Выбор фиксированного переезда (r,s): 1)в приведенной матрице издержек С (Xi) просмотреть все элементы c ij =0; (стремление к уменьшению ) 2)для каждого из них определить величину ij, равного сумме минимального элемента i-той строки и j-го столбца, за исключением самого элемента c ij ;, где (m,v) – дуга, для которой c ij =0.

24 3)выбрать фиксированный переезд (r,s) из условия (стремление увеличить ). Смысл введения функции состоит в том, что величина является оценкой снизу для длины любого маршрута из Х 1, не содержащего дуги (, ), так как величина выражает дополнительное расстояние, которое коммивояжер проезжает в случае, когда в маршрут не включена дуга (, ).

25 Построение редуцированных матриц и и вычисление оценок снизу Рассмотрим, как на произвольной итерации получить матрицы и, если известны матрица и дуга (r,s).

26 Схема получения матрицы Так как дуга (r,s) не должна входить ни в один гамильтонов цикл, принадлежащий множеству, то в матрице полагаем с rs =. Приводим матрицу, получим. Сумма констант редуцирования равна при этом. Нижняя граница издержек для множества определится по формуле

27 Схема получения матрицы Так как дуга (r,s) уже входит в любой гамильтонов цикл, принадлежащий множеству, то согласно постановке задачи необходимо запретить выезд из города r и въезд в город s, поэтому в матрице вычеркиваем строку r и столбец s. Для устранения подциклов необходимо составить из всех дуг, фиксированных для множества, связный путь, обязательно содержащий последнюю фиксированную дугу (r,s). Полагаем в матрице, где t и m – соответственно конец и начало связного пути, в результате получим матрицу.

28 Редуцированная матрица расстояний для вершины получается из матрицы с помощью операции редуцирования. Обозначим через константу приведения (редуцирования) матрицы. Оценка снизу для функции F(x) на множестве вычисляется по формуле

29 Формирование списка кандидатов на ветвление (ответа) После вычисления каждой из оценок (i = 1,2) следует проверить, не состоит ли множество из единственного маршрута: если в каждой строке и в каждом столбце матрицы оказалось лишь по одному элементу, отличному от +, то множество содержит единственный маршрут, длина которого равна. В этом случае верхняя граница (наименьшее из уже вычисленных значений F(x) полагается равной минимуму из предыдущего значения Z 0 и, т.е. Z 0 = min {Z 0, }.

30 иначе… Если содержит более одного маршрута и меньше текущего значения Z 0, то рассматриваемое множество включается в число кандидатов на ветвление. (продолжаем по описанной схеме) Остановка производится, если наименьшая из оценок снизу кандидатов на ветвление не меньше (равна либо превышает) текущего значения Z 0.

31 Решить методом ветвей и границ задачу коммивояжера с матрицей

32 Редуцирование

33 Дерево решений