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

"x_j ³ 0.

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-оптимальное решение.

2 .2. Графическое определение p -множества

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