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

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

Опорный план не получен, следовательно 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  запишутся  в  виде:

(8)

 

где  черта  сверху  у  d,  e  и  D  означает,  что  эти  величины  приведены  к  точке        х, = (1)n.

По  существу,  (8) – ЗЛП  размера  (R+m)xn  (D®max),  а  ее  решение  позволит  найти  все  грани,  составляющие  p-множество  Dxp.

Составляем  с-таблицу,  не  учитывая  пассивные  ограничения,  т.е  e1:

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

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

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

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

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

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

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

(9)

Метод  гарантированного  результата  (ГР)  позволяет  найти  такое  (гарантированное)  решение,  при  котором  значение  «наименьшего»  критерия  станет  максимальным. Таким  образом,  целевая  функция  (ЦФ)  является  некоторой  сверткой  ч-критериев (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,

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

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

Решение  ЗЛП  приводит  к  конечной  с-таблице  Т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:

	(9)

где

	(10)

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

	(11)

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

Наиболее  приемлемой  линейная  свертка  ч-критериев  может  оказаться  в  том  случае,  когда  ч-критерии  однородны  и  имеют  единый  эквивалент,  согласующий  их  наиболее  естественным  образом.

На  содержательном  уровне  данная  МЗЛП  состоит  в  необходимости  принятия  такого  компромиссного  решения  (плана  выпуска  продукции)  xk Î Dx,  которое  обеспечит,  по  возможности,  наибольшую  суммарную  выручку  L1(x)  от   реализации  произведенной  продукции;  наименьший  расход  ресурсов  i-го  вида  Lpl (x)  (i = 1; m);  минимальные  налоговые  отчисления  от  прибыли LH(x)  (или  общей  выручки).

Указанные  цели  носят  противоречивый  характер,  и  фактически  мы  имеем  МЗЛП  с  m+2 –мя  ч-критериями  (m – количество  видов  потребляемых  ресурсов). ОДР  обусловлена  ресурсными  ограничениями  и  условиями  неотрицательных  переменных:

где  aij – расход  ресурса  i-го  вида  для  выпуска  1  единицы  продукции  j-го  вида  (j=1,n);

 bi – запас  ресурса  i-го  вида;

ei – остаток  ресурса  i-го  вида  при  плане  выпуска  x = (xj)n. Ч-критерии  однородны,  если  они  могут  быть  сведены  к  единой  мере  измерения. В  качестве  такой  меры  можно  взять  денежный  эквивалент. Тогда  m+2  ч-критерия  могут  быть  с  помощью  линейной  свертки  сведены  к  трем:

общая   выручка  (руб.):

общая  экономия  ресурсов (руб.):

налоговые  отчисления  (руб.):

где  cj – выручка  от  реализации  1  ед.  продукции  j-го  вида  (цена);  si – стоимость  (цена)  1  ед.  ресурса  i-го  вида  (i = 1;m);  Пj – прибыль  от  реализации  1  ед.  продукции  j-го  вида  (j = 1;n);  aj – доля  (процент  налоговых  отчислений  от  прибыли  (выручки).

В  заключение  заметим,  что  коэффициенты mr  не  обязательно  должны  удовлетворять  условию  (10),  но  обязательно  должны  быть  положительными,  если  все  ч-критерии  максимизируются.

Перейдем  к  решению:

L1 max = 17

L2 max = 19

L3 = 5

LS = 41

5. Составление  сводной  таблицы.

Окончательное  решение  сводится  в  таблицу,  где  записываются  альтернативные  варианты: