Учебные материалы по математике | Градиентный метод решения задач | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

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


Проделав такой поиск усл-оптим управл от конца к началу, найдем последов-ть усл-оптим управл: 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)среди стацион-х точек с примен-ем достат. усл-й нах-им те, в кот. ф-ция имеет экстср-мы

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод