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

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

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

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

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

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

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

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

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

На тему:

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

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

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

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

Дата:

Подпись

Москва

2014 г.

Оглавление

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

1. Дано:

,

,

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

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

,

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

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

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

1. Дано:

,

,

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

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

,

Рисунок 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

4. 

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

	0
	1
	1
	0
	0

5. 

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

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

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

Рисунок 2.