Тема 4. Оптимизация и линейное программирование

4.1. Постановка задачи и классификация методов

Для исследования многих инженерно-технических и экономических процессов сначала составляют математическую модель в виде математической задачи, а затем используют численные методы для ее решения. Очень часто это приводит к необходимости решать задачу нелинейного программирования (НЛП), состоящую в нахождении таких значений переменных x=(x₁,x₂,…,x_n), при которых достигается минимум целевой функции

f(x₁,x₂…,x _n) → min (4.1)

И выполняются ограничения:

G1(x1,x2,…,x n) <0

g₂(x₁,x₂,…,x _n ) 0 (4.2)

………

g_m(x₁,x₂,…x _n ) < 0

где хотя бы одна функция f, g_1, g₂,… - нелинейная (возможны также ограничения в виде равенств). На переменные x могут быть наложены ограничения неотрицательности. Если все эти функции линейные, то мы имеем дело с задачей линейного программирования (ЛП), для решения которой разработаны специальные методы.

Функция (4.1) называется целевой. Вектор х называется допустимым, если он удовлетворяет ограничениям (4.2). Вектор х называется оптимальным решением задачи (4.1)-(4.2), если х является допустимым и f(x₁,x₂,…,x_n) достигает минимума. Задача оптимизации может быть поставлена и на нахождение максимума целевой функции:

F(x₁,x₂,…,x_n) max,

Но она легко может быть сведена к задаче (4. 1):

f(x₁,x₂,…,x_n)= - F(x₁,x₂,…x_n) min

поэтому в дальнейшем будем рассматривать лишь задачу минимизации.

Термин “оптимальный” имеет латинское происхождение и означает “наилучший, наиболее благоприятный”. С математической точки зрения оптимизационная задача - это задача, в которой требуется найти оптимум (максимум или минимум) некоторой величины при выполнении каких-либо условий [6]. Переменные (x₁,x₂, …, x_n) могут быть конструктивными параметрами, установками регулятора, показаниями измерительных приборов и т.д., тогда как целевая функция может представлять собою стоимость, вес, годовой доход и т.д., а ограничения - технические требования, условия работы, пропускную способность…

В последнее время оптимизационные задачи привлекают особое внимание математиков. Разрабатываются новые численные методы оптимизации, хорошо приспособленные для реализации их с помощью компьютеров. Это вызвано, прежде всего, потребностями жизни, практики, постановками задач новых типов. На первый план выводят задачи, связанные с экономным расходом металла, энергии, увеличением прибыли и т.д., математическим образом которых и являются оптимизационные задачи. Разработкой методов решения подобных задач занимается область математики, называемая математическим програмированием. Однако до настоящего времени общих методов решения произвольной задачи НЛП не существует. Для различных классов задач, связанных с определенными видами целевой функции и структурой ограничений, разработаны разные классы методов:

- методы линейного программирования;

- методы динамического программирования (когда ограничения включат в себя как параметр время);

- методы выпуклого программирования (когда целевая функция и функции ограничений выпуклы);

- методы стохастического программирования (когда в задаче есть вероятностный параметр);

- методы геометрического программирования;

- комбинаторные и эвристические методы.

Условно классификацию оптимизационных задач (и связанных с ними методов) можно провести следующим образом:

а) в зависимости от вида функции:

- линейные и нелинейные;

- выпуклые и невыпуклые;

б) по используемости в решении производных: - не использующие производные (метод покоординатного спуска);

- использующие 1 производную (градиентный метод);

- использующие 2 производную (метод Ньютона);

в) в зависимости от наличия ограничений:

- задачи с ограничениями;

- задачи без ограничений;

г) в зависимости от количества переменных:

- c одной переменной;

- со многими переменными;

д) в зависимости от количества экстремумов:

- одноэкстремальные;

- многоэкстремальные.

Геометрически целевая функция (4.1) определяет собой поверхность, а ограничения (4.2) –допустимое множество решений n -мерного Эвклидова пространства (допустимую область - ДО).. Нахождение решения задачи нелинейного программирования сводится к нахождению точки из допустимого множества, в которой f(x) достигает экстремума (минимума). Решение может находиться либо внутри области, либо на ее границе. Следующая теорема дает необходимые и достаточные условия существования решения задачи.

Теорема. Если целевая функция непрерывна, а допустимое множество замкнутое, непустое и ограниченное, то решение задачи (4.1)-(4.2) существует.

Не нашли, что искали? Воспользуйтесь поиском: