Шевченко В.Н., Золотых Н.Ю. Линейное и целочисленное линейное программирование

Учебник. — Нижний Новгород: Нижегородский государственный университет (НГУ) имени Н.И. Лобачевского, 2005. — 160 с. — ISBN 5-85746-820-5. — (Модели и методы конечномерной оптимизации. Вып. 1).Учебник посвящен основам теории линейного и целочисленного линейного программирования. В нем излагаются симплекс-метод, теория
двойственности, алгоритмы решения транспортной задачи, методы решения задач целочисленного линейного программирования. Приводятся многочисленные примеры и задачи для самостоятельного решения.
Для студентов математических и других специальностей, изучающих линейное и целочисленное линейное программирование.Предисловие.
Основные определения, идеи, примеры задач.
Задача математического программирования.
Задача выпуклого программирования.
Задача линейного программирования.
Основная идея симплекс-метода.
Примеры задач линейного программирования.
Задача максимизации прибыли.
Задача о «смесях».
Задачи.
Симплекс-метод.
Числовой пример.
Симплекс-метод в строчечной форме.
Зацикливание и способы защиты от него.
Зацикливание.
Лексикографический метод.
Правило Бленда.
Получение начального допустимого опорного вектора.
Матричное описание симплекс-метода.
Модифицированный симплекс-метод.
Столбцовая форма симплекс-метода.
Задачи.
Двойственность в линейном программировании.
Двойственная задача.
Теорема двойственности.
Лемма Фаркаша и ее варианты.
Дополняющая нежесткость в линейном программировании.
Слабая форма свойства дополняющей нежесткости.
Сильная форма свойства дополняющей нежесткости.
Множители Лагранжа.
Двойственный симплекс-метод.
Двойственный симплекс-метод в строчечной форме.
Двойственный симплекс-метод в столбцовой форме.
Замечания о сложности ЗЛП.
Задачи.
Транспортная задача.
Постановка задачи и основные свойства.
Унимодулярные матрицы.
Задача о назначениях.
Графовая характеристика допустимых векторов.
Получение начального допустимого опорного вектора.
Метод северо-западного угла.
Метод минимального элемента.
Пересчет опорного вектора при изменении базы.
Метод потенциалов.
Задачи.
Целочисленное линейное программирование.
Основные определения.
Примеры задач целочисленного линейного программирования.
Задача о рюкзаке.
Задачи с фиксированными доплатами.
Дихотомии.
Задачи о выполнимости КНФ.
Задача о «раскрое».
Задача коммивояжера.
Идея метода правильных отсечений.
Циклический алгоритм Гомори.
Классификация методов отсечения.
Полностью целочисленный алгоритм.
Прямой метод целочисленного программирования.
Задача о рюкзаке. Динамическое программирование.
Метод ветвей и границ.
Задачи.
Литература.
Предметно-именной указатель.