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

ДипломнаяПомощь в написанииУзнать стоимостьмоей работы

Оптимальное размещение участка слежения в графе решения оператора с кусочно-линейной оценочной функцией, заданной на отрезке (реферат, курсовая, диплом, контрольная)

ДИПЛОМ ТЕМА Оптимальное размещение участка слежения в графе решения оператора с кусочно-линейной оценочной функцией, заданной на отрезке

СОДЕРЖАНИЕ слежение последовательность минимальное множество ВВЕДЕНИЕ Математическая постановка задачи

ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Алгоритмы деятельности экипажа

1.2 Составляющие работы человека-оператора: решения, реализация решений, участие оператора в процессах слежения

1.3 Дискретно-непрерывное слежение

1.4 Граф решений оператора (ГРО) и задача оптимального размещения участков слежения на ветках ГРО

1.5 Оценка временных затрат оператора на процесс слежения

1.6 Примеры ГРО

1.7 Задача размещения участков слежения

1.8 Оценка последовательности ГЛАВА 2. Технология построения полного множества порожденных последовательностей (технология скользящих сечений) с минимальным количеством членов

2.1 Операция укрупнения членов, расположенных на одном участке функции

2.2 Процедуры построения п/последовательностей из разных классов з/последовательностей

2.3 Технология построения полного множества п/последовательностей

2.4 Процедура выделения оптимальной порожденной последовательности.

2.5 Сокращение прямого перебора

2.6 Регулярная процедура построения множества порожденных последовательностей для любой заданной последовательности из класса {I, х₂ У} (технология скользящих сечений) Глава 3. Компьютерная программа определения порожденной последовательности с минимальным количеством членов

3.1 Инструкция пользователя

3.2 Примеры расчета

3.3 Интеграция блока оптимизации моментов включения оператора в процесс слежения в систему «ГРО-оценка»

Глава 4. ЭКОНОМИЧЕСКИЙ РАЗДЕЛ Введение

4.1 Описание продукта

4.2 Анализ рынка сбыта

4.2.1 Конкурентоспособность

4.2.2 Маркетинг

4.2.3 Бизнес-план

4.3 Организация и планирование работ

4.3.1 Расчет затрат и договорной цены

4.3.2 Материал, покупные изделия и полуфабрикаты

4.3.3 Специальное оборудование для экспериментальных работ

4.3.4 Расчет заработной платы

4.3.5 Дополнительная заработная плата

4.3.6 Отчисления в фонды

4.3.7 Оплата работ сторонних организаций

4.3.8 Командировки сотрудников

4.3.9 Накладные расходы

4.3.10 Прочие расходы

4.3.11 Стоимость разработки

4.4 Обоснование экономической целесообразности

4.5 Использование программно-аппаратных средств

4.6 Оценка рисков и поиск путей их минимизации Выводы Глава 5. ЭКОЛОГИЧЕСКАЯ БЕЗОПАСНОСТЬ И БЕЗОПАСНОСТЬ ЖИЗНЕДЕЯТЕЛЬНОСТИ Введение

5.1 Обеспечение оптимальных условий труда на рабочем месте разработчика

5.1.1 Описание рабочего места разработчика

5.1.2 Освещенность рабочего места

5.1.3 Параметры микроклимата на рабочем месте

5.1.4 Вентиляция и отопление

5.2 Расчет естественного освещения

5.2.1 Светотехнические характеристики и единицы измерения

5.2.2 Виды естественного освещения

5.2.3 Принцип нормирования естественного освещения

5.2.4 Расчет бокового одностороннего естественного освещения в производственном помещении.

5.2.4.1 Определение нормированного значения К.Е.О

5.2.4.2 Определение суммарной площади световых проемов

5.2.4.3 Определение количества световых проемов

5.3 Расчет естественной вентиляции

5.3.1 Потребный воздухообмен при наличии в помещении избытка тепла

5.3.2 Потребный воздухообмен при наличии в помещении избытка влаги

5.3.3 Потребный воздухообмен при поступлении вредных веществ в воздух рабочей зоны

5.3.4 Расчет естественной вентиляции Выводы ЗАКЛЮЧЕНИЕ СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ ПРИЛОЖЕНИЕ

Листинг программы

ВВЕДЕНИЕ

На начальном этапе проектирования бортового алгоритмического и индикационного обеспечения функционирования антропоцентрического объекта (Антр/объект) возникает задача аналитического определения суммарного времени, которое потратит оператор (экипаж Антр/объекта) на выполнение запланированных ему алгоритмов деятельности (объема работ). Алгоритмы деятельности оператора (АДО), включающие в себя алгоритмы принятия и реализации решения, алгоритмы включения оператора в бортовую следящую систему в качестве ее звена, представляются в виде графа решения оператора (ГРО). На графе помечены места возможного переключения оператора на алгоритмы слежения. Каждое решение оценивается временем, которое тратит оператор на его выработку и последующую реализацию. Все решения оператор принимает на фоне его работы в качестве звена следящей системы, осуществляя ее в дискретно непрерывном режиме. При отвлечении оператора от процесса слежения на принятие решения следящая система, работающая без оператора, накапливает ошибки. Возвращаясь к процессу слежения, оператор тратит время на устранение этих ошибок. Величина ошибок следящей системы пропорциональна времени отвлечения оператора от процесса слежения. Чем больше ошибка, тем больше времени тратит оператор на ее устранение. На практике эту зависимость представляют в форме аналитической функции монотонно возрастающей функции — «время, затрачиваемое оператором на устранение ошибки слежения» = f (временя отвлечения оператора от процесса слежения, в результате чего накопилась эта ошибка слежения). Эта функция представлялась двумя сопряженными параболами. Однако для ряда практических задач более предпочтительной оказалось ее представления кусочно-линейной зависимостью не более чем с тремя линейными участками.

Для оценки реализуемости оператором спроектированного ГРО необходимо на этом графе в допустимых местах между временными отрезками времен принятия решения разместить участки слежения так, чтобы суммарные затраты оператора на процесс слежения были минимальны. При этом за последним участком принятия решения обязательно должен следовать участок слежения.

Сложившаяся в настоящее время технология разработки спецификаций бортовых алгоритмов системообразующего ядра антропоцентрического объекта (Ант/объекта) включает в себя следующие этапы:

a) разработка естественно языкового технического документа «Логика работы системы «экипаж — бортовая аппаратура». Текст документа обычно структурируется по типовым ситуациям (ТС) функционирования проектируемого Антр./объекта и их проблемным субситуациям (ПрС/С). Семантическая целостность этого технического документа контролируется компьютерной системой «Логика — Текст — Анализ» (ЛоТА);

b) разработка спецификаций бортовых алгоритмов системообразующего ядра Антр/объекта, включающих в себя алгоритмы, предназначенные для реализации на бортовых вычислительных машинах (БЦВМ-алгоритмы), и алгоритмы деятельности экипажа (АДЭ). Этап проектирования поддерживается компьютерной системой «Борт»;

c) оценка реализуемости спроектированной спецификации бортовых алгоритмов:

1) для БЦВМ-алгоритмов — на бортовой цифровой вычислительной системе (БЦВС — сеть БЦВМ),

2) для АДЭ — экипажем за заданное время.

Этап обеспечивается компьютерными системами «БЦВМ-оценка» и «ГРО-оценка»;

d) оценка эффективности разработанной спецификации бортовых алгоритмов. Этап обеспечивается системой компьютерных имитационных математических моделей типовых ситуаций (ИММ-ТС) функционирования Антр/объекта и имитационной математической моделью алгоритмов уровня оперативного целеполагания, в которой обязательно задействован экипаж.

Математическая постановка задачи Дана числовая последовательность {l₁,…, l_i,…, l_n} с конечным числом положительных членов. Назовем ее исходной последовательностью. Из этой последовательности конструируется множество порожденных последовательностей путем сложения любого числа рядом стоящих членов исходной последовательности в любом ее месте. При построении порожденных последовательностей порядок следования членов исходной последовательности менять недопустимо.

Пример. Исходная последовательность {5,3,6,4,2,8}. Последовательности {5,(3+6+4), 2,8}= {5,13,2,8}, {(5+3), 6,4,(2+8)}= {8,6,4,10}, {5+3+6+4+2+8}={28} будут примерами порожденных последовательностей.

Дана монотонно возрастающая оценочная функция y = f (x), имеющая следующий вид:

Параметры оценочной функции a_1, a_2, a_3, b₁ заданные положительные константы.

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

С помощью функции y (x) каждой порожденной последовательности, например А={l₁,…, l_i,…, l_n}, ставится в соответствие ее оценка (положительное число):

y (A)=y (l₁) +…+ y (l_i) +…+ y (l_n) (1.2)

Задача: для исходной последовательности найти порожденную последовательность с минимальной оценкой. Назовем эту порожденную последовательность оптимальной.

При описании процесса решения задачи будем для краткости называть член l_i любой последовательности {l₁,…, l_i,…, l_n}, значение которого:

— 0 < l_i? x₁ членом первого участка,

— x₁ < l_i? x₂ членом второго участка,

— x₂ < l_i членом третьего участка

ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Алгоритмы деятельности экипажа

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

1.2 Составляющие работы человека оператора: решения, реализация решений, участие оператора в процессах слежения

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

Решения, принимаемые оператором в процессе сеанса функционирования, делятся на три типа:

р — перцептивно-опознавательные решения, не требующие времени на обдумывание;

с — речемыслительные решения — их можно разложить на элементарные акты выработки решения;

р-сэвристические решения.

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

Для с-решения помимо аналогичных реакций необходимо учитывать время на обдумывание ситуации — элементарные акты выработки решения (ЭАВР). ЭАВР являются элементарными логическими операциями, на которые можно разбить алгоритм принятия решения оператором по полученным данным от соответствующих приборов. Например: простейшее арифметическое вычисление, сравнение цифробуквенных формуляров, проверка логического условия И/ИЛИ и др. Соответствующие усредненные данные о временных затратах оператора на ЭАВР берутся из литературы по предметной психологии или получаются экспериментальным путем.

Затраты на р-с-решения устанавливаются экспериментальным путем.

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

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

1.3 Дискретно-непрерывное слежение

Пусть на ГРО отмечена последовательность решений, которые должны приниматься оператором при «одновременном» участии его в некотором процессе слежения (например, пилотирование самолета летчиком (оператором) по директорным сигналам). Пусть каждое решение из выделенной последовательности решений охарактеризовано потребным временем _i, которое затрачивает оператор на его выработку и реализации. Принимаем гипотезу о возможности работы оператора в режиме дискретно-непрерывного слежения. В этом режиме оператор отвлекается на время принятия и реализации одного решения (к=1) или подпоследовательности (к >1) следующих друг за другом решений. За время отвлечения оператора от режима слежения накапливается некоторая ошибка процесса слежения (начальная ошибка слежения _нач), которую должен будет устранить оператор при возвращении его к процессу слежения.

1.4 Граф решений оператора (ГРО) и задача оптимального размещения участков слежения на ветках ГРО

Каждое отмеченное в ГРО решение охарактеризовано:

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

б) структурой решения: количеством оперативных единиц восприятия (ОЕВ), составом и последовательностью элементарных актов выработки решения (ЭАВР), представляемых через индикационную символику на кадрах кабиных индикаторов;

в) выходной информацией: составом и последовательностью ручных операций, необходимых для реализации принятого решения.

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

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

1.5 Оценка временных затрат оператора на процесс слежения Пусть на ГРО отмечена последовательность решений, которые должны приниматься оператором при «одновременном» участии его в некотором процессе слежения (например, пилотирование самолета летчиком (оператором) по директорным сигналам). Пусть каждое решение из выделенной последовательности решений охарактеризовано потребным временем _i, которое затрачивает оператор на его выработку и реализации. Принимаем гипотезу о возможности работы оператора в режиме дискретно-непрерывного слежения. В этом режиме оператор отвлекается на время принятия и реализации одного решения (к=1) или подпоследовательности (к >1) следующих друг за другом решений. За время отвлечения оператора от режима слежения накапливается некоторая ошибка процесса слежения (начальная ошибка слежения _нач), которую должен будет устранить оператор при возвращении его к процессу слежения.

Время отработки оператором _нач существенно зависит от динамических характеристик всех звеньев следящей системы и от навыков работы оператора (модель слежения оператора) в этой следящей системе.

На этапе системного проектирования спецификаций алгоритмов бортового интеллекта конструкторы не имеют детальной информации обо всём этом. Она появится на более поздних этапах проектирования.

На рассматриваемом этапе можно ориентироваться только:

— на некоторые зависимости времени отработки (_отр) начальной ошибки _нач слежения

_отр = _отр (_нач),

Полученные в лабораторных условиях для различных типов динамических звеньев или экспериментальные зависимости, полученные при создании аналогичных антропоцентрических объектах на более поздних стадиях их разработки; на экспертную оценку максимальной расчётной скорости = const нарастания ошибки слежения на интервале времени, когда оператор отвлекается от процесса слежения.

При этом возникает задача наилучшего (оптимального по суммарному затраченному оператором времени) распределения участков непрерывного слежения между элементами последовательности решений.

Оптимальное распределение зависит от вида _отр = _отр (_нач). Для нахождения оптимального распределения представим последовательность решений {_i} через последовательность начальных ошибок слежения{_i = _i}, которые будут появляться на момент начала слежения, после окончания отвлечения оператора (на время _i) на выработку и реализацию i-того решения. Полученную ниже последовательность{_i = _i } также будем называть последовательностью решений.

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

1.6 Задачи размещения участков слежения Для верного понимания поставленной задачи, определим следующие понятия:

· Заданная последовательность (з/последовательность) — любая положительная конечная числовая последовательность.

Например: 1 2 3 6 4 2 3 8

· Числовая последовательность с конечным числом членов-заданная последовательность, имеющая конечное число членов.

Например: 5 7 6 8 1 2 3 — числовая последовательность из 7 членов.

· Порожденная последовательность (п/последовательность) — любая последовательность полученная из з/последовательности путем сложения ее членов (запрет на перестановку).

Например:

1. (1+2+3) 6 (4+2) (3+8)

2. 1 2 (3+6) 4 (2+3+8)

3. 1 2 3 6 4 (2+3+8)

1.7 Оценка последовательности

· Оценочная функция — функция, каждому элементу последовательности ставится в соответствие число.

Например:

· Оценка — сумма всех оценок элементов п/последовательности Например:

· Оптимальная п/последовательность (опт п/последовательность) — п/последовательность, имеющая наименьшую оценку (таких п/последовательностей может быть сколь угодно много) Например: 8 7 3 5, 5 3 7 8, 5 7 6 4 1

Пусть оценочная функция имеет только два линейных участка: второй участок II ограничен справа.

Рисунок 1.1

при (1.1)

при (1.2)

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

Для решения поставленной задачи требуется обеспечить обмен информацией системы «ГРО-оценка» и разрабатываемого блока.

Входная информация в блок оптимизации моментов включения:

1. З/последовательность Например: 1 2 2 3 2 2 3 3 4 1

2. Оценочная функция Например: a₁=1, a₂=2, b=4, x=5

Выходная информация из блока оптимизации моментов включения:

1. Опт п/последовательность Например:

8 7 3 5 (1+2+2+3) (2+2+3) 3 (4+1)

5 3 7 8 (1+2+2) 3 (2+2+3) (3+4+1)

5 7 6 4 1 (1+2+2) (3+2+2) (3+3) 4 1

2. Оценка опт п/последовательности Например: 49

ГЛАВА 2. Технология построения полного множества порожденных последовательностей (технология скользящих сечений) С МИНИМАЛЬНЫМ КОЛИЧЕСТВОМ ЧЛЕНОВ Для построения п/последовательностей используется стандартная процедура (СП-Укруп) укрупнения членов заданной последовательности, находящихся на одном участке функции оценки. Участок имеет правую границу. Укрупнение должно обеспечить минимальное число членов, каждый из которых не превосходит правой границы участка.

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

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

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

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

2.1 Операция укрупнения членов, расположенных на одном участке функции Лемма I: Пусть все члены заданной последовательности расположены на I участке оценочной функции и пусть члены всех порожденных последовательностей должны также располагаться на I участке, тогда среди этих п/последовательностей опт п/последовательность имеет минимальное число членов.

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

а) Т.к. при {}, и оптимальная п/последовательность и то минимизация n будет давать опт п/последовательность.

б) Т.к. при {}, и

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

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

Пример:

Оценочная функция: а₁=1, а₂=2, b₁=4, x₁=5.

З/последовательность: 1 2 2 3 2 2 3 3 4 1 из класса {I, x₁У}.

Л№ 1 (1+ 2+ 2) (3+2) (2+ 3) 3 (4+1) 5 5 5 3 5. Оценка = 43

Л№ 2 (1+ 2) (2+3) (2+2) 3 3 (4+1) 3 5 4 3 3 5. Оценка = 47

Л№ 3 1 (2+ 2) (3+2) (2+3) 3 (4+1) 1 4 5 5 3 5. Оценка = 47

Л№ 4 1 2 (2+3) (2+2) 3 3 (4+1) 1 2 5 4 3 3 5. Оценка = 51

Л№ 5 (1+ 2+ 2) (3+2) (2+ 3) 3 4 1 5 5 5 3 4 1. Оценка = 47

На данном примере мы убедились что минимизация членов расположенных на одном участке дала опт п/последовательность Лемма II: Минимальное число членов в операции укрупнения членов, расположенных на одном участке оценочной функции, не зависит от направления укрупнения (слева направо или справа налево, начиная с соответствующих крайних членов заданной последовательности). При этом, если укрупнение начинать не с крайних членов заданной последовательности, то число укрупненных членов будет не меньше предыдущего.

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

Задача: Построить п/последовательность, все члены которой находятся на I участке (,) и число их минимально (min).

Дана последовательность {}, причем (i=1.n)1, (+)x_{1 2 3 4} и (++)>x_1, тогда при укрупнении:

укрупняем «слева-направо»

(+) (+) … (+)-количество членов n/2

укрупняем «справа-налево»

(+) (+) … (+)-количество членов n/2

Процедура укрупнения справа-налево и слева-направо дает одно и тоже число укрупненных членов. Это минимальное количество укрупненных членов при соблюдении условия расположения членов на I участке.

Пример 1:

{1 2 3 2 1 3} x1=4

> {3 3 3 3} k=4

< {3 3 3 3} k=4

Другие процедуры укрупнения дают не меньшее число укрупненных членов.

Пример 2:

Оценочная функция: а₁=1, а₂=2, b₁=4, x₁=5.

З/последовательность: 1 2 2 3 2 2 3 3 4 1 из класса {I, Уx₁}.

укрупняем «слева-направо»

(1 + 2 + 2) 3 2 2 3 3 4 1>5 (3+2) 2 3 3 4 1>5 5 (2+3) 3 4 1>

>5 5 5 3 (4+1)>5 5 5 3 5

укрупняем «справа-налево»

П№ 1 1 2 2 3 2 2 3 3 (4 +1)>1 2 2 3 2 (2+3) 3 5>1 2 2 (3+2) 5 3 5>

>(1+2+2) 5 5 3 5>5 5 5 3 5

Процедура укрупнения справа-налево и слева-направо дает одно и тоже число укрупненных членов

2.2 Процедуры построения п/последовательностей из разных классов з/последовательностей Класс (I,): все элементы заданной последовательности {} находятся на одном участке и их сумма не превосходит правой границы этого участка.

По лемме опт. п/последовательность имеет один член и

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

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

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

a) Первый перенос требует предварительной группировки членов заданной последовательности, но

b) Последующие переносы делаются почленно с добавлением на II участке к уже имеющемуся там члену

2) При каждом переносе на II участок оставшиеся на I участке члены заданной последовательности укрупняются процедурой СП-Укруп. После укрупнения на I участке производится оценка полученной п/последовательности {укрупненные члены на I участке; член на II участке} Важно следить за изменениями числа укрупненных членов на I участке

3) Процедура продолжается до переноса вправо всех членов заданной последовательности. Определяется опт п/последовательность переноса вправо

4) Затем повторяется аналогичная процедура с переносом членов заданной последовательности влево, начиная с первого члена

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

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

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

1) Начиная с первого члена заданной последовательности

a) При всех выделяется фрагмент заданной {} последовательности {}, у которого все члены, кроме последнего, находятся на I участке. К этому фрагменту применяем процедуру, описанную для класса ().

b) При выделяем фрагмент заданной {} последовательности {}, у которого все, кроме, находятся на I участке, а следующий член заданной последовательности. К этому фрагменту применяем процедуру, описанную для класса (). Находим опт. п/последовательность для выделенного фрагмента.

Примечание:

В заданной последовательности, рядом стоящие члены II участка предварительно складываются (укрупняются).

2) Выделяем следующий (за первым выделенным фрагментом) фрагмент заданной последовательности, начиная с первых ее членов не вошедших в первый фрагмент.

С ним выполняем процедуры, описанные выше. Находим опт п/последовательность для этого выделенного фрагмента.

Продолжаем выделение фрагментов заданной последовательности до исчерпания всех ее членов.

Примечание:

Если последний член, то последний фрагмент будет относиться к классу (). или () и для него опт п/последовательность будет определяться процедурой соответствующего класса с переносом членов влево.

Состыковывая (не меняя порядка) полученные опт п/последовательности и объединяя рядом стоящие члены II участка, получим претендента на опт п/последовательность, соответствующую заданной последовательности.

Особенность при состыковке участков, на которых все укрупненные члены находятся на I участке.

1) { }

2) {}

3) {}

2.3 Технология построения полного множества п/последовательностей

· оценочная функция: кусочно-линейная с двумя линейными участками,

· заданная последовательность: из класса {I, У? x₁}.

Скользящее сечение (ск/сечение) для з/последовательности — это набор сечений на заданной последовательности {l₁,…, l_i,…, l_n}, имеющих следующую конструкцию:

а) скользяшие сечения «слева-направо».

Перед каждым членом l_i заданной последовательности {l₁,…, l_i,…, l_n}, начиная с первого l₁, ставится сечение. К члену l_i последовательно прибавляются стоящие справа от него члены заданной последовательности, пока не сформируется член второго участка со следующим свойством

{l_i+ l_i₊₁+… l_к-1+ l_к} x₁, но {l_i+ l_i₊₁+… l_к-1}? x₁

Назовем такой член минимальным членом второго участка (II участка) создаваемой порожденной последовательности.

После так сконструированного члена II участка идут оставшиеся члены заданной последовательности. Получаем порожденную последовательность этого сечения.

Примечание: если перед последними членами заданной последовательности такого члена сконструировать нельзя, то процесс скольжения «слева-направо» заканчивается.

б) скользяшие сечения «справа-налево».

После каждого члена l_i заданной последовательности {l₁,…, l_i,…, l_n}, начиная с последнего l_n, ставится сечение. К члену l_i последовательно прибавляются стоящие слева от него члены заданной последовательности, пока не сформируется член второго участка со следующим свойством

{l_i+ l_i_-1+… l_к+1+ l_к} x₁, но {l_i+ l_i_-1+… l_к+1}? x₁

Перед так сконструированным членом II участка идут оставшиеся члены заданной последовательности. Получаем порожденную последовательность этого сечения.

Примечание: если после первых членов заданной последовательности такого члена сконструировать нельзя, то процесс скольжения «справа-налево» заканчивается.

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

Пример. Заданная последовательность 5 1 3 4 3 2 1 2. Некоторые параметры оценочной функции х₁=6, и х₂ больше суммы членов заданной последовательности.

Построим скользящие сечения только первого уровня с одновременным укрупнением (для каждого положения скользящего сечения) членов, оставшихся на первом участке.

Скользящие сечения первого уровня с одновременным укрупнение членов на первом участке (скольжение слева — направо).

Л1. (5+1+3) 4 (3+2+1) 2 > 9 4 6 2

Л2. 5 (1+3 + 4) (3+2+1) 2 > 5 8 6 2

Л3. (5+1) (3+ 4) (3+2+1) 2 > 6 7 6 2

Л4. (5+1) 3 (4 + 3) (2+1+ 2) > 6 3 7 5

Л5. (5+1) 3 4 (3 +2+1+ 2) > 6 3 4 8

Больше таких скользящих сечений нет.

Скользящие сечения первого уровня с одновременным укрупнение членов на первом участке (скольжение справа — налево).

П1. 5 (1 + 3) 4 (3 +2+1+ 2) > 5 4 4 8 (по оценкам не совпадает с левыми скользящими сечениями) П2. 5 (1 + 3) (4+ 3 +2+1) 2 > 5 4 10 2 (по оценкам не совпадает с левыми скользящими сечениями) П3. 5 (1 + 3) (4+ 3 +2) (1+ 2) > 5 4 9 3

П4. 5 (1 + 3) (4+ 3) (2+1+ 2) > 5 4 7 5 (по оценкам не совпадает с левыми скользящими сечениями) П5. 5 (1 + 3 +4) 3 (2+1+ 2) > 5 8 3 5 (по оценкам не совпадает с левыми скользящими сечениями) П6. (5 +1 + 3) 4 3 (2+1+ 2) > 9 4 3 5

Тот же пример. Заданная последовательность 5 1 3 4 3 2 1 2. Некоторые параметры оценочной функции х₁=6_, и х₂ больше суммы членов заданной последовательности.

Л1. (5+1+3) 4 (3+2+1) 2 > 9 4 6 2

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (5+1+3), минимально превосходивший х₁=6 (это члены 4 3 2 1 2)

Л1-II-правое. Как и в общем случае конструируем на этом множестве скользящие сечения.

Слева-направо: 9 (4+3) (2+1+2) > 9 7 5

9 4 (3+2+1+2) > 9 4 8 (больше нет) Справа-налево: 9 4 (3+2+1+2) > 9 4 8

9 (4+3+2+1) 2 > 9 10 2

9 (4+3+2) 1 2 > 9 9 1 2 (больше нет) Л1-II-левое (нет).

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

(5+1+3+ 4) (3+2+1) 2 > 13 6 2

Л1-II-правое. Как и в общем случае конструируем на множестве 3 2 1 2 скользящие сечения Слева-направо: 13 (3+2+1+2) > 13 8 (больше нет) Справа-налево: 13 (3+2+1+2) > 13 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению Л1.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением Л1

Л2. 5 (1+3 + 4) (3+2+1) 2 > 5 8 6 2

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (1+3+4), минимально превосходивший х₁=6 (это члены 5 3 2 1 2)

Л1-II-правое.

Слева-направо: 5 8 (3+2+1+2) > 5 8 8 (больше нет) Справа-налево: 5 8 (3+2+1+2) > 5 8 8 (больше нет) Л2-II-левое:

Слева-направо: 5 8 (3+2+1+2) > 5 8 8 (больше нет) Справа-налево: 5 8 (3+2+1+2) > 5 8 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению Л2.

(5+1+3+ 4) (3+2+1) 2 > 13 6 2

Л2-II-правое.

Слева-направо: 13 (3+2+1+2) > 13 8 (больше нет) Справа-налево: 13 (3+2+1+2) > 13 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению Л2.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением Л2

Л3. (5+1) (3+ 4) (3+2+1) 2 > 6 7 6 2

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (3+4), минимально превосходивший х₁=6 (это члены 5 1 3 2 1 2)

Л3-II-правое.

Слева-направо: (5+1) 7 (3+2+1+2) > 6 7 8 (больше нет) Справа-налево: (5+1) 7 (3+2+1+2) > 6 7 8 (больше нет) Л3-II-левое:

Слева-направо: (5+1) 7 (3+2+1+2) > 6 7 8 (больше нет) Справа-налево: (5+1) 7 (3+2+1+2) > 6 7 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению Л3.

(5+1+3+ 4) (3+2+1) 2 > 13 6 2

Л3-II-правое.

(5+1+3+ 4) (3+2+1+2) > 13 8

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением Л3

Л4. (5+1) 3 (4 + 3) (2+1+ 2) > 6 3 7 5

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (4+3), минимально превосходивший х₁=6 (это члены 5 1 3 2 1 2)

Л4-II-правое.

Слева-направо: (5+1+3) 7 (2+1+2) > 9 7 5 (больше нет) Справа-налево: (5+1+3) 7 (2+1+2) > 9 7 5 (больше нет) Л4-II-левое:

Слева-направо: (5+1+3) 7 (2+1+2) > 9 7 5 (больше нет) Справа-налево: (5+1+3) 7 (2+1+2) > 9 7 5 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению Л4.

(5+1) 3 (4+3+2+1+2) > 6 3 12

Л4-II-правое.

Слева-направо: (5+1+3) 12 > 9 12 (больше нет) Справа-налево: (5+1+3) 12 > 9 12 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению Л4.

(5+1+3)(4+3+2+1+2) > 9 12

(5+1+3+ 4)(3+2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением Л4

Л5. (5+1) 3 4 (3 +2+1+ 2) > 6 3 4 8

Л5-II-правое.

Слева-направо: (5+1) 7 (3+2+1+2) > 6 7 8 (больше нет) Справа-налево: (5+1) 7 (3+2+1+2) > 6 7 8 (больше нет) Л5-II-левое:

(5+1+3+ 4) (3+2+1) 2 > 13 6 2

Л1-II-правое.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением Л5

Больше таких скользящих сечений нет.

П1. 5 (1 + 3) 4 (3 +2+1+ 2) > 5 4 4 8 (по оценкам не совпадает с левыми скользящими сечениями)

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (3+2+1+2), минимально превосходивший х₁=6 (это члены 5 1 3 4)

П1-II-правое (нет) П1-II-левое

Слева-направо: (5+1+ 3) 4 8 > 9 4 8

5 (1+ 3+4) 8 > 5 8 8

(5+1) (3+4) 8 > 6 7 8 (больше нет) Справа-налево: (5+1) (3+4) 8 > 6 7 8

5 (1+3+4) 8 > 5 8 8

(5+1+3) 4 8 > 9 4 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П1.

(5+1+3) 4 (3+2+1+2) > 9 4 8

П1-II-правое.

Слева-направо: 9 (4+3+2+1+2) > 9 12 (больше нет) Справа-налево: 9 (4+3+2+1+2) > 9 12 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П1.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением П1

П2. 5 (1 + 3) (4+ 3 +2+1) 2 > 5 4 10 2 (по оценкам не совпадает с левыми скользящими сечениями)

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (4+3+2+1), минимально превосходивший х₁=6 (это члены 5 1 3 2)

П2-II-правое

Слева-направо: (5+1+ 3) 10 2 > 9 10 2 (больше нет) Справа-налево: (5+1+3) 10 2 > 9 10 2 (больше нет) П2-II-левое

Слева-направо: (5+1+ 3) 10 2 > 9 10 2 (больше нет) Справа-налево: (5+1+3) 10 2 > 9 10 2 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П2.

(5+1+ 3) (4+ 3 +2+1) 2 > 9 10 2

П2-II-правое.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением П2

П3. 5 (1 + 3) (4+ 3 +2) (1+ 2) > 5 4 9 3

Скользящие сечения второго уровня (работаем с остатком членов заданной последовательности, не вошедших в выделенный член второго участка (4+3+2), минимально превосходивший х₁=6 (это члены 5 1 3 1 2)

П3-II-правое

Слева-направо: (5+1+ 3) 9 (1+2) > 9 4 8 (больше нет) Справа-налево: (5+1+ 3) 9 (1+2) > 9 4 8 (больше нет) П3-II-левое

Слева-направо: (5+1+ 3) 9 3 > 9 4 8 (больше нет) Справа-налево: (5+1+ 3) 9 3 > 9 4 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П3.

(5+1+3) 4 (3+2+1+2) > 9 4 8

П3-II-правое.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением П3

П4. 5 (1 + 3) (4+ 3) (2+1+ 2) > 5 4 7 5 (по оценкам не совпадает с левыми скользящими сечениями)

П4-II-правое

Слева-направо: (5+1+ 3) 7 (2+1+2) > 9 7 5 (больше нет) Справа-налево: (5+1+ 3) 7 (2+1+2) > 9 7 5 (больше нет) П4-II-левое

Слева-направо: (5+1+ 3) 7 (2+1+2) > 9 7 5 (больше нет) Справа-налево: (5+1+ 3) 7 (2+1+2) > 9 7 5 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П4.

(5+1+3) 7 (2+1+2) > 9 7 5

П4-II-правое.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением П4

П5. 5 (1 + 3 +4) 3 (2+1+ 2) > 5 8 3 5 (по оценкам не совпадает с левыми скользящими сечениями)

П5-II-правое

Слева-направо: 5 8 (3+2+1+2) > 5 8 8 (больше нет) Справа-налево: 5 8 (3+2+1+2) > 5 8 8 (больше нет) П5-II-левое

5 8 (3+2+1+2) > 5 8 8

П5-II-правое.

Слева-направо: (5+8) (3+2+1+2) > 13 8 (больше нет) Справа-налево: (5+8) (3+2+1+2) > 13 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П5.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением П5.

П6. (5 +1 + 3) 4 3 (2+1+ 2) > 9 4 3 5

П6-II-правое

Слева-направо: 9 (4+3) (2+1+2) > 9 7 5

9 4 (3+2+1+2) > 9 4 8 (больше нет) Справа-налево: 9 (4+3) (2+1+2) > 9 7 5

9 4 (3+2+1+2) > 9 4 8 (больше нет) П6-II-левое

Слева-направо: 9 (4+3) (2+1+2) > 9 7 5

9 4 (3+2+1+2) > 9 4 8 (больше нет) Справа-налево: 9 (4+3) (2+1+2) > 9 7 5

9 4 (3+2+1+2) > 9 4 8 (больше нет) Продолжение конструирования порожденных последовательностей, строившихся по скользящему сечению П6.

(5+1+3) 4 (3+2+1+2) > 9 4 8

П6-II-правое.

(5+1+3+ 4+3) (2+1+2) > 16 5

(5+1+3+ 4+3+2) (1+2) > 18 3

(5+1+3+ 4+3+2+1) 2 > 19 2

(5+1+3+ 4+3+2+1+ 2) > 21 (больше нет) Построены все порожденные последовательности, связанные со скользящим сечением П6

Больше таких скользящих сечений нет.

Пример.

Оценочная функция: а₁=1, а₂=2, b₁=4, x₁=5.

З/последовательность: 1 2 2 3 2 2 3 3 4 1 из класса {I, x₁У}.

Скользящие сечения (далее их назовем «скользящими сечениями первого уровня) и соответствующие им порожденные последовательности:

скольжение «слева-направо»

Л№ 1 (1 + 2 + 2 + 3) 2 2 3 3 4 1

Л№ 2 1 (2 + 2 + 3) 2 2 3 3 4 1

Л№ 3 1 2 (2 + 3 + 2) 2 3 3 4 1

Л№ 4 1 2 2 (3 + 2 + 2) 3 3 4 1

Л№ 5 1 2 2 3 (2 + 2 + 3) 3 4 1

Л№ 6 1 2 2 3 2 (2 + 3 + 3) 4 1

Л№ 7 1 2 2 3 2 2 (3 + 3) 4 1

Л№ 8 1 2 2 3 2 2 3 (3+ 4) 1

скольжение «справа-налево»

П№ 1 1 2 2 3 2 2 3 (3 + 4 +1)

П№ 2 1 2 2 3 2 2 3 (3 + 4) 1

П№ 3 1 2 2 3 2 2 (3 + 3) 4 1

П№ 4 1 2 2 3 (2 + 2 + 3) 3 4 1

П№ 5 1 2 2 (3 + 2 + 2) 3 3 4 1

П№ 6 1 2 (2 + 3 + 2) 2 3 3 4 1

П№ 7 1 (2 + 2 + 3) 2 2 3 3 4 1

Для каждого из скользящих сечений, полученных скольжением «слева-направо», (для порожденных ими последовательностей) выполняются следующие процедуры:

а) укрупняются члены, стоящие справа от сконструированного члена II участка. Укрупнение производится «слева-направо».

Пример: Л№ 3 1 2 (2 +3 + 2) 2 3 3 4 1

Результат укрупнения:

1 2 (2 +3 + 2) (2 +3) 3 (4+1) 1 2 7 5 3 5. Оценка = 51

б) наращивается сконструированный член II участка, последовательным прибавлением к нему членов, стоящих справа от сконструированного члена II участка.

Результат наращивания: Л№ 3

1 2 (2 + 3 + 2) 2 3 3 4 1 1 2 7 2 3 3 4 1 Оценка = 59

1 2 (7 + 2) 3 3 4 1 Оценка = 59

1 2 (9 + 3) 3 4 1 Оценка = 61

1 2 (12 + 3) 4 1 Оценка = 63

1 2 (15 + 4) 1 Оценка = 67

1 2 (19 + 1) Оценка = 65

Укрупнение и наращивание:

Пример: Л№ 1

(1 + 2 + 2 + 3) (2 + 2) 3 3 (4 + 1) 8 4 3 3 5 Оценка = 46

(8 + 2) (2 + 3) 3 (4 +1) Оценка = 49

(10 + 2) 3 3 (4 + 1) Оценка = 53

(12 + 3) 3 (4 + 1) Оценка = 55

(15 + 3) (4 + 1) Оценка = 57

(18 + 4) 1 Оценка = 65

(22 + 1) Оценка = 63

Пример: Л№ 2

1 (2 + 2 + 3) (2 + 2) 3 3 (4 + 1) 1 7 4 3 3 5 Оценка = 51

1 (7 + 2) (2 + 3) 3 (4 + 1) Оценка = 51

1 (9 + 2) 3 3 (4 + 1) Оценка = 55

1 (11 + 3) 3 (4 + 1) Оценка = 61

1 (14 + 3) (4 + 1) Оценка = 59

1 (17 + 4) 1 Оценка = 67

1 (21+1) Оценка = 65

Пример: Л№ 3

1 2 (2 +3 + 2) (2 + 3) 3 (4 + 1) 1 2 7 5 3 5 Оценка = 51

1 2 (7 + 2) 3 3 (4 + 1) Оценка = 55

1 2 (9 + 3) 3 (4 + 1) Оценка = 57

1 2 (12 + 3) (4 + 1) Оценка = 59

1 2 (15 + 4) 1 Оценка = 67

1 2 (19 + 1) Оценка = 65

Пример: Л№ 4

1 2 2 (3 + 2 + 2) 3 3 (4 + 1) 1 2 2 7 3 3 5 Оценка = 55

1 2 2 (7 + 3) 3 (4 + 1) Оценка = 57

1 2 2 (10 + 3) (4 + 1) Оценка = 57

1 2 2 (13 + 4) 1 Оценка = 67

1 2 2 (17 + 1) Оценка = 65

Пример: Л№ 5

1 2 2 3 (2 + 2 + 3) 3 (4 + 1) 1 2 2 3 7 3 5 Оценка = 55

1 2 2 3 (7 + 3) (4 + 1) Оценка = 57

1 2 2 3 (10 + 4) 1 Оценка = 65

1 2 2 3 (14 + 1) Оценка = 63

Пример: Л№ 6

1 2 2 3 2 (2 + 3 + 3) (4 + 1) 1 2 2 3 2 8 5 Оценка = 54

1 2 2 3 2 (8 + 4) 1 Оценка = 65

1 2 2 3 2 (12 + 1) Оценка = 63

Пример: Л№ 7

1 2 2 3 2 2 (3 + 3) (4 + 1) 1 2 2 3 2 2 6 5 Оценка = 57

1 2 2 3 2 2 (6 + 4) 1 Оценка = 65

1 2 2 3 2 2 (10 + 1) Оценка = 63

Пример: Л№ 8

1 2 2 3 2 2 3 (3+ 4) 1 1 2 2 3 2 2 3 7 1 Оценка = 63

1 2 2 3 2 2 3 (7 + 1) Оценка = 61

Для каждого из скользящих сечений, полученных скольжением «справа-налево», (для порожденных ими последовательностей) выполняются следующие процедуры:

а) укрупняются члены, стоящие слева от сконструированного члена II участка. Укрупнение производится «справа-налево».

Пример:

П№ 3 1 2 2 3 2 2 (3 +3) 4 1

Результат укрупнения:

(1+ 2) (2 +3) (2+ 2) (3 +3) 4 1 3 5 4 6 4 1 Оценка = 49

б) наращивается сконструированный член II участка, последовательным прибавлением к нему членов, стоящих слева от сконструированного члена II участка.

Результат наращивания: П№ 3

1 2 2 3 2 2 (3 +3) 4 1 1 2 2 3 2 2 6 4 1 Оценка = 61

1 2 2 3 2 (2 + 6) 4 1 Оценка = 61

1 2 2 3 (2 + 8) 4 1 Оценка = 61

1 2 2 (3 + 10) 4 1 Оценка = 63

1 2 (2 + 13) 4 1 Оценка = 53

1 (2 + 15) 4 1 Оценка = 63

(1 + 17) 4 1 Оценка = 61

Укрупнение и наращивание:

Пример: П№ 1

(1 + 2 + 2) (3 + 2) (2 + 3) (3 + 4 + 1) 5 5 5 8 Оценка = 45

(1 + 2) (2 + 3) (2 + 2) (3 + 8) Оценка = 51

(1 + 2 + 2) (3 + 2) (2 + 11) Оценка = 51

(1 + 2) (2 + 3) (2 + 13) Оценка = 45

(1 + 2 + 2) (3 + 15) Оценка = 57

(1 + 2) (2 + 18) Оценка = 61

1 (2 + 20) Оценка = 65

(1 + 22) Оценка = 63

Пример: П№ 2

(1 + 2 + 2) (3 + 2) (2 + 3) (3 + 4) 1 5 5 5 7 1 Оценка = 47

(1 + 2) (2 + 3) (2 + 2) (3 + 7) 1 Оценка = 65

(1 + 2 + 2) (3 + 2) (2 + 10) 1 Оценка = 53

(1 + 2) (2 + 3) (2 + 12) 1 Оценка = 57

(1 + 2 + 2) (3 + 14) 1 Оценка = 59

(1 + 2) (2 + 17) 1 Оценка = 63

1 (2 + 19) 1 Оценка = 67

(1 + 21) 1 Оценка = 65

Пример: П№ 3

(1 + 2) (2 + 3) (2 + 2) (3 + 3) 4 1 3 5 4 6 4 1 Оценка = 49

(1 + 2 + 2) (3 + 2) (2 + 6) 4 1 Оценка = 49

(1 + 2) (2 + 3) (2 + 8) 4 1 Оценка = 53

(1 + 2 + 2) (3 + 10) 4 1 Оценка = 55

(1 + 2) (2 + 13) 4 1 Оценка = 59

1 (2 + 15) 4 1 Оценка = 63

(1 + 17) 4 1 Оценка = 61

Пример: П№ 4

(1 + 2) (2 + 3) (2 + 2 + 3) 3 4 1 3 5 7 3 4 1 Оценка = 51

(1 + 2 + 2) (3 + 7) 3 4 1 Оценка = 53

(1 + 2) (2 + 10) 3 4 1 Оценка = 57

1 (2 + 12) 3 4 1 Оценка = 61

(1 + 14) 3 4 1 Оценка = 59

Пример: П№ 5

(1 + 2 + 2) (3 + 2 + 2) 3 3 4 1 5 7 3 3 4 1 Оценка = 51

(1 + 2) (2 + 7) 3 3 4 1 Оценка = 55

1 (2 + 9) 3 3 4 1 Оценка = 59

(1 + 11) 3 3 4 1 Оценка = 57

Пример: П№ 6

(1 + 2) (2 + 3 + 2) 2 3 3 4 1 3 7 2 3 3 4 1 Оценка = 55

1 (2 + 7) 2 3 3 4 1 Оценка = 59

(1 +9) 2 3 3 4 1 Оценка = 57

Пример: П№ 7

1 (2 + 2 + 3) 2 2 3 3 4 1 1 7 2 2 3 3 4 1 Оценка = 59

(1 + 7) 2 2 3 3 4 1 Оценка = 57

Для каждой из полученных таким образом порожденных последовательностей, содержащих только один член II участка, на оставшихся на I участке членах заданной последовательности реализуем процедуру скользящего сечения (скользящие сечения второго уровня) «слева-направо» и «справа налево» как описано выше. Полученные фрагменты стыкуем с полученным при скольжении первого уровня членом II участка. В получаемых порожденных последовательностях при этом конструируются вторые члены II участка.

Если в порожденных последовательностях, образующихся после скольжения II уровня, остались члены заданной последовательности (члены I участка), то на них организуется скользящие сечения III уровня.

2.4 Процедура выделения оптимальной порожденной последовательности Для каждого скользящего сечения первого уровня строятся скользящие сечения второго уровня. Для каждого сечения второго уровня строятся скользящие сечения третьего уровня и т. д.

Получаем пирамиду упорядоченных скользящих сечений

· скользящее сечение первого уровня,

· под ним соответствующие ему скользящие сечения второго уровня,

· под каждым сечением второго уровня — сечения третьего уровня,

· и т. д.

Начиная с нижнего уровня для каждого скользящего сечения ближайшего вышестоящего уровня находиться оптимальная порожденная последовательность среди «подчиненных» последовательностей с ближайшего нижнего уровня.

Показать весь текст

Заполнить форму текущей работой