Некрасова М.Г. Методы оптимизации - файл n1.doc

приобрести
Некрасова М.Г. Методы оптимизации
скачать (3013.5 kb.)
Доступные файлы (1):
n1.doc3014kb.22.08.2012 14:29скачать

n1.doc

1   ...   4   5   6   7   8   9   10   11   12

Теорема 4. Необходимые условия оптимальности


Пусть х* минимизирует f(x) при ограничениях  Предполагается, что S – выпуклое множество, f(x) – выпуклая функция, а gj(x) – функции, вогнутые на множестве S. Предполагается также, что существует такая точка , в которой  для всех j=1, 2, …, J. Тогда существует такой вектор множителей , что (x*, u*) является седловой точкой функции Лагранжа



и неравенство



выполняется для всех

Следующая теорема обеспечивает некоторое упрощение вычислений, связанных с нахождением седловой точки.

Теорема 5. Вектор (x*; u*), где , определяет седловую точку в задаче Куна – Таккера о седловой точке тогда и только тогда, когда выполняются следующие условия:

1)        х* минимизирует L(x; u*) по всем ;

2)         для j =1, …, J;

3)         для j=1, …, J.

Важно отметить, что существование седловых  точек характерно не для всех задач нелинейного программирования; седловые точки имеются лишь в тех задачах, которые отвечают условиям теоремы 4.

 
Вопросы к главе 7
 

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

2.    Что такое седловая точка? Какую роль играет решение задачи о седловой точке в условной оптимизации?

3.    При выполнении каких условий существуют седловые точки в задачах нелинейного программирования?

4.    Укажите основные направления использования необходимых и достаточных условий оптимальности второго порядка.

5.    Напишите функцию Лагранжа.

Глава 8. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Динамическое программирование – это не алгоритм. Речь идет скорее об общем принципе, допускающем приложения ко многим задачам оптимизации с ограничениями, линейными и нелинейными, с непрерывными или дискретными переменными, но обладающими некоторым свойством, называемым разложимостью.

Термин «динамическое программирование» по происхождению связан с тем, что этот метод применялся к оптимизации динамических систем, т.е. систем, меняющихся в ходе  времени, эволюция которых может управляться некоторыми переменными управления. Однако принцип динамического программирования носит более общий характер и может применяться к задачам, в которых время не участвует, например, к задачам целочисленной оптимизации.

Динамическое программирование связано с возможностью представления процесса управления в виде цепочки последова­тельных действий или шагов, развернутых во времени и веду­щих к цели. Таким образом, процесс управления можно разде­лить на части и представить его в виде динамической последо­вательности и интерпретировать в виде пошаговой программы, развернутой во времени. Это позволяет спланировать програм­му будущих действий. Поскольку вариантов возможных планов - программ множество, то, необходимо из них выбрать лучший, оптимальный по какому-либо критерию в соответствии с постав­ленной целью.

В динамическом программировании можно выделить следующие аспекты: теоретический (доказательство теорем существования, единственности, сходимости), прикладной (построение моделей для конкретных задач оптимизации) и вычислительный. Для нас решающим является второй и в некоторой степени третий аспект.

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

8.1. Предмет динамического программирования

Динамическое программирование представляет собой мате­матический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью явля­ется решение задач по этапам, через фиксированные интерва­лы, промежутки времени, что и определило появление термина «динамическое программирование». Следует заметить, что мето­ды динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как поша­говое или поэтапное программирование. Решение задач метода­ми динамического программирования проводится на основе сформулированного Р.Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптималь­ное поведение относительно состояния, полученного в резуль­тате первоначального решения.

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

Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы.

В целом динамическое программирование представляет со­бой теорию стройную для восприятия и достаточно простую для применения в коммерческой деятельности при решении как ли­нейных, так и нелинейных задач.

Динамическое программирование (ДП) является одним из разделов оптимального программирования. Для него характер­ны специфические методы и приемы, применяемые к опера­циям, в которых процесс принятия решения разбит на этапы (шаги). Методами ДП решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенны­ми связями между переменными и целевой функцией, выражен­ными системой уравнений или неравенств. При этом, как и в за­дачах, решаемых методами линейного программирования, огра­ничения могут быть даны в виде равенств или неравенств. Одна­ко если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах ДП эти зависимости могут иметь еще и нелинейный характер. ДП можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ре­сурсов. Это значительно расширяет область применения ДП для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариан­тов, увеличивает достоинства этого комплекса методов.

Вместе с тем ДП свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется свои­ми особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, боль­шие объемы и трудоемкость решения многошаговых задач, име­ющих множество состояний, приводят к необходимости отбора задач малой размерности, либо использования сжатой информа­ции. Последнее достигается с помощью методов анализа вариан­тов и переработки списка состояний.

Для процессов с непрерывным временем ДП рассматривает­ся как предельный вариант дискретной схемы решения. Получа­емые при этом результаты практически совпадают с теми, кото­рые получаются методами максимума Л. С. Понтрягина или Га­мильтона — Якоби — Беллмана.

ДП применяется для решения задач, в которых поиск опти­мума возможен при поэтапном подходе, например:

      распределе­ние дефицитных капитальных вложений между новыми направ­лениями их использования;

      разработка правил управления спро­сом или запасами, устанавливающими момент пополнения за­паса и размер пополняющего заказа;

      разработка принципов календарного планирования производства и выравнивания за­нятости в условиях колеблющегося спроса на продукцию;

      со­ставления календарных планов текущего и капитального ремон­тов оборудования и его замены;

      поиск кратчайших расстояний на транспортной сети;

      при распределении инвестиций по направлениям использования;

      разработки долгосрочных программ функционирования хозяйствующих субъектов;

      формирование последовательности раз­вития коммерческой операции и т.д.

8.2. Постановка задачи динамического программирования

Постановку задачи динамического программирования рас­смотрим на примере инвестирования, связанного с распределе­нием средств между предприятиями. В результате управления инвестициями система последовательно переводится из началь­ного состояния s0 в конечное sn. Предположим, что управление можно разбить на п шагов и решение принимается последователь­но на каждом шаге, а управление представляет собой совокуп­ность п пошаговых управлений. На каждом шаге необходимо определить два типа переменных - переменную состояния систе­мы sk и переменную управления хk. Переменная sk определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния s на этом шаге можно при­менить некоторые управления, которые характеризуются переменной хk которые удовлетворяют определенным ограничениям и называются допустимыми.

Допустим,  - управление, переводящее систему из состояния s0 в состояние sn , а sn  — есть состояние сис­темы на k-м шаге управления. Тогда последовательность состоя­ний системы можно представить в виде графа, представленного на рис. 41.


 

Применение управляющего воздействия хk  на каждом шаге переводит систему в новое состояние s1(s, xk) и приносит некото­рый результат Wk(s, xk). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оп­тимальное управление xk*, такое, чтобы результат, который дос­тигается за шаги с    k-го по последний n-й, оказался бы оптималь­ным. Числовая характеристика этого результата называется фун­кцией Беллмана Fk(s) и зависит от номера шага k и состояния системы s.

Задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния s0 в конечное со­стояние sn, при котором целевая функция принимает наиболь­шее (наименьшее) значение .

Особенности математической модели динамического про­граммирования заключаются в следующем:

1)        задача оптимизации формулируется как конечный многоша­говый процесс управления;

2)        целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:



3)        выбор управления хk на каждом шаге зависит только от со­стояния системы k этому шагу sk-1 и не влияет на предшеству­ющие шаги (нет обратной связи);

4)        состояние системы sk после каждого шага управления зави­сит только от предшествующего состояния системы sk-1 и этого управляющего воздействия хk (отсутствие последей­ствия) и может быть записано в виде уравнения состоя­ния:

;

5)        на каждом шаге управление хk зависит от конечного числа уп­равляющих переменных, а состояние системы зависит sk — от конечного числа параметров;

6)        оптимальное управление представляет собой вектор , оп­ределяемый последовательностью оптимальных пошаговых управлений: число которых и опреде­ляет количество шагов задачи.

8.3. Принцип оптимальности и математическое описание динамического процесса управления

В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р. Э. Беллманом: каково бы ни было состояние системы в резуль­тате какого-либо числа шагов, на ближайшем шаге нужно выби­рать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптималь­ному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирает­ся управление, которое должно привести к оптимальному выиг­рышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максималь­ный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксп­луатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохо­да в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс.

Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств ос­талось в наличии к этому году и какой доход получен в предыду­щем (i - 1)-м году. Таким образом, при выборе шагового управле­ния необходимо учитывать следующие требования:

      возможные исходы предыдущего шага sk-1;

      влияние управления хk на все оставшиеся до конца процесса шаги (n - k).

В задачах динамического программирования первое требова­ние учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и прово­дя для каждого из вариантов условную оптимизацию. Выполне­ние второго требования обеспечивается тем, что в этих задачах условная оптимизация проводится от конца процесса к началу.

Условная оптимизация. На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных со­стояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге опти­мальное управление – xn* определяется функцией Беллмана: , в соответствии с которой максимум вы­бирается из всех возможных значений хn, причем .

Дальнейшие вычисления производятся согласно рекуррен­тному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на преды­дущем шаге. В общем виде это уравнение имеет вид



Этот максимум (или минимум) определяется по всем возможным для k и s значениям переменной управления Х.

Безусловная оптимизация. После того, как функция Бел­лмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно - это ее начальное состояние s0, можно найти опти­мальный результат за все n шагов и оптимальное управление на первом шаге х1, которое этот результат доставляет. После при­менения этого управления система перейдет в другое состояние s1(s, x1*), зная которое, можно, пользуясь результатами услов­ной оптимизации, найти оптимальное управление на втором шаге х2*, и так далее до последнего n-го шага.

Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам пря­мой прогонки (от начала) и обратной прогонки (от конца к нача­лу). Рассмотрим примеры решения различных по своей приро­де задач, содержание которых требует выбора переменных со­стояния и управления.

8.4. Общая схема применения метода динамического программирования

Приведем общую схему применения метода ДП.

Предположим, что все требования, предъявляемые к задаче динамического программирования, выполнены. Построение метода ДП для решения сводится к следующим моментам:

1) Выбирается способ деления процесса управления на шаги.

2) Определяются параметры состояния sk и переменные управления Xk на каждом шаге.

3) Записываются уравнения состояний.

4) Вводятся целевые функции k-го шага и суммарная целевая функция.

5) Вводятся в рассмотрение условные максимумы (минимумы) Z*k(sk-1) и условное оптимальное управление на k-м шаге: X*k(sk-1), k =n, n-1, …, 2, 1.

6) Записываются основные для вычислительной схемы ДП Беллмана для Z*n(sn-1) и Z*k(sk-1), k=n-1, …, 1.

7) Решаются последовательно уравнения Беллмана (условная оптимизация), и получаются две последовательности функций: {Z*k(sk-1)}, {X*k(sk-1)}.

8) После выполнения условной оптимизации определяется оптимальное решение для конкретного начального состояния s0:

а) Zmax = Z*1(s0) (здесь Zmax = max Z)

б) по цепочке

,

оптимальное управление: Х* =(Х1*, Х2*, …, Хn*).

8.5. Двумерная модель распределения ресурсов

Рассмотрим работу схемы на примере. В качестве примера приведем задачу об оптимальном распределении ресурсов между двумя отраслями (между фирмами, хозяйствующими субъектами) на n лет.

Предположим, что планируется деятельность двух отраслей производства на n лет. Начальные ресурсы s0. Средства х, вложенные в первую отрасль в начале года, дают в конце года прибыль f1(x) и возвращаются в размере q1(x)<x; аналогично для второй отрасли: функция прибыли равна f2(x), а возвратаq2(x) (q2(x)<x).

В конце года все возвращенные средства заново перераспределяются между первой и второй отраслями, новые средства не поступают, прибыль в производство не вкладывается

(последние условия приняты с целью упрощения метода, в случае, если поступают новые средства или часть прибыли вкладывается в производство, задача усложняется, однако, алгоритм метода ДП не изменяется).

Требуется распределить имеющиеся средства s0 между двумя отраслями производства на n лет так, чтобы суммарная прибыль от обеих отраслей за n лет оказалась максимальной.

Пример 72. Приведем решение задачи методом ДП при условии, что s0 = 10000 ед., n = 4, f1(x)= 0.6x, q1(x) = 0.7x, f2(x) = 0.5x, q2(x) = 0.8x.

Решение. Процесс распределения средств между двумя отраслями производства разворачивается во времени, решения принимаются в начале каждого года, следовательно, деление на шаги можно сделать следующим образом: номер шага – номер года. Управляемая система – две отрасли производства, а управление состоит в выделении средств каждой отрасли в очередном году.

Параметры состояния к началу k-го года – sk-1 (k = 1, 2, …, n) – количество средств, подлежащих распределению. Переменных управления на каждом шаге две: xk – количество средств, выделенных первой отрасли. Но так как все средства sk-1  распределяются, то yk = sk-1-xk, и поэтому управление на k-м шаге зависит от  одной переменной xk, т.е. Xk(xk, sk-1-xk).

1) Уравнения состояний: sk = q1(xk) + q2(sk-1xk) выражают остаток средств, возвращенных в конце k-го года.

2) Показатель эффективности k-го шага – прибыль, полученная в конце k-го года от обеих отраслей: f1(xk) + f2(sk-1xk).

1)        Суммарный показатель эффективности – целевая функция задачи – прибыль за n лет:



4) Пусть Zk*(sk-1) – условная оптимальная прибыль за n-k+1 лет, начиная с k-го года включительно, при условии, что имеющиеся на начало k-го года средства sk-1 в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за n лет:

Zmax = Z1*(s0).

5) Уравнения Беллмана имеют вид:



Проведем расчет для конкретных данных.

Уравнение состояний примет вид: sk = 0.7xk+0.8(sk-1-xk) или sk = 0.8sk-1-0.1xk.

Целевая функция k-го шага: 0.6xk+0.5(sk-1-xk)=0.1xk+0.5sk-1.

Целевая функция задачи:

Функциональные уравнения (уравнения Беллмана):



Далее проводим условную оптимизацию.

4-й шаг. Используем уравнение (*). Обозначим через Z4 функцию, стоящую в скобках, Z4 = 0.1x4+0.5s3; функция Z4 – линейная возрастающая, так как угловой коэффициент 0,1 больше нуля. Поэтому максимум достигается на конце интервала [0, s3] (рис. 42).







Следовательно, Z4*(s3) = 0.6s3 при X4*(s3) = s3.

3-й шаг. Уравнение



Находим s3 из уравнений состояний: s3 = 0.8s2-0.1x3 и, подставив его выражение в правую часть уравнения, получаем:



Как и в предыдущем случае, максимум достигается при  x3 = s2; т. е. Z3*(s2)=1.02s2 при X3*(s2) = s2.

2-й шаг. Из уравнения состояний: s2 = 0.8s1-0.1x2, поэтому первое функциональное уравнение при k=2 примет вид:



Линейная относительно x2 функция Z2* = 1.31s1-0.002x2 убывает на отрезке [0, s1], и поэтому ее максимум достигается при х2 = 0 (рис. 43).

 













При этом: Z2*(s1) = 1.316s1, при X2*(s1) = 0.

1-й шаг. s1 = 0.8s0-0.1x1. Первое функциональное уравнение при k=1 имеет вид:



Как и в предыдущем случае, максимум достигается в начале отрезка, т.е.: Z1*(s0)=1.5528s0 при X1*(s1)=0.

На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получаем:

Zmax = Z1*(10000), Zmax = 15528.

Далее:

X1* = 0, Y1* = s0 = 10000

(все средства выделяются второй отрасли) 

s1* = 0.810000-0.10 = 8000 X2* = 0, Y2* = s1 = 8000

(все средства выделяются второй отрасли) 

s2* = 0.88000-0.10 = 6400 X3* = 6400, Y3* = 0

(все средства выделяются первой отрасли) 

s3* = 0.86400-0.16400 = 4480 X4* = 4480, Y4* = 0

(все средства выделяются первой отрасли).

Оптимальная прибыль за 4 года, полученная от двух отраслей производства при начальных средствах 10000 ед., равна 15528 ед. при  условии, что первая отрасль получает по годам (0; 0; 6400; 4480), а вторая отрасль соответственно (10000; 8000; 0; 0).
1   ...   4   5   6   7   8   9   10   11   12


Теорема 4. Необходимые условия оптимальности
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации