WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 11 |

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

Рассматриваемый многостадийный процесс условно изображается схемой, изображенной на рис. 5.1.

u1 u2 u um-1 um ym-1 ym y0 y1 2 y2 ym-2 m-1 m … y-1 y … Рис. 5.1 Многостадийный процесс Краеугольным камнем метода динамического программирования является принцип оптимальности:

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

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

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

5.2 МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ.

ФУНКЦИОНАЛЬНОЕ УРАВНЕНИЕ БЕЛЛМАНА Как уже говорилось, математическое описание процесса известно.

Пусть состояние системы на каждой стадии описывается уравнением y = f (y-1, u ), (5.1) где y-1, y – переменные состояния – 1 и стадий соответственно, u – управление на -й стадии.

Уравнение (5.1) связывает выходные переменные стадии с выходными переменными предыдущей стадии y-1 и управлением u, используемым на этой стадии.

На переменные состояния и управляющие воздействия могут быть наложены ограничения, выражающиеся в виде равенств или неравенств Fj (y1,..., ym, u1,..., um) 0, j = 1, J. (5.2) Кроме того, используется запись y Y, u U (5.3) смысл которой заключается в том, что переменные принадлежат к допустимым областям, ограниченным соотношениями (5.2).

Эффективность каждой стадии процесса оценивается скалярной величиной Q (y, u), которая называется функцией полезности – критерием оптимальности Q = Q(y, u), (5.4, а) с учетом (5,1) функциональная зависимость (5.4, а) может быть представлена как Q= Q(y–1, u). (5.4, б) Результирующая оценка эффективности многостадийного процесса в целом определяется как аддитивная функция результатов, получаемых на каждой стадии m Q = (y-1, u ). (5.5) Q -Естественно, что критерий оптимальности Q зависит от совокупности управляющих воздействий на всех стадиях процесса (u1, u2,..., um).

Таким образом, задачу оптимизации многостадийного процесса можно сформулировать как задачу отыскания оптимальной стратегии uопт = (u1опт, u2опт,..., umопт ), для которой критерий оптимальности Q принимает максимальное или минимальное значение.

Процедура применения принципа оптимальности для оптимизации m-стадийного процесса должна начинаться с последней стадии, для которой не существует последующих стадий, могущих повлиять на выбор управления um опт на этой стадии. После этого приступают к определению оптимального управления для предыдущей m – 1 стадии, для которой оптимальная стратегия на последующих стадиях, т.е. на последней m-й известна и т.д. В результате может быть найдена оптимальная стратегия управления для всего многостадийного процесса, являющаяся функцией начального состояния процесса um (y0).

При применении любой стратегии управления величина критерия оптимальности Q зависит только от состояния входа первой стадии у0 Q = Q(y0).

Пусть оптимальное значение целевой функции (для определенности минимальное) на участке от m до m будет B (y-1), и оно зависит от состояния на – 1 стадии m m B (y-1) = min (y-1, u). (5.6) Q u,...,um = Соответственно Bm(y0) = min Q(y0), (5.7) uU =1, m здесь оптимизация проводится по всем возможным управлениям, принадлежащим области допустимых значений U, на всех стадиях процесса. Соотношение (5.7) по существу является математической формулировкой задачи оптимизации m-стадийного процесса, но не содержит указаний как нужно минимизировать критерий Q, чтобы получить оптимальную стратегию uопт = (u1опт, u2опт,..., um опт ).

Так как Q является аддитивной функцией критериев оптимальности отдельных стадий, то его можно представить в виде Q(y0)= Q1(y0, u1)+ Qm-1(y1), (5.8) тогда (5.7) перепишется в виде Bm(y0) = min [Q1(y0, u1) + Qm-1(y1)]. (5.9) u U =1,m Выражение (5.9) может быть также переписано в виде Bm(y0) = min Q1(y0,u1)+ min Qm-1(y1), (5.10) u U u1U &=&2, m & где минимизация первого слагаемого Q1 (y0, u1) проводится только по управлению u1, а второе минимизируется выбором управлений на всех стадиях, причем каждое слагаемое в (5.10) нельзя минимизировать в отдельности, так как они оба зависят от u1.

Минимизацию второго слагаемого в (5.10) можно рассматривать как задачу оптимизации (m – 1) стадийного процесса с критерием оптимальности Qm-1(y1) и оптимальной стратегией um-1опт = (u2опт, u3опт,..., umопт). Таким образом, можно записать, что Bm-1(y1) = min Qm-1(y1). (5.11) u U =2, m Выражение (5.9) с учетом (5.11) может быть представлено в виде Bm(y0) = min [Q1(y0, u1)+ Bm-1(y1)]. (5.12) u1U Если математическое описание первой стадии y1 = f1(y0, u1), то Bm(y0) = min [Q1(y0, u1)+ Bm-1[ f (y0, u1)]]. (5.13) u1U Последнее уравнение является математической формулировкой принципа оптимальности и называется рекуррентным соотношением Беллмана.



Для начала расчетов необходимо задать начальную функцию f0 (ym), которая может быть принята равной нулю, что естественным образом соответствует отсутствию процесса за пределами последней стадии.

Уравнение (5.13) можно трактовать как оптимальные потери, причем Q1(y0, u1) – потери на первом участке, а Bm–1 – оптимальные потери на всех последующих участках. Минимизируя сумму этих потерь, необходимо найти правильное соотношение между ними.

5.3 ОБЩАЯ ПРОЦЕДУРА РЕШЕНИЯ ЗАДАЧ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Согласно общему подходу к решению задач методом динамического программирования определение оптимальных управлений начинается с последней стадии процесса, для которой рекуррентное соотношение Беллмана с учетом, что B0 (ym) = 0, записывается в виде B1(ym-1) = min Qm(ym-1, um ). (5.14) um U Для этой стадии можно построить зависимость целевой функции Qm от управления um для различных значений переменной состояния ym–1 (рис. 5.2).

Эта зависимость позволяет найти зависимость оптимального управления на последней стадии um опт от входной переменной этой стадии ym–1 (рис. 5.3).

Qm ym-ym-BBu1 um um mопт опт Рис. 5.2 Зависимость Qm от um um опт um опт umопт y1 ym- ym-m-Рис. 5.3 Зависимость оптимального управления um от входной переменной ym-Одновременно определяется минимальное значение целевой функции B1 данной стадии от ее входа, т.е. ym–1 (рис. 5.4).

Таким образом можно получить зависимости оптимального управления на m-й стадии от входной переменной этой стадии umопт = um(ym-1), а также критерия оптимальности на этой m-й стадии от ее входа B1 = B1(ym-1). Кроме того, можно определить зависимость выходной переменной при оптимальном управлении от входной переменной ymопт = ym(ym-1) (рис. 5.5).

BBBy1 ym- ym-m-Рис. 5.4 Зависимость B1 от ym–ym опт ym опт ymопт y1 ym-1 ym-m-Рис. 5.5 Зависимость ym от ym-опт Для определения оптимального управления um–1 на (m – 1)-й стадии из всех полученных результатов необходима зависимость B1(ym–1), с учетом которой рекуррентное соотношение для (m – 1)-й стадии записывается как B2(ym-2) = min {Qm-1 (ym-2, um-1)+ B1[ fm-1(ym-2, um-1)]}. (5.15) um-1U Далее необходимо построить зависимость (Qm-1 + B1) от управления um–1 для различных значений ym–2 переменных состояний входа (m – 1) стадии (рис. 5.6).

Qm-1 + Bym-ym-BBu1 um-1 um–m-1опт опт Рис. 5.6 Зависимость (Qm–1 + B1) от um–um-1опт um-опт um-1опт y1 ym-1 ym–m-Рис. 5.7 Зависимость оптимального управления от входа ym–2 на (m – 1) стадии Также как и для m-й стадии в результате минимального значения выражения (5.15) находятся зависимости um-1опт = um-1(ym-2), B2 = B2(ym-2 ), а также ym-1опт = ym-1(ym-2), которые представлены соответственно на рис. 5.7, 5.8, 5.9.

BBBy1 ym- ym–m-Рис. 5.8 Зависимость B2 от ym–ym-опт ym-опт ym-1опт y1 ym-2 ym–m-Рис. 5.9 Зависимость ym -1опт от ym–Далее появляется возможность записать рекуррентные соотношения на (m – 2) стадии, и т.д. Продолжая процесс вычислений можно дойти до первой стадии, для которой также будут получены соотношения u1опт = u1(y0), Bm= Bm(y0), y1опт = y1(y0). Возможный вид кривых для них представлен на рис. 5.10 – 5.13.

Q1 + Bm-yBm yBm 1 uu1 uопт опт Рис. 5.10 Зависимость (Q1 + Bm-1) от uuопт uопт buопт ay1 y yРис. 5.11 Зависимость оптимального управления u1опт от входа на 1-й стадии На этом первый этап решения задачи оптимизации многостадийного процесса заканчивается. Полученные соотношения определяют оптимальную стратегию управления m-стадийного процесса для любого возможного состояния входа первой стадии.

Bm Bm Bm ay1 y0 yРис. 5.12 Зависимость Bm от yНа втором этапе решения оптимальной задачи находятся оптимальные управления всех стадий u, = 1, m, для чего необходимо принять соответствующее значение состояния входа y0. В том случае, если оно в постановке задачи не задано, его можно определить из условия минимума величины Bm как функции значения y0 (рис. 5.12). В рассмотренном случае зависимость Bm от y0 имеет минимум, что позволяет найти оптимальное значение состояния входа y0 = a0. Минимальное значение Bm может достигаться и на концах.

После определения переменной состояния входа из условия минимума функции Bm(y0), преступают к определению оптимальных управлений для всех стадий процесса, соответствующих выбранной величине y0 = a0 (рис. 5.12). Вторым этапом решения задачи оптимального управления методом динамического программирования является определение оптимальных управлений для всех стадий. Здесь порядок расчета следующий.

Определяется оптимальное управление на первой стадии (рис. 5.11) u1опт = b1 и значение выходной переменной этой стадии y1опт = a(рис. 5.13), отвечающее оптимальному управлению. После этого переходят ко второй стадии, и вся процедура повторяется и т.д. В результате решения задачи доходят до последней m-й стадии и имеют значения uVопт для всей рассматриваемой задачи по стадиям.

yопт y1опт ay1опт ay1 y0 yРис. 5.13 Зависимость y1опт от yДинамическое программирование является одним из методов решения задач оптимизации при принятии решений. Основные преимущества этого метода: прежде всего, он позволяет найти глобальное оптимальное решение; оптимизация ведется по одной переменной; рекуррентная формула (уравнение) Беллмана удобна для программирования. Ограничением метода является размерность задачи, так как приходится хранить результаты оптимизации всех этапов. Но гораздо более серьезные затруднения возникают при применении метода динамического программирования для оптимизации многостадийных процессов, для которых размерности векторов состояния y и управления u0 велики, из-за сложности отыскания оптимальных управлений на каждой стадии. Поэтому следует стремиться, чтобы размерность стадии оптимизируемого объекта была по возможности невысокой.





5.4 ЗАДАЧИ, РЕШАЕМЫЕ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 5.4.1 Задача распределения ресурсов Пусть имеется некоторое количество экономических ресурсов. Под термином ресурсы подразумеваются люди, деньги, машины, материалы для технологических процессов, вода для сельскохозяйственных и промышленных целей, топливо и т.д. Эти ресурсы потребляются различными способами, в результате чего получают некоторой доход, размер которого зависит от употребленного количества ресурсов и от выбранного процесса распределения.

Задача заключается в распределении ресурсов таким образом, чтобы максимизировать общий доход при следующих условиях: доходы, полученные от различных процессов измеряются общей единицей;

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

Математическая формулировка задачи следующая.

Пусть имеется N различных процессов ( = 1, 2,..., N), каждому из которых соответствует функция полезности – целевая функция (доход) Q, зависящая от количества выделенных ресурсов u. Общий N доход определяется аддитивной функцией Q(u1,..., uN ) = (u ), на количество ресурсов наложены огQ =раничения, что общее их количество не должно превышать заданного u1 + u2 +...+ uN = u, где u 0.

Требуется максимизировать целевую функцию Q (u1,..., uN) при u, удовлетворяющих соответствующим ограничениям.

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

Если u – число отдельных предметов -го типа, V – вес отдельного предмета -го типа), С – стоимость отдельного предмета -го типа, z – максимальная грузоподъемность судна, N – количество различ- ных типов, тогда ценность груза определяется линейной N формой Q(u) = C и ограничение по грузоподъемности имеет u =N вид uU z.

=Требуется максимизировать целевую функцию Q (u) при ограничении на грузоподъемность и условиях C 0, V 0, u = 0, 1, 2,...

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

5.4.2 Транспортная задача В математической экономике большое значение имеет задача наиболее эффективного перемещения ресурсов из одного пункта в другой. Это, так называемая, транспортная задача.

Пусть ресурсы сосредоточены на складах = 1, 2,..., m (D), спрос на них имеется в пунктах потребления j = 1, 2,..., N (Pj). Для просто- ты рассматривается один вид ресурса, его запасы на -м складе – u, m N спрос на него в j-м пункте потребления – rj. Общий запас равен общему спросу =.

u rj =1 j=Количество ресурсов, отправляемые из -го склада в j-й пункт потребления uj, стоимость соответствующей перевозки Qj(uj). Величины uj должны быть неотрицательны, uj 0. Кроме того, вводятся ограничения на запасы; общее количество ресурсов, отправляемое из любого склада, должно равняться N запасам на этом складе = u, = 1, m ; и ограничение на спрос; общее количество ресурсов, отправuj j=m ляемое в любой пункт потребления, должно равняться спросу в этом пункте = rj, j = 1, N.

uj =Таким образом, требуется определить количество перевозимых ресурсов из -го склада в j-й пункт потребления uj, чтобы общая стоимость перевозок QmN = (uj) была минимальна.

Qj, j Эта задача обычно решается методом линейного программирования. Но, если функции стоимости Qj( u) нелинейные, то эти методы не применимы, и задача может быть решена методом динамического программирования.

Пусть для простоты имеется два склада = 1, 2, и N пунктов потребления. Величина затрат при использовании оптимальной политики составляет BN (u1, u2) при N = 1, 2,..., u1 0, u2 0.

Удовлетворяя первым спрос в N-м пункте потребления, затраты в нем составят Q1N ( u1N )+ Q2N ( u2N ) и запасы ресурсов на складах уменьшатся до u1 - u1N и u2 - u2N. Согласно принципа оптимальности для N 2 рекуррентное соотношение Беллмана записывается в виде BN (u1, u2) = min{Q1N (u1N )+ Q2N (u2N )+ BN -1(u1-u1N, u2-u2N )}, uU где U – область, определенная условиями u1N + u2N = rN, 0 u1N u1, 0 u2N u2.

Для N = 1 будет B1(u1, u2) = Q11( u1)+ Q21( u2).

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

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

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.