Методические рекомендации по курсу

Методические рекомендации по курсу

ДДС. Ф.09 ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Основная образовательная программа подготовки специалиста по специальности

050201.65 «Информатика с дополнительной специальностью математика»

Автор: , ст. преподаватель кафедры М и ММЭ

1. Цели и задачи курса.

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

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

В результате изучения курса студенты

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

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

2. Структура курса.

Линейное программирование. Следствия систем линейных неравенств. Теорема Минковского. Критерий несовместности систем линейных неравенств. Неотрицательные решения систем линейных уравнений и систем линейных неравенств. Классификация задач линейного программирования. Взаимная двойственность задач С и С*, К и К*. Допустимые и оптимальные решения задач линейного программирования. Критерий оптимальности векторов. Теорема двойственности. Теорема равновесия для стандартных и канонических задач линейного программирования.

Векторно-параметрическое уравнение отрезка. Теоремы о выпуклых множествах. Геометрическая интерпретация задач линейного программирования и графический метод решения.

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

Транспортная задача линейного программирования на минимум. Основные теоремы. Методы построения опорного решения транспортной задачи на минимум. Метод потенциалов решения транспортной задачи линейного программирования на минимум и его обоснование. Решение транспортных задач на минимум с ограничениями пропускной способности. Критерий оптимальности решения транспортной задачи на максимум. Задачи транспортного типа.

Динамическое программирование. Задача динамического программирования в общем виде. Принцип оптимальности Беллмана. Алгоритм решения задач динамического программирования. Рекуррентные соотношения для решения задач динамического программирования с аддитивным показателем эффективности.

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

Сетевое планирование. Постановка задачи сетевого планирования. Основные понятия. Характеристики сетевой модели и методы их расчета. Оптимизация сетевых моделей.

3. Содержание дисциплины.

Разделы дисциплины и виды занятий (в часах). Примерное распределение учебного времени:

№ п/п	Наименование раздела, темы	Количество часов
Всего аудит.	ЛК	ПР	Сам. раб.
1	Линейное программирование	36	18	18	30
2	Динамическое программирование	8	4	4	10
3	Сетевое планирование	4	2	2	5
4	Решение задач с помощью компьютера	6	–	6	11

4. Учебно-методическое обеспечение и информационное обеспечение дисциплины

Литература

Основная литература

1. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1987.

2. Арис Р. Дискретное динамическое программирование. – М.: Наука, 1981.

3. Афанасьев М. Ю, Багриновский К. А., Матюшок В. М. Прикладные задачи исследования операций: Учеб. пособие. – М.: ИНФРА-М, 2006.

4. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989.

5. Беллман Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

6. Вентцель Е. С. Исследование операций: задачи, принципы, методология. – М.: Наука, 1988.

7. Габасов Р. Ф., Кириллова Ф. М. Основы динамического программирования. – Минск: Изд-во БГУ, 1975.

8. Долженков В. А., Коретников Ю. В. Microsoft Excel 2002. – CПб.: БХВ-Петербург, 2002.

9. Калихман И. Л. Сборник задач по линейной алгебре и программированию. – Минск: Высшэйшая школа, 1969.

10. Кремер Н. Ш., Тришин И. М., Фридман М. Н. Исследование операций в экономике: Учеб. пособие для вузов.– М.: Банки и биржи, ЮНИТИ, 1997.

11. Кузнецов А. В. и др. Руководство к решению задач по математическому программированию. – Минск: Высшэйшая школа, 2001

12. Кузнецов А. В., Холод Н. И. Математическое программирование. – Минск: «Высшэйшая школа», 2001.

13. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979.

14. Нестеров Е. П. Транспортная задача линейного программирования. М.: Транспорт, 1971.

15. Орлова И. В. Экономико-математическое моделирование: практическое пособие по решению задач. – М.: Вузовский учебник, 2007.

16. Полунин И. Ф. Курс математического программирования. – Минск: «Высшэйшая школа», 1969

17. Сборник задач по высшей математике для экономистов. – М.: ИНФРА-М, 2002.

18. Сдвижков О. А. Математика в Excel 2002. – М.: СОЛОН-Пресс, 2004.

Дополнительная литература

1. Абчук В. А. Экономико-математические методы. – СПб: Союз, 1999.

2.  А. Линейное программирование. – М.: 1981.

3. Волков И. К., Загоруйко Е. А. Исследование операций. – М.: МГТУ им. Баумана, 2002.

4. Гермейер Ю. Б. Введение в теорию исследования операций. – М.: Наука, 1971.

5. Данциг Дж. Б. Линейное программирование, его применения и обобщения. – М.: «Прогресс», 1966.

6. Ермолаев Ю. М., Ляшко И. И., Михалевич В. С., Тюптя В. И. Математические методы исследования операций. – М.: Киев, «Вища Школа», 1979.

7. Морозов В. В., Сухарев А. Г., Федоров В. В. Исследование операций в задачах и упражнениях. – М.: 1986.

8. Экономико-математические методы и прикладные модели. – М.: ЮНИТИ, 2001.

Электронные образовательные ресурсы (ЭОР)

1. http://eqworld. *****/ru/library. htm — Электронная библиотека сайта EqWorld.

2. http://www. *****

3. http://dictionary. *****

5. Примерные вопросы к зачету(экзамену)

  1.  Следствия систем линейных неравенств. Леммы 1 и 2.

  2.  Теорема Минковского.

  3.  Критерий несовместности систем линейных неравенств. Теорема 1.

  4.  Критерий несовместности систем линейных неравенств. Теоремы 2 и 3.

  5.  Неотрицательные решения систем линейных уравнений и систем линейных неравенств.

  6.  Классификация задач линейного программирования. Взаимная двойственность задач С и С*, К и К*.

  7.  Допустимые и оптимальные решения задач линейного программирования. Критерий оптимальности векторов. Теорема двойственности. 

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

  9.  Векторно-параметрическое уравнение отрезка. Теоремы о выпуклых множествах.

  10.  Графический метод решения задач линейного программирования. Теоремы 1 и 2.

  11.  Симплекс-метод решения задач линейного программирования. Леммы 1 и 3.

  12.  Симплекс-метод решения задач линейного программирования. Леммы 2 и 4.

  13.  Симплекс-метод решения задач линейного программирования. Лемма 5. Алгоритм симплекс-метода

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

  15.  Методы построения опорного решения транспортной задачи на минимум.

  16.  Метод потенциалов решения транспортной задачи линейного программирования на минимум и его обоснование.

  17.  Решение транспортных задач на минимум с ограничениями пропускной способности.

  18.  Пример задачи транспортного типа на максимум. Критерий оптимальности решения транспортной задачи на максимум.

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

  20.  Задача динамического программирования в общем виде. Принцип оптимальности Беллмана. Алгоритм решения задач динамического программирования. Рекуррентные соотношения для решения задач динамического программирования с аддитивным показателем эффективности.

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

  22.  Решение задачи «о рюкзаке» методом динамического программирования – вывод рекуррентных соотношений.

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

  24.  Решение задачи о замене оборудования методом динамического программирования – вывод рекуррентных соотношений.

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

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

  27.  Постановка задачи сетевого планирования. Построение сетевой модели. Вычисление ранних сроков начала, поздних сроков свершения и резервов времени событий.

  28.  Ранний и поздний сроки начала и окончания работ, полный и свободный резервы времени и их вычисление.

6. Примерная тематика практических занятий.

Практические занятия по теме «Линейное программирование»

Составление математических моделей задач линейного программирования. Рассматриваются следующие задачи: об использовании сырья, об использовании оборудования, общая задача об использовании ресурсов, задача о диете, задача о раскройке материалов, задача о закреплении транспорта за авиалиниями, задача о посеве культур, о распределении работ между исполнителями. Задачи даются не в общем виде, а с конкретными числовыми данными, что способствует большему пониманию условия задач, позволяет упростить процесс их обсуждения. С целью развития способностей самостоятельно составлять математические модели от студентов требуется четко придерживаться следующих этапов:

анализ условия задачи (он может сопровождаться схемами, рисунками, таблицами);

выделения параметров, которые требуется найти и введение соответствующих переменных;

выявление условий, которые носят характер ограничений и составление соответствующих линейных ограничений;

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

математическая формулировка задачи.

В качестве домашнего задания каждому студенту требуется составить математическую модель своей (по номеру из задачника) задачи линейного программирования; сформулировать ее в общем виде и привести соответствующую математическую модель.

Графический способ решения задач линейного программирования. Здесь рассматриваются три типа задач линейного программирования, которые можно решить графическим способом:

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

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

задачи с произвольным числом переменных и ограничений, но для которых выполняется следующее условие: общее число переменных – ранг основной матрицы подсистемы, составленной из ограничений типа уравнений,  2 (в этом случае задача сводится к задаче с двумя переменными методом исключения неизвестных).

В качестве домашнего задания требуется решить графическим способом по одной задаче каждого типа.

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

Домашнее задание: решить симплекс-методом задачу линейного программирования с конкретным экономическим содержанием и найти оптимальное решение двойственной к ней задачи.

Транспортная задача линейного программирования. Решение транспортных сбалансированных и несбалансированных задач линейного программирования на минимум и на максимум; транспортных задач с ограничениями пропускной способности; задач транспортного типа (распределительные и классическая задача о назначениях). При построении опорного решения первых трех задач используются различные методы построения опорного решения. Далее метод построения опорного решения предлагается выбирать студентами самостоятельно (рекомендуется использовать метод аппроксимаций Фогеля).

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

Практические занятия по теме «Динамическое программирование»

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

Домашнее задание: решить задачу динамического программирования с конкретными числовыми данными. Группа делится на количество подгрупп, соответствующих количеству типов задач, рассмотренных в лекциях и на практических занятиях. Каждой подгруппе достается своя задача одного из этих типов.

Вопросы для коллективного обсуждения – соответствующие вопросы из примерных зачетных тестовых заданий

Практические занятия по теме «Сетевое планирование»

Построение сетевых моделей проектов. Расчет их характеристик.

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

Вопросы для коллективного обсуждения – соответствующие вопросы из примерных зачетных тестовых заданий.

Практические занятия по теме «Решение задач с помощью компьютера»

Решение задач исследования операций в электронных таблицах Microsoft Excel; подробный анализ полученного решения.