Диссертация (786272), страница 17
Текст из файла (страница 17)
Бертсекаса и С. Шрива [4], для решения задачи, рассмотренной в разделе 3.4.1. Система (3.39) является марковской, так как она рекуррентна и её поведение вбудущем полностью определяется текущим состоянием.2. Величина +1 , определяемая формулой (3.34), является аддитивной, её можнопредставить в виде суммы в силу выражения (3.36). Величина Σ +1 , определяемая формулой (3.35), также является аддитивной, ее можно представить в виде суммы (3.37). В силу√строгого возрастания функции квадратного корня, величина Σ +1 — монотонна. Квантиль — детерминированная положительно определенная величина, > 0. Критерий оптимизации (3.42) представляет собой сумму аддитивной функции +1 и строго возрастающей√функции Σ +1 с положительным коэффициентом , поэтому является монотонным.3.
Величина +1 ограничена снизу +1 > 0, так как стоимость работ на каждомучастке, определяемая величиной (3.40), не может быть отрицательной или равняться нулю,а дисперсия Σ +1 представляет собой сумму неотрицательных величин, определенных ввыражении (3.41), поэтому Σ +1 ≥ 0.Поскольку перечисленные условия выполнены, то для решения задачи (3.42) можновоспользоваться методом динамического программирования.Введем функцию будущих потерьΔ ( ) =min{ (·)}= , { (·)}= ∈ ( +1 + √︀Σ +1 ),гдеΔ = {{ (·)}= : ( ) ∈ , = , }.В соответствии с методом динамического программирования получаем следующиерекуррентные соотношения ( ) =min +1 ( +1 ( , , )), = , − 1, . . . , 1, , ∈ +1 ( ) = +1 + √︀Σ +1 ,где зависимость +1 ( , , ) определяется системой (3.39).(3.43)(3.44)91Разрешая рекуррентные соотношения (3.43) — (3.44) динамического программирования так же, как и в детерминированном случае, получаем на каждом шаге зависимостьоптимального управления ¯* (¯ ), ¯* (¯ ) от текущего состояния ¯ , = 1, .
Подставляя найденные зависимости в систему (3.39), находим вектор оптимального состояния ¯* для каждого шага = 1, . После чего получаем оптимальные управления в классе программныхстратегий¯* = ¯* (¯* ), ¯* = ¯* (¯* ), = 1, .При этом +1 (¯* (·), ¯* (·)) = ¯ +1 ( , ) = 1 (¯1 ),гдеΔΔ*).1* , . . . , ¯ = col(¯*1 , . . . , ¯* ), = col(¯Для решения задачи (3.43) может быть применен алгоритм с использованием методасценариев, а также метода ветвей и границ, описанный в разделе 3.3, с учётом некоторыхзамечаний, которые приведены в следующем разделе.923.5.2.Алгоритм решения задачи в стохастическойприменением метода ветвей и границпостановкесЗадача выбора оптимальной трассы в детерминированной постановке, рассмотреннаяв разделе 3.2, была сведена к решению трёх подзадач меньшей размерности, в результатерешения каждой из которых были найдены оптимально проложенные части трассы.
Критерием оптимизации указанной задачи было выбрано математическое ожидание (средниезатраты), что позволило просуммировать оптимальные решения, найденные в каждой изподзадач, и получить оптимальное решение исходной задачи.Как уже отмечалось выше, квантильный критерий не обладает свойством аддитивности, поэтому сумма оптимальных решений, найденных в каждой из трёх подзадач, неявляется оптимальным решением задачи (3.43). Будем рассматривать редуцированный алгоритм раздела 3.3, состоящий из первых двух подзадач, исключив из рассмотрения третьюподзадачу.Суммарная стоимость работ по прокладке трассы от начальной точки 1,1 до конечной +1, +1 определяется выражением[ +1 ] = (1,1 , , ) + ( , , +1, +1 )+√︁+ Σ(1,1 , , ) + Σ( , , +1, +1 ),(3.45)где величины ( , , +1, +1 ) и Σ( , , +1, +1 ) являются решением первой подзадачи, а (1,1 , , ), Σ(1,1 , , ) — решением второй подзадачи.Рассмотрим выражение (3.45).1.
Величины (1,1 , , ) и ( , , +1, +1 ) положительны и аддитивны в силуопределения системы (3.39).2. Величины Σ(1,1 , , ) и Σ( , , +1, +1 ) также аддитивны и положительны. В силу строгого возрастания функции квадратного корня, величина√︀Σ(1,1 , , ) + Σ( , , +1, +1 ) монотонна. Квантиль — положительно определенная величина.Выражение (3.45) представляет собой сумму аддитивных функций (1,1 , , ),√︀( , , +1, +1 ) и строго возрастающей функции Σ(1,1 , , ) + Σ( , , +1, +1 )с положительным коэффициентом, поэтому является монотонным.Тогда значение стоимости прокладки [ +1 ] будет минимально возможным, если входе решения первой подзадачи будут найдены оптимальные ( , , +1, +1 ) иΣ( , , +1, +1 ), а в ходе решения второй подзадачи будут найдены оценки снизу длявеличин (1,1 , , ) и Σ(1,1 , , ).93Найдем нижнюю оценку величины суммарной стоимости прокладки трассы, определяемой соотношением (3.45).
Для этого рассмотрим решение подзадач алгоритма применительно для данного случая.1. В ходе решения первой подзадачи получаем значения стоимости ( , , +1, +1 )прокладки трассы от каждой точки , до +1, +1 , = 0, и оптимальное управление. Причем стоимость прокладки определяется как( , , +1, +1 ) = ( , , +1, +1 ) + √︁Σ( , , +1, +1 ).2. Для нахождения оптимальной трассы необходимо соединить начальную точку 1,1c каждой точкой , , = 0, , после чего определить суммарную стоимость затратпо прокладке всей трассы и выбрать трассу с наименьшей стоимостью.
Будем использоватьминимально возможное значение средних затрат на прокладку трассы по каждому направлению в пределах сетки разбиения между начальной и конечной точками текущего участкатрассы:Δ(1,1 , , ) = min ,(3.46)=1, ,=1,Δ(1,1 , , ) = min ,(3.47)=1, ,=1,Δ(1,1 , , ) = min ,(3.48)=1, ,=1,а также минимально возможные значения дисперсии для каждого из направлений движенияпо сетке разбиения:Δ (1,1 , , ) = min ,(3.49)=1, ,=1,Δ (1,1 , , ) = min ,(3.50)=1, ,=1,Δ. (1,1 , , ) = min (3.51)=1, ,=1,Поскольку значения (3.46) — (3.51) являются минимально возможными, то найдя нижнююоценку данной подзадачи, удастся оценить снизу и выражение (3.45). Нахождение оценкиснизу стоимости прокладки трассы второй подзадачи сводится к решению двух задач:1) необходимо найти оценку снизу для величины (1,1 , , );2) необходимо найти оценку снизу для величины Σ(1,1 , , ).Рассмотрим решение первой задачи.94Для оценивания снизу величины (1,1 , , ) необходимо решить вторую подзадачуалгоритма, описанного в разделе 3.3, где в качестве (3.14) — (3.16) будем рассматривать(3.46) — (3.48).
Находя оценку снизу стоимости прокладки трассы для трёх возможныхсхем движения, найдем оценку снизу и для (1,1 , , ).Рассмотрим решение второй задачи.Для нахождения оценки снизу величины Σ(1,1 , , ) также решаем вторую подзадачу алгоритма, описанного в разделе 3.3, принимая в качестве (3.14) — (3.16) значения(3.49) — (3.51). Находя оценку снизу стоимости прокладки трассы от 1,1 до , для трёхвозможных схем движения, найдем оценку снизу и для величины Σ(1,1 , , ).Для решения задачи (3.45) может быть применена схема отсечения точек, описанная вразделе 3.3, и схема сравнения с трассой эксперта для исключения из рассмотрения заведомонеоптимальных вариантов решения.Таким образом, для решения задачи (3.45) применим алгоритм основанный на методе динамического программирования, схеме сценариев, а также методе ветвей и границ,описанный в разделе 3.3.2, с учётом приведённых замечаний.953.6.Результаты численных расчётов на примере выбора оптимальнойтрассы до аэропортаФактическая транспортная блокада осложняет работу мест базирования аэропортов.Дороги в аэропорты, построенные более чем полвека назад, сегодня уже не соответствуюткак заявленному классу, так и своему прямому назначению.За полвека к трассам до аэропортов сделали примыкания, добавили наземные пешеходные переходы и ввели ограничения скорости.
Одной аварии вполне достаточно, чтобывозникла пробка длиной в несколько километров. Ситуация может усугубляться в случае,когда на дорогах ведутся плановые ремонтные работы.Как уже отмечалось выше, решить проблему пробок можно путём прокладки новыхтрасс до аэропортов, причем проектирование трасс должно быть основано на транспортногеографическом исследовании.
Следует изучить как добираются люди до аэропорта, какиестроения встречаются на пути предполагаемых трасс, необходимо также исследовать рельефместности для предполагаемой прокладки трасс.Алгоритм решения задачи выбора оптимальной трассы в стохастической постановке,предложенный в разделе 3.5.2, основан на алгоритме решения задачи в детерминированнойпостановке с применением метода ветвей и границ, рассмотренном в разделе 3.3.2. Поэтомудля проверки работоспособности и оценки оперативности алгоритма выбора оптимальнойтрассы рассмотрим детерминированную постановку задачи.Численные расчёты предложенных в данной главе алгоритмов рассматриваются напримере выбора оптимальной трассы до четвёртого аэропорта Москвы — аэропорта Быково.На автомобиле можно добраться от МКАДа до Быково по Рязанскому шоссе, котороене отличается ни качественным покрытием, ни скоростными преимуществами.
Пробка, какправило, начинается сразу на выезде из Москвы.Будем рассматривать задачу о прокладке автомобильной трассы минимальной стоимости от пересечения МКАД и Каширского шоссе до аэропорта Быково.На рисунке 3.1 представлена карта местности от МКАДа до аэропорта Быково.Рис. 3.1 Карта района прокладки трассы96Наложим на карту местности сетку разбиения на прямоугольники. Применительно квведённым в разделе 3.1 обозначениям, будем считать начальной точкой — место пересечения Каширского шоссе и МКАДа, а конечной точкой — въезд на территорию аэропортаБыково.Длина сетки разбиения по горизонтали составляет 21 км, а по вертикали 3,5 км. Дляудобства вычислений и более детального учёта особенностей рельефа местности разобьемсетку на квадраты с длиной стороны 0,5 км.
Тогда получим разбиение сетки на = 42, = 7 равных частей по горизонтали и по вертикали соответственно (рис. 3.2).Рис. 3.2 Карта местности с наложенной сеткой разбиенияТрудоёмкость прокладки трассы на каждом участке сетки разбиения зависит от рельефа местности. Можно выделить следующие характерные особенности местности:1) поле;2) лес;3) река;4) озеро;5) шоссе;6) поселок, деревня, город;7) железная дорога.Согласно справочной энциклопедии дорожника А.П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
