Минимизация линейной функции

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

Матрицы, входящие в правую часть этой формулы, имеют одинаковую форму представления они получены в результате умножения вектора на свой транспонированный вектор. Ранг подобных матриц, очевидно, равен единице. Так как ранг суммы матриц не превосходит суммы рангов ее составляющих, то при р < п — 1 ранг матрицы (х ) оказывается меньшим п, т. е. она является вырожденной. Если на нижнем уровне для минимизации функции а(- ) применяется метод Ньютона [см. выражение (1,43)], то в общем случае эффективность его для рассматриваемой ситуации значительно снижается [81, с. 79—86] вместо квадратичной скорости сходимости можно гарантировать лишь линейную скорость, характерную для обычного градиентного метода. Следовательно в целом эффективность алгоритма метода уровней, используемого совместно с методом Ньютона для выполнения безусловной минимизации, должна снижаться по мере приближения значения параметра л к л. Отсюда следует также, что в общем случае метод уровней целесообразно применять лишь для локализации решения задачи на условный экстремум, в частности задавать начальные приближения для х и [Л, достаточно близкие к х, х, нецелесообразно, Последний из упомянутых моментов часто проявлялся при расчетах на ЭВМ с использованием на нижнем уровне других квадратичных методов безусловной минимизации. [c.122]

В связи с вводом искусственного вектора будем рассматривать более расширенную задачу, связанную с минимизацией линейной функции [c.142]

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

Тогда минимизация Т (л ) при ограничениях (4.19) будет, очевидно, эквивалентна минимизации линейной функции [c.138]

Важным этапом в решении задач обработки экспериментальных данных является выбор метода отыскания наилучших значений параметров искомой зависимости. По существу задача определения наилучших значений параметров зависимости, минимизирующих определенную оценку, является задачей минимизации функции многих переменных. В тех случаях, когда искомая зависимость ищется в форме нелинейной функции, решение этой задачи может представить определенные трудности, поскольку приходится применять общие методы решения задач отыскания минимума функции лшогих переменных — методы нелинейного программирования [1]. Лишь когда искомая зависимость Р (х , а ,..., а ) является линейной функцией параметров aj (/ = 1, 2,..., з), например, при отыскании аппроксимирующего полинома, наилучшие значения параметров а ( = 1, 2,..., х), в особенности при использовании критерия оценки среднеквадратичного отклонения (11—8), могут быть найдены относительно просто, для чего используется метод, называемый методом наименьших квадратов (см, стр. 319). [c.299]

Другой важной проблемой машинной реализации линейной или нелинейной диаграммы связи является поиск констант элементов с линейными определяющими соотношениями. Обычно они неизвестны и определяются косвенно по экспериментальным данным. Здесь предлагается метод нахождения таких констант с помощью минимизации целевой функции. В качестве основного метода предлагается метод случайного поиска экстремума (71 как наиболее общий, но пользователь может заменить этот метод на свой, например метод локальных вариаций [7, 8], метод Ньютона [7] и т. д., не являющийся универсальным, т. е. не дающий оптимума наверняка даже в случае произвольно большого числа итераций. [c.201]

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

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

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

Если рассматривается случай минимизации неквадратичной функции и возможно вычисление гессиана О функции то на основе формулы (IV, ПО) может быть построен аналог метода Ньютона для случая условной минимизации с линейными ограничениями. В этом случае итерационные формулы примут вид [c.152]

Обычно, зная характеристики решаемых задач, можно оценить такие параметры УВМ, как быстродействие, объем оперативной памяти, разрядность. В работе [6] в качестве примеров приводятся такие расчеты для часто встречающихся задач системы линейных алгебраических уравнений, задачи Коши для канонических систем обыкновенных дифференциальных уравнений, задачи линейного программирования, задачи минимизации выпуклых функций, многоэкстремальные задачи минимизации н др. [c.205]

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

Данные МЛП для минимизации суммы модулей линейных функций могут быть представлены в другой форме [37]. Среди решений линейной функции [c.281]

При конкретной работе выбор критерия в очень большой степени обусловлен доступностью алгоритмов, которые используются при его минимизации. Именно это, с нашей точки зрения, сыграло решающую роль в широком распространении метода наименьших квадратов (МНК) при решении конкретных задач [7]. Действительно, если исходная задача линейна относительно/i, то МНК приводит к решению системы п линейных алгебраических уравнений с п неизвестными. В любом случае сумма квадратов уклонений есть гладкая функция относительно К, п для ее минимизации можно с успехом применить детерминированные методы поиска минимума. [c.86]

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

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

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

Минимизация функций при наличии линейных ограничений [c.190]

Изложенные методы одномерной минимизации являются по существу методами нулевого порядка, т. е. веточках прямой pi вьшолняется расчет лишь значений минимизируемой функции. Если же в каждой точке известны и значения градиента данной функции, то могут быть использованы теоретически - более эффективные алгоритмы одномерного поиска, основанные на применении так называемых критериев сходимости. При этом автоматически обеспечивается выполнение условия (И1, 163), связанного с устойчивостью алгоритма минимизации. Для обеспечения критерия сходимости в случае его невыполнения на первом шаге обычно используются методы линейной экстраполяции совместно с кубической интерполяцией (см. Приложение 2). По данным решения тестовых задач методы первого порядка требуют в среднем 1,1—1,5 вычислений функции (вместе с градиентом) на направлении по сравнению с 2,5—4 вычислениями при методах нулевого порядка. [c.99]

Рассмотрим теперь ряд методов минимизации функций многих переменных при наличии линейных ограничений. [c.152]

Минимальное значение Е определяется при помощи вариационного метода, который заключается в минимизации интеграла (II, 6) путем варьирования параметров атомных орбиталей в волновой функции. Покажем, как это осуществляется на примере расчета состояния я-электронов молекулы этилена. Молекулярную орбиталь ф этилена можно представить в простейшем случае в качестве линейной комбинации двух атомных 2р -орбиталей h и В таком случае [c.47]

Молекулы всех оснований в ДНК и РНК плоские и содержат объединенную систему я-электронов, которая охватывает все атомы. Соответствующую волновую функцию получают из атомных, составляя линейную комбинацию атомных функций, умноженных на коэффициенты, подбираемые методом минимизации энергии . [c.351]

Теория квадратичных методов минимизации, изложенная в начале этой главы, основана на исследовании задачи о минимуме квадратичной функции. Возможность применения этих методов к минимизации произвольных, т. е. неквадратичных функций связана с тем, что при выполнении известных условий неквадратичную функцию в некоторой окрестности точки минимума можно с определенной точностью аппроксимировать квадратичной функцией. Некоторые свойства квадратичных методов минимизации — устойчивость, идентичность генерируемых последовательностей л —установлены, но существу, для неквадратичных минимизируемых функций [67 72 11, с. 76— 81 ]. Окончательное решение вопроса о возможности применения квадратичных методов к минимизации неквадратичных функций определяется исследованием сходимости рассматриваемых методов, так как свойство конечности алгоритма (достижение минимума за конечное число итераций) для неквадратичных минимизируемых функций, вообще говоря, не выполняется. Для многих, наиболее часто применяемых квадратичных методов минимизации не только доказано свойство сходимости, но и получены оценки скорости сходимости, которая оказывается сверхлинейной [154, 155]. В то же время метод наиекорейшего спуска, например, характеризуется, в общем, более слабой — линейной скоростью сходимости. Практическое подтверждение этих теоретических соображений основывается на результатах решения тестовых задач различными методами и последующей их сравнительной оценке. [c.98]

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

Преимущества метода Ритца заключаются в легкости его обобщения на случай многих линейных вариационных параметров, а также в легкости выполнения процесса минимизации энергетической функции (3.33), который быстро приводит к системе линейных (секулярных) уравнений. Минимизацию по линейным параметрам выполнить намного легче, чем минимизацию ф по параметрам иных типов, таких, как, например, параметр с в экспоненциальной функции Другое преимущество заключается в том, что функции фь ф2, входящие в линейную комбинацию, можно выбирать по нашему усмотрению, следуя химической интуиции и вводя как раз такие функции, которые передают свойства, ожидаемые на основании химических соображений. Если по ошибке введена неудачная функция ф, то ничего не изменится (потребуются только дополнительные вычисления), ибо соответствующий коэффициент Сг окажется автоматически малым это будет свидетельствовать о том, что введенная функция фг действительно не необходима. Наоборот, если в линейную комбинацию введены подходящие функции, то соответствующие коэффициенты Сг. .. не будут малы и пол- [c.77]

Задача минимизации максимального значения отклонения (VIII-16) сводится к следующей задаче линейного нрограммирова-ния введением дополнительной переменной ADmax-Минимизировать линейную функцию [c.282]

Для данной системы характерно то, что в области отрицательных температур зависимость с. от температуры является монотонно возрастающей и описьш ется линейной функцией J = 0,020 + 0,502 х X 10 а при / > О °С значения не изменяются и равны 0,02. Причем значения с. , полученные двумя разными способами в одном случае минимизацией функционала (2.128), а в другом - функционала (2.129), полностью согласуются. Так, значение с ., рассчитанное по данным о паро жидкостном равновесии при t = 71,1 °С, равно 0,02. [c.89]

Итак, два последних результата устанавливают сверхлинейную скорость сходимости метода Давидона — Флетчера — Пауэлла к локальному минимуму, если а,- в (76) определяется точной линейной минимизацией и хс сходится к X при условии (61). Например, пусть минимизируемая функция / "- 1 равномерно выпукла и дважды непрерывно дифференцируема в Е", причем выполнено условие Липшица с р = 1 [c.283]

Естествен И), что непрерывность производных функцнн / никак ие следует из постановки оптимальной задачи как задачи максимизации или минимизации критерия (VH,545). Более того, для целого рида процессов (наиример, описываемых линейными дифференциальными у )авнепиями) можпо показать что функция / (х, /) имеет разрывшее производные, и, следовательно, решение таких задач, строго говоря, ис может удовлетворять уравнению (VI,227), [c.411]

Изло/кеппый метод оценки обусловленности системы предполагает линейность либо возможность легкой линеаризации модели. Если же линеаризация приводит к большим ошибкам, то предпочтительнее для оценки параметров использовать поисковые методы минимизации функции нескольких переменных. При этом в процессе поиска получается обширная информация о поверхности критерия оценки, которую можно использовать для непосредственного вычисления матриц корреляции параметров. Так, в работе [12] предлагается поисковый метод, основанный на вычислении коэффициентов регрессии оцениваемых параметров. Покажем, как можно использовать матрицу коэффициентов регрессии для нахождения корреляционной и ковариационной матриц. Из матрицы коэффициентов регрессии образуем матрицу вида [c.448]

Авторы выражают благодарность сотрудникам НИФХИ им. Л. Я. Карпова и других институтов, совместно с которыми были написаны следующие разделы Оптимизация процесса получения окиси этилена (с Ю- М. Волиным), Определение вида матрицы И , Минимизация функций при наличии линейных ограничений (с Г. Н- Сальниковой), Моделирование и оптимизация производства стирола (с В. А. Приходаем) Синтез реакторной схемы. Первый пример (с А- Л. Шевченко), глава I (с М- Ю- Волиным) глава VI (с Л. М- Брусиловским). [c.8]

Точки XI перехода на следующее направление определяются с помощью (1,48), т. е. а, = Привлекательн()й чертой этого метода является простота реализации, однако недостатки его общеизвестны метод обладает линейной скоростью сходимости — даже для квадратичной функции минимизации процесс поиска ее минимума теоретически бесконечен для функции с сильно вытянутыми линиями уровня (изолиниями) процесс поиска носит явно выраж нный зигзагообразный характер и дает слабое продвижение к минимуму точное нахождение минимума практически нереально. [c.28]

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

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

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