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

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

2.1.Формальное условие и сведение к ЗЛП

Чтобы можно было проверить условие (4) (L^r(x) ³ L^r(x’),"r) для некоторой произвольно взятой точки х^,, не прибегая к попарному сравнению с другими, условие p-оптимальности (4) переформулируем в виде следующей задачи линейного программирования:

Смысл задачи линейного программирования нетрудно понять, если учесть, что d^r – это приращение ч-критерия L^r, получаемое при смещении решения х^, в точку х. Тогда, если после решения ЗЛП окажется D_max = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (D_max = 0), если не допускать уменьшения любого из других (" d^r³ 0). Но это и есть условие p-оптимальности х^,. Если же при решении окажется, что D ³ 0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других  (" d^r³ 0), и значит х^, Ï D^p_x.

Теперь перейдем к решению нашей задачи:

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

L₂ = x₁ + x₂ + 4,

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

x₁ + x₂ £ 15,

 5x₁ + x₂ ³ 1,

 -x₁ + x₂ £ 5,

x₂ £ 20,

"x_j ³ 0.

Проверим некоторую точку х^, = (5; 3) (эта точка принадлежит области Dx) на предмет p-оптимальности:

Запишем ЗЛП в каноническом виде:

d¹ = x₁ - 2x₂ + 1

D_x^k d² = x₁ + x₂ - 8

d³  = -x₁ + 4x₂ - 7

D = x₁ + 3x₂ – 14,

e₁ = 15 - x₁ - x₂

e₂ = 5x₁ + x₂ – 1,

D_x e₃ = 5 + x₁ - x₂

e₄ = 20 - x₂

"x_j ³ 0.

и в форме с-таблицы:

Применяя с-метод, после замены d³« х₂, получаем:

Видим, что опорный план не получен, следовательно делаем еще одну замену: e₁ « х₁:

 В Т₃ получен опорный план. Так как при этом D>0, то, следовательно, система ч-критериев не противоречива и существует некоторая область, смещение в которую решения х^, способно увеличить, по крайней мере, один ч-критерий без уменьшения значений остальных. Эта область и есть конус доминирования - д – конусом D_x^k (на рисунке выделен штриховкой). При R > n д-конус может выродиться в точку х^, (вершина д-конуса). Получено целое множество оптимальных решений, извлекаемое из Т₃: х⁰ = ( 29/3 ; 16/3 ). Таким образом, решение х^, = ( 5; 3) не является p-оптимальным, так как его удалось улучшить (D_max>0). Помимо установления факта неэффективности решения х^,, рассмотренный метод позволил определить ближайшее к нему p-оптимальное решение.

Похожие работы

Блочно-симметричные модели и методы проектирования систем обработки данных

Скачать

158931

0

1

... дискретного программирование для решения задач проектирование систем обработки данных. -  Сформулированы задачи диссертационного исследования. 2. БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ В данном разделе рассматриваются общая постановка блочно-симметричной задачи дискретного программирования, её особенности и свойства. Разработан общий подход решения задач ...