Лектор: Калитин Борис Сергеевич, доц., кандидат физ-мат. наук.

3-й курс, 6-й семестр 2000-2001 учебного года.
Методички (4,3Мб)

Глава 1. Линейное программирование.

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. Модификации в решении транспортных задач при усложнённых формулировках.

    Глава 2. Выпуклое программирование.

31. Выпуклые множества и функции.
32. Свойства выпуклых множеств.
33. Свойства выпуклых функций.
34. Строгая выпуклость.
35. Седловая точка функции Лагранжа.
36. Условие дополняющей нежесткости.
37. Теорема Куна-Таккера.
38. Гладкие задачи. (теорема Фаркаша, необходимое условие оптимальности, случай линейных ограничений).
39. Теория двойственности (двойственная задача, решение задачи квадратичного программирования).

    Глава 3. Нелинейное программирование.

40. Общая задача НЛП (критерий существования решения).
41. Классификация задач НЛП.
42. Задача на безусловный минимум (необходимое условие минимума 1-го и 2-го порядков, достаточное условие локального минимума, случай функции одной переменной).
    
    Задача на условный минимум со смешанными ограничениями
43. Метод исключения.
44. Теорема о несовместности неравенств.
45. Обобщённая лемма Фаркаша.
46. Обобщённое правило множителей Лагранжа.
47. Классическое правило множителей Лагранжа.
48. Необходимое условие минимума 2-го порядка.
49. Достаточное условие локального минимума 2-го порядка.
    
    Вычислительные методы НЛП
50. Основные определения.
51. Методы перебора (метод вариаций, метод ветвей и границ, схемы полного и одностороннего ветвления, задача о рюкзаке).
52. Методы минимизации функций одной переменной (абсолютный минимум гладкой функции, методы поиска точек минимума унимодальных функций: метод Джонсона, метод золотого сечения)
53. Методы безусловной минимизации (методы 1-го и 2-го порядков)
    
    Динамическое программирование
54. Задача о распределении ресурсов.
55. Уравнение Беллмана.
56. Алгоритм решения.

    Глава 4. Вариационное исчисление.

57. Задача о брахистохроне.
58. Основная задача вариационного исчисления.
59. Метод вариаций (необходимые условия слабого минимума).
60. Уравнение Эйлера (лемма Лагранжа).
61. Уравнение Эйлера в интегральной форме (лемма Дю-Буа-Раймона).
62. Теорема Гильберта.
63. Присоединённая задача о минимуме.
64. Условие Лежандра-Клебша.
65. Условие Якоби.
66. Достаточное условие слабого минимума.