- •Государственный комитет рсфср по делам науки и высшей школы
- •Введение
- •Лабораторная работа I одномерная оптимизация
- •Постановка задачи
- •Краткие общие сведения Метод Пассивного поиска
- •Метод Фибоначчи
- •Метод золотого сечения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 3 симплексный метод
- •Постановка задачи
- •Краткие общие сидения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 4 решение прямой и двойственной задач
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Тексты исходных задач Вариант I
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Лабораторная работа 5 транспортная задача
- •Постановка задачи
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 6 задача 0 коммивояжере
- •Постановка задачи
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Содержание
- •197376, Санкт-Петербург, ул. Проф. Попова, 5
Порядок проведения лабораторной работы
Работа выполняется в диалоговом режиме.
Номер варианта, сообщаемый в ответ на запрос, задает некото-рую конкретную функцию, минимум которой необходимо найти, и количество допустимых испытаний.
Аналитическое представление этой функции студенту неизвестно. Задача студента заключается в том, чтобы для каждого из описанных выше методов:
а) последовательно указать точки вычисления функции (для метода пассивного поиска точки должны быть упорядочены в порядке возрастания);
б) указать длину , и границы заключительного интервала неопре-деленности.
В помощь студенту на экран выводится следующая информация:
- для метода пассивного поиска: при неверно введенном значе-нии xkвыводится сообщение об этом, после чего ввод должен быть повторен;
- для методов Фибоначчи и золотого сечения выводится график со значениями функций в уже выбранных точках; ниже графика выво-дятся сами точки в порядке указания; при неверном выборе очеред-ной точки выводится соответствующее сообщение, после чего ввод должен быть повторен.
- 7 -
Требования к отчету
Отчет должен содержать:
а) постановку решаемой задачи;
б) последовательность выбранных для испытаний точек и обоснование такого выбора;
в) длину и границы заключительного интервала неопределеннос-ти;
г) ответы на контрольные вопросы.
Контрольные вопросы
1. В чем отличия в постановке задач, решаемых методами пассивного поиска, золотого сечения и методом Фибоначчи?
2. Как оценить скорость изменения интервала неопределенности в методах одномерной минимизации?
3. Чему равен выигрыш от использования метода золотого сечения по сравнению с методом пассивного поиска при n = 10?
Лабораторная работа 2
МНОГОМЕРНАЯ МИНИМИЗАЦИЯ
Цель работы. Исследование алгоритмов безусловной минимизации гладких функций нескольких переменных.
Постановка задачи
Для заданной функции ƒ(x1,...,xn)найти ее точку минимумаx*с заданной точностью ε. Для поиска минимума воспользоваться различными методами минимизации, описываемыми ниже.
Краткие общие сведения. Градиентный метод с постоянным шагом
Общая схема метода следующая:
по заданному значению x0 -вектору начального приближения -вычисляются последовательно значения x1,x2,... по формуле:
- 8 -
где - вектор частных произ- водных функции ƒ1по координатамх1, ..., x2, вычисленный в точке.
Метод наискорейшего спуска
Отличие этого метода от градиентного метода с постоянным ша-гом заключается в способе вычисления параметра αk наk-м шаге алгоритма:
xk+1 = xk – αk ∙ grad ƒ(xk),
αk=argmin { ƒ( xk – α ∙ grad ƒ(xk)) : α > 0 }
Т.е. на каждом шаге используется дополнительная процедура одномерной минимизации (поиска точки локального минимума функции одного аргумента).
Метод Ньютона-Рафсона
Этот метод используется для вычисления точки локального минимума функции и переменных, обладающей третьими производными по всем переменным. Последовательность { x1, x2, ...} приближений к стационарной точке строится по формуле:
где
- nxn- матрица Гессе
функции ƒ в точке xk.
Порядок проведения лабораторной работы
Работа осуществляется в диалоговом режиме с помощью программы. Описанные выше методы исследуются на примере задачи минимизации квадратичной функции двух переменных ƒ(x) = ƒ(x1,x2):
ƒ(x) = XTAX + BTX + C.
- 9 -
Параметры минимизируемой функции - 2х2 - матрица А, 2-векторВи скалярС -задаются студентом по указанию преподавателя.
В задачу студента входят:
а) определение начального вектора x0и величины шага α, при котором значения ƒ(x1), ƒ(x2), ..., определенные градиентным методом с постоянным шагом, убывают;
б) проведение минимизации заданной функции методами наискорейшего спуска и Ньютона-Рафсона;
в) сравнение результатов, полученных различными методами. В помощь студенту по окончании работы программы в соответствии с одним из методов на экран выводится таблица точек хkи значенийƒ(xk).