ЗАДАНИЯ РАСЧЕТНО-ГРАФИЧЕСКОЙ РАБОТЫ ПО МЕТОДАМ ОПТИМИЗАЦИИ И ПРИНЯТИЮ РЕШЕНИЙ
ЗАДАНИЯ РАСЧЕТНО-ГРАФИЧЕСКОЙ РАБОТЫ ПО МЕТОДАМ ОПТИМИЗАЦИИ И ПРИНЯТИЮ РЕШЕНИЙ
МЕТОДЫ ПОИСКА ЭКСТРЕМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ.
БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ
ЗАДАНИЕ 1. Дана функция:
.
В области определения найти ее минимум.
1. Находя производную
и решая уравнение 
А). методом половинного деления;
Б). методом хорд;
В). методом касательных (Ньютона).
Точность вычислений
.
2. Не производя дифференцирования функции
, организовать процедуры:
А). методом половинного деления;
Б). методом золотого сечения.
Точность вычислений
.
Коэффициенты
по вариантам заданий приведены в в таблице:
№ Варианта
|

|

|

|
1
|
2
|
3
|
-1
|
2
|
3
|
-2
|
4
|
3
|
1
|
-1
|
8
|
4
|
5
|
3
|
2
|
5
|
2
|
4
|
-1
|
6
|
3
|
2
|
4
|
7
|
4
|
-3
|
2
|
8
|
6
|
4
|
7
|
9
|
2
|
8
|
-3
|
10
|
3
|
-5
|
6
|
МЕТОД ГРАДИЕНТНОГО СПУСКА ПОИСКА МИНИМУМА ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ
ЗАДАНИЕ 2. Пусть требуется найти локальный минимум функции
.
Выберем начальное приближение
и построим последовательность
, в которой каждое очередное приближение
получается из предыдущего
"шагом" в направлении вектора
:
. (1)
Выбор вектора
определяет различные варианты метода "спуска" к минимуму
.
Величина шага управляется выбором
. Обычно
выбирается так, чтобы функция
(2)
Принимала наименьшее значение.
Точность полученного приближения к минимуму обычно оценивается по величине отклонения двух соседних приближений
и
, например
(3)
Или
. (3.1)
Процесс приближений прекращается, если
(абсолютная оценка приближения) или
(относительная оценка приближения), где
Заданная точность.
"Скорейший" спуск получается, если шаг делать в направлении быстрейшего убывания
, то есть вдоль вектора
. (4)
Так как градиент
в любой точке ортогонален к поверхности уровня
, то в точке
следует двигаться в направлении вектора
до такой точки
, в которой
ортогонален вектору
(в этой точке
касается поверхности уровня, то есть будет достигнут минимум функции
).
Если
Квадратичная функция (что как раз и имеет место в задании). То непосредственный метод скорейшего спуска сходится довольно-таки медленно. Поэтому необходимо использовать модифицированный Метод сопряженных градиентов Флетчера-Ривса, который обеспечивает более быструю сходимость. В этом методе направление спуска – вектор
Выбирается следующим образом:

Где

Таким образом, на каждом шаге спуск несколько отклоняется от "скорейшего" в направлении предыдущего шага, что дает некоторое ускорение сходимости вблизи точки минимума, когда градиент близок к нулю.
В случае квадратичной функции
описываемые методы сходятся при любом выборе начального приближения
.
Для вычисления
на каждом шаге спуска нужно находить минимум функции одной переменной
, определяемой соотношением (2).
В общем случае для этого можно решить уравнение
,
(необходимое условие экстремума), каким-либо из приближенных методов.
В случае, если
Квадратичная функция,
представляет собой квадратный трехчлен относительно
с положительным старшим коэффициентом и его минимум можно найти, если известны значения
при каких-либо трех значениях
. Выберем, например для
значения –1, 0, 1 и вычислим (обратившись к процедуре
) соответствующие значения
. Обозначим их через
,
и
. Здесь
на самом деле можно не вычислять, так как оно известно с предыдущего шага. Тогда
находится по формуле
.
Для контроля за процессом сходимости спуска на каждом шаге удобно выдавать на печать величины:
(номер шага),
(или
, если оценка ведется по относительной точности),
. Метод сходится к точке минимума
, если:
1.
убывает;
2.
;
3.
(или
)
.
ЗАДАНИЕ 2. Найти экстремум функции
.
Числовые параметры функции даны в таблице для каждого варианта.
№ Варианта
|

|

|

|

|

|

|
Начальные данные
|
Точность
|
I
|
-1
|
2
|
-3
|
2
|
1
|
10
|
(-1; -1)
|
0,02
|
II
|
-2
|
3
|
-1
|
2
|
3
|
7
|
(0; 0)
|
0,01
|
III
|
-3
|
3
|
-3
|
2
|
5
|
3
|
(-2; 1)
|
0,03
|
IV
|
-1
|
4
|
-1
|
2
|
2
|
3
|
(2; 1)
|
0,015
|
V
|
-2
|
4
|
-5
|
1
|
1
|
3
|
(0; 0)
|
0,01
|
VI
|
-3
|
3
|
-2
|
2
|
4
|
1
|
(1; 1)
|
0,01
|
VII
|
-1
|
3
|
-3
|
1
|
1
|
5
|
(2; -1)
|
0,02
|
VIII
|
-4
|
5
|
-2
|
1
|
1
|
6
|
(0; 0)
|
0,02
|
IX
|
-2
|
3
|
-2
|
3
|
3
|
5
|
(-1; -1)
|
0,015
|
X
|
-1
|
1
|
-1
|
4
|
3
|
5
|
(1; 1)
|
0,02
|
Для вычисления экстремума используйте прямой метод градиентного спуска. При вычислении точности руководствуйтесь формулой
для каждого
Го шага вычислений
.
СИМПЛЕКС-МЕТОД.
ЗАДАНИЕ 3. Предположим, что в производстве двух видов продукции
и
принимают участие три предприятия. При этом на изготовление единицы изделия
первое предприятие тратит
часов, второе предприятие -
часов, третье предприятие -
часов. На изготовление единицы продукции вида
первое предприятие тратит
часов, второе предприятие -
часов, третье предприятие -
часов. На производство всех видов продукции первое предприятие может затратить не более, чем
часов, второе предприятие - не более, чем
часов, третье предприятие - не более, чем
часов. От реализации единицы готовой продукции вида
прибыль составляет
, а вида
-
денежных единиц.
Составить математическую модель, определения максимальной прибыли от реализации всей продукции видов
и
. Решить задачу симплекс-методом. Дать геометрическую интерпретацию математической формулировки. Данные приведены в таблице данных.
Таблица данных.
№
Варианта
|

|

|

|

|

|

|

|

|

|

|

|
I
|
7
|
6
|
5
|
8
|
3
|
1
|
476
|
364
|
319
|
11
|
10
|
II
|
10
|
9
|
3
|
18
|
15
|
1
|
123
|
111
|
523
|
11
|
13
|
III
|
8
|
7
|
7
|
12
|
9
|
5
|
459
|
379
|
459
|
9
|
9
|
IV
|
8
|
7
|
7
|
10
|
5
|
2
|
612
|
492
|
562
|
11
|
9
|
V
|
10
|
9
|
5
|
6
|
3
|
1
|
735
|
765
|
455
|
8
|
4
|
VI
|
5
|
6
|
7
|
7
|
6
|
1
|
256
|
283
|
363
|
9
|
7
|
VII
|
3
|
9
|
10
|
5
|
3
|
2
|
414
|
723
|
788
|
12
|
16
|
VIII
|
7
|
7
|
8
|
5
|
2
|
1
|
347
|
300
|
357
|
11
|
7
|
IX
|
7
|
7
|
8
|
13
|
8
|
2
|
363
|
327
|
429
|
6
|
4
|
X
|
5
|
9
|
10
|
7
|
9
|
8
|
343
|
587
|
587
|
11
|
7
|
ТРАНСПОРТНАЯ ЗАДАЧА
ЗАДАНИЕ 4. Имеется три пункта поставки однородного груза
и пять пунктов
потребления этого груза. В пунктах поставки находится груз в количествах
и
соответственно. В пункты потребления необходимо доставить груз в количествах соответственно
. Издержки на транспортировку единицы груза из пунктов поставки в соответствующие пункты потребления сведены в таблицу - матрицу издержек
.
Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты на перевозку были минимальными.
I.
|

|

|
.
|
II.
|

|

|
.
|
III.
|

|

|
.
|
IV.
|

|

|
.
|
V.
|

|

|
.
|
VI.
|

|

|
.
|
VII.
|

|

|
.
|
VIII.
|

|

|
.
|
IX.
|

|

|
.
|
X.
|

|

|
.
|
ЦЕЛОЧИСЛЕННАЯ ЗАДАЧА
ЗАДАНИЕ 5. Найти экстремум целевой функции при заданной системе ограничений. Во всех задачах
Множество целых чисел.
I.
|

|
VI.
|

|
II.
|

|
VII.
|

|
III.
|

|
VIII.
|

|
IV.
|

|
IX.
|

|
V.
|

|
X.
|

|
Эти задачи ввиду своей малой размерности позволяют выполнить вычисления вручную. Однако мы рекомендуем для расчетов дополнительно использовать вычислительную технику, например, вычислительные средства пакета прикладных программ “научного менеджмента” QSB.