Реферат: Решение многокритериальной задачи линейного програмирования
исходные данные:
L1 = x1 - 2x2 + 2,
L2 = x1 + x2 + 4,
L3 = -x1 + 4x2 - 20,
в каноническом виде (после подстановки точки (5;3))
d1 = x1 - 2x2 + 1, (5 - 2*3 + 1= 1)
Dx k 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 , назовем активными (а-неравенства).
Чтобы грани не были включены в Dx p , не имея никакого отношения к Dx p , неравенство 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-оптимальных (эффективных) решений Dx p . Графический метод позволяет сформулировать довольно простой подход к определению множества Dx p . Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования д-конуса ( Dmax > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х, , то, помещая ее на границу ei области Dx , решаем усеченную ЗЛП с добавлением ei , соответствующего i-му участку границ Dx . Вырождение д-конуса в точку х, будет признаком p-оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство указанного метода состоит в том, что потребуется на каждой грани ОДР Dx найти точку х, (по числу граней Dx ) сформулировать и решить столько же ЗЛП размера R xn .
Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х, = (1)n и в нее же параллельно себе перенести грани, составляющие границы Dx