Актуальной является задача распределения ресурсов между альтернативами. В частности, интерес представляют задачи комбинаторной оптимизации, самая простая из которых — определение комбинации (альтернатив, проектов), максимизирующей "общие выгоды" при ограничениях на издержки.
Общая постановка задачи определения комбинации альтернатив с максимальной эффективностью (или эффективностью на единицу требуемого ресурса) заключается в определении сочетаний альтернатив, удовлетворяющих следующим целевым функциям:
при выполнении одного из следующих условий:
где Э — эффективность рассматриваемой комбинации альтернатив, полученной генерацией множества сочетаний с различным числом альтернатив;
Эi — эффективность i-й альтернативы, входящей в рассматриваемую комбинацию из п альтернатив;
РТ — требуемый ресурс рассматриваемой комбинации альтернатив;
Ри — имеющийся в наличии ресурс рассматриваемой комбинации альтернатив;
С— заданное пороговое значение ресурса.
Эффективность исходного множества альтернатив рассчитывается на основе МАИ и может быть определена либо на одной иерархии, отражающей критерии эффективности, либо на основе отражения значений векторов приоритетов альтернатив, характеризующих выгоды и издержки, получаемые от их реализации.
Существуют ситуации, в которых при распределении ресурсов руководствуются следующим правилом: делать как можно больше при ограниченных (имеющихся в наличии) ресурсах.
Целевая функция в данной задаче — обеспечить
при выполнении одного из условий
где Na — число альтернатив;
Аi — альтернатива, на которую распределяется ресурс.
Таким образом, для решения задачи комбинаторной оптимизации необходимо прежде всего сгенерировать множество всех возможных сочетаний (комбинаций) из п-го числа альтернатив. В указанное множество должны входить парные сочетания, тернарные сочетания и далее все п — 1 сочетания, а также сочетание, состоящее из всех п альтернатив.
Максимальное число возможных сочетаний NK для данной задачи определяется на основе следующей формулы:
где К— число альтернатив в i-й комбинации, принимающее значение в диапазоне [0,М];
М — максимальное число рассматриваемых альтернатив.
Определим множество комбинаций с различными числом и составом альтернатив.
Допустим, имеется множество из М альтернатив и каждой альтернативе соответствует ее уникальный порядковый номер.
Требуется из заданного множества получить комбинации всех возможных альтернатив, которые должны удовлетворять следующим условиям: 1) в каждой i-й комбинации не должно присутствовать одинаковых альтернатив;
2) каждая i-я комбинация должна отличаться от других не менее чем одной альтернативой;
3) комбинации альтернатив должны содержать в общем случае все единичные, парные, тернарные и другие М-1 и М сочетания альтернатив.
Каждой альтернативе в процессе генерации комбинаций присваиваются два типа признаков: "истина" (И) и "ложь" (Л).
В начальном состоянии всем альтернативам присваивается признак "ложь". В этом случае сгенерированная комбинация содержит нуль альтернатив. Далее осуществляется циклическое изменение признаков альтернатив и генерация из них новых комбинаций по следующим правилам.
Правило 1.
Если альтернатива А1 множества А имеет признак "Л", то изменяем его на признак "И" и заканчиваем изменение признаков у альтернатив. В противном случае, если альтернатива A1 множества А имеет признак "И", осуществляем переход к альтернативе А2.
Правило 2.
Если i-я альтернатива Ai множества А имеет признак "Л", то изменяем его на признак "И" и заканчиваем изменение признаков альтернатив. В противном случае изменяем признак i-й альтернативы Аi множества А на "Л" и осуществляем переход к i+1 альтернативе Аi+1.
Правило 3.
Если альтернатива АN множества А имеет признак "Л", то изменяем его на "И" и заканчиваем изменение признаков альтернатив. В противном случае, если альтернатива АN имеет значение признака "И", то генерируемая на данной итерации комбинация является последней и содержит все альтернативы множества А.
Таким образом, генерируемая на каждой итерации комбинация включает альтернативы множества А, имеющие на текущей итерации значение признака "Истина".
В табл. 2.11 приведен пример генерации комбинаций с учетом приведенного выше алгоритма для множества А, включающего три альтернативы.
Таблица 2.11 Алгоритм генерации альтернатив
|
Номер итерации |
Состояние множества альтернатив Аi |
Альтернативы, определяющие генерируемую комбинацию |
||
|
1 |
А1 "Л" |
А2 "Л" |
А3 "Л" |
- |
|
2 |
А1* "И" |
A2 "Л" |
А3 "Л" |
A1 |
|
3 |
А1 "Л" |
А2* "и" |
А3 "Л" |
A2 |
|
4 |
А1* "И" |
А2 "И" |
А3 "Л" |
А1А2 |
|
5 |
А1 "Л" |
А2 "Л" |
А3* "И" |
А3 |
|
6 |
А1* "И" |
А2 "Л" |
А3 "И" |
A1A3 |
|
7 |
A1 "Л" |
А2* "И" |
А3 "И" |
A2A3 |
|
8 |
А1* "И" |
А2 "И" |
A3 "И" |
A1A2A3 |
* - отмечен последний изменившийся на итерации признак.
Алгоритм определения комбинации альтернатив, обеспечивающей оптимальное распределение ресурса, имеет следующий вид.
Шаг 1.
Определяется М альтернатив, для каждой из которых устанавливается требуемый ресурс и вычисляется относительная эффективность.
Шаг 2.
Генерируются все парные, тернарные, М-1 комбинации альтернатив.
Шаг 3.
Для каждой сгенерированной комбинации определяются суммарные значения: требуемого ресурса, относительной эффективности и относительной эффективности на единицу требуемого ресурса.
Шаг 4.
Определяется искомая комбинация альтернатив с учетом задаваемой целевой функции.
Рассмотрим пример распределения ресурса на комбинации альтернатив, представляющих компьютерные бухгалтерские программы.
Заданы четыре компьютерные бухгалтерские программы: А1 — "1C:
Бухгалтерия 6.0. ПРОФ" для Windows 95;
А2 — "INFO-Бухгалтер";
А3 — Комплексная система "INOTEC Бухгалтер";
А4 — Бухгалтерская система "ПАРУС".
Относительная эффективность (полезность) бухгалтерских программ оценена по комплексу иерархически упорядоченных критериев качества с трех точек зрения: программиста, сопровождающего функционирование программ; бухгалтера, ведущего бухгалтерский анализ на предприятии; руководителя предприятия, использующего результаты бухгалтерского анализа для принятия решений (рис. 2.21).
Методом анализа иерархий определен вектор приоритетов альтернатив, характеризующий их относительную эффективность. Относительная эффективность бухгалтерских программ и требуемые для их приобретения ресурсы (в условных денежных единицах) приведены в табл. 2.12.
Таблица 2. 12 Исходные данные по эффективности и требуемому ресурсу
|
Параметр |
Альтернатива Ai |
|||
|
А1 |
А2 |
А3 |
А4 |
|
|
Относительная эффективность |
0,20 |
0,30 |
0,35 |
0,15 |
|
Требуемый ресурс |
5 |
5 |
10 |
3 |
Таблица 2.13 Результаты распределения ресурса
|
Параметр |
Комбинация альтернатив |
||||||
|
А1А2 |
А1А3 |
А1А4 |
A1A2A3 |
A1A3A4 |
A2A3A4 |
A1A2A3A4
|
|
|
Суммарная, эффективность комбинации |
0,50 |
0,555 |
0,35 |
0,85 |
0,70 |
0,80 |
1,0 |
|
Требуемый ресурс на комбинацию |
10 |
15 |
8 |
20 |
18 |
18 |
23 |
|
Эффективность на единицу ресурса |
0,050 |
0,037 |
0,044 |
0,043 |
0,039 |
0,044 |
0,043 |
Все возможные комбинации, состоящие из двух, трех и четырех альтернатив, суммарная эффективность комбинаций, требуемый на каждую операцию ресурс и эффективность на единицу ресурса приведены в табл. 2.13.
Требуется определить такие комбинации альтернатив, на которые наиболее целесообразно распределить имеющийся ресурс (15 единиц ресурса) с учетом целевых функций (2.12) и (2.13) при условии min (Ри - Рт).
Искомыми комбинациями альтернатив для первой целевой функции является А1 А2, а для второй — А1 А3.
