Задания для самопроверки

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. Дать описание этапа локализации точки минимума в методе одномерного спуска.

31. Для какого класса функций обосновывается алгоритм локализации точки минимума.

32. Дать описание этапа сокращений интервала, содержащего минимума в методе одномерного спуска.

33. Для какого класса функций обосновывается этап сокращения интервала минимума.

34. Сделать оценку скорости сходимости метода скорейшего спуска.

35. Сделать оценку скорости сходимости метода Ньютона при минимизации функций со строго положительно определённой матрицей вторых производства.

36. Как используются условия экстремума задачи минимизации на простых множествах при решение задач ЛП графическим методом.

37. Дать обоснование условиям экстремума задачи минимизации на простых множествах (6.1.3), (6.1.4).

38. Пояснить графически схему метода проекции градиента.

39. Пояснить графически схему метода условного градиента.

40. Чем определяется знак множителей Лагранжа функции Лагранжа в условии экстремума (6.2.3) задачи минимизации с ограничениями равенствами.

41. Объяснить смысл необходимых условий экстремума (6.2.7) задачи минимизации с ограничениями равенствами.

42. Объяснить смысл достаточных условий экстремума (6.2.8) задачи минимизации с ограничениями равенствами.

43. Почему модифицированная функция Лагранжа более предпочтительна для организации так называемых двойственных методов минимизации для решения задачи минимизации с ограничениями равенствами.

44. .Объяснить, почему множители Лагранжа в задаче выпуклого программирования неотрицательны.

45. Дать понятие активных ограничений.

46. Могут ли быть нулевыми множители Лагранжа активных ограничений неравенств. Ответ обосновать.

47. Чем гарантируется единственность решения в задаче выпуклого программирования.

48. Дать понятие двойственных методов в задаче выпуклого программирования.

49. Откуда следуют условия дополняющей нежесткости в общей задаче (ОЗ) нелинейного программирования (НЛП).

50. Объясните неотрицательность множителей Лагранжа для ограничений неравенств в ОЗ НЛП.

51. Могут ли быть нулевыми множители Лагранжа в ОЗ НЛП для активных ограничений неравенств.

52. Дать краткие обоснования достаточных условий оптимальности в ОЗ НЛП.

53. Как используются уравнения Эйлера –Лагранжа в задаче вариационного исчисления (ВИ).

54. Дать определение первой и второй вариаций минимизируемого функционала в задаче ВИ.

55. Сформулировать необходимые условия экстремума в задаче ВИ.

56. Сформулировать достаточные условия экстремума в задаче ВИ.

57. Сформулировать задачу дискретного оптимального управления.

58. Дать понятие функция Беллмана и сформулировать ее свойства.

59. Дать описание метода динамического программирования для нахождения решения задачи дискретного оптимального управления.

60. Дать определение проблемы синтеза в задаче оптимального управления и в чем заключается ее решение.

61. Как связаны решение проблемы синтеза и принцип оптимальности.

Литература

Основная:

1. Ашманов С.А. Линейное программирование. - М.: Наука, 1981.

2. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. - М.: Мир. 1982.

3. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1980.

4. Габасов Р., Кириллова Ф.И. Методы оптимизации. - Минск: БГУ, 1981.

5. Карманов В.Г. Математическое программирование. - М.: Наука, 1980.

6. Ногин В.Д. и др. Основы теории оптимизации. - М.: Высшая школа, 1986.

7. Интриллигатор М. Математические методы оптимизации и экономическая тория - М.: Прогресс, 1975(пер. с анг.).

8. Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.

9. Данилов Н.Н. Задачи нелинейного программирования. Методическая разработка. – Кемерово: КемГУ, 1993.

Вспомогательная:

1. Зайченко Ю.П. Исследование операций. – Киев: "Вища школа", 1979, 391с. (уч. пособие для студентов университетов и тех. вузов).

2. Кузнецов Ю.Н. и др. Математическое программирование. - М.: Высшая шк., 1980, (уч. пособие для экономистов).

3. Основы теории оптимального управления (под ред. В.Ф.Кротова). - М.: Высшая школа, 1979 (уч. пособие для студентов экономических специальностей).

4. Математические методы и модели в планировании (под ред. А.И.Карасева). 1987 (уч. пособие для студентов экономических специальностей).

5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985.

6. Компьютер и задачи выбора. - М.: Наука, 1989.

Для практических занятий:

1. Алексеев М.М. и др. Сборник задач по оптимизации. - М.: Наука, 1984 (уч. пособие для студентов математических специальностей).

2. Сборник задач по математике для ВТУЗов (методы оптимизации, уравнения в частных производных, интегральные уравнения). Под ред. А.Ф.Ефимова. - М.: Наука.

3. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. - М.: Высшая школа, 1979.

4. Б.Банди. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.

Дополнительная литература:

2. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. - М.: Наука, 1966.

3. Зангвилл У.И. Нелинейное программирование. Единый подход. - М.: Сов. радио, 1973.

4. Пшеничный Б.Н. Необходимые условия экстремума. - М.: Наука, 1982.

5. Полак Э. Численные методы оптимизации. Единый поход - М.: Мир, 1974.

6. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.: 1965.

7. Химмельблау Д. Прикладное линейное программирование. - М.: 1974.

8. Понтрягин Л.С. и др. Математическая теория оптимальных процессов. - М.: Наука, 1974.

9. Гейл Д. Теория линейных экономических моделей. - М.: ИЛ., 1963.

10. Беллман Р. Динамическое программирование - М.: ИЛ., 1960.

11. Блисс Г.А. Лекции по вариационному исчислению.- М.: ИЛ., 1950.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.. 3

Глава 1. Основные определения.. 4

§ 1.1. Постановки экстремальных задач. 4

§ 1.2. Примеры оптимизационных задач. 4

§ 1.3. Понятие локального глобального экстремума. Существование решения 7

§ 1.4. Сведения из анализа (градиент, гессиан, локальные приближения) 8

Глава 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП) 9

§ 2.1. Формы задач ЛП.. 10

§ 2.2. Графическая интерпретация задач ЛП.. 11

§ 2.3. Базисные решения. Базисные допустимые решения (БДР) 12

§ 2.4. Симплекс-метод. 13

§ 2.5. Симплекс- метод при заданном начальном БДР. 15

§ 2.6. Двухэтапный симплекс-метод. 19

§ 2.7. Двойственная задача ЛП.. 20

§ 2.8. Двойственная информация в таблице. 21

§ 2.9. Экономическая интерпретация двойственности. 22

Глава 3. ТРАНСПОРТНАЯ ЗАДАЧА ( ТЗ ) 23

§ 3.1. Постановка задачи. 23

§ 3.2. Метод решения транспортной задачи. 24

§ 3.3. Задача о назначении. 27

Глава 4. ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ (ЦП) 28

§ 4.1. Постановки задач целочисленного программирования. 28

§ 4.2. Точные методы решения задач ЦП.. 30

§ 4.3. Приближенные методы решения задач ЦП (Локальный перебор) 33

Глава 5. Безусловная минимизация.. 34

§ 5.1. Классы функций. 34

§ 5.2. Условия экстремума задачи безусловной минимизации. 36

§ 5.3. Скорости сходимости последовательностей. 37

§ 5.4. Методы спуска. 38

§ 5.5. Оценка скорости сходимости методов спуска. 40

§ 5.6. Принципы организации методов одномерной минимизации. 41

§ 5.7. Градиентный метод. 42

§ 5.8. Метод Ньютона. 43

§ 5.9. Метод сопряженных градиентов. 44

§ 5.10. Квазиньютоновские методы.. 45

Глава 6. Условная минимизация.. 46

§ 6.1. Минимизация на простых множествах. 46

§ 6.2. Задачи минимизации с ограничениями равенствами. 49

§ 6.3. Методы решения задачи с ограничениями равенствами. 53

§ 6.4. Выпуклое программирование. 55

§ 6.5. Методы выпуклого программирования. 58

§ 6.6. Нелинейное программирование. 60

Глава 7. Основы вариационного исчисления (ВИ) 62

§ 7.1. Постановка задачи, примеры и основные понятия. 62

§ 7.2. Необходимые условия экстремума. 65

§ 7.3. Достаточные условия экстремума. 69

Глава 8. Основы теории оптимального управления.. 71

§ 8.1. Постановки задач оптимального управления. 71

§ 8.2. Формулировка принципа максимума. 75

Глава 9. Основы динамического программирования (ДП) 77

§ 9.1. Постановка задачи оптимального управления. 77

§ 9.2. Функция и уравнения Беллмана. 79

§ 9.3. Метод динамического программирования. 80

§ 9.4. Специальный класс задач динамического программирования. 82

Вопросы и задания для самопроверки.. 83

1. Основные вопросы.. 83

2. Задания для самопроверки. 85

Литература.. 88

ОГЛАВЛЕНИЕ.. 91