Смекни!
smekni.com
Экономико-математическое моделирование

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

4.Определение альтернативных вариантов многокритериальной задачи

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

4.1.Метод гарантированного результата

При любом произвольном решении х Î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
 
назад
1
2
3
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.