Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1


НазваниеУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
страница6/9
Дата публикации06.05.2013
Размер1.03 Mb.
ТипЗакон
userdocs.ru > География > Закон
1   2   3   4   5   6   7   8   9

Одномерная задача динамического программирования.

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

Необходимо оптимальным образом распределить ресурс в объеме xo по n вариантам (объектам, схемам, этапам) при целевой функции



и ограничениях

,

где xi – объем ресурса, назначаемый по i-му варианту (0 xi xо);

f(x)– нелинейная функция, определяющая эффект (затраты) в зависимости от значений x;

n – общее число вариантов; xобщ – общий объем распределяемого ресурса.

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

Обозначим через xci – количество ресурса, назначаемого суммарно по i-му варианту и всем предыдущим вариантам. При этом объем ресурса по предыдущим вариантам распределен оптимально исходя из минимума затрат или максимума эффекта.

Тогда целевая функция Zi при рассмотрении i-го этапа решения определяется по выражению

Zi(xci, xi )= fi(xi) + f* i-1 (xci - xi ),

где 0 xсi xобщ при i  n-1 и xсi= xобщ при i = n;

f*i-1 – функция, определяющая эффект (затраты) оптимальным образом по предыдущим вариантам в зависимости от объема ресурса xci-1;

Значение f*i определяется по Zi :

для i =1 (xc1=x1);

, .

Определение и соответствующих им при данном xсi производятся поэтапно от i=2 до i=n.

По окончательному результату поэтапных расчетов формируется оптимальное решение {xоi}:

xоi= (для i = n);

xоi = при (для);

(для i=1).

Вариант алгоритма решения однопродуктовой задачи динамического программирования приведен на рисунке 3.24. Решение предусмотрено для целевой функции, подлежащей оптимизации на максимум. Для решения задачи на минимум необходимо ввести исходные значения sвji с отрицательным знаком или внести изменения в блоках 12 (заменить 1E+12 на -1E+12) и 15 (условие < на >).

Выводимые j, kjidx , snm представляют соответственно номер варианта, объем ресурса по варианту и значение целевой функции для оптимального решения.

1

Пуск

2

Ввод n, xoбщ, dx n – число вариантов распределения ресурса

xoбщ – общий объем ресурса

dx – дискретность распределения ресурса

3

m = xoбщ/ dx m – число разбиений ресурса

4

sвji,; sвji – эффект (затраты) по j-му варианту

при объеме использования ресурса xi

5 6

s1i = sв1i

k1i = i


7



8 Да 9 10

Нет

r = m j = n r = 1


11

17

r = m

12 18

p = 1E+12



13

16 19

sji =cl : kji =l; p = cl Вывод j, kjrdx
Да
Нет 15 14 20

cl < p cl =sвjl + sj-1, i-l r = r - kjr


21

Вывод snm

Рисунок 3.24 – Алгоритм решения однопродуктовой задачи

динамического программирования 22

Останов

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

Для проведения моделирования могут использоваться как универсальные языки программирования так и проблемно-ориентированные - GPSS, SIMULA и др.

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

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

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

Оптимизация при наличии ограничений случайным поиском.

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

Например, на Бейсике подпрограмма без учета ограничений и с учетом ограничений будет при оптимизации на минимум следующей:

m1:

' п/п вычисления Z без учета ограничений

Z= …

Return

m1:

' п/п вычисления Z с учетом ограничений

if (ограничение 1 нарушено) then m2

if (ограничение 2 нарушено) then m2

………..

if (ограничение n нарушено) then m2

Z= …:goto m3

m2:

Z= 1E20

m3:

return

1

Пуск

2

Ввод m,  m – число оптимизируемых переменных;

 – относительная точность поиска

3

Ввод xнi,xвi, xнi и xвi – соответственно нижняя и верхняя

начальные границы поиска оптимума

4

Ввод h, aш ,bш, l h –относительный шаг поиска; l – предельное

число неудачных попыток по каждой переменной;

5 aш и bш – соответственно коэффициент уменьшения

шага поиска и определения шкалы поиска

L = l m


6




7

si = (xвi - xнi)/ bш

8 на минимум


xтi = (xвi + xнi)/2 15 16

xпi= xтi Zп > Z Да xпi = xтi,

Zп= Z
Нет

9 17 11

Z = f(Xт) k = k + 1


10

18 Да

  • Zп = Z k <= L 12



Нет

11 19

k = 0 16,21 h = h aш

12 18 20 Да 21

i = 1, m h >=  aш Вывод xпi ,

Zп, h

Нет

13 22

xтi = xпi + si h (2 r -1) Вывод Zп,xпi, 11

23

  1. Останов

Z = f(Xт)

Рисунок 3.17 – Алгоритм многомерной оптимизации

случайным поиском с пересчетом
Отыскание кратчайших расстояний между пунктами транспортной сети. Алгоритм для реализации на компьютере.

Отыскание кратчайших расстояний между пунктами транспортной сети возможно по методу потенциалов, методу "метлы", динамическому методу, на основе теории графов (метод Флойда) и др.

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

1) Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал vi = 0.

2) Находятся все звенья, для которых начальным пунктам i присвоены потенциалы vi, а конечным пунктам j не присвоены. Если таких звеньев нет, то решение закончено (на п.5), а иначе на следующий п.3.

3) Для найденных звеньев по п.2 рассчитываются значения потенциалов конечных пунктов j по следующей формуле:

uj(i) = vi + lij ,

где uj(i) – потенциал конечного пункта j звена i-j; lij – длина звена i-j.

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

,

где { uj(i) } – множество значений потенциалов конечных пунктов j звеньев i-j, i-м начальным пунктам которых ранее присвоены потенциалы; ur(s) – потенциал конечного пункта r звена s-r , являющийся наименьшим по значению элементом множества { uj(i) }.

Потенциал ur(s) присваивается соответствующему конечному пункту (vs = ur(s)), а звено r-s отмечается стрелкой.

В случае если несколько значений потенциалов множества {vj(i)} окажутся равными и наименьшими, то необходимо установить, относятся они к одному и тому же пункту или нет.

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

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

4) переход на п. 2

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

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

Таблица 3.2 – Кратчайшие расстояния между пунктами транспортной сети (км)

Пункты

1

. . .

j

. . .

n

1

0




l1j




l1n

.

.

.






i

li1




lij




lin

.

.

.






n

ln1




lnj




lnn=0

1   2   3   4   5   6   7   8   9

Похожие:

Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКурс «Статистические методы управления качеством» специальность 200503...
Особенности эмпирических данных. Случайные величины. Распределения случайных величин. Статистические гипотезы
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКоллоквиум 2 тв и мс
Числовые характеристики случайных величин: математическое ожидание (понятие, свойства)
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон больших чисел
Корреляционная матрица случайного вектора. Коэффициент корреляции двух случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconАвтокорреляция случайного возмущения. Причины. Последствия
Алгоритм теста Голдфелда-Квандта на наличие (отсутствие) гетероскедастичности случайных возмущений
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон распределения Пуассона и его характеристики
Локальная предельная теорема Муавра-Лапласа. Теорема Пуассона Понятие случайной величины. Виды случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗачет Казаринова Ирина Николаевна Старовойтова Ольга Рафаэльевна...
Методология, методика, программа, метод, алгоритм исследования, парадигма, научная традиция
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 icon2: Элементы векторной алгебры
Различают понятия величин, которые характеризуются од -ним числом скалярные величины (например: масса, объём, длина, площадь и т...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconНа рисунке 1 приведен график зависимости скорости движения тела от...
Чему равно отношение силы гравитационного взаимодействия, действующей со стороны Луны на Землю, к силе гравитационного взаимодействия,...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЧто такое метрология?
Размерность качественная характеристика физических величин. Правила определения размерности производных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconПрограмма учебного курса «Физическая география России»
В конце программы приведен перечень экзаменационных вопросов за все три семестра: два на 4 курсе и 1 на пятом курсе см!!!
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница