Санкт-Петербургский университет ГПС МЧС России.

Ключевые слова:задача коммивояжера, ориентированный граф, алгебра логики, оптимальное решение

"COMPUTER SIMULATION OF THE TRAVELING SALESMAN PROBLEM IN THE ACTIVITIES OF THE DEPARTMENTS OF EMERCOM OF RUSSIA»

E. U.Morozova

Saint-Petersburg University of state fire service of EMERCOM of Russia;

E. N. Trofimets candidate of pedagogical Sciences, associate Professor

Saint-Petersburg University of state fire service of EMERCOM of Russia

.

The article is devoted to a solution, findings of the optimum way minimizing costs of driving through the Leningrad region inspector of State fire supervision an objective solution as problems of linear integer programming Examines the use of the traveling salesman problem in the tax office.

Key words: the task of the inspector, a directed graph, algebra logic, the optimal solution

В ХХI пробки на дороге стали неотъемлемой частью современных городов, в особенности это касается мегаполисов. Даже трудно себе представить, что можно свободно добраться до работы в час пик, не потратив при этом очень много времени. С данной проблемой сталкивается огромное количество людей. Рассмотрим проблему основанную на нерациональном использовании времени и несоответствующей организации перемещения из одного места в другое. А именно, проанализируем ее на перемещении инспектора Государственного пожарного надзора (ГПН) по Адмиралтейскому району, с целью контроля за соблюдением требований пожарной безопасности и пресечения их нарушений и возвращении его в точку отправления, то есть в Главное управления (ГУ) министерства РФ по делам Гражданской обороны(ГО), ЧС и ликвидации последствий стихийных бедствий по Санкт-Петербургу.

Главной особенностью данной работы является определение оптимального пути коммивояжера. Коммивояжёр (фр. commisvoyageur) — разъездной сбытовой посредник, который, перемещаясь по рынку, играет роль простого посредника или действует по поручению своего клиента. В роли коммивояжера мы будем рассматривать инспектора ГПН. Инспектор Государственного пожарного надзора - должностное лицо Государственной противопожарной службы, наделённое в соответствии с действующим законодательством и нормативными правовыми актами Государственной противопожарной службы полномочиями по осуществлению государственного пожарного надзора. Функциями которого является учет объектов надзора, проведение проверок на объектах надзора, расположенных на обслуживаемой территории, дознание по делам о пожарах на соответствующей территории, лицензионный контроль за соблюдением лицензиатом лицензионных требований и условий и т.д.

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

1. Минимизация расхода времени для перемещения инспектора через указанные объекты, по одному разу, с последующим возвращением в исходный объект пункт.

2. Маршрут должен проходить через один объект только один раз. В этом случае нужно использовать гамильтонов цикл, но прежде всего, разберемся, что же такое граф?

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

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

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

Таблица 1 – Расстояние между объектами, км

В качестве проверяемых объектов за инспектором ГПС по Адмиралтейскому району закреплены:

Объект №1 - Жилой многоквартирный дом ООО «Жилком сервис»;

Объект №2 - Детская библиотека;

Объект №3 - Центр «Адмиралтейский»;

Объект №4 - Школа интернат №2;

Объект №5 - Гимназия №272;

Объект №6 - Школа №278.

Предположим, что инспектор осуществляет перемещение на Renault Koleos, следовательно, необходимо рассчитать расход топлива и потраченных средств во время перемещения. Расход топлива составляет 12 литров на 100 км, 1 литр 95 бензина стоит 37,45 руб. Путем простейших математических действий мы рассчитали объем затраченного топлива и его стоимость на 1 км: 37,45*0,12=4,494 цена топлива на 1 км.

удалить, рассчитанную авторами:

Таблица 2 – Стоимость проезда от объекта№1 до объекта№2, руб

Оптимальным способом решения задачи коммивояжера станет метод алгебры логики. Решение задачи будет рассматриваться в Microsoft Excel [2, 3].

Итак, для начала перенесем таблицу с расстояниями между объектами на рабочий лист Microsoft Excel.(Рис.1)

Рис.1 – Расчет стоимости проезда

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

На языке теории графов - объект, это узел, а участок между парой узлов – дуга. Матрица имеет размерность [6 6], в которой описан ориентированный граф.

x_ij – искомая неизвестная переменная булевого типа: x_ij = 1, если дуга (i, j) принадлежит кратчайшему контуру обхода, x_ij = 0 в противном случае. Исходя из этих данных мы получаем цепь. Далее, переносим матрицу на рабочий лист Microsoft Excel (Рис.2).

Рис.2 – Матрица решений

Кроме n! допустимых гамильтоновых контуров существует множество неполных контуров, которые охватывают лишь определенные группы объектов и вместо одного полного контура можно получить несколько неполных контуров с общей минимальной длиной.

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

Вследствие этого мы ввели дополнительную систему ограничений, выраженную формулой: z_i - z_j + (n -1)x_ij* (n-2), где вектор Z ={z_i} – n- искомых произвольных чисел, которые гарантируют запрет образования неполных циклов, «расплатой» за это является существенное увеличение размеров задачи, z_j = z.

Итог вводимых ограничений:

объекты 1-6 СПБ →Колпино →Красное Село →Гатчина →Большая Ижора →Парголово →Всеволожск → СПБ.

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

Рис.3 –Решение через надстройку «Поиск решения»

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

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

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