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

1. Понятие о методе динамического программирования. Принцип оптимальности Беллмана. Вычислительная схема метода динамического программирования.

2. Задачи выбора наиболее экономичного маршрута доставки груза,

3. Задача оптимального распределения средств на расширение и реконструкцию производства

4. Задача определения оптимальной стратегии замены оборудования.

ВОПРОСЫ ДЛЯ ПОДГОТОВКИ К ТЕСТИРОВАНИЮ

* - низкий уровень сложности,

** - средний уровень сложности,

*** - высокий уровень сложности

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. ***Прикладные аспекты третьей теоремы двойственности.

31. **Постановка транспортной задачи по критерию стоимости.

32. **Транспортная задача с открытой и закрытой моделью.

33. **Условие разрешимости транспортной задачи.

34. **Теорема о ранге матрицы ограничительных уравнений транспортной задачи и ее прикладное значение.

35. *Количество «загруженных» клеток в транспортной таблице.

36. **Построение начального опорного плана транспортной задачи методом «северо-западного угла».

37. **Построение начального опорного плана транспортной задачи методом минимального элемента.

38. ***Построение начального опорного плана транспортной задачи методом Фогеля.

39. **Алгоритм метода потенциалов.

40. **Понятие цикла в транспортной задаче.

41. *Признак оптимальности опорного плана транспортной задачи.

42. *Признак неединственности оптимального плана транспортной задачи.

43. **Система уравнений для определения потенциалов.

44. ***Усложненные постановки транспортной задачи.

45. ***Идея решения задачи целочисленного программирования методом отсечения и его геометрическая иллюстрация.

1. ***Понятие целой и дробной части числа.

47. **Алгоритм метода Гомори решения полностью целочисленной задачи линейного программирования.

48. **Графическая интерпретация решения целочисленной задачи.

49. **Понятие динамического программирования.

50. **Рекуррентное соотношение Р. Беллмана.

51. **Задача о замене оборудования.

52. **Задача о распределении средств на реконструкцию и модернизацию производства.