Задача об оптимальном расходе топлива летательного аппарата при наборе высоты

Теория принятия решений

Красноярск

2013

УДК 519.8

Товбис, Е.М. Теория принятия решений: учебное пособие по выполнению лабораторных работ для студентов направлений 230400.62 «Информационные системы и технологии», 230100.62 «Информатика и вычислительная техника», 231000.62 «Программная инженерия» очной, заочной, очной сокращенной форм обучения / Е.М. Товбис,
Г.Ш. Шкаберина. - Красноярск: СибГТУ, 2013.- 61 с.

Рецензенты: д-р физ.-мат. н., проф. И.М. Шкедов (СибГАУ);

Е.В. Касьянова (научно-методический совет СибГТУ).

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

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

© Е.М. Товбис,

Г.Ш. Шкаберина, 2013

© ФГБОУ ВПО «Сибирский государственный технологический университет», 2013

Содержание

Введение. 5

1 Теоретические сведения. 7

1.1 Основные определения теории принятия решений. 7

1.1.1 Критерии принятия решений, типы переменных и ограничения. 7

1.1.2 Принципы максимального правдоподобия, Байеса и гарантированных оценок 9

Контрольные вопросы.. 11

1.2 Задачи динамического программирования (ДП) 11

1.2.1 Основные определения. Метод «Последовательный анализ вариантов» 11

1.2.2 Применение уравнения Беллмана в задачах. 14

Контрольные вопросы.. 20

1.3 Многокритериальные задачи. 20

1.3.1 Основные определения. Методы решения многокритериальных задач структурированного типа. 20

1.3.2 Методы решения многокритериальных задач слабоструктурированного типа 25

Контрольные вопросы.. 31

1.4 Элементы теории полезности. 31

1.4.1 Основные определения. Задача с вазами. 31

1.4.2 Парадокс Алле и психология выбора. 34

Контрольные вопросы.. 35

1.5 Элементы теории игр. Матричные игры.. 35

1.5.1 Основные определения. Решение игр в чистых стратегиях. 35

1.5.2 Решение игр в смешанных стратегиях. Упрощение платежной матрицы 37

1.5.3 Статистические игры.. 40

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

Контрольные вопросы.. 44

1.6 Экономические приложения теории принятия решений. 44

1.6.1 Основные определения. Оптимальное поведение фирмы на рынке. 44

1.6.2 Оптимальное поведение потребителя. 46

Контрольные вопросы.. 47

2 Задания на выполнение лабораторных работ. 48

2.1 Основные определения принятия решений. 48

Лабораторная работа № 1 Принципы как помощники в принятии решений 48

2.2 Задачи динамического программирования. 49

Лабораторная работа № 2 Реализация задачи выбора дисциплин. 49

Лабораторная работа № 3 Реализация задачи об оптимальном распределении ресурсов 50

2.3 Многокритериальные задачи. 51

Лабораторная работа № 4 Выбор старосты группы методом АНР. 51

Лабораторная работа № 5 Выбор старосты группы методом ELECTRE. 53

2.4 Элементы теории полезности. 53

Лабораторная работа № 6 Реализация задачи о цветочных композициях 53

2.5 Элементы теории игр. Матричные игры.. 55

Лабораторная работа № 7 Решение матричной игры.. 55

Заключение. 58

Библиографический список. 59

Приложение А (справочное) Перечень ключевых слов. 60

Введение

На протяжении жизни мы постоянно принимаем решения. Каким же образом мы принимаем то или иное решение? Какие факторы влияют на нас? И кто это «МЫ» – менеджер, родитель, студент, слушатель различных курсов, директор и т.д. - одним словом - ЧЕЛОВЕК. Большинство решений человеком принимается на интуитивном уровне. Но не всегда мы можем полагаться на нашу интуицию. Интуиция разным людям может подсказывать различные решения, иногда и неверные. Каким же образом доказать собеседнику, что ваши выводы верны? А если речь идет уже не об одном человеке, а об организации? Тогда на помощь приходит Теория принятия решений - область исследования, вовлекающая понятия и методы математики, статистики, экономики, менеджмента и психологии.

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

Для освоения материала учебного пособия потребуется знакомство с курсами «Методы оптимизации» и «Исследование операций», а также базовые знания математического анализа и теории вероятностей.

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

для направления 231000.62

(ПК-4) – готовность обосновать принимаемые проектные решения, осуществлять постановку и выполнение экспериментов по проверке их корректности и эффективности;

(ПК-7) – способность выполнить начальную оценку степени трудности, рисков, затрат и сформировать рабочий график;

для направления 230100.62

(ОК-4) – способность находить организационно - управленческие решения в нестандартных ситуациях и готовность нести за них ответственность;

(ОК-10) – использование основных законов естественнонаучных дисциплин в профессиональной деятельности, применение методов математического анализа и моделирования, теоретического и экспериментального исследования;

(ПК-2) – способность освоить методики использования программных средств для решения практических задач;

(ПК-6) – способность обосновывать принимаемые проектные решения, осуществлять постановку и выполнять эксперименты по проверке их корректности и эффективности;

для направления 230400.62

(ПК-4) – способность проводить выбор исходных данных для проектирования;

(ПК-25) – способность обосновывать правильность выбранной модели, сопоставляя результаты экспериментальных данных и полученных решений;

(ПК-26) – готовность использовать математические методы обработки, анализа и синтеза результатов профессиональных исследований.

Для выполнения студентам предложены 6 лабораторных работ по разным темам курса. Лабораторные работы выполняются с использованием среды программирования Delphi, MS Visual Studio или иной, согласованной с преподавателем. Отчет по лабораторной работе выполняется в печатном виде и должен содержать следующие разделы: титульный лист, задание, цель работы, ход работы, результаты работы. Объем отчета – 3-5 страниц. До защиты допускаются студенты, выполнившие все задания лабораторной работы. На защите студентам необходимо ответить на контрольные вопросы, представленные в конце каждой работы.

1 Теоретические сведения

1.1 Основные определения теории принятия решений

1.1.1 Критерии принятия решений, типы переменных и ограничения

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

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

" Аппарат ЛПР" – это тот, кто участвовал в подготовке решения и предоставил информацию ЛПР.

!!! Вся ответственность лежит на ЛПР, не важно, кто подготовил документ, важно, кто за него отвечает!!!

В зависимости от поставки задачи и метода решения, задачи принятия решений подразделяются на 4 типа (рисунок 1).

Рисунок 1 – Классификация задач ТПР

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

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

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

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

Операция – это способ достижения поставленной цели.

Оперирующая сторона – участник операции, стремящийся к достижению поставленной цели.

Стратегия операции x – разрешенные способы действия оперирующей стороны.

Типы переменных:

- x_i, i =1, 2..n, xÎ X – управляемые переменные, выбираемые из стратегий оперирующей стороны X;

- y_j, j=1, 2..m, yÎ Y – неуправляемые переменные, относительно которых известно только множество Y (обычно это стратегии противоборствующей стороны);

- z_k, k =1, 2..p, zÎ Z – случайные переменные, относительно которых известны только вероятностные характеристики, с которыми они могут принимать значения из области Z (например, плотность вероятности f(z)).

Критерий эффективности – функция F(x, y, z), характеризующая степень достижения поставленной цели.

Прямая задача теории принятия решений – вычисление функции
F(, y, z) при конкретной стратегии ;

Обратная задача – определение наилучшей стратегии , доставляющей минимум или максимум критерию эффективности операции

(1)

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

- принцип максимального правдоподобия – в соответствии с ним принимают такое значение переменных z, которое соответствует наиболее вероятному, определяемому по плотности f(z);

- принцип Байеса – в соответствии с ним вычисляют математическое ожидание критерия эффективности

; (2)

- принцип гарантированных оценок - в соответствии с ним определяют наихудшую для оперирующей стороны оценку критерия эффективности – нижнюю для задачи максимизации критерия и верхнюю для задачи минимизации:

(3)

1.1.2 Принципы максимального правдоподобия, Байеса и гарантированных оценок

Строительная компания выиграла тендер на строительство завода. Необходимо выполнить следующие виды работ:

A - строительство корпусов;

B - разработка модели изделия;

C - наем и обучение рабочей силы;

D - монтаж оборудования;

E - отладка модели изделия.

Время выполнения работ t_A=2, t_B=1. Значения t_C, t_D, t_E с равной вероятностью выбираются из множества {2, 3, 4}.В зависимости от времени ввода завода в строй определяется прибыль, представленная в таблице 1.

В распоряжении оперирующей стороны имеется денежный резерв R=20 млн. руб., который позволяет ускорить строительство завода на 1 год. Вопрос: стоит ли использовать резерв?

Таблица 1 - Предполагаемая прибыль

Решение.

Пусть x=0 означает неиспользование резерва, а x=1 – использование.

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

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

Рисунок 2 – Сетевой график проекта

Срок ввода завода в строй определится как длительность критического (самого длинного пути):

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

Таблица 2 – Варианты времени строительства завода

Вероятность строительства завода за 4 года – , за 5 и 6 лет соответственно – . Тогда .

Критерий эффективности представлен в таблице 3 для случаев использования или неиспользования резерва:

Таблица 3 - Прибыль предприятия в зависимости от xÎ {0, 1}

Применив основные принципы принятия решений к задаче, дадим совет – использовать или не использовать резерв:

Согласно принципу максимального правдоподобия, наиболее вероятен ввод завода в действие за 5 лет, , что больше, чем .Следовательно, использовать резерв нецелесообразно.

В соответствии с принципом Байеса, средняя прибыль для составит M . Для средняя прибыль составит M , значит, использовать резерв целесообразно.

Гарантированная оценка – ввод завода в строй за максимальный срок – 6 лет (наихудшая ситуация). F(0, 6) < F(1, 6). В этом случае использовать резерв также целесообразно.

Контрольные вопросы

1 Назовите основные принципы принятия решений.

2 Что такое операция, стратегия, оперирующая сторона?

3 Кто является лицом, принимающим решение?

4 Сформулируйте прямую и обратную задачу ТПР.

1.2 Задачи динамического программирования (ДП)

1.2.1 Основные определения. Метод «Последовательный анализ вариантов»

Динамическое программирование (ДП) – это совокупность процедур, используемых для оптимизации многошаговых процессов принятия решений. Основателем метода динамического программирования является Ричард Беллман.

Задача ДП формулируется следующим образом - найти экстремум функции:

(4)

при ограничениях

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

Эта задача имеет следующую геометрическую интерпретацию, представленную на рисунке 3.

Рисунок 3 – Геометрическая интерпретация задачи ДП

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

Идея метода динамического программирования и более общего метода последовательного анализа вариантов состоит в возможности минимизировать не всю сумму по всем переменным, а только пару слагаемых из нее по одной переменной. Цена за эту возможность - необходимость ее решения n +1 раз.

На первом шаге найдем кратчайшее расстояние от прямой «0» до произвольной точки x₁ на прямой «1»:

(5)

На втором шаге найдем кратчайшее расстояние от прямой «0» до произвольной точки x₂ на прямой «2»:

(6)

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

Для произвольного шага к +1 получим аналогичным образом

(7)

Эта рекуррентная формула вместе с начальным условием (5) позволяет определить на последнем шаге расчетов в прямом направлении кратчайшее расстояние от начальной прямой «0» до произвольной точки на конечной прямой «n».

Далее расчет ведется в обратном направлении. Сначала определим конкретную точку на прямой «n» из условия

(8)

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

1.2.2 Применение уравнения Беллмана в задачах

Имеется n инвестиционных проектов и сумма средств для инвестиций . Прибыль от каждого проекта задана функцией - вложения в каждый проект. Должна быть максимизирована суммарная прибыль от всех проектов

(9)

при условии . (10)

Решение. Решение задачи методом последовательного анализа вариантов разобьем на n шагов. На первом шаге выделим деньги первому предприятию, на втором второму и так далее. Обозначим через остаток ресурса после k -го распределения

. (11)

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

Введем функцию

, (12)

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

. (13)

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

(14)

Для произвольного шага k аналогичным образом получим следующее уравнение Беллмана:

, (15)

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

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

Недостаток состоит в том, что для решения задачи необходимо помнить все n функций Беллмана.

Пример

Имеется сумма средств для инвестиций в три проекта порциями по 20 ед. Потенциальная прибыль от вложений в каждый проект представлена в таблице 4.

Таблица 4 - Прибыль от вложений в каждый проект

Основные и промежуточные расчеты сведем в таблицы 5 и 6 соответственно.

В таблице 5 последние два столбца получены из (13) максимизацией функции .Расчеты функции Беллмана для следующих шагов сведены во вспомогательную таблицу 6.

Таблица 5 - Основные расчеты

		k= 1	k =2	k =3
			20, 40
	0, 20
				40, 60, 80

Наибольшая прибыль от вложения 100 единиц в три проекта составляет 26 единиц при вложениях х⁰₁ = 20. Остаток средств после первого шага , наилучшая прибыль от двух последних проектов составляет 21 единицу при вложениях . Остаток средств для последнего проекта .

Таблица 6 - Промежуточные расчеты

			k= 2	k =1

Задача об оптимальном расходе топлива летательного аппарата при наборе высоты

Летательный аппарат находится в точке S₀, которая характеризуется высотой H₀ и скоростью V₀. Необходимо переместить летательный аппарат в точку S_k c координатами H_k и V_k. Пусть одновременно нельзя изменять значение скорости и высоты. Для возможных значений изменения скорости и высоты заданы величины расхода топлива. Определить последовательность перемещений летательного аппарата, при котором суммарный расход топлива при переходе из точки S₀ в точку S_k был бы минимальным.

Между понятиями принципа Беллмана и данных задачи существуют следующие соответствия:

Состояния – вершины сетки, для которых определены значения высоты и скорости.

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

Управление – выбор одной из двух стратегий: изменений высоты, либо скорости.

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

Локальный доход на i-ом этапе – расход топлива при переходе из одного состояния в другое.

Согласно методу ДП определяется оптимальное решение n-мерной задачи путем ее декомпозиции на n этапов. Разобьем диапазоны изменения скорости и высоты на n₁и n₂ интервалов соответственно:

· Диапазон изменения скорости V разбивается на n₁ интервалов величиной ∆ V:

. (16)

где ∆ V – величина шага изменения скорости, n₁–количество интервалов изменения скорости;

· Диапазон изменения высоты H разбивается на n₂ интервалов величиной ∆ H:

, (17)

где ∆ H – величина шага изменения скорости, n₂–количество интервалов изменения скорости.

Введем следующие обозначения:

· Состояние – S_i;

· Этап – переход из множества состоянийS_i-1 на (i-1) шаге в состояние S_i;

· Управление – выбор V_i или H_i;

· Оптимальное управление – цепочка, состоящая из стратегий V_i и H_i;

· Оператор перехода – связь между состояниями;

· Локальный доход – расход топлива при переходе из состояния S_i-1 в состояние S_i.

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

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

Последний этап.

Самолет может находиться в двух состояниях S₁₃ и S₁₄. Точно неизвестно, в каком из этих состояний находится самолет. Для каждого состояния - S₁₃ и S₁₄ - определяется оптимальное управление, переводящее аппарат из рассматриваемого состояния в конечное состояние S₁₅:

· Для состояния S₁₃ одна стратегия - изменение скорости. Локальный доход составляет 12 единиц топлива, он же является условным оптимальным доходом для последнего этапа. Отметим «*» и укажем под состоянием S₁₃ (рисунок 5);

· Для состояния S₁₄ одна стратегия - изменение значения высоты. Локальный доход составляет 14 единиц топлива. Он также является условным оптимальным доходом для последнего этапа. Отметим «*» и укажем под состоянием S₁₄.

Предпоследний этап.

Самолет может находиться в состояниях S₁₀, S₁₁, S₁₂:

· Для состояния S₁₀ одна стратегия - изменение скорости. Условный оптимальный доход для данного состояния равен сумме локального дохода 10 единиц топлива и условного оптимального дохода для состояния S₁₃ 12 единиц топлива, итого 22 единицы топлива. Отметим «*» и укажем под состоянием S₁₀.

Рисунок 4 – Покоординатное движение самолета

· Для состояния S₁₂ одна стратегия - изменение высоты. Условный оптимальный доход для данного состояния равен сумме локального дохода 12 единиц топлива и условного оптимального дохода для состояния S₁₄ 14 единиц топлива, итого 26 единиц топлива. Отметим «*» и укажем под состоянием S₁₂.

· Для состояния S₁₁ существует выбор из двух стратегий:

- изменение высоты. Условный оптимальный доход для данного состояния равен сумме локального дохода 13 единиц топлива и условного оптимального дохода для состояния S₁₃ 12 единиц топлива, итого 25 единиц топлива;

- изменение скорости. Условный оптимальный доход для данного состояния равен сумме локального дохода 13 единиц топлива и условного оптимального дохода для состояния S₁₄ 14 единиц топлива, итого 27 единиц топлива.

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

Последующие этапы проводятся аналогично. Далее решаем задачу в обратном направлении – из точки S₀ в точку S₁₅. Оптимальные решения для каждого из состояний выделяем жирной линией. На рисунке 5 представлено решение задачи.

Контрольные вопросы

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

2 В чем состоит идея метода ДП?

3 Дайте геометрическую интерпретацию задачи ДП.

4 Опишите преимущества и недостатки метода ДП.

1.3 Многокритериальные задачи

1.3.1 Основные определения. Методы решения многокритериальных задач структурированного типа

Многокритериальная задача – это задача принятия решений
< Т, А, К, X, F, D>, где:

· Т – постановка задачи;

· А – множество альтернатив;

· K – множество критериев, содержащее два и более элементов;

· Х – множество шкал оценок критериев;

· F – отображение множества допустимых решений в множество предпочтений эксперта;

· D - решающее правило.

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

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

Альтернативы являются эффективными (или принадлежащими множеству Эджворта – Парето), если каждая из них превосходит другую по какому-либо из критериев.

Например, при построении информационной системы, данные которой представлены в таблице 10, альтернатива 1 эффективна по критерию реактивность, а 2 – по критерию стоимость. Сравнение эффективных альтернатив производится только с учетом дополнительной информации о предпочтениях ЛПР.

Таблица 10 - Варианты построения информационной системы

Метод удовлетворительных требований

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

Метод свертки

Предположим, что задача характеризуется n критериями. Причем первые m из них необходимо максимизировать, а оставшиеся n-m – минимизировать. Тогда общий мультипликативный критерий будет иметь вид:

, (31)

Аддитивный критерий:

, (32)

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

Критерии необходимо нормировать, приводя их значения к диапазону от 0 до 1:

(33)

Нормированное значение получается путем деления на разность между максимальным (верхним) и минимальным (нижним) значениями. Достоинство метода – сведение многокритериальной задачи к однокритериальной.

Недостаток метода – в составном критерии эффективные значения здесь могут компенсировать неэффективные.

Метод уступок

Вначале решается задача оптимизации по главному критерию С₁ без учета остальных критериев. Полученное оптимальное значение – С^*₁. После этого ЛПР определяет величину уступки Δ С₁, и производится оптимизация по следующему по степени важности критерию С₂ при ограничении С₁ ≤ С^*₁ - Δ С₁. И т.д. для всех критериев.

Метод STEM

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

Исходные данные: множество критериев и множество линейных ограничений . Предполагается, что для каждого i- го критерия получена модель, связывающая вектор параметров со значением критерия .

Этапы решения задачи:

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

Таблица 11 - Значения локальной оптимизации критериев

Критерии		…		…
		…		…
…	…	…	…	…	…
		…		…
…	…	…	…	…	…
		…		…

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

2. Вычисляют технические веса (индексы) критериев через систему уравнений

, , (34)

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

3. Проводится оптимизация по суперкритерию
совместно с линейными ограничениями , j=1..n. Результатом является вектор оптимальных параметров и компромиссные значения локальных критериев .

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

Таблица 12 - Попарное сравнение критериев

Задача	Критерии
	…		…
Локальная		…		…
Глобальная		…		…

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

5. Определяется критерий , компромиссное значение которого не удовлетворяет ЛПР. Для него устанавливается приемлемое предельное значение . Критерий переводится в разряд ограничений . Производится решение (m-1) локальных задач с учетом нового ограничения. Получаем наилучшие значения критериев

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

7. ЛПР анализирует получившиеся значения. Если все значения удовлетворяют ЛПР, процесс завершается, иначе переход к шагу 5.

Пример

Построена модель, характеризующая состав персонала организации в динамике для прогнозирования последствий управления кадрами. Использовалось 4 критерия: С1 – удовлетворение кадров,
С2 – фактическая эффективность работы, С3 – стоимость приема на работа дополнительных сотрудников, С4 – стоимость нехватки кадров. В модели 350 переменных и 200 ограничений, не имеется априорной информации о важности критериев (иначе можно использовать метод свертки или удовлетворительных значений критериев).

Первый этап дал следующие значения, представленные в таблице 13.

Таблица 13 - Значения локальной оптимизации критериев задачи

Из таблицы видно, что критерии С1 и С2 сильно зависят друг от друга и противоречат критериям С3 и С4.

Технические веса критериев определены как

.

Результат локальной оптимизации: Z1={1; 1; -276; -157} – максимальные значения, недостижимые одновременно.

Результат глобальной оптимизации: Y1={0, 965; 0, 85; -1920; -1269}

Значения по критериям С3 и С4 для облегчения понимания ЛПР не нормированы, а представлены в единицах стоимости.

При сравнении значений Z1 и Y1 ЛПР признал неудовлетворительным значение критерия С3 и ограничил его нижним уровнем -1000. При :

- Для С1=0, 67; С2=0, 62; С3=-731;

- Для С1=0, 78; С2=0, 72; С3=-157;

- Для С1=0, 84; С2=0, 82; С3=-57;

- Для С1=0, 9; С2=0, 88; С3=-157.

ЛПР выбрал вектор при как обеспечивающий приемлемый компромисс между повышением качества по критерию С3 и понижением качества по критериям С1 и С2.

Решается задача оптимизации по 3 критериям с дополнительным ограничением . Результат: