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

штриховкой). При R > n д-конус может выродиться в точку х, (вершина д-конуса). Получено целое множество оптимальных решений, извлекаемое из Т3: х0 = ( 29/3 ; 16/3 ). Таким образом, решение х, = ( 5; 3) не является -оптимальным, так как его удалось улучшить (max>0). Помимо установления факта неэффективности решения х,, рассмотренный метод позволил определить ближайшее к нему -оптимальное решение.

2.2. Графическое определение -множества Сначала необходимо построить график. Для построения графика необходимы следующие данные: исходные данные: L1 = x1 - 2x2 + 2, L2 = x1 + x2 + 4, L3 = -x1 + 4x2 - 20, в каноническом виде (после подстановки точки (5;3)) 1 = x1 - 2x2 + 1, (5 - 2*3 + 1= 1) Dxk 2 = x1 + x2 - 8, (5 + 3 + 4 = 12) 3 = -x1 + 4x2 - 7, (-5 + 4*3 - 20 = -13) = 2x1 + 4x2 14, Находим точки для построения прямых: 1) 1 = x1 - 2x2 + 1, -x1 + 2x2 1 (1;1)

2) 2 = x1 + x2 - 8, x1 + x2 8 (0;8)

3) 3 = -x1 + 4x2 - 7, -x1 + 4x2 7 (1;2)

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

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

3.1.Удаление пассивных ограничений Перед построением -множества из системы ограничений должны быть удалены пассивные ограничения. Пассивным будем называть неравенство (п-неравенство), граница которого не является частью границ области Dx, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы Dx, назовем активными (а-неравенства). Чтобы грани не были включены в Dx, не имея никакого отношения к Dx, неравенство 1 должно быть удалено из исходной системы ограничений. Условием для исключения неравенства i 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии i = 0. Геометрически это означает, что граница i = 0 неравенства i 0 не пересекается с областью Dx или имеет одну общую точку. Если граница i = 0 имеет общую угловую точку с Dx (вырожденность), то с удалением п-неравенства i 0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы Dx. В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки x Dx будут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы. Запишем систему неравенств Dx в форме с-таблицы:

Т1х1х21bi/aisbi/ais1-1-1151515251-11/5131-15-540-120-20

Т21x21Т2x121х1-1-11514-1142-5-474x2-5113-1-22032-1440-12041-119 ОП получен, следовательно ОП получен, следовательно х2 и 1 активные ограничения; x1 и 2 активные ограничения;

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

Т3131x111/252-3234x2-1/2-1/21042Ѕ10 отсюда делаем вывод, что 3 активное ограничение;

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

Т4431x110219x215/21-5 Опорный план не получен, следовательно 4 пассивное ограничение.

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

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

где черта сверху у , и означает, что эти величины приведены к точке х, = (1)n. По существу, (8) ЗЛП размера (R+m)xn (max), а ее решение позволит найти все грани, составляющие -множество Dx. Составляем с-таблицу, не учитывая пассивные ограничения, т.е 1:

Т1х1х212-1-12351-641-10х110-1х201-111-21211-23-14-3 13-4 В начале решается усеченная ЗЛП (под чертой):

Т2х1111-3/21/23/2211/2-1/2-11/231/21/2-1/2х110-1х21/2-1/2-1/2x21/2-1/21/223/2-1/2-3/231-2-15/2-3/2-5/2 Т33111-3/2-5/20211/221/2031/23/20х1120х21/21/20x21/21/2123/25/20x11215/27/20

Т411130x2120x11-5/3-2/30 1 Dx, так как max = 0.

Данный метод построения множества Dx обладает недостатком, связанным с разрушением области допустимых решений (ОДР) Dx при переносе ее граней в х,. Действительно, вершины области Dx в преобразованной модели никак не отражены, а именно одна из них может составить -множество в случае его совпадения с оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы угол при вершине д-конуса приближается к 180 (градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если в -множество не вошла ни одна из граней ОДР Dx. Следовательно, -множество совпадает с оптимальным решением. Для определения -множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и является -множеством. Для ЛПР указание на то, что некоторая грань i = i Dx -оптимальна, является только обобщенной информацией.

4.Определение альтернативных вариантов многокритериальной задачи Наиболее естественным и разумным решением мк-задачи было бы органическое объединение всех ч-критериев в виде единой ЦФ. Иногда это удается сделать путем создания более общей модели, в которой ч-критерии являются аргументами более общей целевой функции, объединяющей в себе все частные цели операции. На практике этого редко удается достигнуть, что, собственно, и является основной причиной появления проблемы многокритериальности. Однако наиболее распространенный подход к решению проблемы пока остается