Онятие о Динам.прогр-ии (ДП).Особенности задач ДП.

ДП-метод нахождения оптимального реш-я в задачах с многошаг-й струк-рой.

Ососбенности зад-ч ДП:

1.Рассматривается сис-ма, состояние которой на каждом шаге определяется вектором состояния x_t .Дальнейшие изменения её состояния зависят только от данного состояния x_tи не зависят от того, каким путём сис-ма принесла в него.Такие процессы называются процессами без последствий .

2.На каждом шаге выбирается одно решение(управление) U_t,под действием которого сис-ма переходит из предыдущего состояния x_t-1 в состояниеx_t.Это новое состояние является функцией состояния на начало шага и принятого в начале шага решения x_t= x_t(x_t-1, U_t) .

3.Действие на каждом шаге связаны с опред-м выигрышем или потерей,котор.зависят от состояния на начало шага и принятого реш-я.

4.На векторы состояния и управ-я могут быть наложены ограничения,объединение которых образует область допустимых решений Ω.

5.Требуется найти такое допустимое управление U_tдля каждого шага t,чтобы получить экстремальное значение ЦФ за все T-шагов.

Любую допустимую последовательность действий для каждого шага,переводящее сис-му из начальн.шага в конечн.называют стратегией управления(СУ).Допустимую СУ,которая доставляет ЦФ экстремальное значение назыв-ся оптимальной.

онятие о ДП.Геометрич-я интерпретация задач ДП.

ДП(динамическое планирование)-метод нахожд-я реш-я в з-чах с многошаговой стр-рой.

Геом-я интерпретация задач. Пусть N-размерность простр-ва состояния.В любой момент времени корд-ты сис-мы имеет вполне опред-ное знач-е,кот. с изм-нием времени мож. изм-ся.Переход сис-мы из одного сост-ния в др наз-ся траекторией его движения в простр-ве сост-ний.Прост-во,в кот. корд-ми служат сост-ние сис-мы наз-ся фазовым. Рассм-м двумерное простр-во сост-ний(рис):обл. доп-мых реш-й изобр-на фигурой Ω, х₀-начальное сост-ние сис-мы, х_Т-конечное.

Для многих эк-ких задач неизв-ны началь-е или конеч-е сост-ние,а изв-ны обл-ти,кот-м принадл-ат данные сост-ния.Задача ДП сост-т в том,чтобы найти фазовую траекторию, кот. нач-ся в обл-ти х₀ и заканч-ся в обл. х_Т,для кот. знач-е ЦФ достигало бы экстр-го знач-я.Если известны нач-ное и конеч-е сост-ния, то такие задачи наз-ся з-чами с закрепл-ми концами.А если изв-ны нач-ные и конеч-е обл-ти,то такие задачи наз-ся з-чами со свободными концами.

ринципы ДП(пр-пы ДП).

Суть метода ДП-идея постепенной,пошаговой оптимизации.Если трудно решить слож-ю задачу,то её след-т разбить на ряд более простых.Каждая новая задача оптим-ся не отдельно от осталь-х,а упр-ние на каждом шаге выбир-ся с учетом всех его последствий.Исключ-е-послед-й шаг,кот. мож. план-ся без учета посдед-вий.Особ-сть ДП:всю ДП целесообр-но разворач-ть от конца к началу.В перв. очередь план-ся N-й шаг,за ним (N-1).Для (N-1)-шага возмож-ми исходами будут явл-ся х_N-1.Набор опти-х упр-ний,зависящих от возм-ных исходов предыд-го этапа наз-ся условным оптим-ым реш-ем U^*_N (х_N-1).Для предпос-го этапа:требуем,чтобы ЦФ достигала экстр-го знач-я на 2-х послед-х этапах вместе,что позволит найти условно оптим-ное реш-е на предпосл-ем U^*_N-1 (х_N-1)…и для первого этапа U^*₁ (х₀).Т.к. х₀ задано однозначно,то найдем оптим-ое упр-ние для 1-го шага и экстр-ное знач-е ЦФ относит-но всего процесса,аналогично для 2-го шага U^*₂ (х^*₁) и т.д.Таким обр. задачи ДП реш-ся дважды:

1)от конца к началу(в рез-те нах-ся оптим-ое упр-ние и условно оптим-ое знач-е ЦФ для каждого шага,оптим-ое реш-е для 1-го шага и оптим-ое знач-е ЦФдля всего процесса);

2)от начала к концу(нах-ся оптим-ое упр-ние на каждом шаге с точки зрения всего процесса).

2 основных принципа ДП:

1)пр-п оптимальности: оптим-ое упр-ние на каждом шаге опред-ся сост-ем сис-мы на начало шага и целеупр-нием.Этот пр-п выраж-ся в состоянии рекуррентных соотнош-й Беллмага.

2) пр-п погружения: на каждом шаге реш-ся задачи наимень-го размера,но с такой же целью как и общая задача.

43).Функц-е ур-ния БЕЛЛМАНА.Будем сч-ть,ч.нач-е Х₀и кон-еХ_тсостояния сист.заданы.Об-чим ч/зf₁(x_0,u₁)-зн-ние ф-ции цели на1-м этапе,при нач-м сост-и сист.x₀ и при упр-нии u_1,ч/з f₂(x_1,u₂)-зн-ние ф-ции цели на2-м этапе ит.д….и f_n(x_n-1,u_n) зн-ние ф-ции цели на n-м этапе,тогда F=f(x_0,u)= (1).Треб-ся найти оптим.ур-ниеU*=U₁*,U₂*,…,U_n*)такое,ч.достав-етЦФ1экср-е зн-е,при огр-яхU€Ω,гдеΩ-обл.опр-я исх.з-чи.Введем обоз-нияΩ_N,Ω_N-1,N,Ω_N-2,N,… Ω_1,N,=Ω-обл-ти опр-ния дан.з-ч на посл-м этапе,2-х посл-х этапах ит.д. F₁(x_N-1), F₂(x_N-2),… F_N(x₀)-зн-яЦФна посл-м этапе,2-х посл.ит.д.

Пусть сост-е x_N-1з-ны,тогда F₁(x_N-1)=max(min)_поUn€Ωf_N(X_N-1,U_N) (2); F₂(x_N-2)=max(min)_{поUn€ΩN-1,N}(f_N-2(X_N-2,U_N-1)+ F₁(x_N-1)) (3); F_N(x₀)=max(min)_{поU1€Ω1,N}(f₁(x_0,u₁)+ F_N-1(x₁)) (4).Ф-лы2-4наз-ся функц-м ур-нием Бел-на.для того,ч.найти оптим ур-ние наNшагах,нужно знать усл.-оптим.ур-ния на предшес-х N-1шаге.

44)З-ча оптим-го маршрута.Треб-ся найти мар-т,связ-й городаАиВ,для кот.сум-е з-ты на перев-ку груза были бы наим-ми.Разобьем все мн-во гор-в на подмн-ва.В1-е п/мн-во вкл.в-ну1(А),во2-е вкл.в-ны,в кот.вх-т дуги из1-го п/мн-ва ит.д.Перенум-м этапы от конечной в-ны n нач-ой и введемобозн-я:n-номер шага,с_ij-ст-ть перев-ки груза из г-даiв г-дj,f_n(i)-ст-ть перев-ки груза(minз-ты) на перев-ку груза г-да i до кон-го г-да,если до кон0го г-да ост-сь n шагов,j_n(i)-№г-да,ч/з кот.надо ехать из г-да i,ч.достичь f_n(i).n=0cлед,ч.мы нах-ся в кон-м г.(В),зн-т f_n(i)= f₀(В)=0;n=1след-но пред-м,ч.мы нахся или в г.i₁или в г.i_2..Для этих г-дов з-ты на пер-ку сот-ят f₁(i₁)=c_i1,B+f₀B, f₁(i₂)=c_i2,B+f₀B,в рез-те найдем i,j₁(i)ч/з какой г-д ехать;n=2след.пред-м,ч.кон-й г-д груз мож.быть доставлен или из г-даS_1,S_2,S_3. f₂(S₁)=min_поj(C_s1,i1+f₁(i₁), C_s1,i2+f₁(i₂)), f₂(S₂)=min_поj(C_s2,i1+f₁(i₁), C_s2,i2+f₁(i₂)), f₂(S₃)=min_поj(C_s3,i1+f₁(i₁), C_s3,i2+f₁(i₂))РИСУНОК..мы найдем из к-го и ч/з какой г-д,т.е.i,j₂(i)

Ур-ниеБел-на для этой з-чи f_n(i)=min_поi,j(C_ij+fn-₁(j)).

45).З-ча оптим-го распр-я ср-в.n-предпр-ем выдел-ся ср-ва с.В зав-ти от выдел.суммы 0≤х≤с по каж-му пр-тию известен возм.прирост выпуска прод-и был max.

n=1-ден.ср-ва выд-ся 1-му пр-тию.Каж-му знач-ю Х по усл-ю з-чи соотв.опред-ое единств.знач-е q₁(х),зн-т мож.записать,что общ.прирост f₁(х)=q₁(х) ,0≤х≤с.

n=2-ден.ср-ва с распред-ся м/ду 2-мя пр-ями.Если2-му пр-тию буд.выд-на сумма Х,то прирост прод. На нем составит q₂(х).зн-т 1-му пр-тию остан-ся(с-х)ден.ед.,ч.поз-итувел-ть выпуск прод.до приростаf₁(с-х).Зн-т общ прирост составит q₂(х)+ f₁(с-х).Опт-му зн-ниюf₂(с) буд-т соот-ть так.зн-ние Х,для кот.посл-я сумм.буд.макс-й f₂(с)=max(q₂(х)+ f₁(с-х)), 0≤х≤с.Для всех n-пр-тий f_n(c)=max(q_n(х)+ fn-₁(с-х)), 0≤х≤с.max прирост вып.прод.на n пр-тиях опр-ся как maxсум.прироста на n-м пр-тии и прироста вып.отдел.n-1-м пр-тии при усл-и,что ост-ся после n-го пр-тия ср-ва м/дуо стал-ми пр-ями распр-ся оптим-но.

46)З-ча план-ния пр-венной прогр-мы.Рассм.пром-к,сост-й из Т мес-в,запас прод. на складе на нач.пл.пер.=i₀ед,спрос на прод в каж-м из месс-в=D_t,t=1.РИСУНОК.Опр-ть пр-вен.пр-му изгот-я прод.,удовл-ю спрос в к-м из мес-в пл.пер.и обеспеч.minз-ты на пр-во и хран-е прод.Запас прод на складе в конце пл.пер.дол.б.=0.Общ.з-ты на пр-во и хр-ние прод.С_t(x_t,i_t)сост-т из з-т на пр-во С_t(x_t)и з-т на хр-ниеед.прод.h•i_t,гдеh-з-ты на хр-ние,i_t-запасы на кон.мес.З-ты на пр-во=усл.пропорц.+пропорц.з-ты С_t(x_t,i_t)=k+l• x_t+h• i_t.Склад-е пло-ди огр-ны в-нойМ,а пр-вен.мощ-ти-в-нойВ.Введем след.обозн-я:n-№шага,соотв.обратной нумерации мес-в,d_n спрос на прод.на n-м отр.,i_n-запас прод.на нач. n- го отр.,x_n(i_n) кол-во пр-ва прод. на n-м отр.,если запас прод.на нач.этого отр.сост-т i_nед., j_n –запас прд.на кон.n-го отр.,C_n(x_n,j_n) з-ты,связ.с выпуском х_nед.прод.,с сод-ем зап-в,Vкот.на кон. n- го отр.=j_nед., f_n(i_n)-зн-еЦФ=з-там на пр-во и хр-ние прод.за n посл.мес-в,если ур-нь зап-в на нач.n-го месс.=i_nед,где n=1,N=T

n=0т.к.запас прод.на к.план.пер.д.б.=0 f₀(0)=0

n=1.Запас прод.на нач.этого отр-ка i₁неизв-н,но он м.б.=люб.цел.неотриц.числу,не превыш.вместимости скдладаМи спроса в расс-ом отр.d₁=>i₁=0,1,…,min(d₁,M).Для удовл-ния спроса на прод.Vпрод.д.б.=x₁=d₁-i₁=>f₁(i₁)=c₁(x₁,j₁)=c₁(d₁-i₁,0)

n=2. Запас прод.на нач.2-го отр-ка=i₂.Зн-яi₂м.прин-тьлюб.неотр.целоч-е зн-я,непревыш.min(d₁₊d₂,M).кол-во пр-ва прод.на 2отр.х₂в азв-ти от за-ний i₂д.б.не<d₁-i₂,т.к.спрос на 2-м отр.д.б.уд-н,но не >чем min(d₁+d₂-i₂,B).Мин.з-ты на пр-во и хр-ние прод.за 2 посл.мес.составят f₂(i₂)=min_поx2(c₂(х_2,j₂)+f₁(i₁)),гдеi₂₌=0,1,…,min(d₁₊d₂,M).,d₂-i₂ x₂ min(d₁₊d₂-i₂,B). Общ.реккурентное соотнош-е им.вид: f_n(i_n)=min_поxn(c_n(х_n,i_n+x_n-d_n)+f_n-1(i_n+x_n-d_n)),гдеi_n==0,1,…,min(d₁₊d_2+…d_n,M).,d_n-i_n x_n min(d₁₊d_2+…+d_n-i_n,B).Далее необх.пр-ти выч-я по ф-ле:f_N-1(i_N-1),i_N-1=0,1,…,min(d₁₊d_2+…d_N-1,M).f_N(i₀),i_0-зад-н.зн-я.На основ-и получ-х расч-в м.найти объемы вып.прод.в к-м мес.соотв.оптим.пл.реш-я з-чи.

48)Геометр.интерп-ция з-чиНП.Общ.з-чей НП наз-ся з-ча вида

max(min)F=f (x_1, x_2,…, x_n) (1)

φ_i (x_1, x_2,…, x_n) (2),в кот.либо ЦФ 1,либо огр-ния,либо те и др.нелин-е.В рез-те реш-я эт.з-чи буд.найдена т.Х^* такая,что для любой др.т-ки Х,коор-ты кот.также удовл-ют огран-ям з-чи и выпол-ся не=во

f(x^*)> f(x)(если з-ча на min,то f(x^*)< f(x)).В отлич.от з-чиЛП ОДР НПне всегда явл.выпуклой.Т.,в кот.достиг-ся экстр-м ф-ции мож.нах-ся как на границеОДР,так и внутри нее.Алгоритм граф.м-да:строимОДРз-чи,если она пуста,то з-ча не имеет реш-я,2)строим гиперпл-ть f(x_1, x_2,…, x_n)=h,3)опред-им гиперпл-ть наив.(наим.)ур-ня или опр-им неразд-ть з-чи из-за неогр-тиЦФ,4)нах-м т-куОДР,в кот.ЦФ достигает экстр-го знач-я и нах-м в ней знач-е ЦФ.

49)Метод множ-лей Ланг-жа реш-я задачНП.Экон-й смысл множ-ей Ланг-жа

Рассм-м частный случай общ.з-чи

max(min)F=f (x_1, x_2,…, x_n)

φ_i (x_1, x_2,…, x_n)=b_{i, i=1,m}

для того,ч.найти ее реш-е сост-ем ф-цию Ланг-жа,безусловный экстр-м кот.совпад. с условным экстр-ом

L(x_1, x_2,…, x_n,λ_1, λ_2,…, λ_n )= f (x_1, x_2,…, x_n)+ (b_i- φ_i (x_1, x_2,…, x_n))

Для эт.ф-ции запи-ем необх-е усл-е экстр-ма

Решив посл-юю сист.,мы найдем все критич.точки,в кот.ф-ция может иметь экстремум знач-я.Затем с пом.достат.усл-й определяем точки экстремума ф-ции.

Алгоритм:1)сост-ем ф-цию Ланг-жа,2)нах-им част-е произв-е ф-ции Л-жа по всем перем-м и при=ваем их к0,3)реш-в сист.ур-ний,найдем стационар-е точки,т.е.точки,в кот.ЦФ мож.иметь экстр-м,4)среди стацион-х точек с примен-ем достат.усл-й нах-им те,в кот.ф-ция имеет экстср-мы

Экон.сод-ние множ-лей Л-жа λ_i:рассм-м прост-шую з-чу оптим-ции

max(min)F=f (x_1, x₂)

φ_i (x_1, x₂)=b.Предпол-м,что экстр-м достиг-ся в как.-то точке Х^*=(x₁^*_, x₂^*), F^*=f(x₁^*_, x₂^*).пусть координаты x₁^*_и x₂^*,а значит и F^*от знач-й прав.части b

x₁^*₌x₁^*(b), x₂^*₌x₂^*(b), F^*=f(x₁^*(b)_, x₂^*(b)).Найдем част.произв-еЦФ по x₁ и x₂ в завис-ти от b

(1)из осн-х огран-й след-т,что част.произв-я ф-ции φ

=1(2)в экстр-й точке вып-ся необх.усл-е экстр-ма и (3).Подставим в 1-ую 3,испол-я2 .для з-ч,у кот.кол-во огран-й=m,т.будет спрвед-ва ф-ла ,i=1,m

50) Градиент.метод решения задачНП

Используя град.метод,можно найти решение люб.з-чиНП,но дан.методы целесообразно испол-ть для нахожд-я решения з-ч выпуклого прогр-ния,т.е.,когда локал.экстремум явл.одновр-но и глобал-м.Для примера будем рассм-ть з-чу макс-ции диффер-й функции.

Решение нач-ся с определен.точкиХ₀,корд-ты кот.удовл-ютОДР.В эт.точке находим градиент ф-ции .Сделав небол шаг в найд-м напр-ии,перех-м какую-то т.Х₁,в кот.опять ищем оптим.напр-ие gradF(X₁)и т.д.

Проц.нахож-ия реш-я пред.соб.ломаную линию Х_0,Х_1,Х_2...в точ-х эт.ломаной знач-яЦФдолжны сход-ся F(x₀)< F(x₁)< … <F(x^*).Переход от т.Х_к к т.Х_к+1 осущ-ся по прямой,ур-ние кот. Опр-ся из ур-ния Х_к+1=Х_к+λ_к• gradF(X_к),где λ _к –шаг,знач-е кот.опред-ся по фор-ле: gradF(X_к+1)• gradF(X_к)=0.

Если окаж-ся,что F(x_к+1)< F(x_к),то следует вернуться в т. Х_к и умен-ть шаг λ _к. Итерацион-й проц.осущ-ся до того момента,пока град-т ф-ции в очередной точке не станет=0 или пока не выпол-ся не=во I F(x_к+1)- F(x_к)I≤ξ ,гдеξ-очень мален-е полож-е число.