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

3.Определение Парето-оптимального множества

с-методом

3.1.Удаление пассивных ограничений

Перед построением p-множества из системы ограничений должны быть удалены пассивные ограничения. Пассивным будем называть неравенство (п-неравенство), граница которого не является частью границ области D_x, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы D_x, назовем активными (а-неравенства).

Чтобы грани не были включены в D_x^p, не имея никакого отношения к D_x^p, неравенство e₁ должно быть удалено из исходной системы ограничений. Условием для исключения неравенства e_i і 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии e_i = 0. Геометрически это означает, что граница e_i = 0 неравенства e_i і 0 не пересекается с областью D_x или имеет одну общую точку. Если граница e_i = 0 имеет общую угловую точку с D_x (вырожденность), то с удалением п-неравенства e_i і 0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы D_x.

В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки x О D_x будут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы.

Запишем систему неравенств D_x в форме с-таблицы:

ОП – получен, следовательно ОП – получен, следовательно

х₂ и e₁ – активные ограничения; x₁ и e₂ – активные ограничения;

из Т₂ получаем:

отсюда делаем вывод, что e₃ – активное ограничение;

из Т₃ получаем:

Опорный план не получен, следовательно e₄ – пассивное ограничение.

3.2.Определение p-множества с-методом.

При подготовке решения для ЛПР интерес будет представлять информация обо всем множестве p-оптимальных (эффективных) решений D_x^p. Графический метод позволяет сформулировать довольно простой подход к определению множества D_x^p. Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования д-конуса ( D_max > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х^,, то, помещая ее на границу e_i области D_x, решаем усеченную ЗЛП с добавлением e_i, соответствующего i-му участку границ D_x. Вырождение д-конуса в точку х^, будет признаком p-оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство указанного метода состоит в том, что потребуется на каждой грани ОДР D_x найти точку х^, (по числу граней D_x) сформулировать и решить столько же ЗЛП размера Rxn.

Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х^, = (1)_n и в нее же параллельно себе перенести грани, составляющие границы D_x

Приведенные к точке х^, = (1)_n приращения d^-r и невязки e_i запишутся в виде:

где черта сверху у 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), то предполагается, что он указывает направление к экстремуму неизвестной функции полезности. Положительная сторона такого подхода – несложность, не всегда компенсирует его серьезный недостаток – потерю физического смысла линейной свертки разнородных ч-критериев. Это затрудняет интерпретацию результатов, поэтому полученное таким путем решение, следует рассматривать только как возможный (альтернативный) вариант решения ЛПР. Для его сравнительного анализа следует привлекать