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

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

Курсовая работа

По предмету:

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

На тему:

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

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

Введение

 

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

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

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

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

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

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

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

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

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

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

2.   Строят гиперповерхность f (x1, x2, …, xn) = h.

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

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

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

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

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

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

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

1. ............