Содержание программы
Тема 1. Введение. Математические методы и модели в принятии решений.
Процесс принятия решений, его участники и этапы. Лицо, Принимающее Решение (ЛПР), его информированность. Математические методы и принятие рациональных управленческих решений. Оптимизация как способ описания рационального поведения.
Взаимосвязь математической теории принятия решений, исследования операций и системного анализа. Необходимость разработки и использования моделей. Моделирование, его виды и этапы. Преимущества математического моделирования по сравнению с натурными экспериментами. Основные этапы моделирования.
Классификация моделей по объекту исследования, уровню агрегирования, применяемому математическому аппарату. Система экономико-математических моделей.
Вопросы применения средств вычислительной техники.
Базовый учебник: [1],[3].
Дополнительная литература: [5], [7], [10], [13], [14], [18].
Тема 2. Линейные оптимизационные модели и линейное программирование.
Задачи линейного программирования (ЛП), их особенности, место и роль в системе оптимизационных математических моделей. Графический метод решения задачи ЛП.
Общая постановка и различные формы задачи ЛП. Примеры типичных постановок задач ЛП: линейная модель производства, транспортная задача, задача о смесях. Переход от описания проблемной ситуации к построению задач ЛП.
Геометрия задач ЛП. Выпуклые множества. Выпуклые оболочки. Вершины многогранного множества. Экстремумы линейной функции на многограннике и многогранном множестве. Алгебра задач ЛП. Базисные и допустимые базисные решения. Связь вершин многогранника допустимых решений и базисных решений. Понятие о симплекс-методе решения задач ЛП.
Теория двойственности в ЛП. Взаимно двойственные задачи. Функция Лагранжа. Содержательная интерпретация двойственных переменных. Анализ чувствительности оптимального решения к изменениям параметров задачи.
Компьютерные системы линейного программирования.
Базовый учебник: [1].
Дополнительная литература: [4], [5], [9], [14].
Тема 3. Нелинейные оптимизационные модели, нелинейное программирование.
Принятие решений в условиях определенности; детерминированная статическая задача оптимизации. Понятие нелинейного программирования. Метод множителей Лагранжа. Теория Куна-Такера. Содержательные примеры.
Прямые методы решения нелинейных оптимизационных задач. Градиентный метод.
Компьютерные системы для решения задач нелинейного программирования.
Базовый учебник: [1].
Дополнительная литература: [6], [8].
Тема 4. Целочисленная оптимизация. Оптимизация на графах.
Целочисленное программирование. Методы решения задач целочисленного программирования.
Транспортные задачи линейного программирования. Задача о назначении. Задача о выборе кратчайшего пути. Метод потенциалов. Теорема о целочисленности решения.
Понятие о графе. Ориентированный граф. Граф транспортной сети. Задача о максимальном потоке в сети. Сведение к задаче линейного программирования. Связь с транспортной задачей в матричной постановке. Алгоритм Форда-Фалкерсона для отыскания максимального потока.
Понятие о сетевом графе. Задача о критическом пути в сетевом графике. Применение сетевых графов в современном управлении проектами.
Базовый учебник: [1].
Дополнительная литература: [5], [10], [11], [12], [13], [21].
Тема 5. Модели оценки эффективности организационных единиц.
Задача оценки эффективности однотипных самостоятельных организационных (управленческих) единиц (ОЕ). Примеры из экономики и менеджмента. Анализ оболочек данных. Составные ОЕ. Множество производственных возможностей и его эффективная граница. Эффективность ОЕ по входам и выходам. Эффективные и неэффективные ОЕ. Оценка эффективности ОЕ при постоянной отдаче от масштаба производства. Обобщение удельных критериев эффективности на многомерный случай. Мультипликативная модель оценки эффективности ОЕ: дробно-линейная задача и связанная с ней пара двойственных задач линейного программирования. Использование результатов анализа оболочек данных для выработки рекомендаций по улучшению работы неэффективных ОЕ.
Дополнительная литература: [19],[20].
Тема 6. Многокритериальное принятие решений.
Понятие о многокритериальной оптимизации. Причины многокритериальности, примеры многокритериальных задач. Пространство решений и пространство оценок. Доминирование и оптимальность по Парето и Слейтеру. Роль понятия Парето-оптимальности в принятии решений.
Достаточные условия оптимальности по Парето и Слейтеру в форме свертки критериев в один обобщенный критерий. Коэффициенты важности в линейных свертках.
Необходимые условия оптимальности в выпуклом случае. Многокритериальные задачи линейного программирования, необходимые и достаточные условия оптимальности для них. Построение оптимальных по Парето решений в задаче ЛП с использованием линейных сверток критериев.
Методы выбора единственного решения из множества Парето-оптимальных решений. Использование линейных и нелинейных функций свертки, ограниченность такого подхода, в частности, применения весовых коэффициентов. Метод уступок. Целевое программирование.
Базовый учебник: [2].
Дополнительная литература: [15], [16], [17].
Тема 7. Паросочетания и обобщенные паросочетания.
Понятие о двудольном графе. Задача о распределении работ. Задача о свадьбах. Паросочетания. Совершенные и максимальные паросочетания. Условие Холла. Чередующиеся цепи. Трансверсали семейства множеств.
Предпочтения. Условия классической рациональности предпочтений. Обобщенные паросочетания. Устойчивость паросочетаний. Теорема о существовании устойчивого паросочетания при любых предпочтениях участников (теорема Гейла – Шепли). Манипулирование предпочтениями. Примеры обобщенных паросочетаний.
Базовый учебник: [3].
Дополнительная литература: [21].
Тема 8. Коллективное принятие решений, задача голосования.
Процедуры выработки коллективных решений. Правило простого большинства. Парадокс Кондорсе. Правило Борда. Внутренняя и внешняя устойчивость. Ядро. Некоторые нелокальные правила принятия решений.
Парадокс Эрроу. Манипулирование и стратегическое поведение участников при голосовании.
Базовый учебник: [3].
Дополнительная литература: [22], [23].
Тема 9. Коалиции и влияние групп в парламенте.
Голосование с квотой. Индексы влияния. Индекс влияния Банцафа. Влияние стран в Совете Безопасности ООН. Институциональный баланс власти в Совете министров расширенного Евросоюза. Примеры других индексов влияния.
Базовый учебник: [3].
Дополнительная литература: [24].
Тема 10. Задача дележа.
Историческая постановка задачи. Процедура «дели и выбирай». Манипулирование при дележе. Критерии справедливости дележа. Процедура «подстраивающийся победитель» и ее свойства. Разрешение трудовых споров. Слияние фирм. Раздел имущества. Дележ при числе участников больше двух.
Базовый учебник: [3].
Дополнительная литература: [25].
Литература
- А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.1. Общие положения. Математическое программирование. Москва: ФИЗМАТЛИТ, 2010.
- А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.2. Многокритериальность. Динамика. Неопределенность. Москва: ФИЗМАТЛИТ, 2010.
- Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц. Бинарные отношения, графы и коллективные решения. М: Издательский дом ГУ-ВШЭ, 2006
4. Ф.П. Васильев, А.Ю. Иваницкий. Линейное программирование. М. Факториал Пресс, 2008.
5. Дж. Данциг. Линейное программирование, его обобщения и применение. М.: Прогресс, 1966.
- М. Интрилигатор. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.
- Х. А. Таха. Введение в исследование операций. М.: Издательский дом «Вильямс», 2005.
8. Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.
9. Л.В. Канторович, А.Б. Горстко. Математическое оптимальное программирование в экономике. М.: Знание, 1968.
10. Г. Вагнер. Основы исследования операций. М.:Мир, 1972 Т.1
11. Г. Вагнер. Основы исследования операций. М.:Мир, 1973 Т.2
12. Л. Р. Форд, Д. Р. Фалкерсон. Потоки в сетях. М.: Мир, 1966.
13. Исследование операций в экономике. Под ред. Кремера Н.Ш. М.: ЮНИТИ, 2005.
14. Е.С. Вентцель. Исследование операций. Задачи, принципы, методология. М.: ВШ, 2001.
15. В.В. Подиновский Введение в теорию важности критериев в многокритериальных задачах принятия решений. М.: Физматлит, 2007.
16. В.Д. Ногин. Методы оптимальных решений. СПб.: СПб филиал ГУ – ВШЭ. 2006.
17. В.В. Подиновский, В.Д. Ногин. Парето-оптимальные решения многокритериальных задач. М.: Физматлит. 2007.
18. А.А. Петров, И. Г. Поспелов, А.А. Шананин. Опыт математического моделирования экономики. М.: Энергоатомиздат. 1996.
Источник
Методы оптимальных решений (стр. 2 )
 | Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 |
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.
8 Содержание дисциплины
Тема 1. Введение. Математические методы и модели в принятии решений
Процесс принятия решений, его участники и этапы. Лицо, Принимающее Решение (ЛПР), его информированность. Математические методы и принятие рациональных управленческих решений. Оптимизация как способ описания рационального поведения.
Взаимосвязь математической теории принятия решений, исследования операций и системного анализа. Необходимость разработки и использования моделей. Моделирование, его виды и этапы. Преимущества математического моделирования по сравнению с натурными экспериментами. Основные этапы моделирования.
Классификация моделей по объекту исследования, уровню агрегирования, применяемому математическому аппарату. Система экономико-математических моделей.
Вопросы применения средств вычислительной техники.
Базовый учебник: [1] (тема 1), [3] (введение, гл.1).
Основная литература: [9] (гл.1-2).
Дополнительная литература:, [12], [20] (гл.1), [13] (гл.1-3).
Тема 2. Линейные оптимизационные модели и линейное программирование
Задачи линейного программирования (ЛП), их особенности, место и роль в системе оптимизационных математических моделей. Примеры: задачи о раскрое материалов, о планировании производства, о диете, о смесях и другие. Графический метод решения задачи ЛП.
Общая постановка и различные формы задачи ЛП. Геометрия задач ЛП. Выпуклые множества. Выпуклые оболочки. Вершины многогранного множества. Экстремумы линейной функции на многограннике и многогранном множестве. Алгебра задач ЛП. Базисные и допустимые базисные решения. Связь вершин многогранника допустимых решений и базисных решений. Понятие о симплекс-методе решения задач ЛП.
Задачи транспортного типа (ТЗ) и сводящиеся к ним. Замкнутая ТЗ. Сведение открытых ТЗ с избытком и с дефицитом запасов к стандартной (замкнутой) ТЗ. Задачи о размещении производства, о назначении персонала и о конкурсе проектов. Общие свойства транспортных задач. Построение допустимого решения ТЗ (методы северо-западного угла и наименьшей стоимости). Транспортные задачи с запрещенными маршрутами. Задачи, сводящиеся к ТЗ или примыкающие к ним — задача о перевозках с промежуточной обработкой и распределительная задача. Свойство целочисленности оптимальных базисных решений в ТЗ с целочисленными условиями (запасами и потребностями).
Теория двойственности в ЛП. Взаимно двойственные задачи. Теоремы двойственности. Содержательная интерпретация двойственных переменных. Анализ чувствительности оптимального решения к изменениям параметров задачи.
Базовый учебник: [3] (гл. 1-7).
Основная литература: [5] (гл. 1), [8]
Дополнительная литература: [15].
Тема 3. Задачи, сводящиеся к линейному программированию. Модели и методы целочисленного линейного программирования.
Задачи дробно-линейного программирования и сведение их к задаче ЛП. Пример — задача об оптимальной рентабельности производства.
Задачи кусочно-линейного программирования, максиминные задачи, методы их решения.
Задачи целочисленного линейного программирования. Метод ветвей и границ. Особенности решения задач с булевыми переменными. Задача об оптимальном наборе инвестиционных проектов. Учет логических условий. Задачи дискретного программирования и их сведение к задаче целочисленного ЛП.
Компьютерные системы линейного программирования.
Базовый учебник:[3] (гл. 8).
Основная литература: [11] (гл. 3, 4).
Дополнительная литература: [17]
Тема 4. Нелинейные оптимизационные модели и нелинейное программирование
Принятие решений в условиях определенности; детерминированная статическая задача оптимизации. Математическое программирование – аппарат решения оптимизационных задач. Классификации задач математического программирования. Содержательные примеры.
Классические методы оптимизации (повторение). Виды экстремумов. Достаточное условие существования глобального экстремума (теорема Вейерштрасса). Безусловная оптимизация (в отсутствии ограничений). Производная по направлению и градиент. Необходимые и достаточные условия локального экстремума. Задача на условный экстремум, примеры из экономики. Функция Лагранжа. Необходимые и достаточные условия условного экстремума. Интерпретация множителей Лагранжа.
Выпуклые множества и функции, их свойства. Необходимые и достаточные условия выпуклости для дважды дифференцируемых функций. Выпуклая задача нелинейного программирования, ее экстремальные особенности.
Общая задача нелинейного программирования. Функция Лагранжа. Условия локального экстремума в задаче оптимизации на неотрицательном ортанте. Теорема Куна-Таккера в «седловой» и дифференциальной форме. Условие Слейтера и его существенность. Условия дополняющей нежесткости.
Понятие о численных методах решения задач нелинейного программирования. Классификация методов. Безусловная оптимизация: градиентные методы и методы второго порядка. Условная оптимизация, метод штрафных функций.
Компьютерные системы для решения задач нелинейного программирования.
Базовый учебник: [1] (темы 3,4), [4] (гл. 2-4), [3] (гл. 10-11,13) .
Основная литература: [7], [11] (гл. 5 ).
Дополнительная литература: [17] (гл. 3 ).
Тема 5. Многокритериальное принятие решений
Понятие о многокритериальной оптимизации. Причины многокритериальности, примеры многокритериальных задач (задача об оптимальном портфеле ценных бумаг, метод «стоимость-эффективность», задача о диете с двумя критериями и другие). Пространство решений и пространство оценок. Доминирование и оптимальность по Парето и Слейтеру. Роль понятия Парето-оптимальности в принятии решений.
Достаточные условия оптимальности по Парето и Слейтеру в форме свертки критериев в один обобщенный (глобальный, интегральный) критерий (скаляризация). Коэффициенты важности в линейных свертках.
Необходимые условия оптимальности в выпуклом случае. Многокритериальные задачи линейного программирования, необходимые и достаточные условия оптимальности для них. Построение оптимальных по Парето решений в задаче ЛП с использованием линейных сверток.
Необходимые и достаточные условия оптимальности по Слейтеру. Собственно эффективные решения, их связь с Парето-оптимальными. Выпуклые задачи многокритериальной оптимизации, невыпуклость множества достижимых оценок для них. Необходимые и достаточные условия оптимальности (собственно-эффективности) в выпуклой задаче многокритериальной оптимизации.
Методы выбора единственного решения из множества Парето-оптимальных решений. Использование линейных и нелинейных функций свертки, ограниченность такого подхода, в частности, применения весовых коэффициентов. Среднеквадратическое решение, решение Нэша. Метод уступок. Целевое программирование.
Базовый учебник: [1] (тема 7)
Основная литература: [10] (гл. 1-2), [11] (гл. 7 )
Дополнительная литература: [16].
Тема 6. Принятие решений в условиях неопределенности
Задачи оптимизации в условиях неопределенности. Виды неопределенности: вероятностная (статистическая), полная (неустранимая, существенная), комбинированная. Принципы оптимальности (критерии выбора решений) в случае полной неопределенности – Вальда (гарантированного результата, максимина,) Гурвица (пессимизма-оптимизма), Сэвиджа (минимаксного сожаления), Бернулли-Лапласа (недостаточного основания).
Оптимизация в условиях вероятностной неопределенности (при риске). Дисперсия как характеристика риска. Сведение исходной задачи к задаче с двумя критериями – характеристикой среднего значения (математическое ожидание) и характеристикой риска (дисперсия).
Базовый учебник: [2], (тема 10).
Дополнительная литература: [17] (гл. 7), [21] (гл. 1).
Тема 7. Оптимизация динамических систем с дискретным временем
Задача оптимального управления динамической системой (непрерывный и дискретный многошаговый варианты). Переменные состояния и управляющие переменные. Программные управления и синтез управлений.
Динамическое программирование. Принцип оптимальности и уравнение Беллмана для дискретных задач оптимального управления; схема их решения. Примеры решения практических задач методом динамического программирования (стратегия замены оборудования, распределение ресурсов). Вычислительные аспекты метода.
Базовый учебник: [3] (гл. 12).
Дополнительная литература: [20] (гл.6).
Тематика заданий по различным формам текущего контроля
Контрольные работы содержат задачи по следующим темам дисциплины:
— контрольная работа № 1: построение моделей по вербальному описанию задачи, линейное программирование, двойственность в ЛП (темы 1, 2);
— домашнее задание: многокритериальные задачи и их сведение к однокритериальным (тема 4);
— контрольная работа № 2: нелинейное программирование, численные методы, многокритериальная оптимизация (темы 4, 5);
метод динамического программирования (тема 7);
— письменный экзамен: по темам 4 – 7.
Методические рекомендации преподавателю
Одно из практических занятий по теме 3. «Линейные оптимизационные модели и линейное программирование» целесообразно провести в компьютерном классе.
Методические указания студентам
Для успешного изучения дисциплины рекомендуется перед каждым практическим занятием повторить теоретический материал по конспекту лекций, а после активной работы на занятии – выполнять полученные задания (решать предложенные задачи) и изучать указанную в программе литературу.
Для решения задач линейного программирования можно использовать любую имеющуюся компьютерную программу, которая позволяет проводить анализ чувствительности, в частности, MS Exсel.
9 Оценочные средства для текущего контроля и аттестации студента
9.1 Тематика заданий текущего контроля
Контрольная работа №1
Темы: «Линейное программирование. Двойственность»
ЗАДАЧА 1. Приведите следующую задачу линейного программирования (ЛП) к стандартному виду (исключением базисных переменных) и к каноническому виду.
ЗАДАЧА 2. Формализуйте приведенную задачу в виде задачи ЛП: введите обозначения, выпишите ВСЕ ограничения и целевую функцию. (РЕШАТЬ полученную задачу не надо).
Бетонный завод может выпускать четыре сорта бетона. При этом используется 3 вида сырья: цемент, песок, щебень, запасы которых известны. Известны также удельные затраты сырья, а также доход от выпуска кубометра каждого вида бетона.
Требуется найти план производства, который обеспечивает максимум дохода.
Задайте конкретные числовые данные и после этого запишите задачу в виде задачи ЛП.
ЗАДАЧА 3. Найти оптимальное решение приведенной задачи ЛП, используя графическое решение двойственной задачи и условия дополняющей нежесткости.
ЗАДАЧА 4. Найти допустимое базисное решение транспортной задачи с помощью метода наименьшей стоимости северо-западного угла.
Источник
