Градиентный метод решения задач

Проделав такой поиск усл-оптим управл от конца к началу, найдем последов-ть усл-оптим управл: U*1 (X0), U*2 (X1), …, U*n (Xn-1). Усл-оптим управл дают возмож-ть найти оптим управл на кажд шаге. Понятно, что нач сост Х0 известно, тогда проделав процедуру движ от начала к концу найдем U*1 (X0), а т. к. начальн сост известно, то это и будет явл оптим управл для 1-го шага. В рез-те перейдем к какому-то сост на начало 2-го шага: Х*1. Т. о., двиг от начала к концу, найдем оптим управл для всех этапов => в процессе реш задач д. п. многошаг процесс проходится дважды: 1)от конца к началу, в рез-те чего будут найдены усл-оптим управл и усл-оптим знач ц. ф. для кажд шага, в т. ч. будет определено оптимальное управление для 1-го шага и оптимальное значение ц. ф. для всего процесса. 2)от нач к концу, в рез-те чего будут опред оптим управл на кажд шаге с точки зрения всего процесса.

45. Пуст необх-мо найти маршрут, связыв-й города А и В для к-го суммарн з-ты на перевозку груза были бы наим-ми. Сеть дорог, связыв-я эти г-да, представл собой ориентированный граф. чтобы данную з-чу решить м-дом ДП всё мн-во г-дов разобьём на подмн-ва.1.Вкл исх г-д А.2.Вкл все г-да, в к-рые мжн попасть из 1-го подм-ва в 3-е подмн-во. Вкл все г-да, в к-рые мжн попасть из 2-го подмн-ва и т. д.3.Перенумер этапы от конечного г-да к исх-му. 4.Введём след обознач-я: n-номер шага /сij – ст-ть перевозки (расстояние) из г-да i в г-д j. /fn(i) – мин з-ты на перевозку груза из г-да i до конечного г-да, если до конечного г-да осталось n-шагов. / jn(i) — номер г-да, через к-рый нужно ехать из г-да i чтобы достичь fn(i) . Сост рекуррентное соотнош-е: Пусть n=0. Эт знач, что мы находимся в конечном г-де, след-но fn(i)=f0(B)=0. / Пусть n=1. Эт знач, что до конечного г-да остался 1 шаг, предполож, что в конечный г-д груз мот быть доставлен или из г-да i1 или из г-да i2. Тогда з-ты на перевозку из этих 2-х состояний будут равны. f1(i1)= сi2,B+f0(B), i и j1(i) / Пусть n=2. Предполож, что груз нах-ся в г-де S1 или S2 или S3. В этом случ из г-да S1 в г-д В груз мжн провезти или чрз г-д i1 или чрз г-д i2. Тогда оптимал маршрут найдётся из выр-я f2(S1)=min(по всем j)(сs1i1+f1(i1); сs1i2+f1(i2)), общая формулаfn(i)= min(по всемi, j)(сij+ fn-1(j))

46.З-ча оптим-го распр-я ср-в.n-предпр-ем выдел-ся ср-ва с. В зав-ти от выдел. суммы 0≤х≤с по каж-му пр-тию известен возм. прирост выпуска прод-и был max. n=1-ден. ср-ва выд-ся 1-му пр-тию. Каж-му знач-ю Х по усл-ю з-чи соотв. опред-ое единств. знач-е q1(х),зн-т мож. записать, что общ. прирост f1(х)=q1(х) ,0≤х≤с. n=2-ден. ср-ва с распред-ся м/ду 2-мя пр-ями. Если2-му пр-тию буд. выд-на сумма Х, то прирост прод. На нем составит q2(х).зн-т 1-му пр-тию остан-ся(с-х)ден. ед.,ч. поз-итувел-ть выпуск прод. до приростаf1(с-х).Зн-т общ прирост составит q2(х)+ f1(с-х).Опт-му зн-ниюf2(с) буд-т соот-ть так. зн-ние Х, для кот. посл-я сумм. буд. макс-й f2(с)=max(q2(х)+ f1(с-х)), 0≤х≤с. Для всех n-пр-тий fn(c)=max(qn(х)+ fn-1(с-х)), 0≤х≤с. max прирост вып. прод. на n пр-тиях опр-ся как maxсум. прироста на n-м пр-тии и прироста вып. отдел. n-1-м пр-тии при усл-и, что ост-ся после n-го пр-тия ср-ва м/дуо стал-ми пр-ями распр-ся оптим-но.

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

Использ град. метод, можно найти реш люб. з-чиНП, но дан. методы целесообразно испол-ть для нахожд-я реш з-ч выпуклого прогр-ния, т.е.,когда локал. экстремум явл. одновр-но и глобал-м. Для примера будем рассм-ть з-чу макс-ции диффер-й функции. Реш нач-ся с определен. точкиХ0,корд-ты кот. удовл-ютОДР. В эт. точке находим градиент ф-ции .Сделав небол шаг в найд-м напр-ии, перех-м какую-то т. Х1,в кот. опять ищем оптим. напр-ие gradF(X1)и т. д.Проц. нахож-ия реш пред. соб. ломаную линию Х0,Х1,Х2…в точ-х эт. ломаной знач-яЦФдолжны сход-ся F(x0)< F(x1)< … <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≤ξ ,гдеξ-очень мален-е полож-е число.

47.З-ча план-ния пр-венной прогр-мы. Рассм.пром-к, сост-й из Т мес-в, запас прод. на складе на нач. пл. пер.=i0ед, спрос на прод в каж-м из месс-в=Dt, t=1..Опр-ть пр-вен. пр-му изгот-я прод.,удовл-ю спрос в к-м из мес-в пл. пер. и обеспеч. minз-ты на пр-во и хран-е прод. Запас прод на складе в конце пл. пер. дол. б.=0.Общ. з-ты на пр-во и хр-ние прод. Сt(xt, it)сост-т из з-т на пр-во Сt(xt)и з-т на хр-ниеед. прод. h•it, гдеh-з-ты на хр-ние, it-запасы на кон. мес. З-ты на пр-во=усл. пропорц.+пропорц. з-ты Сt(xt, it)=k+l• xt+h• it. Склад-е пло-ди огр-ны в-нойМ, а пр-вен. мощ-ти-в-нойВ. Введем след. обозн-я:n-№шага, соотв. обратной нумерации мес-в, dn спрос на прод. на n-м отр.,in-запас прод. на нач. n — го отр.,xn(in) кол-во пр-ва прод. на n-м отр.,если запас прод. на нач. этого отр. сост-т inед., jn –запас прд. на кон. n-го отр.,Cn(xn, jn) з-ты, связ. с выпуском хnед. прод.,с сод-ем зап-в, Vкот. на кон. n — го отр.=jnед., fn(in)-зн-еЦФ=з-там на пр-во и хр-ние прод. за n посл. мес-в, если ур-нь зап-в на нач. n-го месс.=inед, где n=1,N=T

n=0т. к.запас прод. на к. план. пер. д.б.=0f0(0)=0 n=1.Запас прод. на нач. этого отр-ка i1неизв-н, но он м. б.=люб. цел. неотриц. числу, не превыш. вместимости скдладаМи спроса в расс-ом отр. d1=>i1=0,1,…,min(d1,M).Для удовл-ния спроса на прод. Vпрод. д.б.=x1=d1-i1=>f1(i1)=c1(x1,j1)=c1(d1-i1,0) n=2. Запас прод. на нач.2-го отр-ка=i2.Зн-яi2м. прин-ть люб. неотр. целоч-е зн-я, непревыш. Min (d1+d2,M) кол-во пр-ва прод. на 2отр. х2в азв-ти от за-ний i2д. б.не<d1-i2,т. к.спрос на 2-м отр. д.б. уд-н, но не >чем min(d1+d2-i2,B).Мин. з-ты на пр-во и хр-ние прод. за 2 посл. мес. составят f2(i2)=minпоx2(c2(х2,j2)+f1(i1)),гдеi2==0,1,…,min(d1+d2,M).,d2—i2x2min(d1+d2—i2,B). Общ. реккурентное соотнош-е им. вид: fn(in)=minпоxn(cn(хn, in+xn-dn)+fn-1(in+xn-dn)),гдеin==0,1,…,min(d1+d2+…dn, M).,dn-inxnmin(d1+d2+…+dn-in, B). Далее необх. пр-ти выч-я по ф-ле:fN-1(iN-1),iN-1=0,1,…,min(d1+d2+…dN-1,M).fN(i0),i0-зад-н. зн-я. На основ-и получ-х расч-в м. найти объемы вып. прод. в к-м мес. соотв. оптим. пл. реш-я з-чи.

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

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

max(min)F=f (x1, x2,…, xn)

φi (x1, x2,…, xn)=bi, i=1,m

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

L(x1, x2,…, xn,λ1, λ2,…, λn )= f (x1, x2,…, xn)+(bi — φi (x1, x2,…, xn))

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

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

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