8557

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования

«Нижегородский государственный архитектурно-строительный университет»

Прокопенко Н.Ю.

ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ

Учебно-методическое пособие по подготовке к лекциям, практическим занятиям

(включая рекомендации по организации самостоятельной работы)

для обучающихся по дисциплине «Оптимизационные задачи» по направлению подготовки 38.03.01 Экономика, профиль Экономика предприятий и организаций

Нижний Новгород

2018

УДК 004.9

Прокопенко Н.Ю. / Оптимизационные задачи [Электронный ресурс]: учеб.- метод. пос. / Н.Ю. Прокопенко; Нижегор. гос. архитектур. - строит. ун-т – Н. Новгород: ННГАСУ, 2018. – 85 с.– 1 электрон. опт. диск (CD-RW).

В настоящем учебно-методическом пособии по дисциплине «Оптимизационные задачи» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебнометодического пособия – это помощь в усвоении лекций и в подготовке к практическим занятиям.

Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Оптимизационные задачи» по направлению 38.03.01 Экономика, профиль Экономика предприятий и организаций.

© Н.Ю. Прокопенко, 2018 © ННГАСУ, 2018

2

Оглавление

1. Общие положения………………………………………………………………............4

1.1 Цели изучения дисциплины и результаты обучения……………………….........4

1.2Содержание дисциплины………………………………………………….…….....4

1.3Порядок освоения материала……………………………………………….….….5

2. Методические указания по подготовке к лекциям………………………….…..........5

2.1Общие рекомендации по работе на лекциях…………………………….………..5

2.2Общие рекомендации при работе с конспектом лекций……………….…..........6

2.3 Краткое содержание лекций………………………………………………..…......6

2.3.1.Раздел 1. Многокритериальная оптимизация ………………………………...6

2.3.2.Раздел 2. Оптимизация в условиях неопределенности и риска ……………38

3.1Общие рекомендации по подготовке к практическим занятиям……………....52

3.2Примеры задач для практических занятий…………………………....….……..52

4.Методические указания по организации самостоятельной работы…….…............74

4.1Общие рекомендации для самостоятельной работы………………….………..74

3

1. Общие положения

1.1 Цели изучения дисциплины и результаты обучения

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

В процессе освоения дисциплины студент должен Знать:

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

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

методы решения многокритериальных оптимизационных задач.

Уметь:

решать типовые оптимизационные задачи;

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

Владеть:

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

методами поиска оптимальных решений в профессиональной деятельности.

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

Материал дисциплины сгруппирован по следующим разделам:

1. Многокритериальная оптимизация.

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

Свертка критериев. Метод идеальной точки, Метод последовательных уступок.

Оптимальность по Парето.

4

2. Оптимизация в условиях неопределенности и риска.

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

1.3 Порядок освоения материала

Материал дисциплины изучается в соответствии с порядком, определённым в

следующей таблице: Таблица 1

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

2. Методические указания по подготовке к лекциям

2.1 Общие рекомендации по работе на лекциях

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

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

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

5

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

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

2.2 Общие рекомендации при работе с конспектом лекций

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

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

также подчеркивающие особую важность тех или иных теоретических положений.

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

2.3 Краткое содержание лекций.

2.3.1. Раздел 1. Многокритериальная оптимизация

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

логических режимов, элементов конструкций, структуры технологических цепочек,

условий экономической деятельности, повышение доходности и т. д.), оптимальное управление построением нематематических моделей объектов управления (миними-

зации невязок различной структуры модели и реального объекта) и многие другие

6

аспекты решения экономических и социальных проблем (например, управление за-

пасами, трудовыми ресурсами, транспортными потоками и т. д.).

Постановка задачи оптимизации.

где f (x) – целевая функция;

X – допустимое множество

x X – допустимая точка задачи.

Классификация задач оптимизации.

Классификацию задач оптимизации можно проводить по нескольким призна-

кам в зависимости от вида функции f (x) и множества Х:

1)детерминированные, стохастические, задачи оптимизации с неопределенно-

стями; статические, динамические (например, задачи управления);

2)безусловной и условной оптимизации;

3)с непрерывными и дискретными переменными (частично - целочисленные,

целочисленные, с булевыми переменными);

4)однокритериальные и многокритериальные;

5)линейные и нелинейные;

6)одномерные и многомерные, причем многомерные задачи могут быть малой и большой размерности;

7)с выпуклыми и невыпуклыми целевыми функциями;

8)одноэкстремальные и многоэкстремальные.

Постановка задачи многокритериальной оптимизации

F( x ) min

F( x ) ( f1 ( x ), ..., fk ( x ))

G( x ) ( g1( x ),...,gm ( x )) (1 )

f1 ( x ), ..., fk ( x ) - компоненты векторной функции F( x ) , часто их называют частными

7

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

В задаче Ошибка! Источник ссылки не найден. функцию мы называли целе-

вой, поэтому задачу (1 ) еще называют и задачей многоцелевой оптимизации. Заме-

тим, что в общем случае, для реализации одной цели можно использовать много критериев. Поэтому задачу (1 ) можно называть задачей многоцелевой оптимизации,

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

Например, при анализе различных экономических проектов возникает задача выбора наиболее предпочтительного из них или нескольких предпочтительных про-

ектов. Все проекты, рассматриваемые в этой задаче, можно условно назвать альтер-

нативами. В качестве них могут выступать инвестиционные проекты, регионы,

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

жат его технические характеристики, а также такие качества, как надежность, эрго-

номичность, внешний вид. При выборе кандидата на должность важнейшими крите-

риями оценки являются квалификация, образование, эрудиция, возраст, коммуника-

бельность и т.п.

В экономических задачах основными критериями служат экономическая эф-

фективность и стоимость, при этом каждый из этих критериев, в свою очередь, мо-

жет быть подразделен на более частные критерии. Считается, что:

показатели-критерии являются одноименными для всех альтернатив и их ко-

личество у всех альтернатив одинаковое;

другие показатели альтернатив либо одинаковы, либо несущественны в дан-

ной задаче.

Если альтернативы оцениваются по m критериям, где m> 1, то такая задача принятия решений называется многокритериальной.

Критерий называется позитивным, если необходимо стремиться к его увели-

чению, и негативным, если необходимо стремиться к его уменьшению. В конкрет-

8

ных задачах принятия решений характер критерия устанавливается по содержатель-

ным соображениям. Преобразование негативного критерия в позитивный (и наобо-

рот) можно осуществить заменой знака.

При рассмотрении многокритериальных задач в общем виде, если не оговоре-

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

В многокритериальной задаче с позитивными критериями цель – получение альтер-

нативы, имеющей как можно более высокие оценки по каждому критерию.

Классификация методов сведения многокритериальной задачи к одно-

критериальной

Для того чтобы процедура согласования реализовывалась эффективно, необ-

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

Многокритериальные оценки (без использования вычислительной техники).

Оценка варианта решения (сценария, программы) по многим критериям означает,

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

можно свести эти показатели естественным образом к одному. В данном случае мо-

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

1. Принцип свертки критериев – применяется при «оптимизации» многих критериев одним координирующим центром (задача многокритериальной оптими-

зации). Для каждого из критериев (целевых функций) f1 (x),..., fn (x) экспертным путем назначаются «веса» (числа):

n

α1,..., αn : α1≥0, ∑ = 1, i = 1

причем αi показывает «важность или значимость» критерия fi. Далее решение х* из множества допустимых решений Х выбирается так, что максимизировать (или минимизировать) свертку критериев:

9

2. Принцип минимакса – применяется при столкновении интересов противо-

борствующих сторон (антагонистический конфликт). Каждое ЛПР сначала для каж-

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

частности, исключен всякий риск.

3. Принцип равновесия по Нэшу – это обобщение принципа минимакса, когда во взаимодействии участвует много сторон, каждая из которых преследует свою цель (прямого противостояния нет). Пусть число ЛПР

(участников неантагонистического конфликта) есть n. Набор выбранных стратегий

(ситуация) (х1*, х2*,..., хn*) называется равновесным, если одностороннее отклоне-

ние любого ЛПР от этой ситуации может привести разве лишь к уменьшению его же

«выигрыша». В ситуации равновесия по Нэшу участники не получают максималь-

ного «выигрыша», но они вынуждены придерживаться ее.

4. Принцип оптимальности по Парето – данный принцип предполагает в качест-

ве оптимальных те ситуации [наборы стратегий (х1*, х2*,..., хn*)], в которых улучше-

ние «выигрыша» отдельного участника невозможно без ухудшения «выигрышей» остальных участников. Этот принцип предъявляет более слабые (чем принцип рав-

новесия по Нэшу) требования к понятию оптимальности, поэтому по этому принци-

пу оптимальные ситуации существуют почти всегда.

Многокритериальные оценки, опирающиеся на компьютерные процедуры.

1.Метод идеальной точки. Точка называется идеальной, если она опти-

мальна сразу по всем критериям. Как правило, такой точки на практике не сущест-

вует. Правилом поиска компромисса может быть минимизация расстояния до иде-

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

10