Решение многокритериальной задачи линейного програмирования — страница 3
1, -x1 + x2 5, x2 20, xj 0. 2. Решение многокритериальной задачи линейного программирования графическим методом. 2.1.Формальное условие и сведение к ЗЛП Чтобы можно было проверить условие (4) (Lr(x) Lr(x’),r) для некоторой произвольно взятой точки х,, не прибегая к попарному сравнению с другими, условие -оптимальности (4) переформулируем в виде следующей задачи линейного программирования: (5) (6) (7) Смысл задачи линейного программирования нетрудно понять, если учесть, что r – это приращение ч-критерия Lr, получаемое при смещении решения х, в точку х. Тогда, если после решения ЗЛП окажется max = 0, то это будет означать, что ни один из ч-критериев нельзя увеличить (max = 0), если не допускать уменьшения любого из других ( r 0). Но это и есть условие -оптимальности х,. Если же при решении окажется, что 0, то значит какой-то ч-критерий увеличил свое значение без ухудшения значений других ( r 0), и значит х, Dx. Теперь перейдем к решению нашей задачи: L1 = -x1 + 2x2 + 2, L2 = x1 + x2 + 4, L3 = x1 - 4x2 + 20, x1 + x2 15, 5x1 + x2 1, -x1 + x2 5, x2 20, xj 0. Проверим некоторую точку х, = (5; 3) (эта точка принадлежит области Dx) на предмет -оптимальности: Запишем ЗЛП в каноническом виде: 1 = x1 - 2x2 + 1 Dxk 2 = x1 + x2 - 8 3 = -x1 + 4x2 - 7 = x1 + 3x2 – 14, 1 = 15 - x1 - x2 2 = 5x1 + x2 – 1, Dx 3 = 5 + x1 - x2 4 = 20 - x2 xj 0. и в форме с-таблицы: Т1 х1 х2 1 1 -1 -1 16 2 5 1 -4 3 1 -1 100 4 0 -1 10 1 1 -2 -4 2 1 1 -12 3 -1 1 -8 1 4 -24 Применяя с-метод, после замены 3 х2, получаем: Т2 х1 1 1 1 -3/2 ½ 29/2 2 11/2 -1/2 -1/2 3 1/2 ½ 9/2 4 -1/2 ½ 39/2 X2 1/2 -1/2 1/2 2 3/2 -1/2 -15/2 3 1 -2 -5 5/2 -3/2 -25/2 Видим, что опорный план не получен, следовательно делаем еще одну замену: 1 х1: Т3 3 1 1 x1 29/3 2 316/6 3 56/6 4 88/6 x2 16/3 2 7 3 14/3 -5/3 -2/3 70/6 В Т3 получен опорный план. Так как при этом >0, то, следовательно, система ч-критериев не противоречива и существует некоторая область, смещение в которую решения х, способно увеличить, по крайней мере, один ч-критерий без уменьшения значений остальных. Эта область и есть конус доминирования - д – конусом Dxk (на рисунке выделен штриховкой). При R > n д-конус может выродиться в точку х, (вершина д-конуса). Получено целое множество оптимальных решений, извлекаемое из Т3: х0 = ( 29/3 ; 16/3 ). Таким образом, решение х, = ( 5; 3) не является -оптимальным, так как его удалось улучшить (max>0). Помимо установления факта неэффективности решения х,, рассмотренный метод позволил определить ближайшее к нему -оптимальное решение. 2.2. Графическое определение -множества Сначала необходимо построить график. Для построения графика необходимы следующие данные: исходные данные: L1 = x1 - 2x2 + 2, L2 = x1 + x2 + 4, L3 = -x1 + 4x2 - 20, в каноническом виде (после подстановки точки (5;3)) 1 = x1 - 2x2 + 1, (5 -
Похожие работы
- Доклады
- Рефераты
- Рефераты
- Рефераты
- Контрольные