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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Калькулятор симплекс-метода

Выполнено действий: 152

Как пользоваться калькулятором

• Задайте количество переменных и ограничений
• Введите коэффициенты целевой функции
• Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
• Выберите тип решения
• Нажмите кнопку «Решить»

Что умеет калькулятор симплекс-метода

• Решает основную задачу линейного программирования
• Позволяет получить решение с помощью основного симплекс-метода и метода искусственного базиса
• Работает с произвольным количеством переменных и ограничений

Что такое симплекс-метод

Задача линейного программирования — это задача поиска неотрицательных значений параметров, на которых заданная линейная функция достигает своего максимума или минимума при заданных линейных ограничениях.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Алгоритм является универсальным методом, которым можно решить любую задачу линейного программирования.

Если вам тоже ничего не понятно из этого определения, то вы на верном пути. Чаще всего статьи про симплекс-метод очень сильно углубляются в дебри теории задачи линейного программирования, из-за чего очень легко потерять суть и так ничего и не понять. Мы постараемся описать алгоритм симплекс-метода так, чтобы показать, что в нём нет ничего страшного и на самом деле он весьма простой. Но сначала нам всё-таки потребуется ввести несколько определений.

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c₁·x₁ + c₂·x₂ + . + c_n·x_n

Ограничение — условие вида a₁·x₁ + a₂·x₂ + . + a_n·x_n v b , где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x₁ . x_n.

Алгоритм решения основной задачи ЛП симплекс-методом

Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду — виду, в котором все условия задаются равенствами. Для этого предварительно все неравенства с ≥ умножаются на -1, для получения неравенств с ≤.

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

Формирование начального базиса

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

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

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

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₆
Столбец 4 является частью единичной матрицы. Переменная x₄ входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x₅ , предварительно разделив третью строку на 2.
Симплекс-таблица

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

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

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

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

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

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

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

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

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

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

х₁ = 8 /5, x₂ = 4 /5, при этом L = 16 /5 + 4 /5 = 4 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x₂=-3/2x₁+15/2, tgx=-3/2.

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

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

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

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

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

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

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

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

Ответ. Глобальный минимум, равный нулю, достигается в точке O₁ (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).

Математика. Нелинейное программирование

Для просмотра онлайн кликните на видео ⤵

Задача нелинейного программирования Подробнее

Cимплексный метод решения задачи линейного программирования (ЗЛП) Подробнее

Нелинейное программирование 1 Подробнее

Лекция 1 Графический метод решения задач линейного программирования Подробнее

Графический метод решения задачи линейного программирования (ЗЛП) Подробнее

Графический метод решения задач оптимизации Подробнее

Нелинейное программирование 2 Подробнее

Лекция 2: Задача линейного программирования. Задача о ресурсах Подробнее

Нелинейное программирование. Часть 3 Подробнее

Нелинейное программирование. Часть 4 Подробнее

Поиск решения в Excel Подробнее

Метод Гаусса и метод Жордана-Гаусса Подробнее

Решение задачи о распределении ресурсов с помощью Поиска решений Подробнее

Транспортная задача (открытая, без цикла). Метод потенциалов — подробно и понятно Подробнее

Решение задачи линейного программирования при помощи надстройки Поиск решения Подробнее

Метод Жордана-Гаусса (метод прямоугольников). Видеоурок Подробнее

Решение системы уравнений графическим способом #РешитьСистемуГрафически #СистемаУравнений Подробнее

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

Министерство науки и образования Республики Казахстан

Талдыкорганский политехнический колледж

«Моделирование производственных и экономических процессов»

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

г. Талдыкорган 2007 г.

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x₁ , x₂ ,…, x_n ) при ограничениях g_i (x₁ , x₂ ,…, x_n ) b_i , где g_i – функция, описывающая ограничения, а b_i – действительное число, i = 1,…, m. Функция f называется функцией цели (целевой функцией).

В общем, виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f(x₁ , x₂ , …, x_n ) при условии, что ее переменные удовлетворяют соотношениям:

где f и g – некоторые известные функции n переменных, а b_i – заданные числа.

В результате решения задачи будет определена точка Х * = (x₁ * , x₂ * , …, x_n * ), координаты которой удовлетворяют соотношениям и такая, что для всякой другой точки Х= (x₁ , x₂ , …, x_n ), удовлетворяющей условиям, выполняется неравенство f (x₁ * , x₂ * , …, x_n * ) ≥ f (x₁ , x₂ , …, x_n ) [f (x₁ * , x₂ * , …, x_n * ) ≥ f (x₁ , x₂ , …, x_n )].

Если f и g_i – линейные функции, то задача является задачей линейного программирования.

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

В евклидовом пространстве Е_n система ограничений определяет область решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Если определена область допустимых решений, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наименьшего) уровня: f (x₁ , x₂ , …, x_n ) = h. Указанная точка может находиться как на границе области допустимых решений, так и внутри неё.

Процесс нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации включает следующие этапы:

1. Находят область допустимых решений задачи, определяемую соотношениями (если она пуста, то задача не имеет решения).

2. Строят гиперповерхность f (x₁ , x₂ , …, x_n ) = h.

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

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

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

Задача является задачей линейного программирования, а следовательно, ее решение можно найти известными методами: 1) графический; 2) табличный (прямой, простой) симплекс – метод; 3) метод искусственного базиса; 4) модифицированный симплекс – метод; 5) двойственный симплекс – метод.

1. Табличный симплекс-метод

Для его применения необходимо, чтобы знаки в ограничениях были вида «меньше либо равно», а компоненты вектора b – положительны.

Алгоритм решения сводится к следующему:

1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

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

3. Формируется симплекс – таблица.

4. Рассчитываются симплекс – разности.

5. Принимается решение об окончании либо продолжении счёта.

6. При необходимости выполняются итерации.

7. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана – Гаусса или каким-нибудь другим способом.

2. Метод искусственного базиса

Данный метод решения применяется при наличии в ограничении знаков «равно» больше либо равно» меньше либо равно и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами, а в задачи минимизации – с положительными. Таким образом, из исходной задачи получается новая задача.

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

3. Модифицированный симплекс-метод

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

В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Способность хороша для ситуаций, когда число переменных n значительно превышает число ограничений m.

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

Зная оптимальный план этой задачи, на основе соотношений получаем оптимальный план исходной задачи.

Таким образом, процесс нахождения решения задачи нелинейного программирования включает следующие этапы:

1. Первоначальную задачу сводят к задаче линейного программирования.

2. Находят решение линейной задачи

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

Первый этап: Получение задания к курсовой работе

1. Все числовые данные, касающиеся предполагаемых производственных и экономических процессов, берутся на основе шестизначного шифра:

Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде:

из последней строки таблицы индивидуальных заданий находим столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а – том столбце в строке 9, b – том столбце в строке 5, c – том столбце в строке 5, d – том столбце в строке 8 , e – том столбце в строке 7 и f – том столбце в строке 2.

По таблице исходных заданий для любого варианта заданий по столбцу а исполнитель получает вариант выполняемого задания. В моем случае для цифры 9 соответствует вариант 9.

На некотором заводе производится три вида продукта и при этом расходуется два вида ресурсов. Производственная функция каждого вида продукта на предприятии опишется равенствами:

где С_i и — постоянные величины, i = 1, 2, 3;

X₁ – трудовые ресурсы в человеко-днях;

Х₂ – денежно-материальные средства, в тенге;

У_i – получаемый продукт

Найти все неотрицательные базисные решения и определить оптимальный план F = y₁ + y₂ + y₃ .

Известно, что продукт для производства j – того вида затрачивается a_ij единиц i – того ресурса. Эти затраты даются в таблицах 3.9.1. – 3.9.10

Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11.

2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица: