Министерство высшего и среднего специального образования Российской Федерации

Московский ордена Ленина, ордена Октябрьской Революции и ордена Трудового

Красного Знамени

ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени Н. Э. БАУМАНА

Факультет «Робототехники и комплексной автоматизации»

Кафедра «Систем автоматизированного проектирования»

Пояснительная записка

к курсовому проекту

по курсу «Методы оптимизации»

на тему:

«Автоматизация проектирования охранной системы»

Студент: Никулина А. А

Группа: РК6-61

Руководитель проекта: Родионов С.В.

Дата:

Подпись

Москва

2014 г.

Оглавление

Введение 3

Техническое задание 3

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

1.1 Математическая постановка задачи 4

1.2 Пример решения задачи с помощью «Жадного алгоритма». 5

1.3 Решении задачи с помощью метода покрытия булевой матрицы. 7

Введение

Техническое задание

Автоматизация проектирования охранной системы.

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

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

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

1.1 Математическая постановка задачи

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

1. Дано:

,

,

1. Введем булевы переменные

1. Задаем матрицу

,

1. Формулируем приведенную задачу в данном виде

1.2 Пример решения задачи с помощью «Жадного алгоритма».

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

1. Дано:

,

,

1. Введем булевы переменные

1. Задаем матрицу

,

Рисунок 1

Получаем матрицу:

	1	1	0	0	1	1
	1	1	1	0	1	1
	0	1	1	1	0	1
	0	0	1	1	0	0
	1	1	0	0	1	1
	1	1	1	0	1	1

выбираем покрываем данную строку, а также все столбцы, где есть 1 в этой строке:

	0
	1
	1
	0
	0

выбираем покрываем данную строку, а также все столбцы, где есть 1 в этой строке:

Таким образом, мы покрыли все строки и столбцы таблицы.

Кратчайшее же покрытие данной матрицы составляют строки – и , в данных квадратах есть места для 2 устройств наблюдения и . Данные 2 устройства будут обеспечивать охрану всей территории.

Рисунок 2.

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

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

У данного метода экспоненциальная сложность , тогда как у «жадного» алгоритма полиномиальная . Текущая ситуация, соответствующая некоторой вершине дерева поиска, представляется переменной матрицей Х, которая показывает, какие столбцы еще не покрыты и какие строки можно использовать для их покрытия. В этой ситуации выбирается первая из строк с минимальным числом единиц – так минимизируется число вариантов продолжения поиска. Очередной шаг процесса состоит в выборе покрывающего столбца для этой строки и пробном включении ее в получаемое решение. Таким образом, вершины дерева поиска соответствуют некоторым строкам исходной матрицы, а дуги – выбираемым для их покрытия столбцам.

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

1. Если столбец k имеет единицы везде, где имеет единицы столбец l, то столбец k можно удалить. Любая строка, покрывающая столбец l, покрывает также столбец k. Поэтому при поиске покрытия столбец k можно не рассматривать. Достаточно, чтобы в покрытие была включена какая-либо из строк, покрывающих столбец l.

2. Если строка i имеет единицы везде, где имеет единицы строка j, то строку j можно удалить. Действительно, пусть в некотором кратчайшем покрытии имеется строка j. Очевидно, данное покрытие останется кратчайшим, если в нем строку j заменить строкой i.

1. Дано:

,

,

1. Введем булевы переменные

1. Задаем матрицу

,

– i-ая строка

- j-ый столбец

Данный столбец и все покрытые им строки исключаются из таблицы

Рисунок 3

Получаем матрицу:

	1	1	0	0	1	1
	1	1	1	0	1	1
	0	1	1	1	0	1
	0	0	1	1	0	0
	1	1	0	0	1	1
	1	1	1	0	1	1

1. 1) Проводим редукцию строк и столбцов: