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

2.2. Графическое определение p-множества

Сначала необходимо построить график.

Для построения графика необходимы следующие данные:

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

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^kd² = 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 в форме с-таблицы:

Т1	х1	х2	1	bi/ais	bi/ais
e1	-1	-1	15	15	15
e2	5	1	-1	1/5	1
e3	1	-1	5	-	5
e4	0	-1	20	-	20

Т2	e1	x2	1	Т2’	x1	e2	1
х1	-1	-1	15	e1	4	-1	14
e2	-5	-4	74	x2	-5	1	1
e3	-1	-2	20	e3	2	-1	4
e4	0	-1	20	e4	1	-1	19

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

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

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

Т3	e1	e3	1
x1	1	1/2	5
e2	-3	2	34
x2	-1/2	-1/2	10
e4	2	½	10

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

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

Т4	e4	e3	1
x1	10
e2	19
x2	15/2
e1	-5

Опорный план не получен, следовательно 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₁:

Т1	х1	х2	1
e2	-1	-1	2
e3	5	1	-6
e4	1	-1	0
х1	1	0	-1
х2	0	1	-1
d1	1	-2	1
d2	1	1	-2
d3	-1	4	-3
D	1	3	-4