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

Введение

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных 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. Метод искусственного базиса

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--