Принцип оптимальности. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выйгрыш на данном шаге плюс оптимальный выйгрыш на всех последующих шагах был максимальным.
Общая последовательность решения задач динамического программирования следующая.
1. Выбрать способ описания процесса, т.е. параметры, характеризующие состояние системы, фазовое пространство и способ членения операции на шаги.
2. Записать выигрыш wi на i-том шаге в зависимости от состояния системы S в начале этого шага и управления Ui:
wi= wi(S, Ui)
3. Записать для i-того шага функцию выражающую изменение состояния системы от S к S’ под влиянием управления Ui:
S’=j(S, Ui).
4. Записать основное функциональное уравнение, выражающее функцию Wi(S) через Wi+1(S):
Wi(S)=maxUi{wi(S, Ui)+Wi+1(ji(S, Ui))}
5. Найти функцию Wm(S)=maxUm{wm(S, Um)} – условный оптимальный выйгрыш для последнего шага (максимум берется только по тем направлениям, которые приводят систему в заданную область конечных состояний S*w ) и соответствующее ей условное оптимальное управление на последнем шаге Um(S).
6. Зная Wm(S) и пользуясь уравнением из п.4, при конкретном виде функций wi(S, Ui), ji(S, Ui), найти одну за другой функции:
Wm-1(S), Wm-2(S), … , W1(S)
и соответствующие им условные оптимальные управления:
Um-1(S), Um-2(S), … , U1(S).
7. Если начальное состояние системы S0 задано, то найти оптимаьный выйгрыш Wmax(S0), и далее безусловные оптимальные управления (и, при необходимости, конечное состояние системы) по цепочке:
S0®U1(S0)®S*1® U2(S*1)®S*2® U3(S*2)®…®S*m-1® Um(S*m-1)®S*m.
8. Если начальное состояние S0 не задано, а ограничено условием S0ÎS0, то найти оптимальное начальное состояние, при котором выйгрыш достигнет максимума и далее по цепочке, безусловные оптимальные управления.
В данной задаче вместо того, чтобы рассматривать допустимые варианты распределения капиталовложений между n предприятиями и оценивать их эффективность, необходимо исследовать эффективность вложения средств на одном предприятии, на двух предприятиях и т.д., наконец, на n предприятиях. Таким образом получим n этапов, на каждом из которых состояние системы (3 предприятия) описывается объемом средств, подлежащих освоению k предприятиями (k=1¸n). Управлениями будут являться решения об объемах капиталовложений, выделяемых k-тому предприятию.
Литература к задаче 2
1. Вентцель Е.С. Исследование операций: задачи, принципы, методология.– М.:Наука. Гл. ред. физ.-мат. лит.,1988.
2. Вентцель Е.С. Основы исследования операций.– М.: Советское радио, 1972.
3. Габасов Р.Ф., Кириллова Ф.М. Основы динамического программирования.– Минск:Изд-во БГУ,1975.
4. Исследование операций в экономике: Учеб. пособие для вузов по экон. специальностям / Под ред. Н.Ш.Кремера.– М.: Банки и биржи,1997.
5. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах.– М.: Высшая школа,1979.
Задача 3
Марковские случайные процессы
Исходные данные задачи.
 |
Размеченный граф состояний системы представлен на рис. 1.
Заданы следующие состояния системы.
1. S1 – исправна, функционирует (загружена).
2. S2 – исправна, не функционирует (не загружена).
3. S3 – неисправна, факт неисправности устанавливается.
4. S4 – факт неисправности установлен, ведется поиск неисправности.
5. S5 – ремонтируется.
6. S6 – ведется профилактический осмотр.
7. S7 – ведется профилактический ремонт.
Обозначение исходных данных для расчета интенсивностей потоков событий приведено в таблице 7.
Таблица 7
Обозначение исходных данных
| Наименование | Обозначение | Размерность |
| Среднее время наработки на отказ | T1 | сутки |
| Среднее время функционирования системы | T2 | часы |
| Среднее время простоя исправной системы | T3 | часы |
| Среднее время установление факта неисправности | T4 | часы |
| Среднее время поиска неисправности | T5 | часы |
| Среднее время устранения неисправности (ремонта) | T6 | часы |
| Периодичность профилактического осмотра | Один раз в T7 дней | сутки |
| Средняя продолжительность проф. осмотра | T8 | часы |
| Средняя продолжительность проф. ремонта | T9 | часы |
В задаче требуется определить следующее. Окупит ли себя увеличение дохода, связанное с уменьшением Ti в nj раз (n1=2; n2=3), если при этом возникают дополнительные затраты в размере 0,5n1Di, и 0,75n2Di, где Di – убыток, приносимый системой в соответствующем времени Ti состоянии.
Варианты исходных данных приведены в табл. 8.
Таблица 8
Варианты исходных данных
| № | Значения Ti | Доход Di в единицу времени в зависимости от состояния системы (руб.) | |||||||||||||||
| вар. | Т1 | Т2 | Т3 | Т4 | Т5 | Т6 | Т7 | Т8 | Т9 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | Тi |
| 1 | 20 | 6 | 0,3 | 0,4 | 0,9 | 1,3 | 22 | 0,6 | 6 | 207 | -23 | -5 | -4 | -23 | -8 | -9 | 3 |
| 2 | 23 | 4 | 0,4 | 0,2 | 0,6 | 1,7 | 38 | 0,9 | 6 | 229 | -24 | -6 | -3 | -15 | -11 | -11 | 7 |
| 3 | 24 | 8 | 0,3 | 0,4 | 0,9 | 1 | 22 | 0,9 | 7 | 207 | -21 | -5 | -2 | -23 | -7 | -9 | 7 |
| 4 | 20 | 4 | 0,3 | 0,3 | 0,6 | 1,3 | 35 | 1 | 7 | 247 | -20 | -4 | -7 | -22 | -7 | -8 | 3 |
| 5 | 20 | 4 | 0,1 | 0,6 | 0,9 | 2,1 | 32 | 0,6 | 6 | 208 | -20 | -6 | -6 | -17 | -11 | -8 | 3 |
| 6 | 21 | 4 | 0,4 | 0,5 | 0,7 | 1,2 | 44 | 0,8 | 6 | 297 | -22 | -2 | -6 | -10 | -7 | -9 | 3 |
| 7 | 20 | 4 | 0,3 | 0,5 | 0,6 | 2 | 23 | 0,5 | 5 | 228 | -19 | -3 | -4 | -21 | -7 | -8 | 7 |
| 8 | 18 | 4 | 0,4 | 0,2 | 0,6 | 0,9 | 24 | 0,9 | 6 | 214 | -24 | -2 | -7 | -25 | -9 | -9 | 7 |
| 9 | 19 | 5 | 0,1 | 0,3 | 0,7 | 1 | 42 | 0,9 | 5 | 280 | -21 | -6 | -7 | -15 | -9 | -9 | 7 |
| 10 | 21 | 8 | 0,1 | 0,6 | 0,5 | 1,5 | 40 | 1 | 7 | 226 | -20 | -6 | -3 | -18 | -9 | -11 | 3 |
| 11 | 18 | 8 | 0,2 | 0,6 | 1 | 0,8 | 48 | 0,8 | 6 | 214 | -20 | -6 | -7 | -16 | -8 | -8 | 7 |
| 12 | 21 | 4 | 0,2 | 0,6 | 1 | 0,9 | 32 | 0,8 | 5 | 277 | -23 | -5 | -4 | -13 | -7 | -10 | 3 |
| 13 | 21 | 4 | 0,4 | 0,5 | 0,6 | 2,2 | 46 | 0,7 | 6 | 295 | -23 | -4 | -2 | -11 | -10 | -10 | 7 |
| 14 | 18 | 4 | 0,1 | 0,3 | 0,8 | 0,8 | 20 | 0,6 | 5 | 264 | -22 | -6 | -4 | -24 | -8 | -8 | 7 |
Окончание табл. 8
| № | Значения Ti | Доход Di в единицу времени в зависимости от состояния системы (руб.) | |||||||||||||||
| вар. | Т1 | Т2 | Т3 | Т4 | Т5 | Т6 | Т7 | Т8 | Т9 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | Тi |
| 15 | 19 | 6 | 0,4 | 0,3 | 0,9 | 2,1 | 29 | 0,9 | 7 | 208 | -20 | -5 | -3 | -17 | -10 | -10 | 7 |
| 16 | 22 | 4 | 0,3 | 0,2 | 0,5 | 0,9 | 35 | 0,8 | 5 | 255 | -24 | -4 | -7 | -22 | -8 | -9 | 3 |
| 17 | 18 | 8 | 0,4 | 0,5 | 1 | 0,8 | 33 | 0,5 | 7 | 207 | -21 | -2 | -4 | -15 | -10 | -11 | 3 |
| 18 | 20 | 5 | 0,4 | 0,5 | 1 | 1,9 | 22 | 0,6 | 5 | 207 | -21 | -5 | -4 | -25 | -8 | -9 | 7 |
| 19 | 21 | 5 | 0,1 | 0,6 | 0,9 | 1,3 | 40 | 0,9 | 5 | 235 | -18 | -2 | -3 | -11 | -10 | -11 | 3 |
| 20 | 18 | 5 | 0,2 | 0,3 | 0,8 | 1,2 | 43 | 0,5 | 6 | 293 | -23 | -2 | -5 | -21 | -7 | -11 | 7 |
| 21 | 25 | 4 | 0,2 | 0,2 | 0,6 | 1,2 | 45 | 0,7 | 7 | 277 | -19 | -5 | -4 | -13 | -11 | -10 | 3 |
| 22 | 18 | 5 | 0,2 | 0,5 | 0,8 | 1 | 34 | 0,8 | 6 | 210 | -21 | -6 | -5 | -20 | -9 | -11 | 3 |
| 23 | 19 | 8 | 0,3 | 0,6 | 0,8 | 2 | 33 | 1 | 6 | 232 | -25 | -2 | -3 | -14 | -11 | -12 | 7 |
| 24 | 22 | 8 | 0,1 | 0,3 | 1 | 1,9 | 29 | 0,9 | 7 | 238 | -24 | -2 | -2 | -21 | -10 | -10 | 3 |
| 25 | 24 | 5 | 0,1 | 0,6 | 0,5 | 0,8 | 41 | 1 | 7 | 266 | -22 | -5 | -4 | -15 | -11 | -12 | 7 |
Методические указания к решению задачи 3
1. Расчитываются интенсивности потоков событий.
2. Составляются уравнения Колмогорова.
3. Находится решение уравнений Колмогорова (вручную и численно).
4. Вычисляются финальные вероятности состояний системы.
5. Используя значения финальных вероятностей состояний определяется доход, приносимый системой в единицу времени.
6. Определяется изменение дохода при уменьшении Ti. Для этого пересчитывается интенсивность соответствующенго потока событий, находится новое решение уравнений Колмогорова и новые финальные вероятности. После этого определяется новое значение дохода, определяется его разница с предыдущим и результат сопоставляется с произведенными дополнительными затратами.
Численное решение уравнений Колмогорова производится в среде MS EXCEL. Текст программы на языке VB для EXCEL приведен в приложении 2. Оформление рабочего листа – в приложении 3.
Литература к задаче 3
1. Вентцель Е.С. Исследование операций: задачи, принципы, методология.–М.:Наука. Гл. ред. физ.-мат. лит.,1988.
2. Вентцель Е.С. Основы исследования операций.– М.: Советское радио, 1972.
3. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения.– М.: Наука, 1991.
4. Ярлыков М.С., Миронов М.А. Марковская теория оценивания случайных процессов.-М.:Радио и связь, 1993.
Задача 4
Метод Монте-Карло
Рассчитать нетто-ставку тарифа при страховании строительства здания по исходным данным, приведенным в табл.9, табл.10. и на рис.2.
Таблица 9
Обозначения исходных данных
| Наименование | Обозначение |
| Заданная точность | e |
| Вероятность попадания при испытаниях в зону, ограниченную заданной точностью | Y |
| Показатель качества проектирования | mп |
| Закон распределения xп | fп |
| Показатель предполагаемого качества материалов | mм |
| Закон распределения xм | fм |
| Показатель предполагаемого качества выполнения СМР | mс |
| Закон распределения xс | fс |
| Число этажей объекта | m |
| Число несущих конструкций на этаже | n |
| Число несущих конструкций на нулевом цикле | v |
| Класс подверженности внешним факторам риска | K |
| Вероятность внешнего фактора 1 | P1 |
| Вероятность внешнего фактора 2 | P2 |
| Вероятность внешнего фактора 3 | P3 |
Таблица 10
Варианты исходных данных
| № | e | Y | mп | fп | mм | fм | mс | fс | m | n | v | K | P1 | P2 | P3 |
| 1 | 0,001 | 0,9999 | 0,85 | 2 | 0,89 | 3 | 0,80 | 2 | 6 | 6 | 6 | 4 | 6,2E-04 | 6,0E-05 | 1,3E-06 |
| 2 | 0,001 | 0,999 | 0,92 | 3 | - | 4 | - | 4 | 9 | 3 | 7 | 1 | 5,6E-04 | 2,8E-05 | 1,7E-06 |
| 3 | 0,001 | 0,99999 | 0,88 | 1 | 0,87 | 2 | 0,82 | 3 | 16 | 3 | 7 | 4 | 0 | 3,0E-05 | 6,9E-06 |
| 4 | 0,0015 | 0,99999 | - | 4 | 0,82 | 3 | 0,90 | 2 | 24 | 5 | 4 | 2 | 6,0E-04 | 3,2E-05 | 8,7E-06 |
| 5 | 0,0015 | 0,9999 | - | 4 | 0,81 | 3 | 0,90 | 3 | 48 | 5 | 4 | 5 | 7,6E-04 | 0 | 3,4E-06 |
| 6 | 0,0015 | 0,9998 | 0,90 | 1 | 0,90 | 2 | - | 4 | 9 | 5 | 8 | 3 | 7,9E-04 | 3,8E-05 | 6,9E-06 |
| 7 | 0,001 | 0,9999 | 0,83 | 3 | 0,82 | 2 | 0,68 | 2 | 6 | 2 | 5 | 4 | 6,0E-04 | 7,2E-05 | 5,6E-06 |
| 8 | 0,0018 | 0,9999 | 0,87 | 1 | 0,82 | 1 | 0,68 | 1 | 48 | 8 | 8 | 1 | 5,3E-04 | 2,1E-05 | 4,2E-06 |
| 9 | 0,0015 | 0,9998 | 0,85 | 3 | 0,83 | 2 | 0,75 | 1 | 22 | 8 | 4 | 2 | 8,2E-04 | 3,3E-05 | 5,8E-06 |
| 10 | 0,001 | 0,9998 | 0,86 | 2 | 0,86 | 3 | - | 4 | 9 | 3 | 8 | 3 | 0 | 6,0E-05 | 3,0E-06 |
| 11 | 0,0015 | 0,9999 | 0,78 | 3 | 0,88 | 3 | 0,89 | 1 | 10 | 3 | 5 | 2 | 7,3E-04 | 5,4E-05 | 3,5E-06 |
| 12 | 0,0015 | 0,9999 | 0,84 | 1 | - | 4 | 0,87 | 1 | 6 | 7 | 4 | 5 | 7,8E-04 | 3,3E-05 | 2,3E-06 |
Окончание табл. 10
| № | e | Y | mп | fп | mм | fм | mс | fс | m | n | v | K | P1 | P2 | P3 |
| 13 | 0,0015 | 0,9998 | 0,80 | 3 | 0,80 | 3 | - | 4 | 9 | 8 | 6 | 1 | 6,9E-04 | 3,4E-05 | 7,2E-06 |
| 14 | 0,001 | 0,9998 | - | 4 | 0,88 | 3 | 0,83 | 1 | 16 | 5 | 7 | 5 | 5,4E-04 | 5,5E-05 | 2,3E-06 |
| 15 | 0,0015 | 0,9998 | 0,73 | 2 | 0,81 | 1 | 0,82 | 3 | 24 | 2 | 5 | 5 | 7,0E-04 | 4,2E-05 | 4,5E-06 |
| 16 | 0,0012 | 0,9999 | 0,88 | 3 | 0,79 | 3 | - | 4 | 48 | 2 | 7 | 3 | 6,9E-04 | 0 | 8,3E-06 |
| 17 | 0,0015 | 0,9998 | 0,87 | 2 | - | 4 | 0,87 | 2 | 9 | 7 | 6 | 3 | 7,0E-04 | 7,2E-08 | 7,9E-06 |
| 18 | 0,001 | 0,9996 | 0,73 | 3 | 0,91 | 2 | 0,76 | 2 | 6 | 2 | 4 | 2 | 5,2E-04 | 7,4E-05 | 2,9E-06 |
| 19 | 0,0015 | 0,999 | 0,84 | 3 | 0,87 | 3 | 0,75 | 2 | 48 | 8 | 6 | 5 | 5,2E-04 | 7,2E-05 | 1,7E-06 |
| 20 | 0,0018 | 0,9997 | 0,73 | 2 | 0,92 | 1 | 0,79 | 2 | 22 | 3 | 7 | 5 | 7,8E-04 | 3,8E-05 | 6,6E-06 |
| 21 | 0,0015 | 0,9997 | - | 4 | 0,89 | 2 | 0,73 | 1 | 9 | 6 | 4 | 3 | 5,9E-04 | 3,4E-05 | 4,8E-06 |
| 22 | 0,001 | 0,999 | - | 4 | 0,92 | 1 | - | 4 | 10 | 6 | 8 | 4 | 8,1E-04 | 8,0E-05 | 4,2E-06 |
| 23 | 0,001 | 0,9998 | 0,82 | 3 | 0,87 | 1 | 0,72 | 1 | 24 | 2 | 7 | 1 | 7,2E-03 | 4,7E-03 | 5,5E-05 |
| 24 | 0,001 | 0,999 | 0,80 | 2 | 0,80 | 2 | - | 4 | 6 | 4 | 8 | 1 | 6,6E-04 | 5,5E-05 | 2,6E-06 |
| 25 | 0,001 | 0,999 | - | 4 | 0,88 | 2 | 0,84 | 2 | 9 | 8 | 8 | 2 | 5,1E-04 | 0 | 8,0E-06 |
 |
Дата: 2019-05-28, просмотров: 220.
