4.Определение альтернативных вариантов многокритериальной задачи
Наиболее естественным и разумным решением мк-задачи было бы органическое объединение всех ч-критериев в виде единой ЦФ. Иногда это удается сделать путем создания более общей модели, в которой ч-критерии являются аргументами более общей целевой функции, объединяющей в себе все частные цели операции. На практике этого редко удается достигнуть, что, собственно, и является основной причиной появления проблемы многокритериальности. Однако наиболее распространенный подход к решению проблемы пока остается все-таки один: тем или иным путем свести решение мк-задачи к решению однокритериальной задачи. В основе подхода лежит предположение о существовании некой функции полезности, объединяющей в себе ч-критерии, но которую в явном виде, как правило, получить не удается. Получение наиболее обоснованной «свертки» ч-критериев является предметом исследований нового научного направления, возникшего в связи с проблемой многокритериальности - теории полезности. В данной работе будут рассмотрены некоторые подходы, позволяющие получить варианты решения мк-задач при тех или иных посылках и которые лицо принимающее решение (ЛПР) должно рассматривать как альтернативные при принятии окончательного решения и которые, конечно, должны удовлетворять необходимому условию- p-оптимальности.
При любом произвольном решении х ÎDx каждый из ч-критериев примет определенное значение и среди них найдется, по крайней мере, один, значение которого будет наименьшим:
Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой ч-критериев (9), а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР Dx, заданной линейными ограничениями.
Исходные условия записываем в каноническом виде:
d1 = х1 - 2х2 - j + 2,
d2 = х1 + х2 - j + 4,
d3 = -х1 + 4х2 - j + 20,
e1 = -х1 - х2 + 15,
e2 = 5х1 + х2 - 1,
e3 = x1 - х2 + 5,
потом в виде с-таблицы:
Т1 | х1 | х2 | j | 1 |
e1 | -1 | -1 | 0 | 15 |
e2 | 5 | 1 | 0 | -1 |
e3 | 1 | -1 | 0 | 5 |
d1 | 1 | -2 | -1 | 2 |
d2 | 1 | 1 | -1 | 4 |
d3 | -1 | 4 | -1 | 20 |
Вводя в базис переменную j (d1«j), получаем обычную ЗЛП при максимизации ЦФ j.
Т2 | х1 | х2 | d1 | 1 |
e1 | -1 | -1 | 0 | 15 |
e2 | 5 | 1 | 0 | -1 |
e3 | 1 | -1 | 0 | 5 |
j | 1 | -2 | -1 | 2 |
d2 | 0 | 3 | 1 | 2 |
d3 | -2 | 6 | 1 | 18 |
Т3 | d3 | x2 | d1 | 1 | bi/ais |
e1 | 1/2 | -4 | -1/2 | 6 | 6/4 |
e2 | -5/2 | 16 | 5/2 | 44 | - |
e3 | -1/2 | 2 | 2 | 14 | - |
j | -1/2 | 1 | -1/2 | 11 | - |
d2 | 0 | 3 | -1 | 2 | - |
х1 | -1/2 | 3 | 1/2 | 9 | - |
Т4 | d3 | e1 | d1 | 1 |
x2 | 3/2 | |||
e2 | 68 | |||
e3 | 17 | |||
j | -3/8 | -1/4 | -5/8 | 25/2 |
d2 | 13/2 | |||
х1 | 27/2 |
Решение ЗЛП приводит к конечной с-таблице Т4. Видно, что полученное гарантированное решение х p-оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению j - нижнего уровня ч-критериев ("сj < 0). Из таблицы также видно, что решение х0=(27/2; 3/2) находится на грани e4, при этом значения ч-критериев равны (находим по формуле Lr(xr) = j + dr):
L1 = L3 =j = 25/2
L2 = j + d2 = 25/2 + 13/2 = 19
LS = 88/2 = 44
x° = ( 27/2; 3/2)
Если бы в строке j имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня j). Это могло бы привести и к увеличению приращения dr для некоторого ч-критерия, находящегося в базисе.
4.2.Метод линейной свертки частных критериев
Линейная свертка ч-критериев получается как х сумма с некоторыми весовыми коэффициентамиmr:
где
Меняя порядок суммирования и вводя обозначения cj и c0, окончательно получим:
Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор m = (mr) – суть вектор-градиент ЦФ Lm(x), то предполагается, что он указывает направление к экстремуму неизвестной функции полезности. Положительная сторона такого подхода – несложность, не всегда компенсирует его серьезный недостаток – потерю физического смысла линейной свертки разнородных ч-критериев. Это затрудняет интерпретацию результатов, поэтому полученное таким путем решение, следует рассматривать только как возможный (альтернативный) вариант решения ЛПР. Для его сравнительного анализа следует привлекать любые другие варианты и, конечно, значения ч-критериев, получаемые при этом. Иногда при получении свертки ч-критериев предварительно нормируются каким-нибудь способом.
Наиболее приемлемой линейная свертка ч-критериев может оказаться в том случае, когда ч-критерии однородны и имеют единый эквивалент, согласующий их наиболее естественным образом.
На содержательном уровне данная МЗЛП состоит в необходимости принятия такого компромиссного решения (плана выпуска продукции) xkÎDx, которое обеспечит, по возможности, наибольшую суммарную выручкуL1(x) от реализации произведенной продукции; наименьший расход ресурсов i-го вида Lpl (x) (i = 1; m); минимальные налоговые отчисления от прибыли LH(x) (или общей выручки).
Указанные цели носят противоречивый характер, и фактически мы имеем МЗЛП с m+2 –мя ч-критериями (m – количество видов потребляемых ресурсов). ОДР обусловлена ресурсными ограничениями и условиями неотрицательных переменных:
где aij – расход ресурса i-го вида для выпуска 1 единицы продукции j-го вида (j=1,n);
bi – запас ресурса i-го вида;
ei – остаток ресурса i-го вида при плане выпуска x = (xj)n. Ч-критерии однородны, если они могут быть сведены к единой мере измерения. В качестве такой меры можно взять денежный эквивалент. Тогда m+2 ч-критерия могут быть с помощью линейной свертки сведены к трем:
общая выручка (руб.):
общая экономия ресурсов (руб.):
налоговые отчисления (руб.):
где cj – выручка от реализации 1 ед. продукции j-го вида (цена); si – стоимость (цена) 1 ед. ресурса i-го вида (i = 1;m); Пj – прибыль от реализации 1 ед. продукции j-го вида (j = 1;n); aj – доля (процент налоговых отчислений от прибыли (выручки).
В заключение заметим, что коэффициенты mr не обязательно должны удовлетворять условию (10),но обязательно должны быть положительными, если все ч-критерии максимизируются.
Перейдем к решению:
Т1 | х1 | х2 | 1 |
e1 | -1 | -1 | 15 |
e2 | 5 | 1 | -1 |
e3 | 1 | -1 | 5 |
L1 | 1 | -2 | 2 |
L2 | 1 | 1 | 4 |
L3 | -1 | 4 | 20 |
LS | 1 | 3 | 26 |
Т2 | e1 | x2 | 1 |
x1 | -1 | -1 | 15 |
e2 | -5 | -4 | 74 |
e3 | -1 | -2 | 20 |
L1 | -1 | -1 | 17 |
L2 | -1 | 0 | 19 |
L3 | 1 | 5 | 5 |
LS | -1 | 2 | 41 |
L1max = 17
L2 max = 19
L3 = 5
LS= 41
Т3 | e1 | L1 | 1 |
x1 | 28/3 | ||
e2 | 154/3 | ||
e3 | 26/3 | ||
x2 | 17/3 | ||
L2 | 19 | ||
L3 | -2/3 | -5/3 | 100/3 |
LS | -5/3 | -2/3 | 157/3 |
5. Составление сводной таблицы.
Окончательное решение сводится в таблицу, где записываются альтернативные варианты:
Метод | х0 | L1 | L2 | L3 | LS |
Метод гарантированного результата | (27/2 ; 3/2) | 25/2 | 19 | 25/2 | 44 |
Метод свертки | (28/3;17/3) | 0 | 19 | 33 1/3 | 52 1/3 |
Оптимизация L1 | (15;0) | 17 | 19 | 5 | 41 |
Оптимизация L2, L3 | (28/3;17/3) | 0 | 19 | 33 1/3 | 52 1/3 |
xÏDxp | (5;3) | 1 | 12 | -13 | 0 |