Управление и оптимизация / Larichev - Teoriya i metodi prinyatiya resheniy 2000

связан с визуализацией множества Э-П и предоставлением ЛПР возможности проводить анализ на плоскостях пар критериев при фиксированных значениях других критериев. Этот подход получил название метода достижимых целей [13].

Другой подход применяется в тех случаях, когда ЛПР мо­ жет восстановить по совокупности критериальных оценок, а также по другим параметрам целостный облик альтернативы. Эта ситуация характерна обычно для деятельности конструкто­ ра. Предъявление решений, находящихся на множестве Э-П, помогает конструктору в поиске новых эффективных конструк­ ций механизмов и машин [14 ].

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

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

Дано: область D допустимых значений переменных, опреде­ ляемая совокупностью линейных равенств и неравенств; крите­ рии Ci, оценивающие качество решения.

Каждый из критериев линейно связан с переменными:

I ^ u ^ j '

где п — число переменных (j=l,...,n); сучисловые коэффици­ енты.

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

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

11. Человекомашинные процедуры

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

71

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

Фаза расчетов (компьютер):

•используя полученную от ЛПР на предыдуш;ем шаге ин­ формацию, проводит дополнительные расчеты;

•вычисляет решение, соответствуюш;ее последней информа­ ции ЛПР;

•вырабатывает вспомогательную информацию для ЛПР. Фаза анализа (ЛПР):

•оценивая предъявленное решение (или совокупность реше­ ний), определяет, является ли решение (одно из решений) приемлемым; если да, то ЧМП окончена; в противном слу­ чае ЛПР анализирует вспомогательную информацию;

•сообщает дополнительную информацию, с помош;ью которой компьютер вычисляет новое решение.

Суп^ествует большое количество ЧМП [3], [7]. Различные ЧМП отличаются друг от друга содержанием и способом вы­ полнения каждой из фаз. Первые из разработанных ЧМП осно­ ваны на использовании информации об относительной важно­ сти критериев.

12. Весовые коэффициенты важности критериев

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

С.=2:w,c,,	(1)
1=1
где Ci —частные критерии (i=l,...,N); Wi — веса	(коэффициенты
важности) критериев:
0<w, <1; ^w, =1.	(2)
1=1

72

Идея такого объединения состоит в том, что ЛПР назначает числа (часто по численной шкале 1-100), представляюш;ие для него ценность рассматриваемого критерия. Считается, что ЛПР может назначить такие числа. Далее, весовые коэффициенты нормируются на основе условия (2).

Обратимся к рис. 15. Легко увидеть, что решения, соответ­ ствующие точкам А и В на множестве Парето, могут быть пред­ ставлены в виде

C , = f w X ^ C 3 = g w X -

1=1 1=1

Существует лемма [8], утверждающая, что для линейной задачи любое эффективное, находящееся на множестве Э—П решение может быть представлено в виде (1), т. е. в виде весов, умноженных на частные критерии. Следовательно, формально задача сводится к нахождению весов.

Возникла идея, что эти веса можно получить от ЛПР опера­ тивно. Если ЛПР затрудняется в начале процесса решения (до изучения области D) сразу назвать эти веса, то можно постро­ ить ЧМП следующего содержания: ЛПР назначает первона­ чальные веса, смотрит на решение и корректирует веса до по­ лучения удовлетворительного результата.

13.Классификация ЧМП

В[3] предложена классификация ЧМП, основанная на ха­ рактере информации, получаемой от ЛПР на фазе анализа.

Первая группа ЧМП - прямые ЧМП, в которых ЛПР непо­ средственно назначает веса критериев и корректирует их на ос­ нове полученных решений.

Для второй группы ЧМП задача ЛПР состоит в сравнении многокритериальных решений. Эта группа называется ЧМП оценки векторов.

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

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

73

Перед решением задачи рекомендуется произвести норми­ рование критериев, определив диапазон их изменения от О до 1:

с;(х): С,(х)-С,(х) С|с(х)-С,(х)

где С^.Ск - минимально и максимально возможные значения

к-го критерия Ск (х) — промежуточное значение.

Кроме того, как это было показано выше на примере (п. 7), для каждого из критериев вычисляется оптимальное абсолют­ ное значение. Вектор таких (недостижимых одновременно) зна­ чений помогает ЛПР оценить пределы возможного.

14.Прямые человекомашинные процедуры

Воснове прямых ЧМП лежит предположение, что человек может искать наилучшее решение путем непосредственного на­ значения ряда параметров (например, весов критериев) и срав­ нения получаюш;ихся решений.

Вкачестве примера прямых ЧМП рассмотрим процедуру SIGMOP (последовательный генератор информации для много­ целевых задач [9]). В ней ЛПР пытается найти хорошее реше­ ние путем назначения весов критериев (wi) и уровней допусти­ мых значений по всем критериям одновременно (Ci>ii).

Лицо, принимающее решение, задает начальные значения wi и ii(i=l,...,N). Далее на фазе расчетов компьютер определяет новую область D допустимых значений переменных и находит в ней значение глобального критерия (1), а также всех отдельных критериев. Значения всех критериев, не удовлетворяюш;их ус­ ловиям, наложенным ранее, предъявляются ЛПР. После этого ЛПР меняет веса и ограничения в любой последовательности до тех пор, пока процедура не даст ему приемлемого решения.

Если критериев мало (два-три), то данная процедура может быть достаточно удобной. Однако при возрастании числа крите­ риев для ЛПР становится все сложнее оценить влияние на по­ лучаемые решения каждого из весов и каждого из ограниче­ ний. Поэтому, вероятно, количество прямых ЧМП сравнительно невелико.

74

15.Процедуры оценки векторов

Воснове этих процедур лежит предположение, что ЛПР может непосредственно сравнивать решения, предъявляемые ему в виде векторов в критериальном пространстве, и система­ тически искать в этом пространстве наилучший вектор.

Рис. 19. Поиск решения в критериальном пространстве

Одной из наиболее известных ЧМП оценки векторрв явля­ ется процедура Дайера-Джиофриона (Д—Д) [10]. Она начинает­ ся с выбора какой-либо точки в критериальном пространстве (рис. 19). В этой точке ЛПР определяет градиент глобальной целевой функции. Один из критериев считается опорным. Бе­ рется небольшое изменение значения этого критерия (в сторону улучшения) от начального. Перед ЛПР ставятся вопросы типа: какое изменение по иному критерию эквивалентно заданному изменению опорного критерия? Ответы ЛПР определяют век­ тор (направление), вдоль^ которого изменение глобального критерия будет наиболее эффективным. Вдоль этого направле­ ния делается шаг определенной длины значения и получаются новые значения по всем критериям. Совокупность этих значе­ ний (вектор) предъявляется ЛПР вместе с первоначальным решением (соответствующим начальной точке). Далее перед ЛПР ставится вопрос: какое из решений лучше? Если лучше новое решение (назовем его Yi), то делается еще шаг вдоль этого же направления и вычисляется решение Уг. Далее Yi и Y2 предъявляются ЛПР. Если Y2 лучше, то делается еще шаг в прежнем направлении, и т. д. Если Y2 лучше, чем Yi , то в точке Y2 определяется новый градиент (направление) измене­ ния глобальной целевой функции (см. рис. 19), и т. д. Про-

75

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

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

16. Процедуры поиска удовлетворительных значений критериев

Эти процедуры также предназначены для систематического поиска наилучшего решения. Однако такой поиск осуществля­ ется по-иному: в порядке очереди определяется приемлемое значение по каждому из критериев.

Примером ЧМП поиска удовлетворительных значений кри­ териев служит процедура STEM - одна из первых ЧМП [11]. Она предназначена для решения многокритериальных задач линей­ ного программирования, одной из которых как раз и является многокритериальная транспортная задача (см.выше).

Рассмотрим фазы расчетов и анализа ЧМП STEM.

Фаза расчетов:

1. Проводится оптимизация по каждому критерию отдель­ но, при этом значения всех остальных критериев заносятся в табл. 4.

Т а б л и ц а 4

Относительные значения критериев

Критерии	Ci	Са	CN
Ci	1	С?	cr
Са	^2	1	с.^
CN	с'	С'	1

в	таблице	C'j - значение i-ro критерия при оптимиза­
ции	по j-му	критерию. Ясно, что диагональные элементы
равны	единице,	а все прочие меньше единицы. Очевидно, что
после	нормирования наибольшее значение каждого критерия

76

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

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

ний.
2. По табл. 4 вычисляются индексы критериев.
Пусть ai — среднее значение, взятое по всем элементам		i-ro
столбца (кроме единицы). Тогда	A,i (индекс i-ro критерия)	вы­
числяется из соотношений:
^=iZ^.;	У , = , .	(3)

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

Предположим, что все элементы i-ro столбца в табл. 4 близки к единице. Тогда среднее значение тоже близко к еди­ нице, (1- a j мало и соответствующий индекс мал. Действитель­ но, если при оптимизации по другим критериям значение дан­ ного критерия близко к наилучшему, то ему вряд ли стоит уде­ лять внимание. Наоборот, критерию, сильно зависящему от из­ менений других критериев (ai мало), должны соответствовать большие значения индекса. Индексы называют иногда техни­ ческими весами потому, что в отличие от весов wi они не назна­ чаются ЛПР, а вычисляются.

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

C.=ix,C,'	(4)
1-1

где A-i определяются из (3).

Решение, найденное при оптимизации, предъявляется ЛПР.

77

Фаза анализа:

1. ЛПР анализирует вектор значений критериев уь най­ денный при оптимизации по критерию (4). Затем ему задается вопрос: все ли компоненты вектора yi имеют удовлетворитель­ ные значения? Если да, то решение получено. Если нет, то ЛПР указывает один критерий с наименее удовлетворительным значением.

2. ЛПР просят назначить для критерия с наимейее удовле­ творительным значением пороговое значение !„ при достиже­ нии которого можно признать этот критерий имеюш;им удов­ летворительное значение:

С,>1,. (5)

Условие (5) добавляется к совокупности линейных равенств и неравенств, определяюш;их область D допустимых значений переменных. Таким образом, возникает уже новая область до­ пустимых значений.

На этом фаза анализа заканчивается. Следующий шаг на­ чинается с фазы расчетов при новой области допустимых зна­ чений и т.д. При достижении удовлетворительных для ЛПР значений по всем критериям ЧМП останавливается.

17. Пример применения метода STEM: как управлять персоналом

Французской консультативной фирмой SEMA предложена модель, характеризуюш;ая изменения со временем состава пер­ сонала большой организации и продуктивности ее работы [12]. Модель использовалась для прогнозирования последствий раз­ личных вариантов управления кадрами организации. Проверя­ лись разные стратегии приема на работу и повышения в долж­ ности через два, три и четыре года. В качестве переменных мо­ дели рассматривалось количество сотрудников, назначенных на различные должности в определенные периоды времени.

Использовались четыре критерия, представляющих собой линейные функции от переменных: обш;ее «удовлетворение* кадров (SA); фактическая эффективность работы кадров (EF); стоимость приема на работу дополнительных сотрудников (ЕВ); стоимость нехватки кадров по отношению к прогнозируемым потребностям (ЕС).

78

вмодель были заложены следующие зависимости:

•эффективность работы сотрудника линейно зависит от от­ ношения оценки его возможностей Q к оценке требований t, предъявляемых должностью к сотруднику;

•удовлетворение сотрудника во время пребывания на опреде­ ленной должности сначала возрастает до максимального зна­ чения, а затем со временем уменьшается до первоначального значения также в зависимости от отношения Q к t.

С математической точки зрения проблема представляла со­ бой задачу линейного программирования с четырьмя критерия­ ми качества, 350 переменными и 200 ограничениями. Не име­ лось никакой априорной информации о сравнительной важно­ сти критериев.

Для решения был использован метод STEM [11]. На первом этапе решения в области допустимых значений была осуществ­ лена оптимизация по каждому из критериев. Затем при помо­ щи линейного преобразования истинных значений критериев к значениям в интервале (0,1) (нормирования) был выполнен пе­ реход к относительным значениям критериев. Значения крите­ риев при поочередной оптимизации по каждому из них приве­ дены в табл. 5. Из рассмотрения таблицы можно сделать вывод о сильной зависимости критериев SA и EF и о противоречиво­ сти этих критериев и критериев ЕВ и ЕС; последние два проти­ воречивы также друг другу.

				Т а б л и ц а 5
Значения	критериев	при поочередной оптимизации
	по каждому из		них
Критерий	SA	EF	ЕВ	ЕС
SA	1	0,875	0,275	0,83
EF	0,86	1	0,09	0,765
ЕВ	0,131	0,149	1	0,4
ЕС	0,442	0,45	0,733	1

Далее на основе приведенной таблицы были определены на­ чальные индексы (технические веса) критериев. Пусть (аср)у — среднее по v-му столбцу значение всех элементов, кроме макси­ мального (равного 1). Определим

79

Индексы критериев находим из условия

tb Р' 1,

что позволяет получить:

Критерий	SA	EF	ЕВ	ЕС
X,	1 0,261	0,254	0,317	0,168

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

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

SA=0,965; EF=0,85; ЕВ=0,45; ЕС=0,675.

Для диалога с ЛПР значения по критериям ЕВ и ЕС были представлены в единицах стоимости. ЛПР предъявлялись: век­ тор zi максимальных значений, достигаемых при максимиза­ ции по каждому из критериев по отдельности, и вектор yi зна­ чений критериев, достигаемых при оптимизации по глобально­ му критерию с приведенными выше индексами:

zi={l; 1; -276; -157}; У1={0,965; 0,85; -1920; -1269}.

Перед ЛПР был поставлен вопрос: все ли компоненты вектора У1 имеют удовлетворительные значения? При ответе на этот во­ прос использовался вектор zi, компоненты которого представляли собой максимально возможные (недостижимые одновременно) значения компонентов вектора уь Руководитель определил зна­ чение по критерию ЕВ как наименее удовлетворительное и нашел нижний уровень по критерию ЕВ: -1000.

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

Критерий	ЕВ>—750	ЕВ>—1000	ЕВ>—1250	ЕВ>—1500
SA	0,67	0,78	0,84	0,90
EF	0,62	0,72	0,82	0,88
ЕС	-731	-157	-57	-157

80