Вопросы к экзамену по курсу доц. С. М. Машарского

"ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ"

ЧАСТЬ 1. Линейные экстремальные задачи

  1. Лемма об эквивалентных экстремальных задачах.
  2. Примеры эквивалентных экстремальных задач.
  3. Постановка задачи планирования производства. Сведение ее к задаче линейного программирования.
  4. Приведение общей задачи линейного программирования к эквивалентной задаче линейного программирования в канонической форме.
  5. Лемма о базисном плане.
  6. Теорема о существовании оптимального базисного плана у задачи линейного программирования в канонической форме.
  7. Формулировка теоремы Фаркаша. Ее интерпретация в двумерном случае.
  8. Критерий существования неотрицательного решения у системы линейных уравнений.
  9. Критерий совместности системы линейных уравнений и неравенств.
  10. Основная лемма линейного программирования.
  11. Критерий оптимальности для общей задачи линейного программирования.
  12. Первая теорема двойственности в линейном программировании.
  13. Критерий совместной разрешимости пары двойственных задач линейного программирования.
  14. Вторая теорема двойственности в линейном программировании.
  15. Постановка задачи о матричных играх. Лемма об очистке.
  16. Теорема о существовании ситуации равновесия в матричных играх.
  17. Анализ двойственной задачи к линейной дискретной задаче оптимального управления.
  18. Принцип максимума для линейных дискретных систем.
  19. Симплекс-метод.
  20. Пересчет обратной базисной матрицы и двойственного вектора.
  21. Вычислительная схема симплекс-метода.
    22.  

ЧАСТЬ 2. Нелинейные экстремальные задачи

  1. Необходимые условия оптимальности для задачи нелинейного программирования с линейными ограничениями.
  2. Теорема Лагранжа и теорема Куна–Таккера для экстремальных задач с линейными ограничениями.
  3. Критерий выпуклости для дифференцируемых функций.
  4. Критерий выпуклости для квадратичной функции.
  5. Критерий оптимальности для задачи нелинейного программирования с выпуклой дифференцируемой целевой функцией и линейными ограничениями. Частные случаи.
  6. Проектирование точки на подпространство.
  7. Свойства матрицы ортогонального проектирования.
  8. Проектирование точки на стандартный симплекс.
  9. Теорема о существовании решения у задачи квадратичного программирования.
  10. Критерий оптимальности для задачи квадратичного программирования.
  11. Двойственная задача квадратичного программирования. Теорема двойственности.
  12. Основная лемма нелинейного программирования.
  13. Теорема Куна–Таккера в дифференциальной форме.
  14. Пример задачи нелинейного программирования, в единственном решении которой не выполняется условие Куна–Таккера.
  15. Теорема о достаточности условий Куна–Таккера. Пример.
  16. Необходимое условие оптимальности второго порядка в задаче нелинейного программирования.
  17. Достаточное условие оптимальности второго порядка в задаче нелинейного программирования.
  18. Пример на использование условий оптимальности второго порядка в задаче нелинейного программирования.
    19.  

ЧАСТЬ 3. Вариационное исчисление

  1. Постановка простейшей вариационной задачи. Конечномерная аппроксимация. Уравнение Эйлера.
  2. Основная лемма вариационного исчисления.
  3. Минимизация линейной интегральной формы.
  4. Минимизация интегрального квадратичного функционала. Критерий оптимальности.
  5. Необходимое условие Лежандра неотрицательной определенности интегральной квадратичной формы.
  6. Критерий неотрицательной определенности интегральной квадратичной формы. Доказательство достаточности.
  7. Лемма о скруглении углов.
  8. Критерий неотрицательной определенности интегральной квадратичной формы. Доказательство необходимости.
  9. Критерий положительной определенности интегральной квадратичной формы.
  10. Описание всего множества решений квадратичной вариационной задачи.
  11. Схема решения квадратичной вариационной задачи. Примеры.
  12. Естественная область определения интегрального функционала. Ее открытость в пространстве непрерывно дифференцируемых функций.
  13. Первый дифференциал интегрального функционала.
  14. Второй дифференциал интегрального функционала.
  15. Необходимые условия локального минимума первого порядка в нелинейной вариационной задаче (в терминах первого дифференциала и в терминах исходной задачи).
  16. Теорема о существовании и непрерывности второй производной у экстремали нелинейной вариационной задачи.
  17. Необходимые условия локального минимума второго порядка в нелинейной вариационной задаче (в терминах второго дифференциала и в терминах исходной задачи).
  18. Оценка снизу для положительно определенной интегральной квадратичной формы.
  19. Достаточные условия строгого локального минимума в нелинейной вариационной задаче.
  20. Задача о минимальной поверхности вращения.
  21. Случай двух стационарных кривых в задаче о минимальной поверхности вращения.
  22. Изопериметрическая задача.
  23. Цепная линия.
    24.  

 

ЛИТЕРАТУРА

  1. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями. Л., 1984.
  2. Ашманов С. А. Линейное программирование. М., 1981.
  3. Даугавет В. А. Численные методы квадратичного программирования. СПб., 2004.
  4. Таха Х. А. Введение в исследование операций. М., 2001.
  5. Галеев Э. М., Тихомиров В. М. Краткий курс теории экстремальных задач. М., 1989.
  6. Буслаев В. С. Вариационное исчисление. Л., 1980.
  7. Малоземов В. Н. Линейная алгебра без определителей. Квадратичная функция. Л., 1997.
  8. Заславский Ю. Л. Сборник задач по линейному программированию. М., 1969.
  9. Алексеев В. М., Галеев Э. М., Тихомиров В. М. Сборник задач по оптимизации. М., 1984.
  10. Отдельные лекции по экстремальным задачам: http://kio-math.spbu.ru/kio_lect.html