Вычислительных систем
 Скачать 0.78 Mb.
|
|
3.3. Стохастически оптимальное функционирование ВС 37 Математическое ожидание прибыли при эксплуатации ВС равно ?????? ∑︁ ??????=1 (?????? ?????? − ?????? ?????? )?????? ?????? − ?????? ∑︁ ??????=1 ?????? ?????? (?????? ?????? − ?????? ?????? ) − ?????? ∑︁ ??????=1 ?????? ?????? ∞ ∫︁ ?????? ?????? (?????? ?????? − ?????? ?????? )?????? ?????? (?????? ?????? )???????????? ?????? , или ?????? ∑︁ ??????=1 (?????? ?????? ?????? ?????? − ?????? ?????? ?????? ?????? − ?????? ?????? ∞ ∫︁ ?????? ?????? (?????? ?????? − ?????? ?????? )?????? ?????? (?????? ?????? )???????????? ?????? ). Итак, требуется найти разбиение (?????? 1 , ?????? 2 , . . . , ?????? ?????? ) системы на подсисте- мы, доставляющее минимум целевой функции ?????? ?????? (?????? 1 , ?????? 2 , . . . , ?????? ?????? ) = ?????? ∑︁ ??????=1 (?????? ?????? ?????? ?????? − ?????? ?????? ∞ ∫︁ ?????? ?????? (?????? ?????? − ?????? ?????? )?????? ?????? (?????? ?????? )???????????? ?????? ) → min (?????? ?????? ) (3.5) при ограничениях: ?????? ∑︁ ??????=1 ???????????? ?????? ≤ ??????, (3.6) ?????? ?????? ≥ 0, ?????? = 1, 2, . . . , ??????. (3.7) Сформулированная задача может быть решения методом динамического программирования [3, С. 207]. 3.3.2. Метод динамического программирования Ниже приведена оптимизационная задача (3.8)–(3.10) с аддитивной целевой функцией ??????(?????? 1 , ?????? 2 , . . . , ?????? ?????? ) . В [3, 4] показано, что такая задача может быть точно решена методом динамического программирования. ?????? (?????? 1 , ?????? 2 , . . . , ?????? ?????? ) = ?????? ∑︁ ??????=1 ?????? ?????? (?????? ?????? ) → min (?????? ?????? ) (3.8) при ограничениях: ?????? ∑︁ ??????=1 ?????? ?????? ?????? ?????? ≤ ??????, (3.9) ?????? ?????? ≥ 0, ?????? = 1, 2, . . . , ??????. (3.10) Нетрудно заметить, что задача (3.5)–(3.7) может быть приведена к 38 Глава 3. Организация функционирования ВС виду задачи (3.8)–(3.10). Для этого достаточно положить ?????? ?????? (?????? ?????? ) = ?????? ?????? ?????? ?????? − ?????? ?????? ∞ ∫︁ ?????? ?????? (?????? ?????? − ?????? ?????? )?????? ?????? (?????? ?????? )???????????? ?????? , ?????? ?????? = ??????, ?????? = 1, 2, . . . , ??????, ?????? = ??????. Рассмотрим основные шаги метода динамического программирования для решения задачи (3.8)–(3.10) [3, С. 207]. Можно показать, что для последовательности функций Λ ?????? (??????) = min ?????? 1 ,...,?????? ?????? ?????? ∑︁ ??????=1 ?????? ?????? (?????? ?????? ), ?????? = 1, 2, . . . , ??????, ?????? = 0, 1, . . . , ??????, в которых минимум берется по неотрицательным целым числам, удовле- творяющим условию ?????? ∑︁ ??????=1 ?????? ?????? ?????? ?????? ≤ ??????, справедливы рекуррентные соотношения: Λ ?????? (??????) = min ?????? ?????? (?????? ?????? (?????? ?????? ) + Λ ??????−1 (?????? − ?????? ?????? ?????? ?????? )), (3.11) где ?????? ?????? может принимать значения 0, 1, . . . , [??????/?????? ?????? ] . Запись [??????] – это целая часть числа ?????? (см. приложение). На прямом проходе отыскивается оптимальное значение ?????? * целевой функции ?????? * = ?????? (?????? * 1 , ?????? * 2 , . . . , ?????? * ?????? ) Вычислительная процедура для отыскания ?????? * состоит в непосредствен- ном определении Λ 1 (??????) , затем в вычислении Λ ?????? (??????) , ?????? = 2, 3, . . . , ?????? − 1, и ?????? * = Λ ?????? (??????) . Результаты заносятся в таблицу 3.1. Сперва находятся Λ 1 (??????) и ̂︀ ?????? 1 (??????) для всех ?????? = 0, 1, . . . , ??????. Λ 1 (??????) = min ?????? 1 ?????? 1 (?????? 1 ), ?????? 1 = 0, 1, . . . , [??????/?????? 1 ]. Величина ̂︀ ?????? 1 (??????) – значение ?????? 1 ∈ {0, 1, . . . , [??????/?????? 1 ]} , при котором Λ 1 (??????) прини- мает минимальное значение. ̂︀ ?????? 1 (??????) = argmin ?????? 1 ?????? 1 (?????? 1 ), ?????? 1 = 0, 1, . . . , [??????/?????? 1 ]. |