Содержание
- 2. Предметом ТЛ является комплекс задач, связанный с организацией перемещения грузов транспортом общего назначения. В области ТЛ
- 3. Задачи ТЛ решаются во взаимной связи с другими задачами логистики, такими, как производственная логистика (ПС), складская
- 4. «Задача коммивояжера»
- 5. Постановка задачи Имеется n городов, пронумерованных числами 1,2,..., n. Для любой пары городов (i,j) задано расстояние
- 6. Постановка задачи Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться
- 7. Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из
- 8. Описанная модель имеет большое прикладное значение: различные её варианты могут возникать, например, в задачах, связанных с
- 9. Замкнутый маршрут (i1, i2,…,in, i1), проходящий, через каждый город один и только один раз, т.е. набор
- 10. Через Т обозначим множество всех гамильтоновых циклов, а через F(x) – издержки цикла Х. Необходимо отыскать
- 11. Для записи постановки задачи в терминах ЗЦЛП (задачи целочисленного линейного программирования) определим переменные следующим образом: хij=
- 12. при условиях (въезд в город j); (2) (выезд из города i); (3) , i ≠ j,
- 13. Пример, когда маршрут распадается на два не связанных между собой подцикла
- 14. Решение Решение описанной выше математической модели можно реализовать с помощью надстройки «Поиск решения» в Excel (см.
- 15. Применение метода ветвей и границ для решения задачи коммивояжера Допустимый маршрут х представим как множество упорядоченных
- 16. Обозначим через Z0 = F(x0) верхнюю границу длин всех маршрутов, т.е. F(x*) ≤ Z0 , где
- 17. Пусть Тогда – редуцированная матрица. Пусть – сумма констант редуцирования.
- 18. Тогда для любого маршрута справедливо = = ≥ d(х) Это неравенство показывает, что в качестве нижней
- 19. Ветвление Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся
- 20. Ребро дерева, соединяющее вершины Х1 и , помечается (r,s), а ребро дерева, соединяющее Х1 и помечается
- 21. Ясно, что для разбиения лучше выбирать множество с минимальной нижней оценкой, так как вероятнее всего именно
- 22. Кроме того, такой подход к выбору дуги (r,s) позволяет сократить объём хранимой в памяти информации, а
- 23. Выбор фиксированного переезда (r,s): в приведенной матрице издержек С′(Xi) просмотреть все элементы c′ij =0; (стремление к
- 24. выбрать фиксированный переезд (r,s) из условия (стремление увеличить ). Смысл введения функции состоит в том, что
- 25. Построение редуцированных матриц и и вычисление оценок снизу Рассмотрим , как на произвольной итерации получить матрицы
- 26. Схема получения матрицы Так как дуга (r,s) не должна входить ни в один гамильтонов цикл, принадлежащий
- 27. Схема получения матрицы Так как дуга (r,s) уже входит в любой гамильтонов цикл, принадлежащий множеству ,
- 28. Редуцированная матрица расстояний для вершины получается из матрицы с помощью операции редуцирования. Обозначим через τ константу
- 29. Формирование списка кандидатов на ветвление (ответа) После вычисления каждой из оценок (i = 1,2) следует проверить,
- 30. иначе… Если содержит более одного маршрута и меньше текущего значения Z0, то рассматриваемое множество включается в
- 31. Решить методом ветвей и границ задачу коммивояжера с матрицей
- 32. Редуцирование 0 0 9 12 0
- 34. Скачать презентацию