- •Тема 1 : «Математическое моделирование в оптимизации»
- •1.1. Введение
- •1.1.Постановка задачи оптимизации
- •1.2. Классификация задач оптимизации
- •1.2.1. Задача безусловной оптимизации
- •1.2.2 Задача условной оптимизации
- •1.2.3. Задача математического программирования
- •1.3. Математическое моделирование в оптимизации
- •1.4. Примеры задач оптимизации
- •2.1. Формы записи задачи линейного программирования
- •2.2. Способы преобразования форм записи злп
- •2.3. Графический метод решения злп
- •3.1.Многоугольники и многогранники
- •3.2. Экстремум целевой функции
- •3.3.Опорное решение злп, его взаимосвязь с угловыми точками
- •3.4. Жордановы преобразования систем линейных уравнений
- •3.5. Симплексный метод решения задачи линейного программирования
- •3.6. Метод искусственного базиса
- •4.1.Виды математических моделей двойственных задач.
- •4.2. Общие правила составления двойственных задач
- •4.3.Перая теорема двойственности
- •4.4.Нахождение решения двойственной задачи по известному решению
- •4.5. Вторая теорема двойственности
- •4.6. Двойственный симплексный метод
- •5.1. Постановка задачи нелинейного программирования
- •5.2. Классические методы оптимизации
5.1. Постановка задачи нелинейного программирования
Во многих экономических задачах зависимости между постоянными и переменными лишь в первом приближении можно считать линейными, более детальное рассмотрение позволяет обнаружить их нелинейность. Как правило, такие показатели, как прибыль, себестоимость, капитальные затраты на производство , в действительности зависят от объема производства, расхода и т.п. нелинейно.
Оптимизационную задачу нелинейного программирования можно сформулировать в общем случае: найти переменные х1,х2,...,хп, удовлетворяющие системе неравенств (уравнений)
i (x1,x2,…,xn) bi, i=1,2,…,k,
i (x1,x2,…,xn) = bi, i=k+1,…,m. (1)
и обращающие в минимум или максимум целевую функцию
Z = f (x1,x2,…,xn), (2)
где f u i некоторые нелинейные функции.
5.2. Классические методы оптимизации
Можно выделить класс нелинейных задач, которые относятся к классическим методам оптимизации. Допустим, что среди ограничений (1) нет неравенств, не обязательны условия неотрицательности, переменные не являются дискретными, т<n, функции f(x), i(x) непрерывны и имеют частные производные по крайней мере второго порядка. В этом случае задачу оптимизации можно сформулировать так: найти переменные х1,х2,...,хп, удовлетворяющие системе уравнений
i (x1,x2,…,xn) = bi , i=1,2,…,m (3)
и обращающие в максимум (минимум) целевую функцию
Z = f(x1,x2,…,xn) (4)
Такие задачи можно решать классическими методами дифференциального исчисления. Однако, на этом пути встречаются такие вычислительные трудности, которые делают необходимым поиск других методов решения. Поэтому классические методы используются не в качестве вычислительного средства, а как основа для теоретического анализа.
Будем полагать, что функция Z=f(х1,х2,...,хп)=f(X) дважды дифференцируема в точке Х*= (х1*,х2*,...,хп*) (X*D(f). Если для всех точек Х этой окрестности f (X*) f (X) или f (X*) f (X), то говорят, что функция f (X) имеет экстремум в точке Х*.
Определение 1. Точка Х*X называется точкой локального минимума (локального максимума), если надеется 0, такое что:
f (X*) f (X) при ||X-X*|| < (f (X) f (X*) при ||X-X*||<)
Определение 2. Точка Х*Х называется точкой глобального минимума (глобального максимума) функции f (x) на Х, если:
f (X*) f (X) XX (f (X* f (X) XX).
Определение 3.Точка Х*, в которой все частные производные функции f (X) равны нулю, называется стационарной точкой.
Необходимое условие экстремума: если в точке Х* функция z=f (X) имеет экстремум, то частные производные функции в этой точке равны нулю. Следовательно, точки экстремума функции z=f(x) системе уравнений
Для получения достаточных условий можно использовать критерий Сильвестра.
Определение 4. Матрицей Гессе называется квадратная матрица, составленная из вторых частных производных функции f (X) по всем переменным, матрица имеет размерность пп , где п-число переменных функции:
Н(Х)
=
Критерий Сильвестра:
Матрица Н(Х) называется положительно определенной, если все ее диагональные миноры положительны; отрицательно определенной, если они чередуют знак, начиная с «-».
Определение 5. Задача поиска всех минимумов и максимумов целевой функции называется задачей поиска экстремумов.
Множество точек экстремума может содержать конечное число точек
