Ответы к экзамену: Системный анализ и принятие решений

Вопросы к экзамену по дисциплинам
«Системный анализ и принятие решений»
ИБМ, второй курс
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. Критерии оптимальности игры по Вальду, Байесу, Гурвицу и Севиджу.

Темы задач на экзамене
1. Отыскание экстремума функции двух переменных при помощи линий уровня и
градиентов.
2. Решение канонической ЗЛП, имеющей базисную допустимую форму.
3. Приведение канонической ЗЛП к БДФ введением искусственных переменных и
решение этой задачи.
4. Приведение общей ЗЛП к канонической.
5. Проверить (используя двойственность), является ли данный вектор решением данной
ЗЛП.
6. Решение транспортной задачи.
7. Решение задачи о назначении (венгерский метод) и задачи коммивояжѐра (методом
ветвей и границ).
9. Задача о потребительском выборе.
10. Исследовать выпуклость функции.
12. Найти максимальный поток в сети.
13. Задача о распределении средств, о рюкзаке.