НОУ "Математическое моделирование при решении многокритериальных задач на оптимизацию."

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ

АДМИНИСТРАЦИИ ГОРОДА НИЖНЕГО НОВГОРОДА

МУНИЦИПАЛЬНОЕ  БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«ШКОЛА № 66»

Научное общество учащихся

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

                                                                       Выполнил: Огарков Александр

                                                                       ученик 9 «а» класса

                                                                       МБОУ «Школа №66»

                                                                      Руководитель: Китаева М.В.

                                                                       учитель математики

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

                                            2015-2016 год

Содержание :

Введение…………………………………...……………………………………….     3

ГЛАВА I   Теоретическая часть

 1.1   Математическая модель объекта проектирования………………….     5

1.2    Характеристика типовых задач математического

 моделирования и подходов к их решению………………………….   8

1.3  Компоненты принятия решений………………….………………….  11

1.4  Теория решения многокритериальной задачи с помощью

        метода оптимального выбора…………………….…..………...…....  13

1.5  Теория метода многокритериальной оптимизации по Парето….....  14

ГЛАВА II  Практическая часть

 Решение задач на МКО по методу оптимального выбора

     и по методу Парето……………………….…………………………...…    20

Заключение……………………………………………………..…………….…...    29

Литература……………………………………………………..………………......   31

Говорят, самое сложное –

это сделать правильный выбор.

(Из газет)

Введение

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

Таким образом, необходимость принятия решений так же стара, как и само человечество. Несомненно, уже в доисторические времена первобытные люди, отправляясь, скажем, охотится на мамонта, должны были принимать те или иные решения: в каком месте устроить засаду? Как расставить охотников? Чем их вооружить?

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

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

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

Цель работы:

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

Задачи работы:

— дать определение понятию «многокритериальная оптимизация» с точки зрения математического моделирования;

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

— решить практические задачи, используя данные методы.

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

Глава I

Теоретическая часть

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

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

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

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

1.1 Математическая модель объекта проектирования.

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

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

Модель – это материальный тип или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение даёт новые знания об объекте оригинале.

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

В математических методах широко применяются как аналитические, так и статистические модели.

Аналитические модели более грубы, учитывать меньшее число факторов, всегда требует каких-то допущений и упрощений.

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

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

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

Решение - это всякий определенный набор зависящих от нас параметров.

Оптимальные решения - решения, по тем или иным признакам предпочтительнее перед другими.

Допустимые решения - это решения, удовлетворяющие системе ограничений и требованию неотрицательности.

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

Оптимальный план – допустимый план, который удовлетворяет условиям максимизации или минимизации (в зависимости от условия задачи).

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

Математическое моделирование –  метод изучения внешнего мира, а также прогнозирования и управления.

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

·     Первый этап – формулировка законов, связывающих основные объекты модели. Этот этап требует широкого знания фактов, относящихся к изучаемым явлениям, и глубокого проникновения в их взаимосвязи.

·     Второй этап – исследование математических задач, к которым приводят построенные математические модели.

·     Третий этап – выяснение того, удовлетворяет ли принятая гипотетическая модель критерию практики.

·     Четвертый этап – последующий анализ модели в связи с накоплением данных об изучаемых явлениях и модернизации модели.

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

1) Построение модели. На этом этапе задается некоторый «нематематический» объект — явление природы, конструкция, экономический план, производственный процесс и т. д. При этом, как правило, четкое описание ситуации затруднено. Сначала выявляются основные особенности явления и связи между ними на качественном уровне. Затем найденные качественные зависимости формулируются на языке математики, то есть строится математическая модель. Это самая трудная стадия моделирования.

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

3) Интерпретация полученных следствий из математической модели. Следствия, выведенные из модели на языке математики, интерпретируются на языке, принятом в данной области.

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

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

3. Классификация моделей

Классифицировать модели можно по разным критериям. Например, по характеру решаемых проблем модели могут быть разделены на функциональные и структурные. В первом случае все величины, характеризующие явление или объект, выражаются количественно. При этом одни из них рассматриваются как независимые переменные, а другие — как функции от этих величин. Математическая модель обычно представляет собой систему уравнений разного типа (дифференциальных, алгебраических и т. д.), устанавливающих количественные зависимости между рассматриваемыми величинами. Во втором случае модель характеризует структуру сложного объекта, состоящего из отдельных частей, между которыми существуют определенные связи. Как правило, эти связи не поддаются количественному измерению. Для построения таких моделей удобно использовать теорию графов.

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

1.2 Характеристика типовых задач математического моделирования и подходов к их решению.

Задачи моделирования делятся на две категории: прямые и обратные.

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

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

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

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

Их можно разделить на:

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

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

Исходные данные	Переменные	Зависимости	Задача
Детерминированные	Непрерывные	Линейные	Линейного программирования
	Целочисленные	Линейные	Целочисленного программирования
	Непрерывные, целочисленные	Нелинейные	Нелинейного программирования
Случайные	Непрерывные	Линейные	Стохастическое программирование

А по критерию эффективности:

·                   одноцелевое принятие решений (один критерий эффективности);

·                   многоцелевое принятие решений (несколько критериев эффективности).

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

В общем виде обратная детерминированная задача будет выглядеть следующим образом.

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

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

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

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

Это уже другая, не чисто математическая задача. Наличие неопределенных факторов переводит эту задачу в новое качество: она превращается в задачу о принятии решений в условиях неопределенности.

1.3 Компоненты принятия решений.

1. Варьируемые параметры -

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

• Варьируемые параметры (варьируемые переменные) – то, что ЛПР может назначать произвольно при принятии решения.

• Выбор значений параметров при принятии решения и есть задача ЛПР.

• Оптимальное значение параметров – это значит наилучшее в каком-то смысле.

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

параметры принятия решения.

– Описывается одним или несколькими ограничениями

– ЛПР в процессе принятия решения может менять ОДЗ и рассматривать другие возможные варианты.

• Внешние и внутренние ограничения

– Внешние ограничения (ограничения среды – экзогенные)

– Внутренние ограничения (ограничения модели – эндогенные)

• ОДЗ задается набором ограничений на варьируемые параметры:

– Частные ограничения на переменные;

– Ограничения общего вида (линейные и нелинейные).

• Ограничения для варьируемых параметров 𝑥 из n-мерного пространства: 𝑎_𝑗 ≤ 𝑥_𝑗 ≤ 𝑏_𝑗 , 𝑗 = 1, … , 𝑛.

– Данный тип ограничений в практическом применении существует почти всегда.

• Ограничения общего вида для вектора варьируемых параметров 𝑥 из n-мерного евклидового пространства: 𝑔(𝑥) = 𝑔(𝑥₁, … , 𝑥_𝑛) ≥ 0.

– Данные ограничения могут быть легко преобразованы в ограничения типа равенств.

    3. Цель и критерий оптимальности.

• Цель характеризует поведение ЛПР в процессе принятия решения.

• Критерий оптимальности – характеристика (или одна их характеристик) варианта решения.

          – Критерий обязательно должен быть выражен в числовой форме.

          – Большее (меньшее) значение означает лучшую (худшую)   

             характеристику с точки зрения ЛПР.

         – По данному критерию можно сравнить любые два варианта (лучше,  хуже или эквивалентно)

• Частный критерий – объективная характеристика.

         – При условии, что значение характеризует качество (вес, размеры, стоимость, калорийность и т.д. )

• Наличие/отсутствие возможности.

        – Приводит к бинарным значениям характеристик качества (1/0).

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

        – Такая характеристика указывает, какое значение лучше, но не    

         указывает, на сколько.

• Экспертная оценка.

        – Результат субъективного оценивания эксперта и/или ЛПР.

    4. Принцип оптимальности и роль ЛПР

• Принцип оптимальности – это принцип, по которому выбирается решение из множества возможных:

          – ЛПР выбирает «наилучшее» с его точки зрения решение;

          – Оптимальное решение в многокритериальном случае чаще всего не    существует;

– Рациональное решение – решение, принятие которого можно объективно объяснить.

• Роль ЛПР в процессе принятия решения:

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

1.4 Теория решения многокритериальной задачи с помощью метода оптимального выбора.

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

Пусть имеется множество из k альтернатив А = {а1,а2,..аk}.

Тогда для критерия С может быть рассмотрено нечеткое множество

С= {с1/а1, с2)/а2,. . , сk)/ак}, где сi/аi – значение из промежутка [0, 1].

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

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

D = C1 ∩C2 ∩...∩Cn

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

1.5 Теория метода многокритериальной оптимизации по Парето

Вильфредо Парето

(1848 – 1923)

Итальянский математик, инженер, экономист и социолог

• Диссертация «Фундаментальные принципы равновесия в твердых телах»

• Длительная работа инженером в ж/д отрасли и в металлургии

• С 1893 – профессор политической экономии Лозаннского университета в Швейцарии

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

·                   Закон Парето, или принцип Парето, или принцип 20/80

– Эмпирическое правило: «20% усилий дают 80% результата, а остальные 80% усилий — лишь 20% результата».

– Может использоваться как базовая установка в анализе факторов эффективности какой-либо деятельности и оптимизации её результатов:

• Нужно правильно выбрать минимум самых важных действий. Дальнейшие улучшения неэффективны и могут быть неоправданны.

·                   Оптимальность по Парето — такое состояние системы, при котором значение каждого частного показателя, характеризующего систему, не может быть улучшено без ухудшения других.

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

– Признаётся право на все изменения, которые не приносят никому дополнительного вреда.

– Ситуация, когда достигнута эффективность по Парето — это ситуация, когда все выгоды от обмена исчерпаны.

·                   Множество Парето – множество состояний системы, оптимальных по Парето.

Пусть имеется область D и задана функция f – целевая функция (критерий). Задача оптимизации имеет вид

(max)min f(X)

XÎD

Точка X₁ÎD называется оптимальной (недоминируемой, неулучшаемой), если не существует точки X₂ÎD, для которой f(X₁)>f(X₂) (целевая функция минимизируется). Аналогично можно исключить из области D точки, которые заведомо не могут оказаться наилучшими.

Очевидно, что в обобщённом смысле определение оптимальности можно трактовать как описание (выделение) в подмножестве D некоторого нового подмножества D₀, т.е. некоторое сужение D до D₀ ÌD. В зависимости от характера описания, подмножество D₀ может оказаться пустым, состоять из одного элемента, содержать более одного элемента. Описание D₀ можно проводить либо только с помощью критериев Fi, либо использовать дополнительные условия. Здесь мы рассмотрим направление, которое связано с определением оптимальности по Парето.

·                   Отношение доминирования по Парето. Парето-оптимальность.

Как было сказано раньше для всякого решения XÎD набор его оценок по всем критериям, т.е. набор (F₁(X), F₂(X), . . .,Fm(X)), есть векторная оценка решения X. Векторная оценка X содержит полную информацию о ценности (полезности) этого решения для ЛПР и сравнение любых двух решений заменяется сравнение их векторных оценок. Пусть в МЗО требуется получить меньшие значения каждого частного критерия (минимизировать частные критерии) Fi(X).

Опр. Пусть имеются два решения X₁ и X₂. Говорят, что решение X₁ лучше (предпочтительнее, эффективнее, доминирует) решения X₂, если F_i(X₁)<=F_i(X₂) для всех  i=1,m, и хотя бы для одного j - го критерия выполняется строгое неравенство F_i(X₁)<F_i(X₂).

Опр. Решение X₂ называется доминируемым, если существует решение X₁, не хуже чем X₂, т.е. для любой оптимизируемой функции Fi, I=1, 2, …, m,

Fi(X₂)£Fi(X₁) при максимизации функции Fi, Fi(X₂)³Fi(X₁) при минимизации Fi.

В случае доминирования при переходе от X₂ к X₁ ничего не будет проиграно ни по одному из частных критериев, но в отношении j - го частного критерия точно будет получен выигрыш. Говорят, что решение  X₁ лучше (предпочтительнее) решения X₂.

Опр. Стратегия X₁ÎD называется эффективной (оптимальной по Парето), если не существует стратегии X₂ÎD такой, что Fi(X₂) £Fi(X₁),

 i=1, . . ., m, F(X₂)¹F(X₁),

Опр. Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.

Очевидно, тогда в составе множества D нет смысла сохранять решение X₂, оно вытесняется (или,  как говорят, “доминируется”) решением X₁.  Выбросим решение X₂ как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (PÌD).

Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать Y_P (Y_P ÍY_D).

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

В области Y_c нет противоречия между частными критериями оптимальности, т.к. каждая точка XÎD может быть изменена таким образом, что будет одновременно улучшены все частные критерии.

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

Проиллюстрируем приём выделения паретовских решений на примере задачи с двумя критериями F₁ и F₂. Множество D состоит из 11 возможных решений. Каждому решению соответствуют определённые значения показателей F₁ и F₂. Пусть имеются следующие векторные оценки: F(X₁)=(2;4), F(X₂)=(3;5), F(X₃)=(3;3), F(X₄)=(5;2), F(X₅)=(4;3), F(X₆)=(1;3), F(X₇)=(2;3), F(X₈)=(3;2), F(X₉)=(2;2), F(X₁₀)=(3;1), F(X₁₁)=(2;1). Векторные оценки исходов представим точками координатной плоскости (по оси абсцисс откладываем значения критерия F₁, а по оси ординат – значения критерия F₂). Используем принцип оптимальности по Парето для выделения эффективных решений. Решение X₁ вытесняется решением X₂, решение X₂ лучше решений X₃, X₇, X₈, X₉, X₁₀ и X₁₁. Решение X₄ по первому критерию лучше решения X₅, а по второму наоборот, т.е. имеем неулучшаемые решения, и т.д. После проведённого анализа у нас остались три решения X₂,X₄, X₅ оптимальных по Парето.

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

                                                       Множество Y_k

Когда из множества возможных решений выделены эффективные, "переговоры" могут вестись уже в пределах этого "эффективного" множества. На рис. образуют три решения X₂, X₄, X₅; из них X₄ лучше по критерию F₁, а решение X₂ по критерию F₂. Дело ЛПР, выбрать тот вариант, который для него предпочтителен и “приемлем” по обоим критериям.

Замечание. Точка Y₁ выбирается в Y_D в том и только в том случае, когда любая другая точка Y₂ из Y_D имеет хотя бы по одной координате значение больше чем Y₁ (критерии минимизируются).

Замечание. Для определения эффективных точек используют правило “уголка”. Уголок вида  ∟ используется для определения компромиссных точек в критериальном пространстве, когда критерии максимизируются, а уголок   ┐когда критерии минимизируются.

В случае, когда множество допустимых исходов является непрерывным, их векторные оценки "заполняют" некоторую область Y_D на плоскости. В этом случае множество Парето-оптимальных оценок (представляет собой часть границы Y_D, образно говоря, её "юго-западную" границу (красная линия)). Если критерии максимизируются то – "северо-восточную" (синяя линия) границу области Y_D, без тех ее частей, которые параллельны одной из координатных осей или лежат в «глубоких» провалах.

Преимущества метода:

1) Критерии равнозначны;

2) Метод математически объективен.

Недостаток метода: одно окончательное решение получается только в частном случае, то есть количество Парето-эффективных решений, как правило, более одного.

ГлаваII

Практическая часть

 Решение задач на МКО по методу оптимального выбора и по методу Парето.

Задача 1: Определить, какие экзамены по выбору (ОГЭ) оптимально выбрать девятикласснику для успешной сдачи с наименьшими затратами при подготовке, исходя из условий:

С1: сложность предмета в соответствии с СанПиНами для общеобразовательных учреждений;

C2:  количество заданий по каждому предмету, в соответствии с демоверсиями.

1)    Метод оптимального выбора.

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

предметы	сложность предмета(С1)	кол-во заданий(С2)	сложность предмета	кол-во заданий
химия	12	22	0,92	0,61
физика	13	26	1	0,72
обществознание	9	31	0,69	0,86
биология	7	32	0,53	0,89
английский язык	9	36	0,69	1
география	5	23	0,38	0,64
история	10	35	0,77	0,97
литература	7	25	0,53	0,69
информатика	7	21	0,53	0,58
эталон	13-100%	36-100%	1	1

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

предметы	сложность предмета	кол-во заданий	mах
химия	0,92	0,61	0,92
физика	1	0,72	1
обществознание	0,69	0,86	0,86
биология	0,53	0,89	0,89
английский язык	0,69	1	1
география	0,38	0,64	0,64
история	0,77	0,97	0,97
литература	0,53	0,69	0,69
информатика	0,53	0,58	0,58

D = min{0,92/хим; 1/физ; 0,86/общ; 0,89/биол; 1/англ; 0,64/геогр; 0,97/ист; 0,69/лит; 0,58/инф } = = {0,64/геог;0,58/инф}

Оптимальными решениями по данному методу являются два предмета: география и информатика.

2) Метод Парето.

предметы	сложность предмета	кол-во заданий
химия	0,92	0,61
физика	1	0,72
обществознание	0,69	0,86
биология	0,53	0,89
английский язык	0,69	1
география	0,38	0,64
история	0,77	0,97
литература	0,53	0,69
информатика	0,53	0,58

Построим диаграмму:

Оптимальные решения по методу Парето –

география, информатика ("юго-западная" граница).

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

Задача 2: Определить, какие средне-специальные учебные заведения оптимальны для поступления выпускниками 9 классов.

Для проведения исследования были выбраны 10 ССУЗов, исходя из опроса учащихся 9 класса.

Анкета:

В какой колледж вы хотели бы поступить после 9 класса, если не пойдете в 10-11 класс?

1. Нижегородский авиационный технический колледж – ул. Чаадаева 2а

- наименование специальности: «Производство летательных аппаратов», «Технология машиностроения», «Сварочное производство», «Социальная работа», «Экономика и бухгалтерский учет», Электромонтер по ремонту и обслуживанию электрооборудования , Станочник (металлообработка), Слесарь по ремонту строительных машин,  Повар, кондитер, Сварщик (электросварочные и газосварочные работы)

                2. Нижегородский автомеханический техникум – пр.Ленина, 111

- наименование специальности: Техническое обслуживание и ремонт автомобильного транспорта, Экономика и бухгалтерский учет,  Техническая эксплуатация и обслуживание электрического и электромеханического оборудования , Монтаж и техническая эксплуатация промышленного оборудования, Технология машиностроения , Автомобиле - и тракторостроение , Эксплуатация транспортного электрооборудования и автоматики, Программирование в компьютерных системах 

- 3. Нижегородский Губернский колледж –  Московское шоссе, 1, Московское шоссе, 52а, ул. Витебская, 41

- наименование специальности: Туризм Программирование в компьютерных системах Информационные системы, Банковское дело, Экономика и бухгалтерский учет (по отраслям), Право и организация социального обеспечения, Страховое дело (по отраслям), Операционная деятельность в логистике, Документационное обеспечение управления и архивоведение, Коммерция (по отраслям), Товароведение и экспертиза качества потребительских товаров, дошкольное образование

4. Нижегородский радиотехнический колледж -  ул. Студенческая, 6а

- наименование специальности: Техническое обслуживание и ремонт радиоэлектронной техники, Информационные системы, Монтажник  радиоэлектронной аппаратуры и приборов, Компьютерные системы и комплексы, Информационные системы, Радиомеханик, Оператор связи

5. Нижегородский политический колледж –  ул. Энгельса,3

- наименование специальности: Экономика и бухгалтерский учет, Операционная деятельность в логистике, Техническая эксплуатация и обслуживание электрического и электромеханического оборудования, Сварочное производство,   технология  машиностроения, Судостроение, Монтаж и техническое обслуживание судовых машин и механизмов, Операционная деятельность в логистике, Техническая эксплуатация и обслуживание электрического и электромеханического оборудования

6. Нижегородское художественное училище – Варварская, 8

 наименование специальности: живопись, дизайн

7. Нижегородский  медицинский колледж  -  Учебный корпус №3 на ул. Павла Мочалова, д. 9, Административно-учебный корпус №1 на ул. Июльских дней, д. 8, корпус №2 на ул. Ильинская, д. 20

Наименование специальности: лечебное дело, акушерское дело, медико-профилактическое дело, стоматология, сестринское дело

8. Нижегородский строительный техникум – пр. Гагарина,12

Наименование специальности: Монтаж и эксплуатация внутренних сантехнических устройств, кондиционирования воздуха и вентиляции, Строительство и эксплуатация зданий и сооружений, Строительство и эксплуатация зданий и сооружений, Строительство и эксплуатация зданий и сооружений, Рациональное использование природохозяйственных комплексов, Архитектура

9.Нижегородский железнодорожный техникум – ул.Чкалова, 5а

Автоматика и телемеханика на транспорте, Локомотивы, Техническая эксплуатация подвижного состава, Электроснабжение

10.Нижегородский автотранспортный техникум- ул. Невзоровых 34

- наименование специальности Техническое обслуживание и ремонт автомобильного транспорта, Организация перевозок и управление на транспорте (по видам), Операционная деятельность в логистике, Эксплуатация транспортного электрооборудования и автоматики (по видам транспорта, за исключением водного).

Выпускники - эксперты оценивали УЗ по 10-балльной системе.

Далее было вычислено среднее арифметическое значение по каждому УЗ и найдены значения критерия «Выбор эксперта», исходя из условия, что наибольшее значение принимается за 100%.

№№	Наименование колледжа	Выбор абитуриента (сред.ариф. из 10 учеников)	Выбор абитуриента (эксперта)
1	Нижегородский авиационный технический колледж	0,5	0,06
2	Нижегородский автомеханический техникум	4,6	0,59
3	Нижегородский Губернский колледж	5,9	0,76
4	Нижегородский радиотехнический колледж	7,8	1
5	Нижегородский политический колледж	0,6	0,08
6	Нижегородское художественное училище	5,8	0,74
7	Нижегородский  медицинский колледж	6,9	0,88
8	Нижегородский строительный техникум	6	0,77
9	Нижегородский железнодорожный техникум	6,1	0,78
10	Нижегородский автотранспортный техникум	3	0,38
			7,8- 100%

Далее был составлен рейтинг данных УЗ (по среднему баллу за 2015год),  чем выше балл, тем выше рейтинг – это второй критерий.

№№	Наименование колледжа	средний балл аттестата	рейтинг учебного заведения (по среднему баллу аттестата) за 2015 год	значимость рейтинга(1 место-1,0)
1	Нижегородский авиационный технический колледж	4,6	2	0,9
2	Нижегородский автомеханический техникум	4,13	5	0,6
3	Нижегородский Губернский колледж	4	6	0,5
4	Нижегородский радиотехнический колледж	4,5	3	0,8
5	Нижегородский политический колледж	4,42	4	0,7
6	Нижегородское художественное училище	4,9	1	1
7	Нижегородский  медицинский колледж	4,9	1	1
8	Нижегородский строительный техникум	4,9	1	1
9	Нижегородский железнодорожный техникум	4,5	3	0,8
10	Нижегородский автотранспортный техникум	3,95	7	0,4

1)    Метод оптимального выбора.

Были найдены наименьшие значения по каждому УЗ.

№№	Наименование колледжа	Выбор абитуриента (эксперта)	Рейтинг УЗ	min
1	Нижегородский авиационный технический колледж	0,06	0,9	0,06
2	Нижегородский автомеханический техникум	0,59	0,6	0,59
3	Нижегородский Губернский колледж	0,76	0,5	0,76
4	Нижегородский радиотехнический колледж	1	0,8	0,8
5	Нижегородский политический колледж	0,08	0,7	0,7
6	Нижегородское художественное училище	0,74	1	0,74
7	Нижегородский  медицинский колледж	0,88	1	0,88
8	Нижегородский строительный техникум	0,77	1	0,77
9	Нижегородский железнодорожный техникум	0,78	0,8	0,78
10	Нижегородский автотранспортный техникум	0,38	0,4	0,38

D= max{0,06/1; 0,59/2; 0,76/3; 0,8/4; 0,7/5; 0,74/6; 0,88/7; 0,77/8; 0,78/9; 0,38/10}= {0,8/4; 0,88/7; 0,78/9}

Оптимальными решениями по данному методу являются:

Нижегородский радиотехнический колледж (4),

Нижегородский  медицинский колледж (7),

Нижегородский железнодорожный техникум (9).

2)     Метод Парето.

№№	Наименование колледжа	Выбор абитуриента (эксперта)	Рейтинг УЗ
1	Нижегородский авиационный технический колледж	0,06	0,9
2	Нижегородский автомеханический техникум	0,59	0,6
3	Нижегородский Губернский колледж	0,76	0,5
4	Нижегородский радиотехнический колледж	1	0,8
5	Нижегородский политический колледж	0,08	0,7
6	Нижегородское художественное училище	0,74	1
7	Нижегородский  медицинский колледж	0,88	1
8	Нижегородский строительный техникум	0,77	1
9	Нижегородский железнодорожный техникум	0,78	0,8
10	Нижегородский автотранспортный техникум	0,38	0,4

Построим диаграмму:

Оптимальные решения по методу Парето («северо-восточная граница»):

Нижегородский  медицинский колледж  (7),

Нижегородский радиотехнический колледж (4).

Вывод: по данным методам два решения из трех совпадают.

Проблемы многокритериальной оптимизации.

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

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

· нет полного списка критериев, характеризующих качество решений;

· не построены все или некоторые шкалы критериев;

· нет оценок вариантов решений по шкалам критериев;

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

Заключение

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

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

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

· модель должна быть логически непротиворечива;

· модель должна содержать описание всех возможных элементов задачи принятия решений и свойства этих элементов;

· модель должна давать возможность использовать реальную информацию о задаче, полученную от экспертов, ЛПР;

· модель должна быть достаточно простой и удобной для анализа и использования ЛПР.

Под критериями понимают такие показатели, которые:

· признаются ЛПР в качестве характеристик степени достижения поставленной цели;

· являются общими и измеримыми для всех допустимых решений;

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

Набор критериев многокритериальной задачи должен удовлетворять следующим требованиям:

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

· операциональность (каждый критерий должен иметь понятную для ЛПР формулировку, ясный и однозначный смысл, характеризовать определенный аспект решения);

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

· неизбыточность (разные критерии не должны учитывать один и тот же аспект решения);

· минимальность (аспект решения должен содержать как можно меньшее число критериев);

· измеримость (каждый критерий должен допускать возможность количественной или качественной оценки степени достижения соответствующей цели).

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

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

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

Литература:

1.   Т.А.Зудина «РЕШЕНИЕ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ ОПТИМИЗАЦИИ В ШКОЛЬНОМ КУРСЕ С ИСПОЛЬЗОВАНИЕМ АППАРАТА«НЕЧЕТКИХ МНОЖЕСТВ»»,г.Пенза, (Пензенский государственный педагогический институт)

2.   А.Кофман «Введение в теорию нечетких множеств», изд. «Радио и связь», 1982

3.   А.В.Лотов « Визуализация границы Парето в задачах многокритериальной оптимизации» (Лекции в МФТИ, 2013 г.)

4.   В.Д. Ногин «Принятие решений при многих критериях», учебно-методическое пособие, Санкт-Петербург,2007

5.   В.В. Подиновский, В.Д. Ногин «Парето-оптимальные решения многокритериальных задач», изд. «Наука»,1982

6.   Д. Химмельблау. Прикладное нелинейное программирование.  – М.: Мир, 1974. 534 с.

7.    Д.Е. Шапошников Лекции « Многокритериальный анализ. Основы и принципы.», 2013

8.   А.Н. Ярыгин «МЕТОДЫ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО РЕШЕНИЯ ЭКОНОМИЧЕСКИХ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ», 2013