Размерность оптимальных задач

Множители Лагранжа в динамическом программировании. Неопределенные множители Лагранжа используются в классическом анализе и в вариационном исчислении при решении задач, на переменные которых наложены ограничения типа равенств. С неменьшим успехом эти множители можно применять и в динамическом программировании, где при их помощи удается снизить размерность оптимальной задачи. [c.280]

Для решения задач линейного программирования имеется практически универсальный алгоритм — симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства практически важных задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи. [c.33]

Важной характеристикой любой оптимальной задачи является ее размерность п, равная числу переменных, задание значений которых необходимо для однозначного определения состояния оптимизируемого объекта. Как правило, решение задач высокой размерности связано с необходимостью выполнения большого объема вычислений. Ряд методов (например, динамическое программирование и дискретный принцип максимума) специально предназначен для решения задач оптимизации процессов высокой размерности, которые могут быть представлены как многостадийные процессы с относительно невысокой размерностью каждой стадии. [c.34]

Таким образом, устраняя ограничивающие условия (IV,2), удалось и уменьшить размерность исходной оптимальной задачи. [c.140]

Достоинства метода динамического программирования при решении оптимальных задач для процессов невысокой размерности неоспоримы, поскольку он принадлежит к числу немногих методов оптимизации, при применении которых полученное решение соответствует глобальному оптимуму. [c.319]

Вместе с тем следует иметь в виду и недостатки этого метода, обусловленные проклятием размерности (см. стр. 259), и всегда стремиться к тому, чтобы при формулировке оптимальной задачи в терминах динамического программирования размерность оптимизируемого процесса была по возможности малой. [c.319]

Следует отметить, что значение линейного программирования не исчерпывается решением задач только указанных типов. Сообщается , что в методах решения задач так называемого выпуклого программирования существенным образом используется вычислительный аппарат линейного программирования. Кроме того, иногда при рассмотрении сложного нелинейного объекта иногда удается представить его математическое описание в некоторых локальных областях изменения независимых переменных приближенными линейными соотношениями. Это позволяет свести исходную задачу оптимизации к задаче линейного программирования. Тем самым становится возможным применять его математический аппарат, который в настоящее время разработан достаточно подробно и при наличии цифровой вычислительной машины обеспечивает решение оптимальных задач весьма высокой размерности. [c.413]

Последовательная иерархическая многоуровневая декомпозиция граничных задач первого уровня, в результате которой достигается необходимое снижение размерности граничных задач проектирования, что позволяет значительно сократить объем вычислительных операций при определении оптимального решения ИПЗ. [c.258]

В качестве критерия окончания поиска производится подсчет неудачных шагов в обратном направлении. Если число таких шагов превысит некоторую заданную величину, обычно выбираемую кратной размерности решаемой задачи, то поиск прекращается и последнее наилучшее значение критерия принимается за оптимальное. [c.390]

При оптимизации дискретных многостадийных процессов использование математического аппарата принципа максимума зачастую оказывается более эффективным, чем применение метода динамического программирования. В особенности это относится к решению оптимальных задач, где размерность отдельных стадий затрудняет использование вычислительной процедуры динамического программирования [11]. [c.386]

Выше уже отмечалось, что основной объем вычислений при решении задач линейного программирования приходится на расчеты, связанные с определением обратных матриц, для получаемых на каждом шаге базисов. При использовании общих методов [3] для задач высокой размерности, т. е. с большим числом независимых переменных, объем вычислений, приходящийся на обращение матриц порядка т, возрастает быстрее, чем т2, что может существенно увеличить общее время решения оптимальной задачи. Поэтому представляет интерес применение методов вычисления обратных матриц, основанных на свойствах последовательности базисов, получаемой при использовании симплексного метода. [c.441]

Таким образом, число вычислений критерия оптимальности при определении положения оптимума методом сканирования возрастает в показательной зависимости от размерности решаемой задачи. Поэтому эффективное применение данного метода в основном ограничивается задачами невысокой размерности п = 2 — 3, если используется простейший алгоритм поиска, рассмотренный выше, для отыскания оптимума с невысокой точностью. [c.510]

Нетрудно заметить, что обобщенный критерий оптимальности (IX, 193) имеет овраг , расположенный вдоль гиперповерхности ограничений, так как при удалении от нее функция аН(х) и, следовательно, функция Q(x) резко возрастают. Размерность этого оврага выражается числом ограничений (IX, 2а) и равна п — т. Поэтому для решения оптимальных задач с ограничениями типа равенств (IX, 2а) при использовании обобщенного критерия с успехом может быть использован метод шагов по оврагу , рассмотренный выше (см. стр. 516). [c.538]

Иерархический характер управления водными ресурсами и необходимость поэтапной детализации планов и проектов обусловливает потребность в разработке математических моделей разной детальности. В предыдущих разделах отмечалось, что на верхнем уровне принятия решений (регион, крупный речной бассейн) обычно используются оценочные модели, учитывающие лишь основные зависимости между параметрами. Применение таких упрощенных соотношений между параметрами и сильная степень агрегирования информации позволяет не только уменьшить размерность решаемых задач, но и провести многовариантные расчеты, сопоставив множество альтернатив. Поэтому модели верхнего уровня формулируются как экстремальные задачи. Оптимальные или близкие к ним решения отыскиваются чаще всего с применением экономических целевых функций (типа минимума приведенных затрат на реализацию комплекса необходимых мероприятий). Агрегированный характер исходных данных таких моделей приводит к упрощению большинства параметрических связей, допускает их линеаризацию, а также позволяет пренебречь многими условиями и ограничениями. [c.64]

Поскольку оптимизацию надо проводить во всех дугах цепи, размерность комбинаторной задачи поиска оптимального плана-графика Г/ в пути у все-таки остается значительной, особенно на [c.222]

Для того чтобы избежать анализа всех возможных вариантов комбинаторной задачи, можно применить эвристический метод поиска оптимальных структур. Суть метода состоит в выводе правила (алгоритма), позволяющего исключить из рассмотрения некоторые физически реализуемые структуры и тем самым значительно снизить размерность решаемой задачи. [c.431]

Для борьбы с размерностью исходных задач целесообразным является декомпозиционный подход, основанный на специфической особенности структур решаемых задач. Эти особенности могут быть выявлены при применении методов предварительного анализа и компактного преобразования информационных структур исходных задач в виде больших и разреженных матриц [29—36]. Здесь выбираются оптимальные параметры многоэтапных многоуровневых алгоритмов решения комплексных задач набор локальных подзадач, и координирующей задачи, их размерности, последовательность этапов решения этих задач... [c.89]

Примечания . Эффективное применение метода. 2. Используется. 3. Возможно применение. 4. Используется как вспомогательный метод, о. многостадийные процессы (размерность указывается для отдельной стадии). 6. Задачи с линейными критериями оптимальности И линейными ограничениями 7 Используются множители Лагранжа. [c.35]

Применение множителей Лагранжа позволяет снова свести задачу к исходной размерности оптимизируемого процесса. С этой целью сформируем новое выражение для критерия оптимальности каждой стадии [c.266]

Более сложная задача возникает при использовании метода динамического программирования для оптимизации процессов с байпасными потоками. Поскольку направление расчета противоположно направлению такого потока, при выборе оптимального управления на стадии, к которой он подводится, состояние этого потока, так же как и состояние выхода предшествующей стадии, необходимо исследовать во всем возможном диапазоне изменения его параметров. Другими словами, размерность задачи выбора оптимального управления изданной стадии увеличивается на размерность состояния байпасного потока. [c.297]

Для оптимизации процессов с распределенными параметрами предпочтительнее все же оказывается принцип максимума, которому посвящена следующая глава. Однако всегда нужно учитывать воз-мо кность аппроксимации непрерывного процесса дискретным многостадийным процессом и пользоваться указанной возмо кностью для решения оптимальных задач невысокой размерности. Это обусловлено 1см, что метод динамического программирования представляет в распоряжение исследователя весьма удобную процедуру оптимизации многостадийных процессов, которая сравнительно легко программируется на вычислительных ма1[шнах. [c.319]

Задача о построении оптимального контура аЬ в областях I и III при плоскопараллельных течениях была решена Шипилиным [37] с использованием общего метода, не позволяющего уменьшить размерность вариационной задачи. Об этом методе будет сказано в конце главы. Оптимальный профиль имеет бесчисленное количество выпуклых из- [c.164]

Все это с учетом перехода к использованию более мощных ЭВМ позволило производить рационально организованный перебор значительно большего числа деревьев и сутцественно повысить размерность решаемых задач. Соответствующий алгоритм поиска оптимального дерева на исходной схеме состоит из следующих основных операций. [c.187]

Проблема размерности. Таким образом, метод динамического программирования дает возможность при оптимизации многостадийных процессов расчленить задачу врлбора оптимальных управлений (t 1,. . ., N) па N задач, в каждой из которых выбирается только одно управление и< >. [c.259]

Один из возможных алгоритмов решения задачи синтеза оптимальной химико-технологической системы, применяемый для задач небольшой размерности, состоит в упорядочении процедуры поиска оптимального решения. В основе алгоритма лежат с. 1сдующпе представления. Из переменных задачи V/, Л /(/ = — д, т . только две являются независимыми, а две другие [c.192]

Минимизация этой функции производится методом ветпей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых сущсстненное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Поэтому для снижения размерности прибегают к различного рода эвристическим приемам или используют. методы направленного перебора (ветвей и границ). Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования (в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [c.300]

Необходимо отметить, что в настоящее время на основе рассмотренных выше топологических моделей в виде ДГХП и р-сетей, а также благодаря использованию методов динамического программирования (для так называемого алгоритма прямого движения по р-сети от исходных веществ к заданным соединениям), методов эвристического программирования (для алгоритма обратного движения по р-сети от заданных соединений к исходным веществам, когда размерность диаграмм синтеза чрезвычайно возрастает) и методов математической логики разработаны алгоритмы, которые позволяют полностью автоматизировать решение этой трудоемкой задачи поиска оптимальных маршрутов синтеза. [c.194]

Справочник химика 21

Химия и химическая технология