Министерство образования РФ
Пермский государственный технический университет
Утверждаю
Проректор по учебной работе
_________________________
“____”______________ 2001г.
РАБОЧАЯ ПРОГРАММА
по дисциплине «Системный анализ и исследование операций»
Направление (специальность):
220200 - Автоматизированные системы обработки информации и управления
Факультет: Электротехнический
Кафедра: Автоматизированные системы управления
Курс: 3,4
Семестры: 6,7
Трудоёмкость: 204 часа
Аудиторные занятия: 153 часа
В том числе:
лекции 85 часов
практические занятия 51 час
лабораторные занятия 17 часов
Самостоятельная работа: 51 часа
Курсовая работа (6 семестр)
Виды контроля: зачет, 7 семестр
Экзамен, 6 семестр
Пермь, 2001 г.
Программа разработана в соответствии с государственными требованиями к минимуму содержания и уровню подготовки выпускников по направлениям подготовки дипломированных специалистов "Информатика и вычислительная техника" и с учетом содержания предшествующей дисциплины “Теория принятия решений”.
Программу составил:
к. т.н., профессор
Рабочая программа рассмотрена и утверждена на заседании кафедры АСУ
“_____” _________________ 2001 г.
Заведующий кафедрой АСУ
д. т.н., профессор
Требования ГОСа высшего профессионального образования к обязательному минимуму содержания основной образовательной программы по направлению подготовки дипломированного специалиста специальности “автоматизированные системы обработки информации и управления”
1. Цели и задачи дисциплины, её место в учебном процессе
1.1. Цель преподавания дисциплины
Целью дисциплины является изучение основ системного анализа и исследования операций, а также конкретных моделей и методов, используемых в разработках современных систем автоматизации.
1.2. Задачи изучения дисциплины
Предметами изучения данной дисциплины являются ситуации принятия решений, модели операций, математические методы оптимизации и анализа.
В результате изучения дисциплины студенты должны:
1) знать состояние предмета, его терминологию, методологию, значение для практики, перспективы развития;
2) уметь построить модель системы или выполняемой ею операции, поставить задачу исследования, применить математические методы и вычислительные средства для получения искомых результатов, анализировать и интерпретировать полученные результаты.
Дисциплина является базовой для специальности АСОиУ и обеспечивает комплексную подготовку студентов по различным разделам теории и практики поиска оптимальных системотехнических и управленческих решений.
Дисциплина связана с предшествующими ей дисциплинами "Высшая математика", "Специальная математика", "Теоретические основы автоматизированного управления" и последующими дисциплинами "Моделирование систем", "Проектированию систем информатики" и др.
2. Содержание дисциплины
2.1. Наименование тем, их содержание, объём в часах лекционных занятий (общий объем 85 часа)
2.1.1. Введение (2 час.)
Место системного анализа и исследования операций (СА и ИСО) в современной науке и практике. Предмет и задачи дисциплины СА и ИСО, связь с другими дисциплинами учебного плана специальности 22.02. История развития СА и ИСО.
Роль СА и ИСО в решении задач автоматизации обработки информации, планирования и управления, в подготовке специалистов-системотехников.
2Основы системного анализа (4 час.)
Определение системы. Свойства системы. Виды систем и подходы к их изучению. Возможные классификации систем. Понятия поведения и сложности как признаки классификации. Взаимодействие системы с окружающей средой. Определение структуры системы, виды связей, возможные структуры. Целеполагание.
Терминология: теория систем, системотехника, системный подход, системный анализ. Системный анализ как средство подготовки и обоснования решений. Этапы системного анализа. Моделирование как методология анализа и синтеза систем.
2.1.3. Общая методология исследования операций (8 час.)
Основные понятия: решение, оптимальное решение, операция. Составляющие операции. Возможные определения исследования операций. Основные особенности ЙСО как науки. Этапы операционного исследования и их содержание. Исследование операций и системный анализ. Математическое моделирование как методологическая основа исследования операций. Состав математической модели операции. Понятие критерия оптимальности, требования к критерию в ЙСО. Возможные критерии в задачах АСОИУ. Проблема многокритериальности. Виды математических моделей, определяемых условиями принятия решений (определенности, риска, неопределенности). Некоторые принципы принятия решений в условиях неопределенности. Классы задач исследования операций: распределения, управления запасами, упорядочения, состязательные и др.
2.1.4. Общая характеристика задач оптимизации (2 час.)
Постановка задачи оптимизации в общем виде. Классификация задач оптимизации. Место и роль задач математического программирования в системном анализе и исследовании операций. Характеристика методов решения задач оптимизации.
2.1.5. Методы классического анализа (5 час.)
Основные положения теории экстремумов. Допустимое множество. Классификация экстремумов. Теорема существования решения (Вейерштрасса). Экстремальные точки. Свойства функций. Исследование на экстремум функций многих переменных. Достаточные условия оптимума. Проблема отыскания условного оптимума.
Обоснование метода множителей Лагранжа для задачи с двумя переменными. Обобщение на многомерные задачи. Использование метода для решения задачи распределения ресурсов в общем случае.
Область применения классических методов. Понятие о вариационном исчислении, принципе максимума Понтрягина.
2.1.6. Динамическое программирование (ДП) в исследовании операций (10 час.)
Многошаговые процессы. Идея метода ДП. Принцип оптимальности Р. Беллмана. Условия применимости метода. Геометрическое представление концепции метода, функциональное уравнение ДП в общем случае. Процедура динамического программирования. Задача распределения одного вида ресурса, вычислительные аспекты. Достоинства метода ДП. Численные примеры: задача организации выпуска нескольких видов продукции, задача отыскания кратчайшего пути. Применение ДП к задачам с мультипликативным критерием. Декомпозиция в ДП.
Многомерные задачи ДП. Проблема размерности. Снижение размерности с помощью множителей Лагранжа. Область применения динамического программирования.
2.1.7. Линейное программирование (ЛП)
2.1.7.1.Задачи линейного программирования (4 час.)
Общая постановка задачи ЛП. Примеры задач, описываемых моделями ЛП: составление рациона, использование ресурсов, транспортная задача, общая распределительная задача, загрузки оборудования, игра 2-x лиц с нулевой суммой. Условия, приводящие к моделям ЛП
Каноническая форма задач ЛП. Приведение задач к каноническому представлению.
2.1.7.2. Свойства линейных моделей (2 час.)
Основные понятия ЛП. Допустимое решение, допустимое множество, оптимальное решение задач ЛП. Случаи разрешимости и неразрешимости задач ЛП.
Геометрическая интерпретация задач ЛП. Графическое решение на плоскости, обобщение на многомерное пространство, вырожеденность. Базисное решение. Оценка числа вершин. Краткая характеристика методов решения задач ЛП.
2.1.7.3. Симплекс - метод (7 час.)
Сущность метода. Линейно-независимые векторы, базис. Переход от одного базисного решения к другому. Признак оптимальности, его экономическая интерпретация, основные этапы симплекс-метода. Определение начального базисного решения, двухэтапный подход. Связь между параметрами последовательных итераций. Симплекс-таблица, алгоритм симплекс-метода. Численный пример.
Особенности метода для случая двусторонних ограничений на переменные. Модифицированный симплекс-метод.
2.1.7.4.Двойственный и параметрический анализ (4 час.)
Двойственность задач ЛП. Построение модели двойственной задачи в случае симметрии и в общем случае. Экономическая интерпретация двойственной задачи. Основные теоремы двойственности и их интерпретация. Определение решения двойственной задачи на основе решения прямой. Использование двойственности в решении задач ЛП. Двойственный симплекс-метод.
Параметрическое программирование. Параметрический анализ вектора ограничений. Параметрический анализ линейной формы. Численный пример. Применение параметрических решений.
2.1.7.5. Транспортные задачи (6 час.)
Основные модели транспортных задач (ТЗ) и их характерные особенности. Условия разрешимости ТЗ. Построение начального плана перевозок (правила северо-западного угла, минимального элемента). Метод потенциалов: цикл пересчета, потенциалы и их определение, признак оптимальности, алгоритм метода потенциалов, случай вырожденности. Численный пример.
Двойственная пара транспортных задач, экономическая интерпретация.
Отличие распределительного метода от метода потенциалов. Приведение открытой (несбалансированной) ТЗ к сбалансированной (формальные и неформальные способы).
Транспортные задачи с ограниченной пропускной способностью (Td-задачи). Обобщение метода потенциалов на Тd-задачи.
Понятие о транспортных задачах с неоднородным грузом, по критерию времени, многоиндексных. Транспортные задачи в сетевой постановке.
2.1.7.6. Задачи большой размерности (4 час.)
Проблемы большой размерности в ЛП. Понятие о блочном программировании. Метод декомпозиции Данцига-Вулфа. Применение метода для транспортных задач.
2.1.8 Целочисленное программирование (6 час.)
Особенности дискретных задач. Источники дискретности. Целочисленные задачи. Проблемы целочисленности. Методы решения. Идея метода отсечения, обоснование метода. Алгоритм Гомори. Практическая применимость алгоритмов отсечения.
Комбинаторные методы. Метод ветвей и границ. Алгоритм ветвей и границ для задач линейного целочисленного программирования. Численный пример. Аддитивный алгоритм. Понятие о приближенных методах.
2.1.9. Нелинейное программирование (10 час.)
Характеристика задач нелинейного программирования. Функция Лагранжа и седловая точка. Теорема Куна-Таккера. Квадратичное программирование. Дробно-линейное программирование. Сепарабельное программирование. Понятие о геометрическом программировании.
Методы поиска оптимума (методы спуска). Особенности целевой функции. Классификация методов. Сходимость и скорость сходимости. Одномерные методы: деления шага пополам, квадратичной апроксимации, сокращения интервала неопределенности («золотого сечения», чисел Фибоначчи, средней точки), Ньютона-Рафсона.
Многомерные методы: покоординатного спуска, симплексный, градиентный, наискорейшего спуска, Ньютона, случайного поиска. Понятие о генетических алгоритмах, методах сопряженных направлений, поиска глобального оптимума многоэкстремальных функций.
Методы минимизации при наличии ограничений: проектирования градиента, штрафных и барьерных функций, случайного поиска. Сравнение методов.
2.1.10. Вероятностные модели операций (6 час.)
Случайные факторы и их природа. Случайные процессы. Потоки событий. Простейший поток и его свойства. Потоки Пальма и Эрланга.
Марковские процессы. Уравнения Колмогорова. Переходные и стационарные процессы, предельные вероятности. Потоки событий и марковские цепи. Типовые марковские процессы: гибели и размножения, циклические.
Система массового обслуживания (СМО) и ее компоненты. Классификация СМО. Символика моделей СМО по Кендаллу. Показатели эффективности СМО.
Марковские системы. Одноканальная СМО с отказами. Многоканальная СМО с отказами. Одно - и многоканальные СМО с ожиданием. Замкнутые СМО. СМО с непуассоновскими потоками событий.
Понятие о методе статистических испытаний. Проблемы разработки и использования вероятностных моделей в АСУ.
2.1.11. Неполные модели операций (4 час.)
Понятие неполноты модели. Неопределенные факторы, виды неопределенностей. Стохастическое программирование, общие понятия, варианты постановок задач стохастического программирования. Методы стохастического квазиградиента и стохастической аппроксимации.
Многокритериальные задачи. Нечеткое программирование.
2.1.12. Заключение (1 час)
Тенденции и перспективы развития системного анализа и исследования операций. Практическая приложимость СА и ИСО.
2.2. Перечень практических занятий (51 час.)
Цель проведения занятий - научить студентов основам операционных исследований, выработать определенные навыки построения конкретных моделей операций, практически освоить методы оптимизации и анализа операций и решений.
2.2.1. Матричные игры (2 час.)
Формализация операции как игры. Решение игры в чистых стратегиях. Графический метод решения игры в области смешанных стратегий.
2.2.2. Метод множителей Лагранжа (2 час.)
Аналитическое и графическое решение задачи минимизации с одним условием-равенством методом неопределенных множителей Лагранжа. Сравнение с методом исключения переменных.
2.2.3. Динамическое программирование (4 час.)
Построение модели. Определение параметров состояния. Вывод рекуррентного соотношения, условная и безусловная оптимизация.
2.2.4. Модели линейного программирования (2 час.)
Определение критериев операции, параметризация, построение и анализ моделей ЛП.
2.2.5. Геометрия задач ЛП (2 час.)
Геометрическое решение задеч линейного программирования
2.2.6. Симплекс - метод (4 час)
Приведение модели к канонической форме, определение начального базисного решения, симплекс-таблица, итерации, анализ оптимального решения. Решение задачи ЛП модифицированным симплекс-методом.
2.2.7. Двойственность задач ЛП (2 час.)
Составление модели двойственной задачи. Определение двойственных переменных по решению прямой задачи на основе теорем двойственности.
2.2.8. Двойственный симплекс-метод (2 час.)
Решение задачи двойственным симплекс-методом. Сравнение с прямым.
2Параметрический анализ в ЛП (3 час.)
Параметрический анализ вектора ограничений для трех вариантов изменения ресурсов. Параметрический анализ коэффициентов линейной формы в общем случае. Анализ результатов.
2.2.10. Решение Т-задачи (2 час.)
Приведение исходной задачи к сбалансированному виду, определение начального плана перевозок. Решение задачи методом потенциалов. Анализ оптимального решения.
2.2.11. Решение Тd-задачи (2 час.)
Построение искусственного начального плана перевозок. Применение обобщенного метода потенциалов для решения задачи. Анализ особенностей решения Td-задачи.
2.2.12. Декомпозиция задач ЛП (3 час.)
Решение Т-задачи методом Данцинга-Вульфа.
2.2.13. Целочисленное программирование (4 час.)
Решение задачи линейного целочисленного программирования методом ветвей и границ с использованием симплекс-метода и графического метода. Построение и анализ дерева решений.
2.2.14. Квадратичное программирование (2 час.)
Решение задачи квадратичного программирования с использованием конечного метода выпуклого программирования. Анализ особенностей метода.
2.2.15. Методы поиска безусловного оптимума (5 час.)
Отыскание минимума функции одной переменной методами золотого сечения и чисел Фибоначчи. Минимизация функции двух переменных методами первого и второго порядка. Анализ и сравнение результатов.
2.2.16. Методы поиска условного оптимума (2 час.)
Нахождение условного минимума методом проектирования градиента.
2.2.17. Системы массового обслуживания (4 час.)
Определение характеристик одноканальной и многоканальной СМО с ожиданием. Сравнение детерминированного и вероятностного подходов.
2.2.18. Системы сетевого планирования и управления (4 час.)
Построение сети типа "работы-дуги". Определение сроков наступления событий, начала и окончания работ, критического пути и резервов времени. Построение модели оптимизации по затратам. Анализ вероятностной сети.
2.3. Перечень лабораторных работ (17 час.)
2.3.1. Целевые функции (3 час.)
Исследование на компьютере унимодальных, многоэкстремальных, седлообразных и овражных функций.
2.3.2. Нелинейное программирование (12 час.)
Исследование методов прямого поиска. Программирование и применение метода Хука-Дживса. Получение траекторий поиска на фоне линий уровня.
Исследование методов, использующих производные. Программирование и применение методов наискорейшего спуска и Ньютона. Получение траекторий поиска на фоне линий уровня.
Исследование методов поиска условного минимума. Программирование и применение метода штрафных функций. Получение траекторий поиска на фоне линий уровня.
2.3.3. Системы массового обслуживания (2 час.)
Определение показателей работы СМО с потоком заявок типа потоков Эрланга и простейшего потока обслуживания.
2.4. Курсовая работа (18 час.)
Цель курсовой работы - закреплению и углубление знаний, полученных в процессе изучения СА и ИСО, развитие навыков самостоятельной работы при решении конкретных задач, близких по содержанию к производственным задачам оптимального планирования и управления.
Задание на курсовую работу носит индивидуальный характер. Выполнение работы включает основные этапы операционного исследования: осмысление задачи, выбор критерия, параметризация и построение математической модели, выбор метода решения, нахождение оптимального решения, вариантный и послеоптимизационный анализ. На вычислительных этапах используются пакеты прикладных программ milp88, Lindo.
2.5. Самостоятельная работа студентов (51 час.)
1. Подготовка и выполнение контрольной работы - 2 неделя.
2. Выполнение и защита расчетно-графической работы 'Исследование детерминированной задачи управления запасами".
З. Выполнение и защита расчетной работы "Формализация и решение задачи методом динамического программирования".
4. Изучение теоретического материала, консультации с преподавателем - один раз в две недели.
5. Выполнение индивидуальных заданий, защита практических работ и индивидуальных заданий.
6. Выполнение и защита курсовой работы.
З. УЧЕБНО - МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ
Основная литература
1. , Исследование операций.-М.:Сов. радио, с
2. , Загоруйко операций: Учеб. для втузов/ ред. . - М.: Изд-во МГТУ, 2000.-435 с. -(Математика в техническом университете, В.20).
3. Гольдштейн и методы исследования операций: Учеб. пособие. - Пермь: Изд-во ПГТУ. Ч.1: -2000.-113 с.
4. , Северцев операций: принципы принятия решений и обеспечение безопасности: Учеб. пособие/ ред. . - М.: Физматлит, 2000.-318 с.
5. Зайченко операций.-Киев, Выща шк., с.
6. , Тарасенко системного анализа. Учеб. пособие для вузов.-М.:Высш. школа,1989.-367 с.
Дополнительная литература
1. Акулич программирование в примерах и задачах: Учебное пособие.-М.:Высш. шк.,1993.-336 с.
2. Нелинейное программирование. Теория и алгоритмы.-М.:Мир,1982.-583 с.
3. Беллман P., Прикладные задачи динамического программирования.-М.:Наука,1965.
4. Основы исследования операций (В 3-х томах)-М.:Мир,-тс.-тс.-тс.
5. Ермолаев стохастического программирования.-М.:Наука,1976.-240 с.
6. 3айченко Ю. П, Щумилова операций: Сборник задач-Киев:Выща шк., 1990.-239 с.
7. Гольдштейн заданий и задач по курсу "Системный анализ и исследование операций" для студ. спец. 2202 (АСОУ) дневного и вечерне-заочного отд-ний/ Перм. гос. техн. ун-т.. - Пермь: Изд-во ПГТУ, 1998.-50 с.
8. Карманов программирование.-5-е изд., испр - М.: Физматлит, 2000.-263 с.
9. Линейное и нелинейное программирование. Под ред. .-Киев, Вища шк., 1975.-372 с.
10. Современное линейное программирование,-М.:Мир,1984.-224 с.
11. 0рловский C. A, Проблемы принятия решений при нечеткой исходной информации.-М.:Наука,1981,-208 с.
12. 0уэн Г. Теория игр.-М.:Мир,1971.-232 с.
13. Современное состояние теории исследования операций /под ред, . -М.:Наука,1979.-464 с.
14. Введение в исследование операций (В 2-x кн.).-М.:Мир,1985, Кн.1.-479 с., Кн. 2.-469
15. Многокритериальная оптимизация. Теория вычисления и приложения. - М.: Радио и связь, 1992.-504 с.
16. , Гольштейн E. Г. - Задачи и методы линейного программирования.-М:Сов. радио,1964.-736 с.
Приложение к рабочей программе
КАРТА ОБЕСПЕЧЕННОСТИ УЧЕБНО-МЕТОДИЧЕСКОЙ ЛИТЕРАТУРОЙ
Дисциплины "Системный анализ и исследование операций"
Кафедра АСУ
Факультет Электротехнический
специальность | семестры | Количество студентов | Библиогафическое описание издания (автор, заглавие, вид, место, изд-во, год издания, кол-во страниц) | Количество экземпляров в библиотеке | Основной лектор |
АСУ | 67 | 40 | , Исследование операций.-М.:Сов. радио, с , Загоруйко операций: Учеб. для втузов/ ред. . - М.: Изд-во МГТУ, 2000.-435 с. -(Математика в техническом университете, В.20). Гольдштейн и методы исследования операций: Учеб. пособие. - Пермь: Изд-во ПГТУ. Ч.1: -2000.-113 с. , Северцев операций: принципы принятия решений и обеспечение безопасности: Учеб. пособие/ ред. . - М.: Физматлит, 2000.-318 с. Зайченко операций.-Киев, Выща шк., с. , Тарасенко системного анализа. Учеб. пособие для вузов.-М.:Высш. школа,1989.-367 с. Акулич программирование в примерах и задачах: Учебное пособие.-М.:Высш. шк.,1993.-336 с. Нелинейное программирование. Теория и алгоритмы.-М.:Мир,1982.-583 с. Беллман P., Прикладные задачи динамического программирования.-М.:Наука,1965. Основы исследования операций (В 3-х томах)-М.:Мир,-тс.-тс.-тс. Ермолаев стохастического программирования.-М.:Наука,1976.-240 с. 3айченко Ю. П, Щумилова операций: Сборник задач-Киев:Выща шк., 1990.-239 с. Гольдштейн заданий и задач по курсу "Системный анализ и исследование операций" для студ. спец. 2202 (АСОУ) дневного и вечерне-заочного отд-ний/ Перм. гос. техн. ун-т.. - Пермь: Изд-во ПГТУ, 1998.-50 с. Карманов программирование.-5-е изд., испр - М.: Физматлит, 2000.-263 с. Линейное и нелинейное программирование. Под ред. .-Киев, Вища шк., 1975.-372 с. Современное линейное програм-мирование,-М.:Мир,1984.-224 с. 0рловский C. A, Проблемы принятия решений при нечеткой исходной информации.-М.:Наука,1981,-208 с. 0уэн Г. Теория игр.-М.:Мир,1971.-232 с. Современное состояние теории исследования операций /под ред, . - М.:Наука,1979.-464 с. Введение в исследование операций (В 2-x кн.).-М.:Мир,1985, Кн.1.-479 с., Кн. 2.-469 Многокритериальная оптимизация. Теория вычисления и приложения. - М.: Радио и связь, 1992.-504 с. , Гольштейн E. Г. - Задачи и методы линейного программирования.-М:Сов. радио,1964.-736 с. | 43 27 120 11 89 11 17 4 4 5/4/4 0 44 74 1 8 8 2 6 2 1 8 11 | Гольдш-тейн А. Л. |
