РефератБар.ру: | Главная | Карта сайта | Справка
Решение многокритериальной задачи линейного программирования. Реферат.

Разделы: Экономика и управление | Заказать реферат, диплом

Полнотекстовый поиск:




     Страница: 2 из 3
     <-- предыдущая следующая -->

Перейти на страницу:
скачать реферат | 1 2 3 







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

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

Т3
e1
e3
1

x1
1
1/2
5

e2
-3
2
34

x2
-1/2
-1/2
10

e4
2

10



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

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



Т4
e4
e3
1

x1



10

e2



19

x2



15/2

e1



-5



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


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

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

где черта сверху уd,eиDозначает, что этивеличины приведены к точкех, = (1)n.
По существу, (8) – ЗЛП размера (R+m)xn (D®max), аее решение позволит найти все грани, составляющиеp-множество Dxp.
Составляем с-таблицу, не учитывая пассивные ограничения, т.еe1:



Т1
х1
х2
1

e2
-1
-1
2

e3
5
1
-6

e4
1
-1
0

х1
1
0
-1

х2
0
1
-1

d1
1
-2
1

d2
1
1
-2

d3
-1
4
-3

D

1

3
-4



В начале решается усеченная ЗЛП (под чертой):



Т2
х1
d1
1

e1
-3/2
1/2
3/2

e2
11/2
-1/2
-11/2

e3
1/2
1/2
-1/2

х1
1
0
-1

х2
1/2
-1/2
-1/2

x2
1/2
-1/2
1/2

d2
3/2
-1/2
-3/2

d3
1
-2
-1

D
5/2
-3/2
-5/2



Т3
d3
d1
1

e1
-3/2
-5/2
0

e2
11/2
21/2
0

e3
1/2
3/2
0

х1
1
2
0

х2
1/2
1/2
0

x2
1/2
1/2
1

d2
3/2
5/2
0

x1
1
2
1

D
5/2
7/2
0



Т4
e1
d1
1

d3



0

x2



1

d2



0

x1



1

D
-5/3
-2/3
0



e1ОDxp, так какDmax= 0.

Данный метод построения множества Dxpобладает недостатком, связанным с разрушением области допустимых решений (ОДР) Dxпри переносе ее граней в х,. Действительно, вершины области Dxв преобразованной модели никак не отражены, а именно одна из них может составитьp-множество в случае его совпадения с оптимальным решением. Такое совпадение возможно, если все ч-критерии достигают максимум на одной вершине. Физически это значит, что они слабопротиворечивы – угол при вершине д-конуса приближается к 180°(градиенты ч-критериев имеют практически совпадающие направления). Данный случай имеет место, если вp-множество не вошла ни одна из граней ОДР Dx. Следовательно,p-множество совпадает с оптимальным решением. Для определенияp-множества решается обычная ЗЛП с одним из ч-критериев. Если при этом получено множество оптимальных решений, то решается ЗЛП с другим ч-критерием. Пересечение оптимальных решений и являетсяp-множеством. Для ЛПР указание на то, что некоторая граньei=eipОDxpp-оптимальна, является толькообобщенной информацией.


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

Наиболее естественным и разумным решением мк-задачи было бы органическое объединение всех ч-критериев в виде единой ЦФ. Иногда это удается сделать путем создания более общей модели, в которой ч-критерии являютсяаргументамиболее общей целевой функции, объединяющей в себе все частные цели операции. На практике этого редко удается достигнуть, что, собственно, и является основной причиной появления проблемы многокритериальности. Однако наиболее распространенный подход к решению проблемы пока остается все-таки один: тем или иным путем свести решение мк-задачи к решению однокритериальной задачи. В основе подхода лежит предположение о существовании некойфункции полезности, объединяющей в себе ч-критерии, но которую в явном виде, как правило, получить не удается. Получение наиболее обоснованной «свертки» ч-критериев является предметом исследований нового научного направления, возникшего в связи с проблемой многокритериальности -теории полезности. В данной работе будут рассмотрены некоторые подходы, позволяющие получить варианты решения мк-задач при тех или иных посылках и которые лицо принимающее решение (ЛПР) должно рассматривать как альтернативные при принятии окончательного решения и которые, конечно, должны удовлетворять необходимому условию-p-оптимальности.


4.1.Метод гарантированного результата

При любом произвольном решении хОDxкаждый из ч-критериев примет определенное значение и среди них найдется, по крайней мере, один, значение которого будетнаименьшим:

Метод гарантированного результата (ГР) позволяет найти такое (гарантированное) решение, при котором значение «наименьшего» критерия станет максимальным. Таким образом, целевая функция (ЦФ) является некоторой сверткой ч-критериев (9), а МЗЛП сводится к задаче КВП (кусочно-выпуклого программирования) при ОДР Dx, заданной линейными ограничениями.
Исходные условия записываем в каноническом виде:
d1= х1- 2х2-j+ 2,
d2= х1+ х2-j+ 4,
d3= -х1+ 4х2-j+ 20,
e1= -х1- х2+ 15,
e2= 5х1+ х2- 1,
e3= x1- х2+ 5,

потом в виде с-таблицы:



Т1
х1
х2
j
1

e1
-1
-1
0
15

e2
5
1
0
-1

e3
1
-1
0
5

d1
1
-2
-1
2

d2
1
1
-1
4

d3
-1
4
-1
20


Вводя в базис переменнуюj(d1«j), получаем обычную ЗЛП при максимизации ЦФj.



Т2
х1
х2
d1
1

e1
-1
-1
0
15

e2
5
1
0
-1

e3
1
-1
0
5

j
1
-2
-1
2

d2
0
3
1
2

d3
-2
6
1
18



Т3
d3
x2
d1
1
bi/ais

e1
1/2
-4
-1/2
6
6/4

e2
-5/2
16
5/2
44
-

e3
-1/2
2
2
14
-

j
-1/2
1
-1/2
11
-

d2
0
3
-1
2
-

х1
-1/2
3
1/2
9
-



Т4
d3
e1
d1
1

x2




3/2

e2




68

e3




17

j
-3/8
-1/4
-5/8
25/2

d2




13/2

х1




27/2




     Страница: 2 из 3
     <-- предыдущая следующая -->

Перейти на страницу:
скачать реферат | 1 2 3 

© 2007 ReferatBar.RU - Главная | Карта сайта | Справка