Вопрсы методы опт

Вопросы к экзамену по курсу «Методы оптимизации»

1. Классификация задач по виду функций и по типу параметров.

2. Задача математического программирования. Этапы моделирования.

3. Геометрическая интерпретация ЗЛП (3 вида).

4. Каноническая форма ЗЛП. Теорема о канонической форме с доказательством.

5. Графическое решение ЗЛП.

6. Специальная форма ЗЛП.

7. Геометрическая интерпретация специальной формы ЗЛП.

8. Определения для симплексной таблицы.

9. Теоретические основы симплекс-метода (критерий оптимальности).

10. Теоретические основы симплекс-метода (критерий неограниченности).

11. Теоретические основы симплекс-метода (об улучшении целевой функции).

12. Теоретические основы симплекс-метода (о ключевом отношении).

13. Стандартное преобразование симплексной таблицы.

14. Алгоритм прямого симплекс-метода для задачи на минимум.

15. Алгоритм прямого симплекс-метода для задачи на максимум.

16. Теорема о конечности симплекс-метода.

17. Идея метода искусственного базиса.

18. Свойства вспомогательной задачи (без доказательств).

19. Разрешимость вспомогательной задачи (св-во 2).

20. Вырожденность вспомогательной задачи (св-во 5).

21. Алгоритм метода искусственного базиса.

22. Схема решения произвольной задачи прямым симплекс-методом.

23. Формальная схема двойственного симплекс-метода.

24. Сравнение прямого симплекс-метода с двойственным.

25. Правила построения пары двойственных задач. Ключевые моменты для построения пары двойственных задач.

26. Теорема 1: основное неравенство двойственности (с док-вом).

27. Теорема о дополняющей нежесткости (док-во необходимости).

28. Теорема о дополняющей нежесткости (док-во достаточности).

29. Следствие из теоремы о дополняющей нежесткости(с док-вом).

30. Экономическая интерпретация прямой задачи.

31. Экономическая интерпретация двойственной задачи.

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

33. Использование теории двойственности для решения пары задач.

34. Схема решения задачи для проверки оптимальности.

35. Дискретная оптимизация. Целочисленное программирование.

36. Идея методов решения задачи ЦП, геометрическая интерпретация метода.

37. Формальный алгоритм метода Гомори.

38. Замечания по методу Гомори.

39. Теория игр. Матричные игры. Смешанные стратегии.

40. Принцип гарантированного результата в смешанных стратегиях.

41. Эквивалентность матричной игры паре двойственных ЗЛП. Решение задач для матричной игры.

42. Матричная игра «Производство-рынок».

43. Теорема об эквивалентности матричной игры «производство-рынок» паре двойственных задач ЛП.

44. Классическая транспортная задача ЛП. Математическая модель.

45. Сведение классической транспортной задачи ЛП к закрытой форме.

46. Построение начального плана для транспортной задачи.

47. Метод потенциалов для решения транспортной задачи (о разрешении ТЗ).

48. Теорема двойственности для транспортной задачи.

49. Теорема о дополняющей нежесткости для транспортной задачи.

50. Задача о назначениях.

51. Венгерский метод для задачи выбора(подготовительный этап).

52. Венгерский метод (итерации).

53. Схема алгоритма венгерского метода.