Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Запишем систему неравенств Dx в форме с-таблицы:

|Т1 |х1 |х2 |1 |bi/a|bi/a|
| | | | |is |is |
|(1 |-1 |-1 |15 |15 |15 |
|(2 |5 |1 |-1 |1/5 |1 |
|(3 |1 |-1 |5 |- |5 |
|(4 |0 |-1 |20 |- |20 |

|Т2 |(1 |x2 |1 | | | | |Т2’ |x1 |(2 |1 |
|х1 |-1 |-1 |15 | | | | |(1 |4 |-1 |14 |
|(2 |-5 |-4 |74 | | | | |x2 |-5 |1 |1 |
|(3 |-1 |-2 |20 | | | | |(3 |2 |-1 |4 |
|(4 |0 |-1 |20 | | | | |(4 |1 |-1 |19 |

ОП – получен, следовательно ОП – получен, следовательно х2 и (1 – активные ограничения; x1 и (2 – активные ограничения;

из Т2 получаем:

|Т3 |(1 |(3 |1 |
|x1 |1 |1/2 |5 |
|(2 |-3 |2 |34 |
|x2 |-1/2|-1/2|10 |
|(4 |2 |Ѕ |10 |

отсюда делаем вывод, что (3 – активное ограничение;

из Т3 получаем:

|Т4 |(4 |(3 |1 |
|x1 | | |10 |
|(2 | | |19 |
|x2 | | |15/2 |
|(1 | | |-5 |

Опорный план не получен, следовательно (4 – пассивное ограничение.

3.2.Определение (-множества с-методом.

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

Существенно сократить объем вычислений можно путем выбора вершины д-конуса в фиксированной точке х, = (1)n и в нее же параллельно себе перенести грани, составляющие границы Dx

Приведенные к точке х, = (1)n приращения (-r и невязки (i запишутся в виде:

[pic] где черта сверху у (, ( и ( означает, что эти величины приведены к точке х, = (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. Следовательно, (-множество совпадает с оптимальным решением. Для определения (-множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и является (-множеством. Для
ЛПР указание на то, что некоторая грань (i = (i( ( Dx(
(-оптимальна, является только обобщенной информацией.

4.Определение альтернативных вариантов многокритериальной задачи

Рекомендуем скачать другие рефераты по теме: рефераты по психологии, рефераты.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки