В эти годы американскими математиками С. Джонсоном и Р. Беллманом была сформулирована общая задача календарного планирования. Сущность исследуемой задачи состояла в следующем. Имеется m различных деталей и п различных станков. Требуется найти такую последовательность обработки партий деталей, при которой общее время изготовления всех партий деталей будет наименьшим. При построении календарного графика должны выполняться следующие условия [c.109]
С. Джонсон и Р. Беллман получили и первые результаты. Они предложили аналитические методы решения этой задачи для случая, когда число операций не превышает трех, а число обрабатываемых деталей неограничено. [c.109]
В свое время, известный американский математик, лауреат Нобелевской премии по экономике Ричард Беллман заметил, что современные компьютеры по своей природе наиболее приспособлены для решения задач с начальными условиями (задачи Коши). Такие задачи могут быть решены последовательным получением решения от одного момента времени к другому, начиная с начального условия. В известном смысле, вся современная наука является результатом выдающегося и не всегда явно осознаваемого открытия Ньютона, впервые отделившего законы природы от начальных условий. Можно сказать, что традиционные компьютеры, в которых алгоритм отделен от данных, являются парафразом этого достижения. Из вышесказанного следует, что принципы работы обычных компьютеров оказываются в некотором смысле аналогичными принципам обработки информации именно левым полушарием мозга человека. [c.9]
Беллман Р., Заде Л. Принятие решений в расплывчатых условиях / [c.77]
Беллман Р. Введение в теорию матриц. - М. Наука, 1969. - 368 с. [c.130]
Беллман Р., Заде Л. Принятие решений в расплыв- [c.260]
БЕЛЛМАН Р., ЗАДЕ Л. Принятие решений в расплывчатых условиях I [c.10]
Оптимальным решением задачи (12.28)+(12.31) будем считать такое решение. А , которое согласовано по Парето между экспертами [12.6] и является оптимизирующим по Беллману-Заде [12.7,12.2]. [c.513]
Четкая формализация моделей подобного рода дана Беллманом в терминах динамического программирования [10—12]. Качественные и вычислительные аспекты многоэтапных стохастических задач в жесткой постановке изучены в работах Н. 3. Шора и др. [332, 334, 336]. [c.202]
В принципе, при подходящей конструкции семейства и (t a) таким образом можно получить почти точное решение. Но в [98], при отсутствии информации о решении, семейство и (t а) содержало лишь монотонно убывающие функции, которыми никак нельзя аппроксимировать решение (13) поэтому эффект такого оптимального управления был незначителен (по сравнению с тривиальным выключением). Четкая постановка задачи о выключении как вариационной была дана Р. Беллманом [7] был предложен и алгоритм ее решения, использующий идеи динамического программирования (см. также 18], [9], [4]). В дальнейшем в монографии [4], специально посвященной этой задаче, были опубликованы данные о реализации этой программы. Они заслуживают подробного комментария. Заметим еще, что вычислительная схема [c.304]
Однако фактическая реализация этого алгоритма наталкивается на серьезное препятствие нет никаких оснований ожидать, что все функции Fn будут получены в замкнутой аналитической форме, попытки же заменить функциональные зависимости таблицами (что приводит к дискретному варианту задачи) наталкиваются на препятствие, метко названное Р. Беллманом проклятием размерности при г > 2 задача практически становится непосильной для современных ЭВМ. Однако есть частный случай, когда уравнение (8) тем не менее решается в конечном виде. Это задачи, в которых все функции /"+ / (хп, a Bfl) квадратичны и, если начальное и конечное состояния не фиксированы, хотя бы одна из функций (пусть Фц (XN)) — квадратичная. Кроме того, области G являются полным r-мерным пространством. Этот случай, несмотря на определенную искусственность, может оказаться полезным [c.388]
Беллман Р. Процессы регулирования с адаптацией. — М. Наука, 1964. [c.479]
Затем, следуя Беллману [8], при данном уровне запасов в начале -го периода, можно записать функциональное уравнение для политики обеспечения минимальных затрат в периодах с t-ro по Г-й в виде [c.215]
Беллман Р. Об основах теории стохастических вариационных процессов. — В сб. Гидродинамическая неустойчивость. - М. Мир, 1964, с. 323 - 337. [c.433]
П. Беллман Р., Колоба Р. Динамическое программирование и современная теория [c.433]
Такая концепция, получившая название динамического программирования, была создана американским математиком Р. Беллманом и его школой и оказалась весьма эффективной для анализа и численного решения этого типа задач. Прежде чем описывать ее сущность, как обычно, начнем с очень простой задачи, которая позволит тем не менее познакомиться с характерными чертами динамического программирования. [c.64]
Многошаговые процессы принятия решений начали изучаться где-то в начале 50-х годов. Для этого хотя и не очень широкого, но часто встречающегося класса задач далеко не всегда пригодны методы классического математического анализа, аппарат линейного программирования или вариационное исчисление. Специальные же методы, предназначенные для исследования таких процессов, требовали разработки специальной концепции. Такая концепция, получившая название динамического программирования, была создана американским математиком Р. Беллманом и его школой. Существенный вклад в развитие методов динамического программирования сделан советскими математиками. [c.89]
Беллман Р. Динамическое программирование. ИЛ, 1960. [c.227]
В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспределенным ресурсом . При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется уже набором параметров ,, 2,..., т, и табулировать значения функций Ал( ,, %2,..., я) необходимо для многократно большего количества точек. Последнее обстоятельство делает применение метода динамического программирования явно нерациональным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал проклятием многомерности . В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информацию о них можно найти в специальной литературе [4, 5]. [c.169]
Беллман (Bellman) Ричард Эрнест (1920— 1984), американский математик, автор метода динамического программирования. Окончил университет штата Висконсин, преподавал в Принстонском, Стэнфорд-ском университетах (профессор с 1948 г.), работал в корпорации РЭНД профессор Калифорнийского университета с 1965 г. Труды в области вычислительной математики и теории оптимального управления. Принцип оптимальности Бел-лмана — основное понятие динамического программирования. [c.434]
Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. — М. Наука, 1965. [c.315]
Подробная характеристика первых трех вариантов решения задачи дана в главе 11. Напомним, что первый вариант имеет строгое и эффективное решение, называемое по имени его создателя алгоритмом (методом) Джонсона. Второй вариант можно при определенных условиях также свести к решению методом Джонсона, но результат при этом будет не обязательно оптимальным. Строгое решение этой задачи дал Р. Беллман, однако оно трудоемко. Третийвариант самый сложный. Эффективная эвристическая процедура его разрешения известна под названием DS-алгоритм. Этот алгоритм распространяет метод Джонсона на общий случай постановки задачи и обеспечивает околооптимальное решение. Существуют и другие подходы, которые используют теорию очередей и компьютерное моделирование, чтобы решить эту проблему. Но все они трудоемки и сложны и в то же время не гарантируют нахождения оптимальной последовательности. [c.544]
Доказательство. Первая часть теоремы хорошо известна (см. Харди, Литтл-вуд и Полна, 1952 Беккенбах и Беллман, 1961). Докажем вторую часть, относящуюся к случаю, когда (5) превращается в равенство. Очевидно, если xi = yi [c.275]
Идея представления нелинейной функции как огибающей линейных функций восходит к Минковскому и интенсивно использовалась Беллманом и другими. [c.305]
Первой попыткой перехода от статических моделей стохастического программирования к динамическим была, по-видимому, двухэтапная задача Данцига — Маданского. Двухэтапная задача может быть обобщена в различных направлениях. Естественно, например, перейти к многоэтапной задаче с жесткими ограничениями (с ограничениями, которые должны выполняться при всех возможных реализациях случая, подобно тому, как это предполагается в классической двухэтапной задаче). Такого рода подходы рассматривались Беллманом [10], Дж. Данцигом [88], Н. 3. Шором и др. [332, 334—336]. Здесь мы, однако, рассмотрим более широкие обобщения двухэтапной задачи — различные постановки многоэтапных стохастических задач с безусловными и условными статистическими, вероятностными и жесткими ограничениями. Частные модели подобного типа обсуждались в [70, 308—310] и других работах. Многоэтапные модели стохастического программирования имеют многочисленные приложения к задачам планирования в экономике и технике. Ряд практических проблем, возникающих при перспективном планировании, при многостадийном проектировании, при управлении боевыми операциями, при планировании экспериментов и оперативном управлении космическими объектами, при регулировании технологических процессов, подверженных случайным возмущениям, может быть рассмотрен как многоэтапные стохастические задачи со статистическими вероятностными и жесткими ограничениями. [c.192]
Итеративные методы в теории игр и программировании. М, Наука , 1974. Авт. В. 3. Беленький, В. А. Волконский, С. А. Иванков, А. Б. Поманский, А. Д. Шапиро. 10. Беллман Р. Динамическое программирование. М., ИЛ, 1960. [c.381]
Лит. Б е л л м а п Р., Динамическое программирование., пер. с англ., М., 1960 его же, Теория динамического планирования, в кн. Современная математика для инженеров, [пер. с англ.], М., 1959 (гл. 10) Беллман Р., Г л и к с-б е р г И., Гросс О., Некоторые вопросы математической теории процессов управления, пер. с англ., М., 1962 П о н т-р я г и н Л. С., Б о л т я н с к и и В. Г., Г а м к р е л и д а е Р. В., Мищенко Е. Ф., Математическая теория оптимальных процессов, М., 1960 трейдер Ю. А., Задача динамического планиронания и автоматы, в сб. Проблемы кибернетики, под ред. А. А. Ляпунова, вып. 5, М., 1961 Романовский И. В., (Сообщение) О динамическом программировании и его использовании в экономике, в кн. Математический анализ расширенного воспроизводства, М., 1962 (Труды научного совещания о применении математических методов в экономических исследованиях и планировании, т. 2). Э. В. Ершов. [c.316]
Лит. Беллман Р., Гликсберг И., Гросс О., Некоторые вопросы математической теории процессов управления, пер. с англ., М., 1962 В а ж о н ь и А., Научное программирование в промышленности и торговле, М., 1963 Применение статистических методов в производстве, сб., сост. В. В. Головинский, М., 1963. Ю. О. Любович. [c.271]
ПРОГРАММИРОВАНИЕ ДИНАМИЧЕСКОЕ, раздел. математического программирования, предназначенный для анализа п численного решения экстремальных задач специальной (чаще всего динаинч.) структуры. Характеризуется поэтапным способом принятии решении. Наиболее значит, вклад в развитие П. д. сделан амер. математиком Р. Беллманом. Важные исследования но совершенствованию вычислит, схем П. д. проведены [c.343]
Беллман Р., Гликсберг И., Гросс О. Некоторые вопросы математической теории процессов управления. ИЛ, 1962. [c.227]
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления Наука , 1969. [c.227]