7.7. Вопросы для самоконтроля

1. Основные свойства вектора-градиента.

2. Основная идея градиентного метода нахождения экстремума целевой функции.

3. Критерии прекращения итерационного процесса при применении градиентных методов.

4. Особенность градиентного метода с постоянным шагом.

5. Градиентный метод наискорейшего спуска.

6. Какова точность экстремальных значений целевой функции в градиентном методе?

7. Какие существуют методы выбора шага в градиентном методе?

8. Какова роль штрафной функции?

9. В чем заключается суть метода Франка-Вулфа?

10. В каких случаях используют метод Лагранжа?

11. Какова точность приближенных методов задач нелинейного программирования?

12. Общая постановка задачи нелинейного программирования.

13. Какой метод используют для обобщенных приближенных решений?

7.8. Практикум

Задание 1. Решение задач нелинейного программирования градиентным методом по критерию модуля разности оптимизируемой функции.

Предприятие выпускает два вида продукции х₁ и х₂ (в тоннах). Затраты (в тысячах рублей), связанные с производством продукции, выражаются целевой функцией

.

Спланировать выпуск продукции с минимальными затратами на ее производство.

Таблица 7.3

Варианты заданий

№ варианта	А	В	С	D	Е	F	№ варианта	А	В	С	D	Е	F
1	10	1	6	2	5	13	16	5	4	9	4	3	15
2	4	3	5	3	6	14	17	2	9	4	5	2	21
3	5	3	6	7	5	27	18	6	3	5	3	6	30
4	3	6	5	1	2	15	19	6	7	5	2	1	22
5	2	5	3	4	2	17	20	7	3	7	3	4	29
6	3	7	3	5	4	33	21	5	3	9	4	2	26
7	2	7	4	3	5	28	22	9	8	5	2	3	29
8	2	5	4	7	9	30	23	3	6	3	4	6	34
9	4	5	4	4	5	35	24	3	10	4	6	2	47
10	3	7	7	3	2	37	25	6	3	4	3	7	41
11	3	7	4	5	3	42	26	3	6	4	6	2	47
12	3	6	7	3	7	49	27	3	5	5	3	7	41
13	2	8	4	5	1	36	28	3	66	6	1	6	42
14	2	6	4	3	6	25	29	10	3	9	2	5	30
15	3	7	6	3	7	40	30	5	3	5	4	1	32

Задание 2. Решить графическим методом следующие задачи нелинейного программирования:

1.

при

2.

при

3.

при

4.

при

5.

при

6.

при

7.

при

8.

при

9.

при

10.

при

11.

при

12.

при

13.

при

14.

при

15.

при

Задание 3. Оптимизация целевой функции градиентным методом с постоянным и оптимальным шагом.

1. Ознакомиться с оптимизацией целевой функции методом градиентного спуска.

2. В соответствии со своим вариантом задания найти оптимум целевой функции с заданной начальной точкой:

а) с постоянным шагом, например, h=0,5 и =0,2;

б) с оптимальным шагом методом наискорейшего спуска.

3. Составить расчетные таблицы.

4. Построить траекторию поиска экстремума.

Варианты заданий

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

Задание 4. Модификация метода скорейшего спуска на ЭВМ

Найти минимальное значение функции F методом скорейшего спуска на ЭВМ (ППП BTN/GRAD.EXE) . Задать начальные координаты точки, например (1,1,1,1), =0,01, =0,1.

Варианты заданий

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. + 2;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. ;

27. ;

28. ;

29. ;

30. .

Задание 5.

Предприятие выпускает изделия А и В, при изготовлении которых используется сырье вида I и II. Известны запасы сырья а_i0 (i=1,2), нормы его расхода а_ij (j=1,2) на единицу изделия, оптовые цены р_j на изделия и их плановая себестоимость .Как только объем выпускаемой продукции перестает соответствовать оптимальным размерам предприятия, дальнейшее увеличение выпуска Х_j ведет к повышению себестоимости продукции, и в этих условиях фактическая себестоимость с_j в первом приближении описывается функцией , где – некоторая постоянная величина. Составить план выпуска изделий, обеспечивающий предприятию получение максимальной прибыли.

1. В соответствии со своим вариантом задания найти оптимум целевой функции с заданной начальной точкой.

2. Построить траекторию поиска экстремума.

Необходимые числовые данные приведены в таблице 7.4.

Таблица 7.4

Варианты заданий

№ варианта	а10	а20	а11	а12	а21	а22	р1	р2			=.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30	90 30 40 51 10 31 13 10 10 60 10 84 30 60 13 84 72 105 42 88 10 14 30 7 13 72 42 50 30 92	88 60 84 105 10 84 10 7 60 30 13 40 60 10 10 31 10 51 14 90 72 42 60 10 10 10 80 102 60 90	3 5 4 5 3 12 2 1 8 2 3 7 5 11 2 7 9 13 4 6 8 1 5 1 3 8 4 5 5 3	6 2 7 7 2 7 3 1 11 5 2 4 2 8 3 12 8 5 1 3 9 4 2 1 2 9 5 13 3 6	8 8 12 15 1 3 2 2 2 11 1 7 8 1 2 5 1 7 3 11 2 7 8 1 2 2 12 15 7 9	11 11 7 13 2 5 1 1 1 8 2 12 11 2 1 3 2 15 7 8 1 3 11 2 1 1 7 7 10 11	12 8 11 13 16 27 14 11 11 7 16 17 8 10 14 21 23 13 13 10 19 15 8 12 14 23 11 12 8 12	10 7 17 13 14 21 16 12 10 8 14 11 7 11 16 27 19 15 15 12 23 13 7 11 16 19 15 13 7 11	7 6 9 13 12 24 12 10 9 4 13 14 6 7 12 15 20 10 11 8 13 14 6 9 12 20 9 13 5 8	8 4 14 10 13 15 13 9 7 6 12 9 4 9 13 24 13 13 14 7 20 11 4 10 13 13 14 10 4 9	0,2 0,1 0,2 0,1 0,1 0,3 0,2 0,2 0,1 0,1 0,2 0,2 0,1 0,1 0,2 0,3 0,3 0,1 0,2 0,2 0,3 0,2 0,2 0,2 0,2 0,3 0,2 0,1 0,1 0,2	(2;3) (3;1) (4;1) (2;1) (2;2) (3;2) (3;0) (2;1) (2;1) (3;2) (1;3) (1;4) (2;1) (1;2) (3;1) (2;3) (4;2) (2;1) (4;1) (3;2) (2;4) (4;1) (2;1) (1;2) (2;4) (2;2) (4;1) (2;1) (3;1) (2;3)