Главная Коллекция "Otherreferats" Программирование, компьютеры и кибернетика Сетевые модели

Сетевые модели

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 28.09.2017
Размер файла 198,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Томский межвузовский центр дистанционного образования

Томский государственный университет

систем управления и радиоэлектроники (ТУСУР)

Кафедра компьютерных систем в управлении и проектировании

Контрольная работа № 2 по дисциплине

«Автоматизированные информационно-управляющие системы»

«Автоматизированное управление в технических системах»

г. Ноябрьск 2012

СЕТЕВЫЕ МОДЕЛИ

Транспортная задача.

Записать математическую модель транспортной задачи с промежуточными пунктами, заданной сетью на рис.1 и таблицей 1.

Размещено на http://www.allbest.ru/

Рис. 1 Сеть транспортной задачи с промежуточными пунктами

Таблица 1

Данные варианта

i

1

2

3

4

5

6

7

8

A1

A2

A3

A4

A5

A6

A7

c12

5

8

4

5

7

5

1

7

i

9

10

11

12

13

14

15

16

c13

c14

c23

c25

c26

c34

c35

c36

6

6

2

4

8

6

4

5

i

17

18

19

20

21

22

23

24

c37

c46

c47

c56

c58

c67

c68

c78

6

3

2

4

9

3

8

5

Найти оптимальное решение задачи из п.1.1.

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

1.3. Произвести анализ на чувствительность задачи из п.1.1.

1.3.1. Найти наименьшее значение каждого из коэффициентов C25 и C47 в исходной сети с промежуточными пунктами, при которых прежнее решение остается оптимальным.

1.3.2. Допустим, что один избыток запасов Ai (i=1,3,5,7) увеличился на . Найти приращение целевой функции при =1, а также предельное значение , при котором прежнее решение остается оптимальным.

Примечание. Для каждого Ai (i=1,3,5,7) показать цикл перераспределения на матрице условий.

1.3.3. Допустим, что один избыток запасов Ai (i=1,3,5) увеличился на одновременно с таким же увеличением потребности Ai+1. Найти приращение целевой функции при =1, а также предельное значение , при котором прежнее решение остается оптимальным.

Примечание. Для каждой пары Ai и Ai+1 (i=1,3,5) показать цикл перераспределения на матрице условий.

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

2.1. Записать математическую модель для симметричной (cij=cji) задачи коммивояжера, заданной сетью на рис.1 и таблицей 1 (параметры Ai во внимание не принимаются).

2.2. Найти оптимальное решение модели из п.2.1.

1. Формулируем модель. В соответствии с заданной сетью, с учетом исходных данных она имеет вид:

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

ПН

Поставки

ПО

2

4

6

1

7

5

6

9

5

3

2

3

6

1

5

4

5

4

7

4

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Проверяем условие разрешимости задачи, заключающееся в равенстве количества поставок и спроса: 5+4+7+1+1=8+5+5; 18=18.

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

Подсчитаем значение целевой функции:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

5

6

9

2

3

6

1

5

4

7

4

4

3

8

2

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

0

6

5

9

-1

0

3

2

0

6

0

5

-2

-5

5

4

-1

7

0

4

0

-4

7

8

-6

2

4

3

0

-5

8

13

-6

7

4

8

0

0

v j

7

11

8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем максимальную оценку свободной клетки (1;4)=5

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

ПН

Поставки

ПО

2

4

6

1

7

5-

6

+

9

5

3

2

3+

6

1-

5

4

5

4

7

4

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Цикл в таблице (1,4; 1,2; 3,2; 3,4; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 1. Прибавляем 1 к объемам грузов, стоящих в плюсовых клетках и вычитаем 1 из хij, стоящих в минусовых клетках и получим новый опорный план.

ПН

Поставки

ПО

2

4

6

1

7

4

6

1

9

5

3

2

4

6

5

4

5

4

7

4

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Значение целевой функции для этого опорного плана равно:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

4

6

1

9

2

4

6

5

4

7

4

4

3

8

2

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

0

6

0

9

-6

0

3

2

0

6

-5

5

-5

5

4

4

7

0

4

0

1

7

8

-1

2

4

3

0

0

8

13

-1

7

4

8

0

5

v j

7

6

3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем одну из максимальных оценок свободной клетки (5;2)=4

Для этого в перспективную клетку (5;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

ПН

Поставки

ПО

2

4

6

1

7

4-

6

1+

9

5

3

2

4

6

5

4

5

4

+

7

4-

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Цикл в таблице (5,2; 5,4; 1,4; 1,2; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из хij, стоящих в минусовых клетках и получим новый опорный план.

ПН

Поставки

ПО

2

4

6

1

7

6

5

9

5

3

2

4

6

5

4

5

4

4

7

0

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Значение целевой функции для этого опорного плана равно:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

6

5

9

2

4

6

5

4

4

7

0

4

3

8

2

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

-4

6

0

9

-6

0

3

2

0

6-1

5

-3

-1

5

4

0

7

0

4

0

1

7

8

-5

2

4

3

0

0

8

13

-5

7

4

8

0

5

v j

3

6

3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем оценку свободной клетки (7;4)=4

Для этого в перспективную клетку (7;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

ПН

Поставки

ПО

2

4

6

1

7

6

5

9

5

3

2

4

6

5

4

5

4

4

7

0-

4

3+

7

7

8

2

+

3

1-

1

8

13

7

8

1

1

Спрос

8

5

5

Цикл в таблице (7,4; 5,4; 5,6; 7,6; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 4) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из хij, стоящих в минусовых клетках и получим новый опорный план.

ПН

Поставки

ПО

2

4

6

1

7

6

5

9

5

3

2

4

6

5

4

5

4

4

7

4

3

7

7

8

2

0

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Значение целевой функции для этого опорного плана равно:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

6

5

9

2

4

6

5

4

4

7

4

3

8

2

0

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

0

6

0

9

-2

0

3

2

0

6

-5

5

-3

-5

5

4

0

7

-4

4

0

-3

7

8

-5

2

0

3

0

-4

8

13

-5

7

0

8

0

1

v j

7

6

7

Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты для поставленной задачи составят:

Запишем конечный результат для исходной задачи:

5ед. транспортируются из пункта 1 в пункт 4 без промежуточных пунктов;

4ед. транспортируются из пункта 3 в пункт 2 без промежуточных пунктов;

4ед. транспортируются из пункта 5 в пункт 2 без промежуточных пунктов;

3ед. транспортируются из пункта 5 в пункт 6 без промежуточных пунктов;

0ед. транспортируется из пункта 7 в пункт 4 без промежуточных пунктов;

1ед. транспортируется из пункта 7 в пункт 6 без промежуточных пунктов;

1ед. транспортируется из пункта 7 в пункт 8 без промежуточных пунктов;

Покажем решение на графе:

1.3. Проанализируем задачу на чувствительность.

1.3.1. Коэффициент C25=4 является расстоянием между пунктами 5 и 2,то есть его значение может быть использовано только при оценке клетки (5,2):

Так как при найденном оптимальном решении , то при C52<4 значение оценки станет положительным, значит, решение уже не будет оптимальным. Таким образом, наименьшее значение коэффициента C52=4.

Коэффициент C47=9 является расстоянием между пунктами 7 и 4, его значение может быть использовано только при оценке клетки (7,4):

Так как при найденном оптимальном решении , то при C47<2 значение оценки станет положительным, значит, решение уже не будет оптимальным. Таким образом, наименьшее значение коэффициента C47=2.

1.3.2. Приращение запасов одного из поставщиков.

1. При увеличении S1 на единицу с 5 до 6 целевая функция уменьшится на 1. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5+1

9

5+1

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0-1

3

1+1

1

-4

8

13

7

8

1-1

1-1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (8,6) и

2. При увеличении S3 на единицу с 4 до 5 целевая функция уменьшится на 2. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4+1

6

5

4+1

-5

5

4

4-1

7

4

3

7-1

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (5,2) и

3. При увеличении S5 на единицу с 4 до 5 целевая функция увеличится на 2. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4-1

6

5

4-1

-5

5

4

4+1

7

4

3

7+1

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (3,2) и

4. При увеличении S7 на единицу с 0 до 1 целевая функция уменьшится на 4. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5-1

9

5-1

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0+1

3

1

1+1

-4

8

13

7

8

1

1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (1,4) и

5. При увеличении S8 на единицу с 1 до 2 целевая функция увеличится на 1. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5-1

9

5-1

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0+1

3

1-1

1

-4

8

13

7

8

1+1

1+1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (1,4) и

1.3.3 Одновременное увеличение запасов и спроса.

При одновременном увеличении запасов поставщика Si и потребителя Di получаем:

1) Пусть S1 и D2 увеличатся на . При приращение целевой функции будет равно Невозможно составить цикл перераспределения только через базисные клетки, поэтому при любом оптимальное решение будет меняться:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5+

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8+

5

5

vj

7

6

7

2) Пусть S3 и D4 увеличатся на . При приращение целевой функции будет равно Невозможно составить цикл перераспределения только через базисные клетки, поэтому при любом оптимальное решение будет меняться:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4

6

5

4+

-5

5

4

4

7

4

3

7

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5+

5

vj

7

6

7

3) Пусть S5 и D6 увеличатся на . При приращение целевой функции будет равно Составим цикл перераспределения, в данном случае он будет состоять из одной клетки (5,6), поэтому может принимать любые значения, прежнее решение останется оптимальным:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4

6

5

4

-5

5

4

4

7

4

3+1

7+

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5

5+

vj

7

6

7

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

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

Математическая модель задачи коммивояжера в общем виде выглядит так:

решение есть цикл.

Для графа

задача коммивояжера описывается следующей моделью:

Целевая функция:

В каждый пункт назначения входит один и только один путь:

Из каждого пункта отправления выходит только один маршрут:

,

решение есть цикл.

2.2. Решение.

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,8);(8,1)

Тогда F(X0) = 7 + 2 + 6 + ? + 4 + 3 + 5 + ? = 27

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

i j

1

2

3

4

5

6

7

8

min

1

?

7

6

6

?

?

?

?

6

2

7

?

2

?

4

8

?

?

2

3

6

2

?

6

4

5

6

?

2

4

6

?

6

?

?

3

2

?

2

5

?

4

4

?

?

4

?

9

4

6

?

8

5

3

4

?

3

8

3

7

?

?

6

2

?

3

?

5

2

8

?

?

?

?

9

8

5

?

5

Затем вычитаем найденные минимумы из элементов рассматриваемой строки.

i j

1

2

3

4

5

6

7

8

1

?

1

0

0

?

?

?

?

2

?

?

0

?

2

6

?

?

3

4

0

?

4

2

3

4

?

4

4

?

4

?

?

1

?

?

5

?

0

?

?

?

0

?

5

6

?

5

2

0

1

?

0

5

7

?

?

?

0

?

?

?

3

8

?

?

?

?

4

3

0

?

Далее приводим по столбцам, для чего в каждом столбце находим минимальный элемент:

i j

1

2

3

4

5

6

7

8

1

?

1

0

0

?

?

?

?

2

?

?

0

?

2

6

?

?

3

4

0

?

4

2

3

4

?

4

4

?

4

?

?

1

?

?

5

?

0

?

?

?

0

?

5

6

?

5

2

0

1

?

0

5

7

?

?

?

0

?

?

?

3

8

?

?

?

?

4

3

0

?

min

4

0

0

0

1

0

0

3

После вычитания минимальных элементов получаем новую матрицу.

i j

1

2

3

4

5

6

7

8

1

?

1

0

0

?

?

?

?

2

1

?

0

?

1

6

?

?

3

0

0

?

4

1

3

4

?

4

0

?

4

?

?

1

?

?

5

?

0

?

?

?

0

?

2

6

?

5

2

0

0

?

0

2

7

?

?

?

0

?

?

?

0

8

?

?

?

?

3

3

0

?

Сумма найденных минимальных элементов определяет нижнюю границу Q:

Q(0)=( 6+2+2+2+4+3+2+5)+(4+0+0+0+1+0+0+3) = 34

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ? (бесконечность) и определяем для них сумму образовавшихся констант приведения.

i j

1

2

3

4

5

6

7

8

1

?

1

0(0)

0(0)

?

?

?

?

2

1

?

0(1)

?

1

6

?

?

3

0(0)

0(0)

?

4

1

3

4

?

4

0(0)

?

4

?

?

1

????

?

5

?

0(0)

????

?

?

0(1)

?

2

6

?

5

2

0(0)

0(1)

?

0(0)

2

7

?

?

?

0(0)

?

?

?

0(2)

8

?

?

?

?

3

3

0(3)

?

Наибольшая сумма констант приведения равна (3 + 0) = 3 для ребра (8,7), следовательно, множество разбиваем на два подмножества (8,7) и (8*,7*).

Нижняя граница гамильтоновых циклов этого подмножества:

задача коммивояжер транспортный пункт

H(8*,7*) = 34 + 3 = 37

Исключение ребра (8,7) проводим путем замены элемента 8,7 = 0 на ?, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (8*,7*), в результате получаем матрицу.

i j

1

2

3

4

5

6

7

8

min

1

?

1

0

0

?

?

?

?

?

2

1

?

0

?

1

6

?

?

?

3

0

0

?

4

1

3

4

?

?

4

0

?

4

?

?

1

?

?

?

5

?

0

?

?

?

0

?

2

0

6

?

5

2

0

0

?

0

2

0

7

?

?

?

0

?

?

?

0

0

8

?

?

?

?

3

3

?

?

?

min

?

?

?

?

0

0

0

?

?

Включаем ребро (8,7), исключая все элементы 8-ой строки и 7-го столбца, а элемент 7,8 заменяем на ? для исключения образования негамильтонова цикла. В результате получаем следующую сокращенную матрицу:

i j

1

2

3

4

5

6

8

min

1

?

1

0

0

?

?

?

?

2

1

?

0

?

1

6

?

?

3

0

0

?

4

1

3

?

?

4

0

?

4

?

?

1

?

?

5

?

0

?

?

?

0

2

0

6

?

5

2

0

0

?

2

0

7

?

?

?

0

?

?

?

0

min

?

?

?

?

0

0

?

?

Сумма констант приведения сокращенной матрицы равна 2. Нижняя граница подмножества (8,7) равна:

H(8,7) = 34 + 2 = 36 < 37.

Поскольку нижняя граница этого подмножества (8,7) меньше, чем подмножества (8*,7*), то ребро (8,7) включаем в маршрут.

Определяем следующее ребро ветвления.

i j

1

2

3

4

5

6

8

1

?

1

0(0)

0(0)

?

?

?

2

1

?

0(1)

?

1

6

?

3

0(0)

0(0)

?

4

1

3

?

4

0(1)

?

4

?

?

1

?

5

?

0(0)

????

?

?

0(1)

2

6

?

5

2

0(0)

0(1)

?

2

7

?

?

?

0(1)

?

?

?

Так как наибольшая сумма констант совпадает, то выберем одну из них, например, для ребра (7,4), следовательно, множество разбивается на два подмножества (7,4) и (7*,4*). Нижняя граница гамильтоновых циклов этого подмножества:

H(7*,4*) = 36 + 1 = 37.

Включение ребра (7,4) проводится путем исключения всех элементов 7-ой строки и 4-го столбца. В результате получаем следующую матрицу, которая подлежит операции приведения.

i j

1

2

3

5

6

8

min

1

?

1

0

?

?

?

?

2

1

?

0

1

6

?

?

3

0

0

?

1

3

?

?

4

0

?

4

?

1

?

?

5

?

0

?

?

0

0

0

6

?

5

2

0

?

0

0

min

?

?

?

?

0

?

Сумма констант приведения сокращенной матрицы равна 0. Нижняя граница подмножества (7,4) равна:

H(7,4) = 36 + 0 = 36 < 37.

Поскольку нижняя граница этого подмножества (7,4) меньше, чем подмножества (7*,4*), то ребро (7,4) включаем в маршрут.

Определяем следующее ребро ветвления.

i j

1

2

3

5

6

8

1

?

1

0(1)

?

?

?

2

1

?

0(1)

1

6

?

3

0(0)

0(0)

?

1

3

?

4

0(1)

?

4

?

1

?

5

?

0(0)

????

?

0(1)

0(0)

6

?

5

2

0(1)

?

0(0)

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

H(4*,1*) = 36 + 1 = 37.

Включение ребра (4,1) проводится путем исключения всех элементов 4-ой строки и 1-го столбца. В результате получим следующую матрицу, которая подлежит операции приведения.

i j

2

3

5

6

8

min

1

1

0

?

?

?

?

2

?

0

1

6

?

?

3

0

?

1

3

?

?

5

0

?

?

0

0

?

6

5

2

0

?

0

0

min

?

?

?

0

?

Сумма констант приведения сокращенной матрицы равна 0. Нижняя граница подмножества (4,1) равна:

H(4,1) = 36 + 0 = 36 < 37.

Поскольку нижняя граница этого подмножества (4,1) меньше, чем подмножества (4*,1*), то ребро (4,1) также включаем в маршрут.

Определяем следующее ребро ветвления.

i j

2

3

5

6

8

1

1

0(1)

?

?

?

2

?

0(1)

1

6

?

3

0(0)

?

1

3

?

5

0(0)

????

?

0(1)

0(0)

6

5

2

0(1)

?

0(0)

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

H(4*,1*) = 36 + 1 = 37.

Включение ребра (4,1) проводится путем исключения всех элементов 4-ой строки и 1-го столбца. В результате получим следующую матрицу, которая подлежит операции приведения.

i j

2

3

5

6

8

min

1

1

0

?

?

?

?

2

?

0

1

6

?

?

3

0

?

1

3

?

?

5

0

?

?

0

0

?

6

5

2

0

?

0

0

min

?

?

?

0

?

Сумма констант приведения сокращенной матрицы равна 0. Нижняя граница подмножества (4,1) равна:

H(4,1) = 36 + 0 = 36 < 37.

Поскольку нижняя граница этого подмножества (4,1) меньше, чем подмножества (4*,1*), то ребро (4,1) также включаем в маршрут.

Определяем следующее ребро ветвления.

i j

2

3

5

6

8

1

1

0(1)

?

?

?

2

?

0(1)

1

6

?

3

0(1)

?

1

3

?

5

0(0)

????

?

0(3)

0(0)

6

5

2

0(1)

?

0(0)

Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (5,6),отсюда множество разбивается на два подмножества (5,6) и (5*,6*). Нижняя граница гамильтоновых циклов этого подмножества:

H(5*,6*) = 36 + 3 = 39.

Включение ребра (5,6) проводится путем исключения всех элементов 5-ой строки и 6-го столбца, а также элемент 6,5 заменяем на ? для исключения образования негамильтонова цикла. В результате получим следующую матрицу, которая подлежит операции приведения.

i j

2

3

5

8

min

1

1

0

?

?

?

2

?

0

1

?

?

3

0

?

1

?

?

6

5

2

?

?

0

min

?

?

?

?

?

Сумма констант приведения сокращенной матрицы равна 1. Нижняя граница подмножества (5,6) равна:

H(5,6) = 36 + 1 = 37 < 39.

Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут.

Определяем следующее ребро ветвления.

i j

2

3

5

8

1

1

0(1)

?

?

2

?

0(0)

0(0)

?

3

0(1)

?

0(0)

?

6

5

2

?

????

Наибольшая сумма констант приведения равна (2 + 0) = 2 для ребра (6,8),отсюда множество разбивается на два подмножества (6,8) и (6*,8*). Нижняя граница гамильтоновых циклов этого подмножества:

H(6*,8*) = 37 + 2 = 39.

Включение ребра (6,8) проводится путем исключения всех элементов 6-ой строки и 8-го столбца. В результате получим следующую матрицу, которая подлежит операции приведения.

i j

2

3

5

min

1

1

0

?

?

2

?

0

0

?

3

0

?

0

?

min

?

?

?

?

Сумма констант приведения сокращенной матрицы равна 0. Нижняя граница подмножества (6,8) равна:

H(6,8) = 37 + 0 = 37 < 39.

Поскольку нижняя граница подмножества (6,8) меньше, чем подмножества (6*,8*), то ребро (6,8) включаем в маршрут.

Определяем следующее ребро ветвления.

i j

2

3

5

1

1

0(1)

?

2

?

0(0)

0(0)

3

0(1)

?

0(0)

Наибольшая сумма констант приведения равна 1, выберем ребро (1,3), множество разбивается на два подмножества (1,3) и (1*,3*). Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,3*) = 37 + 1 = 38.

Включение ребра (1,3) проводится путем исключения всех элементов 1-ой строки и 3-го столбца. В результате получим следующую матрицу.

i j

2

5

min

2

?

0

?

3

0

0

?

min

?

?

?

Сумма констант приведения сокращенной матрицы равна 0. Нижняя граница подмножества (1,3) равна:

H(1,3) = 37 + 0 = 37 < 38.

Поскольку нижняя граница подмножества (1,3) меньше, чем подмножества (1*,3*), то ребро (1,3) включаем в маршрут.

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

Получаем оптимальное решение:

Представим решение на графе:

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2025, ООО «Олбест» Все наилучшее для вас