Оптимальное размещение участка слежения в графе решения летчика
Дипломная работа - Транспорт, логистика
Другие дипломы по предмету Транспорт, логистика
?есса слежения.
При этом возникает задача наилучшего (оптимального по суммарному затраченному оператором времени) распределения участков непрерывного слежения между элементами последовательности решений.
Оптимальное распределение зависит от вида tотр = tотр (jнач). Для нахождения оптимального распределения представим последовательность решений {ti} через последовательность начальных ошибок слежения{ji = ti}, которые будут появляться на момент начала слежения, после окончания отвлечения оператора (на время ti) на выработку и реализацию i-того решения. Полученную ниже последовательность{ji = ti } также будем называть последовательностью решений.
Для определения такого распределения аппроксимируем экспериментальные зависимости двумя видами аналитических зависимостей.
1.6 Математическая постановка задачи размещения участков слежения
Для верного понимания поставленной задачи, определим следующие понятия:
Заданная последовательность (з/последовательность) - любая положительная конечная числовая последовательность.
Например: 1 2 2 3 2 2 3 3 4 1
Порожденная последовательность (п/последовательность) - любая последовательность полученная из з/последовательности путем сложения ее членов (запрет на перестановку).
Например:
.(1+2+2) 3 (2+2+3) (3+4) 1
.1 2 (2+3+2) 2 (3+3+4+1)
.1 2 2 3 2 2 3 (3+4+1)
Оценочная функция - функция, каждому элементу последовательности ставится в соответствие число.
Например:
1.
.
Оценка - сумма всех оценок элементов п/последовательности
Например:
Оптимальная п/последовательность (опт п/последовательность) - п/последовательность, имеющая наименьшую оценку (таких п/последовательностей может быть сколь угодно много)
Например: 8 7 3 5, 5 3 7 8, 5 7 6 4 1
Пусть оценочная функция имеет только два линейных участка: второй участок II справа не ограничен.
при (1.1)
при (1.2)
Для разработки блока оптимизации моментов включения поставлена математическая задача оптимального размещения участков слежения. Задана числовая последовательность, состоящая из положительных членов. По ней требуется построить порожденную последовательность с минимальной оценкой. Оценочная функция представляется кусочно-линейной функцией с двумя участками.
Для решения поставленной задачи требуется обеспечить обмен информацией системы ГРО-оценка и разрабатываемого блока.
Входная информация в блок оптимизации моментов включения:
.З/последовательность
Например: 1 2 2 3 2 2 3 3 4 1
.Оценочная функция
Например: a1=1, a2=2, b=4, x=5
Выходная информация из блока оптимизации моментов включения:
.Опт п/последовательность
Например:
8 7 3 5(1+2+2+3) (2+2+3) 3 (4+1)
3 7 8(1+2+2) 3 (2+2+3) (3+4+1)
7 6 4 1(1+2+2) (3+2+2) (3+3) 4 1
2.Оценка опт п/последовательности
Например: 49
ГЛАВА 2. КОНСТРУИРОВАНИЕ ОПТИМАЛЬНОЙ ПОРОЖДЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
Для построения п/последовательностей используется стандартная процедура (СП-Укруп) укрупнения членов заданной последовательности, находящихся на одном участке функции оценки. Участок имеет правую границу. Укрупнение должно обеспечить минимальное число членов, каждый из которых не превосходит правой границы участка.
В данном дипломном проекте рассмотрим следующие основные классы последовательностей:
Класс (I, ):
все элементы заданной последовательности { } находятся на одном участке и их сумма не превосходит правой границы этого участка.
Класс (I, )
все элементы заданной последовательности {} находятся на I участке, а их сумма больше правой границы этого участка.
Класс (I, II): Элементы заданной последовательности находятся на I и II участках.
Лемма: При {}, и
оптимальная п/последовательность
Доказательство: т.к.
,
то минимизация n будет давать опт п/последовательность.
2.1 СП-Укруп
Условия обращения: все
li?x1,
Доказательство одинакового количества членов п/последовательностей, порожденной слева-направо и права-налево:
Задача: Построить п/последовательность, все члены которой находятся на I участке (, и число их минимально (min )
Процедура укрупнения справа-налево и слева-направо дает одно и тоже число укрупненных членов
Пример:
{1 2 3 2 1 3} x1=4
> {3 3 3 3} k=4
< {3 3 3 3} k=4
Другие процедуры укрупнения дают не меньшее число укрупненных членов.
Пример:
Рисунок 2.1
2.2 Процедуры построения п/последовательностей из разных классов з/последовательностей
Класс (I, ): все элементы заданной последовательности {} находятся на одном участке и их сумма не превосходит правой границы этого участка.
Рисунок 2.2
По лемме опт. п/последовательность имеет один член и
Класс (I, ): все элементы заданной последовательности {} находятся на I участке, а их сумма больше правой границы этого участка.
Процедура построения п/последовательностей:
1)Перенос вправо на II участок последних членов заданной последовательности {} )Первый перенос требует предварительной группировки членов заданной последовательности , но )Последующие переносы делаются почленно с добавлением на II участке к уже имеющемуся там члену
2)При каждом переносе на II участок оставшиеся на I участк?/p>