1. Строятся вершины первого уровня. Для них подсчитывается оценка ψ( ) 2. Ветвится вершина, которой соответствует лучшая оценка. Подсчитываются оценки. - презентация

1

2

3 1. Строятся вершины первого уровня. Для них подсчитывается оценка ψ( ) 2. Ветвится вершина, которой соответствует лучшая оценка. Подсчитываются оценки для вершин второго уровня. 3. Среди «висячих» вершин 1 и 2 уровней выбирается вершина с наилучшей оценкой и производится ее ветвление. 4. Аналогично на k-ом уровне среди «висячих» вершин выбираем вершину с наилучшей оценкой и ветвим ее. Действие продолжается до последнего n-ого уровня. Оптимальное решение соответствует вершине, для которой значение ψ самое большое.

4 Решаем задачу симплекс методом или графически. В итоге получаем: Так как решение нецелочисленное, то произведем ветвление: возьмем нецелочисленную переменную и проведем разбиение множества на два подмножества.

5 Получаем: Так как решение нецелочисленное, то производим ветвление первого решения (решения с наибольшей оценкой). Получаем ответ: Ответ: L(x)=29, x1=2, x2=5

6

7 Пусть известны расстояния между городами. Поскольку минимальное расстояние между городами равно 1 и число шагов равно 5, в качестве оценки возьмем ψ( )=5. Произведем ветвление первого уровня: Ψ( )=4+min( ), j=3,4,5 Ψ( )=9+ min(11;8;1)+3*1=13 Ψ( )=6+min(4;3;8)+3=12 Ψ( )= 1+min(11;8;1)+3=5 Далее производим ветвление вершин второго уровня. Среди «висячих» вершин выбираем наименьшую оценку и производим ее ветвление и т.д. до последнего этапа, пока не получим наименьшее решение.

8 Ответ :

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

10 1. Вводим ограничения для элементов матрицы по строкам и столбцам (сумма по строкам и столбцам равна 1). Сумма элементов главной диагонали равна Если не удается найти оптимальный путь, то ставим ограничения, что коммивояжер не может вернуться в пройденный уже путь. 3. Если оптимальный путь не найден ( коммивояжер посетил не все пункты до возвращения в начальный пункт), то ставим ограничение, что сумма n элементов полученного пути меньше, либо равна (n-1). Повторяем действие до тех пор, пока не будет получен оптимальный путь.

11

12