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

где черта сверху у d, e и D означает, что эти величины приведены к точке х^, = (1)_n .

По существу, (8) – ЗЛП размера (R+m)xn (D®max), аее решение позволит найти все грани, составляющие p-множество D_x ^p .

Составляем с-таблицу, не учитывая пассивные ограничения, т.е e₁ :

В начале решается усеченная ЗЛП (под чертой):

e₁ ÎD_x ^p , так как D_max = 0.

Данный метод построения множества D_x ^p обладает недостатком, связанным с разрушением области допустимых решений (ОДР) D_x при переносе ее граней в х^, . Действительно, вершины области D_x в преобразованной модели никак не отражены, а именно одна из них может составить p-множество в случае его совпадения с оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы – угол при вершине д-конуса приближается к 180° (градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если в p-множество не вошла ни одна из граней ОДР D_x . Следовательно, p-множество совпадает с оптимальным решением. Для определения p-множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и является p-множеством. Для ЛПР указание на то, что некоторая грань e_i = e_i ^p ÎD_x ^p p-оптимальна, является только обобщенной информацией.

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

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

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

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

Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой ч-критериев (9), а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР D_x , заданной линейными ограничениями.

Исходные условия записываем в каноническом виде:

d¹ = х₁ - 2х₂ - j + 2,

d² = х₁ + х₂ - j + 4,

d³ = -х₁ + 4х₂ - j + 20,

e₁ = -х₁ - х₂ + 15,

e₂ = 5х₁ + х₂ - 1,

e₃ = x₁ - х₂ + 5,

потом в виде с-таблицы:

Вводя в базис переменную j (d¹ «j), получаем обычную ЗЛП при максимизации ЦФ j.

Решение ЗЛП приводит к конечной с-таблице Т₄ . Видно, что полученное гарантированное решение х p-оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению j - нижнего уровня ч-критериев ("с_j < 0). Из таблицы также видно, что решение х⁰ =(27/2; 3/2) находится на грани e₄ , при этом значения ч-критериев равны (находим по формуле L^r ( x^r ) = j + d ^r ):

L₁ = L₃ =j = 25/2

L₂ = j + d₂ = 25/2 + 13/2 = 19

L^S = 88/2 = 44

x° = ( 27/2; 3/2)

Если бы в строке j имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня j). Это могло бы привести и к увеличению приращения d^r для некоторого ч-критерия, находящегося в базисе.

4.2.Метод линейной свертки частных критериев

Линейная свертка ч-критериев получается как х сумма с некоторыми весовыми коэффициентами m_r :

где

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

Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор m = (m_r ) – суть вектор-градиент ЦФ L^m (x), то предполагается, что он указывает направление к экстремуму неизвестной функции полезности . Положительная сторона такого подхода – несложность, не всегда компенсирует его серьезный недостаток – потерю физического смысла линейной свертки разнородных ч-критериев. Это затрудняет интерпретацию результатов, поэтому полученное таким путем решение, следует рассматривать только как возможный (альтернативный) вариант решения ЛПР. Для его сравнительного анализа следует привлекать любые другие варианты и, конечно, значения ч-критериев, получаемые при этом. Иногда при получении свертки ч-критериев предварительно нормируются каким-нибудь способом.

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