Глава «Методы дискретной оптимизации» для задач дискретного (и целочисленного) программирования

40. Классификация задач дискретного программирования: задача «о рюкзаке», задача коммивояжера, транспортная задача и задача распределения ресурса, задача о ранце, задачи теории графов («о покрытиях графов: о реберном и о вершинном покрытии», «об изоморфизме графов», «о вершинной и реберной раскраске», о покрытии конечного множества системой его подмножеств), задача размещения программных модулей в многоуровневой памяти ЭВМ, задача распределения заданий в многопроцессорной системе, задача планирования вычислений для многопроцессорной системы.

41. Целочисленное программирование (ЦП). Классификация и связь с другими задачами математического программирования. Краткая характеристика методов решения задач ЦП: методы отсечения, приближенные методы, комбинаторные методы (алгоритмы метода ветвей и границ, метод динамического программирования и др.

42. Методы отсечения

43. Методы ветвей и границ (МВГ) с симметричной и несимметричной матрицей задачи.

44. Применение метода ветвей и границ для решения задачи «о коммивояжере».

45. Метод Ленда и Дойга (алгоритм типа МВГ) для задачи целочисленного программирования.

46. Аппроксимационно-комбинаторный метод для задач дискретного программирования (использование древовидной схемы решения)

47. Метод «динамического программирования» для задачи коммивояжера (для задачи дискретного программирования).

Замечание: Этот метод более подробно изучается в динамическом программировании.

Глава «Стохастическое программирование»

48. Жесткая и нежесткая постановки задач стохастического программирования.

Глава «Методы оптимизации в функциональных пространствах для решения вариационных задач и задач оптимального управления»

49. Вспомогательные сведения из функционального анализа: линейное функциональное пространство (банахово пространство), функционалы и операторы, необходимое и достаточное условия экстремума (минимума) функционала

50. Постановка простейшей задачи вариационного исчисления (ВИ). 1-ая основная Лемма Лагранжа уравнение Эйлера-Лагранжа.

51. Разновидности «целевых» функционалов в задачах ВИ и оптимального управления: интегральный функционал, терминальный функционал, смешанный функционал и различные виды ограничений: функциональные равенства (изопериметрическая задача) и дифференциальные ограничения.

52. Целевой функционал, переменные состояния и переменные управления в задаче оптимального управления (ОУ), дифференциальные ограничения.

53. Необходимые условия оптимальности (условия регулярности) в задачах ВИ и ОУ как задач математического программирования: функционал (функция) Лагранжа, построенный на целевой функции, ограничениях и целевом функционале и множителях Лагранжа, и позволяющий решать задачу как задачу безусловной оптимизации.

54. Разрешимость задач минимизации функционалов, теорема Вейерштрассе. Метод Ритца как численный метод оптимизации в функциональных пространствах.