6. Задачи вычисления численных оценок

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

6.1. Процедура построения квазипорядка на множестве объектов (задача об упаковке)

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

Емкость контейнеров недостаточна для упаковки всех имеющихся объектов. Требуется упаковать максимальное число объектов, так чтобы:

1. Среди упакованных объектов было бы наибольшее количество таких, качество которых превосходило бы качество неупакованных (критерий О₂).

2. Число упакованных объектов было бы максимально возможным, так как все они в той или иной степени заслуживают

упаковки в емкости (предварительный отбор уже сделан) — критерий О₁.

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

Введем следующие обозначения: , еслиi-й объект упаковывается вl-й контейнер;, в противном случае;—j-й физический параметр i-го объекта;—j-й физический параметрl-го контейнера;— общая ценностьi-го объекта.

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

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

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

2. Упаковка многомерных объектов в контейнеры;

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

Введем обозначения: Q— число критериев;n— номер оценки по шкалеq-го критерия— множество оценокq-го критерия, расположенных в порядке возрастания их качества (шкалаq-го критерия):. — множество векторных оценок; качество каждого объектаоценивается вектором ,,.

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

1. Путем попарного сравнения упаковываемых объектов определяется асимметричное транзитивное отношение доминирования:

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

Будем называть допустимыми для опроса пары векторных оценок: ,. ЛПР предъявляется для сравнения допустимая пара векторных оценоки. Возможны следующие ответы ЛПР:

1. Первая альтернатива — предпочтительнее второй;

2. Вторая альтернатива — предпочтительней первой;

3. Альтернативы — равноценны;

4. Альтернативы — несравнимы между собой.

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

Алгоритм построения приведен на рис. 6.1:

Рис. 6.1. Алгоритм построения квазипорядка

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