шпоры методы оптимизации. Задача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают
 Скачать 1.38 Mb.
|
|
Теор: Если явл. слабой минималью в простейшей задаче вариационного исчисления с фиксированным левым и подвижным правым концом то она уд. ур-нию Эйлера, граничным усл. и условию трансверсальности на правом конце . Замечание Если левый конец траектории тоже является подвижным(лежит на гладкой кривой (x=) , то экстремаль удовлетворяет дифференциальному уравнению Эйлера, краевым условием и условиям трансерсальности , 47. Примеры задач динамического программирования, их особенности Динам программирование (ДМ) (динам планирование) – это метод нахождения оптим реш в задаче с многошаг структурой. Многие эконом задачи раздел на шаги естеств образом, это н-р, процессы планир и управления развиваемые во времени. Естеств шагом в них может быть год, квартал, месяц и т.д. Однако МДП может исп при реш задач, где время не фигурирует. Разделение на шаги в таких задачах вводится искусственно, поэтому динамика ЗДП заключ в методе реш-я. К ЗДП относ задачи перспективного и текущ планирования во времени, задача многошагов нахож-я оптимума при размещ производит сил, задачи оптим быстродействия. Выделим особенности ЗДП: 1. в задаче рассм система, состояния кот в каж мом времени t опред вектором . Дальнейшее изменение состояние системы зависит от дан состояния и не зав от того, каким путём система пришла в это состояние. Такие процессы наз проц без последействия. 2. на каж шаге выбирается одно решение ( управление), под действ кот система переходит из предыдущ состояния в след состояние . Это нов сост явл ф-ей сост-я на начало интервала и принятого в начале интервала решения , т.е.. 3 Действ на каж шаге связаны с опред выигрышем (доходом, прибылью) или потерей (издержками), кот зависят от состояний на начало шага и принятого решения. 4. На векторы состояния и управления может быть наложены ограничения, объединение которых представляют область допуст значений. 5. Требуется найти такое допустимое управление для каждого шага t, чтобы получить экстремальн значение ф-ции цели за все T шагов. Любую допустимую посл-ть действий для каж шага, переводящую систему из нач состояния в конечное наз стратегией управления. Допуст стратегия управления, доставляющая цели экстрем значение наз оптимальной. Пример Задача перспективного планирования. Пусть планируется деятельность группы из N промыш предприятий (пр) на перид Т хоз лет. В нач период на развитие системы пр выделены некот ср-ва в кол-ве K, кот д\б распределены между пр. В проц деят пр вложенные в него ср-ва частично амортизируются. Каж пр за год приносит доход в зависит от вложен ср-в, часть которого отчисл в фонд пр. В нач каж хоз года имеющ ср-ва перераспределяются между пр-ями. Возник задачи определения объема ср-в в нач каж года, кот нужно выделить каждому пр-ю чтобы суммарн чистый доход за Т лет был максимальным. В этой задаче проц принятия решения разбив на T шагов. Управление этим процессам заключ в нач и последовательном распред ср-в , где есть объем ср-в , выделенных i–ому предпр в нач t–го года. Состояние системы опис вектором , где сост i–го предпр. на нач t–го года. В свою очередь состояние каждого пр-я явл вектором, компонентами кот служат труд ресурсы, осн фонды, фин положение и т.д. Очевидно, что вектор управления есть ф-ция состояния системы на начало соотв периода, т.е. . Нач сост системы может быть заданным. В кач целевой ф-ции часто рассм суммарн прибыль объединения пр-й за Т хоз лет. Управление выбирается из некот мн-ва, кот может быть описано как мн-во эконом возможностей, определ различ ограничениями, налагаемыми на состояние системы и вектор управления 48.Принципы динамического программирования и функциональные уравнения Беллмана. В осн вычисл алгоритмов метода ДП лежит след принцип оптимальности: каково бы ни было состояние системы в рез t-1 шагов управление на шаге t должно выбираться так, чтобы оно в совокупности с управлениями на всех посл шагах с (t-1) до N включительно, доставляло экстремум целев ф-ции. Введем след обозначения: - мн-ва всех состояний в кот может нах система перед шагом . В частности при -мн-во нач состояний; - мн-ыо управлений, кот могут быть выбраны на шаге и под воздейств каж их кот система переходит из сост принадлежащего мн-ву в сост, принадлежащее мн-ву - условно оптимальная значение цел ф-ции, если процесс рассм на инт от шага до шага N при усл, что перед шагом t система находилась в одном их сост мн-ва и на шаге t было выбрано управление из мн-ва , которое обеспечило цел ф-ции усл оптим значения; - значение целевой ф-ции на i–ом шаге для всех управлений их мн-ва при усл, что система нах-лась в одном их сост мн-ва . В принятых обозначениях принцип опт-ти можно записать в след форме:(1) Ур-ние (1) наз функцион ур-нием ДП(функц Ур Беллмана). Для последнего шага Ур (1) приним вид:, т.к. ф-ции опред для , то . И тогда на посл шаге справ-во ур-ние:,(2).Т.к. рассм система без последействия, то , то на основании ур (1)-(3) с учетом конкрет мн-в строится высислительная процедура МДП, кот разделяется на 2 этапа: 1. условную; 2. безусловную оптимизацию. Усл опт-ция осуществляется путем обратного движения от последнего шага к первому. Из ур (2) находится такое упраление из мн-ва , кот для каж состояния принадлежащего мн-ву доставляет экстремум ф-ции и сисмема переходит в конечное состояние. Т.одля каждого состояния из мн-ва нах-ся условно-оптимальне знение целевй ф-ции и условно-оптим управление на последнем шаге. Далее из уравнения (1) нах-ся усл-оптим управление на (N-1) шаге и усл-оптим значение целевой ф-ции на 2-ух последних шагах. При этом для каждого состояния из мн-ва и управления из мн-ва по ф-ле (3) нах-ся соотв состояние из мн-ва и поэтому состоянию учетом разультатов, предшествующих расчетов определяется усл-оптим значение целевой ф-ции, начиная рассм шага до конечного. Процесс продолжается до 1-го шага. Безусл-оптим управление нах на этапе безусл оптимизации путем прямого движения от 1-го этапа к последнему. Природа задачи, допускающая использование метода ДП не изменяется при изменении кол-ва шагов N. В этом смысле всякий конкрет процесс с задан кол-вом шагов оказывается как бы погруженным в сем-во подобных процессов и может рассм с позиции более широкого класса задач. В этом заключается 2-ой принцип ДП, наз-емый принципом погружения.В силу этого св-ва при реш задачи методом ДП получают более широкий спектр рез-тов чем в исх постановке. Заметим, что МДП при выборе решения на каж шаге учитывает интересы всего процесса, а не только интересы дан шага.
|