Xreferat.com » Рефераты по информатике и программированию » Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса

Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса

интервале [0,1], имеет равномерный закон распределения


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


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


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. (3)


Вероятность каждого значения (3) равна 2-k. Эти значения можно получить следующим образом


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Случайная величина Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса имеет математическое ожидание


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Учитывая, что


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


и выражение для конечной суммы геометрической прогрессии


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, (4)


получаем:


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. (5)


Аналогично можно определить дисперсию величины Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса:


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса,


где

Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса

Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса,


откуда


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса,


или, используя формулу (4), получаем:


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. (6)

Согласно формуле (5) оценка Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса величины ξ* получается смещённой при конечном k. Это смещение особенно сказывается при малом k. Поэтому вместо Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса вводят оценку


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, (7)


где


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Очевидно, что случайная величина ξ в соответствии с соотношением (3) может принимать значения

Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, i=0,1,2,…, 2k-1

с вероятностью p=1/2k.

Математическое ожидание и дисперсию величины ξ можно получить из соотношений (5) и (6), если учесть (7). Действительно,


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса;


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Отсюда получаем выражение для среднеквадратичного значения в виде


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. (8)


Напомним, что для равномерно распределённой в интервале [0,1] величины x имеем


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


Из формулы (8) следует, что при Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса среднеквадратичное отклонение σ квазиравномерной совокупности стремится к Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. Ниже приведены значения отношения среднеквадратичных значений двух величин ξ и η в зависимости от числа разрядов, причём величина η имеет равномерное распределение в интервале [0,1] (табл. 1).


Таблица 1

k 2 3 5 10 15
σξ/ση 1,29 1,14 1,030 1,001 1,00

Из табл. 1 видно, что при k>10 различие в дисперсиях несущественно.

На основании вышеизложенного задача получения совокупности квазиравномерных чисел сводится к получению последовательности независимых случайных величин zi (i=1,2,…, k), каждая из которых принимает значение 0 или 1 с вероятностью 1/2. Различают два способа получения совокупности этих величин: физический способ генерирования и алгоритмическое получение так называемых псевдослучайных чисел. В первом случае требуется специальная электронная приставка к цифровой вычислительной машине, во втором случае загружаются блоки машины.

При физическом генерировании чаще всего используются радиоактивные источники или шумящие электронные устройства. В первом случае радиоактивные частицы, излучаемые источником, поступают на счётчик частиц. Если показание счётчика чётное, то zi=1, если нечётное, то zi=0. Определим вероятность того, что zi=1. Число частиц k, которое испускается за время Δt, подчиняются закону Пуассона:


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Вероятность чётного числа частиц


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Таким образом, при больших λΔt вероятность P{Zi=1} близка к 1/2.

Второй способ получения случайных чисел zi более удобен и связан с собственными шумами электронных ламп. При усилении этих шумов получается напряжение u(t), которое является случайным процессом. Если брать его значения, достаточно отстоящие друг от друга, так чтобы они были некоррелированы, то величины u(ti) образуют последовательность независимых случайных величин. Обычно выбирают уровень отсечки a и полагают


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


причём уровень a следует выбрать так, чтобы


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


Также применяется более сложная логика образования чисел zi. В первом варианте используют два соседних значения u(ti) и u(ti+1), и величина Zi строится по такому правилу:

Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


Если пара u(ti) – a и u(ti+1) – a одного знака, то берётся следующая пара. Требуется определить вероятность при заданной логике. Будем считать, что P {u(ti)>a}=W и постоянная для всех ti. Тогда вероятность события Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса равна по формуле событий A1Hv. Здесь Hv – это вероятность того, что v раз появилась пара одинакового знака


u(ti) – a; u(ti+1) – a. (9)


Поэтому вероятность события A1Hv


P{A1Hv}=W (1-W) [W2+(1-W)2]v.


Это – вероятность того, что после v пар вида (9) появилось событие A1. Оно может появиться сразу с вероятностью W (1-W), оно может появиться и после одной пары вида (9) с вероятностью


W (1-W) [W2+(1+W)2]


и т.д. В результате


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


или


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.

Отсюда следует, что если W=const, то логика обеспечивает хорошую последовательность случайных чисел. Второй способ формирования чисел zi состоит в следующем:


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


Пусть

W=P {u(ti)>a}=1/2+ξ.

Тогда

P{Zi=1}=2W (1-W)=1/2–2ξ2.

Чем меньше ξ, тем ближе вероятность P{Zi=1} к величине 1/2.

Для получения случайных чисел алгоритмическим путём с помощью специальных программ на вычислительной машине разработано большое количество методов. Так как на ЦВМ невозможно получить идеальную последовательность случайных чисел хотя бы потому, что на ней можно набрать конечное множество чисел, такие последовательности называются псевдослучайными. На самом деле повторяемость или периодичность в последовательности псевдослучайных чисел наступает значительно раньше и обусловливается спецификой алгоритма получения случайных чисел. Точные аналитические методы определения периодичности, как правило, отсутствуют, и величина периода последовательности псевдослучайных чисел определяется экспериментально на ЦВМ. Большинство алгоритмов получается эвристически и уточняется в процессе экспериментальной проверки. Рассмотрение начнём с так называемого метода усечений. Пусть задана произвольная случайная величина u, изменяющаяся в интервале [0,1], т.е. Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. Образуем из неё другую случайную величину


un=u [mod 2-n], (10)

где u [mod 2-n] используется для определения операции получения остатка от деления числа u на 2-n. Можно доказать, что величины un в пределе при Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса имеют равномерное распределение в интервале [0,1].

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

Пример 1. Пусть u = 0,10011101… = 1·1/2 + 0·1/22 + 0·1/23 + 1·1/24 + 1·1/25 + 1·1/26 + 0·1/27 + 1·1/28 + …

Выберем для простоты n=4. Тогда {u mod 2-4} = 0,1101…

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

При проверке качества псевдослучайных чисел прежде всего интересуются длиной отрезка апериодичности и длиной периода (рис. 3). Под длиной отрезка апериодичности L понимается совокупность последовательно полученных случайных чисел α1, …, αL таких, что αi Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процессаαj при Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, но αL+1 равно одному из αk (Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса).

Под длиной периода последовательности псевдослучайных чисел понимается T=L-i+1. Начиная с некоторого номера i числа будут периодически повторяться с этим периодом (рис. 3).


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса

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


2.2 Точность метода Монте-Карло


Метод Монте-Карло применяется там, где не требуется высокой точности. Например, если определяют вероятность поражения мишени при стрельбе, то разница между p1=0,8 и p2=0,805 несущественна. Обычно считается, что метод Монте-Карло позволяет получить точность примерно 0,01–0,05 максимального значения определяемой величины.

Получим некоторые рабочие формулы. Определим по методу Монте-Карло вероятность пребывания системы в некотором состоянии. Эта вероятность оценивается отношением


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса,


где M – число пребываний системы в этом состоянии в результате N моделирований. Учитывая выражение для дисперсии величины M/N


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


и неравенство Чебышёва


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса, (11)


напишем

Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. (12)


Величина


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


есть ни что иное, как ошибка моделирования по методу Монте-Карло. С помощью формулы (11) можно написать следующую формулу для величины (12):


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса,


или


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса,


где p0 – вероятность невыполнения этой оценки. С помощью частоты M/N может быть получена оценка математического ожидания mx некоторой случайной величины X. Ошибка этой оценки


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


находится с помощью соотношения


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.

Отсюда видно, что ошибка моделирования находится в квадратичной зависимости от числа реализаций, т.е.


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса. (13)


Пример 2. Допустим, что определяется математическое ожидание ошибки x поражения мишени. Процесс стрельбы и поражения моделируется на ЦВМ по методу Монте-Карло. Требуется точность моделирования δ = 0,1 м с вероятностью p = 1-p0 = 0,9 при заданной дисперсии σx = 1 м. Необходимо определить количество моделирований N. По формуле (13) получаем:


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса.


При таком количестве реализаций обеспечивается δ=0,1 м с вероятностью p=0,9.


3. Метод ветвей и границ


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

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

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

Комплексный подход по схеме ветвлений объединяет целый ряд близких комбинаторных методов, как-то: метод ветвей и границ, метод последовательного конструирования, анализа и отсева вариантов и др. Общая идея метода крайне проста. Множество допустимых планов некоторым способом разбивается на подмножество. В свою очередь каждое из подмножеств по этому же или другому способу снова разбиваются на подмножества до тех пор, пока каждое подмножество не будет представлять собой точку в многомерном пространстве. В силу конечности наборов значений переменных дерево подмножеств (схема ветвления) конечно.

Построение схемы ветвления есть ни что иное, как формирование процедуры перебора. Перебор может осуществляться различными способами. Сечение исходной допустимой области G0 гиперплоскостью на части G11 и G12 с последующим разделением G11 на G21 и G22 представляет собой построение дерева ветвлений с соответствующими подмно-жествами, как это показано на рис. 4.


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса


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

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

Схема ветвления иллюстрируется решением обобщённой задачи одномерного раскроя (пример 3) с конкретными числовыми данными.

Пример 3.

Имеются заготовки длиной a1=18, a2=16, a3=13. Разрезая их на части, но не склеивая, можно получать детали длинной b1=12, b2=10, b3=8, b4=6, b5=5, b6=4. Стоимость каждой детали известна и в условных единицах численно равна их длине. Перечисленные детали представляют собой «портфель заказов», который желательно обеспечить в первую очередь. В том случае, если это невозможно, максимизируется стоимость получаемых деталей из заданной номенклатуры. Если же портфель заказов обеспечивается, необходимо максимизировать стоимость дополнительной продукции.

Величину Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса будем называть дефицитом. Отрицательность дефицита ещё не означает существование варианта раскроя, при положительном дефиците раскрой невозможен. Это свойство может быть использовано для указания перспективности варианта. Так, если заготовка a2 раскраивается на b2 и b5, то независимо от комбинаций остальных отрезков раскрой невыполним, поскольку для оставшихся отрезков дефицит положителен.

Первые этапы приводимой ниже схемы ветвления, использующей комбинаторные отношения подмножеств вариантов, показаны на рис. 5. На первом этапе формируются разбиения первой группы отрезков (заготовок) на вторую группу (деталей) независимо от того, какой именно отрезок первой группы разрезается. Количество ветвей первого этапа можно вычислить лишь по рекуррентным соотношениям. Смысл подмножества {1, 2, 3} заключается в том, что один из отрезков первой группы в результате раскроя даёт один отрезок второй группы, один из оставшихся отрезков первой группы раскраивается на два отрезка второй группы из числа оставшихся и, наконец, последний отрезок первой группы делится на три части, образуя три отрезка второй группы. На втором этапе формируются все перестановки (с учётом порядка) элементов первого этапа. Скажем, вариант {2, 1, 3} означает, что именно первый элемент первой группы a1 разрезается на две части и т.д.


Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: