"Методы линейного и дискретного программирования"

Вопросы к экзамену по курсу доц. Н. С. Григорьевой и доц. И. В. Агафоновой

"Методы линейного и дискретного программирования"

6 семестр

Транспортная задача в сетевой и матричной постановке.
Методы нахождения начального базисного решения.
Метод потенциалов для транспортной задачи.
Задача о максимальном потоке. Теорема о макси потоке и мини разрезе.
Алгоритмы нахождения максимального потока.
Алгоритм нахождения минимального разреза.
Задача о максимальном паросочетании. Теорема Кенига.
Алгоритм нахождения максимального паросочетания.
Задача о назначениях.
Общая схема метода ветвей и границ.
Метод ветвей и границ для задачи коммивояжера.
Метод ветвей и границ для задачи линейного раскроя.
Метод ветвей и границ для задачи о куче камней.
Приближенные методы решения задачи коммивояжера.
Общая схема динамического программирования.
Метод динамического программирования для задачи линейного раскроя.
Матроиды. Леммы о свойствах баз матроидов.
Жадный алгоритм.
Теорема об оптимальности жадного алгоритма.
Примеры матроидов.
Задача о различных представителях.
Генетический алгоритм. Метод имитации отжига.
Методы локальной оптимизации.

7 семестр

Крайние точки и крайние направления многогранного множества –эквивалентные определения.
Представление крайней точки многогранного множества.
Представление рецессивного направления многогранного множества.
Теорема об отделимости.
Прямой симплекс-метод. Общее описание и правила пересчета. Простая табличная версия и версия с обратной матрицей.
Методы построения начального базисного решения. M-метод.
Методы построения начального базисного решения. Двухэтапный метод.
Вырожденность. Методы борьбы с зацикливанием. Лексикографическое правило. Правило Блэнда.
Элементарные матрицы как мультипликаторы.
Мультипликативный вариант симплекс-метода
Постоптимальный анализ
Двойственный симплекс-метод
Учет ограничений на переменные
Метод генерации столбцов. Общая идея, применение к задаче линейного раскроя.
Метод декомпозиции Данцига-Вулфа.
Декомпозиция для задач транспортного типа.
Алгоритмы для задачи линейного программирования, имеющие полиномиальную сложность. Первые полиномиальные методы.
Прямо-двойственный алгоритм. Сведение задачи к решению нелинейной системы уравнений.
Прямо-двойственный алгоритм. Пошаговое описание.
Подход Дикина к решению задачи ЛП.

ЛИТЕРАТУРА

Ашманов С.А. Линейное программирование. М.:Наука, 1981.
Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.:Наука, 1986.
Карманов В.Г. Математическое программирование.– 5-е изд. М.:Физматлит, 2001.
Ху Т. Целочисленное программирование и потоки в сетях. М.:Наука, 1974.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.
М.: Мир, 1985.
Мину М. Математическое программирование. М.: Наука, 1990.
Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах. М.:Гелиос АРВ, 2003.
Таха, Х.А. Введение в исследование операций. 7-е изд – М.: Издательский дом «Вильямс», 2005.