Трахтенгерц Э.А. Компьютерная поддержка переговоров при согласовании управленческих решений

Подождите немного. Документ загружается.

Таблица 4.1

Разработка прикладных

программ

Отл.

Удовл.

Отл.

Хор.

Удовл.

Групповая работа в сетях

Хор.

Отл.

Научно-технические расче-

ты/ 2-мерные задачи САПР

Хор.

Удовл.

Отл.

Хор.

Удовл.

Настольные издательские

системы

Хор.

Отл.

Хор.

Отл.

Удовл.

Трехмерная графика

Удовл.

Хор.

Отл.

Удовл.

Автоматизация конторских

работ

Отл.

Хор.

Удовл.

Из определения Парето-оптимальности, данного в предыдущем разделе, следует

простой переборный алгоритм нахождения множества Парето-оптимальных элементов.

Поскольку Парето-оптимальность определяется не абсолютными, а относитель-

ными значениями оценок объектов (вариантов решений) по значениям их параметров,

то для реализации алгоритма достаточно иметь информацию о типе отношений между

каждой парой объектов, т.е. существует ли между ними отношение строгого предпоч-

тения или нет. Поэтому введем булеву переменную









случае,противномв0

j;объектаельнеепредпочтитстрогоiобъектесли,1

и построим квадратную матрицу, элементами которой являются переменные a

. Из оп-

ределения следует, что единицы в i-ой строке определяют элементы j, по отношению к

которым элемент i строго предпочтительнее. Поэтому, если в j-м столбце все нули, то

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

надлежит множеству Парето-оптимальности.

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

 одно или несколько значений параметров элемента i лучше (это может быть

либо больше либо меньше) значений параметров элемента j, а остальные равны. В этом

случае

1

;

 одно или несколько значений параметров элемента i хуже значений парамет-

ров элемента j. Тогда независимо от значений других параметров

0

;

 значение всех параметров элемента i равно значениям соответствующих па-

раметров элемента j. При таком равенстве

0

Если сравнивать исследуемые 6 вычислительных систем по всем 6 показателям с

использованием рассмотренного выше алгоритма, то получим табл. 4.2, из которой

видно, что Парето-оптимальными являются четыре системы. (Это оценки для первого

руководителя).

Такое большое число несравнимых систем объясняется большим количеством

показателей (то же 6, но это случайное совпадение). Если сократить число показателей,

например, отказаться от показателя «трехмерная графика» (во многих приложениях ее

не используют), то окажется, что система Compaq Deskpro 5/66 Model 5/0 предпочти-

тельнее Apple Macintosh 800. Если не учитывать другие показатели, то может оказаться,

что предпочтительность систем изменится.

Таблица 4.2

На табл. 4.3 показано предпочтение перечисленных выше вычислительных сис-

тем по первым трем показателям, которое важно для второго руководителя (его интере-

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

Сравнение систем выглядит гораздо более содержательно, чем на табл. 4.2, Парето-

оптимальными являются только системы 3 и 5.

Таблица 4.3

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

дителя (его интересовали трехмерная графика, настольные издательские системы и ав-

томатизация конторских работ). Такими системами оказались система 1, 2 и 5.

Таблица 4.4

Таким образом, для первого руководителя предпочтительными (Парето-

оптимальными) являются системы 1, 2, 3, 5, для второго 3, 5 и для третьего 1, 2, 5. По-

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

телями могут быть рассмотрены системы 3 и 5, первым и третьим – системы 1, 2 и 5, а

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

зная требования руководителей, нашла для каждого Парето-оптимальное решение и

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

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

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

вых предложений СПП. Тем не менее, во всех случаях применение Парето-

оптимальности в качестве стартовых условий переговоров достаточно сильно сокраща-

ет поле выбора договаривающихся сторон, облегчая процесс согласования.

Заметим, что при ранжировании по векторному критерию важно бывает опреде-

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

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

средним числом наиболее предпочтительных объектов.

4.1.3. Поиск начальных условий при непрерывных переменных,

одинаковых «весах» критериев и функциях предпочтения

Часто встречающейся задачей при согласовании решений является задача о раз-

делении ресурсов между подразделениями одной организации.

Ниже приводится математическая постановка задачи нахождения первого Паре-

то-оптимального предложения при переговорах о разделении ресурсов [4.4].

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

пример, затраты каждого i-го подразделения через x

, а общие затраты через





Общий механизм распределения ресурса опишем формулой:







iii

nig

,1),1(

где S

–часть ресурса, получаемого i-м подразделением, функция g

–определена на

(x/X), непрерывна и дважды дифференцируема. Эта формула интересна тем, что при





в зависимости от характера функции g

получаем разные схемы разделения

ресурса S:

 если

nXxXxg

jjjj

,1),/()/( 

, тогда

)/( XxS



– схема пропорцио-

нального разделения;

 если

nbXxg

jjj

,1,0)/( 

, тогда

)/1( nS



– схема равного разделе-

ния;

 если

),/)(1()/( XxaXxg

jjj



10  a

, тогда

)/()/)(1( naXxaS



–

схема разделения Сена [4.5].

Функция g

обладает следующими свойствами:

1).

1'0 

2).

0'' 

, g

(0)=0.

Ниже приводится пример такой функции и ее свойства:

0)0(,)/()/(

2/1



iiii

gXxXxg

0)/(4/1,0)/(2/1

2/3''2/1'





XxgXxg

1)/1()/()/1()/(

1 1 1 1

2/1

















   

   

nXxnXxS

Пусть функции полезности U

каждого члена группы идентичны и описываются

часто применяемой формулой [4.7], несмотря на жесткое требование к ней:

)(

iiii

xVFSU 

где V

() дважды дифференцируемая, выпуклая и возрастающая по x

, характеризующая

i-го участника производства, а F – функция производительности всех участников счи-

тается дважды дифференцируемой, строго возрастающей и квазивогнутой. Таким обра-

зом, на функции F и V

() накладывается ряд ограничений.

Парето-оптимальная продуктивность (совместная производительность) достига-

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

стных усилий. Совместная производительность определяется соотношением:

 

 



iii

xVFUW

1 1

)(

Парето-эффективность достигается при выполнении условий:

nixVF

,1,0)('



Решения этих уравнений образует множество

nix

,1*}{ 

максимальных значе-

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

соответствии с видом функции g

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

тается более предпочтительным) определяются Парето-оптимальные значения S

. Это

множество и может стать основой для первого предложения согласования значений x

(предлагаемых затрат и долей получаемого ресурса каждым участником перегово-

ров).

4.1.4. Поиск начальных условий при непрерывных переменных,

различных «весах» критериев и функциях предпочтения

Теперь рассмотрим случаи, когда у партнеров по переговорам разные функции

предпочтения и разные «веса» критериев [4.6].

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

теризующие эти параметры, непрерывны. Значения i-го параметра обозначим через x

вектор решения через

Xxxx

 ),...,(

. Множество X считается компактным и вы-

пуклым подмножеством R

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

},1,0)

(

{ pjxgRxX



где

pjRRg

,1,: 

– выпуклая функция. Обозначим конечную и строго вогну-

тую функцию предпочтения i-го партнера через

RRxU

:)

(

, W

– «вес» i-ой функ-

ции, целевую функцию представим хорошо известной формулой:







xUW

max)

(

(4.1)

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

pjxg

,1,0)

( 

,,1,0 niW







В работе[4.6] показано, что все Парето-оптимальные решения могут быть полу-

чены из (4.1), если функция полезности строго вогнутая.

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

ограничений на характер функций и вектор решений.

Формулу (4.1) можно представить в другом виде, вводя векторы переменных

для каждого партнера по переговорам:







xUW

,...,

max)

(

(4.2)

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

,1,1,0





nixx

pjxg

,1,0)

( 

ni ,1

Задача:

,...,

min)

,...,

(







, (4.3)

где функция

)(

определяется соотношением:















 









niiTii

XxxxxyxUWyy

,...,

)

()

(max)

,...,

(

(4.4)

является дуальной задаче (4.2).

Здесь

Ryy 

11

,...,

– векторы множителей Лагранжа, соответствующие огра-

ничениям (4.2).

Поскольку U

ni ,1

вогнута,

pjg

,1, 

– выпуклая и X не пусто, для задачи

4.2 существует вектор Куна-Такера [4.7] и оптимальное значение прямой и обратной

задач совпадают [4.8].

Целевая функция (4.4) может быть адидивно декомпозирована по i. Кроме того,

существует только одно сепаратное ограничение для каждого партнера, поэтому задача

(4) может быть сведена к решению n независимых оптимизационных задач.

iTii

xyxUW

max

)

()

( 

(4.5)

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

pjxg

,1,0)

( 

















n.iесли,

1;-n2,...,iесли,

1;iесли,

(4.6)

Для нахождения общего Парето-оптимального решения используется градиент-

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

большого числа обращений к экспертам. На каждой итерации делается шаг в направле-

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

следующего шага.

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

ло. Размер шага определяется по значению направленной производной дуальной функ-

ции. Так если

 

TnT

kykyky )(

...)(

)(

11 



является k-ой текущей итерацией и направле-

ние поиска линии

))(()( kykS 

, тогда направленная производная d как функция от

величины шага

0

определяется уравнением:

 

)(

)()(

)(

kSky





Из выпуклости и дифференцируемости дуальной функции следует, что значение

направленной производной равно нулю, когда размер шага

*

оптимален, т.е.

*

При значениях

*

0)( d

, а при

*

0)( d

. Это означает, что, если размер

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

уменьшается, а во втором увеличивается,. То есть, если размер шага выбран так, что

0)( d

, то величина дуальной функции гарантированно не возрастает.

Величину ошибки, при которой вычисления прекращаются можно оценить со-

отношением:

 







xkyx

nkh

)(

/1)(

где

 





kyx

)(

меньше, чем заранее заданная величина

0

. Если

)(kh

про-

цедура заканчивается.

В [4.6] описан алгоритм решения, который здесь приводить не будем, а рассмот-

рим простой пример, показывающий возможность использования множества Парето,

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

Пусть у двух переговорщиков функции предпочтения (полезностей) разные и

имеют вид:

2.04)(

exxxxxU 

)1)(1()1(4)1(5.0)(

 xxxxxU

Ограничения заданы неравенствами:

.0364

;0568

;0542







Решения показаны в табл. 4.5 и на рис. 4.5. В первом столбце табл. 4.5 показаны

«веса», назначенные первым и вторым участниками переговоров, при которых получе-

но оптимальное решение, указанное во втором столбце.

На рис. 4.5 соответствующие значения Парето-оптимальных параметров поме-

чены «весами», которые назначили каждому параметру участники переговоров.

Рис. 4.5

Таким образом, система поддержки переговоров показывает Парето-

оптимальные значения параметров x

и x

при различных «весах» каждого параметра. В

нашем примере СПП показывает участникам переговоров, как меняются значения x

в зависимости от «весов» параметров. Каждый участник переговоров, исходя из сво-

0.4

0.5

0.6

0.7

0.8

0.9

1.1

0.2

0.4

0.6

0.8

1611 /,

811 /,

411 /,

811 /,

1,1

3211 /,

1,2

1,4

1,8

1,16

1,32

их представлений, может выбрать для первого предложения свою область Парето-

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

пересечения выбранных областей, сужая эти области.

Таблица 4.5

«Веса»

параметров

Парето-оптимальные значения параметров

0.283

0.456

0.272

0.471

0.240

0.513

0.207

0.557

0.157

0.627

0.237

0.801

0.314

0.917

0.416

0.993

0.500

0.994

0.561

0.969

0.599

0.951

4.1.5. Эвристический алгоритм нахождения начальных

Парето-оптимальных условий в СПП RAMONA

В эвристическом алгоритме нахождения Парето-оптимальных стартовых усло-

вий [4.9] для простоты предположим, что существуют только два параметра А и В, зна-

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

хочет максимизировать значения параметров, а другая – минимизировать. То есть иде-

альная точка для одной стороны (1, 1), а для другой (0, 0) (рис. 4.6). Поскольку очень

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

система поддержки переговоров RAMONA (Resource Allocating Multiple Objective Ne-

gotiation Approach) решает задачу нахождения области Парето двумя методами, ис-

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

Парето-оптимальных точек.

Сначала система RAMONA строит пути предпочтения каждой стороны (рис.

4.6). В области, показанной на рис. 4.6 ранее уже определялись две точки предпочтения

(1, 1) и (0, 0). Система вводит искусственные ограничения типа:

a + b =0.5,

a + b =1,

a + b =1.5,

показывает их на дисплее в виде прямых (см. рис. 4.6) и просит указать свои предпоч-

тения на этих прямых. На рис. 4.6 координаты параметров предпочтений обозначены

точками для первой группы и квадратиками для второй. После этого система строит

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

диться в пространстве, ограниченном путями предпочтения. Цель этого этапа – сокра-

щение числа итераций при определении возможной Парето-оптимальной области и ее

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

Рис. 4.6

Здесь надо заметить, что этот метод нахождения Парето-оптимальных точек для

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

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

ваться этим методом становится сложнее.

Второй метод использует более «строгие» подходы, в нем задаются реальные

ограничения вида:





ijkij

bxP

,...2,1,2,1  jk

, (4.7)

где P

– «вес» i-го параметра (

ni ,1

), а x

ijk

– его значения на итерации

,...)2,1( jj

для

участника

)2,1( kk

. Заметим, что в нашем случае ограничение для всех участников

переговоров одно и тоже.

Проведем плоскости, проходящие через точки (0.25, 0.25,…, 0.25), (0.50, 0.50,…,

0.50) и (0.75, 0.75,…, 0.75), которые назовем опорными и обозначим через V

, V

соответственно. Эти опорные точки считаются всегда достижимыми. Тогда ограниче-

ния (4.7) запишутся в виде:





bVP





bVP





bVP

,...2,1j

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

. Направ-

ление поиска может осуществляться разными методами, например, в помощью эври-

стики, показанной в табл. 4.6.

Эвристика базируется на предсказуемых изменениях: если максимизирующая

сторона увеличивает свои предложения больше, чем минимизирующая, то «веса» кри-

териев будут расти, если максимизирующая сторона снижает свои предложения мень-

ше, чем минимизирующая, то «веса» критериев будут уменьшаться.

Первоначально все «веса» критериев полагают равным единице. Затем вычис-

ляются значения:

12111

max

iii

xxD 

ni ,1

Путь предпочтения первой

группы

Путь предпочтения

второй группы

Параметр А

Параметр В

определяющее разность между значениями x

ijk

каждого участника переговоров по i-му

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

Таблица 4.6

Изменение

Цель эксперта

pijk

Vx 

(p=0.25, 0.50,0.75)

ijk

возрастает

уменьшается

да

уменьшается

возрастает

Максимизация

нет

изменение

в обе стороны

неизвестно

возрастает

нет

уменьшается

Минимизация

да

изменение

в обе стороны

неизвестно

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

Dmax

. В табл. 4.7 столбец «процент несогласованности» является индикатором раз-

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

и величиной не-

согласованности. Если D

меньше 0.03 итерации прекращаются и считается, что сторо-

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

которая дает максимум ожидаемого каждой стороне, а поэтому и считается Парето-

оптимальной. В противном случае (D

 0.03) ищутся новые значения по формуле:



















iii

DDP

2112

)2//(1

где



=Z*H (см. табл. 4.7 и 4.8), определяются изменения шага в зависимости от вели-

чины несогласованности и изменения шага. Величина изменения шага, показанная в

табл. 4.8, в свою очередь, зависит от числа параметров решаемой задачи.

Таблица 4.7

Максимум D

% несогласованности (Z)

> 0.5

100

0.25 < D

 0.5

0.125 < D

 0.25

0.05 < D

 0.125

0.03 < D

 0.05

Таблица 4.8

Число параметров

Величина изменения шага (H)

0.333

0.6

0.666

0.714

0.75

0.777

Значения в табл. 7 и 8 получены путем интенсивного моделирования и тестиро-

вания результатов моделирования. Теоретического обоснования этих таблиц нет. Необ-

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

8 были получены для решения вполне конкретной задачи и для других приложений мо-

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

вые таблицы.

Вернемся к алгоритму. Если D

i(j-1)

> 0.03 определяются новые значения D

и их

разности (сравниваются текущая и предыдущая итерации) находятся из соотношения:

)1()2( 



jijiij

DDDD

ni ,1

, j=3,4,…

Аналогично находятся разности «весов» параметров:

)1()2( 



jijiij

PPPP

ni ,1

, j=3,4,…

Эти оценки нужны для определения отношений и изменений «весов» парамет-

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

ijijij

PPDDCP /

ni ,1

ijjiij

CPDSP /

)1( 



ni ,1

Общее изменение «весов» параметров для каждой текущей итерации определя-

ется из соотношения:







ijj

Кроме этого отдельно определяются суммы положительных и отрицательных







SPi

SPPos

для SP

>0,







SPi

SPNeg

для SP

<0.

Наконец, «веса» параметров критериев для каждой новой j-ой итерации опреде-

ляются следующим образом:















































.0для*

,0для*

)1(

ijj

Neg

Pos

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

первого предложения на переговорах.

Эта методика была использована при согласовании бюджетной политики прави-

тельства Финляндии с сельскохозяйственными союзами (МТК) (общественными орга-

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

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

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

поддержки многие небольшие фермы будут убыточны и фермеры не выдержат конку-

ренции. (Одна из причин такого положения – климат Финляндии, другая – малый раз-

мер ферм). Естественно, что предложения правительства Финляндии и МТК не совпа-

дали. Согласование решения было предложено проводить по трем критериям: уровень

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

Диапазон на 1955 г. начальных значений параметров показан в табл. 4.9.