9.5. Практикум. Планирование маршрутов патрульно-постовой службы

 

Цель практического занятия:

1.    Закрепление и углубление теоретических знаний по теме.

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

3.    Совершенствование навыков использования ЭВТ для моделирования задач управления.                           

Учебные вопросы:

1.    Постановка задачи и построение математической модели планирования патрульно-постовой службы в ОВД.

2.    Выбор и обоснование метода решения.

3.     Решение задачи определения оптимальных маршрутов.

9.5.1. Постановка задачи планирования патрульно-постовой службы в ОВД

 

Пусть дана матрица расстояний между объектами патрулирования:

 

             1  2  3  4

          0  7  1  6  3

          1  -  2  4  8

    T =   2  1  -  3  2   .

          3  5  1  -  4

          4  2  2  3  -

 

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

 

9.5.2. Выбор и обоснование метода решения

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

1.    Строится первоначальная перестановка ,  элементы которой упорядочены по возрастанию, и определяется ;

2.    ₁(1,2,3,4)=7+2+3+4=16;

3.    В перестановке  находится обрывающее число e=3;

4.    В  (=(i₄)) находится минимальный элемент больший числа e, т. е. min i₄>e. Эти элементы меняются местами, i₃ на i₄;

5.    ₂(1,2,4,3)=7+2+2+3=12;

6.     Если ₂)< ₁), , то ₂) берется за      наилучшее и алгоритм повторяется с пункта 2.

 Снова находится обрывающее число e. На данном шаге e=2. В =(i₃,i₄) находится минимальный элемент больший числа e, min=3. Эти элементы меняются местами. Затем элементы  упорядочиваются по возрастанию, =(1,3,2,4).

₃(1,3,2,4)=7+4+1+2=14

    И так далее.

₄(1,3,4,2)=7+4+4+2=17

₅(1,4,2,3)=7+8+2+3=20

₆(1,4,3,2)=7+8+3+1=19

₇(2,1,3,4)=1+1+4+4=10

₈(2,1,4,3)=1+1+8+3=13

₉(2,3,1,4)=1+3+5+8=17

₁₀(2,3,4,1)=1+3+4+2=10

₁₁(2,4,1,3)=1+2+2+4=9

₁₂(2,4,3,1)=1+2+3+5=11

₁₃(3,1,2,4)=6+5+2+2=15

₁₄(3,1,4,2)=6+5+8+2=21

₁₅(3,2,1,4)=6+1+1+8=16

₁₆(3,2,4,1)=6+1+2+2=11

₁₇(3,4,1,2)=6+4+2+2=14

₁₈(3,4,2,1)=6+4+2+1=13

₁₉(4,1,2,3)=3+2+2+3=10

₂₀(4,1,3,2)=3+2+4+1=10

₂₁(4,2,1,3)=3+2+1+4=10

₂₂(4,2,3,1)=3+2+3+5=13

₂₃(4,3,1,2)=3+3+5+2=13

₂₄(4,3,2,1)=3+3+1+1=8

    Просмотрены все возможные варианты маршрутов и найдено оптимальное решение ₂₄=8, =(4,3,2,1).

 Метод ближайшей точки. Алгоритм метода ближайшей точки изложен в п.10.4.4. Полученное с помощью этого метода решение:

              =(2,1,3,4), =1+1+4+4=10.

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

Метод ветвей и границ. Порядок решения задачи на основе алгоритма ветвей и границ имеет следующий вид:

1.      Обнуление шага U=0;

2.      На U (на 0) шаге множество маршрутов разбивается на m-U (на m) подмножеств;

3.      Определяется нижняя граница каждого из подмножеств

g₀₁=7+1+2+2=12

g₀₂=1+1+2+4=8

g₀₃=6+1+1+2=10

g₀₄=3+1+1+2=7

7

10,,00

1222

8

                   

 

 

 

 

4.      Из нижних границ выбирается минимальная, g₀₄=7;

5.      Т. к.  еще не определена и не выполняется условие g₀₄>, то U увеличивается на 1 и осуществляется переход на пункт 2, т. е. ветвится подмножество с номером i_U+1=4.

 

 

 

 

 

 

 

 

 

Определяются нижние границы построенных подмножеств:

g₄₁=3+2+1+2=8

g₄₂=3+2+1+4=10

g₄₃=3+3+1+1=8

Из этих нижних границ выбирается минимальная, в данном случае min=g₄₁=8  и ветвится подмножество с номером 1:

Определяются нижние границы подмножеств 2 и 3:

g₁₂=3+2+2+3=10

g₁₃=3+2+4+1=10

 

 

 

 

 

 

 

 

 

 

Из этих границ выбирается минимальная и, т. к. шаг равен m-1, то эта нижняя границ берется за наилучшее значение, т. е. найдена =g₁₂=10. Затем просматривается дерево решений в поисках границы меньшей, чем первое приближение, т. е. g_n<. Такая граница существует и ветвится подмножество соответствующей границы.

Определяются нижние границы подмножеств 1 и 2:

g₃₁=3+3+5+2=13

g₃₂=3+3+1+1=8

 

 

 

 

 

 

 

 

 

 

 

 

6.      На m-1 (на 3) шаге определяется . Если  не было ранее определено или новое значение меньше предыдущего, то это значение берется за наилучшее и осуществляется переход на подпункт 5.1. по алгоритму метода ветвей и границ.  Т. к. шаг равен m-1, полученная минимальная граница меньше первого приближения g₃₂< и веток с меньшей границей в дереве решений нет, то полученное значение =g₃₂=8 является решением данной задачи =(4,3,2,1).

 

Графический метод построения S перестановок. Пусть дана матрица расстояний:

             

   1  2  3

           0   4  2  1

           1   -  6  7

     T =   2   3  -  1  

           3   4  5  -

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

Строится дерево решений и на m шаге определяется  каждой перестановки:

₁(1,2,3)=4+6+1=11

₂(1,3,2)=4+7+5=16

₃(2,1,3)=2+3+7=12

₄(2,3,1)=2+1+4=7

₅(3,1,2)=1+4+6=11

₆(3,2,1)=1+5+3=9.

Из всего множества решений находится минимальное, которое и будет оптимальным решением задачи. В данном примере решением задачи является U₄=7, =(2,3,1).

 

 

 

 

 

 

 

 

 

         

               Рис. 9.5. Множество вариантов решений при m=3

Предыдущая | Главная | Глава 9 | Следующая