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

Для определённости будем рассчитывать з-чу нахождения максимума ф-ции.Суть м-да заключ-ся в том,что сначала реш-ся з-ча без учёта целочис-сти.Если в полученном решении нек.переменные имеют дробные значения,то выбираем любую из дроб-х переменных и по ней строим 2-а ограничения.В первом ограничении величина переменной меньше или равна наименьшему целому числу,а во второй переменной ≥ целому числу +1.Таким образом исходная задача ветвится на 2 з-чи.Решаем каждую из подзадач и находим оптимальное решение.Если получ-е решения опять являются нецелыми,то дальнейшему ветвлению подлежит та ветвь,у которой значение ЦФ будет больше.Процесс решения сопровождается построением деревоветвл-ем.

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

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

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

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-шагов.

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

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

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

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

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