II. Основная задача линейного программирования.
МДК.01.03 Математическое моделирование
I. Основы моделирования. Общий вид задачи линейного программирования.
1. Что такое математическое моделирование. Что такое целевая функция, решение, оптимальное решение.
2. Что такое математическое программирование, линейное программирование.
3. Сформулируйте задачу линейного программирования в общем виде (в полной или краткой форме).
II. Основная задача линейного программирования.
1. Сформулируйте основную задачу линейного программирования.
2. Перечислите правила приведения произвольной задачи линейного программирования к ОЗЛП.
III. Графическая интерпретация основной задачи линейного программирования. Решения задач линейного программирования графическим методом.
1. В каких случаях задачу линейного программирования можно решить графически.
2. Что представляет из себя ОДР если она существует, для случая, когда число переменных n на два больше, чем число независимых уравнений m.
3. Какие 6 основных закономерностей можно вывести при рассмотрении графической интерпретации ОЗЛП.
4. Перечислите шаги алгоритма графического способа решения задач линейного программирования.
IV. Симплекс-метод решения задач линейного программирования.
1. Что такое симплексный метод решения задач линейного программирования.
2. Какие решения называются базисными, опорными.
3. Какова идея симплекс-метода. На какие два этапа его можно разбить.
4. Расскажите правила составления симплекс-таблицы.
5. Опишите этапы алгоритма симплекс-метода с помощью симплекс таблиц.
V. Транспортная задача.
1. Дайте формулировку транспортной задачи (математическую или словесную).
2. Что называется планом ТЗ, какой план называется допустимым, опорным, оптимальным.
3. Какая транспортная задача называется закрытой, открытой. Как осуществляется сведение открытой ТЗ к закрытой.
4. Что является необходимым и достаточным условием разрешимости транспортной задачи.
5. Опишите основные этапы построения математический модели транспортной задачи.
VI. Методы нахождения начального решения транспортной задачи. Метод потенциалов
1. Перечислите методы нахождения опорного решения транспортной задачи. Какие методы нахождения оптимального решения транспортной задачи вам известны.
2. Опишите процесс составления опорного плана методом «Северо-западного угла».
3. Опишите процесс составления опорного плана методом «наименьшего элемента».
4. Что такое потенциалы, сформулируете условие оптимальности плана.
5. Опишите процесс решения транспортной задачи методом потенциалов.
VII. Динамическое программирование.
1. Опишите основные понятия динамического программирования: шаговое управление, управление операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю операцию, аддитивный критерий.
2. Опишите процесс решения задачи о распределении средств между предприятиями методом динамического программирования. Что принимается за шаг управления. Как составляются таблицы на каждом шаге, какой физический смысл имеют значения ячеек таблицы.
VIII. Методы хранения графов в памяти ЭВМ. Задача о нахождении кратчайших путей в граф.
1. Дайте определение графа.
2. Что называется дугой графа. Какие вершины называются смежными. Дайте определение ориентированного, неориентированного и смешанного графа.
3. Перечислите способы представления графов в памяти ЭВМ
4. Какие вершины называются смежными.
5. Как заполняется матрица смежности для неориентированного графа.
6. Как заполняется матрица смежности для ориентированного графа.
7. Как заполняется матрица смежности для взвешенного графа.
8. Инцидентность.
9. Как заполняется матрица инцидентности для неориентированного графа.
10. Как заполняется матрица инцидентности для неориентированного графа.
11. Дайте определение пути между вершинами графа.
12. Опишите основные шаги алгоритма Дейкстры