Системный анализ и исследование операций

Изложено введение в системный анализ и методологию исследования операций. Рассмотрены основные разделы исследования операций: линейное, целочисленное и динамическое программирование, теория игр и транспортные задачи линейного программирования. Изложены примеры решения задач вручную и с использованием современных пакетов прикладных программ, Java Applets. Дана краткая характеристика отечественных и зарубежных библиотек вычислительной математики и оптимизации. Приведено решение задач линейного программирования с использованием языка моделирования AMPL.

Учебное пособие по дисциплине «Системный анализ и исследование операций», для студентов, обучающихся по направлению 552800 - Информатика и вычислительная техника и направлению 654600 - Информатика и вычислительная техника по специальности 230102 - «Автоматизированные системы обработки информации и управления (АС)»

1.1. Понятия и определения системного анализа

1.1.1. Определение понятия «система» 

1.1.2. Свойства систем

1.1.3. Внешняя среда, границы системы, существенные и несущественные связи

1.1.4. Структура систем

1.2. Классификация систем

1.3. Определение понятий «управление» и «система управления». Структура системы управления

1.4. Этапы системного анализа и их детализация

1.4.1. Определение системного анализа

1.4.2. Этапы системного анализа

1.4.3. Детализация этапов системного анализа

Контрольные вопросы и задания

2.1.  Общая характеристика исследования операций. Предмет, цели и задачи исследования операций

2.2. Основные понятия исследования операций

2.3. Структура математической модели операции

2.4.  Этапы исследования операций 

Контрольные вопросы и задания

3.1. Определения и допущения линейного программирования 

3.2. Задача оптимального распределения ресурсов (сырья). Экономическая интерпретация 

3.3.  Математическая модель общей задачи линейного программирования и формы ее постановки

3.4. Симплексный метод решения задачи линейного программирования 

3.5. Содержательная и математическая постановки конкретной задачи оптимального распределения ресурсов (сырья)

3.6. Решение конкретной задачи оптимального распределения ресурсов (сырья) 

3.7. Решение задачи линейного программирования с использованием пакета прикладных программ

3.8.  Математическая постановка расширенной задачи линейного программирования. Метод искусственного базиса (М-метод) 

3.9. Двойственный симплексный метод

3.10. Модифицированный симплексный метод

3.11. Методы внутренней точки 

3.12. Модели параметрического линейного программирования

3.13. Модели дробно-линейного программирования

3.14.  Многокритериальные задачи линейного программирования

3.15.  Классы и примеры задач, решаемых методами линейного программирования 

Контрольные вопросы и задания

4.1. Содержательная и математическая постановки задачи, двойственной к общей задаче оптимального распределения ресурсов (сырья). Экономическая интерпретация

4.2. Математическая постановка общей двойственной ЗЛП. Правила перехода от прямой ЗЛП к двойственной 

4.3. Составление модели задачи, двойственной к конкретной задаче оптимального распределения ресурсов (сырья)

4.4. Решение двойственной ЗЛП

Контрольные вопросы и задания

5.1. Содержательная и математическая постановки ТЗЛП. Экономическая интерпретация. Ее особенности  

5.2. Методы определения опорного плана

5.3. Метод потенциалов

5.4. Открытая модель 

5.5. Математическая модель двойственной ТЗЛП

5.6. Решение тестовой ТЗЛП

5.7. Решение ТЗЛП с помощью пакета прикладных программ Lindo

5.8. Примеры ТЗЛП

Контрольные вопросы и задания

6.1. Математическая постановка целочисленной задачи линейного программирования (ЦЗЛП). Геометрическая интерпретация

6.2. Методы отсечения

6.3. Комбинаторные методы

6.3.1. Метод ветвей и границ

6.3.2. Алгоритм Лэнд и Дойг

6.4. Решение ЦЗЛП методом отсечения

6.5. Решение ЦЗЛП методом ветвей и границ (решение ЦЗЛП на базе пакета прикладных программ Lindo)

6.6. Решение ЦЗЛП с булевыми переменными методом ветвей и границ на базе пакета прикладных программ Lindo 

6.7. Решение задачи о выборе инвестиционного проекта

6.7.1. Содержательная постановка задачи проекта

6.7.2. Решение ЦЗЛП на базе пакета прикладных программ Lindo 

6.8. Решение задачи о назначении (выборе) 

6.9. Содержательная и математическая постановки задачи о коммивояжере

6.10. Примеры содержательной постановки задач, решаемыхметодами целочисленного программирования

Контрольные вопросы и задания

7.1. Характеристика метода динамического программирования

7.2. Основные положения динамического программирования

7.3. Принцип оптимальности. Основное функциональное уравнение Беллмана

7.4.  Свойства задач, решаемых методом динамического программирования 

7.5.  Этапы решения задач методом динамического программирования. Алгоритм обратной прогонки 

7.6. Содержательная и математическая постановки задачи оптимального распределения финансовых ресурсов

7.7. Составление уравнения Беллмана для задачи определения кратчайшего расстояния

7.8. Решение задачи определения кратчайшего расстояния

7.9.  Решение задачи определения кратчайшего расстояния на базе Java Applet

7.10.  Решение задачи об инвестициях методом динамического программирования 

7.11. Задача о рюкзаке

Контрольные вопросы и задания

8.1. Постановка и алгоритм решения задачи о максимальном потоке на сети

8.2. Алгоритм Форда и Фалкерсона

8.3. Решение задачи определения максимального потока на сети 

Контрольные вопросы и задания

9.1. Стратегические матричные игры

9.1.1. Понятия и определения теории игр

9.1.2. Игры двух лиц с нулевой суммой

9.1.3.  Максиминные и минимаксные стратегии. Принцип минимакса

9.1.4. Игры с седловой точкой. Устойчивость

9.1.5. Формализация игр. Чистые и смешанные стратегии. Функция потерь

9.1.6. Решение матричных игр двух лиц с нулевой суммой 

9.1.7. Решение матричных игр на базе Java Applet 

9.1.8. Связь матричных игр и линейного программирования. Переход от матричных игр к ЗЛП

9.2. Статистические игры 

9.2.1. Понятия и определения теории статистических игр

9.2.2. Классические и производные критерии выбора стратегий L, BL, S, Вальда (ММ), HW , HL, G, Р 

9.3. Кооперативные игры 

9.3.1. Понятия и определения кооперативных игр, их сущность

9.3.2. Характеристическая функция. Дележи. Вектор Шепли

9.3.3. Модель финансирования строительства хранилищ 

Контрольные вопросы и задания

10.1.  Характеристика зарубежных библиотек программ по вычислительной математике и оптимизации 

10.1.1. Библиотека IMSL 

10.1.2. Библиотека NAG 

10.1.3. Библиотека IBM OSL

10.1.4. Библиотека HSL

10.2. Характеристика отечественных библиотек по оптимизации 

10.2.1. Библиотека ПАОЭМ 

10.2.2. Библиотека БЧА НИВЦ МГУ

10.3. Решение задач линейного программирования с использованием языка моделирования AMPL 

10.3.1. Решение простейшей задачи

10.3.2. Решение тестовой ЗЛП 

10.3.3. Решение ЗЛП с использованием языка AMPL

Контрольные вопросы и задания