---

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

При совершенствовании ССМП значительное место отводится зада­чам формирования эффективных управленческих решений с помощью за­дачи дискретной векторной оптимизации вида:

 

где JV(x) - (W_l(x),W₂(x),...,W_k(x)) - вектор целевых функций (показателей эффективности) решаемой задачи; <р(х) = ((р₁(х),<р₂(х),...,(р_т(х)) - ограни­чения, накладываемые на переменные рассматриваемой задачи; х = (х_{,х₂х_п) - вектор искомых решений.

Под эффективным решением в данной работе понимается решение, являющееся наилучшим (предпочтительным) по сравнению с остальными решениями. Согласно теории оптимизации решений по Парето [23, 24] та­ких решений может быть более одного. Поэтому в результате решения многокритериальных задач формируется множество компромиссных (эф­фективных, оптимальных по Парето) решений, из которых лицо прини­мающее решение (ЛПР) выбирает конкретный вариант, наиболее полно удовлетворяющий неформализованным целям или интересам данного ЛПР.

В работе [23] приведена значительная библиография работ, посвя­щенных методам решения линейных задач вида (2.1) - (2.3). Как отмечено в работе [25], решение однокритериальных «задач о назначениях» практи­чески значимой размерности традиционными численными методами тре­бует значительных затрат машинного времени.

В работе [26] утверждается, что использование линейной свертки критериев в задачах линейного дискретного программирования приводит к потере 40% точек паретооптимального множества решения таких задач.

В связи с тем, что множество допустимых решений задачи (2.1) - (2.3), которое определяется как:

X = {х(р(х)>0,х_х,х₂,...,х_п є{0,1,2,3,...},                                          (2.4)

является дискретным множеством, то множество достижимости G [27] этой задачи также будет дискретным множеством. Для дискретного мно­жества X не выполняются условия выпуклости множества, что не позво­ляет корректным образом применять при решении задачи (2.1) - (2.3) клас­сический метод линейной свертки целевых функций [26], основанный на

применении теоремы С.Карлина [28].

Предположим, что множество (2.4) содержит конечное число векто­ров x⁽'v = 1 ,N, сформированных путем полного перебора значений векто­ров x^(,) [19], или использования рандомизированных методов генерации таких векторов [21], удовлетворяющих условиям (2.2) - (2.3).

Формируя для каждого вектора є X значения целевых функций W_u = W_l(x^(l)),W_2l -fV₂(x^(,)W_kl=W_k(x^{l)), i-,N, получаем задачу, ко­торая в практических приложениях конкретизируется как:

(W_u,W₂„...,ir_n)-+ms&,

i=,N

(W_r+u,W_r+2„...,W_h)^ min                                                            ⁽²-⁵⁾

i=, N

Как известно [27, 23], оптимизация решений по Парето основывается на выделении во множестве G наилучших (паретооптимальных) точек с использованием отношения предпочтения, заданного на множестве воз­можных решений. В нашем случае, при решении задачи (2.5) можно ут­верждать, что і -ая точка этого множества является предпочтительнее, чем s-ая точка множества G, если для этой пары точек при s Фі одновремен­но выполняются все условия вида:

W_Jt>W_JS, j = й,

Wj,<W_js, j = r + l,k, і Є (IN), se(UV), i*s                                               ^(2-6)

причем хотя бы одно неравенство строгое.

Последовательное сравнение возможных решений между собой с ис­ключением из рассмотрения непредпочтительных решений составляет ос­нову метода решения задачи (2.5). Отметим, что множество эффективных (компромиссных) решений (множество Парето) состоит из несравнимых между собой вариантов решений [29].

В работах [23, 29] для выделения оптимальных по Парето точек в континуальном множестве G использовалось понятие ортанта, который представляет собой выпуклый острый конус без вершины, порожденный единичными ортантами пространства целевых функций (оценок). При этом утверждается, что рассматриваемая точка является паретооптимальной то­гда и только тогда, когда во внутренность ортанта, сдвинутого в эту точку, не попадет ни одна из точек множества G.

В связи с дискретностью задачи (6) для выделения в нем эффектив­ных точек будем использовать выпуклый многогранный ортогональный конус, сдвинутый из начала координат в вершину рассматриваемой точки (W_]s,W_2s,—,W_rs) ^є G, который формально определим как:

с^к, = i(W_uW.2W_k)eE^k I (Ж, > W_JS, j = h~r)&

&(fF_y <W_JSJ = r + ,k)}> ^e(UV).                                                               ^(2J)

Таким образом, разработанный численный метод решения многокри­териальных задач дискретного нелинейного программирования включает в себя следующие типовые этапы получения паретооптимальных решений:

1°. Построение приближенного представления X множества допус­тимых решений задачи с использованием условий (2.2) - (2.3).

2°. Формирование в пространстве критериев (б) соответствующего приближенного представления G множеств достижимости G (множества оценок) путем вычисления значений критериев (2.1).

3°. Выделение в множестве G подмножества паретооптимальных (эффективных, неулучшаемых) решений с использованием понятия орто­гонального конуса вида (2.7).

В предлагаемом методе, существенное значение, с точки зрения точ­ности получаемых результатов, имеет объем N выполняемых статистиче­ских экспериментов. Для получения приемлемых для практики результа­тов в данном методе предлагается использовать следующее правило оста­нова: «Процесс последовательного выполнения этапов 1°— 3° завершается, если при N статистических экспериментах достигается заданная точность сходимости», т.е. полученное решение при N статистических эксперимен­тах отличается от решения при N -1 статистических экспериментах в пре­делах заданной точности.

В результате применения предлагаемого метода, ЛПР, для после­дующего выбора приемлемого варианта, выдается таблица результатов, включающая в себя номер паретооптимального варианта, соответствую­щие ему значения целевых функций и значения искомых переменных ре­шаемой задачи.

 

 

Вся работа доступна по ссылке

https://mydisser.com/ru/catalog/view/32205.html