Использование метода ветвей и границ
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
СОДЕРЖАНИЕ
ЛАБОРАТОРНАЯ
РАБОТА № 1
Тема:
Применение метода «Ветвей и границ» для
решения задачи коммивояжера и задачи
установления оптимальной последовательности
выполнения работ в производстве, сервисе,
длительность которых зависит от очередности
их выполнения на рабочем месте (4 часа).
Цель
работы: изучение комбинаторного метода
решения задач дискретного программирования,
возникающих в производстве, сервисе,
таможенном менеджменте, реализующего
нахождение оптимального решения путем
частичного перебора возможных
решений, и получение практических навыков
в его применении.
ИНДИВИДУАЛЬНОЕ
ЗАДАНИЕ № 1
Имеется 5 городов, которые должен посетить коммивояжер по одному разу, минимизируя пройденный путь, и вернуться в исходный город. Расстояние между городами заданы матрицей А=[aij], i=1,…,5; j=1,…,5 отражены в таблице 1.1.
Таблица 1
| i |
№ последующего города | ||||||
| 1 | 2 | 3 | 4 | 5 | |||
| № предыдущего города | 1 | x | 3 | 6 | 1 | 4 | |
| 2 | 9 | x | 9 | 3 | 8 | ||
| 3 | 7 | 1 | x | 7 | 5 | ||
| 4 | 1 | 4 | 6 | x | 1 | ||
| 5 | 2 | 5 | 1 | 8 | x | ||
Решение
- Шаг А1. В исходной матрице А знак × уже проставлен в клетках главной диагонали матрицы с северо-западного угла до юго-восточного.
- Шаг А2. Приведение матрицы
Таблица 2
| i j | 1 | 2 | 3 | 4 | 5 | hi |
| 1 | x | 2 | 5 | 0 | 3 | 1 |
| 2 | 6 | x | 6 | 0 | 5 | 3 |
| 3 | 6 | 0 | x | 6 | 4 | 1 |
| 4 | 0 | 3 | 5 | x | 0 | 1 |
| 5 | 1 | 4 | 0 | 7 | x | 1 |
Таблица 3
| i j | 1 | 2 | 3 | 4 | 5 | hi |
| 1 | x | 2 | 5 | 0 | 3 | 1 |
| 2 | 6 | x | 6 | 0 | 5 | 3 |
| 3 | 6 | 0 | x | 6 | 4 | 1 |
| 4 | 0 | 3 | 5 | x | 0 | 1 |
| 5 | 1 | 4 | 0 | 7 | x | 1 |
| Hi | 0 | 0 | 0 | 0 | 0 |
- Шаг Б. Вычисление нижней границы
Таблица 4
| i j | 1 | 2 | 3 | 4 | 5 | hi |
| 1 | x | 2 | 5 | 0 | 3 | 1 |
| 2 | 6 | x | 6 | 0 | 5 | 3 |
| 3 | 6 | 0 | x | 6 | 4 | 1 |
| 4 | 0 | 3 | 5 | x | 0 | 1 |
| 5 | 1 | 4 | 0 | 7 | x | 1 |
| Hi | 0 | 0 | 0 | 0 | 0 | 7 |
Нижняя граница (оценка) множества Е равно 7.
(НГЕ=
).
- Шаг В. Выбор претендующей коммуникации на ветвление
Определим дугу, исключение которой максимально увеличило бы полученную оценку. Рассчитаем понижение для элементов (i,j) полученной матрицы, имеющих нулевые значения.
d(1;4)=2+0=2
d(2;4)=5+0=5
d(3;2)=4+2=6
d(4;1)=1+0=1
d(4;5)=3+0=3
d(5;3)=1+5=6
Максимальное
значение понижения рассматриваемых
элементов соответствует
Выбираем
для ветвления пару (5;3).
- Шаг Г. Разделение подмножества (ветвление)
Производим ветвление:
Е=Е(i;j)͝ (i;j), где Е(i;j)={5;3}, (i;j)={ }
Вычислим оценку подмножества (i;j).
Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е и понижения для наиболее перспективного претендента на ветвление, вычисленного на шаге В. Нижняя граница множества полных циклов Е была вычислена на шаге Б. Следовательно:
НГ
(5;3)=НГЕ+d(5;3)=7+6=13
- Шаг Д. Переход к матрице меньшего размера (усечение матрицы)
На этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij)
В приведенной матрице (см. 1.2. шаг А2) матрице вычеркивается пятая строка и третий столбец. Для вновь полученной матрицы повторяется шаг А, то есть осуществляется выставление запрета во избежание образования неполного цикла в клетке 5,3 и проводится ее приведение.
Таблица 5
| i j | 1 | 2 | 4 | 5 | hi | |
| 1 | x | 2 | 0 | 3 | 0 | |
| 2 | 6 | x | 0 | 5 | 0 | |
| 3 | 6 | 0 | 6 | x | 0 | |
| 4 | 0 | 3 | x | 0 | 0 | |
| Hi | 0 | 0 | 0 | 0 |
Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (5;3), как сумма оценки множества Е и значения понижения матрицы, полученного после ее приведения на этом шаге.
НГЕ(5;3)=НГЕ+ 7+0+0=7
Так
как оценка НГЕ(5;3)=7 меньше, чем оценка
НГ
(5;3)=13, то можно считать, что искомый
оптимальный цикл J*
содержит коммуникацию, выбранную в качестве
перспективного претендента на ветвление
(5;3), и можно осуществлять дальнейшее ветвление
дерева из вершины (5;3).
- Шаг Е. Построение графа искомого цикла
Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами из подмножества Е(i;j) и (i;j).
- Шаг Ж. Продолжение ветвления
Далее
проводятся те же действия, что и на шагах
В, Г, Д, Е.
2.1.Шаг В. Выбор претендующей коммуникации на ветвление
Определим дугу, исключение которой максимально увеличило бы полученную оценку НГЕ(5;3). Рассчитаем понижение для элементов (i;j) полученной матрицы, имеющих нулевые значения.
d(1;4)=2+0=2
d(2;4)=5+0=5
d(3;2)=4+2=6
d(4;1)=0+6=6
d(4;5)=0+3=3
Максимальную оценку имеют две пары претендентов на ветвление, а именно: (3;2) и (4;1). В случае равенства максимальных значений для нескольких претендентов выбор из них перспективной коммуникации на ветвление осуществляется произвольно.
Выбираем
для ветвления пару (3;2).
2.2.Шаг Г. Разделение на подмножества (ветвление)
Произведем ветвление Е(5;3):
Е(5;3)=Е(i;j)͝ (i;j),
где Е(i;j)={(5;3),(3;2)}, (i;j)={( }
Вычислим оценку подмножества (i;j).
Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е(5;3) и понижения для наиболее перспективного претендента на ветвление, вычисленного в 2.1. на шаге В. Нижняя граница множества полных циклов Е(5;3) была вычислена в 1.6. на шаге Б. Следовательно:
НГ
(5;3),(3;2)=НГЕ(5;3)+d(3;2)=7+
2.3.Шаг Д. Переход к матрице меньшего размера (усечение матрицы)
На этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij).
В
приведенной см 1.6. матрице вычеркивается
третья стока и второй столбец. Для
вновь полученной матрицы повторяется
шаг А.
Таблица 6
| i j | 1 | 4 | 5 | hi | ||
| 1 | x | 0 | 3 | 0 | ||
| 2 | 6 | 0 | x | 0 | ||
| 4 | 0 | x | 0 | 0 | ||
| Hi | 0 | 0 | 0 |
Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (3;2), как сумма оценки множества Е(5;3) и значения понижения матрицы, полученного после ее приведения на этом шаге.
НГЕ(5;3)(3;2)=НГЕ(5;3)+ 7+0+0=7
Так
как оценка НГЕ(5;3)(3;2)=7 меньше, чем
оценка НГ
(5;3)(3;2)=13, то стоим графу искомого цикла.
2.4. Шаг Е. Построение графа искомого цикла
Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами из подмножества Е(i;j) и (i;j).
5.1.Шаг В. Выбор претендующей коммуникации на ветвление
Определим дугу, исключение которой максимально увеличило бы полученную оценку. Рассчитаем понижение для элементов (i;j) полученной матрицы, имеющих нулевые значения.
d(1;4)=3+0=3
d(2;4)=0+5=5
d(4;1)=6+0=6
d(4;5)=5+0=5
Максимальное
значение понижения рассматриваемых
элементов соответствует
5.2.Шаг Г. Разделение на подмножества (ветвление)
Произведем ветвление Е(3;2):
Е(3;2)=Е(i;j)͝ (i;j),
где Е(i;j)={(5;3),(3;2)(4;1)}, (i;j)={( }
Вычислим оценку подмножества (i;j).
Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е(3;2) и понижения для наиболее перспективного претендента на ветвление, вычисленного в 5.1. на шаге В. Нижняя граница множества полных циклов Е(3;2) была вычислена в 2.3. на шаге Д. Следовательно:
НГ
(5;3),(3;2),(4;1)=НГЕ(5;3)(3;
5.3.Шаг Д. Переход к матрице меньшего размера (усечение матрицы)
На этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij).
В
приведенной (см 2.3.) матрице вычеркивается
четвертая стока и первый столбец. Для
вновь полученной матрицы повторяется
шаг А.
Таблица 7
| i j | 4 | 5 | hi | |||
| 1 | 0 | 3 | 0 | |||
| 2 | 0 | x | 0 | |||
| Hi |
Таблица 8
| i j | 4 | 5 | hi | |||
| 1 | 0 | 0 | 0 | |||
| 2 | 0 | x | 0 | |||
| Hi | 0 | 3 |
Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (4;1), как сумма оценки множества Е(3;2) и значения понижения матрицы, полученного после ее приведения на этом шаге.
НГЕ(5;3)(3;2)(4;1)=НГЕ(3;
Так
как оценка НГЕ(5;3)(3;2)(4;1)=10 меньше, чем
оценка НГ
(5;3)(3;2)(4;1)=13, то можно осуществлять ветвление
дерева из вершины (4;1).
5.4.Шаг Е. Построение графика искомого цикла
Разбиение
множества всех полных циклов Е на
непересекающиеся подмножества графически
изображается деревом ветвей с вершинами
из подмножества Е(i;j) и
(i;j).
6.1.Шаг В. Выбор претендующей коммуникации на ветвление
Остались
пары: (1;4),(1;5),(2;4). Все они равны нулю, поэтому
дальше соединяем график маршрутов.
7.1. Шаг В. Выбор претендующей коммуникации на ветвление.
Искомый полный оптимальный цикл J включает коммуникации:
J={(5;3),(3;2)(4;1)(2;4)(
Имеет длину F(J)=10, а последовательность объезда городов, если коммивояжер находился в городе 5, можно представить в виде:
5
− 3 − 2 − 4 − 1 − 5.
Выполним проверочный расчет для полученной последовательности. По исходной матрице посчитаем F(J):
F(J):1+1+1+3+4=10.
Результат тот же, что и расчетный, следовательно
расчеты выполнены правильно.

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