Xreferat.com » Рефераты по экономико-математическому моделированию » Решение многокритериальной задачи линейного програмирования

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

д-конус в любой точке стороны e1, убеждаемся, что каждая из точек p-оптимальна, значит вся сторона e1 составляет p-множество.


3.Определение Парето-оптимального множества

с-методом


3.1.Удаление пассивных ограничений

Перед построением p-множества из системы ограничений должны быть удалены пассивные ограничения. Пассивным будем называть неравенство (п-неравенство), граница которого не является частью границ области Dx, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы Dx, назовем активными (а-неравенства).

Чтобы грани не были включены в Dxp, не имея никакого отношения к Dxp, неравенство e1 должно быть удалено из исходной системы ограничений. Условием для исключения неравенства ei і 0 из системы является несовместность (или вырожденность) данной системы неравенств при условии ei = 0. Геометрически это означает, что граница ei = 0 неравенства ei і 0 не пересекается с областью Dx или имеет одну общую точку. Если граница ei = 0 имеет общую угловую точку с Dx (вырожденность), то с удалением п-неравенства ei і 0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы Dx.

В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки x О Dx будут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы.

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


Т1

х1

х2

1

bi/ais

bi/ais

e1

-1 -1 15 15 15

e2

5 1 -1 1/5 1

e3

1 -1 5 - 5

e4

0 -1 20 - 20

Т2

e1

x2

1



Т2

x1

e2

1

х1

-1 -1 15



e1

4 -1 14

e2

-5 -4 74



x2

-5 1 1

e3

-1 -2 20



e3

2 -1 4

e4

0 -1 20



e4

1 -1 19

ОП – получен, следовательно ОП – получен, следовательно

х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 (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 О Dxp p-оптимальна, является только обобщенной информацией.


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

Решение ЗЛП приводит к конечной с-таблице Т4. Видно, что полученное гарантированное решение х p-оптимально, поскольку введение в базис любой свободной переменной (т.е. ее увеличение) приведет к снижению j - нижнего уровня ч-критериев ("сj < 0). Из таблицы также видно, что решение х0=(27/2; 3/2) находится на грани e4, при этом значения ч-критериев равны (находим по формуле Lr(xr) = j + dr):

L1 = L3 = j = 25/2

L2 = j + d2 = 25/2 + 13/2 = 19

LS = 88/2 = 44

x° = ( 27/2; 3/2)

Если бы в строке j имелись нули, то это означало бы, что одну из соответствующих переменных можно ввести в базис (увеличить без снижения уровня j). Это могло бы привести и к увеличению приращения dr для некоторого ч-критерия, находящегося в базисе.

4.2.Метод линейной свертки частных критериев

Линейная свертка ч-критериев получается как х сумма с некоторыми весовыми коэффициентами mr:



где



Меняя порядок суммирования и вводя обозначения cj и c0, окончательно получим:



Коэффициенты веса обычно получаются путем опроса экспертов из соответствующей предметной области. Поскольку вектор m = (mr) – суть вектор-градиент ЦФ Lm(x), то предполагается, что он указывает направление к экстремуму неизвестной функции полезности. Положительная сторона такого подхода – несложность, не всегда компенсирует его серьезный недостаток – потерю физического смысла линейной свертки разнородных ч-критериев. Это затрудняет интерпретацию результатов, поэтому полученное таким путем решение, следует рассматривать только как возможный (альтернативный) вариант решения ЛПР. Для его сравнительного анализа следует привлекать

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: