9758

УДК 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

Порядок освоения дисциплины

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

Пример 1 экономической задачи, сводящийся к линейной модели. Пред-

приятие производит изделия трех видов, поставляет их заказчикам и реализует на

9

рынке. Заказчикам требуется 1000 изделий первого вида, 2000 изделий второго вида и 2500 изделий третьего вида.

Условия спроса на рынке ограничивают число изделий первого вида 2000

единицами, второго – 3000 и третьего – 5000 единицами.

Для изготовления изделий используется 4 типа ресурсов. Количество ресур-

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

Как организовать производство, чтобы:

1)обеспечить заказчиков;

2)не допустить затоваривания;

3) получить максимальную прибыль.

Построение математической модели.

1 этап – формирование цели:

Цель – получение максимальной прибыли.

2 этап – определение параметров модели:

Параметрами являются все числовые данные, приведенные в условии задачи.

3 этап – формирование управляющих переменных, изменяя значение кото-

рых, можно приближаться к поставленной цели.

Управляющие переменные:

х1 – число изделий первого вида;

х2 – число изделий второго вида;

х3 – число изделий третьего вида.

4 этап – определение области допустимых значений.

10