Понятие о ДП. Геом. Интерпр.

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

Пусть n-размерн-ть простр-ва сост-ий. С течен. вр. знач. коорд-ат вектора сост-я могут менят-я. Переход из одного сост-я сист в др-е наз – траекторией движ-я сист в простр-е сост-ия. Если изве-ны начал и конеч сост-ие системы то говорят о задаче с закрепл-ми концами. Если же извес только области начал и конеч сост-ия сист, то имеем дело с задач со своюод-ми концами.

42. Принципы ДП. 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.Вкл исх г-д А.2.Вкл все г-да, в к-рые мжн попасть из 1-го подм-ва в 3-е подмн-во. Вкл все г-да, в к-рые мжн попасть из 2-го подмн-ва и т.д.3.Перенумер этапы от конечного г-да к исх-му. 4.Введём след обознач-я: n -номер шага / с_ij – ст-ть перевозки (расстояние) из г-да i в г-д j. / f_n(i) – мин з-ты на перевозку груза из г-да i до конечного г-да, если до конечного г-да осталось n-шагов./ j_n(i) - номер г-да, через к-рый нужно ехать из г-да i чтобы достичь f_n(i). Сост рекуррентное соотнош-е: Пусть n=0. Эт знач, что мы находимся в конечном г-де, след-но f_n(i)=f₀(B)=0. / Пусть n=1. Эт знач, что до конечного г-да остался 1 шаг, предполож, что в конечный г-д груз мот быть доставлен или из г-да i₁ или из г-да i₂. Тогда з-ты на перевозку из этих 2-х состояний будут равны. f₁(i₁)= с_i2,B+ f₀(B), i и j₁(i) / Пусть n=2. Предполож, что груз нах-ся в г-де S₁ или S₂ или S₃. В этом случ из г-да S₁в г-д В груз мжн провезти или чрз г-д i₁ или чрз г-д i₂. Тогда оптимал маршрут найдётся из выр-я f₂(S₁)=min(по всем j)(с_s1i1+f₁(i₁); с_s1i2+f₁(i₂)), общая формулаf_n(i)= min(по всемi, j)(сij+ f_n-1(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-зад-н.зн-я.На основ-и получ-х расч-в м.найти объемы вып.прод.в к-м мес.соотв.оптим.пл.реш-я з-чи.

Задача замены оборуд

Т – продолж-ть план. Периода, t – возраст оборуд-ия, r(t) – cтоим. Прод-ции, u(t) – экспл-е затр-ы, s(t) – остат-я стоим., F_k(t) – макс. Прибыль за k лет.

возможнсти: 1)Сохр-ть оборуд-е: тогда прибыль = r(t) – u(t). 2) Продать оборуд.: прибыль = s(t) – p + r(0) – u(0)

Если s(t) – p + r(0) – u(0) >r(t) – u(t), то замена

Если s(t) – p + r(0) – u(0) <= r(t) – u(t), то cохраняем

Общее функцион-е ур-ие:

r(t) – u(t) + F_k-1(t+1), сохран-е

F_k(t) = maxs(t) – p + r(0) – u(0) + F_k-1(1), замена

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)нах-м т-куОДР,в кот.ЦФ достигает экстр-го знач-я и нах-м в ней знач-е ЦФ.Один-ми знаками в столбце свободн.членов и разреш-м столбце наход-ся симплекс-е отношения.Наименьш.симплексн.отношение и определяет разреш-щую строку