Исследование операций, Писарук Н.Н., 2012

Исследование операций, Писарук Н.Н., 2012.
 
   В учебном пособии изучаются модели и методы из таких разделов исследования операций как нелинейная оптимизация с ограничениями, квадратичное, линейное, динамическое, целочисленное и стохастическое программирование, сетевая оптимизация, теория массового обслуживания. Вспомогательные сведения из других разделов математики приведены в приложениях.
Для студентов экономических, математических и инженерных специальностей университетов.

Скаляризация векторного критерия.
Среди способов скаляризации векторных критериев на практике наиболее часто используются два способа: свертка критериев и целевое программирование. Свертку критериев следует использовать тогда, когда значения всех критериев можно выразить в одной единице измерения. Когда в задаче имеются критерии, которые измеряются в разных единицах, то содержательный смысл свертки (взвешенной суммы) таких критериев непонятен (нельзя приписать какой-либо смысл сумме килограмма и секунды). В подобных случаях используют метод, который называют «целевым программированием», суть которого в том, чтобы найти такое решение, для которого значения всех критериев близки к заранее заданным целевым значениям.
Оглавление
Предмет исследования операций
0.1. Общая задача исследования операций
0.2. Упражнения
1. Нелинейная оптимизация с ограничениями
1.1. Необходимые условия оптимальности
1.1.1. Допустимые направления и выделение ограничений
1.1.2. Необходимые условия Куна — Таккера
1.1.3. Геометрическая и физическая интерпретация
1.1.4. Числовой пример
1.1.5. Экономическая интерпретация множителей Куна — Таккера
1.2. Достаточные условия оптимальности
1.2.1. Седловые точки и функции Лагранжа
1.2.2. Существование седловой точки для задач выпуклого программирования
1.2.3. Связь с условиями Куна — Таккера
1.3. Геометрическое программирование
1.3.1. Мономы и позиномы
1.3.2. Задача геометрического программирования
1.3.3. Сведение к задаче выпуклого программирования
1.4. Примеры задач нелинейного программирования
1.4.1. Неоклассическая задача потребления
1.4.2. Модель равновесия Фишера
1.4.3. Метод максимального правдоподобия
1.5. Мультикритериальные задачи
1.5.1. Скаляризация векторного критерия
1.5.2. Лексикографическая оптимизация
1.6. Упражнения
2. Линейное программирование
2.1. Двойственность в линейном программировании
2.1.1. Двойственные переменные и теневые цены
2.2. Симплекс-метод
2.3. Модели линейного программирования
2.3.1. Задача о диете
2.3.2. Арбитраж
2.3.3. Метод DEA
2.3.4. Краткосрочный финансовый менеджмент
2.3.5. Предсказание предпочтений потребителя
2.3.6. Проверка гипотез
2.4. Транспортная задача
2.4.1. Метод потенциалов
2.4.2. Численный пример
2.4.3. Агрегированное планирование
2.5. Упражнения
3. Квадратичное программирование
3.1. Критерий оптимальности
3.2. Линейная задача о дополнительности
3.2.1. Алгоритм Лемке
3.2.2. Пример
3.3. Модель Марковица оптимизации портфеля
3.3.1. Пример
3.4. Регрессия с ограничениями на коэффициенты
3.5. Аппроксимация выпуклыми функциями
3.6. Назначение цен на молочную продукцию
3.6.1. Формулировка
3.7. Упражнения
4. Смешанно-целочисленное программирование
4.1. Целочисленность и нелинейность
4.1.1. Фиксированные доплаты
4.1.2. Дискретные переменные
4.1.3. Аппроксимация нелинейной функции
4.1.4. Аппроксимация выпуклой функции
4.1.5. Логические условия
4.2. Множественные альтернативы и дизъюнкции
4.2.1. Размещение прямоугольных модулей на чипе
4.2.2. Линейная задача о дополнительности
4.2.3. Квадратичное программирование при линейных ограничениях
4.3. Метод сечений
4.4. Метод ветвей и границ
4.5. Метод ветвей и сечений
4.6. Примеры задач СЦП
4.6.1. Потоки с фиксированными доплатами
4.6.2. Размещение центров обслуживания
4.6.3. Размер партии: однопродуктовая модель
4.6.4. Размер партии: многопродуктовая модель
4.6.5. Планирование производства электроэнергии
4.7. Упражнения
5. Динамическое программирование
5.1. Общая схема
5.1.1. Прямая индукция
5.1.2. Обратная индукция
5.2. Задача о рюкзаке
5.2.1. 0,1-рюкзак
5.2.2. Целочисленный рюкзак
5.3. Размер партии: однопродуктовая модель
5.3.1. Неограниченная емкость склада
5.4. Контроль качества продукции, производимой на конвейере
5.5. Модель оптимального роста Касса — Купманса
5.5.1. Рекуррентная формула
5.5.2. Специальный случай функции полезности
5.6. Упражнения
6. Методы анализа сетей
6.1. Кратчайшие пути
6.1.1. Дерево кратчайших путей
6.1.2. Алгоритм построения дерева кратчайших путей
6.1.3. Алгоритм Форда— Веллмана
6.1.4. Алгоритм Дейкстры
6.1.5. Кратчайшие пути между всеми парами вершин
6.2. Потоки
6.3. Разложение потоков на элементарные
6.4. Сетевая транспортная задача
6.4.1. Критерии оптимальности
6.4.2. Сетевой симплекс-метод
6.5. Задача о максимальном потоке
6.5.1. Критерии оптимальности
6.5.2. Алгоритм пометок
6.6. Упражнения
7. Календарное планирование
7.1. Сетевые графики
7.2. Метод критического пути
7.2.1. Ранние и поздние сроки наступления событий
7.2.2. Ранние и поздние сроки начала и окончания работ
7.2.3. Четыре показателя резерва времени работы
7.3. Распределение ресурсов в графиках проектов
7.4. Упражнения
8. Задачи с неопределенными параметрами
8.1. Двустадийные задачи стохастического программирования
8.2. Минимизация рисков
8.2.1. Расширенная двустадийная модель
8.2.2. Кредитный риск
8.2.3. Портфель из трех активов
8.3. Мультистадийные задачи стохастического программирования
8.3.1. Синтетические опционы
8.3.2. Управление доходами
8.4. Упражнения
9. Теория массового обслуживания
9.1. Потоки событий
9.2. Схема гибели и размножения
9.2.1. Уравнения Колмогорова
9.3. Формулы Литтла
9.4. Многоканальная СМО с отказами
9.5. Одноканальная СМО с неограниченной очередью
9.6. Многоканальная СМО с неограниченной очередью
9.7. Упражнения
А. Элементы нелинейного анализа
А.1. Векторы и линейные пространства
А.2. Элементы топологии
А.2.1. Компактные множества. Теорема Вейерштрасса
А.3. Дифференцируемые функции
А.4. Необходимые условия локального минимума
А.5. Выпуклые множества
А.5.1. Выпуклые конусы
А.5.2. Теорема об отделении выпуклых множеств
А.6. Лемма Фаркаша
А.7. Выпуклые функции
А.7.1. Как доказать выпуклость функции
А.7.2. Преобразования, сохраняющие выпуклость функций
А.7.3. Субградиенты и субдифференциал
A.8. Квазивыпуклые функции
А.8.1. Критерии квазивыпуклости функций
A.8.2. Преобразования, сохраняющие квазивыпуклость функций
B. Элементы теории вероятностностей
В.1. Вероятностные пространства
В.2. Случайные величины
B.2.1. Математическое ожидание, дисперсия и стандартное отклонение
B.2.2. Совместное распределение случайных величин
B.3. Н
C. Графы
С.1. Специальные типы графов
C.2. Примеры самых известных задач теории графов
C.2.1. Эйлеровы графы
С.2.2. Задача коммивояжера
С.2.3. Задача о максимальной клике
С.2.4. Раскраска графа и проблема четырех красок
С.2.5. Укладка графа на плоскости
D. Сложность вычислений
D.1. Сложность алгоритмов
D.2. Полиномиальные алгоритмы
Литература
Предметный указатель.