Приближенные методы решения задач нелинейного программирования , . [c.233]
Нелинейное программирование. Оно объединяет методы решения задач, которые описываются нелинейными соотношениями. Постановка и решение задач нелинейного программирования принципиально не отличаются от постановки и решения задач линейного программирования. К задачам нелинейного программирования относятся задачи оптимизации производства для большинства предприятий, поскольку в настоящее время они действуют на неоднородном рынке в условиях монополистической конкуренции и спрос на их продукцию зависит от цены. [c.114]
Широко распространенный метод решения нелинейных задач состоит в применении так называемых кусочно-линейных приближений. Что это таксе Вы можете определить окружность с любой степенью точности, вписывая в нее многоугольник. Точно так же можно любые кривые приближенно определять, соединяя прямыми отдельные точки этих кривых. ФУНКЦИЯ, изображенная кривой, становится, как говорят, кусочно-линейной, т. е. ломаной, состоящей из прямых кусков (отрезков). Нелинейные задачи, преобразованные таким образом в линейные, решаются хорошо отработанными методами решения задач линейного программирования. [c.125]
Несмотря на большие трудности, связанные с решением задач нелинейного программирования, о которых мы постарались дать представление читателю, в настоящее время ведется большая работа по разработке новых и совершенствованию-уже известных методов их решения. В первую очередь это вызвано большой практической важностью задач такого типа, их актуальностью. Кроме упоминавшейся уже задачи размещения и выбора производственных мощностей, отметим еще одну характерную экономическую задачу, приводящуюся к задаче нелинейного программирования. [c.75]
Несмотря на большие трудности, связанные с решением задач нелинейного программирования, в настоящее время интенсивно ведется работа по созданию новых и совершенствованию уже известных методов их решения. Это результат большой практической важности задач такого типа, их актуальности. [c.108]
При -благоприятных условиях метод штрафных функция позволяет найти обобщенное приближенное решение задачи нелинейного программирования с заданной точностью. [c.236]
Отметим, что методы линейного программирования исполь-дуются в настоящее время и для решения задач оптимизации в нелинейных моделях с нелинейными критериями. При этом осуществляется линеаризация соотношений модели в окрестности текущей точки и переход к новой точке с использованием результатов решения задачи линейного программирования. [c.58]
Нелинейное программирование объединяет методы решения задач, которые описываются нелинейными соотношениями. [c.72]
Прежде всего экономико-математические методы подразделяют на методы решения задач линейного и нелинейного программирования. При этом если все функции f и gt линейные или не содержат произведения искомых переменных, то соответствующая задача — это задача линейного программирования. [c.104]
Точных методов решения целочисленных нелинейных задач в настоящее время нет. Однако нелинейные целочисленные задачи можно свести, к линейным целочисленным [122]. Сведем, например, задачу (4.24) — (4.31) к задаче целочисленного линейного программирования. Для этого любое произведение булевых переменных, входящее в условия задачи, необходимо заменить одной новой булевой переменной, а к системе ограничений экономико-математической модели добавить два линейных неравенства соответственно для каждой вновь вводимой булевой переменной. >В нашем случае [c.193]
Для решения задачи оптимизации структуры выпускаемой продукции необходимо использовать методы линейного или нелинейного программирования с ограничениями. Заранее разработанные алгоритмы решения с использованием компьютерных информационных технологий позволят быстро завершить процесс планирования и сделать его пригодным для принятия промышленным предприятием экономически обоснованных управленческих решений [6]. [c.33]
Численные методы решения задачи НП, основанные на последовательной аппроксимации функции достижимости. Понятия расширения и функции достижимости задачи нелинейного программирования могут быть использованы не только для выбора структуры функции R, но и для анализа способов численного решения [34]. [c.356]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
Нередки случаи, когда при выборе параметров машин целевая функция или ограничения оказываются нелинейными. Тогда возникает задача нелинейного программирования. Решение ее в настоящее время рациональнее всего вести численным методом. [c.212]
Математическое программирование — раздел математики. Он изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств. Объединяет разные математические методы и дисциплины исследования операций программирование, которое подразделяется на линейное и нелинейное, динамическое и выпуклое, геометрическое и целочисленное и др. [c.510]
Экстремальные задачи, в которых либо ограничения, либо целевая функция (случай, который мы рассматриваем ), л иба и то и другое нелинейны, называются задачами нелинейного программирования. К сожалению, пока не имеется общих методов, подобных методу последовательного улучшения плана или симплекс-методу в линейном программировании, которые позволяли бы решать любые задачи нелинейного программирования. Поэтому мы сможем указать на возможность решения лишь для некоторых, впрочем, весьма важных частных случаев. [c.72]
В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения. [c.84]
Если целевая функция является некоторой функцией найденных значений переменных, то для решения задачи применяют методы нелинейного программирования, в частности, его простейшую форму — квадратичное программирование. [c.153]
Зависимость отдельных составляющих целевой функции от числа пунктов разгрузки, включенных в какой-либо вариант внешнего транспортного обеспечения и условно рассматриваемых как непрерывные функции в области целочисленных величин числа пунктов разгрузки пгв, представлена на рис. 27. Как видно из рисунка, с увеличением числа пунктов разгрузки возрастают суммарные затраты на их организацию и уменьшаются транспортные расходы по доставке труб к месту работ. Следовательно, целевая функция как сумма указанных составляющих имеет экстремум при некотором значении числа пунктов разгрузки. Учитывая нелинейную зависимость функционала и его отдельных составляющих от числа вводимых пунктов разгрузки и искомых переменных, для решения поставленной задачи не могут быть применены классические методы математического программирования (например,. линейного). Как известно из курса высшей математики, математическое программирование — область математики, разрабатывающая теорию и методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Само название программирование взято из линейного программирования, где оно обычно обозначает распределение наилучшим образом ограниченных ресурсов для достижения поставленных целей. Следовательно, термин программирование здесь можно заменить термином планирование . [c.145]
Возможности применения моделей с переменными технологическими коэффициентами при решении задач планирования и управления комплексами непрерывного действия освещены также в работах [21—25]. В частности, в [22] рассматривается нелинейная задача статической оптимизации непрерывного производства. Предлагаются кусочно-линейная аппроксимация переменных коэффициентов и замена исходной нелинейной задачи некоторой приближенной задачей, для решения которой могут быть использованы методы линейного программирования. [c.16]
Что касается нелинейных целочисленных задач, то для их решения известен пока что один приближенный метод решения— метод случайного перебора (метод Монте-Карло). Для приближенного решения задач целочисленного линейного программирования сейчас известен целый ряд приближенных ме- [c.129]
Читатель найдет здесь доступное описание основных экономико-математических методов, построенных как на традиционном аппарате математики и логики, известном из школьных программ (дроби, проценты, уравнения, прогрессии, геометрические и логические задачи), так и на основе методов исследования операций - современном математическом аппарате, специально созданном для решения тех задач, с которыми элементарная математика не справляется. Это методы оптимизации (линейное, нелинейное и динамическое программирование), теория вероятностей и математическая статистика, теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), теория игр и статистических решений, сетевое планирование. [c.6]
Рассмотренные случаи не являются исчерпывающими и служат лишь иллюстрацией, из которой видно, что в чисто вычислительном аспекте для нелинейных задач характерны затруднения с получением точного решения либо из-за попадания в локальный оптимум, либо из-за плохой сходимости вычислительного процесса. Кроме того, методы нелинейного программирования в отличие от линейного не являются универсальными и приспособлены для решения лишь ограниченного круга задач того или иного специального класса, а потому гораздо более чувствительны к размерности задач. [c.65]
Другим важным обстоятельством, определяющим неклассический характер задачи оптимального управления, является наличие в задаче условий типа неравенств. Это — условия и (t) U, условия (17), (18). Они, как показал опыт решения таких задач, весьма существенны снятие подобных условий обычно полностью лишает задачу содержательной ценности, так как приводит к решениям либо физически нелепым, либо неприемлемым по техническим условиям. Как правило, в оптимальном решении имеются как интервалы времени, на которых реализуется знак равенства, так и интервалы, на которых реализуется строгое неравенство на первых условие может быть заменено привычным для классического вариационного исчисления условием типа равенства, на последних — снято. К сожалению, расположение и размеры этих интервалов выясняются лишь после решения задачи. Это обстоятельство также имеет глубокие последствия в вопросах конструирования численных методов классический вычислительный аппарат линейной алгебры становится неэффективным и заменяется более соответствующим характеру современных вариационных задач вычислительным аппаратом линейного (и нелинейного) программирования. [c.29]
ПРОГРАММИРОВАНИЕ — составление программ для решения задач на ЭВМ, выбор метода решения, приведение уравнений к виду, удобному для решения на ЭВМ, подготовка исходных данных для постановки задачи, требующей решения наука, занимающаяся разработкой средств и методов подготовки программ для ЭВМ. Программирование включает представление хода решения задачи в виде инструкций, для записи которых разработаны специальные языки (языки программирования или алгоритмические), воспринимаемые ЭВМ. С помощью принятых уравнений, отражающих реальные зависимости между явлениями, по исходным данным определяются значения искомых переменных, совокупность которых может представлять собой параметры плана работы предприятия, объединения, отрасли. В зависимости от формы взаимосвязи между исходными данными и искомыми величинами различают программирование линейное, нелинейное, динамическое и др. Линейное программирование означает прямую пропорциональную зависимость между исходными данными и ис- [c.241]
СКАЛЯРНАЯ ОПТИМИЗАЦИЯ [s alar optimization] — совокупность методов решения задач математического программирования, целевая функция которых представляет собой скаляр. Большинство задач, рассматриваемых в словаре (см. Линейное программирование, Нелинейное программирование, Дискретное программирование и др.), принадлежит к этому классу. Ср. Векторная оптимизация, Многокритериальная оптимизация. [c.330]
Наряду с итеративными способами решения задач нелинейного программирования нередко предлагаются и другие методы. Один из них указан в 1964 г. вьетнамским математиком Хоанг Туем. Его подход основан на идее сужения допустимой области за счет отбрасывания тех частей, в которых заведомо не достигается экстремум. [c.101]
Способ решения задачи зависит от вида функции /. При линейной функции методом решения будет линейное программирование, при нелинейной фиункции — возможно привлечение метода множителей Лагранжа либо динамического программирования. [c.105]
Анализ математической модели задачи показывает, что данная задача относится к задачам нелинейного программирования, а именно к задаче отыскания экстремума нелинейной се-парабельной функции при линейных ограничениях. Для решения задач размещения и развития отрасли используются в основном приближенные методы. Нами предлагается решать задачу с помощью последовательных приближений. На каждом шаге алгоритма (для зафиксированных значений грузооборота неф- [c.47]
МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [mathemati al programming] (см. также Оптимачьное программирование) — раздел математики, который "... изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств"40. Оно объединяет различные математические методы и дисциплины исследования операций линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др. [c.186]
Математические методы оптимизации и оптимального управления в задачах как термодинамики, так и микроэкономики имеют свои особенности. Связано это, во-первых, с тем, что в каждой из этих областей важную роль играют циклические процессы, при которых скорость изменения состояния всей или части системы в среднем за цикл равна нулю. Во-вторых, математические модели часто приводят к уравнениям ляпуновского типа, для которых скорость изменения состояния не зависит от самого состояния. Эти особенности позволяют в ряде случаев свести задачи оптимального управления к усредненным задачам нелинейного программирования, определяют метод получения и характер оптимального решения. Последняя глава книги посвящена методам оптимизации и оптимального управления, применяемым для решения задач о предельных возможностях макроуправляемых систем. [c.4]
Паллиативы (метод проекции градиента в общем случае). Выше было показано, что проектирование градиента осуществляется достаточно просто (правда, в линеаризованной постановке, приводящей к проектированию на линейное подпространство) в двух случаях либо при отсутствии дополнительных условий (F(=ff), либо при отсутствии геометрического ограничения на значения и (t) (u( U). Однако большая часть прикладных задач оптимального управления содержит оба сорта условий, а в этом случае проектирование выполняется решением задачи квадратического программирования. К сожалению, идеи и алгоритмы, относящиеся к линейному и нелинейному программированию, мало известны среди специалистов по прикладной механике, которые особенно часто сталкиваются с необходимостью решения задач оптимального управления достаточно общего вида. Именно в этой среде были созданы многочисленные приемы, имеющие целью сформулировать общую задачу как задачу классического типа, либо как простейшую неклассическую задачу. Мы рассмотрим наиболее типичные из этих приемов. Их следует отнести к разряду паллиативов, так как они не снимают трудностей численного решения, а лишь отодвигают их, так сказать, в глубь проблемы. Создание алгоритма приближенного решения задачи оптимального управления можно условно разбить на два этапа [c.160]
Так, в линейном программировании поочередное использование прямых методов и проверки необходимых условий оптимальности составляет суть описанных выше способов последовательного улучшения плана, симплекс-метода и др. В нелинейном программировании пока еще не созданы столь универсальные способы решения задач. Конечный алгорифм имеется лишь для задачи квадратичного программирования, т. е. задачи с линейными ограничениями и целевой функцией, задаваемой полиномом второй степени. Поэтому, рассматривая общую задачу нелинейного программирования, приходится демонстрировать по отдельности методы первого и методы второго направления. [c.100]
Модель (1)-(9) представляет собой задачу нелинейного стохастического программирования, которая может быть сведена к эквива -лентной детерминированной задаче заменой условий (3) соответствующими детерминированными эквивалентами. Как следует из (I), ее минимизация осуществляется как по глобальным переменным системы Pj, Pj, Ц ц так и по техническим решениям элементов ц -, Их оптимальные значения могут определяться, например, бозградиент-ными методами минимизации по векторам Р -, 9j, QIJ При этом в ходе решения (при фиксированных / Р, , Q j ) выбираются технические решения по газопроводным участкам и компрессорным станциям. [c.32]
При фиксированном значении 0/ -s условия (151) — (158) определяют линейные ограничения, и задача становится нелинейной только относительно функционала. В этом случае, если возможно сведение полученной модели к решению известного типа задач математического программирования, появляется метод решения и исходной задачи (т. е. нелинейной относительно 6 /s). Для этого достаточно найти оптимальные планы группы задач, в которых фиксиро- [c.222]
Если зафиксировать значение в 8, то условия (36) окажутся линейными и задача остается нелинейной только относительно функционала. Используя для решения образовавшейся задачи существующие алгоритмы нелинейного программирования, получаем метод решения и исходной задачи (т. е. нелинейной относительно Qija). Он состоит в том, что для каждого Qijs (I tjs < < Тр) необходимо найти решение соответствующей нелинейной задачи, а затем среди этих решений (их число равно Тр) выбрать то, которое имеет максимальное значение. Оптимальный план, соответствующий задаче с максимальным решением, и будет решением исходной модели. [c.114]
ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ [ onvex programming] — раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений. (См. Выпуклость, Вогнутость ) [c.57]
Задачи вида (25.27) решаются методами математического программирования, которое включает в себя линейное, нелинейное, динамическое, целочисленное программирование и т.д. Выбор методов математического программирования для решения оптимизационных задач определяется видом целевой функции /, видом ограничений, определяющих область М, и специальными ограничениями на управляемые переменные (например, требованием их целочисленности). Решение задачи получения управнения (25.27) обычно называется оптимальным решением, или оптимальным планом. [c.523]
Оптимизационные задачи, сводящиеся к задачам линейного программирования, широко используются в процессе экономико-математического моделирования (они рассматриваются ниже). Однако задачами линейного программирования не исчерпываются все виды оптимизационных экономических задач, так как во многих случаях целевая функция задачи и ограничения на область допустимых решений не удовлетворяют условиям линейности. Тогда применяются специальные методы нелинейного программирования, например метод множителей Ла-гранжа, динамического и имитационного программирования и др. [c.524]