9758
.pdfМинистерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
«Нижегородский государственный архитектурно-строительный университет»
Прокопенко Н.Ю.
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Учебно-методическое пособие по подготовке к лекциям, практическим занятиям
(включая рекомендации по организации самостоятельной работы и выполнению курсовых работ)
для обучающихся по дисциплине «Исследование операций» по направлению подготовки 09.03.03 Прикладная информатика профиль Прикладная информатика в экономике
Нижний Новгород
2016
УДК 004.9
Прокопенко Н.Ю. / Исследование операций [Электронный ресурс]: учеб.- метод. пос. / Н.Ю. Прокопенко; Нижегор. гос. архитектур. - строит. ун-т – Н. Новгород: ННГАСУ, 2016. – 205 с.– 1 электрон. опт. диск (CD-RW).
В настоящем учебно-методическом пособии по дисциплине «Исследование операций» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебно-методического пособия – это помощь в усвоении лекций и в подготовке к практическим занятиям, а также в написании курсовой работы.
Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Исследование операций» по направлению подготовки 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике.
Учебно-методическое пособие ориентировано на обучение в соответствии с календарным учебным графиком и учебным планом по основной профессиональной образовательной программе направления 09.03.03 Прикладная информатика, профиль Прикладная информатика в экономике, утверждённым решением учёного совета ННГАСУ от 02.09.2016 г. (протокол № 1).
© Н.Ю. Прокопенко, 2016 © ННГАСУ, 2016
2
Оглавление
1.Общие положения………………………………………………………………...4
1.1Цели изучения дисциплины и результаты обучения………………………4
1.2Содержание дисциплины…………………………………………………….5
1.3Порядок освоения материала………………………………………………...6
2.Методические указания по подготовке к лекциям……………………………..6
2.1Общие рекомендации по работе на лекциях………………………………..6
2.2Общие рекомендации при работе с конспектом лекций…………………...7
2.3Краткое содержание лекций………………………………………………….8
2.3.1.Раздел 1. Задачи линейного программирования и методы решения...….8
2.3.2.Раздел 2. Элементы теории матричных игр…………………….………..54
2.3.3.Раздел 3. Принятие решений в условиях неопределённости и риска….83
2.3.4.Раздел 4. Многошаговые модели принятия решений и динамическое про-
граммирование……………………………………………………………………95
2.4Контрольные вопросы……………………………………………………….110
3.Методические указания по подготовке к практическим занятиям…………...112
3.1Общие рекомендации по подготовке к практическим занятиям………….112
3.2Примеры задач для практических занятий…………………………...…….113
3.2.1. Раздел 1. Задачи линейного программирования и методы решения...…113
3.2.2.Раздел 2. Элементы теории матричных игр…………………….………..143
3.2.3.Раздел 3. Принятие решений в условиях неопределённости и риска…..151 3.2.4. Раздел 4. Многошаговые модели принятия решений и динамическое про-
граммирование……………………………………………………………………164
4.Методические указания по организации самостоятельной работы……….......171
4.1Общие рекомендации для самостоятельной работы……………………….171
4.2Темы для самостоятельного изучения………………………………………174
4.3.Учебно-методическое обеспечение самостоятельной работы……………179
4.4Задания для самостоятельной работы……………………………………….180
5.Методические рекомендации по подготовке курсовой работы……………….196
3
1. Общие положения
1.1 Цели изучения дисциплины и результаты обучения
Основными целями освоения учебной дисциплины «Исследование опера-
ций» являются: формирование систематических знаний в области исследования операций, изучение математических методов и базовых алгоритмов оптимизации,
используемых при моделировании и проектировании сложных систем, в том чис-
ле изучение линейного, динамического программирования, методов нелинейной оптимизации, методов теории игр, получение навыков их практической реализа-
ции на компьютере.
В процессе освоения дисциплины студент должен Знать:
основные понятия и разделы исследования операций; типовые модели ис-
следования операций (многошаговые модели, линейные оптимизационные модели, элементы теории матричных игр, сетевые модели календарного планирования, модели маршрутизации, модели размещения и др.); описание основных комбинаторных конфигураций; основные свойства комбинатор-
ных объектов и чисел, методы их изучения (теоретико-множественный, ал-
гебраический, метод рекуррентных соотношений);
типовые методы оптимизации, используемые при изучении моделей иссле-
дования операций;
примеры эффективно разрешимых подклассов задач исследования опера-
ций с априорно доказуемыми оценками качества.
Уметь:
формализовать типовые модели исследования операций в виде задач мате-
матического программирования;
решать задачи ЛП симплекс-методом, строить модели двойственных задач ЛП и решать их на основе теорем двойственности;
решать транспортные задачи распределительным методом и методом по-
тенциалов;
4
решать задачи многошаговой оптимизации методом динамического про-
граммирования;
находить решение матричной игры с седловой точкой и без нее.
Владеть:
основными приемами и методами решения задач математического про-
граммирования;
основными приемами и методами решения матричных игр;
навыками решения задач теории систем массового обслуживания и теории принятия решений.
1.2Содержание дисциплины
Материал дисциплины сгруппирован по следующим разделам:
1. Задачи линейного программирования и методы решения.
Математическая постановка задачи ЛП. Методы решения задач линейного программирования (графический, алгебраическое решение cимплекс-методом,
решение симплекс-таблицами, технология решения в Excel).
Основные теоремы теории двойственности. Экономическая интерпретация двойственных переменных и теорем двойственности.
Методы решения задач целочисленного программирования (метод Гомори;
метод ветвей и границ).
Модели транспортного типа. Сведение открытой модели к закрытой. Специ-
альные методы решения транспортных задач.
2. Элементы теории матричных игр.
Основные понятия теории игр. Нижняя и верхняя цена игры. Принципы «ми-
нимакса». Чистые и смешанные стратегии. Решение игры в смешанных стратеги-
ях. Основная теорема матричных игр. Методы решения конечных игр: графиче-
ский и симплекс-метод. Приведение матричной игры к задаче линейного про-
граммирования.
3. Принятие решений в условиях неопределенности и риска.
5
Критерии максимина, Сэвиджа, Вальда, Гурвица, Лапласа. Дерево решений.
Критерий максимизации ожидаемых доходов. Ожидаемая стоимостная оценка наилучшего решения.
4. Многошаговые модели принятия решений и динамическое программиро-
вание.
Принцип оптимальности и уравнения Беллмана.
Задачи динамического программирования:
1) задача об оптимальном использовании ресурсов (инвестиций) при произ-
водственном планировании; 2) задача о загрузке транспортного средства; 3) зада-
ча о замене оборудования.
1.3 Порядок освоения материала
Материал дисциплины изучается в соответствии с порядком, определённым в следующей таблице:
Таблица 1
Порядок освоения дисциплины
№ |
Раздел дисциплины |
№№ предшествую- |
|
|
щих разделов |
|
|
|
1 |
Задачи линейного программирования и методы ре- |
- |
|
шения |
|
|
|
|
2 |
Элементы теории матричных игр |
1 |
|
|
|
3 |
Принятие решений в условиях неопределенности и |
1,2 |
|
риска |
|
|
|
|
4 |
Многошаговые модели принятия решений и дина- |
1,2,3 |
|
мическое программирование |
|
|
|
|
2. Методические указания по подготовке к лекциям
2.1 Общие рекомендации по работе на лекциях
Лекция является главным звеном дидактического цикла обучения. Ее цель – формирование основы для последующего усвоения учебного материала. В ходе
6
лекции преподаватель в устной форме, а также с помощью презентаций передает обучаемым знания по основным, фундаментальным вопросам изучаемой дисци-
плины.
Назначение лекции состоит в том, чтобы доходчиво изложить основные по-
ложения изучаемой дисциплины, ориентировать на наиболее важные вопросы учебной дисциплины и оказать помощь в овладении необходимых знаний и при-
менения их на практике.
Личное общение на лекции преподавателя со студентами предоставляет большие возможности для реализации образовательных и воспитательных целей.
При подготовке к лекционным занятиям студенты должны ознакомиться с презентаций, предлагаемой преподавателем, отметить непонятные термины и по-
ложения, подготовить вопросы с целью уточнения правильности понимания. Ре-
комендуется приходить на лекцию подготовленным, так как в этом случае лекция может быть проведена в интерактивном режиме, что способствует повышению эффективности лекционных занятий.
2.2Общие рекомендации при работе с конспектом лекций
Входе лекционных занятий необходимо вести конспектирование учебного материала. Конспект помогает внимательно слушать, лучше запоминать в процес-
се осмысленного записывания, обеспечивает наличие опорных материалов при подготовке к семинару, зачету, экзамену.
Полезно оставить в рабочих конспектах поля, на которых делать пометки из рекомендованной литературы, дополняющие материал прослушанной лекции, а
также подчеркивающие особую важность тех или иных теоретических положе-
ний.
В случае неясности по тем или иным вопросам необходимо задавать препо-
давателю уточняющие вопросы. Следует ясно понимать, что отсутствие вопросов без обсуждения означает в большинстве случаев неусвоенность материала дисци-
плины.
7
2.3 Краткое содержание лекций.
2.3.1. Раздел 1. Задачи линейного программирования и методы решения.
Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значе-
ния целевой функции, причем значения переменных должны принадлежать неко-
торой области допустимых значений.
Введем условные обозначения:
– параметры модели
x – управляющие переменные или решения
X – область допустимых значений
– случайные или неопределенные факторы
W – целевая функция или критерий эффективности (критерий оптимально-
сти)
В соответствии с введенными терминами математическая модель задачи имеет следующий вид:
W=W(x, , )max(min), x X
Решить оптимизационную задачу – это значит найти такое оптимальное ре-
шение x*X, чтобы при данных фиксированных параметрах и с учетом неиз-
вестных факторов значение критерия эффективности W было по возможности максимальным (минимальным).
W*=W(x*, , )=max(min) W=W(x, , ), x X.
Таким образом, оптимальное решение – это решение, предпочтительное пе-
ред другими по определенному критерию эффективности (одному или несколь-
ким).
Оптимизационная задача является неразрешимой, если она не имеет опти-
мального решения. В частности, задача максимизации будет неразрешима, если целевая функция не ограничена сверху на допустимом множестве.
8
Большое число экономических задач сводится к линейным математическим моделям, т.е. целевая функция линейна и область допустимых значений определя-
ется системой линейных равенств или неравенств. Традиционно оптимизацион-
ные линейные математические модели называются моделями линейного про-
граммирования (линейного планирования).
Постановка задачи линейного программирования.
Максимизировать (минимизировать) функцию
n
f c j x j max(min)
j 1
при ограничениях
n
aij x j bi , i 1, m1
j 1
n
aij x j bi , i m1 1, m2
j 1
n
aij x j bi , i m2 1, m
j 1
где xj, j=1,…n – управляющие переменные или решения задачи, bj, aij, i=1,…m, j=1,…n – параметры,
f – целевая функция или критерий эффективности задачи.
Говорят, что задача представлена в канонической форме, если математиче-
ская модель задачи имеет вид (система ограничений – это система уравнений и все переменные неотрицательные):
n
f c j x j max
j 1
n |
|
|
|
|
aij x j |
b j , i 1, m |
|||
j 1 |
|
|
|
|
|
|
|
|
|
x j 0, |
j 1,n |
Пример 1 экономической задачи, сводящийся к линейной модели. Пред-
приятие производит изделия трех видов, поставляет их заказчикам и реализует на
9
рынке. Заказчикам требуется 1000 изделий первого вида, 2000 изделий второго вида и 2500 изделий третьего вида.
Условия спроса на рынке ограничивают число изделий первого вида 2000
единицами, второго – 3000 и третьего – 5000 единицами.
Для изготовления изделий используется 4 типа ресурсов. Количество ресур-
сов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации одного изделия каждого вида заданы в таблице.
Тип ресурсов |
|
Вид изделий |
|
Всего |
|
1 |
2 |
3 |
ресурсов |
||
|
|||||
1 |
500 |
300 |
1000 |
25000000 |
|
|
|
|
|
(25млн) |
|
2 |
1000 |
200 |
100 |
30млн |
|
3 |
150 |
300 |
200 |
20млн |
|
4 |
100 |
200 |
400 |
40млн |
|
Прибыль |
20 |
40 |
50 |
|
Как организовать производство, чтобы:
1)обеспечить заказчиков;
2)не допустить затоваривания;
3) получить максимальную прибыль.
Построение математической модели.
1 этап – формирование цели:
Цель – получение максимальной прибыли.
2 этап – определение параметров модели:
Параметрами являются все числовые данные, приведенные в условии задачи.
3 этап – формирование управляющих переменных, изменяя значение кото-
рых, можно приближаться к поставленной цели.
Управляющие переменные:
х1 – число изделий первого вида;
х2 – число изделий второго вида;
х3 – число изделий третьего вида.
4 этап – определение области допустимых значений.
10