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

  • Просмотров 318
  • Скачиваний 13
  • Размер файла 50
    Кб

следовательно 4 – пассивное ограничение. 3.2.Определение -множества с-методом. При подготовке решения для ЛПР интерес будет представлять информация обо всем множестве -оптимальных (эффективных) решений Dx. Графический метод позволяет сформулировать довольно простой подход к определению множества Dx. Суть этого подхода в следующем. Решая усеченную задачу линейного программирования, устанавливаем факт существования

д-конуса ( max > 0). Поскольку для линейных ЦФ конфигурация д-конуса не зависит от положения его вершины х,, то, помещая ее на границу i области Dx, решаем усеченную ЗЛП с добавлением i, соответствующего i-му участку границ Dx. Вырождение д-конуса в точку х, будет признаком -оптимальности и всех других точек данной грани. С помощью с-метода указанная процедура легко проделывается для пространства любой размерности n. Неудобство

указанного метода состоит в том, что потребуется на каждой грани ОДР Dx найти точку х, (по числу граней Dx) сформулировать и решить столько же ЗЛП размера Rxn. Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х, = (1)n и в нее же параллельно себе перенести грани, составляющие границы Dx Приведенные к точке х, = (1)n приращения -r и невязки i запишутся в виде: (8) где черта сверху у ,  и 

означает, что эти величины приведены к точке х, = (1)n. По существу, (8) – ЗЛП размера (R+m)xn (max), а ее решение позволит найти все грани, составляющие -множество Dx. Составляем с-таблицу, не учитывая пассивные ограничения, т.е 1: Т1 х1 х2 1 2 -1 -1 2 3 5 1 -6 4 1 -1 0 х1 1 0 -1 х2 0 1 -1 1 1 -2 1 2 1 1 -2 3 -1 4 -3  1 3 -4 В начале решается усеченная ЗЛП (под чертой): Т2 х1 1 1 1 -3/2 1/2 3/2 2 11/2 -1/2 -11/2 3 1/2 1/2 -1/2 х1 1 0 -1 х2 1/2 -1/2 -1/2 x2 1/2 -1/2 1/2 2 3/2 -1/2 -3/2 3 1 -2 -1  5/2 -3/2 -5/2 Т3 3

1 1 1 -3/2 -5/2 0 2 11/2 21/2 0 3 1/2 3/2 0 х1 1 2 0 х2 1/2 1/2 0 x2 1/2 1/2 1 2 3/2 5/2 0 x1 1 2 1  5/2 7/2 0 Т4 1 1 1 3 0 x2 1 2 0 x1 1  -5/3 -2/3 0 1 Dx, так как max = 0. Данный метод построения множества Dx обладает недостатком, связанным с разрушением области допустимых решений (ОДР) Dx при переносе ее граней в х,. Действительно, вершины области Dx в преобразованной модели никак не отражены, а именно одна из них может составить -множество в случае его совпадения с

оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы – угол при вершине д-конуса приближается к 180 (градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если в -множество не вошла ни одна из граней ОДР Dx. Следовательно, -множество совпадает с оптимальным решением. Для определения