WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |

Рисунок 43 Рисунок Строка 9 последней матрицы (рис. 44) соответствует завершению работы алгоритма. Просматривая столбец этой строки, находим значение 7. Это значит, что кратчайРисунок ший путь в вершину 10 проходит через вершину 7. Просматривая столбец 7 последней строки, получаем номер вершины Для получения порядка прохождения вершин в пути 5. Следовательно, в вершину 7 кратчайший путь прошел чеот вершины 1 к вершине 10 воспользуемся матрицей, приверез вершину 5. В столбце 5 последней строки находим верденной на рисунке 40. В ячейку О52 вводится формула (2.20).

шину с номером 1. Следовательно, кратчайший путь из верДалее она распространяется на диапазон О52:Х61. Привешины 1 в вершину 10 проходит через вершины 1, 5, 7 и 10.

денная на рисунке 41 матрица соответствует матрицам, приДлина этого пути равна 19. На рисунке 46 указан соответстведенным на рисунке 35. По мере заполнения столбца М, повующий кратчайший путь.

лучим результаты, приведенные на рисунках 42-44 соответЕсли нет пути, соединяющего указанные в ячейках Оственно.

и Q2 вершины, то на каком-то этапе выполнения алгоритма =ЕСЛИ(ЕОШИБКА(ВПР($M26;$A$14:$K$23;B$1 оценка минимальной длины станет равной 1000. В соответст3+1));"";ЕСЛИ(МИН(B26;$L26+ вии с алгоритмом это означает отсутствие искомого пути. На (2.20) рисунке 45 приведен пример поиска кратчайшего пути между ВПР($M26;$A$14:$K$23;B$13+1))=B26;O51;

вершинами 8 и 9.

$M26)) 37 Решение. Решение задачи можно начинать с потока величины 7 (рис. 48). Нетрудно заметить, что все условия сохранения потока выполнены.

Рисунок Рисунок Пример 7. Найти максимальный поток и минимальный разрез, отделяющий источник 1 и сток 6 для сети, приведен- Рисунок ной на рисунке 47. Число около каждой дуги означает пропускную способность соответствующей дуги.

Рисунок Согласно алгоритму, источник (узел 1) получил пометРисунок ку (-, ). Затем из узла 1 можно пометить только узел 2. Из 39 узла 2 помечается узел 5, а из узла 5 – узел 3 и сток (узел 6).

Так как сток оказался помеченным, переходим к операции В.

Сток получил пометку (5+, 1). Следовательно, f(5, 6) станет равным 2+1=3. Переходим к узлу 5. Так как он имеет пометку (2+, 2), но до стока дошла только одна единица потока, то поток по дуге (2, 5) станет равным 0+1=1. Следовательно, f(2,5)=0+1=1.

Переходим к узлу 2. Так как он имеет пометку (1+, 2), то до стока по дуге (1, 2) дошла только одна дополнительная единица потока. Поток по дуге (1, 2) станет равным 1+1=2.

Следовательно, f(1,2)=1+1=2.

Так как в результате выполнения операции В достигнут источник (узел 1), то следует стереть старые пометки и снова перейти к операции А. Состояние сети приведено на рисунке 50. Жирными стрелками указаны дуги, по которым идет одна дополнительная единица потока.

Рисунок Однако дальнейшее выполнение алгоритма невозможно, так как дуги (5, 6), (3, 6) и (4, 6) имеют нулевую остаточную пропускную способность. Поскольку не удается пометить вершину 6 (сток), то на предыдущем шаге выполнения алгоритма получен максимальный поток величины 8.

Так как помеченными оказались вершины 1–5, а непомеченной – вершина 6, то минимальный разрез, отделяющий источник и сток, представляет собой совокупность дуг (X, X) = {(5, 6), (3, 6), (4, 6) }, где X = {1, 2, 3, 4, 5 }, X = {6}.

Состояние сети приведено на рисунке 52. Жирными стрелками изображен минимальный разрез (X, X).

Рисунок Снова выполняем операцию А. Источник (узел 1) получил пометку (-, ). Затем из узла 1 помечается узел (рис. 51). Из узла 2 помечается узел 5, а из узла 5 – узел 3. Из узла 3 можно пометить узел 4.

41 Таблица Варианты 1 2 3 4 5 6 7 8 9 1 2 1 17 20 12 17 9 14 13 10 1 3 1 11 13 10 13 2 12 13 14 1 4 1 18 20 4 15 16 12 19 14 1 5 2 20 7 9 13 17 6 2 17 1 6 2 6 6 18 10 15 4 3 3 1 7 2 18 14 9 13 19 5 10 14 1 8 2 1 11 3 18 5 14 4 8 1 9 2 5 12 4 11 8 3 14 6 Рисунок 1 10 2 8 14 5 11 16 17 9 20 2 3 3 19 14 8 1 13 15 9 20 Задачи для самостоятельного решения 2 4 3 10 7 9 12 17 14 11 14 2 5 3 13 18 7 17 18 1 14 6 1. Неориентированный граф G содержит 10 вершин. Рас2 6 3 4 5 16 7 8 16 2 20 стояния между вершинами заданы в таблицах 4-5. Найти его 2 7 4 14 8 19 15 20 2 7 17 минимальное дерево-остов (минимальное покрывающее 2 8 4 12 4 9 19 19 11 2 18 дерево).

2 9 5 14 5 14 9 11 5 9 16 2 10 5 20 2 3 16 20 11 7 9 3 4 6 15 10 6 7 17 13 5 3 3 5 6 4 6 2 2 6 9 16 12 3 6 6 17 2 11 17 1 12 12 13 3 7 6 16 11 12 3 10 8 8 14 3 8 6 18 18 9 2 15 6 4 5 3 9 6 15 4 10 20 19 11 10 1 3 10 6 16 17 18 1 20 5 18 1 4 5 6 6 11 14 10 18 18 15 11 43 начало конец длина длина длина длина длина длина длина длина длина длина Продолжение таблицы 4 Продолжение таблицы 1 7 20 2 1 11 6 16 19 3 12 4 6 7 20 12 11 1 2 8 10 13 1 8 9 13 19 2 9 12 4 10 5 4 7 7 7 17 3 5 9 3 2 18 4 8 7 8 16 11 13 1 8 1 19 13 1 9 14 18 18 16 1 9 1 13 12 4 9 7 7 20 13 7 14 10 10 15 1 10 5 9 11 13 17 12 20 3 7 4 10 7 1 17 19 6 6 20 14 14 2 3 18 2 19 10 17 11 9 10 13 5 6 8 15 7 7 1 16 1 12 5 2 4 16 15 4 1 6 16 11 16 10 5 7 8 4 19 1 8 8 13 14 3 2 5 20 10 5 4 10 9 17 6 8 5 8 8 7 17 8 16 7 20 5 2 2 6 18 5 4 3 6 10 13 19 19 5 9 8 9 11 8 7 20 11 3 9 2 7 10 19 19 20 6 15 16 13 9 5 10 8 20 4 10 10 4 11 5 4 2 8 10 3 6 2 7 3 19 12 7 6 7 9 13 7 14 16 14 18 7 19 6 8 9 16 12 1 13 5 8 3 12 2 2 9 20 5 12 1 2 17 2 14 19 6 9 9 7 4 2 17 18 19 20 17 3 2 10 16 7 20 15 4 8 15 13 10 6 10 9 9 16 17 7 6 14 10 15 13 3 4 5 8 12 17 16 9 17 7 15 7 8 9 12 10 17 10 14 15 2 3 16 3 5 6 11 8 10 7 15 20 4 9 7 9 9 9 16 6 15 13 20 6 7 2 3 6 10 17 18 10 20 1 10 19 10 7 10 9 9 10 16 9 15 7 7 4 1 3 7 6 12 15 20 6 14 19 11 2 8 9 10 17 19 18 18 8 1 19 9 14 3 8 19 14 3 18 8 8 17 2 11 8 10 10 1 7 2 15 14 4 11 13 10 3 9 20 10 1 6 13 2 10 11 9 3 10 19 4 7 9 10 3 2 1 16 Таблица 4 5 13 15 19 6 4 20 1 17 20 Варианты 4 6 2 2 2 7 12 2 8 1 16 11 12 13 14 15 16 17 18 19 4 7 13 20 9 12 15 9 3 11 4 4 8 4 5 6 11 5 19 18 17 8 4 9 2 4 6 3 18 18 18 4 8 4 10 11 20 6 18 18 7 8 13 8 5 6 20 10 15 11 20 4 11 10 11 1 2 11 12 13 14 15 16 17 18 19 5 7 14 3 3 4 14 16 18 3 7 1 3 4 18 16 5 14 7 8 4 15 5 8 5 18 14 18 13 20 15 20 8 1 4 4 15 15 16 12 7 9 9 3 5 9 2 11 20 16 20 16 10 12 13 1 5 1 14 17 8 16 16 2 4 14 5 10 8 16 3 2 15 4 17 17 3 1 6 18 16 14 17 16 5 5 16 3 45 начало конец длина длина длина длина длина длина длина длина длина длина Продолжение таблицы 5 Таблица 6 7 17 6 20 5 19 20 19 6 17 Варианты 6 8 1 5 15 7 20 16 5 1 9 1 2 3 4 5 6 7 8 9 6 9 12 13 19 12 12 2 20 3 2 6 10 6 19 5 16 9 5 7 11 18 7 8 5 10 1 2 5 12 11 15 20 7 9 16 15 16 2 16 20 1 13 5 7 10 18 17 8 5 9 20 17 20 14 1 2 1 17 20 12 17 9 14 13 10 8 9 14 4 17 18 17 8 12 3 8 1 5 1 11 13 10 13 2 12 13 14 8 10 1 7 18 19 13 4 18 12 5 2 3 3 19 14 8 1 13 15 9 20 9 10 18 2 7 16 19 8 20 6 6 2 4 3 10 7 9 12 17 14 11 14 2.



Граф содержит 10 вершин (рис.53). Расстояния между 3 4 6 15 10 6 7 17 13 5 3 вершинами заданы таблицами 6-7. Найти кратчайший путь 4 6 7 20 12 11 1 2 8 10 13 между вершинами 1 и 10. 5 6 8 15 7 7 1 16 1 12 5 5 7 8 4 19 1 8 8 13 14 3 6 7 9 13 7 14 16 14 18 7 19 6 9 9 7 4 2 17 18 19 20 17 7 8 9 12 10 17 10 14 15 2 3 7 10 9 9 10 16 9 15 7 7 4 8 10 10 1 7 2 15 14 4 11 13 9 10 10 2 13 3 11 2 20 16 18 Рисунок 47 начало конец длина длина длина длина длина длина длина длина длина длина Таблица Варианты 11 12 13 14 15 16 17 18 19 1 2 15 10 6 7 9 9 9 8 5 1 5 3 8 7 15 10 6 8 12 6 Рисунок 2 3 10 5 10 10 7 13 15 14 14 2 4 12 14 4 3 14 14 13 6 7 Таблица 3 4 11 14 9 15 6 1 1 8 13 Варианты 4 6 10 1 12 12 14 3 1 12 13 1 2 3 4 5 6 7 8 9 5 6 1 7 2 3 7 7 8 6 1 5 7 8 6 3 10 7 14 13 3 12 6 7 2 9 7 11 14 13 5 5 5 6 9 10 4 14 15 4 9 7 4 2 1 2 4 9 12 10 9 12 9 13 13 7 8 3 1 13 7 15 3 1 8 14 1 3 13 12 9 13 11 12 8 10 1 7 10 4 1 4 8 14 8 15 4 13 1 4 14 4 9 11 3 12 7 5 4 8 10 8 9 11 11 10 14 13 4 13 2 5 7 10 7 11 2 3 7 12 9 9 10 10 11 2 2 10 1 9 12 2 2 7 7 3 3 4 1 4 14 6 4 3 6 13 4 14 9 13 5 1 1 1 3. Сеть содержит 10 вершин (рис. 54). Пропускные способ4 6 6 15 5 7 15 5 13 8 8 ности дуг заданы таблицами 8-9. Найти максимальный поток 4 7 9 13 12 9 3 2 12 10 4 между вершинами 1 и 10 и соответствующий минимальный 5 7 6 8 11 5 14 15 5 3 9 разрез. 5 8 2 4 9 13 1 11 4 5 10 5 10 2 10 2 2 10 8 8 14 8 6 7 4 15 11 3 6 4 9 6 10 6 8 9 14 11 15 3 3 3 11 13 49 начало конец длина длина длина длина длина длина длина длина длина длина начало конец длина длина длина длина длина длина длина длина длина длина Продолжение таблицы 3. Теория расписаний 6 9 14 7 5 7 7 5 11 8 10 Пример 8. Имеется множество работ N = {1,2,...7}, 7 10 10 9 15 10 6 11 2 8 6 которые должны быть выполнены на двух последовательных 8 10 15 10 9 8 15 8 15 13 4 приборах А и В (сначала на приборе А, а затем – на приборе В). Время, необходимое для полного обслуживания работы к 9 10 10 5 7 1 12 11 8 11 13 (1к7) на приборе А, обозначим через tкA, а на приборе В – Таблица через tкB соответственно. Необходимо найти такой порядок Варианты обслуживания, при котором суммарное время простоя при11 12 13 14 15 16 17 18 19 боров А и В минимально.

При построении расписания обслуживания требований множества N необходимо учитывать следующие условия:

• в любой момент времени на одном приборе не может 1 2 8 14 15 8 1 2 12 14 11 обслуживаться более одной работы;

1 3 10 12 14 2 15 8 15 15 15 • одна работа в любой момент времени может занимать не 1 4 4 7 9 13 9 3 13 3 7 9 более одного прибора.

Время обслуживания для заданного множества работ N 2 5 14 12 15 9 13 1 6 1 14 на приборах А и В задано в таблице.

2 7 10 8 12 10 8 4 12 3 4 к 1 2 3 4 5 6 3 6 5 10 11 1 13 12 1 11 1 3 4 8 6 7 2 tкA 4 6 10 8 12 14 7 11 13 15 11 2 1 7 4 5 3 tкB 4 7 3 5 12 10 7 4 2 13 13 5 7 3 12 4 6 8 1 7 5 4 Решение. Эта задача называется задачей Беллмана5 8 7 2 4 9 4 2 3 9 5 7 Джонсона для двух последовательных приборов. Доказано ([5], [8]), что в оптимальном расписании порядок обслужива5 10 15 13 10 2 3 2 13 8 6 ния требований множества N одинаков на обоих приборах.

6 7 15 6 2 8 9 1 2 3 4 Приведем описание алгоритма.

6 8 5 13 1 10 2 2 11 12 7 Шаг 1. Среди чисел tкA и tкB выбираем минимальное.

6 9 6 4 11 13 5 14 12 2 3 Если это число находится в строке, соответствующей прибору А, то данная работа будет обслуживаться первой как на 7 10 9 6 4 7 14 4 9 4 6 приборе А, так и на приборе В. Если это число находится в 8 10 10 11 9 6 9 11 11 9 10 строке, соответствующей прибору В, то данная работа будет 9 10 5 12 4 10 2 2 4 6 10 обслуживаться последней как на приборе А, так и на приборе В.

Шаг 2. Исключаем из рассмотрения время выполнения тех работ, которые уже упорядочены. Если оставшееся 51 начало конец длина длина длина длина Длина длина длина длина длина длина множество работ пусто, то задача решена. В противном слук 3 5 чае возвращаемся к первому шагу.

tкA 8 7 tкB 7 5 Переходим к решению задачи. Минимум по всем tкA и tкB приходится на работу с номером 2. Так как число 1 на = (6,,5,4,7, 1, 2). = (6,3,5,4,7, 1, 2).

6 ходится во второй строке (минимум упал на tкB ), то работа На рисунке 55 приведен один из вариантов решения задачи.

будет обслуживаться последней как на приборе А, так и на Суммарный простой приборов А и В равен 12 Второй вариант приборе В.





Последовательность выполнения работ пока вырешения приведен на рисунке 56.

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

к 1 3 4 5 6 3 8 6 7 2 tкA Рисунок 2 7 4 5 3 Минимум по всем оставшимся длительностям приходится на число 2. Так как число 2 находится и в первой, и во второй строках, то выбираем, например, работу 1. Так как и в этом случае число 2 находится во второй строке, то рабоРисунок та 1 будет обслуживаться последней как на приборе А, так и на приборе В (не считая работы 2). Последовательность выПример 9. Пусть n требований обслуживаются одним прибором. Все требования поступают на обслуживание в мополнения работ пока выглядит так: = (,,,,, 1, 2). Для мент времени d=0. Длительность обслуживания требования k дальнейшего решения исключаем работу 1 из рассмотрения и (k=1, 2,…, n) равна tk единиц времени. Если требование k обработаем с таблицей, приведенной ниже.

служивается первым, то для подготовки прибора к обслужик 3 4 5 6 ванию этого требования необходимо 0k единиц времени. Ес8 6 7 2 5 ли требование j обслуживается непосредственно после треtкA бования i, то для переналадки прибора с обслуживания тре7 4 5 3 tкB бования i на обслуживание требования j необходимо ij единиц времени (1ijn). Требуется так организовать процесс Далее приведем только таблицы и соответствующие им пообслуживания (то есть указать такую последовательность следовательности обслуживания. Выбираемые элементы в проходения требований через прибор), для которой общее таблицах подчеркнуты. = (,,,,7, 1, 2).

3 время обслуживания всех требований минимально. Нетрудно заметить, что искомой последовательности при этом должно к 3 4 5 6 к 3 4 соответствовать наименьшее время пуско-наладочных работ.

8 6 7 2 8 6 tкA tкA В ряде случаев желательно также учитывать время, треk 7 4 5 3 7 4 tкB tкB буемое на приведение обслуживающего устройства в исходное состояние, если требование k обслуживается последним.

= (6,,,,7, 1, 2). = (6,,,4,7, 1, 2).

4 53 Таким образом, необходимо найти такую последовательность Значения записать в соответствующих строках и (i, j) =(i1, i2,…,in) обслуживания требований, при которой столбцах приведенной матрицы рядом с нулями.

величина 3. Исключить ту дугу (i, j), для которой сумма констант n - приведения является наибольшей (исключение дуги + + 0i i i i 1 k k + 1 n (i, j) k = (i, j) достигается заменой соответствующего элемента матрибыла бы наименьшей.

цы на. В результате будет образовано подмножество гаЭта задача допускает простую графическую интермильтоновых контуров {(i, j)}.

претацию. Рассмотрим полный симметрический ориентированный граф (X,U), где X={0,1,…,n} – множество вершин, U 4. Привести полученную матрицу расстояний и определить – множество дуг. Каждой дуге (i, j) графа приписано число нижнюю границу подмножества контуров {(i, j)}.

(i, j) ij. Требуется найти контур, проходящий через каждую 5. Включить дугу (i, j) в контур, что приведен к исключевершину один и только один раз (гамильтонов контур), котонию из матрицы, полученной после выполнения п. 2, i-й рому соответствует наименьшая длина. Под длиной контура строки и j-го столбца. Заменить один из элементов полученпонимается величина, равная сумме длин дуг. Эта задача поной матрицы на для предотвращения образования негалучила название задачи коммивояжера ([4], [5], [8]). Привемильтонова контура.

дем решение задачи методом ветвей и границ при n=6 для 6. Привести полученную матрицу расстояний и определить матрицы расстояний С.

нижнюю границу подмножества контуров {(i, j)}.

(i, j) 20 28 12 39 7. Проверить размерность сокращенной матрицы. Если со кращенная матрица имеет размерность 2 на 2, то перейти к 21 15 9 17 пункту 9.

30 25 45 29 8. Сравнить нижние границы подмножеств контуров С = (i, j) 7 52 40 15 и и перейти к шагу 2. Если при этом <, (i, j) (i, j) 60 46 11 5 (i, j) 11 45 14 21 то разбиению подлежит подмножество {(i, j)}, в противном случае – подмножество {(i, j)}.

Решение. Опишем алгоритм решения задачи.

9. Определить гамильтонов контур и его длину.

1. Привести матрицу расстояний по строкам и столбцам.

10. Сравнить длину полученного контура с нижними граниНайти нижнюю границу всех гамильтоновых контуров n n цами оборванных ветвей. Если длина контура не превосходит = = +.

(R) i j нижних границ оборванных ветвей дерева решений, то полуi = 1 j = чен оптимальный гамильтонов контур. Если длина полученного гамильтонова контура больше границы некоторых вет2. Каждый ноль в приведенной матрице условно заменить вей, то, действуя по алгоритму, развиваем эти ветви до тех на и найти сумму констант приведения = +.

i j (i, j) пор, пока не получим контур с меньшей длиной или убедимся, что такого не существует.

55 Выполним приведение матрицы по строкам: Сумма констант приведения для полностью приве6 денной матрицы равна + = 70.

i j i = 1 j = Выполняем оценку нулевых элементов полностью приведенной матрицы:

В результате будет получена матрица:

1 2 3 4 5 1 8 16 0 27 2 12 6 0 8 18 Наибольшую оценку получил элемент, находящийся 3 5 0 20 4 22 на пересечении 4 строки и 6 столбца. Поэтому все множество 4 6 51 39 14 0 гамильтоновых контуров разбивается на подмножества 5 55 41 6 0 {(4,6)} и {(4,6)}. На рисунке 57 приведено дерево решений 6 0 34 3 10 на данном этапе.

Выполним приведение матрицы по столбцам:

Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.