Правительство Российской Федерации
Государственный университет -
Высшая школа экономики
Факультет бизнес-информатики
Программа дисциплины
Исследование операций
для направления 010500.62 «Прикладная математика» подготовки бакалавра
Автор Федотов А. Г.
Рекомендовано секцией УМС Одобрено на заседании кафедры
_________________________ высшей математики
на факультете экономики
Председатель Зав. кафедрой
_____________ __________ _____________ Ф.Т. Алескеров ________________
" __" __________ 200_ г. " __ " ______________ 200_ г.
Утверждено УС факультета
_____________
Ученый секретарь
_______________ ______________
" __ " _________ 200_ г.
Москва
Тематический план учебной дисциплины
№
|
Название темы
|
Всего часов
|
Аудиторные часы
|
Самост. работа
|
лекции
|
семинары
|
1
|
Основы выпуклого анализа
|
8
|
8
|
0
|
28
|
2
|
Линейное программирование
|
6
|
6
|
0
|
30
|
3
|
Целочисленное программирование
|
8
|
4
|
4
|
18
|
4
|
Сетевые задачи
|
4
|
2
|
2
|
|
5
|
Матричные игры
|
8
|
4
|
4
|
|
6
|
Динамическое программирование
|
8
|
4
|
4
|
|
| Итого |
42
|
28
|
14
|
76
|
Формы контроля
Контроль знаний студентов включает формы текущего и итогового контроля. Текущий контроль осуществляется в виде контрольной работы и реферата. Итоговый контроль осуществляется в виде зачета. Итоговая оценка Оитог по 10-балльной шкале формируется как взвешенная сумма Оитог=0,2*Ок.р.+0,2*Ореф.+0,6*Озач., округленная до целого числа баллов. Ок.р., Ореф., Озач. обозначают оценки по 10-балльной шкале за контрольную работу, реферат и экзамен соответственно.
Таблица соответствия оценок по десятибалльной и системе зачет/незачет.
-
Оценка по 10-балльной шкале
|
Оценка по 5-балльной шкале
|
1
|
незачет
|
2
|
3
|
4
|
зачет
|
5
|
6
|
7
|
8
|
9
|
10
|
Таблица соответствия оценок по десятибалльной и пятибалльной системе.
По десятибалльной шкале
|
По пятибалльной системе
|
1 – неудовлетворительно
2 – очень плохо
3 – плохо
|
неудовлетворительно – 2
|
4 – удовлетворительно
5 – весьма удовлетворительно
|
удовлетворительно – 3
|
6 – хорошо
7 – очень хорошо
|
хорошо – 4
|
8 – почти отлично
9 – отлично
10 – блестяще
|
отлично - 5
|
Литература
Основная литература
Васин А.А., Краснощеков П.С., В. В. Морозов В.В. Исследование операций. М.: Изд. центр «Академия», 2008.
Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Айрис-Пресс, 2002.
Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Физматлит, 2008.
Дополнительная литература
Акоф Р., Сасиени М. Основы исследования операций. М.: Мир, 1971.
Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Дрофа, 2006.
Карманов В.Г. Математическое программирование. М.: Физматлит, 2000.
Никайдо. Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.
Рыбников К.А. Введение в комбинаторный анализ. М.: Изд. МГУ, 1985.
Шикин Е.В. Исследование операций. М., изд. «Проспект», 2006.
Содержание программы
Тема 1. Основы выпуклого анализа.
Выпуклые множества. Теорема Каратеодори. Конусы. Теоремы об отделимости выпуклых множеств. Опорные гиперплоскости. Крайние точки выпуклых множеств, теорема Минковского. Сопряженные конусы. Абстрактная лемма Фаркаша. Системы линейных однородных неравенств. Системы линейных неоднородных неравенств. Выпуклые функции, их свойства, связанные с непрерывностью и дифференцируемостью, экстремальные свойства. Задачи выпуклого программирования, принцип седловой точки, теорема Куна-Таккера. Двойственные задачи.
Литература: [1] стр.430-447; [3] стр.97-114; [6]; [7].
Тема 2. Линейное программирование.
Различные формы задачи линейного программирования. Симплекс метод.
Методы поиска базисного допустимого решения. Преодоление зацикливания. Двойственный симплекс метод. Задача с двусторонними ограничениями.
Литература: [1] стр.27-45, 48-67; [3]; [2]; [6].
Тема 3. Целочисленное программирование.
Постановка задач целочисленного программирования. Метод Гомори. Метод ветвей и границ. Задача Булева программирования.
Литература: [1] стр.93-112; [9]; [5].
Тема 4. Сетевые задачи.
Эйлеровы и гамильтоновы графы. Деревья. Минимальное порождающее дерево. Кратчайшие пути, алгоритм Флери. Потоки в сетях. Алгоритм и теорема Форда-Фалкерсона. Теорема о циркуляции. Максимальные паросочетания.
Литература: [1] стр. 134-151; [8]; [9]; [4].
Тема 5. Матричные игры.
Седловые точки и антагонистические игры. Смешанные расширения антагонистических игр, теорема фон Неймана. Методы решения матричных игр: доминирование строк и столбцов, графический метод, сведение к двойственным задачам линейного программирования.
Литература: [1]; [2] стр.204-225, 233-240.
Тема 6. Динамическое программирование.
Управляемые дискретные динамические системы. Оптимальные управления такими системами, их существование. Принцип оптимальности и уравнение Беллмана для дискретных задач оптимального управления. Примеры решения задач с экономическим содержанием методом Беллмана.
Литература: [1] стр.118-125; [3]; [2] стр.365-376; [5]; [4].
Пояснительная записка
Требования к студентам
Изучение курса «исследование операций» требует предварительных знаний линейной алгебры, математического анализа и дискретной математики в объеме, предусмотренном специальностью «прикладная математика».
Аннотация.
Предлагаемый курс имеет целью познакомить студентов с математическим аппаратом исследования операций и приложениями его в области экономики. В курсе предполагается рассмотреть следующие темы:
Основы выпуклого анализа.
Линейное программирование.
Целочисленное программирование.
Сетевые задачи.
Матричные игры.
Динамическое программирование.
Учебные задачи курса.
В результате изучения курса студенты должны:
иметь представление о математических основах исследования операций;
приобрести навыки для работы с моделями, имеющими экономическое содержание.
Типовой вариант контрольной работы
(темы 2-3,5)
1. Решить симплексным методом задачу линейного программирования.
min
 
2. Решить методом потенциалов транспортную задачу.
3. Методом Гомори решить задачу целочисленного программирования.
4. По платежной матрице.
  
построить эквивалентную этой игре пару двойственных задач линейного программирования.
Типовые варианты рефератов.
Вариант 1.
Дать подробное изложение доказательства первой и второй теорем отделимости.
Пользуясь указанной литературой, изложить доказательство теоремы Биркгофа о дважды стохастических матрицах.
Вариант 2.
Дать подробное изложение доказательства теоремы Минковского о крайних точках.
Пользуясь указанной литературой изложить доказательство теоремы Фробениуса-Кенига о диагоналях.
Типовой вариант билета для зачета.
Верно ли, что выпуклая оболочка замкнутого множества есть замкнутое множество?
Верно ли, что образ заостренного конуса при линейном отображении есть заостренный конус?
Можно ли во второй теореме отделимости условие компактности одного из множеств заменить условием его замкнутости?
Описать все опорные гиперплоскости к кубу в его вершине.
Доказать, что множество крайних точек выпуклого компакта на плоскости замкнуто.
Доказать, что выпуклая функция определенная на числовой прямой и ограниченная сверху постоянна.
Решить методом динамического программирования задачу о коммивояжере с матрицей:
  
|
