Задача о коммивояжере

• Метод ветвей и границ;

      Метод ветвей и границ предложен в 1963 году группой авторов Дж. Литлом, К. Мурти, Д. Суини, К. Кэролом. Широко используемый вариант поиска с возвращением, фактически является лишь специальным частным случаем метода поиска с ограничениями. Ограничения в данном случае основываются на предположении, что на множестве возможных и частичных решений задана некоторая функция цены и что нужно найти оптимальное решение, т.е. решение с наименьшей ценой. Для применения метода ветвей и границ функция цены должна обладать тем свойством, что цена любого частичного решения не превышает цены любого расширения этого частичного решения (Заметим, что в большинстве случаев функция цены неотрицательна и даже удовлетворяет более сильному требованию).[11]

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

      В основе метода ветвей и границ лежит  идея последовательного разбиения  множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.[1]

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

• Метод генетических алгоритмов;

      «Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований.

      Генетический  алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.[11]

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

• алгоритм муравьиной колонии.

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

      1.3 Решение задачи коммивояжера при помощи надстройки MS Excel «Поиск решения» 

      Мощным  средством анализа данных MS Excel является надстройка «Поиск решения». С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки, данные которых, определяют значение целевой ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета. [10]

      Программа Поиск решений – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения  определенных систем уравнений, линейных и нелинейных задач оптимизации, используется с 1991 года.

      Размер  задачи, которую можно решить с  помощью базовой версии этой программы, ограничивается такими предельными  показателями: количество неизвестных (decision variable) – 200; количество формульных ограничений (explicit constraint) на неизвестные  – 100; количество предельных условий (simple constraint) на неизвестные – 400.

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

      «Сотруднику компании ООО «Новые технологии» Петрову Н.И. необходимо обновить программный продукт автоматизированного учета в пяти организациях: А, Б, В, Г и Д. Он решил начать свой обход с организации «А», так как она находится на первом этаже дома, в котором проживает Петров. Сотруднику необходимо, спланировать свой маршрут таким образом, чтобы к концу рабочего дня обойти все организации в определенном порядке и выполнив свою работу, вернутся домой (в пункт «А»). В каком порядке Петрову  следует обходить организации, чтобы его замкнутый тур был кратчайшим? Если расстояния между каждой парой организаций заданы следующей квадратной матрицей (5x5): 

             

            Решение: Разместим исходные данные на рабочем листе, изображенном на рисунке 2. Заменим знак   числом 10000 (на результат решения исключение пути не оказывает влияния).

        
 
 
 
 
 
 
 
 
 
 
 
 
 

      Рисунок 2 - Исходные данные задачи 

      Вводим формулы в таблицу 1. 
 
 
 
 

      Таблица 1 – Расчетные формулы

 

      Сценарий  решения:

      1. Запускаем надстройку MS Excel «Поиск решения» командой Сервис/ Поиск решения. И заполняем окно «Поиск решений», изображенное  на рисунке 2.2.

      2. Для того чтобы выполнялись  условия однократного посещения  сотрудником организаций и в то же время запланированный Петровым маршрут был пройден полностью, введем ограничения: в строки B9, G4 заводим формулы из таблицы 1 и распространяем их на соответствующие диапазоны B9:F9 и G4:G8. Задаем следующие данные $B$9:$F$9=1 и $G$4:$G$8=1 в Ограничения окна «Поиск решения». Таким образом, мы можем отследить порядок обхода организаций сотрудником, оценить правильность выбора и оптимальность его маршрута.

      3. Выбираем ячейку B19 и устанавливаем ее адрес в Целевую ячейку окна «Поиск решения», чтобы определить длину наикратчайшего маршрута. Для этого в ячейку B19 предварительно заносим соответствующую формулу из таблицы 1. Когда программа «Поиск решения» вычислит оптимальный маршрут Петрова и станет известен порядок обхода организаций (из Матрицы переменных) будут известны и расстояния между конкретными парами организаций. Затем при помощи простых математических подсчетов программа рассчитает протяженность оптимального маршрута.

            4. Устанавливаем  еще одно ограничение в окно «Поиск решения»: $E$19=0. В указанную ячейку вводим формулу из таблицы 1 и исключаем таким образом, заведомо ложный порядок движения Петрова в порядке обхода организаций.

            5. В связи с  тем, что ячейки  диапазона   B4:F8 – изменяемые, в Ограничение окна «Поиск решения» необходимо добавить строку B$4$:F$8$=двоичное.  

            6. Заводим в ячейки B23; B24; B25; B26 соответствующие формулы из таблицы 1 и распространяем их на следующие диапазоны: B23:E23 B24:E24; B25:E25; B26:E26 для учета всех возможных вариантов обхода организаций сотрудником и выбора из них оптимального. Формулы задаем таким образом, чтобы обеспечить исключение ложного пути, соблюдая условие задачи об обходе всех организаций по одному разу.

      7. Добавляем в Ограничения окна «Поиск решения» $B$23:$E$26 ≤ 3.

        
 
 
 
 
 
 
 

      Рисунок 3 - Окно «Поиск решения» 

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

        
 
 
 
 
 
 
 
 
 
 
 

      Рисунок 4 - Окно «Параметры поиска решения» 

      Таким образом, получаем следующий результат. Если Петров переходит  из организации в организацию, то на рисунке 5 в диапазоне B4:F8 мы будем наблюдать порядок его перемещений. Если видим, что в ячейке, которая отнесена к организации «В» стоит единица, значит сотрудник посетил эту организацию следующей за пунктом «А». Если в ячейке ноль – сотрудник организацию не посещал.   
 
 
 
 

        
 
 
 
 
 
 
 
 

Рисунок 5 - Результаты решения задачи коммивояжера 

      В ходе анализа полученных результатов, приходим к выводу: наиболее оптимальным  маршрут Петрова будет в том  случае, если он начал свой путь с  организации «А», посетит другие организации в следующем порядке «В», затем «Д», далее «Б» и «Г», из которой вернется к началу своего пути (в организацию «А»). представим путь схематически:

                                                   А’В’Д’Б’Г’А

      Длина кратчайшего маршрута (значение целевой ячейки) в результате составит – 21.  

      Задание 2. Решение задач 

      Задача 1. Решить графическим методом типовую задачу оптимизацию 

      Фирма выпускает 2 набора удобрений для  газонов: обычный и улучшенный. В  обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений.  Известно, что для газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 денежных единицы, а улучшенный – 4 денежных единицы. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

      Построить экономико-математическую модель задачи, дать необходимые комментарии к  ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум и почему?

      Решение:

      Сведем  данные задачи в таблицу 2.

      Таблица 2 – Исходное задание,  сведенное  в табличную форму