Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

4. случая в отдельности, об- щее число случаев, как правило, возрастаег экспоненциально или даже быстрее с роса ом числа измерений. Если, например, общее число всех случаев 2а', мы отнюдь не удваиваем вычислительное время, когда переходим ог М к 2Аг, скорее мы совершенно меняем его порядок. Об этом специально пойдет речь в $ 16. С другой стороны, подобное увеличение времени можег быль только помехой. Потратить на вычисления 100 минут вместо 10 нетрудно, если ответ имеет хоть какое-нибудь значение. Однако необходимость посвятить вычислительному решению 100 часов вместо 10 может поставить перед дилеммой: придерживаться ли данной важной линии исследования или отказаться от нее в пользу направления, допускающего более легкое продвижение.

Сегодня, как никогда раньше з истории науки, характер теоретической постановки стремится идти рука об руку с вычислительной осуществимостью. В. Максимизация по дискретным множес т в а м. Аппарат классического анализа приспособлен к решению задач оптимизации с непрерывным изменением независимых переменных. Вообще разумно использовать этот тип изменения в качестве приближения к реальной действительности. Однако в ряде случаев подобное сглаживание оказы- твядности вает серьезное влияние на точность решения. Один из крайних случаев возникает, когда каждая переменная может принимать только два различных значения, 0 или 1. Обычно посредством того или иного искусного приема непрерывное изменение ввести можно.

Оптимиззция же по дискретным множествам з основном требует новых методов, и в нзстояпгее время много важных классов задач находится целиком вне нашей досягаемости. Г. Недифференцируемые функции 21 аг ~а Как известно, супгествуют Рпупанголгаа функция непрерывные функции, Рис. 5. определенные нз некотором интервале, которые не имеют производной ни в одной точке этого интервала. Конечно, мы не рассчитываем встретить какие-либо функции такой природы в ходе физического исследования.

Всякий раз, когда в нашем воображении явственно возникают эти пугающие призраки, более тщательное изучение всегда показывает, что «патология» появилась вследствие некоторых предположений, лишенных физического смысла. Тем не менее вполне моакно встретить функции, несущие различные несущественные неудоб- Х ства и помехи, такие как Рис. 6.

отсутствие непрерывно- сти в конечном множестве точек или односторонние производные. Ступенчатые функции (Рис. 5) являются простейшими среди них и в качестве аа ковых служат полеаными приближениями более гладких, но гораздо более сложных функциИ. Лругой интересный и полезный класс функций образуют кусочно-линейные функции, задаваемые следующими выражениями (рис. 6); К(х)=щах(а,х+Ьь пах+ Ьь ..., аах+Ьа). (1.14) одномввныв пяоцвсс!! Ряспявдвлвния 1гл. ! Работая с функциями э~ого типа, мы можем брать производные при условии, что мы знаем интересуюший нас интервал.

Если этот факт неизвестен, мы сталкиваемся с многими неприятными чертами задач комбинаторного поиска, уже упоминавшимися ранее. Весьма часто определение места особенностей составляет сушественную часть решения. ', Д. Л и н е й и о с т ь. Трудности противоположного характера сопутствуют задачам, в когорых все встречаю!циеся функции линейны.1 В этом случае ясе производные существуют, но дакж небольшую информацик>, так как а рпоп известно, что экстремумы достигаются в граничных точках области иаменепия. Теория линейных неравенств со своим ответвлением, линейным программированием, специально предназначается для изучения задачи максимизации линейной формы м Ьм= ~ с!х! (1.1б) г=! при условиях х! ~ О и ~ а;х =Ьп 1=1,2,...,М.

у — — ! (1. 16) Этот универсальный инструмент уделав~ незначительное внимание конкретной структуре исследуемого процесса. Поэтому в определенных ситуациях можно надеяться найти гораздо более эффективные методы для решения соогветсгвуюших задач оптимизации, и это действительно так. ~ Е. Устойчивость. Выше мы указали, что классический анализ основывается на непрерывном изменении независимых переменных.

Отсюда следует, по результаты, полученные классический путем, весьма чувствительны к локальным изменениям и, следовательно, к малым ошибкам. Рассмотрим две функции д(х) и Ь(х), показанные на рис. 7 и 8; первая — идеализированная «математическая» функция и вторая — «физическая» функция. Смысл рис.

8 следуюший. Если Ь(х) определяется как результат измерений или вычислений, то ее значение в каждой точке х никогда не равно числу Ь (х), так как обладает рзссеянием значений. Следовательно, если даже мы и станем определять значения Ь1х) с высокой степенью точности, касательное направление в любой данной точке мы будем назначать весьма неохотно. 71 злключениз 1зкпм образом, мы не намерены полагаться нз методы оптимизации, 1ребукнпне дифференцирования.

На самом деле, конечно, мы хотим использовать метод, который гарантирует, что ошибка з ответе будет не боль1пего порядка, чем ошибка в начальных данных. Это и есть то, что мы подразумеваем под устойчгувостью. Рис, 8. Рнс. 7. Исследование устопчизости вычислительных алгоритмов занимает одно из основных мест в современнод теории численного анализа. Это очень труднып путь. Трудности велики, з шстности, оттого, что до сих пор отчетливо не осознаемся ~есная связь вычислительной устойчивости с перзоначальным мауемап ическим выражением физического пропесса.

Гледозазельно, многие численные исследования пеобычапно усложцянутся физически малосодержательными деталями исходной мазеуеатпческоп модели. 7, ЗАКЛЮЧЕНИЕ 11редыдупгие рассуждения приводят нас к заключению, ч~о такой мопгнып аппарат, каким язляеуся математический анализ, не всегда приводит к успеху при рассмотрении задач оптимиазцин. В некоторых случаях он совершенно неприменим, а в других случаях его некритическое применение может дать неверные результаты, Если мы хотим гарзнтировать численное Решение для простои задачи распределения, поставленной зыше, мы должны ззести какне-то новые математические мегоды. Я Р.

Беллннн, С. Дрейфус ОДНОМЕРНЫЕ ПРОЦЕССЫ РАСПРЕДЕЛЕНИЯ [Гл. 1 8. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ Как следует оценивать полезность вычислительной схемы? Одним из подходов является следующий. Пусть требуется повторно произвести вычисления того же самого типа, но для других значений основных параметров. Можем ли мы при этом использовать информацию, полученную от первоначальных вычисления, или же каждыя раз мы должны проделывать все вычисления с самого начала? Если для любого множества параметров нужно выполнить все новые вычисления, чо получение желаемой информации в полном объеме становится краИне дорогостоюцим предприятием.

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

Эта мысль неизменно обитаег в интеллектуальной сфере и обьясняет успех сравнительноп анатомии, сравнительноя филологии, сравнительной религии н т. д. 9, ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Высказанные идеи оформляются явным образом в теории динамического программйрования. Мы начнем с рассмотрения некоторых простых задач для того, чтобы по возможности яснее проиллюстрировать как смысловую, так и вычисли гельную стороны. Как будет показано, метод функциональных уравненип преодолевает все трудности, зафиксированные ранее, по краянея мере в о~ношении одномерных процессов распределения. Почему возникают трудности при рассмотрении более сложных процессов, в чем они состоят и что можно сделать, чтобы их обойти,— всего этого мы коснемся в последующих главах.

Функпнональныв уединения Вместе с тем мы можем ободрить читателя откровенным признанием, что мы никоим образом не преодолеем и не обойдем абсолютно всех возникающих трудностей. Таким образом, имеются достаточно благоприятные возможности для исследования приложения этих новых методов. 10. ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ Для того чтобы исследовать конкретную зздачу максимизации функции й (хн хм ... „х,) = д, (х,) + ля (х,) +...

+ дх (хх) (1.17) в области х,)0, ~', х;=х, мы погружаем ее в некоторое г=! семейство процессов распределения. Вместо рассмотрения одной задачи с данным количеством ресурсов н фиксированным числом процессов мы рассматриваем целое семейство тзких задач, в которых х может принимать любые положительные значения и М может принимать любые целые значения. То, что нз первый взгляд, по-видимому, может показаться саатическим процессом, мы искусственно развертываем во времени, допуская, а в действительности требуя, производить распределения ресурсов в каждую единицу времени.

Сначала какое-то количество ресурсов назначается Х-му процессу, затем (Аг — 1)-му и т. д. Поступая таким образом, мы вводим динамический процесс распределения. Перейдем теперь к аналитическому рассмотрению. Так как максимум )с(хь хм ..., х ,) в указанной области зависит от х и Аг, мы сделаем эту зависимость явной, задав последовательность функций (Г" (х)), определенных для М= 1, 2, ..., х) О, следующим образом: у' (х)=щах)с(хн х„, ..., х,), (1.18) (яД л где х, ~ 0 и ~, 'х; = х.

Характеристики

Список файлов книги