Метод «ветвей и границ»

Домашнее задание

Тема: Применение метода «ветвей и границ» для решения задачи коммивояжера и задачи установления оптимальной последовательности выполнения работ в производстве, длительность которых зависит от очередности их выполнения на рабочем месте.

Цель работы: изучение комбинаторного метода решения задач дискретного программирования, возникающих в производстве, реализующего нахождение оптимального решения путем частичного перебора возможных решений, и получение практических навыков в его применении.

Методика проведения занятия: изучение студентом учебной группы комбинаторного метода решения задач дискретного программирования, возникающих в производстве – метода «ветвей и границ». Индивидуальное решение методом «ветвей и границ» предложенного преподавателем варианта задачи нахождения минимальной длительности выполнения заданной совокупности работ в производстве, длительность которых зависит от очередности их выполнения на рабочем месте.

Постановка задачи нахождения минимальной длительности выполнения заданной совокупности работ в производстве, длительность которых зависит от очередности их выполнения на рабочем месте.

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

Содержательную постановку указанной задачи сформулируем следующим образом.

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

Любые два наименования деталей из множества образуют пару . Назовем полным циклом набор из таких упорядоченных пар деталей, которые образуют замкнутый маршрут, в котором каждое наименование детали встречается лишь один раз. Каждая пара этого цикла образует коммуникацию замкнутого маршрута. Тогда суммарная трудоемкость для полного цикла , соответствующая матрице , это есть сумма элементов по коммуникациям замкнутого маршрута.

Требуется найти такой полный цикл (замкнутый маршрут), при котором сумма элементов матрицы по коммуникациям найденного маршрута была бы минимальной (чтобы его длина была минимальной), а именно:

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

Эта задача относится к классу комбинаторных задач, объединенных под общим названием «задача коммивояжера».

Для «задачи коммивояжера» число возможных полных циклов определяемых и оцениваемых методом полного перебора равно , где! – факториал. При число полных циклов достаточно значительно, поэтому для решения этой задачи методом полного перебора целесообразно применять компьютер. В 1963 году математик Литл разработал алгоритм решения «задачи коммивояжера» на основе применения метода частичного перебора – метода «ветвей и границ». Идея этого метода состоит в следующем.

Метод «ветвей и границ»

Все множество вариантов полных циклов представляется в теории графов корнем дерева: . Процесс решения основан на разделении (разветвлении) по определенному правилу множества на более мелкие «перспективные подмножества» и вычисления для каждого из них нижней границы [ , ], сравнения полученных оценок и выбора минимальной. Решение осуществляется параллельно в двух направлениях: первое – преобразование матрицы [ C, ] и вычисление нижней границы [ , ]; второе – построение графа.

Рассмотрим многошаговую схему реализации метода «ветвей и границ».

Шаг А. Преобразование матрицы.

А1. Выставление запретов.

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

В исходной матрице [ C, ] знак уже проставлен в клетках главной диагонали матрицы с северо-западного угла до юго-восточного, а также может уже стоять в некоторых других клетках матрицы.

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

А2. Приведение матрицы.

В каждой строке матрицы находится минимальный элемент и вычитается из всех элементов этой строки. В полученной матрице такой же процесс повторяется для столбцов. Вновь полученная матрица называется приведенной. Она содержит в каждой строке и каждом столбце один ноль, а может и больше. Процесс, позволяющий на шаге А2 из неотрицательной матрицы получить приведенную матрицу называется приведением. Оптимальный план задачи коммивояжера с приведенной матрицей является оптимальным и для задачи коммивояжера с исходной матрицей. Длина цикла на приведенной матрице будет меньше длины цикла на исходной матрице на сумму приводящих констант.

Шаг Б. Вычисление нижней границы значений [ , ].

Суммируются все элементы, называемые приводящие константы или константы приведения, которые вычитались на шаге А2. Полученная сумма приводящих констант, называемая понижением матрицы, является нижней границей множества решений Е. Величина понижения для множества решений Е является его оценкой, то есть нижней границей длительности цикла. Это означает, что искомый оптимальный цикл не может иметь длину меньшую, чем полученная величина понижения.

Шаг В. Выбор претендующих коммуникаций на ветвление.

Определим дугу, исключение которой максимально увеличило бы полученную оценку. С этой целью в приведенной матрице рассматриваются все клетки, содержащие нули, то есть все пары , имеющие нулевые значения, и для каждой из них рассчитывается понижение. Понижение любого рассматриваемого элемента , обозначенное через , есть сумма минимального элемента из -ой строки и минимального элемента из -го столбца, не учитывая при этом числовое значение самого элемента . Максимальное значение понижения рассматриваемых элементов соответствует наиболее перспективному претенденту на ветвление. В случае равенства максимальных значений для нескольких претендентов, выбор из них перспективной коммуникации на ветвление осуществляется произвольно.

Шаг Г. Разделение на подмножества (ветвление).

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

Нижняя граница Е

Нижняя граница

Нижняя граница множества полных циклов Е была вычислена на шаге Б.

Оценка (нижняя граница) подмножества равна сумме оценки множества Е и понижения для наиболее перспективного претендента на ветвление, вычисленного на шаге В. Оценка подмножества вычисляется на следующем шаге (шаге Д).

Шаг Д. Переход к матрице меньшего размера (усечение матрицы).

В приведенной матрице на шаге А2 вычеркивается строкаи столбец, содержащие наиболее перспективную коммуникацию. Получается матрица, размер которой на единицу меньше от приведенной на шаге А2. Для вновь полученной матрицы повторяется шаг А, то естьосуществляется выставление запрета во избежание образования неполного цикла и проводится ее приведение, а также выполняется шаг Б, то есть вычисляется оценка подмножества , содержащего перспективную коммуникацию на ветвление , как сумма оценки множества Е и значения понижения матрицы, полученного после ее приведения на этом шаге.

Если оценка подмножества меньше, чем оценка подмножества , то можно считать, что искомый оптимальный цикл содержит коммуникацию, выбранную в качестве перспективного претендента на ветвление на шаге В и можно осуществлять дальнейшее ветвление дерева из вершины . В противном случае производится возврат к исходной матрице, в которой ставится запрет в соответствующей «неудачной» клетке и весь процесс поиска минимального цикла повторяется сначала.

Шаг Е. Построение графа искомого цикла.

На графе, полученном на шаге Г, проставляется у вершины оценка, вычисленная на шаге Д.