6.2.2. Экзаменационная программа.

Общая теория математического программирования

1. Задачи оптимизации. Примеры задач оптимизации (в том числе задач, рассмотренных в курсе). Определение допустимых и оптимальных решений. Задачи математического программирования и их классификация. Задачи линейного программирования (ЗЛП). Задача о выпуске продукции при ограниченных ресурсах, как пример ЗЛП. Формы записи ЗЛП (общая, стандартная, каноническая), приведение произвольной ЗЛП к стандартной, к канонической формам.

2. Гиперплоскости, полупространства, нормали в пространстве N переменных. Геометрическая трактовка ЗЛП Теорема существования решения ЗЛП. Примеры, когда есть много оптимальных решений, когда нет оптимальных решений. Графический метод решения ЗЛП.

3. Определение пары двойственных ЗЛП, пример. Первая (с доказательством) теорема двойственности. Следствие из первой теоремы. Вторая теорема двойственности. Следствие из второй теоремы. Определение условия дополняющей нежесткости для двойственных ЗЛП. Третья теорема двойственности (с доказательством обоих пунктов). Двойственная ЗЛП для задачи о выпуске продукции при ограниченных ресурсах, смысл двойственных переменных.

4. Примеры задач нелинейного программирования, способы их решения.

Оптимизационные задачи на сетях

5. Определение ориентированного графа. Основные объекты графа: маршруты, пути, контуры, цепочки, циклы. Деревья, их характеристические свойства (то есть альтернативные определения). Матрица смежности, матрица инциденций. Способы задание графов в компьютере.

6. Сетевая транспортная задача (ТЗ): постановка задачи. Существование оптимального транспортного плана. Сведение ТЗ к закрытой вспомогательной ТЗ с фиктивной вершиной. Метод потенциалов решения сетевой ТЗ. Критерий оптимальности плана ТЗ в методе потенциалов и его доказательство, основанное на третьей теореме двойственности.

7. Классическая транспортная задача (КТЗ): постановка задачи, закрытые и открытые КТЗ. Вид оптимального решения закрытой КТЗ (связь с деревьями). Табличный метод потенциалов решения КТЗ. Критерий оптимальности плана КТЗ в табличном методе потенциалов и его доказательство.

8. Понятие о назначениях. Классическая задача об оптимальном назначении. Сведение ее к сетевой ТЗ (обоснование того факта, при ее решении как сетевой ТЗ в ответе действительно получается оптимальное назначение). **Табличный метод потенциалов решения задачи об оптимальном назначении (факультативно).

9. Постановки задач об оптимальных маршрутах (минимальных, максимальных). Примеры, когда нет оптимальных маршрутов. Сведение их к сетевой ТЗ (обоснование того факта, при ее решении как сетевой ТЗ в ответе действительно или находится оптимальный маршрут или обнаруживается его отсутствие).

10. Правильная нумерация вершин. Метод потенциалов (метод Беллмана) нахождения оптимальных маршрутов в сетях без контуров с помощью правильной нумерации. Метод потенциалов (метод Беллмана) нахождения оптимальных маршрутов в произвольных сетях (с возможными контурами).

10.Простейшая задача об аренде оборудования. Планы аренды, их количество. Сведение задачи об аренде к нахождению кратчайшего маршрута в сети. Потенциалы и решение задачи в сетевой модели. Табличный алгоритм решения задачи об аренде оборудования.

Билеты:

1. Теория двойственных ЗЛП. (полностью абзац 3).

2. Сетевая транспортная задача и ее решение (абзац 6).

3. Классическая ТЗ и ее решение (абзац 7).

4. Оптимальные маршруты и метод потенциалов их нахождения (абзацы 9,10).

5. Задача об аренде оборудования (абзац 11)