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

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

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

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

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

L₂ = x₁ + x₂ + 4,

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

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

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

D_x^{k 2} = x₁ + x₂ - 8, (5 + 3 + 4 = 12)

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

= 2x₁ + 4x₂ – 14,

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

1. ¹ = x₁ - 2x₂ + 1,

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

1. ² = x₁ + x₂ - 8,

x₁ + x₂ 8 (0;8)

1. ³ = -x₁ + 4x₂ - 7,

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

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

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

с-методом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

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