Решение многокритериальной задачи линейного программирования

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

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

Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой ч-критериев (9), а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР Dx, заданной линейными ограничениями. Исходные условия записываем в каноническом виде: 1 = х1 - 2х2 - + 2, 2 = х1 + х2 - + 4, 3 = -х1 + 4х2 - + 20, 1 = -х1 - х2 + 15, 2 = 5х1 + х2 - 1, 3 = x1 - х2 + 5,

потом в виде с-таблицы: Т1х1х211-1-10152510-131-10511-2-12211-143-14-120Вводя в базис переменную (1 ), получаем обычную ЗЛП при максимизации ЦФ .

Т2х1х2111-1-10152510-131-1051-2-12203123-26118

Т33x211bi/ais11/2-4-1/266/42-5/2165/244-3-1/22214--1/21-1/211-203-12-х1-1/231/29- Т43111x23/2268317-3/8-1/4-5/825/2213/2х127/2 Решение ЗЛП приводит к конечной с-таблице Т4. Видно, что полученное гарантированное решение х -оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению - нижнего уровня ч-критериев (сj < 0). Из таблицы также видно, что решение х0=(27/2; 3/2) находится на грани 4, при этом значения ч-критериев равны (находим по формуле Lr(xr) = + r): L1 = L3 = = 25/2 L2 = + 2 = 25/2 + 13/2 = 19 L = 88/2 = 44 x = ( 27/2; 3/2) Если бы в строке имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня ). Это могло бы привести и к увеличению приращения r для некоторого ч-критерия, находящегося в базисе. 4.2.Метод линейной свертки частных критериев Линейная свертка ч-критериев получается как х сумма с некоторыми весовыми коэффициентами r:

где

Меняя порядок суммирования и вводя обозначения cj и c0, окончательно получим:

Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор = (r) суть вектор-градиент ЦФ L(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-го вида; i остаток ресурса i-го вида при плане выпуска x = (xj)n. Ч-критерии однородны, если они могут быть сведены к единой мере измерения. В качестве такой меры можно взять денежный эквивалент. Тогда m+2 ч-критерия могут быть с помощью линейной свертки сведены к трем: общая выручка (руб.):

общая экономия ресурсов (руб.):

налоговые отчисления (руб.):

где cj выручка от реализации 1 ед. продукции j-го вида (цена); si стоимость (цена) 1 ед. ресурса i-го вида (i = 1;m); Пj прибыль от реализации 1 ед. продукции j-го вида (j = 1;n); aj доля (процент налоговых отчислений от прибыли (выручки). В заключение заметим, что коэффициенты r не обязательно должны удовлетворять условию (10), но обязательно должны быть положительными, если все ч-критерии максимизируются.

Перейдем к решению:

Т1х1х211-1-115251-131-15L11-22L2114L3-1420L1326

Т21x21x1-1-1152-5-4743-1-220L1-1-117L2-1019L3155L-1241 L1 max = 17 L2 max = 19 L3 = 5 L = 41

Т31L11x128/32154/3326/3x217/3L219L3-2/3-5/3100/3L-5/3-2/3157/35. Составление сводной таблицы.

Окончательное решение сводится в таблицу, где записываются альтернативные варианты:

Методх0L1L2L3LМетод гарантированного результата (27/2 ; 3/2) 25/2 19 25/2 44Метод свертки(28/3;17/3)01933 1/352 1/3Оптимизация L1(15;0)1719541Оптимизация L2, L3(28/3;17/3)01933 1/352 1/3xDx(5;3)112-130