Содержание к диссертации
Введение
Глава 1. Сравнительный анализ походов к моделированию процесса ведения переговоров 13
1.1. Переговоры как динамический процесс взаимодействия экономических агентов 13
1.2. Классические подходы моделированию переговорного процесса 16
1.3. Ограничения применения классического подхода 32
1.4. Когнитивный подход 35
1.5. Дескриптивный подход: интегративный и разделенный типы переговоров 39
1.6. Метод принципиальных переговоров и концепция процедуры одного текста 45
1.7. Моделирование переговоров SNT-типа 50
1.8. Выводы к главе 1 57
Глава 2. Метод регулярного симплексного поиска переговорного компромисса в пространстве предложений 59
2.1. Постановка задачи оптимизации функции полезности ЛПР 59
2.2. Элементы теории оптимизации 60
2.2.1. Постановка задачи оптимизации и классификация 60
2.2.3. Алгоритмы прямого поиска 66
2.3. Метод регулярного симплексного поиска 71
2.3.1. Пространства предложений и совместных полезностей 72
2.3.2. Алгоритм метода симплексного поиска в пространстве предложений 78
2.4. Точность локализации точки компромисса 84
2.5. Вопросы повышения точности и выбора значений параметров 92
2.6. Выводы к главе 2 95
Глава 3. Численные испытания метода для случая неоклассических функций полезности 96
3.1. Описание параметров численного эксперимента 96
3.2. Методика проведения численных исследований, результаты и их интерпретация 97
3.2.1. Режимы работы алгоритма 97
3.2.2. Иллюстрация и результаты работы алгоритма в типичном режиме 99
3.3. Аппроксимация границы Парето 102
3.5. Сравнение трудоемкости метода симплексного поиска и метода улучшающих направлений 103
3.6. Экономическая интерпретация результатов и сравнение эффективности переговорных схем 107
3.7. Выводы к главе 3 114
Заключение 124
Список литературы
- Классические подходы моделированию переговорного процесса
- Дескриптивный подход: интегративный и разделенный типы переговоров
- Постановка задачи оптимизации и классификация
- Иллюстрация и результаты работы алгоритма в типичном режиме
Введение к работе
Актуальность проблемы. Теория трансакционных издержек является одной из основ неоинституционального подхода в современной экономической науке. Понятие трансакционных издержек впервые ввел известный американский экономист Р.Коуз в тридцатых годах прошлого столетия. В своей работе «Природа фирмы» [22] он объяснял существование фирмы как иерархической структуры, противоположной рынку и имеющей целью своей деятельности минимизацию трансакционных издержек. В дальнейшем формулировка Коуза подверглась многочисленным модификациям, однако понятие трансакционных издержек прочно утвердилось в экономической теории и к настоящему моменту приобрело огромную значимость.
Среди ученых, развивавших подход трансакционной экономики, можно назвать имена А. Алчиана, И. Барцеля, Г. Демсеца, Д. Норта, У. Меклинга, О.Уильямсона, С. Чена и других. Базовой категорией в данном подходе является трансакция - акт взаимодействия экономических агентов [19, 23, 35, 36]. Под трансакцией в современной неоинституциональной экономике понимается обмен товарами, различными видами деятельности или юридическими обязательствами, долговременные или краткосрочные сделки и т.п. При этом полагается, что любая трансакция требует детализированного документального оформления и предполагает простое взаимопонимание сторон [17,19]. Издержки по осуществлению трансакций в неоинституциализме являются основным фактором, определяющим структуру и динамику развития различных институтов общества. Значение трансакционных издержек возрастает в процессе экономического развития. Согласно анализу экономики США, проведенного Дж.Уоллисом и Д. Нортом [95], доля в ВВП США трансакционных услуг, оказываемых частным
сектором, в период с 1870 по 1970 г. увеличилась с 23% до 41%,
оказываемых государством - с 3,6% до 13,9%. Итоговый рост в указанном
4$ периоде 1870-1970 гг. составил с 26,6% до 54,9%. В литературе встречаются
различные классификации трансакционных издержек, и часто выделяются пять основных форм [19, 65, 68, 76,91,96]:
Y>
издержки поиска информации или поиска партнера трансакции (затраты времени и ресурсов на получение информации о текущей рыночной ситуации и ее анализ);
издержки ведения переговоров;
издержки измерения количества и качества вступающих в обмен товаров и услуг;
издержки по спецификации и защите прав собственности (затраты на содержание судов, арбитража, органов государственного управления, и расходы по восстановлению нарушенных прав);
издержки недобросовестного поведения партнера (поведения, нарушающего условия контракта и/или направленное на получение односторонних выгод).
^ В рыночной экономике расходы на ведение переговорного процесса
составляют неотъемлемую часть трансакционных издержек деятельности любого экономического агента. Действительно, практически любой сделке предшествуют переговоры об условиях экономического обмена. Заключение и документальное оформление контрактов также требует расходования значительных средств. Основной существующий способ экономии издержек указанного рода - это использование типовых договоров. Однако на этапе согласования сторонами условий контракта или сделки подобные стандартные решения оказываются малопригодными. Переговоры как процесс согласования интересов участников и разрешения потенциального или реального их конфликта, являются актуальным объектом исследования
многих научных дисциплин: психологии, социологии, политологии, экономики, теории управления и др.
На протяжении последних десятилетий наблюдается постоянный рост интереса к исследованию переговоров. Первые работы в этой области появились в США. Отечественные исследования начались в середине восьмидесятых годов прошлого века и касались в основном международной и внешнеполитической проблематики, поскольку они проводились в тот период преимущественно в МГИМО и в Институте США и Канады АН СССР [59, 61]. Полученные результаты малоприменимы для процесса переговоров между экономическими агентами, допустим, между двумя фирмами, причем не только из-за кардинальных изменений, произошедших с тех пор в экономике и обществе. Современные микроэкономические ситуации, требующие разрешения с помощью переговоров, характеризуются меньшим масштабом и иными способами достижения целей сторон, чем международные. В начале 90-х годов XX века качественно новых исследований в России практически не проводилось, лишь в рамках конфликтологии появился интерес к национальным особенностям ведения переговорного процесса [3,4, 37].
Переговоры представляют собой сложный динамический процесс
взаимодействия людей, на ход которого оказывают влияние множество
социологических, социально-психологических, экономических,
культурологических и прочих факторов. Математическое моделирование как один из методов исследования присутствует в научных подходах указанных выше дисциплин, занимающихся проблемой переговоров.
Первые попытки формализации переговоров были предприняты в моделях теории игр [82, 84, 85] (торг по Нэшу, модель Рубинштейна и др.). В их основе, как и большинства классических теоретико-игровых моделей, лежало предположение о полном рационализме участников переговоров. При данных предположениях были построены и исследованы множество
моделей, получены условия достижимости и свойства равновесных решений.
Однако практическая применимость полученных результатов была сильно
у. ограничена в виду следующих моментов. Условие полного рационализма
участников на практике часто нарушается, что подтверждается многими исследованиями психологии принятия человеком решений, а также работами в области экспериментальной экономики. Кроме того, теоретико-игровые стратегии поведения учитывали, по сути, только влияние действий экономических агентов на стратегию противника, т.е. не учитывалось влияние контекста переговорной проблемы. Под контекстом проблемы понимается совокупность причин конфликта, разрешаемого при помощи
4> переговоров, относительным положением (состоянием) сторон, опыта
ведения ими переговоров и т.п. Представляются некорректными попытки поиска в рамках теории игр универсальных равновесий и стратегий для любых переговорных ситуаций, поэтому учет контекста в моделях очень важен. На практике стратегия поведения на переговорах, кроме действий оппонента и собственных интересов, определяется множеством различных факторов: информированность о намерениях противника, структура взаимной информированности участников, ограниченность времени для принятия решении, и очень часто - психологическое влияние непосредственно в ходе деловой беседы.
Метод принципиальных переговоров, разработанный под руководством Р. Фишера и У. Юри в рамках Гарвардского проекта по переговорам (Harvard Negotiation Project [101]), состоит в подходе к разрешению конфликта на основе его качественных свойств. Главное внимание в подходе уделяется анализу сути (т.е. структуре и контексту)
V) проблемы. Single negotiation text (SNT) или процедура одного текста -
специальный случай метода принципиальных переговоров, также разработанный этими исследователями [54, 58]. Целью процедуры является поддержание процесса в русле принципиальных переговоров и упрощение
процесса в целом. Принцип к настоящему времени детально проработан и хорошо зарекомендовал себя в переговорной практике благодаря тому, что он совмещает учет контекста переговорной проблемы с принципом поиска выгоды одновременно для обоих участников. Основной идеей, позволяющей уйти от неэффективного торга относительно позиций, является привлечение независимой третьей стороны (медиатора), которая регулирует процесс взаимодействия остальных. Ввиду этого особенно актуальной явилось создание инструментальных и аналитических методов поддержки для медиации переговорных процессов. Эти методы преимущественно являются интерактивными и существенно используют информацию о проблеме, которую получают от взаимодействующих с ними участников переговоров. При SNT-подходе наилучшим результатом применения подобных методов является достижение компромисса, оптимального по Парето1. Оптимальные по Парето решения считаются в широком смысле «хорошими» для многих прикладных задач в экономике [1, 12, 46, 55, 82].
Анализ проблематики исследований позволяет утверждать, что возникает необходимость развития методов моделирования переговорных процессов, учитывающих контекст проблемы и индивидуальные характеристики участников. Отсутствуют в экономической литературе практические рекомендации по оптимизации переговорных схем на основе анализа переговорной ситуации, учитывающих упомянутые выше факторы (исключение составляют рекомендации по методам психологического воздействия на оппонента в ходе деловой беседы).
Таким образом, актуальной экономической проблемой является разработка экономико-математической модели и инструментальных средств поддержки, позволяющих анализировать ситуацию на переговорах,
1 Переговорное соглашение называется оптимальным по Парето, если изменение этого соглашения с целью увеличения полезности какого-либо участника возможно только за счет уменьшения полезности остальных.
^
способствовать скорейшему достижению Парето-оптимальных компромиссов и тем самым снижать издержки участников. В связи с изложенным был определен выбор темы, цель и задачи диссертации.
Целью диссертационного исследования является разработка методики поддержки переговорного процесса, сокращающей трансакционные издержки субъектов-участников.
Для реализации цели в работе поставлены и решены следующие задачи:
І/
анализ процессов взаимодействия между экономическими агентами при ведении двусторонних переговоров;
анализ существующих моделей переговорных процессов, методов их формализации и средств поддержки;
обоснование применения методов, основанных на процедуре одного текста, к решению задачи снижения переговорных издержек;
разработка метода симплексного поиска в пространстве предложений переговорного компромисса, оптимального по Парето;
разработка алгоритма и реализация компьютерной программы, моделирующей переговорный процесс по методу симплексного поиска;
выявление и описание влияния параметров метода симплексного поиска на основной экономический критерий задачи - уменьшение переговорных издержек.
Объектом исследования являются экономические агенты в качестве участников двустороннего переговорного процесса.
Предметом исследования являются средства и методы
формализованного представления, экономико-математического
Ч) моделирования и поддержки переговорных процессов.
Теоретическая и методическая основа исследования. Теоретической и методологической базой диссертационной работы являются научные труды
отечественных ученых МГУ им. М.В.Ломоносова, МГИМО, Института проблем управления им. Трапезникова РАН в областях анализа переговорных процессов, принятия решений в условиях неопределенности, исследования трансакционных механизмов в современной экономике. В диссертации также использованы разработки зарубежных ученых, выполненные в рамках переговорных проектов в Университете Карлетон (Канада), Гарвардском юридическом факультете (США), Технологическом университете Хельсинки (Финляндия).
В ходе исследования применялись методы переговорного анализа, конфликтологии, теории игр, теории принятия решений и теории оптимизации. Для программной реализации и численных испытаний использованы инструментальные средства разработки и компьютерного анализа данных: Borland C++ Builder, Origin, Maple.
Работа выполнена в соответствии с пунктом 1.2 Паспорта специальности 08.00.13 - Математические и инструментальные методы экономики.
Научная новизна диссертационного исследования заключается в разработке и научном обосновании методики поддержки переговорного процесса на основе регулярного симплексного поиска компромисса.
В результате исследования были получены и выносятся на защиту следующие научные результаты:
применение принципа процедуры одного текста для задачи
уменьшения трансакционных издержек участников переговоров;
разработка методики поддержки переговорного процесса, основанной
на методе симплексного поиска компромисса и позволяющей уменьшить трансакционные издержки участников при любых выпуклых функциях полезности;
разработка комплекса инструментальных средств поддержки процесса
в рамках предложенной модели переговоров. В частности, методика
позволяет находить множество возможных переговорных соглашений,
оптимальных по Парето при данных переговорных условиях; . разработанный инструмент, в отличие от классических методик,
позволяет работать с предпочтениями ЛПР без построения его
функции полезности в явном виде.
Практическая значимость диссертационной работы заключаются в том, что ее основные положения, результаты и разработанные методики ориентированы на широкое использование на практике при оптимизации процесса переговоров между экономическими субъектами по заключению договоров, контрактов, сделок.
Самостоятельное практическое значение имеют:
значительное ускорение переговорного процесса и снижение трансакционных издержек;
алгоритм программы и инструментальное средство, реализующее взаимодействие участников переговоров по предложенной методике;
особенность метода работать без построения функции полезности участников в явном виде;
рекомендации аналитику-медиатору по выбору режимов и значений параметров алгоритма, позволяющие за счет учета особенностей конкретных переговорных ситуаций повысить эффективность методики.
Апробация и внедрение результатов. Основные положения диссертационного исследования докладывались второй международной школе-семинаре "Science Online: электронные информационные ресурсы для науки и образования" (22-29 ноября 2003 г., г. Хургада, Египет); на постоянно действующем научно-методическом семинаре кафедры математического моделирования экономических процессов Финансовой
академии при Правительстве Российской Федерации.
Полученные теоретические и методологические результаты используются в учебном процессе при преподавании дисциплины «Экономико-математическое моделирование» на кафедре математического моделирования экономических процессов Финансовой академии при Правительстве Российской Федерации.
Публикации. Основные положения диссертационного исследования нашли отражение в 4 публикациях общим объемом 2,16 п.л., все авторские.
Структура и содержание работы обусловлены логикой, целью и задачами проведенного исследования. Работа включает введение, три главы, 23 рисунка, 4 таблицы, заключение, список использованной литературы из 103 наименований, 5 приложений.
Классические подходы моделированию переговорного процесса
Что означает термин «переговоры» (англ. - negotiations) В книге «Управление переговорами», выпущенной в США, дается следующее определение: "переговоры - это процесс, в ходе которого участники конфликта пытаются разрешить его с помощью соглашения" [73]. В этом довольно общем утверждении выделен важный момент, а именно: переговоры рассматриваются как один из основных способов разрешения или управления конфликтами. Подобное определение можно часто встретить в литературе по конфликтологии [3, 4, 27, 37] - относительно новой дисциплины, сформировавшейся к середине XX века на пересечении таких, казалось бы, далеких друг от друга наук как психология, социология, правоведение, экономическая теория, теория управления, математика и других.
г ) В ряде работ производится уточнение понятия переговоров. Так, в [28] переговоры определяются как совместная с партнерами деятельность, основанная на отношениях в системе «субъект-субъект» (в отличие от отношений в системе «субъект-объект», характерных, например, для диспетчерской, конструкторской и других видов деятельности). То есть, несмотря на расхождения в целях, интересах и намерениях между сторонами-участниками переговоров, деятельность на переговорах обязательно совместная. Кроме того, предполагается существование некоторой степени взаимозависимости между сторонами, которая и позволяет прийти к соглашению, поскольку бездействие или борьба только за свои интересы не приносит участникам выгоды [31].
Наиболее полное, синтезированное из перечисленных выше и дополненное, определение приводится в [56]: "переговоры - процесс взаимодействия социальных объектов или их представителей в форме прямого или опосредствованного диалога, предполагающего согласование интересов и (или) направленного нейтрализацию потенциального или регулирование (разрешение) реального конфликта".
Переговоры представляют собой сложный динамический процесс взаимодействия людей, на ход которого оказывают влияние множество социологических, социально-психологических, экономических, культурологических и прочих факторов, многие из которых трудно выражаемы в количественном отношении.
Переговорный процесс с экономической точки зрения может быть рассмотрен в виде задачи взаимодействия двух экономических агентов с целью оптимального перераспределения благ2 между участниками переговоров. Предполагается, что число благ конечно, количество каждого блага ограничено и лежит в некотором интервале значений. Агенты делают свой выбор из множества альтернатив в соответствии с заданной моделью принятия экономических решений. Например, это может быть гипотеза максимизации ожидаемой полезности [34] или одна из моделей ограниченной рациональности [26, 63], теории проспектов [36, 69, 78] и т.п. Каждый из агентов стремится к такому распределению благ, которое является наилучшим для него в смысле выбранного им критерия. От задачи оптимизации для отдельного агента рассматриваемая ситуация отличается тем, что агентам приходится некоторым способом учитывать предпочтения другого участника переговоров. Решение поставленной таким образом задачи можно искать в виде компромисса, который одновременно оптимизировал бы частные критерии агентов и удовлетворял принципу согласования их предпочтений. Решение может не существовать или быть неединственным, как будет показано далее. В более широком смысле решением можно считать нахождение в том или ином смысле устойчивых стратегий поведения агентов, при которых достигается компромисс.
Для обеспечения достижения целей, поставленных настоящим исследованием, определим переговоры как процесс двустороннего взаимодействия экономических агентов, в ходе которого участниками ищется такое распределение переговорных ресурсов, которое оптимизирует критерии каждого агента и одновременно удовлетворяет некоторому принципу согласования их интересов.
Из вышесказанного следует, что способ согласования предпочтений должен быть приемлемым для обоих участников. Кроме того, условие его выполнения в любом раунде переговоров является необходимым для перехода к следующему раунду, поэтому этот принцип должен быть определен сторонами до начала переговорного процесса. Такая постановка задачи отражает основное назначение любых переговоров - разрешение конфликта путем согласования интересов, и именно эта задача далее будет формализована и решена.
Введенное таким образом понятие переговоров как взаимодействия экономических агентов должно быть дополнено двумя важными моментами. Во-первых, это критерий окончания процесса. Переговоры завершаются с положительным результатом, если достигается компромисс интересов в указанном выше смысле. Доказательство несуществования такого компромисса на практике затруднено, поэтому неудачное завершение переговоров обычно соотвествует достижению определенных граничных условий процесса.
Дескриптивный подход: интегративный и разделенный типы переговоров
Проблема учета контекста конфликта имеет много общего с широко обсуждаемой в современных иностранных публикациях дихотомией разделенных и интегративных типов переговоров (distributive and integrative negotiations) [58, 66, 88, 94]. Такую классификацию переговоров ввели в 1965 году Walton and McKersie на основе дескриптивного (качественного) подхода к проблеме [80]. Проведенные ими лабораторные исследования были ориентированы на изучение качественных отличий между различными типами переговорных процессов, особенностей восприятия и предпочтения участников, анализ поведения сторон. Изначально типы предполагались равнозначными, но со временем в публикациях интегративный тип стал преобладать как «лучший» из двух, поскольку в его основе лежат концепции типа «выигрыш-выигрыш», создание стоимости (value creation) и т.п.
В теоретико-игровом подходе, являющимся нормативным (формальным), указанные типы переговоров в простейшем случае могут быть представлены как игры с нулевой и ненулевой суммой выигрыша соответственно. Указанные выше ограничения в применении игровых моделей, а также развитие многокритериальных методов принятия решений и методов интерактивного взаимодействия привели к появлению отдельного направления в моделировании переговоров - переговорного анализа (negotiation analysis). Основная задача, постулируемая в переговорном анализе, заключается в преодолении разрыва между формальным нормативным и качественным дескриптивным подходами [97]. Решения в основном ищутся путем совместного применения методов теории принятия решений и теории игр.
В работе [80] рассмотрены вопросы, связанные с особенностями и различиями в моделировании переговоров разделенного и интегративного типов. Представим переговоры как процесс взаимодействия между двумя сторонами, обозначим их А и В. Каждая сторона имеет три основные характеристики: предложения, цели и функцию полезности. Множество всех допустимых предложений (альтернатив выбора) обозначим X, X с R". Предполагается, что множество X — конечное и выпуклое. Размерность X определяется количеством вопросов п, обсуждаемых в ходе любого раунда переговоров, набор конкретных значений которых определяет каждое предложение. Например, в переговорном процессе о поставке некоторого товара набор из четырех величин д: = {цена; гарантийный срок; способ оплаты; время поставки) после присвоения им значений будет рассматриваться как некоторое предложение, при этом п=4, X с R , х є X. Заметим, что величины не обязательно должны быть только числовыми. Так, в приведенном примере величина способ оплаты может принимать одно из нескольких заранее заданных текстовых значений.
Каждая сторона / (і=А,В) стремится на максимально возможном уровне достичь определенных целей в результате переговоров. Эти цели задаются векторными функциями : /А = {f/л}: X YAczRm\ (j = 1, ..., mj, (1.1) fB={fjB}: X- YBcRm,(j = l, ...,тв), (1.1 ) Жирным шрифтом обозначаются векторные величины. где ті — размерность пространства целей Yh количество целей стороны /. Уровень достижения целей для каждого из участников измеряется его функцией полезности: gA:YA- UAeR, (1.2) gB:YB- UBeR. (1.2 ) Множество всех векторов и = (UA, UB) образует, совместное пространство полезностей U, и є U. Будем говорить, что предложение Xj доминирует предложение х2 для стороны і, если UXX\) = ei(fi{x\))-8i{fi{xi)) = Ui{xi) (знак соответствует случаю строгого доминирования).
В терминах теории принятия решений достижение игроком целей можно определить как задачу многокритериального выбора (критерии -компоненты fi). При такой постановке полезностью называется результат свертки этих критериев в один итоговый показатель. Наиболее простой и изученный вид этой свертки - линейная комбинация критериев с определенными заранее весами. Более сложные варианты рассматриваются в теории многокритериальной полезности [20, 26, 90]. Здесь и далее предполагается, что множества критериев обеих сторон допускают сведение их в один, что и отражено в выражении (1.2). Функции fi и gi предполагаются псевдо-выпуклыми (вогнутыми).
Постановка задачи оптимизации и классификация
Рассмотрим процесс выбора ЛПР одного (наилучшего) варианта из некоторой совокупности возможных вариантов его поведения или принятия решения. Если этот выбор предполагает проведение количественного анализа, например, при оценке различных вариантов по некоторой количественной шкале, то говорят о необходимости решения задачи оптимизации [5, 29, 33]. Очевидно, что задача оптимизации имеет смысл при наличии нескольких вариантов, которые называются альтернативами. Определим необходимые для дальнейшего изложения понятия [5].
Объект оптимизации — любое устройство, процесс или ситуация для которого необходимо решать задачу оптимизации;
Критерием оптимальности будем называть совокупность признаков и предпочтений, согласно которым проводятся сравнительные оценки альтернатив, и выбирается наилучшая с точки зрения поставленной цели оптимизации.
Математическая модель объекта оптимизации описывает соотношения между величинами, характеризующими его свойства. Входящие в модель величины, варьируемые при оптимизации, называются параметрами оптимизации, или переменными задачи оптимизации, а соотношения, определяющие границы изменения этих параметров -ограничениями. Последние могут входить в математическую модель в виде равенств или неравенств (соответственно это ограничения типа равенства и ограничения типа неравенства).
Если множество параметров оптимизации является подмножеством конечномерного линейного пространства, то соответствующая задача оптимизации называется конечномерной. В этом случае в качестве критерия оптимальности может быть выбрано требование достижения наибольшего или наименьшего значения действительными скалярными функциями параметров оптимизации. Каждая такая функция называется целевой и служит количественной мерой достижения цели оптимизации данного объекта. Наконец, если целевая функция единственная, то задача оптимизации будет являться задачей математического программирования [5, 6, 29], формулировка которой в общем случае обычно записывается так: /0(дг)- тіп, лгєО, (2.1) где xeR" - точка , координатами которой являются параметры оптимизации xJtj = \,п; /0( ) - целевая функция, выбранная с таким знаком, чтобы задача оптимизации представляла собой поиск минимума этой функции; QczR"- множество возможных альтернатив или множество допустимых решений (или просто допустимое множество).
При отсутствии ограничений множество П совпадает с областью определения функции целевой функции. Если на альтернативы накладываются ограничения, то множество допустимых решений сужается.
Часто встречается следующая классификация задач оптимизации [5]:
По виду целевой функции и ограничений выделяют задачи линейного и нелинейного {квадратичного, геометрического, сепарабельного и т.д.) программирования.
Наличие или отсутствие ограничений приводит соответственно к задачам условной и безусловной оптимизации.
По виду допустимого множества Q: если оно является конечным множеством, то имеем задачу дискретного программирования, а если при этом координаты точек множества - целые числа, то - задачу целочисленного программирования.
Особо выделяется широкий класс задач выпуклого программирования, целевая функция в этом случае сохраняет свое направление выпуклости на всем допустимым множестве, которое во многих прикладных задачах часто оказывается выпуклым.
Иллюстрация и результаты работы алгоритма в типичном режиме
Ниже приводится детальное описание и интерпретация всех получаемых результатов для следующего набора параметров: ? размерность пространства предложений и = 2; ? множество допустимых предложений Q - единичный неотрицательный квадрат, прилегающий к началу координат; ? начальная точка JC = (0.2,0.4); ? длина ребра симплекса / = 0.1; ? коэффициент редукции симплекса 8 = 0.8; ? параметр точности є = 0.5 (т.е. одним из условий остановки алгоритма являлось уменьшение размера симплекса более чем в 2 раза от первоначального); ? Л = \,а1А=а2А = а1В=а2в = \/2; функции полезности сторон:
На рис. 3.1(а, б) изображены карты изолиний для функций (3.3) на множестве Q. После запуска программы результат каждого шага алгоритма определялся как промежуточный компромисс, состояние SNT-K, где К -номер текущей итерации. Локализация области компромисса производилась по формулам (2.20). Для визуализации процесса поиска производился экспорт данных в формат документа Maple 8. В приложении 4 приведен листинг такого файла, а на рис. 3.2 - результат его выполнения в Maple.
Картину процесса естественно было дополнить информацией о значениях полезностей участников переговоров. На рис. 3.3 в совместном пространстве полезностей U изображена цепочка SNT-итераций, получаемая в данном режиме (ср. с рис. 1.6). Номерами обозначены порядковые номера промежуточных компромиссов.
Как можно видеть, для данного набора значений параметров алгоритм сходится за 8 шагов. Причиной остановки алгоритма стали последовавшие неудачные отражения симплекса. Точка компромисса расположена довольно близко к границе Парето, представленной на том же рисунке. Координаты Парето-оптимальных точек были рассчитаны непосредственно по определению 1.2.
Рис. 3.4 иллюстрирует данный процесс в увеличенном масштабе и с указанием погрешностей определения точек компромисса. Полезность любой из сторон согласно (3.1) и (3.3) является заданной функцией переговорных переменных X/ и Х2- Поэтому погрешность ее определения можно найти по формуле для ошибки косвенного измерения [16, 52]: где j = A,B и Дх,,Дх2 - абсолютные погрешности определения величин xvx2, вычисляются по формулам (2.20 ). Такие расчеты были сделаны, и зависимость величины относительной ошибки локализации от номера шага алгоритма изображена на рис. 3.5. Невозрастающий характер этой зависимости объясняется тем, что последовательность значений функции полезности для каждого участника в процессе оптимизации являлась неубывающей.
На предпоследнем шаге алгоритма произошел выход за пределы множества допустимых предложений. В соответствии с процедурой обработки выхода за границу множества Q, размеры шаблона были уменьшены в kS раз. Здесь к — количество циклических выполнений этой процедуры (см. раздел 2.3.2 и блок-схему алгоритма в приложении 1). Поскольку размеры области локализации (а значит, и погрешности определения точки компромисса) напрямую зависят от размеров симплекса, то при переходе SNT-7— SNT-8 наблюдалось скачкообразное уменьшение
На рис. 3.6 приведена динамика полезностей участников переговоров А я В в процессе работы алгоритма. Как видно, до четвертой итерации включительно происходило одновременное увеличение полезностей сторон. В дальнейшем полезность стороны В в пределах ошибок локализации оставалась постоянной, и наблюдалось только возрастание UA ДО тех пор, пока это было возможным без уменьшения полезности В. Очевидно, что получаемый в итоге компромисс оптимален по Парето по определению.
Заметим, что подобное поведение полезностей является одним из двух характерных случаев. Второй случай соответствует ситуации, когда полезность с номером шага растет постоянно как для участника А, так и для участника В.
Таким образом, в результате численных экспериментов подтверждены предположения, сделанные во второй главе диссертации.
Одним из результатов проведенных исследований стал тот факт, что выбор различных начальных точек приводит к локализации, вообще говоря, различных точек на границе Парето. Вопрос устойчивости алгоритма к начальным условиям или сходимости к определенным областям специально в диссертации не исследовался. Однако был поставлен дополнительный эксперимент с целью проверки, является ли получаемая информация о точках компромисса достаточной для аппроксимации по ним границы Парето.
В качестве начальных точек были выбраны 16 точек, равномерно распределенных по множеству допустимых предложений О. (рис.3.7). Остальные параметры для наглядности были выбраны такими же, как и в предыдущем разделе. Результаты эксперимента отображены на рис. 3.8 в виде множества точек компромисса с указанием ошибок их локализации. Сплошной линией изображена граница Парето, как и выше, вычисленная по определению 1.2. Как можно видеть, на некотором участке этой границы полученные точки компромисса хорошо ложатся на «теоретическую» кривую. Поэтому можно утверждать, что ее аппроксимация на данном участке, например, квадратичными функциями методом наименьших квадратов, даст весьма хорошее приближение.
Также было "отмечено (рис. 3.8), что алгоритм имеет «области притяжения» на границе Парето, т.е. участки, к которым он сходится при запуске из разных начальных точек. Это явление может быть объяснено видом функций полезности (см. рис. 3.1а-б), а также следующими рассуждениями.
