Методы оптимизации и исследование операций

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ

ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ»

(НИУ «БЕЛГУ»)

ИНСТИТУТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ И ЕСТЕСТВЕННЫХ НАУК

КАФЕДРА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ

ОТЧЕТ

 ПО ЛАБОРАТОРНОЙ РАБОТЕ №1

МЕТОДЫ ОПТИМИЗАЦИИ И ИСЛЕДОВАНИЕ ОПЕРАЦИЙ

Вариант 14

Выполнила: Корсева Надежда (07001301)

Проверила: Болгова Евгения Витальевна

Белгород 2016

Теоретическая часть

Постановка задачи оптимизации: заданы множество X и функция [pic 1], определенная на Х; требуется найти точки минимума или максимума функции f на X.

Задачу на минимум запишем в виде

[pic 2], [pic 3].                                         (1)

При этом f будем называть целевой функцией, X — допустимым множеством, любой элемент [pic 4] — допустимой точкой задачи (1). 

Далее будем изучать конечномерные задачами оптимизации, т.е. задачами, допустимое множество которых лежит в евклидовом пространстве .

Точка [pic 5] называется:

1) точкой глобального минимума функции f на множестве X или глобальным решением задачи (1), если

f ([pic 6]) ≤ f (x) при всех [pic 7];                                         (2)

2) точкой локального минимума f на X или локальным решением задачи (1.1), если существует число ε > 0 такое, что

f ([pic 8]) ≤ f (x) при всех [pic 9],                                 (3)

где [pic 10] — шар радиуса [pic 11] с центром в [pic 12]. Если неравенство в (2) или (3) выполняется как строгое при [pic 13], то говорят, что [pic 14] — точка строгого минимума (строгое решение) в глобальном или локальном смысле.

По аналогии с (1) будем записывать задачу максимизации функции f на множестве X в виде

[pic 15], [pic 16].                                                 (4)

Заменяя в данных выше определениях слово «минимум» на «максимум» и заменяя знак неравенств в (2), (3) на противоположный, получаем соответствующие понятия для задачи (4).

Решения задач (1), (4), т.е. точки минимума и максимума функции f на X, называют также точками экстремума, а сами задачи (1), (4) — экстремальными задачами.

Ясно, что задача (4) эквивалентна задаче

[pic 17], [pic 18],

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

Теорема 1 (Вейерштрасса). Пусть X — компакт в  [pic 19], f - непрерывная функция на X. Тогда точка глобального минимума функции f на X (глобальное решение задачи (1)) существует. В дальнейшем окажется полезной и несколько иная форма данной теоремы

Практическая часть

Задания лабораторной работы

При выполнении заданий лабораторной работы все вычисления следует реализовать с помощью циклов for и while (в отличие от примеров, выполненных на основе матричных операций Matlab).

Задание 1. Вычислить минимальное значение двумерной функции [pic 20] в области [pic 21] на основе полного перебора ее значений в данной области с фиксированным шагом [pic 22]по каждой из переменных, используя следующие способы: