XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 59
Текст из файла (страница 59)
При определении условного оптимального управления на (п — 1)-м шаге необходимо исходить из всех возможных вариантов завершения (и — 2)-го шага и для каждого иэ них найти такое управление, чтобы выигрыш (в смысле значения целевой функции) от его применения за последние два шага (из которых последний уже полностью определен) был бы максимально возможным. Затем переходят к определению условного оптимального управления на (и — 2)-м шаге и т.д. В результате проведенных рассуждений мы пришли ко второй формулировке принципа оптимальности в дискретном динамическом программировании, который больше известен нан принцип оптимальности Беллмана: каково бы ни было состояние динамической системы в результате реализации какого-то числа шагов, управление на ближайшем шаге нужно выбирать так, чтобы оно, в совокупности с оптимальным управлением на всех последующих шагах, привело к максимально возможному выигрышу на всех оставшихся шагах, включая данный.
На практике при применении в дискретном динамическом программировании принципа оптимальности используют прием, называемый мепзодом поеруженил. Он состоит в том, что вместо решения одной исходной задачи с заданным начальным состоянием Яо и известным числом шагов решают совокупность однотипных задач, различающихся начальным состоянием. Так, в примере П2.2 в процессе решения последовательно находят кратчайшие пути от первого узла сети, до каждого из оставшихся узлов. Исходная задача (поиск кратчайшего пути от узла 1 до узла 9) представляет собой последнюю из восьми однотипных задач.
В примере П2.4 состояние описывается парой (Й,у), а пара (1, а) соответствует начальному состоянию. Реализация рассматриваемого принципа оптимальности приводит к появлению специфических функциональных уравнений, методы решения которых и составляют основу вычислительных схем динамического программирования. В примерах П2.1 и П2.4 такими функциональными уравнениями являлись уравнения (П2.1) и (П2.4). Если известны условные оптимальные управления для каждого шага процесса изменения состояния некоторой динамической фстемы, то можно найти и безусловные опяпимальные управления, т.е. решение рассматриваемой задачи. Действительно, пусть известно начальное состояние Яо изучаемой системы.
Но для первого шага известно условное оптимальное управление, связанное с начальным состоянием Яо. В результате реализации этого управления после первого шага система перейдет в другое состояние Я1. Но для второго шага известно условное оптимальное управление, связанное с состоянием 51 и т.д. Таким образом, при реализации метода дискретного динамического программирования многошаговую процедуру принятия решений повторяют дважды: первый раз — „от конца к началу" и находят- условные оптимальные управления 421 Таблица ПЕ.1 Рис. П2.9 420 ПРИЛОЖЕНИЕ 2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ на каждом шаге; второй раз — „от начала к концу" и находят безусловные оптимальные управления на каждом шаге.
В заключение отметим, что при реализации метода дискретного динамического программирования многошаговую процедуру принятия решений можно сразу проводить „от начала к концу" и определять безусловные оптимальные управления, В вычислительном аспекте зта схема ничуть не хуже предложенной выше, но в смысле удобства описания и „прозрачности" для понимания уступает ей. Для иллюстрации возможностей метода дискретного динамического программирования рассмотрим задачу о распределении капиталовложений. Пример П2.5. Руководство фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях А1, Аз и Аз. Каждое предприятие представило на рассмотрение различные проекты наращивания своих производственных мощностей, реализацию каждого из которых характеризуют величины 1в условных денежных единицах) суммарных затрат С и суммарных доходов И (табл.
П2.1). Возможность отказа фирмы от наращивания производственных мощностей учтена проектом, для которого С = О и Л = О. Для расширения производства на всех трех предприятиях фирма выделяет средства в объеме 5 условных денежных единиц. Их нужно распределить между предприятиями так, чтобы с учетом представленных проектов получить максимальный доход от инвестиций.
В рассматриваемой задаче каждому из предприятий А1, Аз, Аз ставим в соответствие этап многошаговой процедуры принятия решений 1распределение инвестиций или капиталовложений), поскольку нужно выбрать оптимальный проект для каждого из них. Номер этапа у будет соответствовать предприятию А, у = 1, 3. Пусть далее у1 — объем капиталовложений, распределяемых на этапах 1, 2, 3; уз — объем капиталовложений, распределяемых на этапах 2 и 3; уз — объем капиталовложений, распределяемых на этапе 3. Понятно, что конкретные значения 92 и уз не известны, но известно, что уз, уз б 10, 1, ..., 51.
Значение же у1 равно суммарному объему капиталовложений, распределенных на всех трех этапах, т.е. равно 5, На рис. П2.9 представлена ациклическая сеть, соответствующая рассматриваемой задаче. Конечный этап (у' = 4) введен в рассмотрение для удобства вычислений. Каждому возможному значению у1, уз, уз поставлен в соответствие узел сети, ассоциированный с одним из этапов. Длины ориентированных дуг, соединяющих узлы на этапе у + 1 с узлами на этапе у', числен- Этап 1 Этап 2 Этап 3 Этап 4 91 ит Уз 422 ПРИЛОЖЕНИЕ 2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 423 но равны. доходам от реализации наилучшего допустимого (в смысле объема капиталовложений) проекта. В узлах сети проставлены возможные значения уг, уг и уз Это сделано лишь для удобства построения сети и никоим образом не связано с нумерацией ее узлов. Рассмотрим ориентированные дуги, соединяющие узел 0 на этапе 4 с узлами на этапе 3.
Дуга (О, 0) соответствует случаю, когда капиталовложения на этапе 3 отсутствуют, т.е. допустимым является проект с номером 1 и Вз = О. Поэтому дуге (О, 0) соответствует длина, равная нулю. Дуга (О, 1) соответствует единичному объему капиталовложений на этапе 3, и оба заявленных проекта с номерами 1 и 2 являются допустимыми. Но (см. табл.
П2.1) доход от реализации второго проекта Вз = 3 больше дохода от реализации первого проекта Вз = О. Таким образом, более предпочтительным является второй проект и дуге (О, 1) соответствует длина, равная 3. Рассуждая аналогичным образом и учитывая тот факт, что предприятие Аз представило лишь два проекта, приходим к выводу: длина каждой из ориентированных дуг (О, й), й = 2,5, равна 3. Переходя к рассмотрению ориентированных дуг сети, соединяющих ее узлы на этапе 3 с узлами на этапе 2, обращаем внимание на величину уг — уз, значение которой равно объему капиталовложений, распределенных на этапе 2.
Таким образом, ориентированная дуга (уз, уг) является допустимой лишь для тех проектов предприятия Аг, затраты на реализацию которых не превышают уг — уз. Длина дуги (уз, уг) будет равна наибольшему значению Вг для всех таких проектов. В частности, для ориентированной дуги (1, 5) объем капиталовложений, распределенных на этапе 2, равен уг — уз = 5 — 1 = 4, и все проекты, представленные предприятием, являются допустимыми. А так как шах(0, 8, 9, 12) = 12, то эта дуга имеет длину, равную 12.
Для ориентированной дуги (2, 4) объем капиталовложений, распределенных на этапе 2, равен уг — уз = 4 — 2 = 2, и лишь первые два проекта, представленные предприятием Аг, являются допустимыми. А так как п1ах(0, 8) = 8, ориентированная дуга (2, 4) имеет длину, равную 8. Заметим, что при уз > уг ориентированная дуга (уз, уг) не существует, так как объем капиталовложений, распределяемых на этапах 2 и 3, не может быть меньше объема капиталовложений, распределяемых на этапе 3.
Анализируя ациклическую сеть, изображенную на рис. П2.9, видим, что каждая ее ориентированная дуга единственным образом связана с некоторым конкретным проектом, а исходная задача заключается в отыскании самого длинного пути от узла 0 на этапе 4 до узла 5 на этапе 1. Кроме того, нетрудно заметить, что некоторые ориентированные дуги можно отбросить как заведомо неоптимальные, сократив тем самым объем вычислений при поиске оптимального решения.
Так, например, можно исключить ориентированную дугу, соединяющую узел 0 на этапе 3 с узлом 1 на этапе 2, так как уг — уз = 1 — 0 = 1 и эти капиталовложения на этапе 2 не могут принести какой бы то ни было доход (см. табл. П2.1). Однако, чтобы не отвлекаться, мы не будем рассматривать процедуры подобного рода. В принципе можно воспользоваться уже обсуждавшейся процедурой нумерации ациклической сети и решить нсходную задачу с помощью алгоритма нахождения наиболее длинного пути (см. пример П2.3).
Но мы остановимся на методе дискретного динамического программирования, который обычно применяют при решении многошаговых задач в исследовании операций. Пусть й — номер проекта на этапе у. Этот проект будет допустимым на этапе у при заданном значении у, если с (й„) < ( у, где с,(й ) — величина суммарных затрат на реализацию проекта й,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
