pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

В соответствии со схемой динамического программирования следу­ ет разбить процесс на этапы, или шаги, и выделить соответствующие со­ стояния системы. Последнее, л-е, состояние, естественно, должно соответ­ ствовать попаданию в точку М. Рассмотрим в качестве предпоследнего, (п - 1)-го, состояния попадание в один из тех пунктов, откуда можно прий­ ти в пункт М только за один переход, причем отсутствуют маршруты, по­ зволяющие сделать это за два или более переходов. Очевидно, таким усло­ виям удовлетворяют пункты Д К, но не пункт И, так как для него, кроме маршрута Я - Муесть еще путь И - К - М , состоящий из двух переходов. С состоянием (п - 2) поставим в соответствие пункты, для которых наиболь­ шее число переходов до пункта М равно двум, с состоянием (п - 3) - пунк­ ты с наибольшим числом переходов, равным трем и т. д. Тогда состоянию (п - 2) соответствует только один пункт И; состоянию (п - 3) - пункты Г и 3; состоянию (п - 4) - пункты В и Е; состоянию (п - 5) - пункты Б иД. Со­ стоянию (п - 6) соответствует только начальный пункт А. Начальное со­ стояние обычно считается нулевым, поэтому число состояний в данной за­ даче равно п = 6.

Таким образом, пункты маршрута приведены в соответствие со­ стояниям системы следующим образом:

Сначала решаем задачу для последнего, шестого, шага. Здесь оты­ скиваются оптимальные участки маршрута от пунктов, соответствующих пятому состоянию, т. е. JI и К, до пункта М. Оптимальное управление со­ стоит в выборе кратчайшего маршрута. На данном шаге выбора нет: каж­ дый из пунктов JIylK соединен с пунктом М только одним переходом, ко­ торый и будет условным оптимальным управлением. На рис. 5.2 маршрут, соответствующий условному оптимальному управлению, выделен двойной линией. Критерий оптимальности всей задачи - это минимум суммарной длины маршрута. Значения целевой функции на данном последнем шаге - это просто расстояния от пунктов Я и А’ до пункта М Эти числа записаны в рамках рядом с соответствующими пунктами.

Перейдем к оптимизации предпоследнего, пятого, шага. Здесь рас­ сматривается только пункт И. Кратчайший из двух маршрутов от него до пункта М - это путь в один переход И - М9длина которого равна 4 ед. На четвертом шаге анализируем маршруты из пунктов Г и 3. Для пункта Г есть два варианта окончания маршрута: первый - через пункт Д второй - через пункт И. Для отыскания лучшего варианта надо сравнить длины этих фрагментов, предполагая, что при попадании в пункт Л или И дальнейшее движение происходит по оптимальному маршруту (пользуемся принципом оптимальности).

Это окончание маршрута нам уже известно по результатам оп­ тимизации последнего шага. Поэтому для определения длины каждого участка маршрута из пункта Г достаточно сложить длину первого перехода из этого пункта с числом, стоящим над пунктом, которым данный переход оканчивается. Так, длина участка маршрута от пункта Г до М через пункт Л равна 6 + 5 = 11, а через пункт Я равна 5 + 4 = 9. Кратчайшим, следова­ тельно, будет путь через пункт И. Поэтому участок Г - И выделяем двой­ ной линией, а над пунктом /"проставляем число 9 - оптимальное расстояние от него до пункта М. Теперь уже, каким бы путем мы ни попали в пункт Г\ оптимальное окончание маршрута нами получено: это путь Г - И - М. Аналогичным образом из двух вариантов маршрутов из точки 3 оптимален путь через пункт И. Соответствующее расстояние до точки М равно 6. Та­ ким же способом оптимизируются третий и второй шаги. Найденные оп­ тимальные маршруты и соответствующие расстояния приведены на рис. 5.2.

Отметим, что при выборе маршрута из пункта Д можно принять любое решение: длина пути через пункт Е и через пункт И оказалась оди­ наковой и равной 11:2 + 9 = 7 + 4. Для определенности на рис. 5.2 изобра­ жен первый вариант. То же можно сказать о пункте Б, где из трех возмож­ ных путей два оказываются одинаково эффективными. Остается 1-й шаг, на котором предстоит выбрать одно из четырех возможных направлений движения из пункта А. Для этого сравниваем длины маршрутов из А через

Б, В ,Д иЕ . Они равны, соответственно, 4 + 13 = 17; 6 + 11 = 17; 6 + 11 = 17; 7 + 9= 16 . Длина последнего маршрута оказалась минимальной. Поэтому из пункта А следует перейти в пункт Е и далее, выбирая каждый раз най­ денный ранее оптимальный путь. Таким образом, кратчайший маршрут длиной 16 единиц проходит через пункты А, Е,3, И, М.

На этом же примере легко показать, что попытка оптимизировать каждый шаг в отдельности не приводит к получению оптимального реше­ ния задачи. В самом деле, действуя таким образом, ъ е. отыскивая на каж­ дом шаге переход минимальной длины, мы на 1-м шаге придем из пункта А в Б, на 2-м - из Б в В и далее по маршруту Г - И - М. Длина всего пути составит 18 единиц - хуже, чем в оптимальном решении.

5.1.5.Задача распределения ресурсов

Вкачестве примера задачи распределения ресурсов рассмотрим один из вариантов задачи о реконструкции.

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

ли F ., которую получило бы каждое предприятие после реконструкции, в

зависимости от объема х вложенных средств.

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

Для удобства деления на этапы будем условно предполагать, что процесс реконструкции происходит последовательно: на первом этапе вы­ деляются средства на реконструкцию первого предприятия; на втором эта­ пе - на реконструкцию второго и т. д. Номер этапа, таким образом, соот­ ветствует номеру предприятия, для которого выделяются средства. Управ­ лением на каждом шаге является объем ^.средств, выделенных на рекон­

струкцию /-го предприятия, i = 1,2, 3, 4.

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

приятия вкладываются все оставшиеся средства, то есть и\ = х (вторая гра­ фа табл. 5.2). Величина условного оптимального выигрыша на этом этапе, которую мы обозначим W4 (x), будет равна соответствующему значению прибыли четвертого предприятия: W4 (x) = F4(x). Теперь можно заполнить

третью графу табл. 5.2. В ней переписаны значения прибыли четвертого предприятия из 5-й графы табл. 5.1.

Перейдем к оптимизации предыдущего, третьего, шага. Пусть к на­ чалу его объем средств равен х. Это средства, выделенные на реконструк­ цию третьего и четвертого предприятий. Если для третьего предприятия решено выделить и3 единиц, то для четвертого останется (х - и3). Поэтому

Последнее слагаемое - это выигрыш на четвертом этапе. Руково­ дствуясь принципом оптимальности, следует искать такое управление на третьем шаге, которое обратит в максимум выигрыш на третьем шаге в сумме с максимальным выигрышем на четвертом шаге, т. е. величину

F 3(u 3) + W 4' ( x - u 3).

В результате будет получен максимальный условный выигрыш на

двух последних шагах. Эту величину обозначим через 1V3 (x). Таким обра­

зом,

Чтобы найти W* (x), приходится перебрать все возможные значения

управления и3 на третьем шаге при различных количествах средств д:, вло­

женных к началу данного шага. Эти величины приведены в первой и второй графах табл. 5.3. Так, для х = 20 управление и3 может принимать

одно из двух значений: 0 или 20; для х = 40 - одно из трех значений: 0, 20, 40 и т. д. (табл. 5.3, графа 2). Соответствующие значения выигрыша на третьем шаге F3(u3) взяты из четвертой графы табл. 5.1 и переписаны в чет­

вертой графе табл. 5.3. Аргументом величины W4 в (5.2) является выраже­

ние ( х - и 3). Его значения для различных и3 приведены в третьей графе табл. 5.3. Соответствующие значения W*( х - и 3) взяты из третьей графы

табл. 5.2 и вписаны в пятой графе табл. 5.3. Например, для х = 20 и и3 =0

Т а б л и ц а 5.3

Объем расчетов здесь уменьшается, так как к началу первого шага нам известно количество выделенных средств х: оно равно 100. Следова­ тельно, вычисления достаточно выполнить только для этого *. По завер­

шении расчетов оказалось (графы 8 и 9 табл. 5.2), что оптимальное управ-

*

ление на первом шаге равно щ =40. Найденное значение является уже

безусловным оптимальным управлением, поскольку оно обеспечивает максимум суммарной прибыли на всех шагах. Величина этого максимума оказалась равной Wx =26.

Последняя стадия расчетов - прохождение процесса, начиная с пер­ вого и до последнего, четвертого, шага с целью отыскания на каждом из них уже не условного, а безусловного оптимального управления. На пер­ вом шаге, как уже выяснено, и* =40, т. е. 40 единиц денежных средств

следует выделить первому предприятию. У нас осталось, следовательно, х = 100 - 40 = 60 ед. к началу второго шага, т. е. для финансирования ре­ конструкции всех остальных предприятий. Числу х = 60 на втором шаге соответствует и\ =20 (графа 6 табл. 5.2). Теперь уже это безусловное оп­ тимальное управление. Оставшиеся средства в количестве 60 -20 = 40 единиц предназначены третьему и четвертому предприятиям. Для х = 40 из графы 4 табл. 5.2 получим и\ =20 - столько средств выделяется третьему, а остаток, я: = 40 - 20 = 20, - четвертому предприятию.

Таким образом, оптимальное распределение средств на реконструк­ цию следующее: первому предприятию выделяется 40 ед., второму, треть­ ему и четвертому - по 20 ед. Суммарная прибыль при этом составит 26 ед.

5.2. Формальное описание, основное уравнение и вычислительная схема метода динамического программирования

Для решения практических задач методом динамического програм­ мирования необходимо иметь его формальное описание.

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

Введем обозначения: S( - состояние процесса в конце z-ro этапа;

SQ- начальное, a S„- конечное состояние (см. рис. 5.3). Состояния S0 и Sn

предполагаются известными. Это могут быть точки и области в простран­ стве фазовых переменных.

Ш а г и , 1 , 2 , . . . , * , . . . , " - 1 , w ,

Рис. 5.3. Обозначение состояний процесса и управлений

Процесс является управляемым: состояние его к концу очередного, z-го, шага определяется не только предыдущим состоянием но и вы­

бором вектора управления щ на данном шаге. Это можно записать так:

(5-5)

где f i - обозначение функции.

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

Запишем аналитическое выражение для привдипа оптимальности, сформулированного в п. 5.1.

Обозначим через Wt величину выигрыша, полученного на /-м и на всех последующих шагах процесса. Очевидно, можно записать

где coi - выигрыш, полученный только на z-м шаге. Величина со; зависит

от начального состояния системы на данном шаге St_x и управления Ъ-х на

этом шаге:

®/=®Д 5 , ( 5 . 7 )

Предположим, что на всех этапах, начиная с z-ro, применялось оп­ тимальное управление. Тогда величина Wt обратится в максимум, который

В соответствии с принципом оптимальности управление ui на i-м шаге должно быть выбрано так, чтобы обратить в максимум выигрыш на этом этапе в сумме с условным оптимальным выигрышем на всех осталь­ ных этапах. Таким управлением обеспечивается максимум величины Wt, то есть

W* = max \coi + W*+j}.

Щ

Принимая во внимание выражения (5.7), (5.8) и (5.9), получим

Уравнение (5.10) называется основным функциональным уравне­ нием динамического программирования, или уравнением Веллмана, и

представляет собой математическую запись принципа оптимальности. С

его помощью можно вычислить функцию W* (S/_i), если известна эта же

функция для следующего шага И^*+1 (£,■). Подобные соотношения называ­

ют рекуррентными. Запись основного функционального уравнения в фор­ ме (5.10) является символической. В зависимости от конкретной задачи это уравнение приобретает тот или иной явный вид.

Уравнение (5.10) лежит в основе вычислительной схемы метода ди­ намического программирования. Сначала решают задачу условной оптими­ зации для последнего, «-го, шага, задаваясь различными возможными со­ стояниями системы Sn_} в конце предыдущего шага. Для каждого из этих

состояний определяется условный оптимальный выигрыш из выражения

и условное оптимальное управление на последнем шаге. Это относительно простая задача, так как известно конечное состояние процесса Sn и среди допустимых управлений рассматриваются только те, которые приводят систему в это состояние. Перепишем теперь уравнение (5.10), положив в нем i = п —1:

180

< - , ( 5 п. 2)=шах{й,л. 1(5л. 2)17я. 1)+ < ( ^ . 1(5п. 2, «„_,))}. (5.12)

ип-1

Поскольку значения условного оптимального выигрыша на по­ следнем шаге W*(Sn_l) теперь уже известны, то с помощью уравнения

(5.12) можно выполнить условную оптимизацию для (п - 1)-го шага, за­ даваясь различными возможными состояниями системы к его началу. Аналогичным образом производится условная оптимизация на (п - 2)-м, (п - 3)-м шаге и т. д., вплоть до первого шага. Так как состояние S0 сис­ темы в начале первого шага задано, то на этом шаге сразу отыскивается оптимальный выигрыш Wx(S0) - уже действительный, а не условный. Он

равен оптимальному значению целевой функции по сумме всех этапов процесса. Одновременно определяется оптимальное управление на пер­ вом шаге й\ - уже безусловное.

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

найденное оптимальное управление и*, получим состояние Sx по формуле

(5.5). Для Sx воспользуемся вычисленным выше оптимальным управлени­ ем на втором шаге й2. Оно уже будет выступать в роли безусловного опти­ мального управления на этом шаге. По величинам 5, и й2 найдем S2 и

т. д.

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

1) выбираются параметры, называемые фазовыми координатами, которые характеризуют состояние системы, и принцйп деления всего про­ цесса на отдельные этапы;

2) выбирается вектор управления на каждом шаге й1. Проверяется свойство аддитивности для применяемого критерия оптимальности. Опре­ деляется зависимость целевой функции соi на z-м шаге от состояния систе­ мы в начале этого шага Si_] и вектора й1: (о{ =o)i{Si_l,ui). При этом со­ стояние системы к концу очередного z-ro шага S', и целевая функция на этом шаге должны зависеть только от состояния системы в начале данного шага 5,|-_1 и от управления на этом шаге, но не от того, каким образом, в

результате каких управлений система пришла в состояние ;

3) выясняется, каким образом система переходит из очередного со­ стояния в следующее, т. е. определяется зависимость (5.5);