Решить задачу нелинейного программирования онлайн

Содержание

Решить задачу нелинейного программирования онлайн

Сервис для решения задач по линейному программированию

Пример №2. Решение задачи линейного программирования графическим методом.
Функция достигает наименьшего значения в точке

при следующих ограничениях:

Точки, координаты которых удовлетворяют одновременно всем неравенствам системы ограничений, называются областью допустимых решений.

Очевидно, для нахождения области допустимых решений данной задачи, необходимо последовательно рассмотреть каждое неравенство. (см. шаг 1 — шаг 4)

Последние два шага (см. шаг 5 — шаг 6) служат непосредственно для получения ответа.

Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче.

По условию задачи: x1 ≥ 0 x2 ≥ 0.

Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке (вся первая четверть).

Рассмотрим неравенство 1 системы ограничений.

Построим прямую: x1 + 2 x2 = 8

Найдены коородинаты двух точек (0, 4) и (8 ,0). Соединяем их и получаем необходимую прямую (1).

Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x2

Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (1).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Рассмотрим неравенство 2 системы ограничений.

Найдены коородинаты двух точек (0, -2) и (2 ,0). Соединяем их и получаем необходимую прямую (2).

Нас интересуют точки расположенные выше или ниже построенной прямой (2) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x2

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (2).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Рассмотрим неравенство 3 системы ограничений.

Построим прямую: x1 + 2 x2 = 4

Найдены коородинаты двух точек (0, 2) и (4 ,0). Соединяем их и получаем необходимую прямую (3).

Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x2

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Рассмотрим неравенство 4 системы ограничений.

Построим прямую: x1 = 1

Данная прямая параллельна оси OX2 и проходит через точку (1,0) (4)

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные правее построенной прямой (4).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Строим вектор C = (2, 2), координатами которого являются коэффициенты функции F.

Будем перемещать «красную» прямую, перпендикулярно вектору C , от левого нижнего угла к правому верхнему.

В точке, в которой «красная» прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения.

В точке, в которой «красная» прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения.

Функция F достигает наименьшего значения в точке A. (см. рисунок)

Найдем координаты точки A.
Точка A одновременно принадлежит прямым (3) и (4).

Особенности задач нелинейного программирования

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

  1. Прямые методы — методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек – решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
    Недостаток: трудно получить свойство глобальной сходимости.
    Задачи с ограничениями в виде равенств.
    Метод замены переменных (МЗП)
  2. Двойственные методы — методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
    Недостаток: не дают решения исходной задачи в ходе решения – оно реализуемо лишь в конце итерационного процесса.
    • Метод множителей Лагранжа (ММЛ)
    • Методы штрафов
    • Метод множителей
    • Методы линеаризации для задач условной оптимизации
      Алгоритм Франка–Вульфа
      Метод допустимых направлений Зойтендейка
    • Метод условного градиента
    • Метод проекции градиента
    • Сепарабельное программирование.
    • Квадратичное программирование

Методы поиска нулей функции

  1. Метод Ньютона (Метод касательных)
  2. Метод хорд
  3. Комбинированный метод
  4. Метод итераций
  5. Метод секущих

Методы минимизации функций

Функция одной переменной

Функция двух переменных

  1. Матрица Гессе. . Позволяет ответить на вопрос является ли функция выпуклой или вогнутой, а также определить тип экстремума (минимум или максимум).
  2. Производные второго порядка
  3. Экстремум функции двух переменных.

Методы прямого поиска

  1. Метод Хука–Дживса
  2. Метод сопряженных направлений (метод Пауэлла). Найти минимум целевой функции методом сопряженных направлений: f(x)=3x1 – x1 3 + 3x2 2 + 4x2. x 0 =(0.78;1)

Градиентные методы

  1. Метод наискорейшего спуска (метод Коши).
  2. Метод Ньютона
  3. Метод Марквардта. Найти минимум функции: y=x1 2 +4x2 2 +x1x2+1-5x2 методом Марквардта с начальной точкой (10;10) и εxy= ε|f(x)|=0.5. Предельное число итераций равно M=5.
  4. Метод сопряженных градиентов (метод Флетчера-Ривса).
  5. Метод Бройдена–Флетчера–Гольдфарба–Шанно (квазиньютоновские методы).
Читать еще:  Clipper язык программирования

Нелинейное программирование

Прямые методы

  1. Метод множителей Лагранжа. В задачах 301-320 используя метод множителей Лагранжа найти точки экстремума функции z=f(x,y) при заданном условии: z=xy+7x , 2x+y=1
  2. Условия Куна-Таккера.

Метод проекции градиента.
Метод условного градиента.

Методы линеаризации для задач условной оптимизации

Методы перебора применимы для отыскания экстремумов унимодальных целевых функций. Действие любого из методов поиска заключается в сужении области поиска экстремума (длины l 0):
а) до области заданной длины (e> 0), проводя минимальное число измерений значений функции (методы дихотомии, золотого сечения);
б) до наименьших возможных размеров ln при заданном числе измерений n (метод Фибоначчи).
Первая формулировка целесообразна в том случае, если с каждым измерением связаны значительные затраты средств или времени, однако на поиск отпускаются неограниченные средства, которые мы все же стремимся минимизировать; вторая – когда исследователь располагает ограниченными средствами и, зная расходы, связанные с каждым измерением, стремится получить наилучший результат.

Классические методы нахождения экстремумов функций предполагают, что целевые функции непрерывные и гладкие. Для существования точки экстремума должны выполняться необходимые и достаточные условия. Необходимыми условиями существования экстремума являются требования обращения в нуль частных производных первого порядка целевой функции по каждой из переменных. Точка, найденная из необходимых условий, называется стационарной (подозрительной на оптимальную). В качестве стационарных точек могут быть точки перегиба, седловые точки и др. Поэтому необходим учет достаточных условий нахождения экстремумов функций. Он сложен для функций многих переменных как в алгебраическом, так и в вычислительном плане. Так в случае функции двух переменных достаточным условием существования экстремума будет положительная определенность матрицы А размером 2×2 (условие Лежандра-Клебша), составленной из вторых частных производных функции. Недостатком классического метода дифференциального исчисления является и то, что он дает возможность найти экстремум только в том случае, если он лежит внутри области определения функции. Если экстремум находится на границе области определения, то этот метод становится бессильным.

Методы покоординатного спуска относятся к группе приближенных методов нелинейной оптимизации и направлены на уменьшение трудностей, связанных с отысканием экстремума функции цели со сложной аналитической структурой классическими методами дифференциального исчисления. Суть этих методов заключается в продвижении от исходной точки в области определения функции к точке оптимума итеративно; в методе Гаусса – последовательно по каждой из переменных (покоординатно); в градиентных методах – одновременно по всем переменным в направлении градиента или антиградиента.

Критерием окончания итеративных процедур является равенство нулю всех частных производных целевой функции, или квадрат суммы всех частных производных целевой функции должен быть не более заданного числа e, или разность достигнутого значения целевой функции и значения в предыдущей точке должна быть не более e и другие.

Решить задачу нелинейного программирования онлайн

Задачи математического программирования

max (min) Z = ƒ(x); (6.1)

в которой либо целевая функция (6.1), либо ограничения (6.2), либо и то и другое не линейны, называются нелинейными.

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

Геометрическая интерпретация задач нелинейного планирования аналогична задачам линейного планирования.

Общая постановка задачи нелинейного планирования может быть сформулирована следующим образом: найти параметры Х * (х1, х2,…, хп), обращающих целевую функцию W = ƒ(х1, х2,…, хп) в mах(min) при условии наложенных ограничений

число ограничений меньше числа переменных; и (или) целевая функция, и (или) ограничения представляются нелинейными зависимостями.

Нелинейные задачи составляют широкий класс настолько сложных задач, что до сих пор невозможно разработать общие методы, подобные симплекс-методу в линейном программировании, которые позволяли бы решать любые нелинейные задачи. Но, несмотря на отсутствие универсальных методов, разработаны способы решения специальных классов задач, и прежде всего задач с выпуклыми (вогнутыми) функциями ƒ(х) и φi(x).

Особенности решения задач нелинейного программирования.

При решении задач нелинейного программирования очень важно знать: 1) выпукло или не выпукло множество решений? 2) является ли критериальная функция W = ƒ(х) выпуклой или вогнутой, или не относится ни к тому, ни к другому классу?

Множество выпукло, если оно содержит точки А и В, а так же все точки прямой АВ.

Функция у = ƒ(х), определенная на выпуклом множестве Х, называется выпуклой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается выше его (рис. 6.1. а). Функция у= ƒ(х), определенная на выпуклом множестве Х, называется вогнутой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается ниже его (рис. 6.1. б).

Аналогичные понятия можно привести и для функций многих переменных.

В математике доказывается ряд теорем, которые позволяют определять глобальные экстремумы. Так, для задач, в которых множество допустимых решений выпукло: 1) если ƒ(х) – выпуклая функция, то локальный минимум, определенный на выпуклом множестве Х, совпадает с ее глобальным минимумом на этом множестве; 2) если ƒ(х) – вогнутая функция на заданном выпуклом множестве Х, то локальный максимум ƒ(х) является глобальным.

Решение задач линейного программирования симплекс-методом Калькулятор онлайн

Симплексный метод является универсальным методом решения оптимизационных задач. За исходное решение берётся одно из возможных базисных решений (или «план», «программа»). Затем эта программа улучшается до тех пор, пока не будет найдена оптимальная программа. Наш калькулятор онлайн позволяет решать задачи как на максимум целевой функции, так и на минимум. При решении задач на минимум исходная задача линейного программирования сводится к двойственной задаче. При выполнении этих операций на бумаге часто возникают ошибки, а наш калькулятор онлайн поможет своевременно проверить ошибки.

Читать еще:  Ноутбук dexp безопасный режим

Симплекс метод онлайн

Вычисление происходит за время немногим более секунды. Этот калькулятор находит максимум целевой функции. Если требуется найти минимум целевой функции, то следует воспользоваться калькулятором Решение двойственной задачи линейного программирования.

Как онлайн калькулятор находит решение задачи линейного программирования?

Он выдаёт шаги решения задачи симплекс методом, на которых преобразуется система ограничений и целевая функция. Это значит, что на соответствующем шаге функция цели не принимает оптимального значения и по определённому правилу совершается переход от одной вершины многогранника решений к другой пока функция цели не примет оптимального значения. По шагам решения можно наблюдать, как переменные, которые входят в выражение целевой функции с коэффициентом 0, являются неосновными, а остальные — основными. Таким образом осуществляется перевод переменных в основные и неосновные.

Материалы по теме Линейное программирование

Поделиться с друзьями

Введите данные вашей задачи, и вы получите подробное решение.
Используются лучшие онлайн-калькуляторы интернета.

Математический анализ

Предел

Производная

Производная функции от одной переменной

Производная функции от двух переменных

Производная функции от трех переменных

Производная параметрической функции

Вторая и третья производные

Интеграл

Разложение дроби на сумму элементарных дробей (для метода неопределнных коэффициентов)

Построение графиков

Построение графика функции (2D) в декартовых координатах

Построение графика функции в полярных координатах

Построение графика функции, заданного параметрически

Построение поверхности (3D)

Сумма числового ряда(см. пример…)

Разложение в ряд Фурье

Дифференциальные уравнения:

Линейное однородное уравнение

Линейное неоднородное уравнение

Уравнение в полных дифференциалах

Линейное однородное уравнение второго порядка с постоянными коэффициентами

Линейное однородное уравнения 2-го порядка вида ay»+by’+cy=0 с начальными условиями

Линейное неоднородное уравнение второго порядка с постоянными коэффициентами

Векторная алгебра и аналитическая геометрия

Пирамида. Задача расчета параметров пространственной пирамиды по координатам вершин. Позволяет найти длины ребер, площади граней, объем пирамиды, длины высот, углы между ребрами, углы между гранями, углы между ребрами и гранями.

Получить уравнение прямой по двум точкам

Получить уравнение плоскости по трем точкам

Разложение вектора по базису

Линейная алгебра

Матрицы

Разложение определителя по строке или столбцу

Обратная матрица (метод алгебраических дополнений)

Обратная матрица (метод присоединенной матрицы)

Характеристическое уравнение матрицы

Собственные значения (числа)

Возведение матрицы в степень

Приведение матрицы к треугольному виду

Системы уравнений

Решение системы линейных уравнений методом Крамера

Решение системы линейных уравнений методом Гаусса

Решение системы линейных уравнений методом обратной матрицы (матричный метод)

Любая система уравнений

Теория вероятностей и математическая статистика

Биномиальное распределение: расчет Pn(k) при данных p и n

Гистограмма: группировка результатов эксперимента, подсчет частот

Обработка выборки (простой статистической совокупности) — будут построены: статистические ряды частот, полигоны частот, гистограмма, функция распределения, найдены точечные оценки математического ожидания и дисперсии.

Особенности задач нелинейного программирования

Обработка группированного ряда абсолютных частот — будут построены: статистические ряды относительных частот, полигоны частот, гистограмма, функция распределения, найдены точечные оценки математического ожидания и дисперсии. ( см.пример…)

и – функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных , называемых множителями Лагранжа, и составляют функцию Лагранжа

находят частные производные

и рассматривают систему n + m уравнений

(15.3)

с n + m неизвестными , . Решив систему уравнений (15.3), получают все точки, в которых функция (15.1) может иметь экстремальные значения.

решение задачи нелинейного программирования онлайн

Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (15.3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции при ограничениях

Составим функцию Лагранжа:

Продифференцируем ее по переменным . Приравнивая полученные выражения к нулю, получим следующую систему уравнений:

Из второго и третьего уравнений следует, что ; тогда

Решив данную систему, получим:

и

Сервис для решения задач по линейному программированию

Пример №2. Решение задачи линейного программирования графическим методом.
Функция достигает наименьшего значения в точке

при следующих ограничениях:

Точки, координаты которых удовлетворяют одновременно всем неравенствам системы ограничений, называются областью допустимых решений.

Очевидно, для нахождения области допустимых решений данной задачи, необходимо последовательно рассмотреть каждое неравенство. (см. шаг 1 — шаг 4)

Последние два шага (см. шаг 5 — шаг 6) служат непосредственно для получения ответа.

Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче.

По условию задачи: x1 ≥ 0 x2 ≥ 0.

Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке (вся первая четверть).

Рассмотрим неравенство 1 системы ограничений.

Построим прямую: x1 + 2 x2 = 8

Найдены коородинаты двух точек (0, 4) и (8 ,0). Соединяем их и получаем необходимую прямую (1).

Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x2

Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (1).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Рассмотрим неравенство 2 системы ограничений.

Найдены коородинаты двух точек (0, -2) и (2 ,0). Соединяем их и получаем необходимую прямую (2).

Нас интересуют точки расположенные выше или ниже построенной прямой (2) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x2

Читать еще:  Программирование алгоритмов разветвляющейся структуры

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (2).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Рассмотрим неравенство 3 системы ограничений.

Построим прямую: x1 + 2 x2 = 4

Найдены коородинаты двух точек (0, 2) и (4 ,0). Соединяем их и получаем необходимую прямую (3).

Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x2

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Рассмотрим неравенство 4 системы ограничений.

Построим прямую: x1 = 1

Данная прямая параллельна оси OX2 и проходит через точку (1,0) (4)

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные правее построенной прямой (4).

Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.

Строим вектор C = (2, 2), координатами которого являются коэффициенты функции F.

Будем перемещать «красную» прямую, перпендикулярно вектору C , от левого нижнего угла к правому верхнему.

В точке, в которой «красная» прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения.

В точке, в которой «красная» прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения.

Функция F достигает наименьшего значения в точке A. (см. рисунок)

Найдем координаты точки A.
Точка A одновременно принадлежит прямым (3) и (4).

Графический метод решения задач нелинейного программирования.

Рассмотрим примеры решения задач нелинейного програм­мирования с двумя переменными, причем их целевые функции и системы ограничений могут быть заданы в линейном и не­линейном виде. Так же как и в задачах линейного программи­рования, они могут быть решены графически.

2.1. Задача с линейной целевой функцией и нелинейной системой ограничений

Пример 1. Найти глобальные экстремумы..

Целевая функция . Ограничения:

Решение. Область допустимых решений — часть окруж­ности с радиусом 4, которая расположена в первой четверти.

Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным -2.

Глобальный минимум достигается в точке O (0, 0), глобальный максимум — в точке А касания линии уровня и окружности. Проведем че­рез точку А прямую, перпендикулярную линии уровня.

Прямая проходит через начало координат, имеет угловой коэффициент 1/2 и уравнение x2 = 1/2х1.

Решение системы, очевидно:

х1 = 8 /5, x2 = 4 /5, при этом L = 16 /5 + 4 /5 = 4 .

Ответ. Глобальный минимум, равный нулю, достигается в точке O (0, 0), глобальный максимум, равный 4 , — в точке А(8 /5, 4 /5).

2.2. Задача с нелинейной целевой функцией и линейной системой ограничений

Пример 2. Найти глобальные экстремумы.

Целевая функция Ограничения:

Решение. Область допустимых решений – фигура OABD .

Линиями уровня будут окружности с центром в точке O1. Максимальное значение целевая функция имеет в точке D(9, 0), минимальное — в точке O1 (2, 3). Поэтому

Ответ. Глобальный максимум, равный 58, достигается в точке D (9, 0), глобальный минимум, равный нулю, — в точке O1 (2, 3).

Пример 3. Найти глобальные экстремумы:

Целевая функция

Ращение. Область допустимых решений фигура OABD. Линии уровня представляют собой окружности с центром в точке O1 (6, 3).

Глобальный максимум находится в точке О(0,0) как самой удаленной от точки O1.

Глобальный минимум расположен в точке Е, находящейся на пересечении прямой 3x1 + 2x2 = 15 и перпендикуляра к этой прямой, про­веденного из точки O1.

Найдем координаты точки Е: так как угловой коэффици­ент прямой 3x1 + 2x2 = 15 равен -3/2, то угловой коэффициент перпендикуляра O1Е равен 2/3. Из уравнения прямой, прохо­дящей через данную точку О2 с угловым коэффициентом 2/3, получим

Решая систему находим координаты точки Е: х1 = 51/13, x2 = 21/13, при этом L(Е) = 1053/169.

Координаты точки Е можно найти и другими способами, например, дифференцируя выражение (x1 — 6) 2 + (x2 — 3) 2 как неявную функцию по x1, получим искомые координаты.

Приравниваем полученное значение к тангенсу угла накло­на прямой: 3x­1 + 2x2 = 15, откуда получим, что

x2=-3/2x1+15/2, tgx=-3/2.

Решаем систему уравнений получим координаты точки Е: х1 = 51/13, x2 = 21/13.

Можно воспользоваться формулой нахождения расстояния от данной точки до данной прямой.

Ответ: Глобальный максимум, равный 52, находится в точке O (0, 0). Глобальный минимум, равный 1053/169, нахо­дится в точке E (51/13, 21/13).

2.3.Задача с нелинейной целевой функцией и нелинейной системой ограничений

Пример 4. Найти глобальные экстремумы функции

при ограничениях:

Решение. Областью допустимых решений является ок­ружность с радиусом 4, расположенная в первой четверти (рис. 28.4). Линиями уровня будут окружности с центром в точке O1 (2, l).

Глобальный минимум достигается в точке O1. Глобальный максимум — в точке А (0, 4), при этом

Ответ. Глобальный минимум, равный нулю, достигается в точке O1 (2, l), глобальный максимум, равный 13, находится в точке А (0, 4).

Пример 5. Найти глобальные экстремумы

Область допустимых решений не является вы­пуклой и состоит из двух частей. На рисунке эта область представляет собой прямоугольник, без внутренней части, заключенной между гиперболой и прямой линей.

Линиями уровня являются окружности с центром в точке O (0, 0).Найдем координаты точек А и В, решая систему

Получим А (1, 4), В (4, 1). В этих точках функция имеет гло­бальные минимумы, равные 17. Найдем координаты точек D и Е, решая системы

Откуда получаем D (2/3, 6) и L(D) = 328/9, E (7, 4/7) и L(E) = 2417/49.

. Ответ. Целевая функция имеет два глобальных миниму­ма, равных 17, в точках А (1, 4) и B (4, 1), глобальный макси­мум, равный 2417/49, достигается в точке E (7, 4/7).

IT Новости из мира ПК
Добавить комментарий