42.Метод ветвей и границ.

Для определённости будем рассчит з-чу нахожд мах ф-ции. Суть м-да заключ-ся в том,что сначала реш-ся з-ча без учёта целочис-сти.Если в полученном решении нек.переменные имеют дробные знач,то выбир.любую из дроб-х переем-х и по ней строим 2 ограничения.В 1-м ограничен.велич.переменой берется <или = наибольшему целому числу,а во 2-м огранич.она >или = наименьш.целому значен,но не < значения дробной переменной.Т.о. исходн.зад.ветвится на 2 новые подзад.Если после их реш.получ-е значения неизв-х будут нецелые,то.сравнив значения ЦФ, выбираем подзадачу с большим значением ЦФ.По новой неизвестной с дробным значен.снова строим 2 доп-х ограничен., тем самым разбивая выбранную подзадачу еще на 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*)такое,что доставляетЦФ экстремум при огр-ях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 – возможные состояния системы на начало N-го этапа,тогда F₁(x_N-1)=max(min)_uN€ΩNf_N(X_N-1,U_N) (2);Для 2-х последних этапов:F₂(x_N-2)=max(min)_{uN-1€ΩN-1,N}(f_N-2(x_N-2,u_N-1)+ F₁(x_N-1)) (3); F_N(x₀)=max(min)_u1€Ω(f₁(x_0,u₁)+ F_N-1(x₁)) (4).Ф-лы2-4наз-ся функц-м ур-нием Бел-на.длятого,ч.найтиоптимур-ние наNшагах,нужно знать усл.-оптим.ур-ния на предшес-х N-1шаге.

44. Вычисл схема реш задач методом дп

Раньше всех планируется последнийN-й шаг, за ним N-1 и т.д.Длякаждвозможн исхода X_N-1 на N-1 шаге находим оптимуправл на N-м шаге. Такой набор оптим-хуправл-й, зависящих от возможных исходов предыд этапа наз. усл-оптим решением: u^*_N(x_N-1). Завершив анализ конечн этапа – рассм аналог задачу для предпослед этапа, при этом треб, чтобы ЦФ достиг экстремзнач на 2-х послед этапах вместе. В итоге найдем усл-оптимреш на предпослед этапе: u^*_N-1(x_N-2) и т.д.

Проделав такой поиск усл-оптимуправл от конца к началу, найдем последов-тьусл-оптимуправл: u^*₁ (x₀), u^*₂ (x₁), …, u^*_N (x_N-1). Усл-оптимуправл дают возмож-ть найти оптимуправл на кажд шаге. Пусть начальноесост-е Х₀ известно, тогда проделав процедуру движ от начала к концу найдем U^*₁ (X₀), а т.к. начальнсост известно, то это и будет явлоптимуправл для 1-го шага. В рез-те перейдем к какому-то сост на начало 2-го шага: Х^*₁. Т.о., двиг от начала к концу, найдем оптимуправл для всех этапов => в процессе реш задач ДПмногошаг процесс проходится дважды: 1)от конца к началу, в рез-те чего будут найдены усл-оптимуправл и усл-оптимзнач ЦФ для кажд шага, в т.ч. будет определено оптимальное управление для 1-го шага и оптимальное значение ЦФ для всего процесса. 2)от нач к концу, в рез-те чего будут опредоптимуправл на кажд шаге с точки зрения всего процесса.

45. Пустьнеобх-мо найти маршрут, связыв-й города А и В, для к-госуммарн затраты на перевозку груза были бы наименьшими. Сеть дорог, связыв-я эти г-да, представл собой ориентированный граф. Чтобы данную з-чу решить м-дом ДП, всё мн-во г-дов разобьём на подмн-ва.В 1-е подмн-во включ.исх г-д А. Во 2-е вкл все г-да, в к-рые можно попасть из 1-го подм-ва. В 3-е подмн-во вкл все г-да, в к-рыемжн попасть из 2-го подмн-ва и т.д.Перенумеруем этапы от конечного г-да к исх-му.Введём след обознач-я: 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₁)= с_i1,B+f₀(B),найдемiи j₁(i),f₁(i₂)= с_i2,B+f₀(B),найдемi и j₁(i). Пусть n=2.Предполож, что груз нах-ся в г-де S₁ или S₂ или S₃. В этом случ из г-да S₁ в г-д В груз мжн провезти или чрз г-д i₁ или чрз г-д i₂. Тогда оптимал маршрут найдётся из выр-я f₂(s₁)=min(по всем j)(с_s1,i1+f₁(i₁); с_s1,i2+f₁(i₂)),найдем i и j₂(i).общая формула будет иметь вид: f_n(i)= min(по всемi, j)(сi,j+ f_n-1(j))

46.З-ча оптим-го распр-я ср-в.

Пустьn-предпр-ям выдел-ются сумма с. По каждому предпр. Изв. Прирост выпуска прод-ии в зав-ти от выдел.суммы х; gi(х)- прирост(0≤х≤с),i=1;n. Треб-ся так распред-ть сре-ва см//у nпредпр-ми,чтобы общий прирост выпущ.прод-ии fn(c) был макс-ым.

n=1.Это означ.,чтоден.ср-ва выдел-ся одному предп-тию.F1(х)- прирост выпуска прод-ии на этом предпр-тии.Каж-му знач-ю Х соотв. единств.знач-е g1(х),зн-т мож.записать:F1(х)=g1(х).

n=2-ден.ср-ва с распред-ся м//у 2-мя пр-ями.Если2-му пр-тию буд.выд-на сумма Х,то прирост прод-ии на нем составитg1(х). След-но 1-му пр-тию остан-ся(с-х)ден.ед., а приростg1(c-x)=f1(c-x). Максим.прирост выпуска прод-ии на 2х предп-ях будет достигнут при таком х,чтобы сумма прироста на обоих предпр-ях была макс-ой: f₂(с)=max(q₂(х)+ f₁(с-х)), 0≤х≤с. Тогдадля всех n-предп-тий f_n(c)=max(q_n(х)+ fn-₁(с-х))- функцион. уравне-е Беллмана , 0≤х≤сТ.о. max-ый прирост вып.прод-ии на n пр-тиях опр-ся как max-ум суммы прироста выпуска прод-ии на n-м пр-тии и прироста выпуска прод-ии на остальн. (n-1) предп-тии при усл,что оставшиеся ср-ва (с-х)распред-ся м//уостальн. предпр-ями распр-ся оптим-но.Для того,чтобы найти оптим.распред.сре-в,надо найти сумму выделен. n-му предпр:хn*(c),кот и позволит ЦФ достичь max-ма.Затем по оставшейся сумме c-хn*(c)и значен. Fn-1 найдём сумму ср-в,выдел. препоследнему предп-ию хn-1*(c)и найдём х1*(с).