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