Министерство науки и образования Республики Казахстан
Талдыкорганский политехнический колледж
Курсовая работа
По предмету:
«Моделирование производственных и экономических процессов»
На тему:
«Решение задач нелинейного программирования»
г. Талдыкорган 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. ............
