«Малыхин В.И., Моисеев С.И. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ учебное пособие Допущено учебно-методическим объединением по образованию в области менеджмента в качестве учебного пособия для студентов ВУЗов, ...»

Министерство образования и науки Российской Федерации

Московский гуманитарно-экономический институт

Воронежский филиал

Малыхин В.И., Моисеев С.И.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ

ПРИНЯТИЯ РЕШЕНИЙ

учебное пособие

Допущено учебно-методическим объединением

по образованию в области менеджмента в качестве

учебного пособия для студентов ВУЗов, обучающихся по специальности «Менеджмент организаций»

Воронеж, 2009 УДК 519.816(338.24) ББК М 71 Малыхин В.И. Математические методы принятия решений: учебное пособие / Малыхин В.И., Моисеев С.И. Воронеж: ВФ МГЭИ, 2009.- 102 с.

ISBN Рецензенты:

кафедра Высшей и прикладной математики Академии труда и социальных отношений (зав кафедрой д-р физ.-мат. наук, проф. Геворкян П.С.

Холщевникова Н.Н., зав. кафедрой математики МГТУ «Станкин», д-р физ.-мат. наук, профессор Учебное пособие содержит основные математические методы и модели принятия управленческих решений в условиях определенности, неопределенности, риска, конфликта. Рассмотрены модели принятия коллективных решений, задача о назначениях и исторические аспекты принятия управленческих решений. Пособие можно рекомендовать студентам экономических и юридических специальностей при изучении дисциплин, связанных с принятием управленческих и иных решений, аналитического планирования, решением задач оптимизации. Учебное пособие содержит теоретический материал, примеры решения задач, задачи для самостоятельного решения, лабораторный практикум, обучающий решению задач на ЭВМ, список литературы и 30 вариантов контрольных заданий, которые можно рекомендовать для выдачи на контрольную работу для студентов заочной формы обучения.

В.И. Малыхин, С.И. Моисеев, ВФ МГЭИ

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.

КРИТЕРИЙ И АЛЬТЕРНАТИВА

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

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

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

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

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

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

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

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

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

';

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

Альтернативой или стратегией называется вариант, конкретные правила действий, которые возможны для ЛПР при принятии решений. Сам процесс принятия решений состоит в выборе ЛПР оптимальной альтернативы, наиболее выгодной для него. Например, при взятии кредита директором предприятия его альтернативами служат банки, готовые предоставить кредит. При защите обвиняемого альтернативами адвоката служат стратегии поведения, выбираемые им для защиты в суде. Альтернатив может быть несколько, все их можно перечислить и четко определить - например, какой выбрать банк для кредита из нескольких имеющихся, сколько яиц нужно сварить для салата. Такие альтернативы назовем дискретными. Однако, количество альтернатив может быть и бесконечным, все их перечислить нельзя, они могут изменяться непрерывно – например, сколько денег взять в кредит из банка, сколько минут нужно варить яйца для салата. Такие альтернативы назовем непрерывными.

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

Критерии могут быть количественные и качественные. Если показатель привлекательности можно точно оценить численным значением пропорциональным показателю, то он является количественным. Например, количественными являются критерии связанные с показателями цены, прибыли или затрат (рубли), времени (часы, дни и т.д.), размеры (метры), площади (м 2) и подобные им. Однако часто показатели критериев нельзя точно связать с каким-либо числом. В этом случае он является качественным. Его в этом случае можно лишь охарактеризовать терминами сравнения: «лучше - хуже», «дальше-ближе», «больше-меньше» и другими. Для применения математических методов анализа качественных критериев необходимо задать им количественные характеристики. Для этого применяются экспертные оценки критериев, при которых специалисты в данной области либо оценивают по n-мерной шкале показатель привлекательности критериев для каждой альтернативы, либо сравнивают попарно все показатели критериев для каждой альтернативы и рассчитывают вес альтернатив по каждому критерию. Как это делать на практике и какие существуют методы обработки результата, приводящие к принятию оптимального решения, будет рассмотрено далее.

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

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

Например, некто желает приобрести автомобиль и у него есть три варианта покупки: автомобили А, В и С. В качестве критериев покупатель определяет два: цена и качество. Предположим, что оценки критериев для альтернатив следующие:

(альтернатива) Цена (тыс. руб.) Качество (оценка по Видно, что автомобиль А лучше чем С по обоим критериям: и по цене (дешевле) и по качеству (лучше). Следовательно, альтернатива автомобиля А доминирует над С и вопрос покупки автомобиля С можно отбросить, выведя эту альтернативу из задачи. Далее, можно определять выбор лишь среди автомобилей А и В.

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

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

ПРИНЯТИЕ РЕШЕНИЙ

В УСЛОВИЯХ ПОЛНОЙ ОПРЕДЕЛЕННОСТИ

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

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

Обозначим U ij - оценку i-й альтернативы по j-му критерию. Очевидно, что критерии имеют различную важность. Одни оказывают большее влияние на принятое в результате решение, другие меньшее. Назовем степень важности каждого критерия его весом. Пусть вес j-го критерия равен W j. Вес критерия измеряется по любой пропорциональной шкале (например от 0 до 1 или по десятибалльной или любой другой шкале). Веса критериев определяют либо эксперты, либо непосредственно ЛПР. Методы определения экспертных оценок альтернатив по критериям и весов критериев будут рассмотрены далее.

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

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

Пример 1. Директор предприятия желает заключить договор с одной из ремонтно-сервисных компаний на обслуживание автоматизированной сборочной линии. Ему предлагают свои услуги четыре компании, которые условно обозначим А, В, С и D. Для выбора стороны по договору директор выделяет несколько критериев. В первую очередь важна стоимость обслуживания, гарантийные обязательства и прочие накладные расходы, которые в совокупности назовем «Финансовые условия», директор считает их вес наибольшим и по единичной шкале оценивает в W1 =0,8. Также немаловажна экспертная оценка надежности компании, их репутация. Данный критерий имеет оценку веса W2 =0,5. Кроме того нельзя не учесть такой критерий как быстрота реагирования, то как поставлена система обслуживания линии, как быстро устраняются неполадки и осуществляется наладка. Вес этого критерия W3 =0,3. Оценки альтернатив по каждому критерию (чем выше, тем привлекательнее альтернатива) приведены в таблице:

Альтернативы Оценки критериев (10-балльная шкала) Финансовые условия Репутация Быстрота реагирования Рассчитываем функции полезности для каждой альтернативы:

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

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

Предположим, что имеется n альтернатив и k критериев. Обозначим U ij - оценку i-й альтернативы по j-му критерию. Пусть оценки альтернатив по критериям имеют различные размерности. Введем обозначение U j max (U ij ) - максимальное значение j-го критерия по каждой альтернативе, а U j min(U ij ) - минимальное значение j-го критерия по альтернативам. Тогда введем нормализованные оценки альтернатив по критериям.

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

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

В результате нормализации, вне зависимости, ведется максимизация или минимизация критерия, альтернатива, имеющая наилучший для ЛПР показатель привлекательности по любому критерию получает оценку 1, наименее привлекательная имеет оценку 0, а остальные альтернативы имеют промежуточные оценки от 0 до 1 пропорционально их привлекательности между показателями наилучшей и наихудшей альтернатив. Функции полезности каждой альтернативы Fi вычисляются по формулам (1), но с нормализованными показателями привлеk кательности Fi uijW j, i 1,2,...,n, где W j - веса критериев. Приj нимается та альтернатива, для которой функция полезности максимальна. Рассмотрим пример.

Пример 2. Сотовая компания, открывая свое представительство в городе Н. выбирает помещение, которое собирается снять в аренду для своего офиса. Имеется несколько альтернатив: центр города А, парковая зона В, индустриальный район С, район ранка D. Рассматриваются следующие критерии: арендная плата (тыс. руб./год.), площади помещения (кв. м.), доступность для клиентов (балл из 10), состояние помещения (балл из 10). Оценки альтернатив по критериям, а также веса критериев (по 10-балльной системе) приведены в таблице:

натива Проводим нормализацию показателей альтернатив по критериям. Для первого критерия (аренда), который минимизируется, максимальный элемент равен 130, минимальный 65. Данный критерий минимизируется, поэтому от максимального элемента первого столбца матрицы U ij (который равен U i1 130 ) отнимаем каждый элемент этого столбца отнимаем и делим на разность 130-65=65. Для второго элемента (площадь), который максимизируется, от каждого элемента второго столбца отнимаем минимальный элемент этого столбца, равный 90 и делим на разность максимального и минимального элементов 110-90=20. Аналогично рассчитывая нормализованные показатели третьего и четвертого критериев, получаем матрицу нормализованных показателей:

Альтер- Нормализованный критерии (матрица uij ) В результате, рассчитанные с учетом весов функции полезности равны Видно, что альтернатива A (центр города) наилучшая, т.к. ее функция полезности максимальна.

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

ЭКСПЕРТНОЕ ОЦЕНИВАНИЕ

МЕТОДОМ АНАЛИТИЧЕСКОЙ ИЕРАРХИИ

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

Однако на практике не всегда можно точно и пропорционально оценить показатели привлекательности альтернатив, особенно при большом их числе. Гораздо проще бывает попарно сравнить все имеющиеся альтернативы по каждому критерию и оценить, насколько одна конкретная альтернатива привлекательнее другой. Такой метод экспертной оценки получил название метода аналитической иерархии. Рассмотрим его для случая n альтернатив, которые обозначим A1, A2,...,An, и m критериев, обозначенные K1, K2,...,Km. Возьмем первый критерий K1 и попарно сравним все альтернативы друг с другом по этому критерию. В результате получим матрицу сравнений Vij(1), каждый элемент которой, в случае, если альтернатива Ai не менее предпочтительна чем альтернатива A j равен h. Если же альтернатива Ai не более предпочтительна чем альтернатива A j, то соответствующий элемент матрицы Vij(1) равен 1/h. Так же вычисляются матрицы сравнения Vij( k ), k 1,2,...,m для других критериев. Введем, например, такую шкалу сравнений.

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

Аналогично, попарно сравнивая важности критериев, составляется матрица сравнения критериев по которой можно определять их веса.

На следующем этапе вычисляются собственные векторы альтернатив по всех критериям. Для каждой i-й альтернативы по k-му критерию вычисляем элемент вектора U i(k ) который равен среднегеометрическому показателей матрицы сравнения для этой альтернативы (строки матрицы):

Такой же собственный вектор вычисляется и для матрицы сравнения критериев.

Далее в результате нормализации собственных векторов вычисляют веса альтернатив по каждому критерию и веса самих критериев. Вес i-й альтернативы по k-му критерию Wi (k ) равен отношению соответствующего элемента собственного вектора к сумме всех элементов собственного вектора данного критерия:

Также вычисляются и веса критериев, которые обозначим Wкрит, k 1,2,...,m.

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

Рассмотрим применение метода аналитической иерархии на примере.

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

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

- стоимость строительства, доступность коммуникаций – K2;

- возможность дальнейшего расширения (планируется со временем пристроить помещения для дополнительных отделов) – K3.

Предприниматель, выступая экспертом по первому критерию о доступности и месторасположения магазина сравнил альтернативы и решил, что А по сравнению с В имеет умеренное преимущество (балл 3), А по сравнению с С имеет значительное превосходство (балл 7) и А по сравнению с D – существенное превосходство (балл 5). Эти баллы записываем в первую строку таблицы. Сравнивая альтернативы В и С, эксперт решил, что В имеет превосходство большее, чем умеренное и менее, чем существенное, поэтому в таблицу на соответствующую позицию было решено занести балл 4. Альтернатива В по сравнению с D имеет умеренное превосходство, а С и D имеют равную важность. В результате таблица примет вид:

Критерий «Доступность магазина для клиентов»

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

Критерий «Стоимость строительства»

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

Третий этап состоит в расчете собственных векторов и весов альтернатив по каждому критерию. Для первого критерия «Доступность магазина для клиентов» собственный вектор альтернативы А 1 3 7 5 3,201, Для второй, третьей и четвертой альтернатиравен Рассчитаем теперь веса альтернатив. Просуммируем элементы собственного вектора: 3,202 1,414 0,435 0,508 5,559. Разделим каждый элемент собственного вектора на эту сумму, получим нормализованные веса каждой альтернативы, а именно, для альтернативы А:

3,202/5,559=0,576, для других альтернатив, аналогично, 0,254, 0,078, 0,092. Следует отметить, что в сумме веса должны давать единицу.

Запишем результат в таблицу:

Критерий «Доступность магазина для клиентов»

Аналогичные таблицы составляем и для случая парного сравнения альтернатив по другим критериям.

Таким же способом вычисляем собственные вектора и веса критериев. Единственное отличие при вычисление собственных векторов состоит в том, что число критериев равно трем (а число альтернатив – четыре), поэтому из произведения парных оценок сравнений нужно брать корень третьей степени. Например для критерия K1:

1 3 5 2,466. Результаты – в таблице:

Рассчитываем функции полезности для каждой альтернативы:

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

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

ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ РИСКА

Рассмотренная ранее ситуация подразумевала, что ЛПР обладает полной информацией (своими оценками или экспертизами) о рассматриваемой проблеме. Однако, часто бывает, когда степень привлекательности альтернативы по тому или иному критерию зависит от случайных факторов. Например, физическое лицо, желающее положить деньги в банк, становится над проблемой выбора: положить деньги в Сбербанк РФ, где процент дохода минимален, но надежность вклада составляет 100 %, или рискнуть, положив деньги в коммерческих банк и получить по ним больший процент, но рискуя иметь проблемы с выплатами вклада, в связи с возможным банкротством банка.

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

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

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

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

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

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

1. Если взвешиваемая ветка расходится на несколько в результате принятого ЛПР решения (развилка – квадрат), то вес ветки равен максимальному весу веток, исходящих из нее, при этом ветки с меньшими весами обрубаются.

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

3. Если какая-либо ветка имеет дополнительных вес (например из-за промежуточных дополнительных затрат), то этот вес добавляется к рассчитанному.

Взвешивание веток производится до тех пор, пока не будет взвешена последняя левая корневая ветка. Ее вес и есть средний выигрыш ЛПР, если он будет действовать оптимально, принимая решения по «неотрубленным» веткам дерева решений.

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

ЛПР должен выбрать одну из двух корзин. В первой корзине имеются пять белых шаров и три черных, во второй – три красных и семь черных. ЛПР может выбрать корзину по своему желанию, однако, шары из нее извлекаются случайно. Если ЛПР из выбранной корзины достанет белый шар, то получит 100 рублей, если красный, то 500 рублей, если черный, то отдаст 200 рублей. Какую корзину рациональнее всего выбрать?

Дерево решений начинаем строить от корневой ветки (номер 1, для удобства ветки пронумерованы), которая соответствует началу принятия решения. Далее ЛПР должен выбрать корзину. Этот выбор осознанный, поэтому развилка обозначена квадратом. Перемещаясь по ветки 2, соответствующей первой корзине подходим к ситуации, когда ЛПР наудачу выбирает шар. Этот выбор случаен, поэтому развилка обозначается окружностью. У линии указываем вероятности исходов – 5/8 и 3/8 соответственно. В конце линий указываем их веса - выигрыши ЛПР при том или ином исходе: 100 и -200. Аналогично размечаем ветви 3,6 и 7.

Рассчитываем веса других ветвей дерева решений. Из ветви выходят две ветки со случайным выбором, поэтому в соответствии с правилом 2 ее вес 5/8*100+3/8*(-200)=-12,5. По аналогии, вес ветки равен 10. Из корневой ветки 1 выходят две ветки с неслучайным выбором, поэтому ее вес равен максимальному из их весов, то есть 10. Ветка 2 с меньшим весом обрубается.

Задача решена. ЛПР должен выбирать вторую корзину и его средний выигрыш составит 10 руб.

Частный предприниматель, руководитель компании, которая занимается разработкой Интернет - сайтов для предприятий и организаций получил крупный заказ. При этом поставлены жесткие сроки – разработать сайт в течении двух недель. Если это удается, то предприниматель получает прибыль 120 тыс. руб. Однако, в соответствии с договоренностью, если срок разработки сайта будет продлен на неделю, то прибыль составит лишь 40 тыс. руб. Если заказ не выполнен и за 3 недели, то договор расторгается и предприниматель терпит убытки, связанные с невыполнением заказа и штрафными санкциями в сумме 140 тыс. руб.

По оценкам сотрудников организации, оценка шансов того, что заказ будет выполнен своими силами за две недели составит 30 %.

Шанс выполнить заказ за три недели оценивается в 50%. Однако, можно воспользоваться услугами сотрудников посторонней организации, которые значительно ускорят время выполнения заказа. Можно привлечь сотрудников фирмы «WebSite», помощь которой гарантирует выполнение заказа за 3 недели, а выполнение заказа за 2 недели оценивается с вероятностью 70%. Можно заключить договор с фирмой «Intersite», помощь которой поможет выполнить заказ за 2 недели со 50 % вероятностью и гарантируют его выполнение за 3 недели. Помощь фирмы «Website» оценивается в 70 тыс. руб. (вне зависимости от срока выполнения заказа), а фирмы «Intersite» - в 50 тыс. руб. Какое решение оптимальнее всего принять предпринимателю?

Решение. Предприниматель должен сделать выбор: либо выполнять заказ своими силами, либо привлекать помощь. Если будет привлечена помощь, то нужно определиться, какая фирма будет участвовать в выполнении заказа. В результате, рассчитав все прибыли и издержки, строим дерево решений.

Рассчитав его, делаем вывод, что нужно привлекать помощь в виде компании Intersite, что даст среднюю прибыль в 30 тыс. руб.

Предприниматель имеет несколько торговых точек по продаже газет и журналов. Большую прибыль приносит ему спортивные газеты, в частности «Спорт-Экспресс». Однако спрос на него не стабилен и во многом зависит от успеха российских и местных (городских) спортсменов за предыдущий день. Если спортивную газету не удается продать в день выпуска, то спрос на нее, и соответственно прибыль предпринимателя, значительно падают. Оптовую закупку газет выгодно осуществлять партиями, кратными 1000 экземпляров. Как показывает практика, в самые удачные дни выгодно покупать для реализации не более 3-х партий газет. По статистике, вероятность не продать ни одной партии равна 0,1, вероятность продать только одну партию газеты составляет 0,3, вероятность продать две партии – 0,4, и все три – 0,2. При продаже каждой партии предприниматель получает прибыль 4000 руб. В случае, если партия была закуплена, но не была продана, убытки составляют 3000 руб. Определить, какое количество партий оптимальнее всего закупать.

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

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

ПРИНЯТИЕ РЕШЕНИЙ

В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

Предположим, что ЛПР имеет п альтернатив решения ситуации, которые обозначим A1, A2,..., An. Результат выбора (выигрыш ЛПР) зависит от того, как будит развиваться ситуация, на которую ЛПР повлиять ни как не может. Предположим, что ЛПР выделяет m вариантов развития ситуации, которые обозначим S1, S 2,... S m. Данные варианты в теории принятия решений называют «Состояниями природы», т.к. в большинстве реальные задачи этого типа связаны с погодными, климатическими, социальными и другими неопределенностями.

Допустим, что известен результат для ЛПР (выраженный количественно) при каждой альтернатива Ai и развитии ситуации Bj.

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

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

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

Директор торговой фирмы, продающей телевизоры марки «Zarya» решил открыть представительство в областном центре. У него имеются альтернативы либо создавать собственный магазин в отдельном помещении, либо организовывать сотрудничество с местными торговыми центрами. Всего можно выделить 5 альтернатив решения:

A1, A2, A3, A4, A5. Успех торговой фирмы зависит от того, как сложится ситуация на рынке предоставляемых услуг. Эксперты выделяют 4 возможных варианта развития ситуации S1, S 2, S3, S 4. Прибыль фирмы для каждой альтернативы при каждой ситуации представлена матрицей выигрышей a ij (млн. р./год).

Рассмотрим основные критерии, позволяющие выбирать оптимальную альтернативу для принятия решения.

1) Критерий Лапласа.

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

Выбирается та альтернатива, для которой функция полезности максимальна. Для примера:

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

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

Для нашего примера: 1 5; 2 9; 3 2; 4 1; 5 6. Видно, что наилучшим из наихудших показателей обладает альтернатива А2, для нее 2 9 наибольшее.

3) Критерий максимального оптимизма.

Наиболее простой критерий, основывающийся на идее, что ЛПР, имея возможность в некоторой степени управлять ситуацией, рассчитывает, что произойдет такое развитие ситуации, которое для него является наиболее выгодным. В соответствии с критерием принимается альтернатива, соответствующая максимальному элементу матрицы выигрышей. Для приведенного примера эта величина a34 22, поэтому выбираем альтернативу A3.

Он основан на принципе минимизации потерь, связанных с тем, что ЛПР принял не оптимальное решение. Для решения задачи составляется матрица потерь, которая называется матрицей рисков rij, которая получается из матрицы выигрышей aij путем вычитания из максимального элемента каждого столбца a max max (aij ) всех осj тальных элементов. В рассматриваемом примере эта матрица есть:

Далее, для каждой альтернативы определяем величины i, равные максимальному риску (наибольшее число в каждой строке матрицы рисков) и выбирают ту альтернативу, для которой максимальный риск минимален. В нашем примере: 1 17; 2 12;

3 13; 4 21; 5 18, минимально 2 12. Принимаем альтернативу А2.

Это самый универсальный критерий, который позволяет управлять степенью «оптимизма - пессимизма» ЛПР. Введем некоторый коэффициент, который назовем коэффициентом доверия или коэффициентом оптимизма. Этот коэффициент можно интерпретировать как вероятность, с которой произойдет наилучший для ЛПР исход. Исходя из этого, наихудший вариант можно ожидать с вероятностью (1-). Коэффициент доверия показывает, насколько ЛПР может управлять ситуацией и в той или иной степени рассчитывает на благоприятный для него исход. Если вероятности благоприятной и неблагоприятной ситуации для ЛПР равны, то следует принять =0,5.

Для реализации критерия определяются наилучшие a i и наихудшие a i значение каждой альтернативе по формулам ai max aij, ai min aij. Далее, вычисляются функции полезности по формуле:

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

Предположим, что для нашего примера ЛПР достаточно уверен в положительном результате и оценивает вероятность максимального успеха в =0,7. Тогда:

В соответствии с расчетами ЛПР следует выбрать альтернативу А3. Если же, например, ЛПР не очень уверен в положительном исходе и расценивает его вероятность порядка =0,2, то функции полезности равны:

Видно, что в этом случае следует принять А2, для которого функция полезности максимальна.

Следует отметить, что при =0, критерий Гурвица переходит в пессимистический критерий Вальда, а при =1 – в критерий максимального оптимизма.

В случае, если показатель привлекательности по критерию a ij минимизируются (чем меньше, тем лучше для ЛПР, например затраты, риск и др.), то критерии принятия оптимального решения несколько меняются. Рассмотрим эти отличия.

Критерий Лапласа определяет оптимальное решение по минимальной функции полезности. Применяя критерий Вальда необходимо вычислять максимальный показатель каждой альтернативы (строки) i и принимать альтернативу, где этот показатель минимален. Критерий максимального оптимизма позволяет определить оптимальное решение, соответствующее минимальному элементу матрицы выигрышей (которую в случае минимизации часто называют матрицей потерь). Матрица рисков в критерии Сэвиджа получается в результате вычитания из каждого элемента матрицы потерь aij минимального элемента каждого столбца a min min(aij ). Для реализации критерия Гурвица вычисляются максимальные и минимальные показатели для каждой альтернативы ai max aij, ai min aij и функj ции полезности рассчитываются по формуле: Fi ai ai (1 ).

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

Нефтяная компания собирается построить в районе крайнего севера нефтяную вышку. Имеется 4 проекта A, B, C и D. Затраты на строительство (млн. руб.) зависят от того, какие погодные условия будут в период строительства. Возможны 5 вариантов погоды S1, S2, S3, S4, S5. Выбрать оптимальный проект для строительства используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при 0,6. Матрица затрат имеет вид:

Критерий Лапласа.

Следует выбрать альтернативу А1.

Критерий Вальда: среди наихудших вариантов 1=12, 2=10, 3=15, 4=11, наилучший соответствует 2=10, следовательно принимаем альтернативу А2.

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

Критерии Сэвиджа имеет матрицу рисков:

Максимальные элементы для каждого критерия матрицы рисков равны: 1=4; 2=4; 3=8; 4=3. Принимаем альтернативу, соответствующую минимальному значению 4=3, то есть А4.

В соответствии с критерии Гурвица на уровне 0,6, функции полезности равны:

Принимаем альтернативу А2 с наименьшей функцией полезности F1 7,8.

ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ КОНФЛИКТА

В рассмотренных в предыдущем параграфе моделях, «соперник»

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

Рассмотрим следующую модель. ЛПР А желает принять решение, на результат которого влияет другое ЛПР В, цели которого противоположны А. ЛПР В анализирует все возможные варианты А и принимает такое решение, которое приводит к наименьшему выигрышу А (соответственно максимальному своему выигрышу). Примерами таких ситуаций служат отношения между продавцом и покупателем, адвокатом и прокурором, кредитором и дебитором, истцом и ответчиком и т.д. Подобные ситуации называются конфликтными. Математические методы анализа конфликтных ситуаций объединяются под названием теории игр, сама конфликтная ситуация носит название игры, а стороны, участвующие в конфликте, называются игроками. Исход игры называется выигрышем (или проигрышем) игроков. Если выигрыш одного игрока равен проигрышу другого, то игра называется антагонистической. Пусть игрок А может выбрать в качестве действий одну из п альтернатив: А1, А2,…, Аn. Эти альтернативы в теории игр принято называть стратегиями. Аналогично, игрок В может принять одну из m стратегий В1, В2,…, Вm. Предположим, что известны выигрыши (проигрыши) игрока А при любой выбранной им стратегии Аi и любом ответе ему игроком В – стратегии Вj. Пусть этот результат выражен числом аij (которое может быть и отрицательным в случае проигрыша А). Величины аij образуют матрицу:

Эта матрица называется платежной или матрицей игры.

Рассмотрим игру со стороны А. Он, выбирая свою стратегию Аi, понимает, что В ответит ему такой стратегией Вj, чтобы выигрыш А был минимальным. Поэтому, из всех наихудших вариантов (минимальных элементов каждой строки платежной матрицы) i min(aij ), игроку А выгодно выбрать стратегию, соответствующую максимальному из этих элементов:

Величина называется нижней ценой игры или максимином.

Это гарантированный выигрыш игрока А. С другой стороны, игрок В выбирая свою стратегию Вj понимает, что игрок А ответит такой стратегией Аi, чтобы его выигрыш был максимален. Поэтому из наилучших вариантов для А (максимальных элементов каждого столбца) j max aij игроку В рационально выбрать свою стратегию, соответi ствующую минимальному из этих чисел:

Величина называется верхней ценой игры или минимаксом.

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

ПРИМЕР 1: Дебитор А желает выбрать один из четырех условий займа: А1, А2, А3, А4. Кредитор может на любой вариант займа ответить вариантом предоставления кредита В1, В2, В3, В4, В5. Процентные ставки для дебитора при любом варианте кредитора представлены платежной матрицей:

Находим минимальные элементы каждой строки платежной матрицы I и из них находим максимальное значение. Из максимальных элементов каждого столбца j выбираем минимальный.

Видно, что верхние и нижние цены игры совпадают 5, следовательно для обоих игроков выгодны стратегии A2, B и процентная ставка, равная 5. При принятии игроками иной стратегии, отличной от оптимальной, этот игрок только проиграет.

Рассмотрим теперь ситуацию, когда верхняя и нижняя цены не совпадают. В этом случае игра решается в смешанных стратегиях. Смешанный стратегии предполагают, что каждый игрок будет выбирать случайно из возможно допустимых чистых стратегий (но выбирать их с вероятностями), либо частично реализовывать чистые стратегии в заданных пропорциях. Нахождение этих вероятностей (или пропорций) и является решением игры. Таким образом, в общем виде, решением игры являются смешанные стратегии 1 2 p p... p и B1 B2...Bm q q... q, где p i и q j - вероятности чистых стратегий Ai u B j в смешанной.

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

ПРИМЕР 2. Игрок А прячет в одной из рук монету. Игрок В пытается угадать руку с монетой. Если В не угадывает, то А получает от В 1 у.е. Если В угадывает руку с монетой и эта рука правая, то он получает от А 1 у.е. Если В находит монету в левой руке, то он получает от А 2 у.е. Определить оптимальные стратегии поведения для каждого игрока и средний выигрыш для А.

Пусть стратегии игроков: А1 – спрятать в правой; В1 – искать в правой; А2 – спрятать в левой; В2 – искать в левой. Игровая матрица для данной ситуации относительно игрока А имеет вид:

Тогда вероятности чистых стратегий в смешанной равны:

Таким образом, игроку А нужно случайно чередовать руки с монетой, но в правой руке прятать в среднем в трех случаях из пяти, а в левой в двух случаях из пяти. В это случае в каждой игре в среднем А получит (-1/5) руб., то есть теряет 20 коп., игра для А не выгодная.

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

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

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

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

ПРИМЕР 3. Директор транспортной компании А, оказывающей транспортные услуги по перевозке пассажиров в областном центре, планирует открыть один или несколько маршрутов: А1, А2, А3 и А4. Для этого было закуплено 100 микроавтобусов. Он может поставить весь транспорт на одном из маршрутов (наиболее выгодном), либо распределить по нескольким маршрутам. Спрос на транспорт, а соответственно и прибыль компании во многом зависит от того, какие маршруты в ближайшее время откроет главный конкурент - компания В. Ее руководство полностью владеет ситуацией и может открыть несколько из пяти маршрутов В1, В2, В3, В4 и В5. Оценки прибыли компании А (млн. руб.) при любом ответе В представлена платежной матрицей:

Находим оптимальное распределение прибыли по маршрутам и ожидаемую прибыль.

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

которая эквивалентна матрице:

Тогда вероятности чистых стратегий компании А в смешанной (17 машин) нужно направить на маршрут А1, а остальные 5/6 парка ( машины) на маршрут А3. Маршруты А2 и А4 использовать не рационально. При этом прибыль, не зависимо от ответа компании В будет составлять 34/6 млн. руб.

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

ПРИМЕР 4. Построить прямую и двойственную задачи линейного программирования для решения матричной игры, заданной платежной матрицей: 6 7 2 4.

Прямая и двойственная задачи линейного программирования имеют вид:

Из решения можно найти игры цену игры pi xi, (i 1,2,3,4,5); q j y j, ( j 1,2,3,4).

Известно, что решение задач линейного программирования связано с громоздкими вычислениями. Для численного решения этих задач можно использовать надстройку пакета прикладных программ MS Excel «Поиск решения», которая входит в MS Office.

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

ЗАДАЧА О НАЗНАЧЕНИЯХ

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

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

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

1. n – количество ресурсов, m – количество работ.

2. ai 1 – единичное количество ресурса Ai (i 1,2,..., n), например: один работник; одно транспортное средство; одна научная тема и т.д.

3. b j 1 – единичное количество работы B j ( j 1,2,..., m), например: одна должность; один маршрут; одна лаборатория.

4. cij – характеристика качества выполнения работы B j с помощью ресурса Ai. Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой. Величину cij можно рассматривать как показатель привлекательности (критерий) для альтернативы В качестве исходных данных введем переменные xij – факт назначения или неназначения ресурса Ai на работу B j, которая определяется по правилу:

0, если i й ресурс не назначен на j ю работу;

1, если i й ресурс назначен на j ю работу.

Также имеется некоторая целевая функция L(x), равная общей (суммарной) характеристики качества распределения ресурсов по работам. Это может быть прибыль или процент брака, издержки или себестоимость продукции, время производства или время эксплуатации ресурсов. Эта функция зависит от характеристик cij, которые образуют матрицу вида:

Количество Эта матрица называется матрицей эффективностей (при максимизации целевой функции) или матрицей затрат (при минимизации).

Математическая модель задачи о назначениях имеет вид:

Задача о назначениях является частным случаем общих классов оптимизационных задач, и поэтому существует много разнообразных методов ее решения. История решения задачи о назначениях показывает, как постепенно математики приходили к пониманию вычислительной сложности методов, как далеко не сразу была осознана необходимость поиска эффективных алгоритмов, удобных для практического применения. Впервые задача о назначениях была рассмотрена Гаспаром Монжем (1746-1818) в 1784 году в геометрической форме.

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

Задача о назначениях может быть переформулирована как задача поиска совершенного паросочетания минимального веса во взвешенном двудольном графе. При этом вершины графа соответствуют строкам и столбцам матрицы стоимостей, а ребра имеют веса, равные элементам матрицы [3]. Книг доказал теорему о том, что максимальный размер паросочетания совпадает с размером минимального вершинного покрытия, а Эгервари впервые рассмотрел паросочетание во взвешенном графе и доказал теорему для оценки максимальной суммы весов ребер в паросочетании. Доказательство теоремы содержало алгоритм, позволяющий путем последовательного преобразования матрицы найти эту сумму. Работы Книга и Эгервари стали основой для «венгерского» метода решения задачи о назначениях, разработанного Куном в 50-х годах. В конце 40-х годов XX века были созданы первые ЭВМ. Задача о назначениях была в ряду первых задач, которые решались с помощью компьютера. Развитие вычислительной техники привело к бурному развитию методов оптимизации. Тем временем, в году Данциг предложил очень эффективный метод для решения общей задачи линейного программирования, получивший название симплексметод. Задача о назначениях может быть легко сведена к задаче линейного программирования, если ввести для каждого элемента матрицы стоимостей свою переменную, принимающую значения 0 или 1, и записать 2n ограничений, что в каждом столбце и каждой строке сумма элементов строго равна единице.

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

Венгерский метод Куна состоит из трех шагов:

Шаг 1. Редукция матрицы.

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

Шаг 2. Построение паросочетания.

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

Шаг 3. Преобразование Эгервари.

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

Далее снова выполняется шаг 2.

ПРИМЕР 1. Решить задачу об оптимальном назначении с матрицей затрат A:

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

Этап 1. В каждой строке ищем минимальный элемент (он взят в круглые скобки):

и отнимаем эти числа от всех элементов строки. Получим:

Теперь проводим аналогичную процедуру для всех столбцов:

ищем наименьший элемент по столбцу и отнимаем его из всех элементов столбца. Получим:

Этап 2. Выбираем строку с одним нулем (строка №1), выделяем нуль жирным и зачеркиваем (обозначим символом ) оставшиеся нулевые значения этого столбца (столбца №3). Выбираем строку с одним нулевым значением (строка №5), выделяем нуль. Выбираем строку с одним нулем (строка №3), выделяем нуль жирным и зачеркиваем оставшиеся нулевые значения этого столбца (столбца №4). Выбираем строку с одним нулем (строка №4), выделяем нуль жирным и зачеркиваем оставшиеся нулевые значения этого столбца (столбца №1). Выбираем строку с одним нулевым значением (строка №2), выделяем нуль. Получаем оптимальную матрицу назначений:

По выделенным жирным шрифтом нулям определяем решение задачи о назначениях: ( A1, B3 ); ( A2, B5 ); ( A3, B4 ); ( A4, B1 ); ( A5, B2 ).

Минимальное значение целевой функции: 1+2+2+1+2=8. В лабораторном практикуме приводится метод решения задачи о назначениях на ЭВМ.

КОЛЛЕКТИВНЫЕ РЕШЕНИЯ

Коллективные решения принимаются в результате голосования.

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

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

Однако, при использовании данной системы на практике, Кондорсе столкнулся с парадоксальным результатом, который получил название «парадокса Кондорсе». Рассмотрим его на примере.

Предположим, что в выборах участвуют 3 кандидата: А, В и С.

Предпочтения 100 избирателей распределились следующим образом:

Предпочтения Число голосов Предпочтение Число голосов

АВС ВСА

АСВ САВ

ВАС СВА

Рассмотрим пару А-В. За предпочтение А проголосовало 23+13+16=52 избирателя, за В: 7+22+19=48 избирателей, в этой паре победил А (обозначим это как АВ).

Рассмотрим пару А-С. За предпочтение А проголосовало 23+13+7=43 избирателя, за С: 22+16+19=57 избирателей, в этой паре победил С (обозначим это как СА).

Рассмотрим пару В-С. За предпочтение В проголосовало 23+7+22=52 избирателя, за С: 13+16+19=48 избирателей, в этой паре победил В (обозначим это как ВС).

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

Одной из самых распространенных систем голосования в мире является система, основанная на правиле большинства голосов, когда победителем считается тот, кто наберет больше всего первых мест. В нашем примере победит А (36 первых мест), у В 29 голосов за первые места, у С – 35 голосов. Однако данный метод голосования учитывает лишь наилучшее предпочтение, что, очевидно, является его недостатком. Кроме того, известно множество примеров когда (чисто психологически) избиратель вместо того, чтобы участвовать в определении наилучшего из двух явных лидеров, противодействуя им обоим, выводит на первое место аутсайдера, который потом и является победителем.

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

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

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

Кандидат, занявший по предпочтениям первое место у избирателя получает n-1 очко, за второе место n-2 очка и так далее, за предпоследнее место – 1 очко, за последнее – 0 очков. Покажем на примере, что данный метод также не лишен недостатков. Предположим, что распределение голосов имело следующий вид:

Кандидат А по системе Борда набрал 142+130+182+150= очка, В набрал 141+92+180+191=51 очко, а С набрал 140+91+181+192=65 очков. Видно, что победил С, хотя большинство первых мест (32 из 60) получил А.

В последнее время, особенно в телевизионных играх и шоу, очень распространены системы голосования с выбыванием, когда в течении нескольких туров для каждого кандидата вычисляются количества последних мест для каждого кандидата в каждом туре и из числа кандидатов удаляется тот, кто набрал максимальное число последних мест. По такой системе, исходя из предыдущего примера, в первом туре кандидат А набрал 28 последних мест, В – 18 мест и С – мест. В первом туре исключается А. Во втором туре (без учета А) у В имеется 19+18=37 последних мест, а у С – 14+9=23 мест, исключается В, выиграл С. Видно, что кандидат А, который имеет большинство первых мест, был исключен уже в первом туре, что подтверждает несовершенство и этой системы голосования.

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

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

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

ПРИМЕР 1. В коллективных выборах участвуют 4 кандидата:

А, B, C и D. Голоса 150 избирателей были распределены по следующим схемам предпочтений:

Предпочтения Число голосов Предпочтения Число голосов

ACDB CABD

ADBC CADB

BACD DCBA

BDCA DCAB

BCDA DABC

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

1. Выбор победителя по большинству первых мест в одном туре.

Кандидаты набрали голоса избирателей за первые места в количестве:

А: 13+8+15=36; B: 16+12+9=37; C: 4+23+11=38; D: 18+14+7=39.

Победил кандидат D.

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

Во второй тур вышли D (39 голосов) и C (38 голосов).

В паре C-D за C проголосовало 13+8+16+9+4+23+11=84 голоса, за D проголосовало 15+12+18+14+7=66 голоса, победил С.

3. Выбор победителя по системе Кондорсе, в результате парных сравнений кандидатов.

Рассмотрим число голосов для каждой пары кандидатов Пара A-B. За А: 13+8+15+23+11+14+7=91. За В: 16+12+9+4+18=59, получаем АВ.

Пара А-С. За А: 13+8+15+16+7=59. За С: 12+9+4+23+11+18+14=91, получаем СА.

Пара А-D. За А: 13+8+15+16+23+11=86. За D: 12+9+4+18+14+7=64, получаем АD.

Пара В-С. За В: 13+15+16+12+9+7=72. За С: 8+4+23+11+18+14=78, получаем СВ.

Пара В-D. За В: 13+16+12+9+23=73. За D: 8+15+4+11+18+14+7=77, получаем DB.

Пара С-D. За С: 13+8+16+9+4+23+11=84. За D: 15+12+18+14+7=66, получаем СD.

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

Видно, что победил кандидат С, он оказался лучшим в парных сравнениях со всеми остальными кандидатами (на графе из вершины «С» выходят все стрелки). Худшим оказывается кандидат В (на графе в вершину «В» входят все стрелки).

Следует отметить, что могут быть ситуации, когда нет ни одного кандидата, победившего в парных сравнениях всех остальных. Такие варианты голосования иллюстрируют «парадокс Кондорсе».

4. Выберем победителя по системе Борда, когда за первое место набирается 3 очка, за второе – 2, за третье – 1 очко и за четвертое – 0.

Посчитаем очки, набранные кандидатами по этой системе.

Кандидат А набрал: 3(13+8+15)+216+0(12+9+4)+2(23+11)+018+ +114+27=236 очков.

Кандидат В набрал: 213+08+115+3(16+12+9)+1(4+23)+011+ +118+014+17=204 очков Кандидат С набрал: 113+28+015+1(16+12)+29+3(4+23+11)+ +2(18+14)+07=253 очка.

Кандидат D набрал: 013+81+215+016+212+19+24+023+ +111+3(18+14+7)=180 очков.

Видно, что по данной системе победил С, набравший большинство очков.

5. Выберем победителя по многотуровой системе, в которой на каждом туре отсеивается один, последний, кандидат.

Вычисляем количество последних мест для каждого кандидата в первом туре. Для А – 12+9+4+18=43 последних места, для В – 8+11+14=33 места, для С – 15+7=22 места, для D – 13+16+23=52 последних места. Видно, что наихудшим в первом туре оказался D, который набрал больше всего последних мест, поэтому исключаем именно его.

Во втором туре по исходной таблице вычисляем количество последних мест для участников А, В и С. При этом, в исходном раскладе голосов кандидата D не учитываем (то есть если в предпочтениях на последнем месте стоит кандидат D, то баллы за последнее место прибавляем предпоследнему кандидату). В результате во втором туре А набирает 12+9+4+18=43 последних места, В имеет 8+23+11+14= места, С набирает 13+15+16+7=51 последних места. Исключаем В.

В третьем туре, исходя их предпочтений пары А-С, выигрывает С, набрав 91 голос против 59.

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

ИСТОРИЧЕСКАЯ РОЛЬ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ

Продукцией специалиста-управленца является управленческое решение. Каковы основные требования к таким решениям?

Управленческое решение принимается в конкретной ситуции, назовем ее СУР-ситуацией управленческого решения. Решение должно разрешать СУР, т.е. предлагать меры, направленные на ее изменение, на приведение СУР к какому-то конечному состоянию, устраивающему ЛПР. Лицо, которое должно обеспечить осуществление решения, назовем Исполнителем. Управленческое решение должно содержать четкую и ясную инструкцию Исполнителю по осуществлению решения. Неплохо, если эта инструкция будет содержать стимул для Исполнителя (например, в виде обещания награды или, наоборот, наказания). Существует масса учебных пособий, освещающих те или иные аспекты управленческих решений [16-18]. Но гораздо полезнее и доходчивей объяснять тонкости разработки и принятия управленческих решений на примерах. В биографиях знаменитых менеджеров можно найти немало примеров управленческих решений, хороших или даже замечательных в том или ином смысле.

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

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

Еще и потому, что в первых трех примерах ЛПР является Сталин 1., Еще при жизни Ленина Сталин возглавил Учраспред-отдел ЦК партии, ведавший учетом и распределением партийных кадров. Проще говоря, Сталин решал кого на какой пост поставить. В книге [16]так оценивается в наше время содержание двух статей Сталина 1921 и 1923 годов!(У Сталина еще вся жизнь впереди!) «Если оценивать содежание этих работ по общепринятым в науке критериям, то выводов здесь больше, чем на очень сильную докторскую диссертацию по специальности «политология» или, точнее, «политическая технология». Причем своей актуальности они не утратили и спустя много лет. Здесь нет «красивых» слов, ярких образов «высокого» литературного стиля-только технология политики».

общепризнанный гений управленческой науки, для доказательства этого достаточно того факта, что он 28 лет руководил СССР и победил всех своих противников именно методами оргработы Один из таких примеров возьмем из знаменитой книги В.Богомолова «В августе 44» (другое название книги «Момент истины»). Советская военная контрразведка «СМЕРШ» уже целый месяц в августе 1944г. не может поймать группу немецких шпионов, действующих в тылу 3-го Белорусского фронта в западной Украине в окрестностях реки Неман. Советское Верховное Главнокомандование планирует осуществить в этих местах в скором времени крупную стратегическую операцию с далеко идущими последствиями.

Чрезвычайно важно не допустить никакой утечки секретных сведений об этой операции. О ней знают только 5 генералов, два маршала и сам Сталин. Знакомясь с донесениями советской военной контрразведки Сталин отметил действия немецкой шпионской группы как угрожающей успеху намечающейся стратегической операции. Это явилось основанием для взятия на контроль Ставкой ВГК дела СМЕРШа по поимке немецкой группы шпионов. Ознакомясь с докладом начальника штаба фронта, на котором намечалась стратегическая операция о ходе ее подготовки Сталин отметил, что подготовка эта идет успешно, в частности, режим секретности выполняется хорошо и толково. Тем большую досаду у Сталина вызвала не пойманная немецкая шпионская группа. Сталин распорядился экстренно вызвать к себе начальников МВД и госбезопасности страны, а также главного «виновника»- начальника СМЕРШа (сейчас мы знаем, что тогда им был В.Абакумов-в романе Богомолова эта фамилия не названа). В недолгом ожидании вызванных Сталин размышляет о том, как вести с ними разговор. Цитата из книги Богомолова:

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

Дальше мы вкратце перескажем состоявшийся разговор Сталина с тремя вызванными.

Богомолов с симпатией описывает начальника СМЕРШа и мы в этот момент переносим эту симпатию на всю советскую армию:

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

«Поверьте, товарищ Сталин, делается все возможное»-сказал он.

Но что же в ответ услышал?

«Не уверен»-ответил Сталин. «И потом, что значит делается?»продолжал он. «Нас не интересует процесс поиска сам по себе, нам нужен результат. Заметьте также, мы Вас не ограничиваем- делайте и НЕВОЗМОЖНОЕ».

Вот реплика Сталина, из-за которой мы и привели этот пример.

Одной фразой Сталин придал начальнику СМЕРШа новый импульс в работе и какой импульс! Характерно, что выйдя от Сталина и разговаривая по телефону со своим подчиненным на фронте, непосредственно занятым розыском и поимкой упомянутой немецкой шпионской группы начальник СМЕРШа употребил для его «накачки»

те же самые слова: «Делайте и невозможное!».

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

Смущенный Яковлев пытался объяснить «непонимающему» Сталину, что даже в богатой и невоюющей Америке на создание такого самолета ушло бы никак не меньше 2-х лет. На что Сталин ответил одной-единственной фразой «А разве Вы «амэриканец»?

Одной-единственной фразой Сталин дал понять Яковлеву, что его апелляция к Америке не уместна: и то, что Америка не воюет, а СССР ведет смертельную войну и что американцы нам не пример и т.д. и т.п.

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

В своих довольно объемистых «Воспоминаниях» Яковлев этот эпизод почему-то не приводит, хотя много и в деталях рассказывает о своих многочисленных встречах со Сталиным.

Яковлев приказ Сталина выполнил- в указанный срок лучший в мире истребитель был создан.

Третий пример тоже связан со Сталиным.

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

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

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

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

«Ви знаете такого человека?»-спросил Сталин. «Да»- ответил молодой директор. «Это я». Сталин ничего не сказал, но рано утром в город прибыл курьер с распоряжением ГКО, в котором молодой директор назначался директором объединенного танкового завода.

Управленческое решение часто весьма необходимо принимать вовремя. Как говорят в народе -«дорога ложка к обеду». При принятии решения ЛПР должен проявить необходимую ответственность, сделать это быстро и эффективно.

Следующий пример связан с известнейшим русским адвокатом А.Ф.Кони (с ударением на последнем слоге). КОНИ Анатолий Федорович - юрист, гос. деятель, литератор, действительный тайный советник (1910); д-р права (1890), почетный член Петербурсгской Академии наук(1900). Окончил юрид. ф-т Моск. ун-та (1865). С 1870-х гг. получил всероссийскую известность как судебный оратор. Из выигранных им дел широкую известность получила историю о суде над контрабандистами-греками в Таганроге. И сидеть бы им, горемыкам, в тюрьме, если бы не позвали Кони. Тот внимательно ознакомился с делом и вплоть до судебного заседания не предпринимал никаких действий в защиту контабандистов. А на судебном заседании зачитал протокол задержания контрабандистов. В котором было констатировано, что контрабанда была совершена на «фелюгах». Таково было официальное местное название суденышка.

Затем Кони зачитал уголовное уложение- соответствующую статью уголовного кодекса. В этой статье было перечислено 126 типов судов, перевозка на которых признавалась контрабандой. И Кони торжествующе окончил свою речь последней фразой из этой статьи уголовного кодекса, в которой было сказано, что приведенный перечень судов носит исчерпывающий характер. И значит, перевозка на фелюгах не может быть признана контрабандой.

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

В 1956 г. Египет национализировал Суэцкий канал. Израиль, Англия и Франция начали агрессию против Египта. США напрямую не были на их стороне, но попросили разрешения у Турции использовать ее военную инфраструктуру для организации помощи Англии и Франции по воздуху. Турецкий парламент разделился в спорах по этому поводу. Противники предоставления турецких баз США апеллировали к позициии СССР: дескать неизвестно, как он себя поведет. И вот наступил решающий день голосования. Но председатель главной оппозиционной партии был спокоен и держал в руке какую-то иностранную газету. В чем дело, почему он так спокоен-терялись в догадках его сторонники. Наконец ему дали слово.

Он развернул газету- это оказалась советская «Правда» и вслух прочитал сообщение советского правительства: командующим войсками закавказского военного округа назначается Маршал Советского Союза К.Рокоссовский. Все стихло, голосование отменили.

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

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

ПРИНЯТИЕ РЕШЕНИЙ

В УСЛОВИЯХ ПОЛНОЙ ОПРЕДЕЛЕННОСТИ

Рассмотрим решение задачи нахождения оптимального решения в условиях полной определенности с помощью ЭВМ на примерах.

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

Частный предприниматель открыл новый продовольственный магазин. При этом необходимо заключить долгосрочный договор с одной из оптовых баз по поставке продукции. В городе имеется пять оптовых баз: А,В,С,D и Е. В качестве альтернатив, определяющих выбор базы выступают: широта ассортимента (К1); кредитные и финансовые условия (К2); сервисные и транспортные условия (К3); репутация и надежность (К4). По всем критериям были получены экспертные оценки в баллах по 10-балльной системе. Также имеются оценки весов критериев.

Альтернатива С какой базой лучше всего заключить договор?

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

Ставим курсор в ячейку F2 и вводим формулу =B2*B$7 и автозаполняем ячейки от F2 до I 6, растягивая сначала ячейку F2 за нижней правый угол на диапазон F2 - F6, а затем этот выделенный диапазон вправо на 4 столбца до I 6. Ставим курсор в К2 и вводим =СУММ(F2:I2). Автозаполняем данные этой ячейки на К2-К6. Видно, что максимальная функция полезности, равная 145, у альтернативы D, следовательно с этой базой лучше всего заключить договор.

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

Негосударственное образовательное учреждение в связи с расширением желает приобрести здание под учебный корпус. Имеются варианты покупки четырех зданий: в центре города – А; в жилом секторе – В; в промышленной зоне С; на окраине города D. В качестве критериев выступают: цена покупки (К1, млн.руб.), площадь строения (К2, кв.м.), место расположения (К3, минуты от метро), качество строения (К4, балл по 10-балльной шкале). Результаты оценок альтернатив по критериям и веса критериев приведены в таблице:

Альтернатива нужно ввести подписи таблицы, соответственно названия критериев К1, К2, К3, К4. В область G2-J5 вводим нормализованную таблицу.

Первый критерий (цена) минимизируется. Поэтому от максимального элемента каждого столбца матрицы выигрышей отнимаем каждый элемент этого столбца и делим данное число на разность между максимальным и минимальным элементами столбца. Вводим в G формулу (ссылки на ячейки вводятся латинскими буквами):

=(МАКС(B$2:B$5)-B2)/(МАКС(B$2:B$5)-МИН(B$2:B$5)) За нижний правой угол этой ячейки мышкой с помощью автозаполнения формулу нужно растянуть на G2-G5. Второй критерий (площадь) максимизируется. Поэтому, от каждого показателя привлекательности критерия К2 отнимаем минимальный элемент столбца С2:С5 и делим на разницу максимального и минимального элемента этого столбца. Для этого вводим в Н2 формулу =(C2-МИН(C$2:C$5))/(МАКС(C$2:C$5)-МИН(C$2:C$5)) Аналогично, автозаполнением переносим формулу на ячейки Н2-Н5.

Третий критерий минимизируется. Вводим в I2 формулу =(МАКС(D$2:D$5)-D2)/(МАКС(D$2:D$5)-МИН(D$2:D$5)) автозаполняя ее на I2-I5. Четвертый критерий максиминируется. Вводим в J =(E2-МИН(E$2:E$5))/(МАКС(E$2:E$5)-МИН(E$2:E$5)) автозаполняя ячейки J2-J5.

В результате получаем матрицу рисков. Теперь можно вычислить функции полезности по каждой альтернативе. Для этого в F8 вводим подпись «Функция полезности», в ячейки F9-F12 вводим подписи «F1»…«F4», в G9 вводим формулу =G2*$B$6+H2*$C$6+I2*$D$6+J2*$E$6, которую автозаполнением переносим на G9-G12. Видно, что максимальная функция полезности 17,6 для второй альтернативы.

Задания для самостоятельного решения ЛПР выбирает адвоката для представления его интересов в суде. В качестве альтернатив у него имеются адвокаты А1, А2, А3 и А4.

В качестве критериев выступают: Стоимость (К1), Авторитет (К2), Репутация (К3), Специализация (К4). Оценки показателей привлекательностей каждого адвоката (альтернативы) по каждому критерию, а также веса критериев по десятибалльной системе представлены матрицей:

Директор частного предприятия собирается принять на должность юриста одного специалиста. Имеется пять кандидатов на эту должность: А1, А2, А3, А4, А5. В качестве критериев выступают: Образование (100 балльная система, максимизируется, К1), Запрашиваемая зарплата (тыс. руб. в месяц, К2); Стаж работы на юридической должности (лет, К3); Доля выигранных дел в суде; Характеристики с мест работ, авторитет (10 балльная система, максимизируется).

Оценки альтернатив по всем критерием, а также веса критериев приведены в таблице.

Альтернатива \ Принять оптимальное решение.

ВЫБОР ОПТИМАЛЬНОГО РЕШЕНИЯ

МЕТОДОМ АНАЛИТИЧЕСКОЙ ИЕРАРХИИ

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

Директор завода собирается открыть дочернее предприятие в одном из районных центров области. Имеется возможность выбрать один из городов: А, В, C и D (альтернативы). В качестве критериев выбора выступают: Стоимость (К1), Дальность от областного центра (К2), Месторасположение в райцентре (К3) и наличие в райцентре квалифицированных сотрудников (К4). В результате экспертных исследований матрицы парных сравнений альтернатив по каждому критерию и критериев между собой имеют вид:

Откроем программу MS EXCEL. Введем исходные данные, учитывая, что 1/2=0,5; 1/3=0,333; 1/4=0,25; 1/5=0,2; 1/7=0,143. Подготовим также поля для собственных векторов и весов, а также поля для вычисления функции полезности альтернатив. Полученная картина в листе электронной таблицы должна быть такая же, как на рисунке.

Для вычисления собственных векторов (столбец F) необходимо перемножить данные столбцов В,С,D и Е для каждой альтернативы – строки и из полученных чисел извлечь корень четвертой степени.

Для этого ставим курсор в ячейку F3 и вводим функцию:

=СТЕПЕНЬ(ПРОИЗВЕД(B3:E3);0,25) (ссылка на ячейки B3:E3 вводится английскими буквами или путем обведения данных ячеек курсором мыши). Автозаполнением (за нижний правый угол) переносим формулу на диапазон F3-F24. Лишние данные из ячеек F7, F13 и F удаляем, поставив курсор в эти ячейки и нажав клавишу DELETE. В этих ячейках будут храниться суммы векторов. Также вычисляем вектора критериев. Ставим курсор в М3 и вводим формулу =СТЕПЕНЬ(ПРОИЗВЕД(I3:L3);0,25). Автозаполнением за нижний правый угол ячейки переносим данную формулу на М3-М6.

Далее вычисляем сумму элементов векторов. Ставим курсор в F7 и нажимаем кнопку вызывая мастер автосумм, обводим мышкой ячейки F3-F6, указав, какие ячейки просуммировать. Результат должен выглядеть так: =СУММ(F3:F6). Аналогично в ячейке F13 выводим сумму F9-F12 =СУММ(F8:F12), в ячейке F19 выводим сумму F15-F18 =СУММ(F15:F18), в ячейке F25 выводим сумму F21-F =СУММ(F21:F24), в ячейке М7 выводим сумму М3-М =СУММ(М3:М6).

Находим теперь веса альтернатив и критериев. Для этого вводим в G3 формулу =F3/$F$7 и автозаполняем ее на G3-G6. Аналогично вводим в G9 формулу =F9/$F$13 и автозаполняем ее на G9-G12, вводим в G15 формулу =F15/$F$19 и автозаполняем ее на G15-G18, вводим в G21 формулу =F21/$F$25 и автозаполняем ее на G21-G24, вводим в N3 формулу =M3/$M$7 и автозаполняем ее на N3-N6.

На последнем этапе вычисляем функции полезности альтернатив. Вводим в I10 формулу:

=G3*$N$3+G9*$N$4+G15*$N$5+G21*$N$ и автозаполняем данные на ячейки I10-I13. Видно, что максимальная функция полезности 0,334 у альтернативы С, следовательно ее нужно выбрать.

Задание для самостоятельного решения ЗАДАНИЕ. Предприниматель желает приобрести автомобиль.

Имеются 4 варианта покупки A,B,C и D. В качестве критериев выступают: Цена (К1), Комфортность (К2) и Экономичность (К3). Оценки парных сравнений альтернатив по каждому критерию и критериев между собой имеют вид:

ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

ПРИМЕР 1. Директор финансовой компании проводит рискованную финансовую операцию. Страховая компания предлагает застраховать сделку и предлагает 4 варианта страховки:

A1, A2, A3, A4. Компенсация ущерба для каждого варианта зависит от того, какой из возможных страховых случаев произошел. Выделяют 5 видов страховых случаев: S1, S2, S3, S4, S5. Компенсации (тыс. у.

е.) для каждого вида страховки при каждом страховом случае составляют матрицу выигрышей вида:

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при коэффициенте доверия 0,4.

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

Вычисляем функции полезности для критерия Лапласа. Для этого ставим курсор в ячейку G2 и вводим формулу, усредняющую значения показателей привлекательности по первой альтернативе. Для этого вызываем мастер функций, нажимая на кнопку fx и выбираем в категории «Статистические» функцию «СРЗНАЧ», в качестве аргумента функции указываем ячейки B2:F2, обводя их курсором. Нажимаем ОК, видим результат 40,2. Автозаполняем ячейки G2-G5, перетаскивая нижний правый уголок ячейки G2. Видно, что наибольшая функция полезности 40,4 для альтернативы А3. Вводим в G6: «А3».

Для критерия Вальда вычисляем наименьшие показатели привлекательности для каждой альтернативы. Для этого вводим в Н функцию МИН с аргументами B2:F2: «=МИН(B2:F2)» (кавычки не вводить!). Автозаполняем на Н2-Н5. Выбираем альтернативу, где результат наибольший. Это значение 37 для альтернативы А2, вводим в Н6: «А2».

Для критерия максимального оптимизма находим максимальные выигрыши для каждой альтернативы. Вводим в I2 формулу «=МАКС(B2:F2)», автозаполняем на I2-I5. Выбираем альтернативу с наибольшим показателем, это А4, вводим в I6: «А4».

Для критерия Сэвиджа необходимо построить матрицу рисков.

Для этого ставим курсор в ячейку В8 и вводим формулу «=МАКС(B$2:B$5)-B2», автозаполняем результат на ячейки В8-F11.

Далее находим максимальный риск для каждой альтернативы. Для этого ставим курсор в ячейку J2 и вводим «=МАКС(B8:F8)», автозаполняем результат на J2-J5. Выбираем альтернативу с минимальным риском, это А3. Вводим в J6: «А3».

Для критерия Гурвица нужно наибольшее значение каждой альтернативы умножить на (по условию 0,4 ), наименьшее на (1и результаты сложить. Вводим в К2 формулу:

=МАКС(B2:F2)*0,4+МИН(B2:F2)*0, и автозаполняем результат на К2-К5. Выбираем альтернативу с наибольшей функцией полезности. Это А3, вводим К6: «А3». Задача решена.

Рассмотрим теперь метод решения задачи в случае минимизации критерия – «чем меньше, тем лучше».

ПРИМЕР 2. Фермер, имея в аренде большие площади под посев кукурузы, заметил, что влажности почвы в сезон созревания кукурузы недостаточно, чтобы получить максимальный урожай. Эксперты советовали фермеру провести дренажные каналы в период конца весны – начала лета, что должно значительно повысить урожай. Были предложены 5 проектов дренажных каналов: A1, A2, A3, A4, A5, затраты на которые зависят от погодных условий в период весна – лето.

Возможны варианты: S1 – дождливая весна и дождливое лето; S2 – дождливая весна и сухое лето; S3 – сухая весна и дождливое лето; S4 – сухая весна и сухое лето. Матрица затрат имеет вид:

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при коэффициенте доверия 0,7.

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

Вычисляем функции полезности для критерия Лапласа. Для этого ставим курсор в ячейку F2 и вводим формулу:

«=СРЗНАЧ(В2:Е2)», автозаполняем на В2-Е6. Наилучшей в данном случае считается альтернатива с минимальной функцией полезности, это А2. Вводим в F7: «А2».

Для критерия Вальда вычисляем наибольшие показатели привлекательности для каждой альтернативы. Для этого вводим в G функцию «=МАКС(B2:E2)», автозаполняем на G2-G6. Выбираем альтернативу, где результат наименьший, вводим в G7: «А2».

Для критерия максимального оптимизма находим минимальные затраты для каждой альтернативы. Вводим в Н2 формулу «=МИН(B2:Е2)», автозаполняем на Н2-Н6. Выбираем альтернативу с наименьшим показателем, вводим в Н7: «А1».

Для критерия Сэвиджа необходимо построить матрицу рисков.

Для этого ставим курсор в ячейку В9 и вводим формулу «=B2МИН(B$2:B$6)», автозаполняем результат на ячейки В9-Е13. Далее находим максимальный риск для каждой альтернативы. Для этого ставим курсор в ячейку I2 и вводим «=МАКС(B9:E9)», автозаполняем результат на I2-I6. Выбираем альтернативу с минимальным риском, таких альтернатив две, это А2 и А4. Вводим в I7: «А2, А4».

Для критерия Гурвица нужно наименьшее значение каждой альтернативы умножить на (по условию 0,7 ), наибольшее на (1и результаты сложить. Вводим в J2 формулу:

и автозаполняем результат на J2-J6. Выбираем альтернативу с наименьшей функцией полезности. Это А1, вводим J7: «А1». Задача решена.

ЗАДАНИЕ № 1. Директор торговой фирмы, продающей телевизоры, решил открыть представительство в областном центре. У него имеются альтернативы либо создавать собственный магазин в отдельном помещении, либо организовывать сотрудничество с местными торговыми центрами. Всего можно выделить 5 альтернатив решения:

A1, A2, A3, A4, A5. Успех торговой фирмы зависит от того, как сложится ситуация на рынке предоставляемых услуг. Эксперты выделяют 4 возможных варианта развития ситуации S1, S 2, S3, S 4. Прибыль фирмы для каждой альтернативы при каждой ситуации представлена матрицей выигрышей a ij (млн. р./год).

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при коэффициенте доверия 0,6.

ЗАДАНИЕ № 2. Нефтяная компания собирается построить в районе крайнего севера нефтяную вышку. Имеется 4 проекта A, B, C и D. Затраты на строительство (млн. руб.) зависят от того, какие погодные условия будут в период строительства. Возможны 5 вариантов погоды S1, S2, S3, S4, S5. Выбрать оптимальный проект для строительства используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при 0,6. Матрица затрат имеет вид:

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при коэффициенте доверия 0,5.

МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ В УСЛОВИЯХ КОНФЛИКТА

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

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

не нанимать адвоката А1, нанять адвоката без проведения расследования А2, нанять адвоката с проведением дополнительного расследования А3, обратиться в частную юридическую организацию, имеющую собственную адвокатскую поддержку А4. Юристы выделили четыре стратегии поведения адвоката ответчика B1, B2, B3, B4. Оценки вероятностей выигрыша спора для истца (в процентах) при каждой возможной стратегии адвоката ответчика приведены в таблице: