В предыдущем пункте использованы процедуры итеративных методов решения задач выпуклого программирования в функциональных пространствах для установления вида решающих правил некоторых задач стохастического программирования. Следует, однако, подчеркнуть, что в приведенных рассуждениях существенной была не столько схема 1эе [c.132]
Стохастическая аппроксимация в широком смысле слова представляет собой общий метод решения условных экстремальных задач при неполной информации об исходных данных. Мы будем рассматривать стохастическую аппроксимацию как общий итеративный метод решения задач стохастического программирования по последовательным реализациям случайных наборов параметров условий задачи. Такой подход к стохастической аппроксимации влияет известным образом и на ее проблематику и направления развития. [c.341]
В настоящей главе под стохастической аппроксимацией подразумевается теория и итеративные методы решения задач стохастического программирования по последовательным реализациям наборов случайных параметров условий задачи. [c.345]
Естественно, что стохастическая аппроксимация как итеративный метод решения задач стохастического программирования представляет интерес только в многомерном случае. Это, однако, не единственный аргумент в пользу многомерных модификаций процедур стохастической аппроксимации. Различные причины заставляют конструктора в процессе проектирования и создания экспериментального образца сложной системы довольствоваться не наилучшими решениями. Однако при испытаниях системы возникает возможность совершенствовать ее качество, подбирая экспериментальным образом . значения регулируемых параметров и оценивая при этом величину показателя эффективности системы. Ошибки измерений и отсутствие информации о виде функциональной зависимости показателя качества системы от измеряемых параметров усложняют истолкование и использование экспериментальных данных для доводки образца. Опытные инженеры интуитивно используют для совершенствования систем по результатам испытаний схемы типа многомерной стохастической аппроксимации. Задача теории — оценить допустимый диапазон применения этих методов, модифицировать их, упростить вычисления и ускорить сходимость. [c.351]
Итеративный метод решения задачи вогнутого программирования 1218 [c.395]
Итеративные методы решения оптимизационных задач 137 [c.468]
Декомпозиционные методы решения задачи. В связи с большой размерностью и блочной структурой матрицы задачи (6.1) — (6.12) целесообразно для ее решения применять специальные декомпозиционные методы, которые должны включать а) расчленение (декомпозицию) условий задачи на отдельные блоки (подзадачи) б) выработку рациональных способов решения подзадач в) итеративную увязку (координацию) локальных решений подзадач для получения оптимального решения всей задачи. [c.143]
Методы адаптации представляют собой достаточно общий итеративный процесс решения задач стохастического программирования — процесс совершенствования решающих правил или статистических характеристик решающих распределений — по последовательным реализациям наборов случайных параметров условий задач. Формальная основа методов адаптации — различные обобщения схемы стохастической аппроксимации. [c.15]
Заметим, что при отсутствии статистических характеристик случайных исходных данных можно заменить на предварительном этапе прямой путь построения решающих механизмов адаптивным — итеративным методом решения стохастической задачи по последовательным наборам реализаций случайных параметров условий задачи.. 30 [c.30]
Дисперсия D(aax) линейной формы аох — выпуклая функция х в гильбертовом пространстве Нп. Градиент D(a0x) в точке х равен 2(айх — а0х)ат0. Здесь а=Ма. В соответствии с процедурой метода возможных направлений итеративный процесс решения задачи (9.20) — (9.22), исходящий из начала координат, приводит к решающему правилу х (а), удовлетворяющему соотношению [c.132]
Условие (2.36) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений x(q) и и<< ) , то с помощью неравенств вида [c.106]
Одним из основных направлений развития и совершенствования методов решения задач такого типа является построение комплексов взаимосвязанных моделей (Рис. 2), в которых каждая модель отвечает своим специфическим требованиям, а окончательное решение достигается в процессе преобразования и передачи информации между моделями на основе организации итеративных процедур их взаимодействия [2]. [c.250]
Для решения некоторых задач можно использовать и индексный метод. Он также является итеративным и состоит в последовательном улучшении отправного варианта решения задачи. Однако сфера применения симплексного метода значительно шире, чем индексного он успешно может использоваться для расчета затрат на производство и прибыли. [c.73]
В этом параграфе мы опишем более близкие к реальности и одновременно более сложные модели развития отрасли. Основной особенностью этих моделей является учет пространственного расположения уже существующих и строящихся предприятий, а также расположение пунктов, в которых есть потребность в продукции отрасли. При огромных затратах на перевозку продукции и сырья для предприятий учет этих затрат в модели делает ее гораздо ближе к реальности. Кроме того, в модель вносят и некоторые другие усовершенствования, о которых мы расскажем подробнее в процессе математической формулировки модели. Делая модель более реалистичной, мы теряем ее достоинство — простоту. Поэтому модель отрасли будет анализироваться отдельно от остальных отраслей экономики. Потребность в продукции отрасли будет считаться заданной заранее. Возникает вопрос о том, как можно заранее задать эту потребность (а также расположение пунктов, где эта потребность имеется), если не решены еще задачи перспективного планирования других отраслей. Для решения этого вопроса предлагаются различные итеративные методы, основная идея которых состоит в том, что задаются исходные варианты потребности в продукции каждой из отраслей, затем строятся планы перспективного развития каждой из отраслей на основе ее математической модели, после чего потребность в продукции отраслей пересматривается, что приводит к изменению в планах развития отраслей, и так далее до тех пор, пока оптимальные планы различных отраслей не будут согласованы как между собой, так и с целями развития экономики. [c.169]
В этих случаях используется симплекс-метод, который представляет собой итеративную (пошаговую) процедуру для определения оптимального решения задачи линейного программирования. Расчеты по симплекс-методу начинают с определения допустимого решения, а затем отыскиваются другие допустимые решения и проверяются возможности их улучшения. Переход от одного решения к другому продолжается до тех пор, пока новые улучшения не будут невозможны. Широко распространены стандартные компьютерные программы, которые используют симплекс-метод для решения таких управленческих задач, которые можно представить как задачи линейного программирования. [c.220]
Выбор оптимального плана геофизических исследований по этому критерию должен осуществляться итеративным методом, а именно путем многократного решения задачи среднего уровня каждый раз после направленного обновления вариантов развития отдельных баз ц всего перспективного задания экспедиции. Такое обновление осуществляется на основе вспомогательных моделей верхнего и нижнего уровней. Алгоритм согласования [2] обеспечивает последовательное улучшение перспективного плана по значению выбранного критерия оптимизации. [c.153]
Суть этого алгоритма [92] состоит в соединении основной схемы итеративного алгоритма решения соответствующей нецелочисленной задачи с идеей доводки его до целочисленного методом случайного поиска. Итеративный алгоритм, основанный на идее известного метода Брауна— Робинсона решения матричных игр, дает возможность получить приближенное решение задачи линейного программирования при небольших затратах машинного времени. Проведенные эксперименты доказывают, что в применении к некоторым классам задач линейного программирования итеративные алгоритмы могут конкурировать с симплексными [92]. [c.190]
Блочная структура задачи текущего планирования на уровне объединения делает возможным ее расчленение на ряд подзадач существенно меньшей размерности и их взаимосвязанное решение в рамках итеративного процесса. Методы решения могут быть различными. Рассмотрим некоторые из них на условном примере, обращая главное внимание на экономическую интерпретацию. [c.179]
Реальность результатов решения задач перспективного планирования развития ГСС во многом зависит от характера выбранного метода и алгоритма решения задач и еще больше от подхода в целом к их постановке и решению. При использовании оптимальных итеративных алгоритмов следует стремиться к тому, чтобы они были не просто математически сходящимися (например, такими, в которых оптимальное допустимое решение получается лишь на последней итерации), а имели бы удобную экономическую интерпретацию и соответствовали бы по достигаемой точности исходным данным и требованиям к результатам. Это, в свою очередь, предполагает получение на каждой итерации допустимого решения, пригодного для практической реализации, а также обеспечения хорошей сходимости алгоритма. Возможно сокращение трудоемкости расчетов на итерации за счет некоторого уменьшения точности получаемых результатов, что оправдано при наличии фактора неопределенности исходной информации. [c.140]
Чтобы после некоторого числа шагов, проведенных в окрестности искомой точки, не выйти из нее, необходимо потребовать стремления к нулю шага ап при п— оо. Таким образом, на классические методы стохастической аппроксимации можно смотреть как на итеративные методы (градиентного типа) решения безусловной экстремальной стохастической задачи [c.342]
В настоящей главе кратко излагаются основные схемы стохастической аппроксимации и обсуждаются обобщения теории и методов, позволяющие строить итеративные вычислительные процедуры решения задач стохастического программирования. [c.343]
Можно предложить следующий итеративный приближенный метод решения такой задачи, сводящийся к решению последовательной серии общих задач линейного программирования. [c.396]
Рассмотренная модель характеризуется рядом упрощающих предположений. Так, предполагается единая типовая мощность установок, задача рассматривается в статике, не учитывая возможности ввода новых установок. Для учета всех этих факторов ныне разработаны динамические модели. Они сложны, требуют большого количества информации, решение их сопровождается применением специальных приемов (разбивка на блоки, итеративный метод получения оптимального результата и др.). [c.176]
Все методы линейного программирования делятся на две группы конечные и итеративные. Методы первой группы обеспечивают решение задачи за конечное число шагов, методы второй связаны с бесконечным числом итераций и позволяют получить лишь приближенное решение. В настоящем учебном пособии рассматриваются только конечные методы линейного программирования. [c.183]
Прямое решение задачи детерминированного эквивалента, в котором условные вероятности повторно вычисляются на каждом шаге для всех информационных траекторий. Программы для решения задач линейного и квадратичного программирования очень большой размерности имеются в наличии и способны решать задачи, используя соответственно стандартные алгоритмы линейного программирования (т.е. симплекс-метод и метод внутренней точки) и квадратичного программирования (итеративный алгоритм, или на основе метода внутренней точки). [c.35]
Такие математические методы, как моделирование, линейное, динамическое и целочисленное программирование, теория игр и другие могут быть использованы для определения оптимального плана, но обычно в задачах такого рода число переменных и ограничений настолько велико, что они превышают возможности современной вычислительной техники. Следовательно, при имеющихся математических средствах, как правило, невозможно оптимизировать альтернативные планы и затем выбрать окончательное решение. Современные итеративные методы, использующие эвристику, позволяют определить если не оптимальный, то приемлемый план. [c.252]
Принятие решений на базе экономико-математических моделей оптимизации основного производства НПП представляет собой итеративный процесс, отдельными этапами которого являются решение исходной задачи с использованием оптимизационных методов, анализ конкретных результатов, уточнение данных, а иногда и самой формулировки задачи, и переход к новому решению. [c.76]
Рассмотрим итеративный метод решения задачи (4.15) вогнутого программирования, представляющий собой обобщение метода Гаусса — Зейделя покоординатного спуска. В [83] метод Гаусса — Зей-деля распространен на случай, когда на каждом шаге производится оптимизация не по отдельным переменным, а по векторам, составляющие которых — некоторые подмножества множества переменных задачи. Задача (4.15) не укладываетя в класс задач, для решения которых в [83] обосновано обобщение метода покоординатного спуска. Векторы X/j( oh ) — аргументы функции
Условия, при которых классические процедуры стохастической аппроксимации сходятся к искомому экстремуму, требуют выпуклости или по крайней мере одноэкстремальности функции -Мш (со, х) по х. Это значит, что для использования стохастической аппроксимации в качестве итеративного метода решения задач стохастического программирования необходимо модифицировать классические схемы применительно к задачам условной оптимизации и отказаться от требования выпуклости или одноэкстремальности Мщ<р (ш, х). [c.343]
Т. Блум [31], Ж. Сакс [244] и другие обобщили схемы стохастической аппроксимации на многомерный случай. Кратко опишем не только многомерный аналог процедуры Кифера — Вольфовица оптимизации одноэкстремальной функции регрессии, но и многомерный аналог схемы Роббинса — Монро. Оба эти процесса могут быть использованы для построения итеративных методов решения задач стохастического программирования (см. 7). [c.351]
ИТЕРАЦИЯ [iteration] — повторное применение математической операции (с измененными данными) при решении вычислительных задач для постепенного приближения к нужному результату (это видно на блок-схеме вычисления среднего арифметического — рис. А.2 к ст. "Алгоритм"). Итеративные расчеты на ЭВМ характерны для решения экономических (особенно оптимизационных и балансовых) задач. Чем меньше требуется пересчетов, тем быстрее сходится алгоритм. См. Итеративные методы решения оптимизационных задач. [c.137]
Итеративный метод решения двухэтапных задач, не требующий априорных характеристик случайных параметров условий, разработан Ю. М. Ермольевым и Н. 3. Шорам [110]. Ерю.шеву принадлежит, кроме того, ряд общих подходов к анализу задач стохастического программирования [104—109]. [c.17]
Чтобы расширить круг задач стохастического программирования, для которых стохастическая аппроксимация может служить итеративным методом решения, целесообразно также отказаться от рассмотрения ошибок наблюдения как аддитивного шума, наложенного на детер-. минированный процесс аппроксимации. На. этом предположении основано доказательство сходимости большинства вычислительных схем стохастической аппроксимации. Некоторые задачи стохастического программирования (см., например, 5 гл. 14 Обобщенные задачи фильтрации и прогноза ) требуют разработки итеративных процессов оптимизации функционалов вида / (Мш<р (ю, х)) на некотором множестве X. Итеративные процессы решения некоторых классов двухэтапных задач стохастического программирования должны обеспечить последовательную условную оптимизацию функционалов вида M JR М (ш,, о>2, хг,х2), [c.343]
В дальнейшем нас будут интересовать, главным образом, процессы типа Кифера — Вольфовица, поскольку от них естественно перейти к итеративным схемам решения условных экстремальных задач, в которых параметры целевой функции и ограничений случайны, т. е. к итера-тивньш методам решения задач стохастического программирования. [c.345]
Наряду с итеративными способами решения задач нелинейного программирования нередко предлагаются и другие методы. Один из них указан в 1964 г. вьетнамским математиком Хоанг Туем. Его подход основан на идее сужения допустимой области за счет отбрасывания тех частей, в которых заведомо не достигается экстремум. [c.101]
Бакушинский А.Б., Гончарский А.В. Итеративные методы решения некорректных задач. М. Наука, 1989. [c.90]
В настоящей главе обсуждаются методы построения решающих правил для одноэтапных задач стохастического программирования, а для отдельных моделей приводятся и явные выражения для решающих правил. В 1 рассматриваются частные модели первого класса, в которых предполагается, что решающие правила — линейные функции случайных составляющих условий задачи. Вычисление параметров решающих правил сводится к задачам выпуклого программирования. Параграф 2 посвящен изучению. М-модели с вероятностным ограничением общего вида. Относительно решающего правила л (со) не делается никаких предположений, кроме того, что л (со)—измеримая вектор-функция на множестве X произвольной структуры, на котором она определена. В 3 метод построения решающих правил из предыдущего параграфа обобщается на М-модель с конечнозначным ограничением — с условием, ограничивающим математическое ожидание случайной функции от х, принимающей конечное число значений. Таким условием может быть аппроксимировано любое статистическое ограничение. В 4 построены решающие правила (точнее, решающие таблицы) дляч Р-мо-дели с вероятностными ограничениями общего вида. В 5 рассматривается стохастическая задача со смешанными ограничениями. Эта модель отличается от задачи 4 дополнительными условиями, которые могут существенно изменить структуру решения. В 6—8 построены решающие правила для одноэтапных задач стохастического программирования со статистическими ограничениями достаточно общего вида. Модель, изученная в 6, представляет собой стохастический аналог общей задачи линейного программирования с двухсторонними ограничениями. Модель из 7 — стохастический аналог общей задачи квадратичного программирования. Модель, исследованная в 8, является стохастическим аналогом частной задачи выпуклого программирования с квадратичной целевой функцией и квадратичными ограничениями. Заключительный параграф главы ( 9) посвящен итеративным методам построения решающих правил одноэтапных задач стохастического программирования. [c.84]
Для решения задачи предлагается сходящийся итеративный метод. На каждом шаге метода решается конечно-мерная задача квадратичного программирования для выбора возможного направления, вдоль которого можно улучшить значение целевого функционала fo(x), и выбирается рациональная величина шага. В алгоритме используется так называемый antizigzaging прием, исключающий заедание вычислительного процесса и обеспечивающий точность вычислений. Предлагаемый метод представляет собой естественное обобщение метода возможных направлений, разработанного в [126] для решения задач линейного и выпуклого программирования. [c.123]
В J108] предлагается, следуя Вульфу, использовать для решения задачи (3.14) — (3.16) следующий итеративный метод. [c.139]
В 2 рассматриваются классические схемы одномерной стохастической аппроксимации и некоторые их модификации. Основное внимание здесь уделяется итеративным процедурам решения безусловной экстремальной задачи вида (1.2). Параграф 3 посвящен условиям сходимости многомерных процессов стохастической аппроксимации. Помимо классических схем здесь излагаются и результаты, полученные в последние годы.. В 4 приводится обзор обобщений схем стохастической аппроксимации на случай решения условных экстремальных задач. Только в этом случае стохастическая аппроксимация может рассматриваться как итеративный метод стохастического программирования. В 5 исследуется важный для приложений вопрос о скорости сходимости и возможных путях ускорения сходимости процессов стохастической аппроксимации. Процедуры, рассмотренные в 6 и 7, позволяют в ряде случаев отказаться от основных допущений, на которых основаны классические схемы стохастической аппроксимации, — от одноэкстремальности целевого функционала задачи и несмещенности оценок наблюдаемых случайных величин. [c.343]
Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования (алгоритмы метода внутренних точек). -Новосибирск Наука, 1988. [c.364]
Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(s=/0, . .., i ip=t). [c.129]
ИТЕРАТИВНОЕ АГРЕГИРОВАНИЕ [iterative aggregation] —метод организации информации при решении планово-экономических задач большой размерности на основе итеративной увязки подзадач, показатели которых определены с разной степенью детализации. Этот принцип организации информации противоположен принципу, применяемому в блочном программировании там исходная задача подразделяется на подзадачи, соответствующие разным уровням управления, в которых, однако, фигурируют показатели одной и той же степени детализации. См. также Агрегирование. [c.137]