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

Перед построением 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-оптимальности.