Условное оптимальное управление
Cтраница 2
Аналогично, пятясь от предпоследнего шага назад, найдем для каждой точки с целочисленными координатами условное оптимальное управление ( с или в), которое обозначим стрелкой, и условный оптимальный выигрыш ( расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним - уже оптимизированы. [16]
 |
Возможные значения х ( и эффективности f ( x. [17] |
Значение х нам неизвестно, так как это то количество ресурсов, которое осталось от условного оптимального управления на предпоследнем ( втором с конца) шаге. [18]
Однако вся процедура динамического программирования может быть для этого случая построена непосредственно: в основу процедуры динамического программирования положен такой выбор условного оптимального управления на каждом шаге, при котором обращается в максимум ( минимум) выигрыш, равный произведению выигрыша на данном шаге и уже оптимизированного выигрыша на всех предыдущих шагах. [19]
Поскольку вначале у нас для всех объектов имеется 5 ед.р., а после выделения ресурсов на один из объектов в соответствии с условным оптимальным управлением на все остальные должны остаться х3 ( х4) 2 ед. [20]
Для динамического программирования характерен следующий прием: процесс перемещения точки в фазовом пространстве разделяется на ряд последовательных этапов и производится последовательная оптимизация каждого из них, начиная с последнего. На каждом этапе находится условное оптимальное управление ( при всевозможных - предположениях о результатах предыдущего шага), а затем, когда процесс доведен до исходного состояния s0, снова проходят всю последовательность шагов, но уже из множества условных оптимальных управлений выбирается одно наилучшее. [21]
Затем мы переходим к выбору предпоследнего шага и делаем возможные предположения о том, чем закончился предпредпоследний шаг. Для каждого предположения выбираем условное оптимальное управление для предпоследнего шага. Постепенно пятясь назад, оптимизируем управление на разных шагах - ив конечном итоге доходим до первого шага. В результате выявляется искомое оптимальное решение; это есть решение, состоящее из тех выборов, какие мы сделали в процессе нашего мысленного перемещения от конца многошаговой операции к ее началу. [22]
Решение задачи динамического программирования с мультипликативным критерием характеризуется тем, что любая такая задача может быть сведена к задаче с аддитивным критерием. При этом обычно непосредственно не логарифмируют w, а заключают в основу решения такой выбор условного оптимального управления на каждом шаге, при котором выигрыш на всех оставшихся шагах обращается в максимум. Этот выигрыш равен произведению выигрыша на данном шаге и оптимизированного выигрыша на всех последующих шагах. [23]
На первом этапе при движении от начала 5-го года пятилетки к началу 1 -го года для каждого допустимого состояния оборудования найдем условное оптимальное управление ( решение), а на втором этапе при движении от начала 1-го года пятилетки к началу 5-го года из условных оптимальных решений для каждого года составим оптимальный план замены оборудования на пятилетку. [24]
Процесс решения при этом складывается из двух этапов. На первом он ведется с конца: для каждого из различных предположений о том, чем кончился предпоследний шаг, находится условное оптимальное управление на последнем шаге, т.е. управление, которое надо применить, если предпоследний шаг закончился определенным образом. [25]
Это будут гипотезы о состоянии машины после ( т - 1) - го шага, для каждой из которых мы должны найти условное оптимальное управление на m - м шаге. На рис. 4.2 эти возможные положений отмочены кружком с точкой внутри. [26]
Внимательный читатель, вероятно, заметил, что в нашей задаче точки А и В ( начало п конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные - в обратном направлении. Действительно, это так: в любой задаче динамического программирования начало и конец можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на уже сложившиеся условия к началу данного шага, чем тга те, которые еще предстоят после этого шага. По существу же оба подхода совершенно равносильны. [27]
Внимательный читатель, вероятно, заметил, что в нашей задаче точки А и В ( начало и конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные - в обратном направлении. Действительно, это так: в любой задаче динамического программирования начало и конец можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на уже сложившиеся условия к началу данного шага, чем на те, которые еще предстоят после этого шага. По существу же оба подхода совершенно равносильны. [28]
Для динамического программирования характерен следующий прием: процесс перемещения точки в фазовом пространстве разделяется на ряд последовательных этапов и производится последовательная оптимизация каждого из них, начиная с последнего. На каждом этапе находится условное оптимальное управление ( при всевозможных - предположениях о результатах предыдущего шага), а затем, когда процесс доведен до исходного состояния s0, снова проходят всю последовательность шагов, но уже из множества условных оптимальных управлений выбирается одно наилучшее. [29]
Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств S, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по таблице 13.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца ( учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум - условный оптимальный выигрыш. [30]
Страницы: 1 2 3