Конструирование оптимальной порожденной последовательности

Другое » Оптимальное размещение участка слежения в графе решения летчика » Конструирование оптимальной порожденной последовательности

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

В данном дипломном проекте рассмотрим следующие основные классы последовательностей:

Класс (

I

,

):

все элементы заданной последовательности { } находятся на одном участке и их сумма не превосходит правой границы этого участка.

Класс (

I

,

)

все элементы заданной последовательности {} находятся на I участке, а их сумма больше правой границы этого участка.

Класс (I, II): Элементы заданной последовательности находятся на I и II участках.

Лемма: При {}, и

оптимальная п/последовательность

Доказательство: т.к.

,

то минимизация n будет давать опт п/последовательность.

СП-Укруп

Условия обращения: все

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,

):

все элементы заданной последовательности {} находятся на I участке, а их сумма больше правой границы этого участка.

Процедура построения п/последовательностей:

Перенос вправо на II участок последних членов заданной последовательности {}

Другие публикации:

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

Нормирование подвижного состава
Общий рабочий парк вагонов определяется по формуле: ; (6.34) ваг Рабочий парк порожних вагонов ; (6.35) ваг Парк груженых вагонов ; (6.36) ваг Парк местных вагонов ; (6.37) ваг Парк сдаточных вагонов (6.38) ваг Среднесуточный пробег и производительность вагона Норму среднесуточного пробега вагона д ...

Составление графика постановки электровозов на технические обслуживания и ремонты
Декадный график постановки электровозов на текущие ремонты ТР-1, ТР-2, ТР-3 и технические обслуживания ТО-3, ТО-4 в соответствии с данными таблицы 7 и с учётом среднесуточного пробега на удлинённом участке обращения Б-Д, представлен в виде таблицы 8. Таблица 8 – Декадный график постановки электрово ...