Реферат: Решение многокритериальной задачи линейного програмирования
Dxk d2 = x1 + x2 - 8, (5 + 3 + 4 = 12)
d3 = -x1 + 4x2 - 7, (-5 + 4*3 - 20 = -13)
D = 2x1 + 4x2 – 14,
Находим точки для построения прямых:
1) d1 = x1 - 2x2 + 1,
-x1 + 2x2 £ 1 (1;1)
2) d2 = x1 + x2 - 8,
x1 + x2 ³ 8 (0;8)
3) d3 = -x1 + 4x2 - 7,
-x1 + 4x2 ³ 7 (1;2)
По полученным точкам строим график (рисунок 1). На рисунке штриховкой показан полученный д-конус. Переход к любой точке внутри конуса обеспечивает увеличение всех критериев. Точка (29/3; 16/3) является p-оптимальным решением. Смещая точку х, внутрь д-конуса придем на границу e1. При этом д-конус выйдет из области допустимых решений (ОДР) Dx. Теперь полученная точка не сможет улучшить ни один ч-критерий без ухудшения других, значит она p-оптимальная. Построив д-конус в любой точке стороны e1, убеждаемся, что каждая из точек p-оптимальна, значит вся сторона e1 составляет p-множество.
3.Определение Парето-оптимального множества
с-методом
3.1.Удаление пассивных ограничений
Перед построением p-множества из системы ограничений должны быть удалены пассивные ограничения. Пассивным будем называть неравенство (п-неравенство), граница которого не является частью границ области Dx, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы Dx, назовем активными (а-неравенства).
Чтобы грани не были включены в Dxp, не имея никакого отношения к Dxp, неравенство e1 должно быть удалено из исходной системы ограничений. Условием для исключения неравенства ei ³ 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии ei = 0. Геометрически это означает, что граница ei = 0 неравенства ei ³ 0 не пересекается с областью Dx или имеет одну общую точку. Если граница ei = 0 имеет общую угловую точку с Dx (вырожденность), то с удалением п-неравенства ei ³ 0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы Dx.
В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки x Î Dx будут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы.
Запишем систему неравенств Dx в форме с-таблицы:
|
Т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 |
ОП – получен, следовательно ОП – получен, следовательно
х2 и e1 – активные ограничения; x1 и e2 – активные ограничения;
из Т2 получаем:
|
Т3 |
e1 |
e3 |
1 |
|
x1 |
1 | 1/2 | 5 |
|
e2 |
-3 | 2 | 34 |
|
x2 |
-1/2 | -1/2 | 10 |
|
e4 |
2 | ½ | 10 |
отсюда делаем вывод, что e3 – активное ограничение;
из Т3 получаем:
|
Т4 |
e4 |
e3 |
1 |
|
x1 |
10 | ||
|
e2 |
19 | ||
|
x2 |
15/2 | ||
|
e1 |
-5 |
Опорный план не получен, следовательно e4 – пассивное ограничение.
3.2.Определение p-множества с-методом.
При подготовке решения для ЛПР интерес будет представлять информация обо всем множестве p-оптимальных (эффективных) решений Dxp. Графический метод позволяет сформулировать довольно простой подход к определению множества Dxp. Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования д-конуса ( Dmax > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х,, то, помещая ее на границу ei области Dx, решаем усеченную ЗЛП с добавлением ei, соответствующего i-му участку границ Dx. Вырождение д-конуса в точку х, будет признаком p-оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство указанного метода состоит в том, что потребуется на каждой грани ОДР Dx найти точку х, (по числу граней Dx) сформулировать и решить столько же ЗЛП размера Rxn.
Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х, = (1)n и в нее же параллельно себе перенести грани, составляющие границы Dx
Приведенные к точке х, = (1)n приращения d-r и невязки ei запишутся в виде:
|
где черта сверху у d, e и D означает, что эти величины приведены к точке х, = (1)n.
По существу, (8) – ЗЛП размера (R+m)xn (D®max), а ее решение позволит найти все грани, составляющие p-множество Dxp.
Составляем с-таблицу, не учитывая пассивные ограничения, т.е e1:
|
Т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 |
В начале решается усеченная ЗЛП (под чертой):
|
Т2 |
х1 |
d1 |
1 |
|
e1 |
-3/2 | 1/2 | 3/2 |
|
e2 |
11/2 | -1/2 | -11/2 |
|
e3 |
1/2 | 1/2 | -1/2 |
|
х1 |
1 | 0 | -1 |
|
х2 |
1/2 | -1/2 | -1/2 |
|
x2 |
1/2 | -1/2 | 1/2 |
|
d2 |
3/2 | -1/2 | -3/2 |
|
d3 |
1 | -2 | -1 |
| D | 5/2 | -3/2 | -5/2 |
|
Т3 |
d3 |
d1 |
1 |
|
e1 |
-3/2 | -5/2 | 0 |
|
e2 |
11/2 | 21/2 | 0 |
|
e3 |
1/2 | 3/2 | 0 |
|
х1 |
1 | 2 | 0 |
|
х2 |
1/2 | 1/2 | 0 |
|
x2 |
1/2 | 1/2 | 1 |
|
d2 |
3/2 | 5/2 | 0 |
|
x1 |
1 | 2 | 1 |
| D | 5/2 | 7/2 | 0 |
|
Т4 |
e1 |
d1 |
1 |
|
d3 |
0 | ||
|
x2 |
1 | ||
|
d2 |
0 | ||
|
x1 |
1 | ||
| D | -5/3 | -2/3 | 0 |
