Введение в теорию оптимизации и линейное программирование

Введение в теорию оптимизации и линейное программирование

Цель работы: Знать основные понятия теории оптимизации и линейного программирования.

Задание: Составить теоретический отчет о базовых понятиях теории оптимизации и линейного программирования.

Краткие теоретические сведения:

Понятие оптимизации (оптимальности)

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

Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

Классификация методов оптимизации:

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

· Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

· Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1) детерминированные;

2) случайные (стохастические);

3) комбинированные.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации.

 

Оптимальное решение, необходимые условия существования оптимальности.

Оптимальное (от лат. optimus — наилучшее) решение — решение, которое по тем или иным признакам предпочтительнее других.

В технике оптимальный (вариант, решение, выбор и т. д.) — наилучший (вариант, решение, выбор) среди допустимых при наличии правила предпочтения одного другому. Такое правило называется критерием оптимальности, а мерой предпочтения будут служить показатели качества. Можно говорить об оптимальном варианте только при удовлетворении двух условий:

1) наличия хотя бы одного критерия,

2) наличия не менее двух сравниваемых вариантов (необходимость осуществления выбора).

 

Целевая функция.

Целевая функция — вещественная или целочисленная функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации) в целях решения некоторой оптимизационной задачи. Термин используется в математическом программировании, исследовании операций, линейном программировании, теории статистических решений и других областях математики в первую очередь прикладного характера, хотя целью оптимизации может быть и решение собственно математической задачи. Помимо целевой функции в задаче оптимизации для переменных могут быть заданы ограничения в виде системы равенств или неравенств. В общем случае аргументы целевой функции могут задаваться на произвольных множествах.

 

1.5 Экстремум функции, локальный и глобальный экстремум (описание и примеры).

Экстре́мум (лат. extremum — крайний) в математике — максимальное или минимальное значение функции на заданном множестве. Точка, в которой достигается экстремум, называется точкой экстремума. Соответственно, если достигается минимум — точка экстремума называется точкой минимума, а если максимум — точкой максимума. В математическом анализе выделяют также понятие локальный экстремум (соответственно минимум или максимум).

Значение функции в точке максимума называется локальным максимумом, значение функции в точке минимума - локальным минимумом данной функции. Локальные максимум и минимум функции называются локальными экстремумами.

Точка называется точкой строгого локального максимума функции , если для всех из окрестности этой точки будет справедливо строгое неравенство .

Точка называется точкой строгого локального минимума функции , если для всех из окрестности этой точки будет справедливо строгое неравенство .

Наибольшее или наименьшее значение функции на промежутке называется глобальным экстремумом.

 

Линейное программирование

Вывод:

Узнал основные понятия теории оптимизации и линейного программирования.

 

Введение в теорию оптимизации и линейное программирование

Цель работы: Знать основные понятия теории оптимизации и линейного программирования.

Задание: Составить теоретический отчет о базовых понятиях теории оптимизации и линейного программирования.

Краткие теоретические сведения: