Приведенный пример характерен для структуры задач динамического программирования с конечным числом решений. Как видим, здесь сначала осуществлялся выбор последнего по времени решения, а затем при движении в направлении, обратном течению времени, выбирались все остальные решения, вплоть до исходного (см. Беллмана принцип оптимальности). [c.77]
Имея в виду, что курс предназначен не для специалистов в области исследования операций, а для менеджеров, а также учитывая всегда неизбежный недостаток времени, автор не включил в настоящий курс традиционные для курсов исследования операций вопросы нелинейного и динамического программирования. Основная причина в том, что не существует универсальных компьютерных алгоритмов решения задач нелинейной и многошаговой оптимизации. Использование имеющихся программ и алгоритмов требует более серьезного внимания к деталям модели и алгоритма, чем возможно уделить в настоящем курсе. Вместе с тем собственно концепция условной оптимизации, которая обязательно должна быть усвоена читателем, достаточно хорошо может быть проиллюстрирована примерами линейного (и цело численного) программирования. [c.19]
Более общие выражения могут быть получены при решении задач расплывчатого программирования и -расплывчатого оптимального управления с использованием соответствующих критериев оптимальности [70]. Примеры применения расплывчатого программирования и расплывчатого оптимального управления приведены в 3.3 для решения задач соответственно с помощью метода ветвей и границ (В-1-4) и получения многоэтапного решения с помощью процедуры динамического программирования (В-4-2). [c.75]
Другое направление, связанное с решением рассматриваемой задачи, может быть охарактеризовано как аналитическое. В этом случае целевая функция для решения оптимального количества складов представляет собой так называемую транспортно-производственную задачу, решение которой предполагает использование алгоритма комбинаторного поиска последовательных оценок вариантов [47] или методов динамического программирования. Однако, как и в первом случае, отсутствие примеров расчетов говорит о необходимости дальнейших исследований. [c.398]
Идеи и принципы динамического программирования рассмотрим на простом примере, подобранном так, чтобы основные идеи не загромождались техническими деталями. В связи с этим наша задача будет предельно простой, но за счет некоторых изменений может быть сделана адекватной действительности. [c.368]
Динамическое программирование. В 1 гл. III рассматривался метод динамического программирования, весьма эффективный при изучении многошаговых процессов принятия решений. Тот же метод оказывается полезным и при решении непрерывных задач управления Чтобы показать это, сначала опишем концепцию в целом, а потом проиллюстрируем ее на примере [c.220]
Изложим сущность вычислительного метода динамического программирования на примере задачи оптимизации [c.159]
Одним из важнейших классов задач, для которых применение динамического программирования оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные J P J 2,..., xk,... должны определяться в строгой временной последовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о найме работников (задачу об использовании рабочей силы). [c.170]
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же первое и второе одновременно, характеризуются нелинейными зависимостями. Примерами нелинейных зависимостей могут [c.233]
Процедурная сторона анализа существенно усложняется ввиду множественности вариантов, техника "прямого счета" в этом случае практически неприменима. Наиболее удобный вычислительный аппарат -методы оптимального программирования (отметим, что термин "программирование", заимствованный из западной литературы в результате прямого и не вполне удачного перевода, означает в данном случае "планирование"). Эти методы (линейное, нелинейное, динамическое, выпуклое программирование и др.) достаточно хорошо разработаны в теории, однако на практике в экономических исследованиях относительную известность получило линейное программирование. В частности, рассмотрим общую постановку транспортной задачи как пример выбора оптимального варианта из набора альтернативных. Суть задачи состоит в следующем. [c.10]
Отметим основное отличие данной реализации метода динамического программирования от схемы вычислений 15. Оно связано с использованием интерполяции функции Беллмана F (х1, х ) с узлов сетки. Этим снимается ограничение на шаг сетки в фазовом пространстве типа h=o (t), необходимое в схеме метода Н. Н. Моисеева. Вместе с тем интерполяция является источником определенных ошибок, тем более, что сетки приходится брать сравнительно грубые. Кроме того, используя интерполяцию, неявно предполагают наличие у функции Беллмана таких свойств гладкости, которых может и не быть. Известны простые примеры задач, в которых функция Беллмана разрывна, а наличие разрывов производной может считаться почти общим явлением. Схема вычислений 15 может быть (при h=0 (t2)) обоснована без всяких предположений о свойствах функции Беллмана. Что касается реализации алгоритма на ЭВМ, то в данном случае наибольшие ограничения связаны с ресурсом памяти. Вычисления в [4] тре= буют N таблиц по 30x30 величин, однако при вычислении очередной функции Fn (х1, х2-) в оперативной памяти нужно иметь только две такие таблицы. [c.307]
Ярким примером применения метода динамического программирования на отраслевом уровне может служить решение советскими экономистами задачи по оптимизации производства пластических масс. Программа решения была составлена так, что машина могла выдавать план распределения заданий по выпуску различных видов пластмасс на любой год планового периода. Это дало экономию народному хозяйству, исчисляе-11о мую сотнями миллионов рублен. [c.118]
По поводу только что рассмотренного примера надо сделать два замечания. Во-первых, удалось не только решить поставленную задачу (найти план загрузки самолета грузоподъемностью H =83), но сделать гораздо больше. Из табл. 22—25 могут быть найдены оптимальные планы загрузки для самолетов любой грузоподъемности в пределах до 87, т. е. вместо одной задачи решен целый набор сходных между собой задач. Это характерная черта метода динамического программирования — расширив задачу, мы облегчили ее решение Отметим также, что, поскольку метод носит явно выраженный ал-горифмический характер, он легко реализуется на ЭВМ. [c.94]
Смотреть главы в:
Математические исследования операций в экономике -> Примеры задач динамического программирования