Общая классификация эвристических методов решения многокритериальных задач

Основными методами решения многокритериальных задач являются:

- принцип равномерности;

- принцип справедливой уступки;

- принцип выделения одного оптимизируемого критерия;

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

- метод идеальной точки.

Принцип равномерности провозглашает целесообразность выбора такого варианта решения, при котором достигалась бы некоторая “равномерность” показателей по всем локальным критериям. Используют следующие реализации принципа равномерности:

- принцип равенства;

- принцип максимина;

- принцип квазиравенства.

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

- оптимальным считается вариант, принадлежащий области компромиссов, при котором все значения локальных критериев равны между собой. Однако случай f₁=f₂=…=f_k может не попасть в область компромиссов или вообще не принадлежать к области допустимых вариантов.

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

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

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

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

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

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

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

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

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

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

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

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

Практический блок

Пример 1

Предприниматель покупает в одном месте мужские свитера (в количестве не более 60 штук), в другом — женские (не более 40 штук). С помощью мягкой щетки он делает начес и продает по 2 условные единицы за мужские и по 4 единицы за женские. За некоторый единичный интервал времени он может начесать не более 80 свитеров. Поскольку предприниматель хочет удержаться и на рынке мужских свитеров (М), и на рынке женских свитеров (Ж), постольку он интересуется не максимумом суммарного дохода или прибыли, а оценками сразу по нескольким критериям. Пусть закупочные цены в условных единицах таковы: мужские свитера по 1 ед/шт., женские по 2 ед/шт. Оптимизационная задача предпринимателя выглядит так (х_м, х_ж— объемы закупок):

F₁=2х_м → max,

F₂=4х_ж → max,

F₃= х_м +2х_ж → min,

0 ≤ х_м ≤60,

0 ≤ х_ж ≤40,

х_ж + х_м ≤80.

хм
А		В
				С
О				D							хж

Рис. 2.9.6. Иллюстрация к примеру задачи с тремя критериями

На рис. 2.9.6 показана допустимая область OABCD. Отдельно по каждому из критериев решения находятся сразу (по F₁: x_м = 60, F₁ = 120; по F₂: x_ж = 40, F₂ = 160; по F₃: x_м = х_ж = 0, F₃ = 0;), отрезок ВС является множеством точек, оптимальных по Парето по совокупности критериев F₁ и F₂. Среди этих точек оптимум по F₃ достигается в точке С (F₃=120, x_м=х_ж=40, F₁=80, F₂=160). Допустим, зная ситуацию на рынках и свои финансовые возможности, этот предприниматель выбирает такие пороги: f₁ = 100 (то есть он хочет иметь F₁ ≥f₁ = 100), f₂ = 112 (хочет иметь F₂ ≥f₂ = 112), что дает задачу х_м ≥50, х_ж ≥28 с целевой функцией F₃. Ясно, что в этом случае решением будет х_м = 50, х_ж = 28 с F₃ =106.

Пример 2

Необходимо обеспечить бесперебойную работу организации – своевременное снабжение сырьем и материалами. Для выбора поставщика продукции руководством фирмы определены следующие критерии: ассортимент продукции, качество поставляемых продуктов, стоимость, наличие сервиса, надежность поставок. При этом в качестве альтернатив рассматриваются следующие поставщики: фирма ОАО «Меркурий», фирма ОАО «Прометей», фирма ОАО «Везувий», фирма ООО «Находка», фирма ОАО «Мегатрон+».

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

Исследование поставщиков Таблица 2.9.3

Определим важность каждого критерия в табл. 2.9.4. При этом используют соответствующую шкалу оценок от 0 до 9 (табл. 2.9.2).

Определение важности критериев Таблица 2.9.4

Важности критериеви нормализованные оценкиопределяем по формулам (9.2.3) – (9.2.4).

l_max =20,33∙0,5193+27∙0,02975+9,37∙0,14331+4,625∙0,2706+2,07∙0,50439=5,42;

ИС=(5,42 - 5)/4=0,105; СС=1.98(5-2)/5=1.188;

Отношение согласованности ОС=ИС/СС = 8,84% < 10%.

Проведем оценку альтернатив по каждому критерию.

По критерию «ассортимент» получим результаты, приведенные в табл. 2.9.5.

Парное сравнение альтернатив по критерию «ассортимент» Таблица 2.9.5

Отношение согласованности ОС = 0,00% < 10%.

По критерию «качество» получим результаты, приведенные в табл. 2.9.6.

Парное сравнение альтернатив по критерию «качество» Таблица 2.9.6

Отношение согласованности ОС = 6,13% < 10%.

По критерию «стоимость» получим результаты, приведенные в табл. 2.9.7.

Парное сравнение альтернатив по критерию «стоимость» Таблица 2.9.7

Отношение согласованности ОС = 2,97% < 10%.

По критерию «сервис» получим результаты, приведенные в табл. 2.9.8.

Парное сравнение альтернатив по критерию «сервис» Таблица 2.9.8

Отношение согласованности ОС = 1,4% < 10%.

По критерию «надежность» получим результаты, приведенные в табл. 2.9.9.

Парное сравнение альтернатив по критерию «надежность» Таблица 2.9.9

Отношение согласованности ОС = 2,33% < 10%.

Составим итоговую таблицу оценки альтернатив по установленным критериям (табл. 2.9.10).

Оценка альтернатив с учетом важности критериев Таблица 2.9.10

Следует остановить свой выбор на альтернативе с максимальным значением глобального приоритета = 0.439640

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

1. Многокритериальная задача и её экономическая интерпретация.

2. Понятие оптимума по Парето и его экономическая интерпретация.

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

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

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

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

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

8. Многокритериальная задача при заданных уровнях насыщения целей и её приложение к проблемам менеджмента.

Тесты

1. Как поступить лучше в случае, если приходится оценивать эффективность операции по нескольким показателям?

а) сузить множество возможных решений за счет отсечения заведомо неудачных, уступающих другим по всем критериям;

б) свести многокритериальную задачу к дроби;

в) свести многокритериальную задачу к взвешенной сумме частных показателей;

г) содержание п. а, б;

д) содержание п. а, в;

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

а) он помогает “выбраковать” из множества возможных решений Х заведомо неудачные, уступающие другим по всем критериям;

б) он позволяет решать прямые задачи исследования операций;

в) он помогает “выбраковать” из множества возможных решений Х заведомо удачные;

г) содержание п. а, б;

д) содержание п. а, в;

3. Какие существуют пути построения компромиссного решения?

а) выделить один (главный) показатель F1 и стремиться его обратить в максимум, а на все остальные F2, F3, ... наложить только некоторые ограничения, потребовав, чтобы они были не меньше каких-то заданных чисел;

б) “методом последовательных уступок”;

в) волевым актом “начальника”;

г) выделить один (главный) показатель F1 и стремиться его обратить в максимум;

д) содержание п. а, б;

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

а) область согласия;

б) область компромиссов;

в) область сглаживания.

5. Какая из схем компромисса многокритериальных задач допускает увеличение одного критерия при сравнительно малых значениях других критериев?

а) относительной уступки;

б) абсолютной уступки;

в) справедливой уступки.

6. Какая схема компромисса не требует нормализации критериев?

а) относительной уступки;

б) абсолютной уступки;

в) справедливой уступки.

Ответы к тестам

Задания и задачи

1. Множество допустимых планов описывается системой неравенств:

0£х£1,

0£у£1.

Заданы две целевые функции

F₁=2x —>max,

F₂=x – y - 1 —>min.

Найти идеальную точку.

2. Множество допустимых планов описывается системой неравенств:

0£х£1,

0£у£1.

Заданы две целевые функции

F₁=2x+1—>max,

F₂=2у + 3 —>mах.

Найти идеальную точку.

3. Множество допустимых планов описывается системой неравенств:

0£х£2,

0£у£4,

2х+у£6.

Заданы две целевые функции

F₁=x + у +2—>max,

F₂=x – y + 6 —>mах.

Найти идеальную точку.

4. Фирма имеет возможность реализовывать свои товары на 4-х различных рынках. Затраты на рекламу на этих рынках составляют соответственно 7, 5, 9, и 6 тыс. денежных единиц, доля рынка - 45, 40, 50 и 45 процентов, а объем продаж - 90, 85, 80 и 83 тыс. штук. При этом ставятся одновременно следующие цели: минимизация затрат на рекламу, завоевание максимальной доли рынка и максимизация объема продаж в течение планируемого периода. Построить математическую модель и предложить метод решения.

5. (В задачах 5-8 конкретные значения координат точек р1, р2, р3 задать самотоятельно). Два города р1 и р2 (рис.2.9.7) решили на трассе р11-р12 построить завод (р) по переработке отходов. Возможны разные варианты: первый и второй города стремятся построить завод р как можно ближе, чтобы общее расстояние (s3=s1+s2) до завода было минимальным, второй город имеет приоритет, на одинаковом расстоянии (s1=s2), или первый город стремиться построить завод как можно дальше, второй город - как можно ближе и т.д. Решить для первого случая - определить частную цель для первого города, или тоже самое: найти наикратчайшее расстояние от точки р1 до прямой р11-р12.

рис. 2.9.7

6. Смоделировать и решить следующие задачи (данные в зад.5):

1) 1-й город стремится построить завод р как можно ближе (s1→ min).

2) 2-й город стремится построить завод ближе (s2→ min).

3) Решили, чтоб (s3=s1+s2) было минимальным (s3→ min).

4) Второй город имеет приоритет 2 (s4=s1+2.*s2) (s4→ min).

5) Города хотят построить завод на одинаковом расстоянии (s1=s2).

6) 1-й город стремиться построить завод как можно дальше (s1→ max), 2-й город - ближе (s2→ min).

7. Три города р1, р2, р3 решили также на трассе р11-р12 построить завод р по переработке отходов. Определить ЧЦФ и общее минимальное расстояние (поиск ГЦФ). Укажите зону решений в случае компромисса (все заводы решили построить завод на одинаковом расстоянии).

8. Три города р1, р2, р3 решили в плоскости треугольника, образованного их расположением построить завод р по переработке отходов. Определить местоположение завода таким, чтобы сумма расстояний от городов до него была минимальной. Определите зоны Парето при противоречивых условиях.

9. Руководителю фирмы требуется решить, какую программу для бухучета следует приобрести. Альтернативы – предлагаемые на рынке программы: «1С», «Парус», «С2», «Бухгалтер-3», «программа, изготовленная на заказ». Факторы, определяющие выбор, – параметры программы: стоимость, защищенность информации, гибкость настройки, расширяемость, нетребовательность к ресурсам. С помощью метода анализа иерархий составить рейтинг программ.

10. Для разработки некоторого нефтяного месторождения в результате анализа его геолого-геофизических и геолого-гидродинамических характеристиках определено три благоприятных технологических варианта разработки: законтурное заводнение (D1), циклическое заводнение (D2), циклическое заводнение в сочетании паротепловой обработкой скважин на всех объектах разработки (D3).

Из множества показателей эффективности разработки месторождений нефти и газа руководитель выбрал следующие показатели (критерии):

В1. Экономические показатели

С1. Чистый дисконтированный доход

С2. Внутренняя норма рентабельности

СЗ. Срок окупаемости

С4. Индекс доходности

В2. Риски

С5. Оправданность выбора технических решений (вариантов разработки)

Сб. Надежность контроля за выработкой запасов

С7. Экономический риск

В3. Охрана окружающей среды и недр

С8. Загрязнение воздуха и воды

С9. Сохранность флоры и фауны

Эти показатели образуют следующую иерархию (рис. 2.9.8).

Рис. 2.9.8

Здесь буквами В обозначены виды критериев (показателей) эффективности разработки месторождений, буквы С обозначают конкретные критерии, буквы D – варианты разработки.

Пусть матрицы парных сравнений оказались следующими (табл. 2.9.11):

Таблица 2.9.11

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