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

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

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

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

(5)

(6)

(7)

Смысл задачи линейного программирования нетрудно понять, если учесть, что ^r – это приращение ч-критерия L^r, получаемое при смещении решения х^, в точку х. Тогда, если после решения ЗЛП окажется D_max = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (D_max = 0), если не допускать уменьшения любого из других ( ^r 0). Но это и есть условие -оптимальности х^,. Если же при решении окажется, что   0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других ( ^r 0), и значит х^,  D^_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) на предмет -оптимальности:

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

¹ = x₁ - 2x₂ + 1

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

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

 = x₁ + 3x₂ – 14,

₁ = 15 - x₁ - x₂

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

D_x ₃ = 5 + x₁ - x₂

₄ = 20 - x₂

x_j  0.

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

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

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

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

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

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

Скачать

20768

22

2

... = -x1 + 2x2 + 2, L2 = x1 + x2 + 4, L3 = x1 - 4x2 + 20, и система ограничений: x1 + x2 £ 15,  5x1 + x2 ³ 1,  -x1 + x2 £ 5, x2 £ 20, "xj ³ 0. 2. Решение многокритериальной задачи линейного программирования графическим методом. 2.1.Формальное условие и сведение к ЗЛП Чтобы можно было ...

Оптимизационные методы решения экономических задач

Скачать

23385

0

0

... конечные результаты при минимальных затратах ресурсов. Математический инструментарий, позволяющий решать экономические задачи оптимального типа, называется программированием. Различают линейное и нелинейное программирование. На практике наибольшее распространение получило линейное программирование. Методы линейного программирования в математике известны под названием общей задачи линейного ...

Линейное программирование

Скачать

63048

19

8

... 4 X1 + 2 X2 + 0 X3 + X4 = 19 0 X1 + 1 X2 + 1 X3 + X5 = 8 1 X1 + 2 X2 + 0 X3 + X6 = 24 Получили задачу: 4X1+2X2+X4 = 19 X2 + X3 +X5 = 8 X1+2X2 +X6 =24   3.3 Решаем задачу путем сведения к задаче линейного программирования: Xi≥0 ; 0-Z= -3X1- -7X2- -2X3 Приведем задачу к канонической форме. Задача ...

Теория принятия решений

Скачать

83422

1

0

... условиях определенности математическое программирование дает точное решение поставленной задачи. Поэтому необходимости выбирать из нескольких вариантов попросту нет. Таким образом, в условиях определенности "Теория принятия решений" не используется, такими задачами занимается математическое программирование. 2)  ЛПР знает вероятность реакции окружающей среды на выбор им той или иной альтернативы. ...