Практикум по предмету Математические методы и модели (стр. 4 из 7)
Методические указания к решению задачи 2
Принцип оптимальности. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выйгрыш на данном шаге плюс оптимальный выйгрыш на всех последующих шагах был максимальным.
Общая последовательность решения задач динамического программирования следующая.
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. Используя значения финальных вероятностей состояний определяется доход, приносимый системой в единицу времени.