Курс лекци Русакова по методам оптимизации (1083216), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Возможно, чтоp=i или q=j. Положим a qp := ∞ .Эта мера предохраняет от выбора ребра (q , p) в качествепоследующего, а тем самым предохраняет от формирования замкнутогоцикла длины < n.В общем случае, среди всех полученных множеств вариантов выбираемто, для которого оценка минимальна.Пример:119A/ :A:134min по строкам :12∞50 24 1212102 10∞18 453 504∞244445 50∞11⇒12341∞38 12020∞835 ⇒3 460∞20444 49∞027min по столбцам 0 0 8 0 8⇒ A // : 27+8=351 2 31 ∞ 38 42 0040244∞ 0 35583 46 0 ∞ 20414 0 44 41 ∞- определяем "веса" нулей (минимум по строке + минимум по столбцу)- выбираем ноль с максимальным "весом",- выбираем соответствующий путь и вычеркиваем столбец и строку.Выбираем путь 3→2.A1 :11 ∞2 04 034∞41нормализ.

A1 по 41204035 , 2→3 - запрещен (т.к. выбран 3→2)∞⇓A1 :1341∞4370352035∞35403741∞оценка 35 + 4 =39Выбираем путь 1→3; пути 3→1 нет ⇒A2 : 3 →/ 2 - запрещенный путь ( выб. в A1)1234∞38402 03 46∞∞0∞352020444 411038⇒∞12341∞04020∞0353 26 ∞∞0441 ∞06оценка 35 + 38 + 20 =93A12 : 1 →/ 31341 ∞∞020∞354037∞371⇒341 ∞ ∞020∞ 35400∞оценка 39 + 37 =76⇒ 1→3→2 ; запрещенный путь: 2 →/ 1A11 :12114⇒2 ∞ 353540∞142 ∞04∞0оценка 39 + 35 =74Путь 1→3→2 был . По A11 : 2→4→1244451Оптимальный путь: 1 → 3 → 2 → 4 → 1Вес: 74 = 24 + 4 + 45 + 1(см. A)строилось дерево:353974A93A1A1176A2A12(выбир. 39)(выбир.

74)Упражнение: Написать программу решения задачи о ранце с помощью метода ветвей и границ.4.03 Динамическое программирование.Модельная задача: поиск кратчайшего пути на графе.122N134212235iНN0413212N21430iК11N3N 1 (далее)Рис.1На дугах проставлены расстояния между двумя вершинами. Ввершинах - кратчайшее расстояние до конечной вершины i K .Кратчайший путь i H → i K имеет длину 5.Этот граф без циклов.Таким образом, можно разметить любой граф без циклов.Двигаемся от конечной вершины к начальной:любая вершина - состояние процесса,дуги - переходы.Таким образом, задача: на множестве всех траекторий выбрать ту,длина которой минимальна.Абстрактная схема.Пусть Μ- конечное множества состояний и конечное множествоуправлений U. На некотором подмножестве Γ ⊂ Μ × U задана функцияперехода ϕ i : Γ → Μ.

Пусть есть последовательность состояний { i0 , i1 ,..., ik } ипоследовательность управлений { u0 , u1 ,..., u k −1 }, для которых ϕ ( i j , u j ) = i j +1 .Определение: Совокупность состояний и управлений называетсятраекторией процесса.i0 - нач.  ∈ Μ ( множество состояний )ik - конеч.123Введем множество траекторий Т, соединяющих начальные и конечныевершины.Пусть на Т задан функционал:J (t ) = ∑ f j (i j , u j )(*)вес дугиjТребуется найти траекторию с минимальным значением функционала:min J (t) −?TЗаметим, что (*) можно представить в виде:k −1J ( i0 ,..., ik ) = ∑ f j (i j , i j +1 )j =0Функционал такого вида называется аддитивным.

Следуетподчеркнуть, что динамическое программирование применимо, еслифункционал аддитивный.Методдинамическогопрограммированияпозволяетсвестиминимизацию функции n переменных к n одномерным минимизациям.4.04 Вывод уравнения Беллмана.Пусть Ti - множество траекторий , ведущих из i-й вершины в конечную.ОбозначимU i -множествоуправлений, допустимых для даннойвершины.(∀u∈ U i , ∃ ϕ (i, u ) )123∗вершина ,в которой осуществляется переходТогдаTi = UU {(i, u), t }/(2)u∈U i t /∈Tϕ (i ,u )t i - хвост траектории.Введем функцию:Z( i ) = minJ (t)t∈Ti124(3)Используя (2) получим соотношение для функции (3):Z( i ) = min min J (( i ,u), t / ) =u∈U i t / ∈Tϕ (i,u)Представим функционал через (*):= min min ∑ f j (i j , u j ) =u∈U i t / ∈Tϕ (i,u)jВыделим первую компоненту этой суммы:f 0 (i, u ) + ∑ f j (i j , u j )j ≥1f 0 (i, u ) не зависит от (i,uj) при j≥1 («хвоста траектории»).Поэтому := min ( f 0 (i, u ) + minu∈U it / ∈Tϕ (i,u)∑fjj(i j , u j ) ) =*= min ( f 0 (i, u ) + Z(ϕ ( i ,u)))u∈U iСуществуют марковские процессы или процессы без предыстории (так называются процессы, развитие которых при t > t 0 не зависит отхарактера их протекания при t< t 0 ).Например, процесс задачи коммивояжера не марковский (очевидно).Для процессов марковского типа Беллман сформулировал такназываемый принцип оптимальности:Конечный участок оптимальной траектории (хвост) являетсяоптимальной траекторией.Учитывая принцип оптимальности , можем написать:Z j (i) = min ( f j (i, u ) + Z j +1 (ϕ (i, u )) ) - уравнение Беллманаu∈U iZ j (i) -функция БеллманаZ k (ik ) = 0 (н.у.

для рекурсии)ik -конечная вершина.4.05 Методика применения функции Беллмана длярешения задачи125Рассмотрим множество вершин N1 , из которых можно попасть только вконечную (см. рис.1),Z k (ik ) = 0 ( ik -конечная вершина).С помощью уравнения Беллмана можно рассчитать Z (i) в любой точкемножества N1 .Для каждой из этих вершин можно зафиксировать управление u , накоторомдостигается min уравнения Беллмана.Рассмотрим множество вершин, N 2 , из которых можно попастьтолько в N1 .С помощью уравнения Беллмана можно вычислить Z (i) влюбой точке N 2 и зафиксировать u, на котором достигается min уравненияБеллмана.Описанные действия повторяют, пока не вычислят Z (i) вначальной вершине.

Это и будет значение функционала.Описанный процесс часто называют обратным ходом, закоторым следует прямой, в течение которого определяют оптимальнуютраекторию, которая определяется через выбранные при обратном ходеуправления для каждой вершины.4.06 Примеры задач динамического программирования1. Задача о рюкзаке.Задано конечное множество предметов, которые имеют вес истоимостьi -й предмет : вес - aiстоимость - ciНадо выбрать такую совокупность предметов, чтобы суммарный весбыл не более наперед заданного значения, а стоимость максимальна.nmax∑cixi при ∑ ai ≤i =1возможный вес)126y,гдеy - грузоподъемность (максимальноЧтобырешитьэтузадачуспомощьюдинамическогопрограммирования, надо представить ее решение в виде процесса:Z (y) = max ( ci + Z(y − ai ))i∈I zгде I z = { i : ai ≤ y} -уравнение Беллмана для задачи о рюкзаке.Зная значения Z для малых аргументов, можно вычислить его длялюбого аргумента.Процесс построения функции Беллмана не формализуется.

Этотворческий процесс, т.е. динамическое программирование, это идея, котораяв каждой предметной области реализуется по-своему.2. Задача оптимального распределения ресурсов.Существуетn предприятий, между ними надо распределитьζ 0 средств. Известно, что выдача i -му предприятию xi средств дает доходf i ( xi ).Требуется распределить средства так, чтобы суммарный доходбыл максимальным:nS = ∑ f i ( x i ) → maxi =1xi ≥ 0, i = 1, n ,n∑ xi =ζ 0i =1Эту задачу удобно решать методом динамического программирования.Пусть все xi кратны ∆ ( ∆ -некоторая константа), например:x1x2x340 80 120 ...( ∆ = 40)Представим процесс решения задачи как n -шаговый.На первом шаге выдадим средства первому предприятию1) x1 : ζ 1 = ζ 0 − x1 - оставшиеся средства (первому предприятию выдано x1средств)2) x 2 : ζ 2 = ζ 1 − x 2::n) x n : ζ n = 0 (все средства распределены)127Введем функцию БеллманаZ k (ζ k ) - максимальный доход, которыйможет быть получен при распределении средств ζ k между предприятиямиk+1, ...

, n.Z k (ζ k ) = max { f k +1 ( x k +1 ) + Z k +1 ( ζ k - x k +1 )}0 ≤ xk +1 ≤ ζ kЗамечание:Если разбиение задачи размера n сводит ее к n задачам размера n−1 ,то рекурсивный алгоритм имеет экспоненциальную сложность. В этомслучае часто можно получить более эффективный алгоритм с помощьютабличной техники, называемой динамическим программированием.Динамическое программирование, в сущности, вычислительноерешение для всех подзадач. Вычисление идет от малых подзадач к большим,и ответы записываются в таблице. Преимущество этого метода состоит в том,что раз уж подзадача решена, ее ответ где-то хранится и никогда невычисляется заново.Задачидинамическогопрограммированияназываютсямногоэтапными или многошаговыми.Недостатки динамического программирования.1.

В отличие от линейного программирования, в котором симплексметод является универсальным, в динамическом программировании такогометода не существует. Каждая задача имеет свои трудности, и в каждомслучае необходимо найти наиболее подходящую методику решения.2. Трудоемкость решения многомерных задач. При очень большомчисле переменных решение задачи ограничивается памятью ибыстродействием ЭВМ.Глава 5 Вариационное исчисление (ВИ)5.01 Основные определения128Вариационное исчисление занимается оптимизацией функционалов,аргументами которых являются функции:bJ (y(x)) =∫ f ( x, y( x), y/( x ))dxaБудемискатьнеобходимыеусловияэкстремумафункционала.Рассмотрим функции с фиксированными концами.

Норма:y (x ) = max { y (x ) + y / ( x) }a < x< bПусть y*(x) доставляет минимум функционалу J (y(x))Рассмотрим вариацию :(y(x)) = y * (x) + ε(x) , где ε(a) = ε(b) = 0ε(x) - вариацияε - гладкая, то есть непрерывная вместе со своей производной.Иллюстрация:y 1 (x )- д р .ф -ц и яy * (x )ε(x)0y (x ) = y * (x ) + ε (x )xε(x)Пусть yα = y * + α ⋅ ε , тогда:b/J ( yα ( x )) = ∫ f ( x, y * + α ⋅ ε , y * + α ⋅ ε / ) ⋅ dx ≥ J ( y * ( x ))(т.к.этоminaфункционала)Изэтогоэкстремума.129неравенстваможнополучитьнеобходимыеусловия5.02 Уравнение Эйлера-ЛагранжаЛемма Дюбуа-Раймона:Пусть для некоторой функции f, непрерывной на [a, b] , и для всехфункций h , непрерывных на [a, b]вместе со своей производной и таких,что h(a) = h(b) = 0bсправедливо:∫a f ( x)h( x)dx = 0 ,тогдаf ≡ 0 (б/д)Разложим J( yα (x)) в ряд Тейлора в окрестности точки α = 0:J( yα (x)) = J( y * ) + α ⋅SJ = α ⋅∂J+ o(α)∂α∂J- первая вариация функционала.∂αПри фиксированных y * (x) и ε(x) функционал зависит от параметра αи необходимым условием экстремума функционала является:∂J∂α=0 ⇒α =0SJ = 0Получим необходимое условие экстремума функционала в болееконструктивной форме: функционал J, рассматриваемый как функция от α ,может быть записан в виде:bJ (α ) = ∫ f ( x, y ( x ) + α ⋅ ε ( x ), y | ( x ) + α ⋅ ε / ( x )) ⋅ dxaТогда необходимое условие экстремума:b ∂f ( x, y, y / )∂f ( x, y , y / ) / ∂J (α )=∫⋅ ε ( x) +⋅ ε ( x ) ⋅ dx = 0/∂α∂y∂yabb∂fd ∂f∂fb/∫a ∂y / ⋅ ε ( x) ⋅ dx = (по частям) = ∂y / ⋅ ε ( x) a − ∫a ε ( x) dx ⋅ ∂y / dx\ ___ = 0 ___/т.к.

Характеристики

Список файлов лекций