Урок №11

Урок №11. "Методы оптимального планирования"

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

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

Итак, для того, чтобы более наглядно понять, что же такое планирование. Рассмотрим конкретную задачу.

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

Итак, для решения этой задачи существует несколько алгоритмов.

Первый называется "Жадный алгоритм".

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

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Пусть коммивояжер стартует из города 1. Алгоритм «иди вы ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по самой длинной (дорогой). В результате получится не кратчайший, а длиннейший тур.

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

Второй алгоритм - это "Деревянный алгоритм".

Этот алгоритм решает задачу путем построения кратчайшего остовного дерева.

Опишем решающий задачу деревянный алгоритм.

1.Построим на входной сети ЗК кратчайшее остовное дерево и удвоим все его ребра. Получим граф G– связный и с вершинами, имеющими только четные степени.

2.Построим эйлеров цикл G, начиная с вершины 1, цикл задается перечнем вершин.

3.Просмотрим перечень вершин, начиная с 1, и будем зачеркивать каждую вершину, которая повторяет уже встреченную в последовательности. Останется тур, который и является результатом алгоритма.

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

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

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

Рассмотрим конкретную задачу, итак на рисунке имеем транспортную сеть коммивояжера.

Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам), а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, приведенную по столбцам. Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34. Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура.

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

Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на таблице правее и выше нуля (оценки нуля, равные нулю, не ставились). Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.

Что касается первого класса, то в нем надо рассмотреть матрицу на таблице 4 с вычеркнутой первой строкой и вторым столбцом.

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

Кружки представляют классы: верхний кружок – класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2); нижний правый – класс всех туров, не включающих ребро (1,2). Числа над кружками – оценки снизу.

Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C[1,2] в таблице.

Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины есть 35+3=38. Для оценки левой нижней вершины на рис. 2 нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] в таблице.

В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3).

Эта матрица приводится по столбцу на 1, таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6) .

Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается.

Оценивая нули в матрице на табл. 8, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на таблице 9.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур.

Теперь давайте рассмотрим программу, решающую нашу задачу методом "Ветвей и границ".

Для начала ознакомьтесь с интерфейсом программы.

Для решения задачи в выпадающем меню выберете необходимое количество городов. На экране появится таблица. Заполните ее.

Для того, чтобы найти решение, необходимо нажать кнопку "Найти путь". На экране появится дерево решения.

Данные в таблице можно редактировать, выделив нужную ячейку двойным щелчком мыши и заменив значение. Либо просто нажав кнопку "Сброс всех значений".

После ознакомления с программой проверьте с ее помощью решение задачи.

Практический

материал

Решить задачи методом ветвей и границ и проверить свое решение с помощью программы.

Задание №1.

Дана матрица:

- | 1 | 2 | 3 | 4
1 | - | 0 | 3 | 4
2 | 6 | - | 5 | 1
3 | 7 | 4 | - | 5
4 | 7 | 3 | 3 | -

Задание №2.

Дана матрица:

- | 1 | 2 | 3 | 4 | 5
1 | - | 8 | 5 | 7 | 9
2 | 0 | - | 6 | 1 | 3
3 | 7 | 8 | - | 3 | 5
4 | 9 | 8 | 5 | - | 2
5 | 2 | 3 | 4 | 8 | -

Практическая работа

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

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами.

Деревянный алгоритм - это алгоритм, который решает задачу путем построения кратчайшего остовного дерева.

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

Основные определения

1. Что такое «оптимальное планирование»? 2. Что представляет собой задача коммивояжера? 3. Объясните в чем состоит суть деревянного алгоритма. Покажите его работу на своем примере. 4. На чем основан метод «ветвей и границ»? |  | Контрольные вопросы