Министерство образования и науки Российской Федерации

федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования

Тобольская государственная социально - педагогическая академия им. Д.И. Менделеева

УМК дисциплины

«Теория игр и исследование операций»

Направление 010200.62 «Математика. Прикладная математика»

Степень: Бакалавр математики Программу составил Ярков В.Г., к.п.н., доцент Тобольск 2012 Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Тобольская государственная социально - педагогическая академия им. Д.И. Менделеева Программа дисциплины «Теория игр и исследование операций»

Направление 010200.62 «Математика. Прикладная математика»

Степень: Бакалавр математики Программу составил Ярков В.Г., к.п.н., доцент Тобольск Программа дисциплины “Теория игр и исследование операций” регионального компонента цикла ЕН (общих математических и естественнонаучных дисциплин) составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по направлению подготовки 010200.62 “Математика.

Прикладная математика”. Программа утверждена на заседании кафедры математического анализа (протокол № 1 от 17. 09. 2007 г.).

Организационно-методический раздел I.

1. Цель курса Целью дисциплины «Теория игр и исследование операций» является изучение теоретических основ и конкретных математических моделей прикладных производственных и экономических задач принятия решений в условиях неопределенности.

2. Задачи курса:

изучение теоретических основ применения различных методов решения задач исследования операций;

изучение методов линейного программирования как основы для построения математических моделей;

изучение основных типов задач исследования операций;

изучение способов построения математических моделей для решения прикладных задач;

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

3. Место курса в профессиональной подготовке выпускника.

Теория игр и исследование операций изучается как дисциплина регионального компонента цикла общих математических и естественнонаучных дисциплин в 8-ом семестре. Содержание дисциплины опирается на знания, полученные студентами ранее при изучении алгебры, геометрии, математического анализа, функционального анализа, компьютерных наук, методов вычислений, методов оптимизации. Также тесно связано с этим предметом математическое моделирование, изучаемое в 7-ом, 8-ом семестрах.

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

4. Требования к уровню освоения содержания курса Студент, изучивший дисциплину, должен знать:

содержание предмета, его методологию, связь с другими дисциплинами;

основные методы построения моделей прикладных задач, основные методы решения;

смысл и формулировки основных типов задач исследования операций;

формулировку основной задачи линейного программирования, ее геометрический смысл, методы решения;

разные формулировки транспортной задачи;

различные подходы к построению моделей теории игр и статистических должен уметь:

определить тип задачи, подобрать соответствующие методы ее решения;

построить математическую модель задачи, решить ее, интерпретировать ответ;

решать задачу линейного программирования графическим методом и симплексметодом;

решать транспортную задачу табличным и сетевым методами;

решать задачи теории игр различными методами;

должен владеть:

навыками работы со специальной литературой;

навыками математического программирования;

вычислительными навыками.

II. Содержание курса 1. Разделы курса 1. Предмет исследования операций и теории игр.

2. Задачи линейного программирования. Симплекс-метод. Теоремы двойственности.

3. Транспортные задачи. Сетевое планирование.

4. Модели принятия решения в конфликтных ситуациях.

5. Игры с нестрогим соперничеством.

6. Элементы теории статистических решений.

2. Темы и краткое содержание 1. Предмет исследования операций и теории игр. Основные понятия исследования операций. Основные типы задач. Прямые и обратные задачи. Однокритериальные и многокритериальные задачи. Обзор методов решения.

2. Задачи линейного программирования. Симплекс-метод. Теоремы двойственности.

Основная задача линейного программирования, ее геометрическая интерпретация.

Жордановы исключения. Симплекс-метод. Двойственные задачи линейного программирования.

3. Транспортные задачи. Сетевое планирование. Постановка транспортной задачи (ТЗ).

ТЗ по критерию стоимости. Методы поиска опорного и оптимального планов (метод наименьшей стоимости, метод потенциалов и др.) ТЗ с неправильным балансом. ТЗ с дополнительными ограничениями. Решение ТЗ на сети.

4. Модели принятия решения в конфликтных ситуациях. Игра как математическая модель конфликта. Основные понятия теории игр. Понятие оптимальности в теории игр.

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

5. Игры с нестрогим соперничеством. Понятие игры нескольких лиц. Кооперативные игры. Ядро игры нескольких лиц. Множество Парето. Арбитражная схема Нэша.

6. Элементы теории статистических решений. Модели принятия решений в условиях действия неопределенных факторов стохастической природы. Понятие игры с природой.

Критерии выбора решения.

самостоятельной работы Основные типы задач исследования операций.

Формулировка прямой и обратной задач исследования операций в детерминированном и стохастическом случаях.

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

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

Жордановы исключения. Симплекс-метод.

Двойственность линейного программирования.

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

Транспортная задача с неправильным балансом.

Транспортная задача с дополнительными ограничениями.

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

4. Примерная тематика рефератов и курсовых работ 1. Предмет и задачи исследования операций и теории игр.

2. Основная задача линейного программирования.

3. Симплекс-метод.

4. Теория двойственности линейного программирования.

5. Транспортные задачи.

6. Оптимизация на сетях.

7. Антагонистические матричные игры.

8. Игры с нестрогим соперничеством. Кооперативные игры.

9. Ядро игры нескольких лиц. Арбитражная схема Нэша.

10. Игры с природой.

5. Примерный перечень вопросов к зачету 1. Предмет и задачи исследования операций и теории игр.

2. Основные понятия и методы исследования операций. Основные типы задач.

3. Прямые и обратные задачи исследования операций.

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

5. Основная задача линейного программирования, ее геометрический смысл.

6. Жордановы исключения. Симплекс-метод.

7. Двойственные задачи линейного программирования.

8. Транспортные задачи по критерию стоимости.

9. Транспортная задача с дополнительными ограничениями.

10. Задачи сетевого планирования.

11. Модели принятия решения в конфликтных ситуациях. Игра как математическая модель конфликта. Основные понятия теории игр.

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

13. Геометрическое решение матричной игры.

14. Игры с нестрогим соперничеством.

15. Понятие игры нескольких лиц. Кооперативные игры.

16. Ядро игры нескольких лиц.

17. Арбитражная схема Нэша.

18. Элементы теории статистических решений. Игры с природой.

Распределение часов курса по темам и видам работ теории игр.

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

планирование.

конфликтных ситуациях.

соперничеством.

решений.

IV. Форма итогового контроля Теория игр и исследование операций изучается как дисциплина регионального компонента цикла общих математических и естественнонаучных дисциплин в 8-ом семестре. Согласно учебному плану общий объем часов по дисциплине составляет часов, из них 42 часа – аудиторные (лекции – 28 часов, практические занятия – 14 часов), 36 часов – самостоятельная работа. Итоговый контроль по дисциплине – зачет в 8-ом семестре.

V. Учебно-методическое обеспечение курса 1. Рекомендуемая литература (основная) Благодатских В.И. Введение в оптимальное управление (линейная теория): Учебник/ Под ред. В.А. Садовничего. – М.: Высшая школа, 2001.

Васильев Ф.П. Методы оптимизации. - М.: Факториал Пресс, 2002.

Косоруков О.А., Мищенко А.В. Исследование операций. – М.: Издательство «Экзамен», 2003.

Лагоша Б.А. Оптимальное управление в экономике: Учебное пособие. -- М.: Финансы и статистика, 2003. -- 192 с.

Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах. -- М.: Логос, 2003. -- 392 с.

Шикин Е.В., Чхартишвили А.Г. Математические модели и методы в управлении:

Учебное пособие для вузов. -- М.: Дело, 2002. -- 440 с.

Экономико-математические методы и прикладные модели: Учеб. пособие для вузов\ В.В.Федосеев и др. – М.: ЮНИТИ, 2002. – 391 с.

2. Рекомендуемая литература (дополнительная) Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. - М.:

Наука, 1991.

Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. - М.: Факториал, 1998.

Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, Карманов В.Г. Математическое программирование. – М.: Наука, 1975. – 272 с.

Костевич Л.С., Лапко А.А. Теория игр. Исследование операций. – Минск: Выш. школа, 3. Перечень обучающих, контролирующих компьютерных программ Среды программирования Delphi, Vbasic; математические пакеты MathCad, Mathematica; табличный процессор Microsoft Excel.

Тема: «Линейное программирование. Симплекс-метод. Двойственные задачи».

Цель: Изучение методов линейного программирования. Решение задачи линейного программирования и двойственной ей задачи. Экономическая интерпретация основной и двойственной задачи.

Дана матрица технологических коэффициентов аij, которые показывают, сколько единиц i-го вида сырья требуется для производства одной единицы j-го вида продукта.

Запасы сырья bi. Прибыль от реализации j-го продукта составляет c j.

Требуется:

1) составить математическую модель задачи; пояснить экономический смысл основных и дополнительных переменных;

2) найти опорный план выпуска продукции симплекс-методом;

3) найти оптимальный план выпуска продукции симплекс-методом; указать максимально возможную суммарную прибыль;

4) определить количество неизрасходованного сырья при найденном оптимальном 5) составить двойственную задачу, пояснить ее экономический смысл; решить двойственную задачу;

6) выяснить, выгоден ли выпуск новой продукции, если затраты i-го вида сырья на новый вид продукции составляет d i единиц.

Тема: «Динамическое программирование. Двухэтапный метод».

Цель: Изучение методов решения многоэтапных задач динамического программирования, когда экономические условия производства меняются с течением времени.

Дана матрица технологических коэффициентов аij, которые показывают, сколько единиц i-го вида сырья требуется для производства одной единицы j-го вида продукта.

Запасы сырья bi. Прибыль от реализации j-го продукта составляет c j.

Первый этап состоит в производстве продукции. На втором этапе предприятие вкладывает часть полученной прибыли (но не более 10%) чтобы арендовать контейнеры для перевозки топлива, горючего и.т.п. Цель второго этапа максимизировать объем грузоперевозок. Возможна аренда 8-тонных контейнеров по цене 2 тыс. руб. за контейнер и 10-тонных контейнеров по цене 3 тыс. руб. за контейнер. Всего в наличии у фирмы арендодателя имеется a штук 8-тонных контейнеров и b штук 10-тонных контейнеров.

вар.

Требуется:

1) Составить математическую модель двухэтапной задачи;

2) Найти решение симплекс-методом на втором этапе;

3) Указать количество арендованных контейнеров каждого вида, указать максимальный объем грузоперевозок;

4) Указать окончательную сумму прибыли предприятия.

Тема: «Сетевое планирование».

Цель: Изучение методов решения транспортных задач, условия которых представлены таблицей или на сети.

Условие задачи изображено в виде неориентированного связного графа. На ребрах поставлены значения тарифов, в вершинах - значения запасов (+) или потребностей (-).

Требуется:

1) построить допустимый план перевозок; проверить его на оптимальность;

2) методом потенциалов и оценок найти оптимальный план задачи о минимизации суммарной стоимости перевозок;

3) преобразовать задачу к табличному виду, решить ее табличным методом потенциалов.

Вариант Вариант Вариант Вариант ариант Вариант Вариант Тема: «Элементы теории массового обслуживания»

2. Одноканальная СМО с ограниченным временем ожидания (модель М/М/1/k) 3. Многоканальная замкнутая СМО (модель М/М/m/k/l, k+m>l) 4. Преобразование Лапласа времени реакции G*(s) в системе M/G/1.

5. Модель выбора перспективной дисциплины обслуживания ( метод цепей Маркова ).

6. Разложение времени задержки сообщения по отдельным каналам.

7. Вычислительная система обслуживает поток задач, запросы на выполнение которых поступают в случайные моменты времени ( a запросов за 10 мин.). На решение одной задачи необходимо в среднем 1 мин. Сравнить характеристики вычислительной системы для моделей M/M/1/k (k=2,4,6), M/M/m (m=1,2,4) и M/M/1//l (l=2,4,6) (вариант a 16 16 8). Проектируется система обработки информации, описываемая моделью M/D/1. Интенсивность входного потока задач - 1 тр./мин. Цена потерь в результате пребывания требования в системе - a. Расходы, необходимые для создания и эксплуатации обслуживающих мощностей - L(2) = b*m. Определить интенсивность обслуживания ( m ), при которых суммарные потери будут наименьшими. (вариант a b 16 8 1) 9. Проектируется система обработки информации, описываемая моделью M/M/m.

Запросы на выполнение задач поступают в случайные моменты времени ( a запросов за t мин.). На решение одной задачи необходимо в среднем 1 мин. Определить число обслуживающих устройств, минимизирующих суммарные потери, если цена потерь в результате пребывания требования в системе - C(n). Простой обслуживающих мощностей характеризуется ценой C(m). (вариант a t C(n) C(m) 16 40 20 6.0 3.0) 10.Определить среднее время задержки требования в каждом узле сети, если известен внешний пуассоновский источник требований g1,g2,g3 и матрица переходных вероятностей:

Поток обслуживания считать детерминированным. В каждом узле находится один обслуживающий прибор, с интенсивностью обслуживания m треб/сек.

11. Определить среднюю задержку сообщения в сети, если заданы внешний трафик G(i,j) и пропускная способность каналов C (i,j) :

Задержкой сообщения в узле пренебречь. Средняя длина сообщения m.

12. Распределить суммарную канальную емкость ( С = 20 ) сети так, чтобы средняя задержка сообщения была бы наименьшей, если заданы :

внешний трафик | 0 g12 g13 | топология сети | 0 s12 s13 | Задержкой сообщения в узле пренебречь. Средняя длина сообщения m.

вариант g12 g13 g21 g23 g31 g32 s12 s13 s21 s23 s31 s32 m Тема: «Задача целочисленного программирования. Метод Гомори».

Цель: Изучение методов решения задач линейного программирования с учетом целочисленности их решения.

Дана матрица технологических коэффициентов аij, которые показывают, сколько единиц i-го вида сырья требуется для производства одной единицы j-го вида продукта.

Запасы сырья bi. Прибыль от реализации j-го продукта составляет c j.

Требуется:

1) составить математическую модель задачи;

2) найти опорный план выпуска продукции;

3) найти оптимальный план выпуска продукции симплекс-методом без учета целочисленности;

4) найти целочисленный оптимальный план методом Гомори.

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

1. Фирма может за небольшую плату (100 руб.) составить любому студенту программу для каких-то типовых расчетов на ПЭВМ. Каждый сотрудник фирмы может качественно выполнить до 10 заказов. Cтоимость аренды машинного времени составляет 800 руб. в месяц (этого времени достаточно для выполнения 10 работ). Количество студентов, пользующихся услугами фирмы, не превышает 100 человек в месяц.

Определить число сотрудников фирмы, дающее максимум общего дохода (для регистрации фирмы необходима численность не менее двух человек).

2. Землевладелец на знойном юге решает вопрос о числе рабочих, привлекаемых к уборке томатов. Урожайность колеблется в зависимости от погоды от 500 до центнеров, закупочная цена стабильна и равна 5 руб/кг. Рабочий за сезон собирает центнеров, получая 1.2 руб/кг за уборку и 280 руб. для оплаты стоимости проезда к месту работ. Затраты на обеспечение рабочих жильем (речь не идет даже о трехзвездочной гостинице) составляют 300 руб. и не зависят от численности.

3. В сельхозрайоне с посевной площадью 1430 га решено построить элеватор по одному из типовых проектов на 20, 30, 40, 50 или 60 тыс. центнеров зерна. Привязка проекта обойдется в 37 тыс.руб. Cтоимость материалов и оборудования для элеватора мощности 20 тыс. равна 60 тыс.руб. и растет на 10% с ростом мощности на 10 тыс.

Затраты на эксплуатацию элеватора на 20 тыс. равны 10 тыс. руб. и растут на 10 тыс. c ростом мощности на 10 тыс. За хранение зерна на счет элеватора вносится плата 10 руб. за центнер. Урожайность колеблется от 14 до 20 ц/га.

4. Председатель сельхозкооператива решает закупить бочки для засолки огурцов.

Виды на урожай колеблются от 700 до 1000 кг, в бочку вмещается 50 кг, цена бочки - руб., затраты на засолку - 20 руб. за бочку, аренда места на рынке - 50 руб, реализационная цена - 7.20 руб/кг.

5. Универмаг, работающий по 10 часов в сутки, ежедневно посещают от 7 до тыс. чел. Cтоимость покупок одного посетителя в среднем - 50 руб. Время обслуживания мин. на покупателя. Затраты на оборудование одного рабочего места - 2400 руб., зарплата продавца - 1400 руб. в месяц. Найти число рабочих мест при планировании работы на год (300 рабочих дней), если покупатель не намерен стоять в очереди из более чел.

6. Фирма, действующая в живописном Горном Алтае, планирует десятидневные маршруты для туристов в летнем сезоне (60 дней). Известно, что число туристов в течение десятидневки колеблется от 1 до 1.5 тыс. чел. Группы комплектуются из 25 чел.

Стоимость путевки – 2 тыс.руб. Заработная плата инструктора составляет 6 тыс.руб. в месяц. На экипировку группы затрачивается 1.5 тыс.руб., на питание группы – 12 тыс.руб.

К тому же приходится оплачивать ремонт помещений и снаряжения при подготовке к сезону 30 тыс.руб. Сколько же инструкторов разумно пригласить на работу ?

7. В транспортном цехе ежедневно выходит из строя до 8 агрегатов, каждый из которых мог бы дать продукции на 350 руб. Слесарь-ремонтник, получающий 2500 руб. в месяц, не может в день обслужить более двух станков. Сколько же слесарей должен привлечь на работу начальник транспортного цеха ?

8. В городе N решено открыть яхт-клуб (под громким названием скрывается скромная лодочная станция). Предполагаемое число членов клуба колеблется от 100 до 250 чел. Годовой абонемент стоит 1000 руб. Аренда причала, помещений для хранения яхт и стимулирование ускоренного получения лицензии обойдутся в 20 тыс.руб.

Владельцу абонемента, не получившему яхты, выплачивается неустойка в двойном размере. Сколько же прогулочных яхт следует заказать, если каждая из них стоит тыс.руб. и обычно ежедневно приходит каждый десятый любитель пребывания на воде (прочими затратами пренебречь) ?

9. Организуются пригородные автобусные рейсы. Число пассажиров колеблется от 300 до 450 чел., из которых 10% имеют право бесплатного проезда. Цена билета 6 руб.

Вместимость автобуса – 30 чел. Эксплуатационные затраты на один рейс – 50 руб. Оплата шофера за одну поездку - 60 руб. Сколько же организовать рейсов ?

10. В райцентре решается вопрос о строительстве сыроваренного завода. Известно, что дневной объем поставок молока колеблется от 4800 до 5600 л в день. Один сепаратор ежедневно перерабатывает 600 л молока в 50 кг сыра. Стоимость аппарата 40000 руб, ежемесячные эксплуатационные расходы –1500 руб, аренда помещения – 12000 руб. в год.

Молоко закупается по 3 руб/л, сыр продается по 45 руб/кг. Неиспользованное молоко приходится вывозить на свинокомплекс молоковозами (вместимость 5 т) с затратами руб. за рейс. Сколько же сепараторов закупать ?

11. Прядильная фабрика ежемесячно получает от 35 до 50 т хлопка повышенной влажности. Один сушильный агрегат может высушить 5 т. Затраты на техническое обслуживание агрегата 1000 руб. (независимо от его использования или простоя). Потери от 1 т невысушенного хлопка - 7000 руб. Сколько агрегатов разумно иметь на фабрике ?

12.В 50-е годы в одном из небольших городов области планировалось строительство кинотеатра. Имелись проекты на 400, 500, 600 и 750 мест. Затраты на содержание кинотеатра составляли 40 руб. в день и дополнительно 10 руб. за каждые сто мест (свыше 600). В день можно было дать 6 сеансов, стоимость билета составляла в среднем 40 коп. Количество посетителей колебалось от 2000 до 3000 чел. Какой из проектов следовало выбрать?

13. Требуется выяснить потребности транспортного агентства в автобусах для экскурсионного обслуживания. Обычно число заявок на автобусы колеблется в пределах от 10 до 50. Затраты на эксплуатацию каждого автобуса составляют 10 денежных единиц плюс 100 на содержание авто-парка в целом в день. Экскурсионное бюро выплачивает транспортному агентству 20 денежных единиц за каждую заявку.

14. Бюро трудоустройства населения планирует открытие курсов компьютерной грамотности. Ожидаемая численность слушателей в пределах от 100 до 200 чел. За каждого их них бюро получает от работодателя 1000 руб. Преподаватель работает с группой, не превышающей 10 чел. Расходы на хозяйственные нужды составляют 5000 и на оплату преподавателя 4500 руб. Сколько преподавателей разумно привлечь?

15. В условиях задачи 14 по некоторым мотивам было решено увеличить оплату преподавателя до 6500 руб. Сколько преподавателей приглашать в этом случае?

Решить матричную игру. Указать оптимальные стратегии обоих игроков.

Вариант «Решение транспортных задач в MS Excel 2010»

Для решения оптимизационных задач в программе MS Excel используется встроенное приложение «Поиск решений». Если на вкладке «Данные»

отсутствует кнопка «Поиск решения», то данное приложение необходимо установить:

1. Перейти во вкладку «Файл»

2. В меню выбрать пункт «Параметры»

3. В окне «Параметры Excel» выбрать пункт «Надстройка»

4. Среди надстроек выбрать «Поиск решения», внизу окна нажать кнопку 5. В окне «Надстройки» поставить галочку в строке «Поиск решения», 1. На рабочий Лист занести исходные данные (рис. 1) 2. Ниже, на рабочем листе набрать таблицу для решения (рис. 2) 3. Проверить, является ли задача закрытой (сумма мощностей поставщиков = сумме мощностей потребителей): суммы данных в ячейке G14 по строке и по столбцу совпадают (рис. 3) 4. В ячейки H10:H13, B15:F15 внести формулы системы ограничений (рис. 4, 5) Рис. 5. В ячейки H15 внести целевую функцию (рис. 6, 7) 6. Перейти во вкладку «Данные», нажать кнопку «Поиск решения»

7. В окне «Параметры поиска решения» указать (рис. 8):

Адрес целевой ячейки (адрес ячейки, куда внесена целевая Тип функции (минимум);

В строке «Изменяя ячейки переменных» указать диапазон требуемых ячеек (B10:F13);

В окне «В соответствии с ограничениями» указать систему ограничений данной задачи:

а) Нажать кнопку «Добавить»

б) В окне «Добавление ограничения» указать ячейку с левой частью ограничения из системы ограничения, знак отношения, ссылку на ячейку, где находится правая часть ограничения (Рис.

в)Для ввода следующего ограничения нажать кнопку «Добавить»

8. Нажать кнопку «Найти решение» (рис. 10) Рис. 8.

Рис. 10.