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

исходные данные:

L₁ = x₁ - 2x₂ + 2,

L₂ = x₁ + x₂ + 4,

L₃ = -x₁ + 4x₂ - 20,

в каноническом виде (после подстановки точки (5;3))

d¹ = x₁ - 2x₂ + 1, (5 - 2*3 + 1= 1)

D_x ^k d² = x₁ + x₂ - 8, (5 + 3 + 4 = 12)

d³ = -x₁ + 4x₂ - 7, (-5 + 4*3 - 20 = -13)

D = 2x₁ + 4x₂ – 14,

Находим точки для построения прямых:

1) d¹ = x₁ - 2x₂ + 1,

-x₁ + 2x₂ £ 1 (1;1)

2) d² = x₁ + x₂ - 8,

x₁ + x₂ ³8 (0;8)

3) d³ = -x₁ + 4x₂ - 7,

-x₁ + 4x₂ ³7 (1;2)

По полученным точкам строим график (рисунок 1). На рисунке штриховкой показан полученный д-конус. Переход к любой точке внутри конуса обеспечивает увеличение всех критериев. Точка (29/3; 16/3) является p-оптимальным решением. Смещая точку х^, внутрь д-конуса придем на границу e₁ . При этом д-конус выйдет из области допустимых решений (ОДР) D_x . Теперь полученная точка не сможет улучшить ни один ч-критерий без ухудшения других, значит она p-оптимальная. Построив д-конус в любой точке стороны e₁ , убеждаемся, что каждая из точек p-оптимальна, значит вся сторона e₁ составляет p-множество.

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 ) сформулировать и решить столько же ЗЛП размера R xn .

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