Лабораторные работы по Основам теории систем .

Лабораторная работа № 7
                        Телешовой Елизаветы, гр. 726,

            Решение задачи коммивояжера методом ветвей и границ.


  1. Постановка задачи.

      Испекла бабка колобок и поставила его  остывать  на  окошко.  И  решил
колобок, что пока он остывает, он вполне может обежать  лес,  посмотреть  на
лесных жителей и  снова  вернуться  к  деду  и  бабке.  Сказано  –  сделано.
Спрыгнул колобок из  окошка  и  покатился  в  лес.  Помогите  колобку  найти
кратчайший маршрут его  движения  по  лесу,  если  расстояния  между  норами
лесных жителей, а также домом деда и бабки даны в таблице.
|          |Дед и     |Заяц      |Волк      |Медведь   |Лиса      |
|          |бабка     |          |          |          |          |
|Дед и     |0         |6         |4         |5         |2         |
|бабка     |          |          |          |          |          |
|Заяц      |6         |0         |3         |3,5       |4,5       |
|Волк      |4         |3         |0         |5,5       |5         |
|Медведь   |5         |3,5       |5,5       |0         |2         |
|Лиса      |2         |4,5       |5         |2         |0         |


  2. Математическая модель задачи.

      Для решения  задачи  присвоим  каждому  пункту  маршрута  определенный
номер: дед и бабка – 1, заяц – 2, волк  –  3,  медведь  –  4  и  лиса  –  5.
Соответственно  общее  количество  пунктов   .   Далее   введем   
альтернативных переменных , принимающих значение 0, если переход из  i-
того пункта в j-тый не входит в маршрут и  1  в  противном  случае.  Условия
прибытия в каждый пункт и выхода из каждого пункта  только  по  одному  разу
выражаются равенствами (1) и (2).
                              (1)
                              (2)
      Для  обеспечения  непрерывности  маршрута  вводятся  дополнительно   n
переменных  и  дополнительных ограничений (3).
                              (3)
      Суммарная протяженность маршрута F, которую необходимо минимизировать,
запишется в следующем виде:
                        (4)
      В нашем случае эти условия запишутся в следующем виде:
        (1);        (2);
             (3)
       (4)


  3. Решение задачи методом ветвей и границ.

      1) Анализ множества D.
      Найдем оценку  снизу  Н.  Для  этого  определяем  матрицу  минимальных
расстояний по строкам (1 где расстояние минимально в строке).
       => ;
      Аналогично определяем матрицу минимальных расстояний по столбцам.
       => ;
      ;
      Выберем начальный план: . Тогда верхняя оценка:
      .
Очевидно, что , где  означает переход из первого пункта  в  j-тый.
Рассмотрим эти подмножества по порядку.
      2) Анализ подмножества D12.
;
;
;
;
;
      3) Анализ подмножества D13.
;
;
;
;

      4) Анализ подмножества D14.
;
;
;
;
;
      5) Анализ подмножества D15.
;
;
;
;
;
6) Отсев неперспективных подмножеств.
;
      Подмножества D13 и D15 неперспективные. Т.к. , но , то далее
будем рассматривать подмножество D14.
      .
      7) Анализ подмножества D142.
;
;
;
;
;
      8) Анализ подмножества D143.
;
;
;

;
      9) Анализ подмножества D145.
;
;
;
;
;
      10) Отсев неперспективных подмножеств.
;
      Подмножество D143 неперспективное. Т.к.  ,  но  ,  то  далее
будем рассматривать подмножество D145.
      .
      9) Анализ подмножества D1452.
;
;
;
;
;
      9) Анализ подмножества D1453.
;
;
;
;
;
;
Оптимальное решение: .
.
Таким образом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк
– дед и бабка.


-----------------------



































D12

D

D13

D14

D15

D142

D143

D145

D1452

D1453

1 2 3 4 5 6